Back to Multipol Home Page
This page contains the document and source code of Multipol (a 940KB tar.Z file) , a data structure library designed for distributed memory multiprocessors and workstation networks. This is version 1.0. It includes distributed data structures, example applications, and underlying runtime support. The current release runs on distributed memory multiprocessors and uniprocessors.
The doc subdirectory contains documentation on Multipol. It describes the interfaces for application programmers who wish to use the data structures and some information about how to write new data structures and port the system to new platforms.
Papers related to Multipol and the applications are available though the Multipol home page. An online version of the manual. is also included.
To install the library, run the install-multipol script in the root directory. Install-multipol takes a single argument, which identifies the kind of machine on which you wish to run. The syntax is install-multipol <arch> where <arch> is one of the following:
If you are using a shared file system and want to support multiple architectures, you should run install-multipol for each type of machine in your environment.
To install Multipol, you will probably need the following system tools: gcc, libgcc.a, makedepend, and gmake. It is possible that other compilers could be used, but the system has only been tested with gcc. In addition, Multipol uses a set of gm4 macros to simplify programming of some of the data structures and applications. The macro versions of these modules are in a .m file, so you will nee gm4 to generate the .c version. Since many systems do not support gm4, we have provided a ``pre-processed'' .c file for each .m file. However, we recommend looking at the .m files if you wish to read or modify the code.
To remove the binaries and other files created by install-multipol, run the cleanup script in the root directory. The cleanup command does not take a architecture argument, and will remove the binary for all architectures. The library files in the lib directory are not removed by cleanup.
If your system does not support gm4, you may need to run the script fixgm4 to ensure the ``pre-processed'' .c files have more recent timestamps than their .m files. On some machines the unarchiving process refreshes the timestamps of all files, which may cause gmake to invoke gm4 to re-generate the .c files. Although failures to find gm4 are ignored, the user will see many redundant warning messages when making the applications. fixgm4 resolves this problem by refreshing only the timestamps of the .c files.
To enable gmake to find the various utility software on a new machine, You may need to change the path names in the platform specific makefiles. The makefile for the platform <arch> is in src/Rts/<arch>.
Along with the Multipol library, we have provided eight example applications. These are small- to medium-sized irregular applications, which are described in more detail in the manual (see the doc directory). After installing the library, one of the first tests you might want to do is to compile and run all of our applications. To do this, go to the examples subdirectory and run the run-appls script. On some machine platforms you will have to ``source'' this file, rather the executing it directly. In addition, there are two arguments require for run-appls: the machine type and the number of processors on which they should be run. The syntax is source run-appls <arch> <procs>. For example, to run all eight programs in 16 processors of an IBM SP2, use:
source run-appls sp2 16
The file run-appls.output contains the results of the executions.
Notice that <procs> is the number of processors used to perform the computation, and it should always be smaller than the number of available processors on the machine. On machines that are space-shared (such as the Intel Paragon), the script allocates exactly <procs> processors to the application. On machines that are used exclusively by one program at a time (such as the Think Machines Corp. CM5), the script allocates the entire machine to the application, while the application may use only a subset of <procs> processors for the computation, depending on how it is written.
It is also possible to run an individual application. You must first cd to the application's directory, and then compile the source code using the command gmake ARCH=<arch>. The executable is in the file <appl>-<arch>, where <appl> is the name of the application specified by the variable APP in Makefile. To execute the application in a platform-independent manner, use the command gmake ARCH=<arch> PROCS=<procs> execute. The processors are allocated in the same manner as described in the previous paragraph. You may set the variable ARGS in Makefile to change the command-line arguments. The ``gmake execute'' command may not work for all platforms. On some platforms the executable must be scheduled by a job manager using a special script file. If this is the case, you can always find the executable in the file <appl>-<arch> for use in a platform-dependent method.
The easiest way to learn to write a Multipol application is probably to read the overview information in the manual and then to look at a simple example. In our experience, one of the most useful data structures in the library is a TaskStealer, which does dynamic load balancing of a set of tasks (uninterpreted data) across processors. An example of a problem that uses such dynamic load balancing is the proverbial n-queens problem. The Multipol solution to this problem is found on the examples/queen directory, along with a Makefile that you will want to copy of for each new Multipol application. The file include/makefile-all contains instructions on how to set the makefile variables.
This Multipol release runs on a version of Active Messages for the CM5, on send/receive message passing libraries for the Paragon and SP machines, and on uniprocessors. Ports that fit any of these models can probably be done without too much difficulty. All of the machine-specific code is within the runtime system layer, which is found in the src/Rts/<arch> directory, where <arch> is the name of the platform. To create a new architecture, you should add implementation for this machine in a subdirectory of the corresponding name. The interface for the runtime system is documented in the manual under ``Porting to New Platforms''. Besides providing implementation of this interface, you will also need to create a makefile called makefile-<arch> in the subdirectory. The makefile specifies the machine dependent modules to be included in the library, and contains rules for compilation and linking.
The following are known problems with the 1.0 release:
For questions or bug reports, please send mail to:
Back to Multipol Home Page