Abstract

Sorting is a fundamental operation that has important implications in a vast number of areas. For instance, sorting is heavily utilized in applications such as database machines, in which hashing techniques are used to accelerate data-processing algorithms. It is also the basis for interprocessor message routing and has strong implications in video telecommunications. However, high-speed electronic sorting networks are difficult to implement with VLSI technology because of the dense, global connectivity required. Optics eliminates this bottleneck by offering global interconnects, massive parallelism, and noninterfering communications. We present a parallel sorting algorithm and its efficient optical implementation. The algorithm sorts n data elements in few steps, independent of the number of elements to be sorted. Thus it is a constant-time sorting algorithm [i.e., O(1) time]. We also estimate the system’s performance to show that the proposed sorting algorithm can provide at least 2 orders of magnitude improvement in execution time over conventional electronic algorithms.

© 1995 Optical Society of America

Performance analysis of self-electro-optic-effect-device-based (SEED-based) smart-pixel arrays used in data sorting

M. P. Y. Desmulliez, B. S. Wherrett, A. J. Waddie, J. F. Snowdon, and J. A. B. Dines
Appl. Opt. 35(32) 6397-6416 (1996)

Optical content-addressable parallel processor for high-speed database processing

Ahmed Louri and James A. Hatch
Appl. Opt. 33(35) 8153-8163 (1994)

Optical implementation of a constant-time multicomparand bit-parallel magnitude-comparison algorithm using wavelength- and polarization-division multiplexing with application to parallel database processing

Abram Detofsky, Peng Yin Choo, and Ahmed Louri
Opt. Lett. 23(17) 1372-1374 (1998)

Visual-area coding technique (VACT): optical parallel implementation of fuzzy logic and its visualization with the digital-halftoning process

Tsuyoshi Konishi, Jun Tanida, and Yoshiki Ichioka
Appl. Opt. 34(17) 3097-3102 (1995)

Optical content-addressable parallel processor: architecture, algorithms, and design concepts

Ahmed Louri
Appl. Opt. 31(17) 3241-3258 (1992)