Divisible Load Scheduling in Parallel and Distributed Systems

Welcome! This research is concerned with scheduling in parallel and distributed processor systems with divisible loads. A divisible load (job) is one that can be arbitrarily partitioned among the processors in a system. The theory of scheduling such divisible loads is commonly referred to as divisible load theory (DLT) in the literature. Applications include multiprocessor and distributed scheduling and distributed sensor networks. The approach is particularly suited to the processing of very large linear data files as in signal processing, image processing, and experimental data processing. In general, divisible load theory is applicable to situations wherein large amount of CPU time is in demand due to a very heavy computational requirement. Very recently, the divisibility property is applied to movie on-demand multimedia systems. In reality, most of the loads submitted for processing are not strictly arbitrarily divisible. However, if the dependencies can be taken care, this paradigm will give elegant solutions to optimize the overall processing time.

The methodology that has been developed to date is unique in that it is a linear and continuous one. Both computing time and channel transmission time are modelled linearly. Continuous time modelling is invoked as jobs can be arbitrarily partitioned. This leads to a very tractable overall model and in many cases recursive, linear or closed form solutions. This new methodology allows a close examination of the integration of computation and communication in networked computing. In fact, what has been developed is a new "calculus" for scheduling problems.

Scheduling Divisible Loads in Parallel and Distributed Systems: This monograph gives a compilation of all the developments in this domain of research until 1994. For recent papers, please contact me by email: elebv@nus.edu.sg

From 1995 till date, several practical issues related to the problem are being addressed. These typically include the following. Fault-tolerance (processor/link failure); processor available times (in the form of release times), multiple divisible loads processing (more than one load processing by the system), time-varying processor and link speeds (non-deterministic approach wherein processor and link speeds are no longer constants), inclusion of start-up costs (accounting the overheads involved), granularity issues (constraints on the divisible nature of the jobs), finite buffer constraints (processors with limited buffer capacities -SLTN and Hypercube topologies), load quantization algorithms, and experimental studies mentioned below.

RECENT SURVEY: An up-to-date survey of the literature is available on request. This work is to appear in a special issue in Cluster Computing, Baltzer Press, 2002.

=====================================================================================

Experimental work conducted so far in the domain:

Very large matrix-vector multiplication on bus networks - Dept of ECE, NUS: A matrix of size 100,000 x 100,000 is considered for distribution on a homogeneous bus network of PCs (Pentium III machines) and DLT approach is taken. Equal load division strategy (as always the case in the literature) is also implemented to compare the results.
Very large size image processing - edge detection application - Dept of ECE, NUS: Two different platforms have been considered for implementation. Here we have considered images of size 256 x 256, 512 x 512, and 3000 x 3000 pixels for processing. The application was to detect the edges of the images using the following platforms. For comparison purposes, we have also implemented the equal load division strategy (as always the case in the literature ).

(a). HP Workstation Clusters under PVM environment

(b). PC Clusters test bed

=====================================================================================