Globus Toolkit 5.0.3 on Cygwin 1.7

Cygwin patches (see earlier post) did not make it into GT5.0.3. The patch requirement is therefore the same as for GT5.0.2 (see earlier post). These patches may make it into future distributions.

I took slightly more detailed notes during the 5.0.3 build process, so you can now find more details about which packages require patches here.

Faster median calculation and generic rank selections in MatLab via nth_element

Update (2011-09-03): I've added new functions to the release that edit the arrays in-place. This is not good Matlab style but gives significant speedups for the very performance conscious. It appears it may be useful for me to add a multithreaded version as well, so this may come in an upcoming release.

C++ std::nth_element is a standard specification for an efficient rank selection algorithm. This algorithm can be used to solve a number of rank selection problems efficiently.

One example is median finding. A naive median finding algorithm, as implemented in MatLab (at least up to R2010a) is to sort the entire list of values and then just take the value in the middle position. But sorting the entire list is overkill; it is more efficient to do a sort of partial sort just to the point where the desired value is in the correct position. The version of this typically implemented in nth_element is known as quickselect or Hoare's Selection Algorithm. See Wikipedia: Selection algorithm for more details.

I find that a MatLab fast_median function based on nth_element runs about twice as fast as the native MatLab median function based on sort. Theoretically, the average complexity of quickselect is O(n), while the best performance complexity of the sort based method is O(n log n).

Finding median values is central to robust statistics, for example calculating the Median Absolute Deviation.

If you are interested, my MatLab wrapping of nth_element and an example implementation of fast_median are available at MatLab Central File Exchange.

Globus Toolkit 5.0.2 on Cygwin 1.7

Updates (2011-02-20): Cygwin patches did not make it into GT5.0.3, but they may make it into a future release.

Updates (2010-12-08): Binghamton University TeraGrid has written up instructions for applying the patches and getting GT compiled. Also, it appears new versions of GT will be coming out over the next few months. I plan to check them out for Cygwin compatibility.

If you are interested in compiling Globus Toolkit 5.0.2 on Cygwin, I have some simple patches that seem to get the job done. Perhaps they will make it into the next release. For now: http://lists.globus.org/pipermail/gt-dev/2010-September/001885.html

Note that I built this on Cygwin 1.7; Cygwin 1.5 will probably not work. Also you must have the gcc4.x Cygwin packages (C and C++) installed. Getting GT to build on gcc3.x is probably not much more work, but going with gcc4 is easier than worrying about unrecognized compiler flags all over the place.

You also need to specify the flag: --with-buildopts="-static=1" when running the main configure script. Building GT on Cygwin with dynamic linking is certainly beyond me, and is a pretty big undertaking, so this tells it to use only static linking. I recommend --with-buildopts="-verbose -static=1" so you can also see what is going on.

(For the record, on dynamic linking: I tried adding some flags to configure.ac or configure.in to let autoconf know that we wanted to make DLLs and do dynamic linking. But trying to run a modern version of autoreconf generated configure scripts that don't work with the GT package. Even if the build worked, this probably wouldn't be a good idea as making DLLs properly requires going through all the source and making sure data exports are handled correctly. At least one package (globus_libtool) is DLL ready and already generates a DLL and RTL properly, so we know it all works theoretically once the individual libraries are DLL ready. There may be other subpackages that are DLL ready, but they will probably have to be handled one at a time. Unfortunately, GPT doesn't really offer a method to build the whole Globus Toolkit with some parts statically linked and some dynamic.)

If you get a build failure with an error like "fork()" or "vfork()" "resource temporarily unavailable", this means your machine ran out of processes while building (due to what I'm going to call a "process leak" bug). Basically just rerun make and it should get farther each time before crashing, until finally it gets all the way through. Or build GT in smaller chunks; if you are just trying to get proxy certificate running you only really need "make gsi-myproxy gsi-openssh".

You may also have to circumvent GPT's somewhat outdated Perl libraries. If you have a problem getting Archive::Tar to open some of the source packages, then you should install the Cygwin CPAN package and then use that to install an updated version of Archive::Tar. You may then need to hide GPT's versions under $GLOBUS_LOCATION/sbin/perl.

Feel free to ping me with any questions/thoughts.

Compiling GnuCAP in CygWin

Update: GnuCAP is now available as an official CygWin package, as is some dialect of SPICE.

Very simple patch to get recent development snapshots of GnuCAP to compile in CygWin:

--- md.h.bak    2010-03-19 00:21:26.030900000 -0700
+++ md.h        2010-03-19 00:34:18.810900000 -0700
@@ -100,6 +100,12 @@
  #define MS_DLL
#endif
/*--------------------------------------------------------------------------*/
+#ifdef __CYGWIN__
+  #ifndef RTLD_LOCAL
+    #define RTLD_LOCAL 0
+  #endif
+#endif
+/*--------------------------------------------------------------------------*/
/* some convenient names */
typedef std::complex COMPLEX;
typedef std::pair DPAIR; 

Dapple

On vacation in Paris last month we visited the Musee D'Orsay to see some of the classics of Impressionism. One of my current favorites (and one of the most expensive paintings ever sold) is Renoir's Bal du Moulin de la Galette:

What I particularly like about this painting is Renoir's careful depiction of sunlight dappling through trees. Look at the man in the foreground, facing away from us, with the curious round dabs of sunlight across his back. If you focus on this point and think about it, the appearance of the dapples seems a little strange, yet holistically it feels right.

In fact, what Renoir has captured here is a true optical curiosity. As discussed by Marcel Minnaert in Light and Color in the Outdoors, sunlight dappling through trees often produces these beautiful, perfectly round or elliptical spots of light:


As Minnaert points out: "the surprising thing is that all these images have the same shape, although it is obviously impossible that all the holes and slits in the foliage happen to have the same shape."

This happens because holes in foliage that are sufficiently small result in dapples whose shape is dominated by the image of the sun, i.e. a disc, rather than the shape of the hole. If the sun were a mere point source rather than having a significant diameter, we would not see this effect. (I believe that the shape of the spot of light produced is essentially just the image of the sun, scaled by the projection throw length and then convolved with the shape of the hole, neglecting diffraction effects...)

This effect is most dramatic when something distorts or obscures the image of the sun. A classic example is the change in the appearance of tree dapples during a solar eclipse: as the sun becomes obscured, its image becomes crescent shaped, as do its dapples through the trees:



Update: new eclipse photo, this time at annular stage: