Efficient Schemes for Parallel Communication
Eli Upfal · Journal of the ACM · 1984
A thmdy of balanced commumcatwn schemes for connecting N processors with only a constant number of hnes entering or leaving each processor is defined.It is proved that this network topology enables a fully distributed probabilistlc algorithm to execute a variety of communication requests efficiently.In particular it enables implementauon of an arbitrary permutation, that is, a set of N packets mitmlly located in distinct processors and destined for distinct destinations in O(logaN) steps.Similar results are proved for randomly generated communication requests.These results suggest an efficient solution to a fundamental problem in the design of parallel computers.