The goal of this research project is to devise novel methodologies and devices for problems in computational science and engineering that require high-intensity of arithmetic operations (also known as Floating-point Operations Per Second, or ``FLOPS''). Among the many hurdles faced in research and development of such compute-intensive technologies is achieving energy-efficient utilization of the available computing resources. Similar to the miles/gallon metric used in automotive design, one is interested in a metric that can be used in the design of new computing technologies: optimizing FLOPS/watt. This research will be on designing novel algorithms and architectures that optimize this metric. These algorithms and architectures will be customized to a particular class of scientific computing problems: tree-based finite element methods and N-body problems.
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 work optimality. It is much more difficult to design algorithms that do so while achieving both work optimality and energy efficiency. This on-node utilization wall---a chronic problem since the early nineties---not only remains unresolved but has become more acute with the emergence of deeper memory hierarchies and manycore and heterogeneous architectures. At the same time, there is a large untapped potential by not only adapting algorithms to architectural changes, but instead driving architecture design from algorithm requirements. This research will identify the design space for tree-based algorithms (under the constraints of work-optimality and maximum concurrency), evaluate performance of state-of-the-art codes, and explore custom algorithm/hardware platforms. A number of broader impacts are anticipated from this project. The target methodologies find applications in earth sciences, engineering, cosmology, biology, and data analysis. Along with the research activities, an educational and dissemination program will be designed to communicate the results of this work to both students and researchers, as well as a more general audience of computational and application scientists.
