SHF: Small: Empirical Autotuning of Parallel Computation for Scalable Hybrid Systems

今天，科学和工程计算是并行计算的同义词，并且诸如气候建模、药物设计、飞机设计等应用利用非常大的超级计算机装置，功耗以兆瓦为单位测量，并且电力成本以数百万美元为单位测量。同时，每个并行应用程序都需要某种程度的调优，以确保软件正确映射到硬件。否则，次优性能可能导致周期损失、千瓦时损失，并最终导致损失美元。在非常大的规模上，通过重复运行来调优应用程序也是一种浪费的选择。DARE项目通过在非常大的规模上对其行为进行建模和模拟来调优应用程序，而不是实际运行它，从而解决了这个问题。因此，与生产运行中消耗的资源相比，调优所需的资源是微不足道的。DARE是基于这样的观察，即用翼型的计算机模拟代替风洞的相同方法可以应用于软件本身。当今高端计算领域的两个方面使DARE工作变得独特：1）硬件加速器的普及，例如图形处理单元和Xeon Phi协处理器，以及2）采用基于任务的动态工作调度系统作为传统锁步并行编程模型的替代方案。特别是，DARE将三个组件组合成一个细化循环：硬件分析组件、内核建模组件和工作负载模拟组件。硬件分析组件的作用是提取基本硬件信息，如处理能力和数据链路速度。内核建模组件的作用是提供构成并行程序的构建块的串行内核的性能模型。最后，模拟组件的作用是模拟大规模并行工作负载。硬件分析组件收集有关系统的基本知识，例如：每个共享存储器节点的CPU插槽的数量、每个插槽中的CPU核的数量、该高速缓存层次结构、超线程的存在、NUMA节点的数量以及CPU与NUMA节点的接近度，GPU加速器或Xeon Phi协处理器的数量及其设备内存的容量，以及每个节点（总线）内和节点（网络交换机）之间的数据链路的拓扑和带宽。这些知识的一部分可以通过使用适当的查询API来收集，例如hwloc、netloc、PAPI以及CUDA SDK、OpenCL SDK和Xeon Phi SDK中提供的API。合成测试可以用于无法以这种方式建立的参数。内核本质上是并行问题的串行构建块。虽然内核通常以串行控制流为特征，但大多数时候它们已经依赖于高度的数据并行性。今天的CPU从SIMD并行性中获得大部分性能，而GPU从大规模SIMT并行性中获得性能。内核建模组件的作用是双重的：1）在给定的粒度下调整内核以获得最大的性能; 2）提供作为粒度函数的内核性能模型，该粒度是变化的以适应并行执行。DARE转向随机时间步进模拟，以预测动态运行时调度器的性能，这有两个基本原因：1）在基准测试实际并行运行的基础上构建良好的性能模型需要大量的具有显著问题大小的运行，这太耗时了。以及2），许多调谐参数的影响太复杂而不能通过对调谐空间进行稀疏采样并将简单曲线/曲面拟合到采样点来建模。这个问题的答案是用时间步进模拟代替运行，其中给定的基于任务的调度器用于将任务分配给内核，但不是调用实际的内核任务，而是将控制传递给进度跟踪模拟系统，该系统依赖于内核性能模型来模拟任务的执行并产生模拟执行的虚拟跟踪。性能优势有两个方面：1）模拟单次运行比实际运行快得多，2）可以并行运行多个模拟，允许快速扫描大型参数搜索空间。DARE用本质上是增量和迭代的过程取代了标准的瀑布自动调优过程。DARE方法的强大之处在于相互细化循环，其中三个阶段中的每一个都能够大规模地修剪其他两个阶段的搜索空间。因此，可以为特定的工作负载构建非常高质量的模型，因为时间花费在针对实际应用的条件细化模型上，而不是在运行时从未触及的区域中对搜索空间进行采样。

Today, scientific and engineering computing is synonymous with parallel computing, and applications such as climate modeling, drug design, aircraft design, etc. utilize very large supercomputer installations, with power consumption measured in MegaWatts, and the cost of electricity measured in millions of dollars. At the same time, every parallel application requires some level of tuning to ensure that the software is mapped appropriately to the hardware. Otherwise, suboptimal performance can lead to lost cycles, kilowatt-hours, and, ultimately, dollars. Tuning the application by making repeated runs is also a wasteful option at very large scale. The DARE project addresses this problem by tuning the application through modeling and simulation of its behavior at very large scale, rather than actually running it. Therefore, resources required for tuning are marginal compared to those consumed in production runs. DARE is based on the observation that the same approach that replaces a wind tunnel with a computer simulation of the airfoil can be applied to the software itself. Two aspects of today's high-end computing landscape make the DARE work unique: 1) the prevalence of hardware accelerators, such as Graphics Processing Units and Xeon Phi co-processors, and 2) adoption of task-based, dynamic, work scheduling systems as an alternative to traditional, lock-step parallel programming models. In particular, DARE combines three components into a refinement loop: a hardware analysis component, a kernel modeling component, and a workload simulation component. The role of the hardware analysis component is to extract the basic hardware information, such as processing power and data link speed. The role of the kernel modeling component is to provide performance models of the serial kernels that constitute the building blocks of the parallel program. Finally, the role of the simulation component is to simulate large-scale parallel workloads.The hardware analysis component gathers the basic knowledge about the system, such as: the number of CPU sockets per shared memory node, the number of CPU cores in each socket, the cache hierarchy, existence of hyper-threading, number of NUMA nodes and proximity of CPUs to NUMA nodes, number of GPU accelerators or Xeon Phi co-processors and capacities of their device memories, and the topology and bandwidth of data links, both within each node (busses), and between nodes (network switches). Part of this knowledge can be gathered by using appropriate query APIs, such as hwloc, netloc, PAPI, and those provided in the CUDA SDK, OpenCL SDK, and Xeon Phi SDK. Synthetic tests can be used for parameters that cannot be established in this manner.Kernels are essentially the serial building blocks of parallel problems. Although kernels are usually characterized by serial control flow, most of the time they already rely on a high degree of data parallelism. Today's CPUs get most of their performance from SIMD parallelism, and GPUs get their performance from massive SIMT parallelism. The role of the kernel modeling component is two-fold: 1) to tune kernels for maximum performance at a given granularity, 2) to provide the kernel performance model as a function of granularity, which is changing to accommodate parallel execution.DARE turns to a stochastic time-stepping simulation in order to predict the performance of a dynamic runtime scheduler for two fundamental reasons: 1) Building good performance models on the basis of benchmarking actual parallel runs requires a significant number of runs with significant problem sizes, which is simply too time consuming. And 2), the impact of many tuning parameters is too complex to be modeled by sparsely sampling the tuning space and fitting simple curves / surfaces to the sample points. The answer to the problem is to replace the run with a time stepping simulation, where a given task-based scheduler is used for assigning tasks to cores, but instead of invoking actual kernel tasks, control is passed to a progress tracking simulation system, which relies on kernel performance models to simulate the execution of the tasks and produce a virtual trace of the simulated execution. The performance advantage is twofold: 1) Simulating a single run is much faster than actually making that run, and 2) Many simulations can be run in parallel allowing for fast sweeps through a large parameter search space.DARE replaces the standard waterfall autotuning process with a process that is incremental and iterative in nature. The power of the DARE approach lies in the mutual refinement loop, where each of the three phases is capable of massively pruning the search space for the other two. As a result, very high quality models can be built for a particular workload, since time is being spent refining the model for the conditions that actually apply, rather than sampling the search space in areas never touched at runtime.