On the Slowdown of Efficient Simulations of Multibutterflies on Butterflies and Butterfly-Derived Networks

Abstract

In this paper we compare the relative computing power of Multibutterfly netmorks to Butterflies and Butterfly-related machines. The comparisons are made using efficient simulations. The notion is that machines of comparable computational power should be able to efficiently simulate each other with only a constant increase in execution time, while a machine of lesser power will be unable to efficiently simulate a more powerful machine without a substantiaI increase in computation time. One of the most surprising results is the apparently wide disparity in computing power between Butterflies and Multibutterflies. We show that the largest Butterfly, or Butterfly-derived machine that can efficiently simulate a P-processor Multibutterfly has fewer than 0( P^epislon) processors for all constants epsilon > 0.