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

题目：静态互联网络上树形结构并行计算的动态和随机负载分布[id: Keqin li]这个为期三年的项目将研究一类基于随机行走的动态树嵌入算法的性能，以支持各种静态网络上的树形结构并行计算。研究将在四个空间的乘积框架内进行，即嵌入算法空间、树模型空间、静态网络空间和性能度量空间。总体研究目标是最大程度地深入研究和理解基于随机行走算法的随机树嵌入在静态网络中的行为。方法包括设计嵌入算法，提出随机树模型，开发分析工具，制定数学方程，生成数值数据，观察和证明一般性质，模拟动态嵌入。这个项目的动机是由于在计算机科学和工程中有广泛的树形结构应用，以及具有静态互连网络的分布式内存多计算机的广泛可用性。该项目的重要性体现在其广泛覆盖各种随机树嵌入算法，许多确定性和概率树模型，广泛的静态互连网络和不同的性能度量。本课题所获得的算法和方法将很容易用于支持树结构并行和分布式计算的动态负载分配，并将对各种多计算机和分布式系统的各种应用产生重大影响。

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.