Abstract
This paper presents systematic methods, based on graph theoretic approach, for mapping of neural networks onto mesh connected SIMD arrays. The methods are applicable to a large class of multilayer network models, which can be represented in terms of sparse matrix vector operations. The class of computers, that the mappings are suitable for, encompasses most of the experimental and commercial mesh-connected SIMD arrays of processors. There are three methods described in the paper, one for the case of a processor array, which is larger or equal to the network size and two for the partitioned case, i.e. array smaller than the input data size. The methods are illustrated on an example of a multilayer perceptron with back-propagation learning, which consists ofn nuerons ande synaptic connections. For the first method, the processor array is assumed to be of sizeN×N, whereN 2 ≥n+e, and the required local memory of processors is limited to only a few registers. The implementation of a single iteration of a recall phase according to the method requires 24(N-1) shifts. For this method we have developed a software tool, which generates a sequence of pseudo instructions, such as elemental data shift and arithmetic operations, that implement a given neural network on a given size processor array. For the two partitioned methods, the processor array is of sizeP×P, whereP 2≤n+e, and the local memory in the processors is of sizeO(K). The faster of the two methods requiresO(N 3/P 3 K) time for an iteration of the recall or learning phase.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
DARPA Neural Network Study, AFCEA Publication, 1988
J.B. Hampshire II, and A.H. Waibel, “A Novel Objective Function for Improved Phoneme Recognition Using Time-Delay Neural Networks,”,IEEE Transactions on Neural Networks, 1990, pp. 216–228.
R.P. Gorman and T.J. Sejnowski, “Learned Classification of Sonar Targets Using a Massively Parallel Network,”IEEE Transactions on Acoustics, Speech and Signal Processing, 1988, pp. 1135–1140.
J.R. Brown, S.J. Archer and M.R. Bower, “Neural Net Classifier for Millimeter Wave Radar,”SPIE Real-Time Signal Processing XII, vol. 1154, 1989, pp. 71–76.
J. Pearson, “Applications of Neural Networks in Video Signal Processing,”1990 IEEE Conference on Neural Information Processing Systems-Neural and Synthetic, Denver 1990.
K. Wojtek Przytula and V.K. Prasanna Kumar,Parallel Digital Implementations of Neural Networks, Englewood Cliffs, N.J.: Prentice Hall, to be published in 1992.
H.M. Hasting and S. Waner, “Neural nets on the MPP,”Frontiers of Massively Parallel Scientific Computation, James R. Fisher, ed., NASA, 1987.
D.A. Pomerleau, G.L. Gusciora, D.S. Touretzky and H.T. Kung, “Neural network simulation at warp speed: How we got 17 million connections per second,”Proc. of International Conference on Neural Networks, San Diego, 1988.
G. Belloch and C. Rosenberg, “Network Learning on the Connection Machine,”Proc. of 10th International Joint Conference on Artificial Intelligence, Milan, Italy, 1987.
Soheil Shams and Wojtek Przytula, “Mapping of Neural Networks onto Programmable Parallel Machines,”Proceedings of the IEEE International Symposium on Circuits and Systems, New Orleans, Louisiana, 1990.
S.Y. Kung, and J.N. Hwang, “Systolic Architectures for Artificial Neural Nets,”International Conference on Neural Networks, San Diego, 1988.
Sherryl Tomboulian, “A System for Routing Arbitrary Directed Graphs on SIMD Architectures,” Institute for Computer Applications in Science and Engineering, NASA Langley Research Center, ICASE Report No. 87-14, 1987.
Sherryl Tomboulian, “Introduction to a System for Implementing Neural Net Connections on SIMD Architectures,” Institute for Computer Applications in Science and Engineering, NASA Langley Research Center, ICASE Report No. 88-3, 1988.
Sherryl Tomboulian, “Overview and Extensions of a System for Routing Directed Graphs on SIMD Architectures,”Proceedings of Frontiers of Massively Parallel Processing, 1988.
Daniel Hillis,The Connection Machine, Cambridge, MA: MIT Press, 1985.
DAP Series Technical Overview, Active Memory Technology Inc., 1989.
Peter Christy, “Picture-Perfect Parallel Processing,ESD, 1989, pp. 49–52.
J.L. Potter, ed.,The Massively Parallel Processor, Cambridge, MA: MIT Press, 1985.
M.J. Little and J. Grinberg, “The 3-D Computer: An Integrated Stack of WSI Wafers”,Wafer Scale Integration, (Earl Swartzlander, ed.), Boston: Kluwer Academic Publishers, 1989.
K.W. Przytula, “Medium Grain Parallel architecture for Image and Signal Processing,”Parallel Architectures and Algorithms for Image Understanding (Prasanna Kumar ed.) Academic Press, 1991.
Yaun Le Cun, John Denker, Sove Solla, Richard Howard and Lawrence Jockel, “Optimal Brain Damage,”Proceedings of 1989 IEEE Conference on Neural Information Processing Systems —Natural and Synthetic, Denver, 1989.
S.Y. Kung, and J.N. Hwang, “A Unified Modeling of Connectionist Neural Networks,”International Joint Conference on Neural Networks, 1989.
Wei-Ming Lin,NetMap Software for Mapping Neural Networks onto Mesh Connected Arrays, Hughes Research Laboratories, Internal Report, 1991.
J.L. McClelland, D.E. Rumelhart, and the PDP Research Group,Parallel Distributed Computing, vol I, Cambridge, MA: MIT Press, 1986.
K.W. Ptzytula and G. Nash, “A Special Purpose Processor for Robotics and Signal Processing,” International Conference on Robotics and Automation, Philadelphia, 1988.
V.K. Prasanna Kumar and K. Wojtek Przytula, “Algorithmic Mapping of Neural Network Models onto Parallel SIMD Machines”Intl' Conf. on Applications-Specific Array Processors, 1990.
Uwe Schweigelsohn, “A Shortperiodic Two-dimensional Systolic Sorting Algorithm,”Proc. of Intl. Conf. on Systolic Arrays, 1988, pp. 257–264.
Wei-Ming Lin, V.K. Prasanna Kumar and K. Wojtek Przytula, “Algorithmic Mapping of Neural Network Models onto Parallel SIMD Machines,”IEEE Transactions on Computers, vol. 40, no. 12, 1991, pp. 1390–1401.
Wei-Ming Lin, “Mapping Image Algorithms onto Fixed Size Window Architectures,” PhD thesis, USC, 1991.
Author information
Authors and Affiliations
Additional information
This research was supported in part by the National Science Foundation under grant MIP-8714689 and IRI-9145810.
Preliminary versions of the results contained in this paper appear in the International Conference on Applications-Specific Array Processors 1990 and the IEEE Workshop on VLSI Signal Processing 1990.
Rights and permissions
About this article
Cite this article
Wojtek Przytula, K., Prasanna, V.K. & Lin, WM. Parallel implementation of neural networks. J VLSI Sign Process Syst Sign Image Video Technol 4, 111–123 (1992). https://doi.org/10.1007/BF00925117
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF00925117