Optimal Placement of Processors based on Effective Communication Load

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.

Authors:

• A. R. Aswatha
• T. Basavaraju
• N. Bhaskara Rao

Keywords:

• Ascending Sort Index Vector
• EffectiveCommunication Load
• Effective Distance Matrix
• OptimalPlacement
• Sorting Order.

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.