Optimal Placement of Processors based on Effective Communication Load

Authors: A. R. Aswatha, T. Basavaraju, N. Bhaskara Rao

Abstract:

This paper presents a new technique for the optimum placement of processors to minimize the total effective communication load under multi-processor communication dominated environment. This is achieved by placing heavily loaded processors near each other and lightly loaded ones far away from one another in the physical grid locations. The results are mathematically proved for the Algorithms are described.

Keywords: Ascending Sort Index Vector, EffectiveCommunication Load, Effective Distance Matrix, OptimalPlacement, Sorting Order.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1063254

References:

[1] Prof. David Pan. VLSI placement (II). Users.ece.utexas.edu/~dpan/2006Sp_EE382V/notes/lecture20_placemen t_2.ppt
[2] Andrew B. Kahng University of California & Gabriel Robins University of Virginia. "On Optimal Interconnections for VLSI" vlsi.ucsd.edu/Publications/Books/Books.pdf
[3] M. S. Bazaraa, J. Jarvis, and H. D. Sherali. Linear Programming and Network Flows. John Wiley & Sons, 2nd edition, 1990.
[4] J. Kleinhans, G. Sigl, F. Johannes, and K. Antreich. GORDIAN: VLSI placement by quadratic programming and slicing optimization. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems,10(3):356-365, 1991.
[5] H. Eisenmann and F. M. Johannes. Generic global placement and floorplanning. In Proc. Design Automation Conf, pages 269-274, 1998.
[6] M. W. P. Savelsbergh. A branch-and-price algorithm for the generalized assignment problem. Operations Research, 6:831-841, 1997.