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

摘要：alex PothenOld Dominion Research foundation并行计算中的数据迁移：模型和算法目前在多处理器上解决的科学计算问题有大量数据集，需要访问外部存储器。在处理器之间重新分配数据需要一个最小化（或近似最小化）通信成本的处理器间通信调度。这个问题也出现在其他几个上下文中：并行文件系统、并行I/O和网格计算应用程序。本提案的目标是设计、分析和实现实用的算法，使数据迁移在多处理器中具有低通信成本。问题的组合模型引出了在适当的图表示上的边着色及其推广。这些问题的算法将在两个具有不同特征的应用领域实现和评估：计算科学和信息科学。这项工作预计将产生以下更广泛的影响：随着许多科学和工程学科中大规模数据集的可用性，需要并行计算的计算科学应用正变得越来越数据密集。数据访问仍然是大型多处理器的一个重要瓶颈，所提出的工作有望减轻这些应用程序的数据访问成本。研究生将在该项目中接受训练，并在组合科学计算中进行更广泛的研究问题。基于这项工作的一个模块将包含在并行计算的研究生课程中。PI还参与了组合科学计算的社区建设活动。

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.