Alex Pothen Old Dominion Research Foundation
Data Migration in Parallel Computing: Models and Algorithms
Scientific computing problems being solved on multiprocessors currently have large data sets that require access to external memory. Redistributing the data among the processors requires an inter-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 to edge coloring and its generalizations on appropriate graph representations. Algorithms for these problems will 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 course on parallel computing. The PI is also involved in community building activities in combinatorial scientific computing.
