No Access

The Systolic Reconfigurable Mesh

MARY M. ESHAGHIAN-WILNER

Department of Electrical Engineering, University of California at Los Angeles, Los Angeles, CA 90095-1594, USA

The present address of the author.

Search for more papers by this author

and

RUSS MILLER

Department of Computer Science, State University of New York at Buffalo, Buffalo, NY 14260, USA

Search for more papers by this author

https://doi.org/10.1142/S0129626404001921Cited by:5 (Source: Crossref)

Abstract

In this paper, we introduce the Systolic Reconfigurable Mesh (SRM), which combines aspects of the reconfigurable mesh with that of systolic arrays. Every processor controls a local switch that can be reconfigured during every clock cycle in order to control the physical connections between its four bi-directional bus lines. Data is input on one side of the systolic reconfigurable mesh and output from another side, one row/column per unit time. Efficient algorithms are presented for intermediate-level vision tasks, including histograming, connectivity, convexity, and proximity.

Keywords:

References

H. M. Alnuweiri, IEEE Trans. on Parallel and Distributed Systems 320 (1994), DOI: 10.1109/71.277785. Google Scholar
D. Chinet al., IEEE Transactions on Consumer Electronics 34(2), 285 (1988), DOI: 10.1109/30.2943. Crossref, Web of Science, Google Scholar
R. Cypher, J. L. C. Sanz and L. Snyder, EREW PRAM and mesh connected computer algorithms for image component labeling, Proceedings of the IEEE Workshop on Computer Architecture for Pattern Analysis and Machine Intelligence (1987) pp. 122–128. Google Scholar
M. J. B. Duff, Special Computer Architectures for Pattern Processing (1982) pp. 65–86. Google Scholar
Mary M. Eshaghian, IEEE Transactions on Computers 40(7), 827 (1991), DOI: 10.1109/12.83620. Crossref, Web of Science, Google Scholar
Mary M. Eshaghianet al., Reconfigurable Massively Parallel Computers, eds. H. Li and Q. Stout (Prentice Hall, 1991) pp. 64–87. Google Scholar
Terry J. Fountain, K. N. Mathews and Michael J. B. Duff, IEEE Transactions on Pattern Analysis and Machine Intelligence 10(3), 310 (1988), DOI: 10.1109/34.3896. Crossref, Web of Science, Google Scholar
Dan W. Hammerstorm and Daniel P. Lulich, Proceedings of the IEEE 84(7), 1005 (1996). Crossref, Web of Science, Google Scholar
M. C. Herbordt, C. C. Weems and M. J. Scudder, Machine Vision and Applications 5(2), 105 (1992), DOI: 10.1007/BF02620310. Crossref, Web of Science, Google Scholar
J.-W. Jang, H. Park and V. K. Prasanna, A fast algorithm for computing histograms on a reconfigurable mesh, Proc. 4th Symposium on Frontiers of Massively Parallel Computation (IEEE, 1992) pp. 244–251. Google Scholar
J.-F. Jenq and S. Sahni, Histogramming on a reconfigurable mesh computer, Proc. 6th International Parallel Processing Symposium (IEEE, 1992) pp. 425–432. Google Scholar
R. Milleret al., IEEE Trans. on Computers 42(6), 678 (1993), DOI: 10.1109/12.277290. Crossref, Web of Science, Google Scholar
R. Miller and Q. F. Stout, IEEE Transactions on Pattern Analysis and Machine Intelligence (1985). Google Scholar
R. Miller and Q. F. Stout, IEEE Transactions on Computers 1605 (1988), DOI: 10.1109/12.9737. Web of Science, Google Scholar
V. K. Prasanna-Kumar and M. Mary Eshaghian, Parallel geometric algorithm for digitized pictures on mesh of trees, Proc. of IEEE International Conference on Parallel Processing (1986) pp. 270–273. Google Scholar
Lorenz A. Schmitt and Stephen S. Wilson, IEEE Transactions on Pattern Analysis and Machine Intelligence 10(3), 320 (1988), DOI: 10.1109/34.3897. Crossref, Web of Science, Google Scholar
J. Rose, A. El Gamal and A. Sangiovanni-Vincentelli, Proceedings of the IEEE (1993). Google Scholar
S. Hauck, Proceedings of IEEE 86, (1998), DOI: 10.1109/5.663540. Google Scholar
S. Schaumont et al. , A quick safari through the reconfiguration jungle , Proceedings of the 38th Design Automation Conference ( 2001 ) . Google Scholar
Xilinx Inc. Xilinx platform FPGAs. http://www.xilinx.com . Google Scholar
K. Q. Li and V. Y. Pan, IEEE Transactions on Computers 50(2), 519 (2001). Web of Science, Google Scholar
Mary M. Eshaghian and Lili Hai, Journal of Parallel and Distributed Computing 61, 737 (2001), DOI: 10.1006/jpdc.2001.1704. Crossref, Web of Science, Google Scholar
Mary M. Eshaghian and Lili Hai , Handi-book on Innovative Computing ( 2005 ) , DOI: 10.1007/0-387-27705-6_10 . Google Scholar
K. Bondalapati. Modeling and Mapping of Dynamically Reconfigurable Hybrid Architectures. PhD thesis, University of Southern California, 2001 . Google Scholar
K. Bondalapati and V. K. Prasanna, Current Science 78(7), 828 (2000). Web of Science, Google Scholar
Kiran Bondalapati and Viktor K. Prasanna, Proceedings of IEEE (2002). Google Scholar
R. Milleret al., Meshes with reconfigurable buses, Proc. 15th MIT Conference on Advanced Research in VLSI (1988) pp. 163–178. Google Scholar
H. Li and M. Maresca, IEEE Trans. on Computers 38(9), 1345 (1989), DOI: 10.1109/12.29479. Crossref, Web of Science, Google Scholar
C. C. Weemset al., International Journal of Computer Vision 2, 251 (1989), DOI: 10.1007/BF00158166. Crossref, Web of Science, Google Scholar
K. Nakano, Parallel Processing Letters 5(1), 111 (1995), DOI: 10.1142/S0129626495000102. Link, Web of Science, Google Scholar
A. Condon, R. E. Ladner, J. Lampe, and R. Sinha. Complexity of sub-bus mesh computations. Technical Report 93-10-02, Dept. of CS&EE, U. of Washington, 1993 . Google Scholar
R. Miller and Q. F. Stout , Parallel Algorithms for Regular Architectures: Meshes and Pyramids ( The MIT Press , Cambridge, Mass , 1996 ) . Google Scholar
R. L. Graham, Information Processing Letters 1, 132 (1972), DOI: 10.1016/0020-0190(72)90045-2. Crossref, Google Scholar
B. F. Wang and G. H. Chen, Information Processing Letters 36, 31 (1990), DOI: 10.1016/0020-0190(90)90182-W. Crossref, Web of Science, Google Scholar
S. Olariu, J. L. Schwing and J. Zhang, Journal of Computer and Software Engineering 1, 33 (1993). Web of Science, Google Scholar

Vol. 14, No. 03n04

Metrics

Downloaded 12 times

History

Received 1 November 2003

Revised 1 July 2004

Keywords

PDF download

The Systolic Reconfigurable Mesh

Abstract

Recommended