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

Suny College At New Paltz, New Paltz NY

Investigators

Abstract

PROPOSAL NUMBER: CCR-0091719 TITLE: Dynamic and Randomized Load Distribution for Tree-Structured Parallel Computations on Static Interconnection Networks PI: Keqin Li This three-year project will investigate the performance of the class of random-walk-based algorithms for dynamic tree embedding to support tree-structured parallel computations on various static networks. The research will be conducted within the framework of the product of four spaces, 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 understand the behavior of randomized tree embedding produced by random-walk-based algorithms in static networks to the largest extent. The methods include devising embedding algorithms, proposing random tree 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 of tree-structured applications in computer science and engineering and the wide availability of distributed memory multicomputers with static interconnection networks. The significance of the project is reflected by its wide coverage of various randomized tree embedding algorithms, a number of deterministic and probabilistic tree models, a wide range of static interconnection networks, and different performance measures. Algorithms and methods obtained from this project will be readily used to support dynamic load distribution for tree-structured parallel and distributed computing, and will have great impact on various applications on a variety of multicomputers and distributed systems.