Dynamic and Randomized Load Distribution for Tree-Structured Parallel Computations on Static Interconnection Networks

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

PROPOSAL NUMBER: CCR-0091719TITLE: Dynamic and Randomized Load Distribution for Tree-Structured Parallel Computations on Static Interconnection NetworksPI: Keqin LiThis three-year project will investigate the performance of the classof random-walk-based algorithms for dynamic tree embedding to supporttree-structured parallel computations on various static networks.The research will be conducted within the framework of the product of fourspaces, namely, the embedding algorithm space, the tree model space,the static network space, and the performance measure space.The overall research objective is to thoroughly investigate and understandthe behavior of randomized tree embedding produced by random-walk-basedalgorithms in static networks to the largest extent.The methods include devising embedding algorithms, proposing randomtree models, developing analytical tools, formulating mathematical equations,generating numerical data, observing and proving general properties,and simulating dynamic embedding.The project is motivated by the fact that there are a wide spectrum oftree-structured applications in computer science and engineeringand the wide availability of distributed memory multicomputerswith static interconnection networks.The significance of the project is reflected by its wide coverage ofvarious randomized tree embedding algorithms, a number of deterministicand probabilistic tree models, a wide range of static interconnectionnetworks, and different performance measures.Algorithms and methods obtained from this project will be readily usedto support dynamic load distribution for tree-structured parallel anddistributed computing, and will have great impact on various applicationson a variety of multicomputers and distributed systems.