Download A Field-Programmable Prototyping Board - Courses

7.10. Performance
61
Augment2(NetNodes,SOLUTION DESIRED) f
Recursive Breadth,First,Search *=
=*
for each unassigned node
'cnn'
f
mark cnn;
=*
check if net cnn can pick a pad of opposite color for
its solution which some other net wants *=
pad = swap if available2(cnn,SOLUTION DESIRED);
if (!pad) pad = Augment1(NetNodes,SOLUTION DESIRED);
if (pad) return(pad);
for each unmarked pad 'p' connected to cnn f
for each unmarked node 'nn' connected to p f
if ('nn' has a solution that cnn is looking for using pad p) f
g
g
==
g
g
mark p;
put nn onto NextQ;
recursive call
pad = Augment2(NextQ,SOLUTION DESIRED);
if (pad) f
g
g
nd the node 'cnn' which wants to use pad for its solution;
rpad = swap(pad, cnn);
return(rpad);
Figure 7.8: The Augment2() Algorithm.
program. Figure 7.9 shows the pseudocode for the main program loop, and for the
Solve() procedure called by the main loop.
7.10 Performance
Let n be the number of nets to be pairwise assigned, p be the maximum number
of pads each net can be assigned to, and w be the number of window sizes spanned.
The default Augment2() algorithm runs in O(n2p2 ) time. This is because of the
particular implementation of the breadth rst search algorithm, which looks at every
node, and every pad connected to every node. One would expect that the algorithm