29-06-2012, 04:12 PM
Hypergraph Partitioning with Fixed Vertices
Hypergraph Partitioning with Fixed Vertices.pdf (Size: 176.17 KB / Downloads: 18)
Abstract
We empirically assess the implications of fixed terminals for
hypergraph partitioning heuristics. Our experimental testbed incorporates
a leading-edge multilevel hypergraph partitioner and IBM-internal circuits
that have recently been released as part of the ISPD-98 Benchmark Suite.
We find that the presence of fixed terminals can make a partitioning instance
considerably easier (possibly to the point of being “trivial”); much
less effort is needed to stably reach solution qualities that are near bestachievable.
Toward development of partitioning heuristics specific to the
fixed-terminals regime, we study the pass statistics of flat FM-based partitioning
heuristics. Our data suggest that more fixed terminals implies
that the improvements within a pass will more likely occur near the beginning
of the pass.
INTRODUCTION
Hypergraph partitioning research in very large scale integration
(VLSI) computer-aided design (CAD) has been primarily motivated
by the gate-level top-down placement context, which in modern
ASIC design methodology can demand extremely efficient and
high-quality solutions for netlist sizes exceeding one million vertices.
New heuristics for hypergraph partitioning are typically evaluated in
the context of free hypergraphs, where all vertices are free to move
into any partition [2], [4]. Every benchmark, and every benchmark
result reported in the literature, is for the free-hypergraph context.
Even when input–output (I/O) pad locations are specified in the .vpnr
or .yal source for early ACM/SIGDA benchmarks, the partitioning
benchmarks (in .are format; see [1]) do not indicate how these
pads correspond to fixed vertices in partitions.
TOWARD PARTITIONERS FOR THE FIXED-TERMINALS REGIME
A motivating observation is that in the absence of sufficient fixed
terminals, FM may occasionally produce passes in which nearly every
vertex is moved. Recall that during an FM pass, vertices are moved one
at a time until each vertex has been moved; for bipartitioning, all vertices
have been “flipped” when the end of the pass is reached. Then,
the best solution found during the pass (i.e., best prefix of the move sequence)
is restored. Any move “undone” in this process has essentially
been wasted. Without terminals, FM will occasionally produce passes
in which almost no moves are wasted—the pass flips almost all vertices
between partition zero and partition one. However, if there are sufficiently
many vertices adjacent to fixed terminals, such a “near-flip” is
very unlikely to be improving. Table II documents the average number
of passes per run and the average percentage of vertices moved per
pass: increasingly higher percentages of the moves in theFM passes are
wasted as the proportion of fixed terminals increases. This strongly suggests
that in the fixed-terminals regime, FM-style heuristics can profitably
impose a hard cutoff on pass lengths.
TOWARD BENCHMARKS FOR THE FIXED-TERMINALS REGIME
Our experiments indicate that the nature of the partitioning problem
may be changed by the presense of sufficiently many terminals. Since
several effects cannot be presently explained, further research is required.
To facilitate collaborative research on partitioning with fixed
terminals, we propose a new type of benchmarks that capture sufficient
information to make them a reasonable substitute to partitioning calls
from running a top-down placer. We require the following features.
CONCLUSIONS AND ONGOING WORK
We have empirically demonstrated a mismatch between the
top-down placement context and current directions in VLSI CAD
hypergraph partitioning research and benchmarking. We point out
how easy the partitioning problem becomes when fixed terminals are
present. We believe that there is a great deal of work remaining to be
done in the area of extremely fast partitioning for the fixed-terminals
regime, i.e., the real-world placement context.