Auto-tuned parallel algorithms for hybrid multi-core/many-core processor clusters

并行计算研究的主要目标是为解决自然科学、工程科学、医学科学和社会科学中的数据密集型和/或计算难题创造支持技术。我的研究目标是通过开发通用并行算法设计方法和针对特定问题领域的并行算法来实现这一目标。在下一个资助期，我建议研究混合多核/多核处理器集群的自动调优并行算法。这种混合处理器集群由同时包含多核和多核（GPU）处理器的节点组成。我们提出的基础研究的重点将是非数值问题，如计算几何和图算法。这些问题通常涉及不规则的数据移动和复杂的数据结构，这对并行计算来说尤其具有挑战性。我建议通过整合自动调优并行方法的研究来扩展混合集群的并行算法研究。自动调优的目标是设计能够自动适应不同硬件配置的高效并行算法和软件。自动调优的目标不是为每个新的并行架构开发新的并行算法，而是为大量当前和（希望）未来的并行机器设计可移植的并行算法和软件。自动调优方法目前在线性代数和其他基于矩阵的问题上是最先进的，但到目前为止，关于非数值问题（如计算几何和本项目提出的图算法）的自动调优方法发表的工作很少。由于不规则的数据移动和更高级的数据结构，这些问题的自动调优并行算法将具有相当大的挑战性。为了证明我们的研究的重要性和促进知识转移，本项目还包括并行科学计算的研究组成部分，重点是混合处理器集群的自动调谐并行蛋白质相互作用预测算法的设计和实现。

The main goal of parallel computing research is to create enabling technology for solving data intensive and/or computationally hard problems in the Natural Sciences, Engineering, Medical Sciences, and Social Sciences. My research objective is to contribute towards that goal by developing general parallel algorithm design methodologies and parallel algorithms for specific problem areas.For the next funding period, I propose to study auto-tuned parallel algorithms for hybrid multi-core/many-core processor clusters. Such hybrid processor clusters consist of nodes that contain both, multi-core and many-core (GPU) processors. The focus of our proposed fundamental research will be on non-numerical problems such as computational geometry and graph algorithms. These problems often involve irregular data movements and complex data structures that are particularly challenging for parallel computing. I propose to extend this parallel algorithms research for hybrid clusters by integrating the study of auto-tuned parallel methods. The goal of auto-tuning is to design efficient parallel algorithms and software that adapt automatically to different hardware configurations. Rather than developing new parallel algorithms for every new parallel architecture, auto-tuning aims at designing portable parallel algorithms and software for a large class of current and (hopefully) future parallel machines. The auto-tuning approach is currently most advanced for linear algebra and other matrix based problems but there is very little work published so far on auto-tuning for non-numerical problems such as computational geometry and graph algorithms proposed for this project. Due to the irregular data movements and more advanced data structures, auto-tuning parallel algorithms for these problems will be considerably more challenging. To demonstrate the significance of our research and facilitate knowledge transfer, this project also has a research component on parallel scientific computing, focusing on the design and implementation of an auto-tuned parallel protein interaction prediction algorithm for hybrid processor clusters.