The most-conventional algorithms assume a computing platform with a single central processing unit (CPU). The processing power of a CPU has practical limits, though, so computer performance is enhanced using several interconnected CPUs. This approach shows great promise for parallel processing loads that can be divided among processors. This is often the case in scientific computing, in large simulations, and when processing huge amounts of data. The achievable performance then depends not only on the number of processors, but also on the partitioning and scheduling of the processing loads, which is the subject matter of divisible load theory (DLT). Most work in DLT research considers a single load that originates on one processor. “While multiple loads processing has been studied in the DLT literature, these studies focus towards bus networks ... [where] the loads are available at the root (bus-controller unit)”; the authors consider this a single-site multiple-jobs problem. In contrast, this paper presents the load-scheduling problem for multiple loads from multiple sites. In 16 pages, the authors develop the processor-set partitioning and data distribution algorithm (PPDD), in order to solve this problem in a near-optimal way. This type of scheduling is of particular interest for grid computing environments, where multiple loads are submitted from geographically distributed areas.

After a short but comprehensive introduction to the subject matter and related work, the authors formulate the problem formally and introduce the specific notation used in their paper. The third section presents strategies for solving the problem, distinguishing two cases: with front ends and without front ends. Here, front end means that the processor is able to communicate with other processors and process the received data at the same time. In Section 4, the authors consider the communication delay. Even with optimal load fractions, some processors may sit idle because the load shares do not reach the processors immediately. Section 5 compares the performance of the new algorithm with a commonly used round-robin scheduling algorithm. In the final section, the authors summarize their work and indicate some directions for future research on the topic. The appendix provides the proof for the three lemmas established in the paper.

Rigorously and well written, this paper is a valuable contribution to the still-important theory of divisible loads.