An Array with Reconfigurable Optical Buses (AROB) is essentially an m x n reconfigurable mesh in which the buses are implemented using optical technology. This model has attracted the attention of many researchers in the recent past owing to its promise in superior practical performance.

In this talk we present various algorithms (both deterministic and randomized) for packet routing, sorting, and selection. One of our results on packet routing is an algorithm that routes any h-relation in O(h) time with high probability. In contrast, the best known algorithm for routing h-relations on the OCPC model runs in O(h + log log n) time with high probability.

This is joint work with Sartaj Sahni.

Back to Workshop Schedule

1996-1997 Mathematics in High Performance Computing