Abstract
In this paper we present an approach to localize the data transfer in processor arrays. Our aim is to select channels between processors of the processor array performing the data transfers. Channels can be varying with respect to the bandwidth and to the communication delay and can be bidirectional. Our objective is to minimize the implementation cost of the channels while satisfying the data dependencies. The presented approach also applies to the problem of localizing data dependencies for a given interconnection topology. The formulation of our method as an integer linear program allows its use for automatic parallelization.
Chapter PDF
References
W.H. Chou and S.Y. Kung. Scheduling partitioned algorithms on processor arrays with limited communication support. In Proc. IEEE Int. Conf. on Application Specific Systems, Architectures and Processors’93, pages 53–64, Venice, 1993.
A. Darte and Y. Robert. Constructive methods for scheduling uniform loop nests. IEEE Trans. on Parallel and Distributed Systems, 5(8):814–822, 1994.
M. Dion, T. Risset, and Y. Robert. Resource constraint scheduling of partitioned algorithms on processor arrays. Integration, the VLSI Journal, 20:139–159, 1996.
D. Fimmel and R. Merker. Determination of the processor functionality in the design of processor arrays. In Proc. IEEE Int. Conf. on Application Specific Systems, Architectures and Processors’97, pages 199–208, Zü;rich, 1997.
D. Fimmel and R. Merker. Design of processor arrays for real-time applications. In Proc. Int. Conf. Euro-Par’ 98, pages 1018–1028, Southampton, 1998. Lecture Notes in Computer Science, Springer.
J.A.B. Fortes and D.I. Moldovan. Parallelism detection and transformation techniques useful for vlsi algorithms. Journal of Parallel and Distributed Computing, 2:277–301, 1985.
R.M. Karp, R.E. Miller, and S. Winograd. The organization of computations for uniform recurrence equations. Journal of the ACM, 14:563–590, 1967.
S.Y. Kung. VLSI Array Processors. Prentice Hall, Englewood Cliffs, 1987.
P.Z. Lee and Z.M. Kedem. Mapping nested loop algorithms into multidimensional systolic arrays. IEEE Trans. on Parallel and Distributed Systems, 1:64–76, 1990.
S.K. Rao. Regular Iterative Algorithms and their Implementations on Processor Arrays. PhD thesis, Stanford University, 1985.
A. Schrijver. Theory of Integer and Linear Programming. John Wiley & Sons, New York, 1986.
L. Thiele. Resource constraint scheduling of uniform algorithms. Int. Journal on VLSI and Signal Processing, 10:295–310, 1995.
Y. Wong and J.M. Delosme. Optimal systolic implementation of n-dimensional recurrences. In Proc. ICCD, pages 618–621, 1985.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fimmel, D., Merker, R. (1999). Localization of Data Transfer in Processor Arrays. In: Amestoy, P., et al. Euro-Par’99 Parallel Processing. Euro-Par 1999. Lecture Notes in Computer Science, vol 1685. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48311-X_52
Download citation
DOI: https://doi.org/10.1007/3-540-48311-X_52
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66443-7
Online ISBN: 978-3-540-48311-3
eBook Packages: Springer Book Archive