Parallel algorithms based on expander graphs for optical computing

Ramamohan Paturi, Dau Tsuong Lu, Joseph E. Ford, Sadik C. Esener, Sing H. Lee

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


We consider the task of interconnecting processors to realize efficient parallel algorithms. We propose interconnecting processors using certain graphs called expander graphs, which can provide fast communication from any group of processors to the rest of the network. We show that these interconnections would result in a number of efficient parallel algorithms for sorting, routing, associative memory, and fault-tolerance networks. As the interconnections based on expander graphs are global and irregular, we reason that optical interconnections are preferred to electronic and propose implementation of these interconnections using the programmable optoelectronic multiprocessor architecture.

Original languageEnglish (US)
Pages (from-to)917-927
Number of pages11
JournalApplied Optics
Issue number8
StatePublished - Mar 10 1991
Externally publishedYes


  • Expander graphs
  • Optical computing
  • Optical interconnection

ASJC Scopus subject areas

  • Atomic and Molecular Physics, and Optics
  • Engineering (miscellaneous)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Parallel algorithms based on expander graphs for optical computing'. Together they form a unique fingerprint.

Cite this