Code Scheduling Under Varying Parallel Resource Constraints

高速计算中尚未解决的主要问题之一是设计高度并行的机器，以利用应用程序中固有的潜在并行性。目前的高速计算机没有充分发挥其潜力，部分原因是代码调度效率低下，导致硬件资源未得到充分利用。本研究的目标是通过改进代码调度，在高性能并行硬件上获得更好的执行加速比。这项研究将为具有多指令流和非阻塞内存引用的并行机开发高效的代码调度器，这些并行机具有较长且变化很大的延迟。对这类机器进行调度的困难在于，虽然代码调度是一种静态活动，但正在调度的硬件的可用性和延迟在执行时间期间会发生变化。PI设计了四种不同的调度算法，具有不同的复杂性(即，它们生成具有不同效率的调度)和编译成本。它们的不同之处在于它们是否跨具有数据相关性的指令进行调度，以及它们是否以及以何种方式考虑了内存延迟和多个指令流的差异。该算法将在与Aiken/Nicolau软件流水线算法相结合并假设高度并行的硬件配置时进行评估。性能研究的指标将是代码调度大小、代码调度密度、执行时间和硬件利用率。

One of the major unsolved problems in high-speed computing is designing highly parallel machines that can exploit the latent parallelism inherent in applications. Current high-speed computers do not achieve their full potential, in part because of inefficient code scheduling that leaves hardware resources underutilized. The goal of this research is to obtain better execution speedup on high- performance parallel hardware by improving code schedules. The research will develop efficient code schedulers for parallel machines with multiple instruction streams and non-blocking memory references that have long and widely varying latencies. The difficulty of scheduling for machines of this type is that, while code scheduling is a static activity, the availability and latency of the hardware that is being scheduled varies during execution time. The PI has devised four different scheduling algorithms, with varying complexity(i.e., they generate schedules with varying efficiencies) and compilation costs. They differ in whether they schedule across instructions with data dependencies and whether and in what way they take into account variances in memory latencies and multiple instruction streams. The algorithm will be evaluated when combined with the Aiken/Nicolau software pipelining algorithm and assuming a highly parallel hardware configuration. The metrics for the performance study will be code schedule size, code schedule density, execution time and hardware utilization.