Divisible load scheduling theory

Divisible loads are parallel applications with fine granularity and negligible data dependencies: the work can be split into parts of arbitrary size that are processed independently. Distributing the load costs communication time, so it is often sent in several smaller installments rather than one large chunk, which shortens the time processors wait before they can start computing. Choosing the number and sizes of these installments is a scheduling problem.

This was the subject of my doctoral thesis at Poznań University of Technology (2006), written with Maciej Drozdowski, and it remains the basis of the scheduling tools I build today.

Multi-installment scheduling in heterogeneous systems

In heterogeneous distributed systems the installment sizes must match the communication and computation speed of each processor. We showed that ignoring heterogeneity can produce arbitrarily bad schedules, proposed an exact branch-and-bound algorithm and a genetic-search heuristic to size the load chunks, and found that the problem has both a combinatorial and an algebraic nature, with optimal solutions becoming harder to find as heterogeneity grows.

Systems with limited memory

When processors have limited memory, an installment cannot exceed what a processor can hold. A series of papers studied multi-installment processing under memory limits, from models and optimisation methods to an experimental study of hybrid solution methods.

Multiple divisible loads and complexity

Scheduling several divisible loads on a star network of processors is computationally hard; special cases solvable in polynomial time were identified, including results for homogeneous star systems. Work with Yang Yang, Henri Casanova and Arnaud Legrand addressed the complexity of multi-round divisible load scheduling.

From theory to a tool: the DLT Portal

The DLT Portal applies divisible load theory to schedule large splittable workloads, such as data batches, parallel scans, rendering and simulations, across distributed processors while minimising both completion time and energy, with time–energy Pareto analysis. Its solver library, DLT Studio, is archived on Zenodo.

Publications

Software: DLT Portal at dlt.psnc.pl. Today the same question of how to split and place work drives my study of MPI rank placement and node count for CFD on AMD EPYC clusters.

Other research topics: Performance and energy of CFD on AMD EPYC · Digital twins and environmental simulation · IT for natural history collections · Virtual Laboratory and remote instrumentation · all research themes.

Go to top of the page.