A theoretical comparison of four parallel processing networks /

Previous work on the analysis of execution time of parallel algorithms has either largely ignored communication delays or has dealt with specific interconnection structures such as the perfect shuffle and the nearest neighbor. In this paper it is shown that the communication time is just as significant as the execution time and that the communication time is dependent upon the data size. Four networks are compared, using parameters that are defined in the paper. Using a few representative algorithms it is determined that the communication time depends on, (1) the average distance between processors when the number of processors in the network is large and, (2) the average number of processors a given processor is connected to when the number of processors in the network is small. The breakeven point varies from algorithm to algorithm