CPA-CPL: Cache-Aware Synchronization and Scheduling of Data-Parallel Programs for Multi-Core Processors

多核（并行）处理器正变得无处不在。这些系统的使用是科学、工程、金融和其他主要经济领域的关键。然而，只有将这些应用程序映射到多核机器上，才能提高这些系统上的应用程序性能。复杂内存组织的存在使得这项任务变得更加困难，这可能是有效执行的关键瓶颈，并且以前没有得到有效解决。这项研究包括在编译过程的所有阶段使程序映射到意识到内存层次结构复杂性的机器。这将确保应用程序代码与实际机器之间的良好匹配，从而保证比以前更有效地利用硬件（从而高效/快速执行）。现代处理器（多核）采用越来越复杂的内存层次结构。这种层次结构的管理对于编译过程的整体成功变得至关重要，因为内存层次结构的有效利用支配着整体性能。本研究开发了一种新的感知缓存层次结构的编译和运行系统（即，包括编译、调度和并行程序的静态/动态处理器映射）。这些任务有一个共同点：它们都需要准确估计数据元素（迭代、任务）的计算和内存访问时间，而这些都超出了当前（缓存无关）技术的范围。因此，本研究开发了迭代空间分区、调度和同步的新技术，这些技术捕获了由于缓存、内存和条件语句行为及其相互作用而引起的可变性。这项研究将对计算机行业产生广泛的影响，因为它将使未来无处不在的多核系统能够被并行程序有效地利用。

Project AbstractMulti-core (parallel) processors are becoming ubiquitous. The use of such systems is key to science, engineering, finance, and other major areas of the economy. However, increased applications performance on such systems can only be achieved with advances in mapping such applications to multi-core machines. This task is made more difficult by the presence of complex memory organizations which is perhaps the key bottleneck to efficient execution, and which was not previously addressed effectively. This research involves making the mapping of the program to the machine aware of the complexities of the memory-hierarchy in all phases of the compilation process. This will ensure a good fit between the application code and the actual machine and thereby guarantee much more effective utilization of the hardware (and thus efficient/fast execution) than was previously possible. Modern processors (multi-cores) employ increasingly complex memory hierarchies. Management of such hierarchies is becoming critical to the overall success of the compilation process since effective utilization of the memory hierarchy dominates overall performance. This research develops a new cache-hierarchy-aware compilation and runtime system (i.e., including compilation, scheduling, and static/dynamic processor mapping of parallel programs). These tasks have one thing in common: they all need accurate estimates of data element (iteration, task) computation and memory access times which are currently beyond the (cache-oblivious) state-of-the-art. This research thus develops new techniques for iteration space partitioning, scheduling, and synchronization which capture the variability due to cache, memory, and conditional statement behavior and their interaction. This research will have a broad impact on the computer industry as it will allow the ubiquitous multi-core systems of the future to be efficiently exploited by parallel programs.