Abstracts for Charles J. Alpert's Publications
Click on title for the full manuscript in
PostScript format.
C. J. Alpert and A. Devgan,
"
Wire Segmenting for Improved Buffer Insertion",
34th ACM/IEEE Design Automation Conference,
Anaheim, June 1997, pp. 588-593 (193K).
[Abstract]
Buffer insertion seeks to place buffers
on the wires of a signal net to minimize delay.
Van Ginneken [14] proposed an optimal dynamic programming
solution (with extensions proposed by [7][8][9][12]
such that at most one buffer can be placed on a single wire. This
constraint can hurt solution quality, but it may be
circumvented by dividing each wire into multiple smaller
segments. This work studies the problem
of finding the correct number of segments for each
wire in the routing tree. Too few segments yields sub-par
solutions, but too many segments can lead to excessive
run times and memory loads. We derive new theoretical results for
computing
the appropriate number of buffers (and hence wire segments)
which motivate our new wire segmenting
algorithm. We show that using wire segmenting as a
precursor to buffer insertion produces solutions within a few
percent of optimal, while using only seconds of CPU time.
C. J. Alpert, J.-H. Huang and A. B. Kahng,
"
Multilevel Circuit Partitioning",
34th ACM/IEEE Design Automation Conference,
Anaheim, June 1997, pp. 530-533 (90K).
[Abstract]
Recent work [2][5][11][12][14]
has illustrated the promise of
multilevel approaches for partitioning large circuits.
Multilevel partitioning recursively clusters
the instance until its size is smaller than a given threshold,
then unclusters the instance while applying a partitioning refinement
algorithm. Our multilevel partitioner uses
a new technique to control the number of levels
in the matching-based clustering phase and also exploits
recent innovations in classic iterative partitioning [7][10].
Our heuristic outperforms
numerous existing bipartitioning heuristics, with improvements
ranging from 6.9 to 27.9% for 100 runs and 3.0 to 20.6% for
just 10 runs (while also using less CPU time).
C. J. Alpert, T. Chan, D. J.-H. Huang, I. Markov and K. Yan,
"
Quadratic Placement Revisited",
34th ACM/IEEE Design Automation Conference,
Anaheim, June 1997, pp. 752-757 (294K).
[Abstract]
The ``quadratic placement'' methodology is rooted in [6][14][16]
and is reputedly used in many commercial and in-house tools
for placement of standard-cell and gate-array designs. The
methodology iterates between two basic steps: solving sparse systems
of linear equations, and repartitioning. This work
dissects the implementation and motivations for quadratic
placement. We first show that (i) Krylov subspace engines for solving
sparse systems of linear equations are more effective
than the traditional successive over-relaxation (SOR) engine
[15] and (ii) order convergence criteria
can maintain solution quality while using substantially fewer
solver iterations. We then discuss the motivations and relevance
of the quadratic placement approach, in the context of past and future
algorithmic technology, performance requirements, and design
methodology. We provide evidence that the use of numerical
linear systems solvers with quadratic wirelength objective may be
due to the pre-1990's weakness of min-cut partitioners, i.e.,
numerical engines were needed to provide helpful hints to
min-cut partitioners. Finally, we note emerging
methodology drivers in deep-submicron design
that may require new placement approaches to the placement problem.
C. J. Alpert, T. F. Chan, D. J.-H. Huang, A. B. Kahng,
I. L. Markov, P. Mulet and K. Yan,
"
Faster Minimization of Linear Wirelength for Global Placement",
Proceedings International Symposium on Physical Design,
Napa Valley, April 1997, pp. 4-11 (232K).
[Abstract]
A linear wirelength objective more effectively captures timing,
congestion, and other global placement considerations than a
squared wirelength objective. The GORDIAN-L cell placement
tool [16] minimizes linear wirelength by first
approximating the linear wirelength objective by a squared wirelength
objective, then executing the following loop -- (1) minimize the
current objective to yield some approximate solution, and (2) use
the resulting solution to construct a more accurate objective -- until
the solution converges.
In this paper, we first show that the GORDIAN-L loop can be viewed
as a special case of a new algorithm that generalizes a
1937 iteration due to Weiszfeld [19].
Specifically, we formulate the Weiszfeld iteration using a
regularization parameter to control the tradeoff between
convergence and solution accuracy; the GORDIAN-L iteration
is equivalent to setting this regularization parameter to zero.
Next, we describe two more recent numerical methods,
the Primal Newton iteration and the Primal-Dual Newton
iteration, that improve upon the Weiszfeld iteration.
Our Primal-Dual Newton iteration
stably attains quadratic convergence and at a much faster
rate than Weiszfeld, making it a superior choice for
implementing a placer such as GORDIAN-L, or for any
linear wirelength optimization.
C. J. Alpert and S.-Z. Yao,
"Spectral Partitioning: the More Eigenvectors
the Better", to appear in Proceedings of the 32nd
ACM/IEEE Design Automation Conference, 1995 (184K).
[Abstract]
A spectral partitioning method uses the eigenvectors
of a graph's adjacency or Laplacian matrix to construct
a geometric representation (e.g., a linear ordering) which
is then heuristically partitioned. We map each graph vertex to a
vector in d-dimensional space, where d is the number
of eigenvectors, such that these vectors constitute
an instance of the vector partitioning problem. When
all the eigenvectors are used, graph partitioning exactly
reduces to vector partitioning. This result motivates
a simple ordering heuristic that can be used to yield high-quality
2-way and multi-way partitionings. Our experiments suggest the
vector partitioning perspective opens the door to new and
effective heuristics.
[Abstract]
We present a general framework for the construction of vertex
orderings for netlist clustering. Our WINDOW algorithm
constructs an ordering by iteratively adding the vertex with
highest attraction to the existing ordering. Variant
choices for the attraction function allow our framework to
subsume many graph traversals and clustering objectives from the
literature. The DP-RP method of [3] is then applied to optimally split
the ordering into a k-way clustering. Our approach is
adaptable to user-specified cluster size constraints. Experimental
results for clustering and multi-way partitioning are encouraging.
[Abstract]
Spectral geometric embeddings of a circuit netlist can lead to fast,
high quality multi-way partitioning solutions. Furthermore, it
has been shown that d-dimensional spectral embeddings
(d > 1) are a more powerful tool than single-eigenvector
embeddings (d = 1) for multi-way partitioning [2] [4].
However, previous methods cannot fully utilize information from
the spectral embedding while optimizing netlist-dependent objectives.
This work introduces a new multi-way circuit partitioning
algorithm called DP-RP. We begin with a d-dimensional
spectral embedding from which a 1-dimensional
ordering of the modules is obtained using a spacefilling curve.
The 1-dimensional ordering retains useful information from
the multi-dimensional embedding while allowing application of
efficient algorithms. We show that for a new Restricted
Partitioning formulation, dynamic programming efficiently
finds optimal solutions in terms of Scaled Cost [4] and can
transparently handle user-specified cluster size constraints.
For 2-way ratio cut partitioning, DP-RP yields an average
of 45% improvement over KP [4] and EIG1 [6] and 48% improvement
over KC [2].
[Abstract]
We give new, effective algorithms for k-way circuit partitioning
in the two regimes of k << n and k = Theta(n), where
n is the number of modules in the circuit. We show that
partitioning an appropriately designed geometric embedding
of the netlist, rather than a traditional graph representation,
yields improved results as well as large speedups. We derive
d-dimensional geometric embeddings of the netlist via (i)
a new "partitioning-specific" net model for constructing the
Laplacian of the netlist, and (ii) computation of d
eigenvectors of the netlist Laplacian; we then apply (iii) fast
top-down and bottom-up geometric clustering methods.
[Abstract] Motivated by analysis of distributed RC delay
in routing trees, we propose a new tree construction for
performance-driven global routing which directly trades
off between Prim's minimum spanning tree algorithm and Dijkstra's
shortest path tree algorithm. This direct combination of
two objective functions and their corresponding optimal algorithms
contrasts with the more indirect "shallow-light" methods
of [2,4,10]. Our method achieves routing
trees which satisfy a given routing tree radius bound while
using less wire than previous methods. Detailed simulations
show that this wirelength savings translates into significantly
improved delay over both the method of [2] and standard
MST routing in both IC and multi-chip module (MCM) interconnect
technologies.
[Abstract]
We present a genetic circuit partitioning algorithm that
integrates the Metis graph partitioning package [15] originally
designed for sparse matrix computations. Metis is
an extremely fast iterative partitioner that uses multilevel clustering.
We have adapted Metis to partition circuit netlists, and have applied
a genetic technique that uses previous Metis solutions to help
construct new Metis solutions. Our hybrid
technique produces better results than Metis alone, and also
produces bipartitionings that are competitive with previous methods
[20] [18] [6] while using less CPU time.
C. J. Alpert and A. B. Kahng,
" Simple
Eigenvector-Based Circuit Clustering", to appear in
IEEE Intl. Symp. on Circuits and Systems,
Atlanta, May 1996 (102K).
[Abstract]
Clustering has proven effective in improving the quality of VLSI
netlist partitioning and placement algorithms. A wide variety of
clustering schemes have been proposed, including random
walks [13], iterative matching [7], and fairly
complicated spectral techniques [1] [8].
Like [1] and [8], we use eigenvectors to
compute a clustering, but do so in the simplest, most obvious manner.
Our algorithm first computes a d-digit code for each module
v_i according to the signs of the ith entries in a set of
d eigenvectors. Then, modules with the same code are assigned to
the same cluster. Despite its simplicity, this new clustering algorithm
is strongly motivated by theoretical results for both spectral
bipartitioning [6] and multi-dimensional vector partitioning [4].
The algorithm also has linear time complexity
(not including the eigenvector computation) and is at least as
effective as previous clustering algorithms in terms of two-phase
Fiduccia-Mattheyses bipartitioning.
[Abstract]
Many algorithms can find optimal bipartitions for various objectives
including minimizing the maximum cluster diameter (``min-diameter'');
these algorithms are often applied iteratively in top-down fashion
to derive a partition consisting of k clusters, with
k > 2. Bottom-up agglomerative approaches are also commonly used
to construct partitions, and we discuss these in terms
of worst-case performance for metric data sets. Our main
contribution derives from a new restricted partition formulation
that requires each cluster to be an interval of a given
ordering of the objects being clustered.
Dynamic programming can optimally
split such an ordering into a partition for a large class
of objectives that includes min-diameter. We explore a variety
of ordering heuristics and show that our algorithm, when combined
with an appropriate ordering heuristic, outperforms
traditional algorithms on both random and non-random data sets.
[Abstract]
This paper presents effective algorithms for multi-way
partitioning. Confirming ideas originally due to Hall [27],
we demonstrate that geometric embeddings of the circuit netlist
can lead to high-quality k-way partitionings. The netlist
embeddings are derived via the computation of d eigenvectors of
the Laplacian for a graph representation of the netlist.
As [27] did not specify how to partition such geometric
embeddings, we explore various geometric partitioning objectives
and algorithms, and find that they are limited because they do not
integrate topological information from the netlist.
Thus, we also present a new partitioning algorithm that exploits both
the geometric embedding and netlist information, as well as a
Restricted Partitioning
formulation that requires each cluster of the k-way partitioning
to be contiguous in a given linear ordering.
We begin with a d-dimensional spectral embedding and construct
a heuristic 1-dimensional ordering of the modules (combining
spacefilling curve with 3-Opt approaches originally
proposed for the traveling salesman problem).
We then apply dynamic programming to efficiently
compute the optimal k-way split of the ordering for a variety of
objective functions, including Scaled
Cost [12] and Absorption [44]. This approach
can transparently integrate user-specified cluster size bounds.
Experiments show that this technique yields multi-way
partitionings with lower Scaled Cost than previous spectral
approaches [2] [12] [25].
[Abstract]
Vertex orderings have been successfully applied to problems in netlist
clustering, for system partitioning and layout [2] [20].
We present a vertex ordering construction that
encompasses most reasonable graph traversals. Two parameters -- an
attraction function and a window -- provide
the means for achieving various graph traversals and addressing
particular clustering requirements.
We then use dynamic programming [2] to optimally
split the vertex ordering into a multi-way clustering. Our
approach outperforms several clustering methods in the
literature in terms of three distinct clustering objectives
[5] [8] [22]. The ordering
construction, by itself, also outperforms existing graph ordering
constructions [2] [3] [17] [19]
for this application. Tuning our approach to
``meta-objectives'', particularly clustering for two-phase
Fiduccia-Mattheyses bipartitioning [9], remains an
open area of research.
Charles Alpert's Home Page