A symbolic substitution based parallel architecture and algorithms for high-speed parallel processing

ABSTRACT

A new parallel architecture that is amenable to optical implementation is presented for massively data-parallel computing. The architecture is an SIMD model that exploits spatial parallelism and processes 2-D binary images as fundamental computational entities. Processing is based on a new technique called symbolic substitution logic. A hierarchical mapping technique is presented for designing data-parallel algorithms and mapping them onto the optical architecture. The mapping of several numerical algorithms onto the architecture is presented. Implementation issues as well as performance analysis of the optical system are also considered.

REFERENCES

• 1: K. Hwang, Z. Xu, and A. Louri, "Remps: An electro-optical supercomputer for parallel solution of PDE problems," in Proc. 2nd Int'l. Conf. on Supercomputing (Santa Clara), May 5 - 8, 1987.
• 2: A. A. Sawchuk and T. C. Stand, "Digital optical computing," Proceedings of The IEEE, vol. 72, no. 7, pp. 758-779, July 1984.
• 3: K. E. Batcher, "Design of a massively parallel processor," IEEE Transactions on Computers, vol. C-29, pp. 836-884, Sept 1980.
• 4: M. J. Duff (Fu and Ichikawa, eds.), CLIP Special computer Architecture for Pattern Recognition, CRC Press, 1982.
• 5: S. F. Reddaway, DAP—a distributed array processor, Proceedings of the 1st annual symposium on Computer architecture, p.61-65, December 09-11, 1973
• 6: W D Hillis, The connection machine, MIT Press, Cambridge, MA, 1985
• 7: A. Huang, "Parallel algorithms for optical digital computers," In Proceedings IEEE Tenth int'l Optical Computing Conf., pp. 13- 17, 1983.
• 8: K. H. Brenner, A. Huang, and N. Streibl, "Digital optical computing with symbolic substitution," Applied Optics, vol. 25, no. 18, pp. 3054- 3060, 15 Sept 1986.
• 9: K. Hwang and A. Louri, "Optical multiplication and division using modifed signed-digit symbolic substitution," Optical Engineering, Special issue on Optical Computing, vol. 28, no. 4, pp. 364- 373, April 1989.
• 10: R. W. Hockney , C. R. Jesshope, Parallel Computers Two: Architecture, Programming and Algorithms, IOP Publishing Ltd., Bristol, UK, 1988
• 11: Thinking Machine Corporation, "Connection machine model CM-2 technical summary," Technical Report Series ttA87-4, Thinking Machine Corporation, 1986.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Single-instruction-stream, multiple-data-stream processors (SIMD)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms