Self-Simulation for the Passive Optical Star

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 use of pos optical technology as the communication medium for parallel computing. In particular, a feature of parallel models which is extremely important for the simplicity of algorithm design and program portability is the scalability property or self-simulation capability. It states that when a computation achieves a certain speedup on a large machine with many processors, then it achieves a similar speedup on any smaller machine (relative to the number of processors). We show that the pos is indeed scalable, namely, we present a randomized algorithm for an n-processor pos that does not assume global knowledge and that simulates a kn-processor pos with a slowdown of O..