Data decomposition and load balancing for networked data-parallel processing.

摘要

The improving speeds of networks and microprocessors, and the recent interest in heterogeneous parallel computing have given rise to a new parallel architecture, the parallel network. Networked parallelism has much in common with the loosely-coupled multicomputer model of computation, but it poses specific challenges that must be addressed before this paradigm can be of practical value. Three issues are central to this computational environment: high internode communication cost, heterogeneous node-performance capabilities, and fluctuating node performance due to multiuser workloads. This research has examined a number of common partitioning methods to determine those that are suitable for this programming environment. New block decomposition algorithms have been developed to accommodate the heterogeneity of the parallel network, and these are capable of offering better performance than previously proposed partitioning methods. The communication costs associated with typical partitioning techniques have been mathematically characterized in a way that permits evaluation of the relative value of various decomposition schemes for specific applications based on their communication patterns and size. A decomposition advisory system is presented that uses these mathematical characterizations, knowledge about the configuration of the network and its processors, and information about the application problem to provide advice regarding the partitioning method expected to yield the best performance.