TY - JOUR

T1 - The Tiny-Tasks Granularity Trade-Off

T2 - Balancing Overhead Versus Performance in Parallel Systems

AU - Bora, Stefan

AU - Walker, Brenton

AU - Fidler, Markus

N1 - Funding Information: This work was supported in part by the German Research Council (DFG) under Grant VaMoS FI 1236/7-1.

PY - 2023/4/1

Y1 - 2023/4/1

N2 - Models of parallel processing systems typically assume that one has ll workers and jobs are split into an equal number of k=lk=l tasks. Splitting jobs into k > lk>l smaller tasks, i.e. using 'tiny tasks', can yield performance and stability improvements because it reduces the variance in the amount of work assigned to each worker, but as kk increases, the overhead involved in scheduling and managing the tasks begins to overtake the performance benefit. We perform extensive experiments on the effects of task granularity on an Apache Spark cluster, and based on these, develop a four-parameter model for task and job overhead that, in simulation, produces sojourn time distributions that match those of the real system. We also present analytical results which illustrate how using tiny tasks improves the stability region of split-merge systems, and analytical bounds on the sojourn and waiting time distributions of both split-merge and single-queue fork-join systems with tiny tasks. Finally we combine the overhead model with the analytical models to produce an analytical approximation to the sojourn and waiting time distributions of systems with tiny tasks which include overhead. We also perform analogous tiny-tasks experiments on a hybrid multi-processor shared memory system based on MPI and OpenMP which has no load-balancing between nodes. Though no longer strict analytical bounds, our analytical approximations with overhead match both the Spark and MPI/OpenMP experimental results very well.

AB - Models of parallel processing systems typically assume that one has ll workers and jobs are split into an equal number of k=lk=l tasks. Splitting jobs into k > lk>l smaller tasks, i.e. using 'tiny tasks', can yield performance and stability improvements because it reduces the variance in the amount of work assigned to each worker, but as kk increases, the overhead involved in scheduling and managing the tasks begins to overtake the performance benefit. We perform extensive experiments on the effects of task granularity on an Apache Spark cluster, and based on these, develop a four-parameter model for task and job overhead that, in simulation, produces sojourn time distributions that match those of the real system. We also present analytical results which illustrate how using tiny tasks improves the stability region of split-merge systems, and analytical bounds on the sojourn and waiting time distributions of both split-merge and single-queue fork-join systems with tiny tasks. Finally we combine the overhead model with the analytical models to produce an analytical approximation to the sojourn and waiting time distributions of systems with tiny tasks which include overhead. We also perform analogous tiny-tasks experiments on a hybrid multi-processor shared memory system based on MPI and OpenMP which has no load-balancing between nodes. Though no longer strict analytical bounds, our analytical approximations with overhead match both the Spark and MPI/OpenMP experimental results very well.

KW - Network calculus

KW - parallel processing

KW - performance bounds

KW - processing overhead

KW - Spark

KW - synchronization constraints

KW - task granularity

KW - tiny-tasks

UR - http://www.scopus.com/inward/record.url?scp=85147217340&partnerID=8YFLogxK

U2 - 10.1109/TPDS.2022.3233712

DO - 10.1109/TPDS.2022.3233712

M3 - Article

AN - SCOPUS:85147217340

VL - 34

SP - 1128

EP - 1144

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

SN - 1045-9219

IS - 4

ER -