RITUAL An Algorithm for Performance-Driven Placement of Cell-Based ICs

A. Srinivasan, K. Chaudhary and Ernest S. Kuh

EECS Department
University of California, Berkeley
Technical Report No. UCB/ERL M91/47
May 1991

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/ERL-91-47.pdf

In this paper we describe an efficient algorithm for obtaining a placement of cell-based ICs subject to performance constraints. Using sophisticated mathematical techniques, we are able to solve large problems quickly and effectively. The algorithm is very simple and elegant, making it easy to implement. In addition, it yields good results as we show on a set of real examples. On the average, we are able to make 20% improvement in the wire delay of these examples with little or no impact on the total Steiner tree wirelength. The acronym RITUAL represents the key idea of our technique: Residual Iterative Technique for Updating All Lagrange multipliers.

BibTeX citation:

@techreport{Srinivasan:M91/47,
    Author = {Srinivasan, A. and Chaudhary, K. and Kuh, Ernest S.},
    Title = {RITUAL An Algorithm for Performance-Driven Placement of Cell-Based ICs},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1991},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/1762.html},
    Number = {UCB/ERL M91/47},
    Abstract = {In this paper we describe an efficient algorithm for obtaining a
placement of cell-based ICs subject to performance constraints. Using
sophisticated mathematical techniques, we are able to solve large
problems quickly and effectively. The algorithm is very simple and
elegant, making it easy to implement. In addition, it yields good
results as we show on a set of real examples. On the average, we
are able to make 20% improvement in the wire delay of these examples
with little or no impact on the total Steiner tree wirelength. The
acronym RITUAL represents the key idea of our technique: Residual
Iterative Technique for Updating All Lagrange multipliers.}
}

EndNote citation:

%0 Report
%A Srinivasan, A.
%A Chaudhary, K.
%A Kuh, Ernest S.
%T RITUAL An Algorithm for Performance-Driven Placement of Cell-Based ICs
%I EECS Department, University of California, Berkeley
%D 1991
%@ UCB/ERL M91/47
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/1762.html
%F Srinivasan:M91/47