📄 ch15.7.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML EXPERIMENTAL 970324//EN">
<HTML>
<HEAD>
<META NAME="GENERATOR" CONTENT="Adobe FrameMaker 5.5/HTML Export Filter">
<TITLE> 15.7 Partitioning Methods</TITLE></HEAD><!--#include file="top.html"--><!--#include file="header.html"-->
<DIV>
<P>[ <A HREF="CH15.htm">Chapter start</A> ] [ <A HREF="CH15.6.htm">Previous page</A> ] [ <A HREF="CH15.8.htm">Next page</A> ]</P><!--#include file="AmazonAsic.html"--><HR></DIV>
<H1 CLASS="Heading1">
<A NAME="pgfId=1883">
</A>
15.7 <A NAME="29058">
</A>
Partitioning Methods</H1>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=1887">
</A>
System partitioning requires goals and objectives, methods and algorithms to find solutions, and ways to evaluate these solutions. We start with measuring connectivity, proceed to an example that illustrates the concepts of system partitioning and then to the algorithms for partitioning.</P>
<P CLASS="Body">
<A NAME="pgfId=11422">
</A>
Assume that we have decided which parts of the system will use ASICs. The goal of partitioning is to divide this part of the system so that each partition is a single ASIC. To do this we may need to take into account any or all of the following objectives:</P>
<UL>
<LI CLASS="BulletFirst">
<A NAME="pgfId=1891">
</A>
A maximum size for each ASIC</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=1897">
</A>
A maximum number of ASICs</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=12182">
</A>
A maximum number of connections for each ASIC</LI>
<LI CLASS="BulletLast">
<A NAME="pgfId=12183">
</A>
A maximum number of total connections between all ASICs</LI>
</UL>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=12188">
</A>
We know how to measure the first two objectives. Next we shall explain ways to measure the last two.</P>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=1901">
</A>
15.7.1 <A NAME="31222">
</A>
Measuring Connectivity</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=1903">
</A>
To measure connectivity we need some help from the mathematics of graph theory. It turns out that the terms, definitions, and ideas of graph theory are central to ASIC construction, and they are often used in manuals and books that describe the knobs and dials of ASIC design tools.</P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=175900">
</A>
</P>
<DIV>
<IMG SRC="CH15-8.gif">
</DIV>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigureTitle">
<A NAME="pgfId=175903">
</A>
FIGURE 15.6 <A NAME="41480">
</A>
Networks, graphs, and partitioning. (a) A network containing circuit logic cells and nets. (b) The equivalent graph with vertexes and edges. For example: logic cell D maps to node D in the graph; net 1 maps to the edge (A, B) in the graph. Net 3 (with three connections) maps to three edges in the graph: (B, C), (B, F), and (C, F). (c) Partitioning a network and its graph. A network with a net cut that cuts two nets. (d) The network graph showing the corresponding edge cut. The net cutset in c contains two nets, but the corresponding edge cutset in d contains four edges. This means a graph is not an exact model of a network for partitioning purposes.</P>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=152148">
</A>
<A HREF="CH15.7.htm#41480" CLASS="XRef">
Figure 15.6</A>
(a) shows a circuit schematic, netlist, or <A NAME="marker=152137">
</A>
network. The network consists of <A NAME="marker=152149">
</A>
circuit modules<A NAME="marker=152150">
</A>
A–F. Equivalent terms for a circuit module are a cell, logic cell, macro, or a block. A cell or logic cell usually refers to a small logic gate (NAND etc.), but can also be a collection of other cells; macro refers to gate-array cells; a block is usually a collection of gates or cells. We shall use the term <SPAN CLASS="Emphasis">
logic cell</SPAN>
in this chapter to cover all of these.</P>
<P CLASS="Body">
<A NAME="pgfId=94255">
</A>
Each logic cell has electrical connections between the <A NAME="marker=1922">
</A>
terminals (<A NAME="marker=94238">
</A>
connectors or <A NAME="marker=1924">
</A>
pins). The network can be represented as the mathematical <A NAME="marker=1926">
</A>
graph shown in <A HREF="CH15.7.htm#41480" CLASS="XRef">
Figure 15.6</A>
(b). A graph is like a spider’s web: it contains <A NAME="marker=175919">
</A>
vertexes (or <A NAME="marker=1930">
</A>
vertices) A–F (also known as graph <A NAME="marker=1932">
</A>
nodes or <A NAME="marker=1934">
</A>
points) that are connected by <A NAME="marker=1936">
</A>
edges. A graph <A NAME="marker=1938">
</A>
vertex corresponds to a logic cell. An electrical <A NAME="marker=1940">
</A>
connection (a <A NAME="marker=12206">
</A>
net or a <A NAME="marker=12207">
</A>
signal) between two logic cells corresponds to a graph <A NAME="marker=1942">
</A>
edge.</P>
<P CLASS="Body">
<A NAME="pgfId=3879">
</A>
<A HREF="CH15.7.htm#41480" CLASS="XRef">
Figure 15.6</A>
(c) shows a network with nine logic cells A–I. A connection, for example between logic cells A and B in <A HREF="CH15.7.htm#41480" CLASS="XRef">
Figure 15.6</A>
(c), is written as net (A, B). Net (A, B) is represented by the single edge (A, B) in the network graph, shown in <A HREF="CH15.7.htm#41480" CLASS="XRef">
Figure 15.6</A>
(d). A net with three terminals, for example net (B, C, F), must be modeled with three edges in the network graph: edges (B, C), (B, F), and (C, F). A net with four terminals requires six edges and so on. <A HREF="CH15.7.htm#41480" CLASS="XRef">
Figure 15.6</A>
illustrates the differences between the nets of a network and the edges in the network graphs. Notice that a net can have more than two terminals, but a terminal has only one net.</P>
<P CLASS="Body">
<A NAME="pgfId=9965">
</A>
If we divide, or partition, the network shown in <A HREF="CH15.7.htm#41480" CLASS="XRef">
Figure 15.6</A>
(c) into two parts, corresponding to creating two ASICs, we can divide the network’s graph in the same way. <A HREF="CH15.7.htm#41480" CLASS="XRef">
Figure 15.6</A>
(d) shows a possible division, called a <A NAME="marker=9969">
</A>
cutset. We say that there is a <A NAME="marker=9989">
</A>
net cutset (for the network) and an <A NAME="marker=9990">
</A>
edge cutset (for the graph). The connections between the two ASICs are <A NAME="marker=9970">
</A>
external connections, the connections inside each ASIC are <A NAME="marker=9971">
</A>
internal connections. </P>
<P CLASS="Body">
<A NAME="pgfId=3243">
</A>
Notice that the number of external connections is not modeled correctly by the network graph. When we divide the network into two by drawing a line across connections, we make <A NAME="marker=1976">
</A>
net cuts. The resulting set of net cuts is the net cutset. The number of net cuts we make corresponds to the number of external connections between the two partitions. When we divide the network graph into the same partitions we make <A NAME="marker=1980">
</A>
edge cuts and we create the edge cutset. We have already shown that nets and graph edges are not equivalent when a net has more than two terminals. Thus the number of edge cuts made when we partition a graph into two is not necessarily equal to the number of net cuts in the network. As we shall see presently the differences between nets and graph edges is important when we consider partitioning a network by partitioning its graph [<A NAME="Schweikert79">
</A>
Schweikert and Kernighan, 1979].</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=1991">
</A>
15.7.2 <A NAME="10529">
</A>
A Simple Partitioning Example</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=1993">
</A>
<A HREF="CH15.7.htm#14578" CLASS="XRef">
Figure 15.7</A>
(a) shows a simple network we need to partition [<A NAME="Goto86">
</A>
Goto and Matsud, 1986]. There are 12 logic cells, labeled A–L, connected by 12 nets (labeled 1–12). At this level, each logic cell is a large circuit block and might be RAM, ROM, an ALU, and so on. Each net might also be a bus, but, for the moment, we assume that each net is a single connection and all nets are weighted equally. The goal is to partition our simple network into ASICs. Our objectives are the following:</P>
<UL>
<LI CLASS="BulletFirst">
<A NAME="pgfId=5267">
</A>
Use no more than three ASICs.</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=5270">
</A>
Each ASIC is to contain no more than four logic cells.</LI>
<LI CLASS="BulletList">
<A NAME="pgfId=5273">
</A>
Use the minimum number of external connections for each ASIC.</LI>
<LI CLASS="BulletLast">
<A NAME="pgfId=5276">
</A>
Use the minimum total number of external connections.</LI>
</UL>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=2011">
</A>
<A HREF="CH15.7.htm#14578" CLASS="XRef">
Figure 15.7</A>
(b) shows a partitioning with five external connections; two of the ASICs have three pins; the third has four pins.We might be able to find this arrangement by hand, but for larger systems we need help.</P>
<TABLE>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=191951">
</A>
(a)</P>
<DIV>
<IMG SRC="CH15-9.gif">
</DIV>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=191956">
</A>
(b)</P>
<DIV>
<IMG SRC="CH15-10.gif">
</DIV>
</TD>
</TR>
<TR>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigTitleSide">
<A NAME="pgfId=191959">
</A>
FIGURE 15.7 <A NAME="14578">
</A>
Partitioning example. (a) We wish to partition this network into three ASICs with no more than four logic cells per ASIC. (b) A partitioning with five external connections (nets 2, 4, 5, 6, and 8)—the minimum number. (c) A constructed partition using logic cell C as a seed. It is difficult to get from this local minimum, with seven external connections (2, 3, 5, 7, 9,11,12), to the optimum solution of b.</P>
</TD>
<TD ROWSPAN="1" COLSPAN="1">
<P CLASS="TableFigure">
<A NAME="pgfId=191967">
</A>
(c)</P>
<DIV>
<IMG SRC="CH15-11.gif">
</DIV>
</TD>
</TR>
</TABLE>
<P CLASS="Body">
<A NAME="pgfId=161689">
</A>
Splitting a network into several pieces is a <A NAME="marker=161688">
</A>
network partitioning problem. In the following sections we shall examine two types of algorithms to solve this problem and describe how they are used in system partitioning. <A HREF="CH15.7.htm#20759" CLASS="XRef">
Section 15.7.3</A>
describes <A NAME="marker=161693">
</A>
constructive partitioning, which uses a set of rules to find a solution. <A HREF="CH15.7.htm#25880" CLASS="XRef">
Section 15.7.4</A>
describes <A NAME="marker=161697">
</A>
iterative partitioning improvement (or <A NAME="marker=161698">
</A>
iterative partitioning refinement), which takes an existing solution and tries to improve it. Often we apply iterative improvement to a constructive partitioning. We also use many of these partitioning algorithms in solving floorplanning and placement problems that we shall discuss in Chapter 16.</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=161707">
</A>
15.7.3 <A NAME="20759">
</A>
Constructive Partitioning</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=2060">
</A>
The most common constructive partitioning algorithms use <A NAME="marker=11963">
</A>
seed growth or <A NAME="marker=11965">
</A>
cluster growth. A simple <A NAME="marker=2058">
</A>
seed-growth algorithm for constructive partitioning consists of the following steps:</P>
<OL>
<LI CLASS="NumberFirst">
<A NAME="pgfId=2064">
</A>
Start a new partition with a seed logic cell.</LI>
<LI CLASS="NumberList">
<A NAME="pgfId=16279">
</A>
Consider all the logic cells that are not yet in a partition. Select each of these logic cells in turn.</LI>
<LI CLASS="NumberList">
<A NAME="pgfId=2066">
</A>
Calculate a gain function, <SPAN CLASS="EquationVariables">
g(m)</SPAN>
, that measures the benefit of adding logic cell <SPAN CLASS="EquationVariables">
m</SPAN>
to the current partition. One measure of gain is the number of connections between logic cell <SPAN CLASS="EquationVariables">
m</SPAN>
and the current partition.</LI>
<LI CLASS="NumberList">
<A NAME="pgfId=2068">
</A>
Add the logic cell with the highest gain <SPAN CLASS="EquationVariables">
g(m)</SPAN>
to the current partition.</LI>
<LI CLASS="NumberList">
<A NAME="pgfId=2070">
</A>
Repeat the process from step 2. If you reach the limit of logic cells in a partition, start again at step 1.</LI>
</OL>
<P CLASS="Body">
<A NAME="pgfId=27029">
</A>
We may choose different gain functions according to our objectives (but we have to be careful to distinguish between connections and nets). The algorithm starts with the choice of a <A NAME="marker=152195">
</A>
seed logic cell (<A NAME="marker=152196">
</A>
seed module, or just <A NAME="marker=152197">
</A>
seed). The logic cell with the most nets is a good choice as the seed logic cell. You can also use a set of seed logic cells known as a <A NAME="marker=27034">
</A>
cluster. Some people also use the term <SPAN CLASS="Emphasis">
clique</SPAN>
—borrowed from graph theory. A <A NAME="marker=118830">
</A>
<A NAME="marker=118841">
</A>
clique of a graph is a subset of nodes where each pair of nodes is connected by an edge—like your group of friends at school where everyone knows everyone else in your clique . In some tools you can use schematic pages (at the leaf or lowest hierarchical level) as a starting point for partitioning. If you use a high-level design language, you can use a Verilog module (different from a circuit module) or VHDL entity/architecture as seeds (again at the leaf level).</P>
</DIV>
<DIV>
<H2 CLASS="Heading2">
<A NAME="pgfId=2084">
</A>
15.7.4 <A NAME="25880">
</A>
Iterative Partitioning Improvement</H2>
<P CLASS="BodyAfterHead">
<A NAME="pgfId=11982">
</A>
The most common iterative improvement algorithms are based on <A NAME="marker=12266">
</A>
interchange and <A NAME="marker=12268">
</A>
group migration. The process of interchanging (swapping) logic cells in an effort to improve the partition is an <A NAME="marker=2088">
</A>
interchange method. If the swap improves the partition, we accept the trial interchange; otherwise we select a new set of logic cells to swap.</P>
<P CLASS="Body">
<A NAME="pgfId=16342">
</A>
There is a limit to what we can achieve with a partitioning algorithm based on simple interchange. For example, <A HREF="CH15.7.htm#14578" CLASS="XRef">
Figure 15.7</A>
(c) shows a partitioning of the network of part a using a constructed partitioning algorithm with logic cell C as the seed. To get from the solution shown in part c to the solution of part b, which has a minimum number of external connections, requires a complicated swap. The three pairs: D and F, J and K, C and L need to be swapped—all at the same time. It would take a very long time to consider all possible swaps of this complexity. A simple interchange algorithm considers only one change and rejects it immediately if it is not an improvement. Algorithms of this type are <A NAME="marker=16380">
</A>
greedy algorithms in the sense that they will accept a move only if it provides immediate benefit. Such shortsightedness leads an algorithm to a <A NAME="marker=16381">
</A>
local minimum from which it cannot escape. Stuck in a valley, a greedy algorithm is not prepared to walk over a hill to see if there is a better solution in the next valley. This type of problem occurs repeatedly in CAD algorithms.</P>
<P CLASS="Body">
<A NAME="pgfId=2102">
</A>
Group migration consists of swapping groups of logic cells between partitions. The group migration algorithms<A NAME="marker=2097">
</A>
are better than simple interchange methods at improving a solution but are more complex. Almost all group migration methods are based on the powerful and general <A NAME="marker=2099">
</A>
Kernighan–Lin algorithm (<A NAME="marker=2101">
</A>
K–L algorithm) that partitions a graph [<A NAME="Kernighan70">
</A>
Kernighan and Lin, 1970]. The problem of dividing a graph into two pieces, minimizing the nets that are cut, is the <A NAME="marker=12274">
</A>
min-cut problem—a very important one in VLSI design. As the next section shows, the K–L algorithm can be applied to many different problems in ASIC design. We shall examine the algorithm next and then see how to apply it to system partitioning.</P>
</DIV>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -