GENERATING AN EFFICIENT BROADCAST SEQUENCE USING REFLECTED GRAY CODES

One-to-all broadcast is frequently implemented on multicomputers using a binomial tree communication pattern. The source processor, at the r oot of the broadcast tree, completes the broadcast before the processo rs at the leaves of the tree. This imbalance can degrade performance w hen a data-parallel algorithm requires a series of broadcasts from dif ferent source processors. In this paper, we show that using a reflecte d Gray code to order broadcasts minimizes the communication time.