The Tiny-Tasks Granularity Trade-Off: Balancing overhead vs. performance in parallel systems
The Tiny-Tasks Granularity Trade-Off: Balancing overhead vs. performance in parallel systems
复制标题
小任务粒度权衡：平衡并行系统中的开销与性能
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Markus Fidler
中科院分区：
文献类型：
--
作者：
Stefan Bora;Brenton D. Walker;Markus Fidler
并行处理系统的模型通常假设一个系统有$l$个工人，作业被分成相等数量的$k=l$个任务。将作业拆分为$k>l$个更小的任务，即使用"微小任务“，可以提高性能和稳定性，因为它减少了分配给每个工作者的工作量的差异，但是随着$k$的增加，调度和管理任务所涉及的开销开始超过性能收益。我们进行了广泛的实验上的Apache Spark集群的任务粒度的影响，并在此基础上，开发了一个四参数模型的任务和作业的开销，在模拟中，产生逗留时间分布相匹配的真实的系统。我们还提出了分析结果，说明如何使用微小的任务，提高了分裂合并系统的稳定区域，和分析边界上的逗留和等待时间分布的分裂合并和单队列fork-join系统与微小的任务。最后，我们结合联合收割机的开销模型与分析模型，产生一个解析近似的逗留和等待时间分布的小任务，其中包括开销。虽然不再是严格的分析界限，但这些近似值在split-merge和fork-join两种情况下都与Spark的实验结果非常匹配。
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.