CPA-CPL: Addressing the Memory Bottleneck in High-Level Programming Systems

综合各种因素，整个行业开始在单个芯片上构建多个核心，以维持处理器计算能力的增长速度。与此同时，高级编程系统（例如，脚本语言）已经获得了巨大的普及，这是由于与传统编程语言（如C/ c++或Java）相比，这些系统提供了更高的编程效率。不幸的是，这两种趋势结合起来增加了应用软件和底层硬件之间的差距，这对硬件利用率产生了负面影响。一个重要的原因是现代多核处理器上内存子系统的关键性质，以及缺乏任何系统的方法来推导在高级编程系统中编写的程序的内存行为。本研究旨在通过建立一个理论模型来估计用MATLAB编写的程序的内存行为，并在原型编译器中实现该模型来解决这个问题。过去的研究人员发现在内存相关的优化中有用的一个定量度量是重用距离。定义为在对内存位置的两次连续引用之间访问的数据量，目标是将程序转换为将大多数重用距离降低到阈值以下（通常与缓存大小有关）。通过将重用距离的计算限制在源级可访问的位置，可以定义源级重用距离。尽管度量是近似的，但是它支持对高级编程系统进行关键的分析，这些系统通常从源代码级转换中显著受益。本研究开发了用于源级重用距离分析的高效算法，针对实际程序行为进行了验证，并在MATLAB编译器中实现了该算法，以驱动与内存相关的优化，特别是与数组访问相关的优化。

A combination of factors has resulted in an industry-wide move to build multiple cores on a single chip to sustain the rate of growth in the computing power of processors. At the same time, high-level programming systems (e.g., scripting languages) have gained tremendous popularity motivated by dramatically higher programming productivity that such systems afford compared to traditional programming languages, such as C/C++ or Java. Unfortunately, these two trends combine to increase the gap between application software and the underlying hardware, which negatively impacts hardware utilization. An important reason is the critical nature of memory subsystems on the modern multi-core processors and a lack of any systematic methods to derive the memory behavior of programs written in high-level programming systems. This research aims at addressing the problem by developing a theoretical model to estimate the memory behavior of programs written in MATLAB and implementing the model in a prototype compiler.A quantitative metric that past researchers have found useful in memory-related optimizations is reuse distance. Defined as the volume of data accessed between two successive references to a memory location, the goal is to transform programs to lower most of their reuse distances to below a threshold (usually, related to cache size).By restricting the computation of reuse distances to locations accessible at the source-level it is possible to define source-level reuse distance. The metric, even though approximate, enables crucial analysis for high-level programming systems that often benefit remarkably from source-level transformations. This research develops efficient algorithms for source-level reuse distance analysis, validates it against the actual program behavior, and implements it in a MATLAB compiler to drive memory-related optimizations, especially those related to array accesses.