Validated Models of MapReduce Scaling

VAMOS项目的目标是在面向系统的研究和关于并行系统的排队理论工作之间架起一座桥梁，以创建反映真实系统性能及其伸缩行为的模型。这份文件报告了该项目的第一阶段，并建议通过一个工作计划来扩展该项目，该工作计划建立在过去几年该领域的成功和发展的基础上。在VAMOS项目的第一阶段，我们在并行系统上进行了广泛的、受到实验启发的工作。我们研究了作业局部性的影响，分析了真实集群的踪迹，从理论和实验上研究了更细的任务粒度对性能的好处和权衡，并进行了实验，并开发了带有障碍的并行系统的模型，这是并行化机器学习工作负载时经常需要的。这项工作涉及到我们已经公开发布的几个软件包的实现或扩展。我们建议的项目扩展主要集中在带有障碍的并行系统上。通常，这意味着作业被分成多个任务，这些任务将由一群工作者并行服务，但这些任务被约束为同时开始并且可能完成。还可能存在中间同步点。这种类型的约束在机器学习工作负载中很常见，为了支持这些类型的工作负载，最近在一些MAP-Reduce引擎中添加了对障碍执行模式的支持。这些障碍限制具有重大的性能影响，因为它们可能会迫使工作人员无所事事，等待一个长期运行的任务完成。在项目的第一阶段，我们为这些类型的系统的基本配置开发了分析性能界限。要将我们的结果与实际系统联系起来，我们需要回答一些问题，比如并行系统如何在多障碍工作负载下进行扩展、它们如何处理包含障碍的异类作业流，以及如何对多障碍工作负载进行建模。我们还需要解决某些实现问题，包括动态操作作业的并行度，以及支持极细任务粒度所需的调度优化在流数据的并行处理中是否有用。

The goal of the VaMoS project is to bridge the gap between systems-oriented research and queueing theoretic works on parallel systems to create models which reflect the performance of real systems and their scaling behavior. This document reports on the first phase of this project, and proposes an extension to the project with a work program that builds on the successes and developments in the field over the last few years.During the first phase of the VaMoS project we performed wide-ranging, experimentally inspired work on parallel systems. We investigated the effects of job locality, analyzed traces from real clusters, investigated the performance benefits and trade-offs of finer task granularity both theoretically and experimentally, and conducted experiments and developed models for parallel systems with barriers, as are often needed when parallelizing machine learning workloads. This work involved implementation or extension of several software packages which we have publicly released.Our proposed project extension focuses mainly on parallel systems with barriers. Typically this means that jobs are divided into tasks which will be serviced in parallel by a cluster of workers, but that the tasks are constrained to start, and possibly complete, simultaneously. There may also be intermediate synchronization points. This type of constraint is common in machine learning workloads, and support for barrier execution mode has very recently been added to some map-reduce engines in order to support these types of workloads. These barrier constraints have major performance implications, because they can force workers to sit idle, waiting for a single long-running task to finish. In the first phase of the project we developed analytical performance bounds for basic configurations of these types of systems. To connect our results with real systems we need to answer a number of questions about how parallel systems scale under multi-barrier workloads, how they handle a heterogeneous stream of barrier-containing jobs, and how multi-barrier workloads can be modeled. We also need to address certain implementation problems involving dynamic manipulation of a job's degree of parallelism, and whether scheduling optimizations required to support extremely fine task granularity can be useful in parallel processing of streaming data.