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

点击翻译按钮获取中文摘要

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.