The ALDY Load Distribution System

We present a new portable library for the support of non-preemptive and preemptive load distribution, called ALDY. The ALDY programming model consists of three different classes of virtual objects: virtual processes, virtual workers, and virtual tasks. Similar to the task farming paradigm, virtual tasks are assigned non-preemptively to virtual workers. Virtual workers are assigned semi-preemptively to virtual processes: If a virtual worker does not hold a task, it can be migrated to another virtual process. The application maps its concrete subproblems to virtual objects of the ALDY programming model and informs ALDY about virtual objects. On the other hand, ALDY initiates load distribution mechanisms for virtual objects and informs the application about these mechanisms. Using the mapping of subproblems to virtual objects, the application transforms the load distribution mechanisms to concrete load distribution mechanisms for subproblems. Communication and synchronization of the ALDY library are realized by the application on top of the conventional message passing library by implementing a specific library interface. Consequently, the portability of the application is not reduced if ALDY is used, even if object migrations are performed. The library interface is very simple to implement. For example, the PVM interface for ALDY consists of about 100 lines of code. Instead of using a fixed load distribution strategy, ALDY provides a collection of several strategies (for example sender-initiated and receiver-initiated) which are specified in a parameter file. The strategies can be easily replaced without having to recompile the program. Several relations describing directives for the strategy (for example assignment of tasks to specific workers, preservation of a specific topology when migrating workers) can be used to adjust the strategy to the specific properties of the application. ALDY compensates both internal and external load imbalances: internal load imbalances arise from the application program itself due to differing computational requirements of processes; external load imbalances arise from heterogeneous hardware or from heterogeneous load due to a multi-user environment.     «

We present a new portable library for the support of non-preemptive and preemptive load distribution, called ALDY. The ALDY programming model consists of three different classes of virtual objects: virtual processes, virtual workers, and virtual tasks. Similar to the task farming paradigm, virtual tasks are assigned non-preemptively to virtual workers. Virtual workers are assigned semi-preemptively to virtual processes: If a virtual worker does not hold a task, it can be migrated to another virt...     »