Research Initiation Award: Scheduling Task and Loop Parallelism on Message-Passing Architectures

9409695 Yang计算任务执行和数据移动的高效调度对于大规模并行机和工作站集群上的高性能计算至关重要。 本文主要研究图调度算法和运行时调度执行方法，以将程序并行性映射到消息传递体系结构上。 优化的目标是通过在有限数量的处理器之间平衡负载，消除不必要的通信和重叠的计算与通信，以最大限度地减少并行时间。 程序中存在两种类型的并行性，任务并行性被表示为功能任务的集合，它们之间具有通信。 依赖结构是一个有向无环图（DAG）。 循环并行性表示为具有循环承载依赖的迭代计算的集合.本项目的主要研究内容是：开发任务并行和循环并行的调度算法，以及执行调度图的运行时方法，研究循环变换方法以帮助图调度算法探索更多的并行性，将这些算法应用于科学计算，如稀疏矩阵分解和迭代方法，分析程序划分对调度性能的影响。 研究活动包括开发和实现上述问题的算法，评估并行机和工作站集群上的性能，将这些算法集成到调度工具中并分发实现。 ***

9409695 Yang Efficient scheduling of computational task execution and data movement is essential to high-performance computing on massively parallel machines and workstation clusters. This research focuses on the study of graph scheduling algorithms and the run-time schedule executing methods for mapping program parallelism on message-passing architectures. The goal of optimization is to minimize the parallel time by balancing load among a limited number of processors, eliminating unnecessary communication and overlapping computation with communication. There exists two types of parallelism in a program, task parallelism is expressed as a collection of functional tasks with communication between them. The dependence structure is a directed acyclic graph (DAG). Loop parallelism is expressed as a collection of iterated computation with loop- carried dependence. The main research topics identified in this project are to develop scheduling algorithms for both task and loop parallelism and run-time methods to execute the scheduled graph, study the methods of loop transformation to help graph scheduling algorithm to explore more parallelism, apply these algorithms in scientific computing such as sparse matrix factorization and iterative methods, analyze the impact of program partitioning on scheduling performance. Research activities include developing and implementing algorithms for the above problems and evaluating the performance on parallel machines and workstation clusters, integrating these algorithms in a scheduling tool and distributing the implementation. ***