Mapping image processing operations onto a linear systolic machine

A high-performance systolic machine, called Warp, is operational at Carnegie Mellon. The machine has a programmable systolic array of linearly connected cells, each capable of performing 10 million floating-point operations per second. Many image processing operations have been programmed on the machine. This programming experience has yielded new insights in the mapping of image processing operations onto a parallel computer. This paper identifies three major mapping methods that are particularly suited to a Warp-like parallel machine using a linear array of processing elements. These mapping methods correspond to partitioning of input dataset, partitioning of output dataset, and partitioning of computation along the time domain (pipelining). Parallel implementations of several important image processing operations are presented to illustrate the mapping methods. These operations include the Fast Fourier transform (FFT), connected component labelling, Hough transform image warping and relaxation.H.T. Kungjoined the faculty of Carnegie Mellon University in 1974 after receiving his Ph.D. degree there. Appointed to Profesor in 1982, he is currently holding Shell Distinguished Chair in Computer Science at Carnegie Mellon. He was Guggenheim Fellow in 1983–84, and a full time Architecture Consultant to ESL, Inc., a subsidiary of TRW, in 1981. Dr. Kung's current research interests are in high-performance computer architectures and their applications. He has served on editorial boards of several journals and program committees of numerous conferences in VLSI and computer science.Jon A. Webbreceived the Ph.D. degree in computer science from The University of Texas at Austin in 1980. From 1981 he has worked on the faculty of the Department of Computer Science at Carnegie-Mellon University, where he is currently a Research Computer Scientist. His research interests include the theory of vision and parallel architectures for vision. He has published papers on the recovery of structure from motion, the shape of subjective contours, the design and use of a parallel architecture for low-level vision, and experiments in the visual control of a robot vehicle. Dr. Webb is a member of the IEEE Computer Society and the Association for Computing Machinery.The research was supported in part by Defense Advanced Research Projects Agency (DOD), monitored by the Air Force Avionics Laboratory under Contract F33615-84-K-1520, and Naval Electronic Systems Command under Contract N00039-85-C-0134, in part under ARPA Order number 5147, monitored by the US Army Engineer Topographic Laboratories under contract DACA 76-85-C-0002, and in part by the Office of Naval Research under Contracts N00014-80-C-0236, NR 048-659, and N00014-85-K-0152, NR SDRJ-007