From: softlib.cs.rice.edu
Last mod: December 23, 1995 fastlink 3.0P

Running FASTLINK on parallel computers

Starting with FASTLINK version 2.3P, much of the code can run in parallel on a variety of UNIX platforms.

Parallel Code, Introduction

The (sequential) FASTLINK package already provides considerable running time improvements over the older programs for the LINKAGE package. Response from users about sequential FASTLINK has been extremely enthusiastic and yet, it is abundantly clear that more speedup is necessary. At this time, we believe that one realistic way to obtain substantially more speedup on long runs is to use multiple processors in parallel. We continue to investigate further sequential speedups.

Two attempts to parallelize ILINK from FASTLINK are described in the papers: 

3. Sandhya Dwarkadas, Alejandro A. Schaffer, Robert W. Cottingham Jr.,
   Alan L. Cox, Peter Keleher, and Willy Zwaenepoel, Parallelization of
   General Linkage Analysis Problems, Human Heredity 44(1994),
   pp. 127--141.

4. Sandeep K. Gupta, Alejandro A. Schaffer, Alan L. Cox, Sandhya
   Dwarkadas, and Willy Zwaenepoel, Integrating Parallelization
   Strategies for Linkage Analysis, Computers and Biomedical Research
   28(1995), pp. 116-139.
These two papers are available as paper3.ps and paper4.ps with the distribution. The version of parallel ILINK that we are distributing is similar algorithmically to that described in the second paper. We were able to achieve speedups in the 5 to 7 range on a network of 8 DECStation5000/Ultrix processors on ILINK runs that take tens of minutes sequentially. As explained in the second paper, ILINK is the hard case to parallelize; our preliminary timing experiments with LINKMAP and MLINK suggest that the speedup for those two programs is better.

At this time, parallel FASTLINK does not provide all of the functionality of the sequential code. On the basis of a variety of sample data sets I have gotten, it appears to handle the vast majority of cases that desperately need more speedup. The main limitations on the parallel version are:

  1. . LODSCORE is not parallelized because very few users use it and similar functionality is provided by ILINK.
  2. Only autosomal data is handled.
  3. Checkpointing is not yet available.
We are actively working to remove limitations 2, 3. Version 2.3P could not handle multiple loops very well, but that limitation is removed in 3.0P.

Parallel FASTLINK, Operation

FASTLINK 3.0P can be run in parallel on two different types of platforms: shared-memory multiprocessors and networks of UNIX workstations.

FASTLINK on shared-memory multiprocessors:

The shared-memory version uses the p4 macros which are available by anonymous ftp to Argonne National Labs. More detailed retrieval and installation instructions can be found in README.p4 that comes with FASTLINK.

So far we have successfuly run the shared-memory version on SUN multiprocessors using SOLARIS, a DEC Alpha using OSF, and an SGI Challenge. The p4 macro package can be used on a wide variety of shared-memory machines. We are keenly interested to work with users who have access to different shared-memory models to help ensure that parallel FASTLINK does port properly.

FASTLINK on network of workstations:

If you have access to a network of (uniprocessor) Unix workstations, then you can run parallel FASTLINK using a runtime package called TreadMarks. TreadMarks essentially provides the same execution environment on a network of workstations as that available on shared-memory multiprocessors.

TreadMarks is available for a small fee for universities and medical schools, and at commercial rates for other institutions. All users can get a 30-day free trial license. See README.TreadMarks for more details on how to configure FASTLINK with TreadMarks.

Currently available for Ethernet, ATM, FDDI networks of SUN, DEC, HP, IBM, or SGI workstations . Also available on IBM SP-1 and SP-2. TreadMarks only executes on a homogeneous set of machines: i.e., all machines must be of the same architecture, although of course other machines may be present on the network.

TreadMarks licenses can be obtained by sending e-mail to treadmarks@ece.rice.edu. Please specify the nature of your organization (commercial or university/medical school) and the machine architecture and operating system you plan to use TreadMarks for. Once you return the signed license and the license fee, a copy of TreadMarks will be sent to you or be made available via ftp. A free 30-day demo copy can also be obtained by sending e-mail to the same address.

As usual, FASTLINK 3.0P can be ftp-ed from softlib.cs.rice.edu in the directory 

         pub/fastlink

We recognize that installing the parallel code is more difficult that installing the sequential code because of the need to configure both the FASTLINK code and the runtime library (either p4 or TreadMarks). We will be pleased to work with you in getting the parallel code up and running on your system.

Parallel FASTLINK, References

The main references for sequential FASTLINK are: 
 1. R. W. Cottingham Jr., R. M. Idury, and A. A. Schaffer, Faster Sequential 
 Genetic Linkage Computations, American Journal of Human Genetics, 53(1993),
 pp. 252-263.


 2. A. A. Schaffer, S. K. Gupta, K. Shriram, and R. W. Cottingham, Jr.,
 Avoiding Recomputation in Genetic Linkage Analysis, Human Heredity,
 44(1994), pp. 225-237.

 5. G. M. Lathrop, J.-M. Lalouel, C. Julier, and J. Ott, Strategies for
 Multilocus Analysis in Humans, PNAS 81(1984), pp. 3443-3446.

 6. G. M. Lathrop and J.-M. Lalouel, Easy Calculations of LOD Scores
 and Genetic Risks on Small Computers, American Journal of Human Genetics,
 36(1984), pp. 460-465.

 7. G. M. Lathrop, J.-M. Lalouel, and R. L. White, Construction of Human
 Genetic Linkage Maps: Likelihood Calculations for Multilocus Analysis,
 Genetic Epidemiology 3(1986), pp. 39-52.
One reference for p4 is: 
 8. R. Butler and E. Lusk. Monitors, Messages and Clusters: The p4
 Parallel Programming System, Parallel Computing 20(1994), pp. 547-564.
One reference for TreadMarks is: 
 9. P. Keleher, A.L. Cox, S. Dwarkadas, and W. Zwaenepoel,
 TreadMarks: Distributed Shared Memory on Standard Workstations
 and Operating Systems, Proceedings of the Winter 94 Usenix Conference,
 pp. 115-131, January 1994.
FASTLINK 3.0P represents the conjunction of 5 substantial research efforts and software engineering projects. Therefore, if you use FASTLINK in parallel, we ask that you cite: 
at least one of 5,6,7 to give credit to LINKAGE
at least one of 1,2 to give credit to sequential FASTLINK
at least one of 3,4 to give credit for the parallel algorithms and
either 8 (p4) or 9 (TreadMarks) to give credit for the runtime library
  that you use.
back to fastlink