The Limited Applicability of Block
Decomposition in Cluster Computing

Phyllis E. Crandall
Computer Science and Engineering Department
University of Connecticut
Storrs, CT 06269

This paper investigates the usefulness of block partitioning in cluster computing in light of recent network improvements such as FDDI and high-speed switch technology. Mathematical characterizations of the communication costs for contiguous partitioning and block decomposition in both a ring-connected and switched network are presented. Simulations of ring and switch technologies indicate that as network speeds increase and as the effects of message-preparation latency dominate, the advantages claimed for block decomposition diminish.