1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
/*===================================================================*/
//
// place_gordian.c
//
// Aaron P. Hurst, 2003-2007
// ahurst@eecs.berkeley.edu
//
/*===================================================================*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <limits.h>
#include "place_gordian.h"
#include "place_base.h"
ABC_NAMESPACE_IMPL_START
// --------------------------------------------------------------------
// Global variables
//
// --------------------------------------------------------------------
int g_place_numPartitions;
// --------------------------------------------------------------------
// globalPlace()
//
/// \brief Performs analytic placement using a GORDIAN-like algorithm.
//
/// Updates the positions of all non-fixed non-pad cells.
///
// --------------------------------------------------------------------
void globalPlace() {
bool completionFlag = false;
int iteration = 0;
printf("PLAC-10 : Global placement (wirelength-driven Gordian)\n");
initPartitioning();
// build matrices representing interconnections
printf("QMAN-00 : \tconstructing initial quadratic problem...\n");
constructQuadraticProblem();
// iterate placement until termination condition is met
while(!completionFlag) {
printf("QMAN-01 : \titeration %d numPartitions = %d\n",iteration,g_place_numPartitions);
// do the global optimization in each direction
printf("QMAN-01 : \t\tglobal optimization\n");
solveQuadraticProblem(!IGNORE_COG);
// -------- PARTITIONING BASED CELL SPREADING ------
// bisection
printf("QMAN-01 : \t\tpartition refinement\n");
if (REALLOCATE_PARTITIONS) reallocPartitions();
completionFlag |= refinePartitions();
printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
iteration++;
}
// final global optimization
printf("QMAN-02 : \t\tfinal pass\n");
if (FINAL_REALLOCATE_PARTITIONS) reallocPartitions();
solveQuadraticProblem(!IGNORE_COG);
printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
// clean up
sanitizePlacement();
printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
globalFixDensity(25, g_place_rowHeight*5);
printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
}
// --------------------------------------------------------------------
// globalIncremental()
//
/// \brief Performs analytic placement using a GORDIAN-like algorithm.
//
/// Requires a valid set of partitions.
///
// --------------------------------------------------------------------
void globalIncremental() {
if (!g_place_rootPartition) {
printf("WARNING: Can not perform incremental placement\n");
globalPlace();
return;
}
printf("PLAC-10 : Incremental global placement\n");
incrementalPartition();
printf("QMAN-00 : \tconstructing initial quadratic problem...\n");
constructQuadraticProblem();
solveQuadraticProblem(!IGNORE_COG);
printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
// clean up
sanitizePlacement();
printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
globalFixDensity(25, g_place_rowHeight*5);
printf("QMAN-01 : \t\twirelength = %e\n", getTotalWirelength());
}
// --------------------------------------------------------------------
// sanitizePlacement()
//
/// \brief Moves any cells that are outside of the core bounds to the nearest location within.
//
// --------------------------------------------------------------------
void sanitizePlacement() {
int c;
float order_width = g_place_rowHeight;
float x, y, edge, w, h;
printf("QCLN-10 : \tsanitizing placement\n");
for(c=0; c<g_place_numCells; c++) if (g_place_concreteCells[c]) {
ConcreteCell *cell = g_place_concreteCells[c];
if (cell->m_fixed || cell->m_parent->m_pad) {
continue;
}
// the new locations of the cells will be distributed within
// a small margin inside the border so that ordering is preserved
order_width = g_place_rowHeight;
x = cell->m_x, y = cell->m_y,
w = cell->m_parent->m_width, h = cell->m_parent->m_height;
if ((edge=x-w*0.5) < g_place_coreBounds.x) {
x = g_place_coreBounds.x+w*0.5 +
order_width/(1.0+g_place_coreBounds.x-edge);
}
else if ((edge=x+w*0.5) > g_place_coreBounds.x+g_place_coreBounds.w) {
x = g_place_coreBounds.x+g_place_coreBounds.w-w*0.5 -
order_width/(1.0+edge-g_place_coreBounds.x-g_place_coreBounds.w);
}
if ((edge=y-h*0.5) < g_place_coreBounds.y) {
y = g_place_coreBounds.y+h*0.5 +
order_width/(1.0+g_place_coreBounds.y-edge);
}
else if ((edge=y+h*0.5) > g_place_coreBounds.y+g_place_coreBounds.h) {
y = g_place_coreBounds.y+g_place_coreBounds.h-h*0.5 -
order_width/(1.0+edge-g_place_coreBounds.x-g_place_coreBounds.w);
}
cell->m_x = x;
cell->m_y = y;
}
}
ABC_NAMESPACE_IMPL_END
|
