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

提案编号：CCR-0091719标题：树形结构的动态和随机负载分布 静态互连网络上的并行计算PI： 李克勤本项目为期三年，研究基于随机游走的动态树嵌入算法在各种静态网络上支持树结构并行计算的性能，研究将在嵌入算法空间、树模型空间、静态网络空间、和性能度量空间，研究的总体目标是最大程度地深入研究和理解静态网络中基于随机游走算法产生的随机树嵌入行为，方法包括设计嵌入算法，提出随机树模型，开发分析工具，制定数学方程，生成数值数据，观察和证明一般属性，和模拟动态嵌入。该项目的动机是，有一个广泛的树-结构化应用在计算机科学和工程中的广泛应用，以及具有静态互连网络的分布式内存多计算机的广泛应用。该项目的重要性反映在其本项目所获得的随机树嵌入算法、确定性树模型、概率树模型、静态互连网络、性能度量等方面的研究成果，将为支持树结构并行和分布式计算的动态负载分配提供有力的支持，并将对各种多机和分布式系统的应用产生重要影响。

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.