2022/02/23 by Stefan Bora, Bora, Stefan, Brenton Walker +3
Computer Science · Engineering · #Cloud Computing and Resource Management #Distributed #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #Parallel #Performance (cs.PF) #Scheduling and Optimization Algorithms #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2202.11464
openalex publication_date 2022/02/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Models of parallel processing systems typically assume that one has l workers and jobs are split into an equal number of k=l tasks. Splitting jobs into k > 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 k 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, developed 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. Though no longer strict analytical bounds, these approximations matched the Spark experimental results very well in both the split-merge and fork-join cases.