Browse Prior Art Database

Optical Facility for Parallel Enumeration Sort

IP.com Disclosure Number: IPCOM000101329D
Original Publication Date: 1990-Aug-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 4 page(s) / 93K

Publishing Venue

IBM

Related People

Huang, KS: AUTHOR [+3]

Abstract

Disclosed is a method for implementing sorting with optical devices. The basic idea is illustrated in Fig. 1. For actual implementation, additional supporting lenses or devices may be needed. The major goal is to sort a sequence of N items in constant time steps. (Image Omitted)

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Optical Facility for Parallel Enumeration Sort

       Disclosed is a method for implementing sorting with
optical devices.  The basic idea is illustrated in Fig. 1.  For
actual implementation, additional supporting lenses or devices may be
needed.  The major goal is to sort a sequence of N items in constant
time steps.

                            (Image Omitted)

      Given a sequence of integers A = {A1, a2, ..., aN}, this
disclosed optical facility assigns a rank ri, where 1 & ri & N, to
each element ai in A, such that ri > rj if ai > aj, and
ri = rj if ai = aj, for ij = 1,2, ..., N, in only
O(1) time steps.

      This optical facility implements an algorithm of enumeration
sort:  the position of each element of A in the sorted sequence is
determined by counting the number of elements larger than it.  The
operations needed to be performed are:
    Compare all pairs of ai and aj in A.  There are O(N2) such
comparisons.
    Calculate the rank rj of each element aj in A.  The rank rj is
defined as the number of elements ai in A (including aj itself)
larger than or equal to the element aj.  The optical facility (Fig.
1) executes these operations in a constant time.  It functions as
follows:
   Step 1 - Compare all parts of ai and aj in parallel.

      In order to compare a pair of elements ai, aj, a subtraction is
required between those two numbers.  All the minuends ai are arranged
in a one-dimensional vertical vector, also denoted as A in the
disclosed facility.  They are represented in the spatial amplitude
trans mittance of an input transducer which is illuminated by
coherent beams.  The amplitude transmittance of cell i is
proportional to ai .  This vertical input data is spread out
horizontally by a cylindrical lens.  The cylindrical lens duplicates
each ai into N copies, which are...