📄 node21.html
字号:
<html><!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95.1 (Fri Jan 20 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE>2.7 Case Study: Floorplan Optimization</TITLE>
</HEAD>
<BODY>
<meta name="description" value="2.7 Case Study: Floorplan Optimization">
<meta name="keywords" value="book">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>
<BR> <HR><a href="msgs0.htm#2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#2"><img ALIGN=MIDDLE src="asm_color_tiny.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/asm_color_tiny.gif" alt="[DBPP]"></a> <A NAME=tex2html2095 HREF="node20.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node20.html"><IMG ALIGN=MIDDLE ALT="previous" SRC="previous_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/previous_motif.gif"></A> <A NAME=tex2html2103 HREF="node22.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node22.html"><IMG ALIGN=MIDDLE ALT="next" SRC="next_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/next_motif.gif"></A> <A NAME=tex2html2101 HREF="node14.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node14.html"><IMG ALIGN=MIDDLE ALT="up" SRC="up_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/up_motif.gif"></A> <A NAME=tex2html2105 HREF="node1.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node1.html"><IMG ALIGN=MIDDLE ALT="contents" SRC="contents_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/contents_motif.gif"></A> <A NAME=tex2html2106 HREF="node133.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node133.html"><IMG ALIGN=MIDDLE ALT="index" SRC="index_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/index_motif.gif"></A> <a href="msgs0.htm#3" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/tppmsgs/msgs0.htm#3"><img ALIGN=MIDDLE src="search_motif.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/search_motif.gif" alt="[Search]"></a> <BR>
<B> Next:</B> <A NAME=tex2html2104 HREF="node22.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node22.html">2.8 Case Study: Computational Chemistry</A>
<B>Up:</B> <A NAME=tex2html2102 HREF="node14.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node14.html">2 Designing Parallel Algorithms</A>
<B> Previous:</B> <A NAME=tex2html2096 HREF="node20.html" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node20.html">2.6 Case Study: Atmosphere Model</A>
<BR><HR><P>
<H1><A NAME=SECTION02370000000000000000>2.7 Case Study: Floorplan Optimization</A></H1>
<P>
<A NAME=secfloor> </A>
<P>
Our second case study is an example of a highly irregular, symbolic
problem. The solution that we develop incorporates a task scheduling
algorithm.
<A NAME=1840> </A>
<P>
<H2><A NAME=SECTION02371000000000000000>2.7.1 Floorplan Background</A></H2>
<P>
VLSI is a process used to build
<A NAME=1842> </A>
electronic components such as microprocessors and memory chips
comprising millions of transistors. The design of VLSI components is
a computationally demanding process. Computers are used extensively
to verify the correctness of a circuit design, to lay out a circuit in
a two-dimensional area, and to generate the patterns used to test
circuits once they have been fabricated. Many of these problems
involve either an exhaustive or a heuristically guided search of a
large space of possible solutions. Here, we consider a layout
problem. The first stage of the VLSI design process typically
produces a set of indivisible rectangular blocks called <em> cells</em>.
In a second stage, interconnection information is used to determine
the relative placements of these cells. In a third stage,
implementations are selected for the various cells with the goal of
optimizing the total area. It is the third stage, <em>
floorplan optimization</em>, for which we shall develop a parallel
algorithm. This is an important part of the design process, since the
cost of a chip is usually dominated by its area.
<P>
VLSI floorplan optimization can be explained by analogy with the
problem of designing a kitchen. Assume that we have decided on the
components the kitchen is to contain (this action is stage 1 of
the VLSI design process) and how these components are to be arranged
(stage 2). For example, we may wish to have a stove, refrigerator,
table, and sink and may require that the stove be next to the refrigerator
and the table next to the sink. Assume also that we can choose
among several possible models for each of these components, with
different models having different shapes but occupying the same floor
area. In the floorplan optimization phase of our kitchen design, we
select models so as make the best use of available floorspace.
<P>
In VLSI, a floorplan is represented as a pair of polar graphs,
conventionally called the <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img286.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img286.gif"> and <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img287.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img287.gif"> graphs. (A polar
graph is a directed acyclic graph with a single source and a single
sink. The term <i> directed</i> means that edges have a direction, and
<i> acyclic</i> means that there are no cycles.) These graphs specify
which cells are adjacent in the vertical and horizontal directions,
respectively. Each arc denotes a cell, and nodes (other than the
source and sink) link cells that must have touching edges.
<P>
Although a cell has a fixed area, it may have several possible
implementations with different aspect ratios. If we have
<em> N</em>
cells, and if cell <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img288.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img288.gif"> has <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img289.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img289.gif"> implementations, then the
total number of possible floorplan configurations is
<P><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img290.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img290.gif"><P>
For example, Figure <A HREF="node21.html#figfloor1" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node21.html#figfloor1">2.27</A> shows a floorplan optimization
problem with three cells and six possible
configurations.
<P>
<P><A NAME=2857> </A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img297.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img297.gif">
<BR><STRONG>Figure 2.27:</STRONG> <em> A floorplan optimization problem. The three cells A, B, and C,
have 1, 3, and 2 implementations each, respectively. In (a) are the
alternative implementations. In (b) are the <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img294.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img294.gif"> and <IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img295.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img295.gif">
graphs, which state that B must be above C, and that A must be to the
left of B and C, respectively. In (c) are the <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img296.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img296.gif">
alternative floorplans that satisfy the constraints; each is labeled
with its area. The lowest area floorplan is constructed from A, B0,
and C1 and has an area of 130.</em><A NAME=figfloor1> </A><BR>
<P>
<P>
<P><A NAME=2872> </A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img298.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img298.gif">
<BR><STRONG>Figure 2.28:</STRONG> <em> Solving a floorplan optimization problem. This
is the search tree corresponding to the problem illustrated in Figure
2.27. Level 0 is the root. At level 1, an implementation has been
chosen for A; the three level 2 subtrees represent the choices for B
and the level 3 leaves the choices for C. The number in each tree
node represents the area of the associated (partial) solution. The
optimal configuration is (A,B0,C1) and has area
130.</em><A NAME=figfloor2> </A><BR>
<P>
<P>
The problem then is to identify the configuration with the lowest
area, where area is defined as the product of the maximum horizontal
and vertical extents. This identification can be achieved by using a search
algorithm to explore a search tree representing all possible
configurations. As shown in Figure <A HREF="node21.html#figfloor2" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node21.html#figfloor2">2.28</A>, level <em> i</em>
of
this tree corresponds to the situation in which implementations have been
chosen for <em> i</em>
cells. We can explore this search tree by using
Algorithm <A HREF="node10.html#algsearch" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#algsearch">1.1</A>. An initial call <tt> search(root)</tt> causes the
entire tree to be visited, with the path used to get to each leaf node
reported as a solution.
<P>
<A NAME=1871> </A>
Algorithm <A HREF="node10.html#algsearch" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#algsearch">1.1</A> implements an <em> exhaustive search
</em>
that visits all nodes of the search tree. Unfortunately, this
strategy is computationally infeasible for any but the smallest
problems. For example, a problem with just 20 cells and 6
implementations per cell has a search space of <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img299.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img299.gif"> nodes. Fortunately, the number of nodes explored can be
reduced considerably
by using a technique called <em> branch-and-bound
</em> search. The
basic idea is to keep track of the best (lowest area) solution found
so far. Before ``expanding'' a node (that is, looking at its
subtrees), we check whether the area of the partial configuration
represented by that node is already greater than that of the best
known solution. If so, we know that this node cannot yield a better
solution, and the subtree rooted at that node can be abandoned,
<A NAME=1877> </A>
or <em> pruned
</em> (Figure <A HREF="node21.html#figfloor3" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node21.html#figfloor3">2.29</A>). This approach is
specified as Algorithm <A HREF="node21.html#algbbs" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node21.html#algbbs">2.2</A>, with the global variable
<em> A</em>
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img300.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img300.gif"> used to maintain a record of the best solution.
<P>
<A NAME=1884> </A>
<P><A NAME=2890> </A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img301.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img301.gif">
<BR><STRONG>Figure 2.29:</STRONG> <em> Branch-and-bound search. This figure shows the nodes actually
explored in the example problem, assuming a depth-first and
left-to-right search strategy. The subtree rooted at the second node
on level 2 is pruned because the cost of this node (170) is greater
than that of the cheapest solution already found
(130).</em><A NAME=figfloor3> </A><BR>
<P>
<P>
<P><A NAME=algbbs> </A><IMG BORDER=0 ALIGN=BOTTOM ALT="" SRC="img302.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img302.gif"><P>
<P>
<A NAME=1903> </A>
<P>
On a sequential computer, the <tt> foreach</tt> in Algorithm <A HREF="node21.html#algbbs" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node21.html#algbbs">2.2</A>
can examine each subtree in turn, thereby giving a <em> depth-first
</em>
search algorithm that explores the tree depth-first and left-to-right.
<A NAME=1907> </A>
In this case, pruning can reduce the number of nodes explored
enormously. In one experiment reported in the literature, the number
of nodes explored in a typical 20-cell problem was reduced from
<IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img303.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img303.gif"> to <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img304.gif" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/img304.gif">. As we shall see, efficient
pruning is a difficult problem in a parallel environment and, to a
large extent, determines the structure of our parallel algorithm.
<P>
In summary, the fundamental operation to be performed in the floorplan
optimization problem is branch-and-bound search. This is an
interesting algorithm from a parallel computing perspective because of
its irregular computational structure: the size and shape of the
search tree that must be explored are not known ahead of time.
Also, the need for pruning introduces a need both to manage the
order in which the tree is explored and to acquire and propagate
global knowledge of computation state. In these respects this problem
is typical of many algorithms in symbolic (nonnumeric) computing.
<P>
<H2><A NAME=SECTION02372000000000000000>2.7.2 Floorplan Algorithm Design</A></H2>
<P>
<H4><A NAME=SECTION02372010000000000000> Partition.</A></H4>
<P>
<A NAME=1911> </A>
Algorithm <A HREF="node21.html#algbbs" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node21.html#algbbs">2.2</A>, like Algorithm <A HREF="node10.html#algsearch" tppabs="http://www.dit.hcmut.edu.vn/books/system/par_anl/node10.html#algsearch">1.1</A>, has no obvious
data structure to which we can apply domain decomposition techniques.
Hence, we use a fine-grained functional decomposition in which each
search tree node is explored by a separate task. As noted earlier,
this means that new tasks will be created in a wavefront as the search
progresses down the search tree, which will tend to be explored in a
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -