CAREER: A Unified Framework for Designing Efficient Resource-Oblivious Parallel Algorithms

该项目将开发基础理论和高效工具，以促进并行算法的设计，这些算法在代码中没有提到任何硬件参数，但仍然可以在从小型笔记本电脑到巨型超级计算机的广泛的并行计算平台上高效运行。这些算法将被称为资源无关算法。这些算法将支持高效的并行代码，而不考虑不断变化的底层硬件平台，从而可以更多地关注实现的正确性，而不需要针对特定硬件进行优化。从一台机器到另一台机器的代码移植将减少或消除。简而言之，算法将实现一次并继续高效地运行。为多核机器的多级缓存层次结构设计高效的资源无关并行算法的一种方法是颠倒程序和硬件之间信息流的方向，而不是基于硬件参数(如缓存大小和核的数量)进行选择，程序现在只需通过告诉调度器正在运行的算法的属性来辅助调度。该项目将把资源忽略的概念扩展到包含多核处理器和多核协处理器的混合计算节点网络。将自下而上地建立统一的框架，从仅在单个节点的处理器上运行的程序(阶段1)或主要在单个节点的协处理器上运行的程序(阶段2)开始，然后是利用同一节点的处理器和协处理器的混合程序(阶段3)，最后是用于混合节点网络的程序(阶段4)。每个阶段将有四个结果。-分别用于评估和执行算法的资源的算法模型。-有效的资源无关算法，用于求解一组具有理论界限的评价模型上的代表性问题。-保证评估模型预测的实际程序性能的调度器。-调度器和算法在真实机器上的实现和实验评估。这项研究将使各种计算科学应用程序更易于开发和维护。研究成果将通过新开设的和现有的关于算法分析、并行编程和超级计算的课程来传播，这些课程使用NSF资助的XSEDE计划提供的资源，以及针对计算机科学和计算科学受众的研讨会。

This project will develop fundamental theory and efficient tools to facilitate the design of parallel algorithms that make no mention of any hardware parameters in the code, but still run efficiently across a wide spectrum of parallel computing platforms ranging from small laptop computers to gigantic supercomputers. These algorithms will be called resource-oblivious algorithms. These algorithms will enable efficient parallel code regardless of the ever-changing underlying hardware platforms allowing more focus on the correctness of implementations without the need of optimizing for a particular hardware. Porting code from one machine to another will be reduced or eliminated. In short, algorithms will be implemented once and continue to run efficiently.One way of designing efficient resource-oblivious parallel algorithms for the multilevel cache-hierarchy of a multicore machine is to reverse the direction of information flow between the program and the hardware ― instead of making choices based on hardware parameters, such as cache sizes and number of cores, the program now simply assists scheduling by telling the scheduler about the properties of the algorithm being run. This project will extend the notion of resource-obliviousness to networks of hybrid compute nodes containing both multicore processors and manycore coprocessors. A unified framework will be built bottom-up starting with programs that run solely on processors (stage 1) or mainly on coprocessors (stage 2) of a single node, followed by hybrid programs utilizing both processors and coprocessors of the same node (stage 3), and ending with programs for networks of hybrid nodes (stage 4). Each stage will have four outcomes. - Algorithmic models of resources separately for evaluation and for execution of algorithms. - Efficient resource-oblivious algorithms for a suite of representative problems with theoretical bounds on the evaluation model. - Schedulers that guarantee practical program performance predicted by the evaluation model. - Implementation and experimental evaluation of the schedulers and the algorithms on real machines.This research will make a wide variety of computational science applications easier to develop and maintain.The research results will be disseminated through new and existing courses on analysis of algorithms, parallel programming and supercomputing using resources made available through the NSF-funded XSEDE program, as well as workshops targeting both computer science and computational science audiences.