XPS: DSD: A2MA - Algorithms and Architectures for Multiresolution Applications

本研究项目的目标是为计算科学和工程中需要高强度算术运算（也称为每秒浮点运算，或“FLOPS”）的问题设计新的方法和设备。在这种计算密集型技术的研究和发展中面临的许多障碍之一是实现对可用计算资源的高效利用。与汽车设计中使用的英里/加仑公制类似，人们对可用于新计算技术设计的公制感兴趣：优化flops /watt。这项研究将设计新的算法和架构来优化这一指标。这些算法和架构将被定制为一类特殊的科学计算问题：基于树的有限元方法和n体问题。有可能设计出并行性良好且节能的算法（即产生高“峰值百分比”测量值）。然而，这种算法通常会牺牲工作最优性。在实现工作最优性和能源效率的同时，设计这样的算法要困难得多。这个节点利用墙——从早期开始就是一个长期存在的问题——不仅没有得到解决，而且随着更深层次的内存层次和多核心和异构架构的出现变得更加尖锐。与此同时，有一个巨大的未开发的潜力，不仅是适应架构变化的算法，而是从算法需求驱动架构设计。本研究将确定基于树的算法的设计空间（在工作最优性和最大并发性的约束下），评估最先进代码的性能，并探索自定义算法/硬件平台。预计该项目将产生一系列更广泛的影响。目标方法在地球科学、工程学、宇宙学、生物学和数据分析中都有应用。在研究活动的同时，还将设计一个教育和传播计划，将这项工作的结果传达给学生和研究人员，以及更广泛的计算和应用科学家受众。

The goal of this research project is to devise novel methodologies anddevices for problems in computational science and engineering thatrequire high-intensity of arithmetic operations (also known asFloating-point Operations Per Second, or ``FLOPS''). Among the manyhurdles faced in research and development of such compute-intensivetechnologies is achieving energy-efficient utilization of theavailable computing resources. Similar to the miles/gallon metric usedin automotive design, one is interested in a metric that can be usedin the design of new computing technologies: optimizingFLOPS/watt. This research will be on designing novel algorithms andarchitectures that optimize this metric. These algorithms andarchitectures will be customized to a particular class of scientificcomputing problems: tree-based finite element methods and N-bodyproblems.It is possible to devise algorithms that parallelize well and are energy efficient (i.e., produce high ``percentage-of-peak''measurements). Often, however, such algorithms sacrifice workoptimality. It is much more difficult to design algorithms that do sowhile achieving both work optimality and energy efficiency. Thison-node utilization wall---a chronic problem since the earlynineties---not only remains unresolved but has become more acute withthe emergence of deeper memory hierarchies and manycore andheterogeneous architectures. At the same time, there is a largeuntapped potential by not only adapting algorithms to architecturalchanges, but instead driving architecture design from algorithmrequirements. This research will identify the design space fortree-based algorithms (under the constraints of work-optimality andmaximum concurrency), evaluate performance of state-of-the-art codes,and explore custom algorithm/hardware platforms. A number of broaderimpacts are anticipated from this project. The target methodologiesfind applications in earth sciences, engineering, cosmology, biology,and data analysis. Along with the research activities, an educationaland dissemination program will be designed to communicate the resultsof this work to both students and researchers, as well as a moregeneral audience of computational and application scientists.