Problems in Combinatorial Scientific Computing (Data Migration in Parallel Computing: Models and Algorithms)

Alex Pothen Old Dominion Research Foundation并行计算中的数据迁移：模型和算法多处理器上正在解决的科学计算问题目前具有需要访问外部存储器的大型数据集。在处理器之间重新分配数据需要使通信成本最小化(或近似最小化)的处理器间通信调度。在并行文件系统、并行I/O和网格计算应用中也会出现这个问题。本方案的目标是设计、分析和实现实用的算法，以实现在多处理器中以较低的通信成本进行数据迁移。问题的组合模型导致了边着色及其在适当的图表示上的推广。针对这些问题的算法将在两个具有不同特点的应用领域实施和评估：计算科学和信息科学。这项工作预计将产生以下更广泛的影响：需要并行计算的计算科学应用程序正变得更加数据密集型，因为许多科学和工程学科都可以获得大规模数据集。数据访问仍然是大规模多处理器的一个重要瓶颈，拟议的工作有望缓解这些应用的数据访问成本。一名研究生将接受该项目的培训，并接受组合科学计算中更广泛的研究问题的培训。基于这项工作的一个模块将包括在关于并行计算的研究生课程中。该协会还参与了组合科学计算的社区建设活动。

ABSTRACT0515218Alex PothenOld Dominion Research FoundationData Migration in Parallel Computing: Models and AlgorithmsScientific computing problems being solved on multiprocessors currently have large data sets thatrequire access to external memory. Redistributing the data among the processors requires aninter-processor communication schedule that minimizes (or approximately minimizes) the communication costs. This problem also arises in several other contexts: parallel file systems, parallel I/O, and in grid computing applications.The objective of this proposal is to design, analyze and implement practical algorithms that enable data migration in a multiprocessor with low communication costs. Combinatorial models of the problems lead toedge coloring and its generalizations on appropriate graph representations. Algorithms for these problemswill be implemented and evaluated on two application areas with different characteristics:computational science and information science.The broader impact this work is expected to have include the following: Applications from computational sciences that require parallel computing are becoming more data intensive, as large scale data sets become available in many scientific and engineering disciplines. Data access continues to be a significant bottleneck for large-scale multiprocessors, and the proposed work is expected to alleviate the data access costs for these applications. A graduate student will be trained in the project and also on broader research problems in combinatorial scientific computing. A module based on this work will be included in a graduate courseon parallel computing. The PI is also involved in community building activities in combinatorial scientific computing.