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

Suny At Stony Brook, Stony Brook NY

Investigators

Abstract

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.