Abstract

Shift-connected digital optical single-instruction multiple-data (SIMD) arrays¹ comprise a 2-D (N × N) array of 1-bit logic/arithmetic elements with optical inputs and outputs, a memory that stores binary images, and hardware to perform arbitrary, programmable space-invariant shifts on data images as they are brought from memory to the logic array. Results of logic operations are returned to the memory in parallel. Such a shift-connected array can efficiently perform multiples of dense matrices or of sparse matrices possessing a multidiagonal structure from which algorithms for matrix inversion, partial differential equations, and eigenvalue problems can be assembled. Multiplication of an N vector by an N × N dense matrix requires computation time proportional to K², where K is the number of bits of precision desired, and memory proportional to K. Multiplication of an N² vector by an N² × N² sparse matrix with multidiagonal structure corresponds to accumulating weighted, shifted versions of an N × N array of numbers. Computation time required is proportional to DK², where D is the number of nonzero diagonals. Memory required also depends linearly on D. Because shifts across multiple processing elements are available, 2-D shift-connected arrays can easily be programmed to have 3-D or 4-D topologies as well.¹ Multiples by sparse matrices arising from the discretization of continuous problems in two to four dimensions can be optimally performed on a processor array with the same dimensionality. The case of implementing these algorithms derives from the 2-D parallelism and global data movement capability of optical systems.

© 1986 Optical Society of America