Self-Simulation for the Passive Optical Star Model

Pascal Berthomé, Th. Duboux, Torben Hagerup, Ilan Newman, Assaf Schuster

Abstract

In the context of parallel computing, optical technology offers simple interconnection schemes with straightforward layouts that support complex logical interconnection patterns. The Passive Optical Star (Pos) is often suggested as a platform for implementing the optical network: logically it offers an all-to-all broadcast capability. We investigate the self-simulation or scalability properties of the Pos. A family of parallel machines is said to be self-simulating or scalable if reducing the number of processors by a factor of k (by going to a smaller member of the family) increases the computation time by a factor of (the optimal) O(k). We present a randomized algorithm for an n-processor Pos that simulates a kn-processor Pos with a slowdown of O(k+log* n) using local control only, thus coming close to the self-simulation ideal of O(k). We also analyze direct algorithms that send messages directly from their origin to their destination; for this case we prove that Θ(k 2) is the exact complexity.
BibTeX
@inproceedings{berthome1995self,
  author = {Pascal Berthomé and Th. Duboux and Torben Hagerup and Ilan Newman and Assaf Schuster},
  title = {{Self-Simulation for the Passive Optical Star Model}},
  booktitle = {ESA},
  year = {1995},
  doi = {10.1007/3-540-60313-1\_156},
}

Loading related content...

Figure