Abstract
Polymorphic Torus is a novel interconnection network for SIMD massively parallel computers, able to support effectively both local and global communication. Thanks to this characteristic, Polymorphic Torus is highly suitable for computer vision applications, since vision involves local communication at the low-level stage and global communication at the intermediate- and high-level stages. In this paper we evaluate the performance of Polymorphic Torus in the computer vision domain. We consider a set of basic vision tasks, namely,convolution, histogramming, connected component labeling, Hough transform, extreme point identification, diameter computation, andvisibility, and show how they can take advantage of the Polymorphic Torus communication capabilities. For each basic vision task we propose a Polymorphic Torus parallel algorithm, give its computational complexity, and compare such a complexity with the complexity of the same task inmesh, tree, pyramid, and hypercube interconnection networks. In spite of the fact that Polymorphic Torus has the same wiring complexity as mesh, the comparison shows that in all of the vision tasks under examination it achieves complexity lower than or at most equal to hypercube, which is the most powerful among the interconnection networks considered.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Barrow HG, Tenenbaum JM (1981) Computational vision. IEEE Proceedings 69:572–595
Batcher KE (1980) Design of a massively parallel processor. IEEE Transactions on Computers C-29:836–840
Batcher KE (1982) Bit-serial parallel processing systems. IEEE Transactions on Computers C-31:377–384
Blelloch GE, Little JJ (1986) Parallel Solution to Geometric Problems on the Scan Model of Computation. MIT Artificial Intelligence Laboratory, Cambridge, MA
Brady M (1982) Computational approach to image understanding. ACM Computing Surveys 14:3–70
Cantoni V (1986) Image processing hierarchical systems: Architectural features. In: Cantoni, V, Levialdi, S (eds) Pyramidal Systems for Computer Vision. Springer-Verlag New York, pp 21–39
Cantoni V, Levialdi S (eds) (1986) Pyramidal Systems for Computer Vision. Springer-Verlag, New York
Cantoni V, Levialdi S (1987) PAPIA: A case history. In: Uhr, L (ed) Parallel Computer Vision. Academic Press, New York, pp 3–13
Cypher RE, Sanz JLC, Snyder L (1987b) The Hough transform has O(N) complexity on SIMD N x N mesh array architectures. In: Proceedings of IEEE Workshop on Computer Architecture for Pattern Analysis and Machine Intelligence, pp 115–121
Cypher RE, Sanz JLC, Snyder L (1987a) Hypercube and shuffle-exchange algorithms for image component labeling. In: Proceedings of 1987 IEEE Workshop on Computer Architectures for Pattern Analysis and Machine Intelligence, pp 5–9
Duff MJB (1976) CLIP4: A large-scale integrated circuit array parallel processor. In: Proceedings of International Joint Conference on Pattern Recognition, pp 728–733
Duff MJB (1978) Review of the CLIP image processing system. In: Proceedings of AFIPS National Computer Conference, pp 1055–1060
Duff MJB (ed) (1983) Computing Structures for Image Processing. Academic Press, New York
Dyer CR (1982) Pyramid algorithms and machines. In: Jr, Kp, and Uhr, L (eds) Multicomputers and Image Processing. Academic Press, New York, pp 409–420
Guerra C, Hambrusch S (1987) Parallel algorithms for line detection on a mesh. In: Proceedings of IEEE Workshop on Computer Architecture for Pattern Analysis and Machine Intelligence, pp 99–106
Hillis WD (1985) The Connection Machine. The MIT Press, Cambridge, MA
Ibrahim HAH, Kender JR, Shaw DE (1986) On the application of massively parallel SIMD tree machine to certain intermediate-level vision tasks. Computer Vision, Graphics and Image Processing 36:53–75
Jrad AM, Hall RW (1987) Orthogonal fast channel: An enhanced mesh architecture. In Proceedings of the 1987 International Conference on Parallel Processing, pp 828–831
Li H, Lavin MA, Master RJL (1986) Fast Hough transform: A hierarchical approach. Computer Vision, Graphics and Image Processing 36:139–161
Li H, Maresca M (1987a) Polymorphic Torus: A new architecture for vision computation. In: Proceedings of IEEE Workshop on Computer Architectures for Pattern Analysis and Machine Intelligence, pp 176–183
Li H, Maresca M (1987c) Polymorphic-Torus Architecture for Computer Vision. Technical Report IBM RC 12492, February
Li H, Maresca M (1987d) Polymorphic-Torus Architecture for Supercomputing. Technical Report IBM RC 12568, March
Li H, Maresca M (1987b) Polymorphic-Torus network. In: Proceedings of International Conference on Parallel Processing, pp 411–414
Little JJ, Blelloch G, Cass T (1987) Parallel algorithms for computer vision on the connection machine. In: Proceedings of DARPA/ISTO Image Understanding Workshop, pp 628–638
Maresca M, Lavin MA, Li H (1988) Hough transform on Polymorphic-Torus Architecture. In: Levialdi, S (ed) Multicomputer Vision. Academic Press, New York, pp 9–21
Maresca M, Li H (1986) Morphological operations on mesh-connected computers: A generalized convolution algorithm. In: Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition, pp 299–304
Maresca M, Li H (1987) Connection Autonomy in SIMD Computers: AVLSI Implementation. Technical Report IBM RC 13028, August
Maresca M, Li H (1988a) Toward connection autonomy of fine-grain SIMD parallel architecture. In: Proceedings of Conference on Parallel Processing for Computer Vision and Display, January
Maresca M, Li H (1988b) A VLSI implementation of Polymorphic-Torus architecture. Microprocessing and Microprogramming, The Euromicro Journal 24:737–742, August
Marr D (1982) Vision. Freeman, New York
Marr D, Hildreth E (1978) Theory of edge detection. In: Proceedings of Royal Society of London B-207:187–217
Miller R, Kumar VKP, Reisis D, Stout Q (1988) Meshes with reconfigurable buses. In: Proceedings of Fifth MIT Conference on Advanced Research in VLSI, pp 176–183
Miller R, Stout Q (1987) Data movement techniques for the pyramid computer. SIAM Journal of Computing 16:38–60
Miller R, Stout QF (1985) Geometric algorithms for digitized pictures on a mesh-connected computer. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-7:216–228
Nassimi D, Sahni S (1980) Finding connected components and connected ones on a mesh-connected parallel computer. SIAM Journal of Computing 9:744–757
Nishihara HK, Larson NG (1981) Toward a real-time implementation of the Marr-Poggio Stereo-Matcher. In: Proceedings of 1981 Image Understanding Workshop, pp 21–23
Poggio T, Torre V, Koch C (1985) Computational vision and regularization theory. Nature 317:314–319
Potter JL (1983) Image Processing on the massively parallel processor. IEEE Computer 16:62–67
Potter JL (1985) The Massively Parallel Processor. The MIT Press, Cambridge, MA
Reddaway SF (1978) DAP-A flexible number cruncher. In: Proceedings of LASL Workshop on Vector and Parallel Processors, pp 233–234
Reddaway SF (1980a) An image understanding performance study on the ICL Distributed Array Processor. In: Electronics to Microelectronics. North-Holland, Amsterdam, pp 730–734
Reddaway SF (1980b) Revolutionary array processors. In: Electronics to Microelectronics. North-Holland, Amsterdam, pp 730–734
Reddaway SF (1980b) Revolutionary array processors. Electronics to Microelectronics 730–734
Rosenfeld A (1987) A report on the DARPA Image Understanding Architectures Workshop. In: Proceedings of DARPA/ISTO Image Understanding Workshop, pp 298–302
Rosenfeld A (ed) (1984) Multiresolution Image Processing and Analysis. Springer-Verlag, New York
Shaw DE (1982) The NON-VON Supercomputer, Computer Science Dept., Columbia University, New York
Shaw DE (1984) SIMD and MSIMD variants of the NON-VON supercomputer. In: Proceedings of COMPCON Spring 84, pp 360–363
Shaw DE, Sabety TM (1985) The multiple-processor PPS chip of the NON-VON 3 supercomputer. Integration, the VLSI Journal 3:161–174
Stout QF (1983) Mesh-connected computers with broadcasting. IEEE Transactions on Computers C-32:826–830
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Maresca, M., Li, H. & Sheng, M.M.C. Parallel computer vision on Polymorphic Torus architecture. Machine Vis. Apps. 2, 215–230 (1989). https://doi.org/10.1007/BF01215876
Issue Date:
DOI: https://doi.org/10.1007/BF01215876