THE AVERAGE DIAMETER OF GENERAL TREE-STRUCTURES

In this paper, we study the static behavior of distributed memory arch itecture with general tree structures. After defining and discussing t he notion of average diameter, we first show that the average time it takes to send messages between any two arbitrary processors in a binar y tree structure with n processors is Theta(log n), through combinator ial analysis. We will also show that we can extend this result to gene ral tree structures with n nodes, with a reasonable assumption, i.e., when m = o(n), where m is the maximum number of children any node coul d have. We believe that the results presented in this paper have captu red some important inter-processor data transmission behavior of compu ters with distributed memory architectures, particularly those with (b inary) tree structured inter-processor networks. As an application of combinatorial and asymptotic analysis, this paper solves yet another a verage path length problem, thus is also theoretically interesting. Fi nally, some of the techniques we have developed in this paper might al so be useful in the study of similar problems. (C) 1998 Elsevier Scien ce Ltd. All rights reserved.