Self-simulation for the passive optical star

Optical technology offers simple interconnection schemes with straightforwa rd layouts that support complex logical interconnection patterns. The passi ve optical star (POS), in which communication takes place via optical wavel engths agreed upon between senders and receivers, is often suggested as a p latform 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, focusing on the scalab ility or self-simulation issue, which is a fundamental concern of great imp ortance to the simplicity of algorithm design and program portability. A fa mily of parallel machines is scalable or self-simulating if any member of t he family can simulate any larger member with k times as many processors wi th a slowdown close to k; i.e., scalability states that if a certain effici ency is achievable on a large machine, then it is achievable on any smaller machine as well. A pos is balanced if the number of available wavelengths equals the number of processors. We show that the balanced pos is highly sc alable by presenting a universal randomized simulation of a kn-processor ba lanced pos on an H-processor balanced pos, for arbitrary integers n, k grea ter than or equal to 1, with an expected slowdown of O(k + log* n). We also describe a deterministic simulation with a slowdown of O(min{k(2), k + log n}) and show that a slowdown of O(k) is achievable if the communication pa ttern of each step is known in advance and available for preprocessing. For a certain restricted class of self simulations we establish matching upper and lower bounds of Theta(k(2)). We also show that the balanced pos is equ ivalent to a balanced version of the well-known COLLISION CRCW PRAM, where we now take the balance condition to mean that the number of shared memory cells is the same as the number of processors. (C) 2000 Academic Press.