1 /////////////////////////////////////////////////////////////////////////////
2 // Original authors: SangGi Do(sanggido@unist.ac.kr), Mingyu
3 // Woo(mwoo@eng.ucsd.edu)
4 // (respective Ph.D. advisors: Seokhyeong Kang, Andrew B. Kahng)
5 // Rewrite by James Cherry, Parallax Software, Inc.
6 //
7 // Copyright (c) 2019, The Regents of the University of California
8 // Copyright (c) 2018, SangGi Do and Mingyu Woo
9 // All rights reserved.
10 //
11 // BSD 3-Clause License
12 //
13 // Redistribution and use in source and binary forms, with or without
14 // modification, are permitted provided that the following conditions are met:
15 //
16 // * Redistributions of source code must retain the above copyright notice, this
17 // list of conditions and the following disclaimer.
18 //
19 // * Redistributions in binary form must reproduce the above copyright notice,
20 // this list of conditions and the following disclaimer in the documentation
21 // and/or other materials provided with the distribution.
22 //
23 // * Neither the name of the copyright holder nor the names of its
24 // contributors may be used to endorse or promote products derived from
25 // this software without specific prior written permission.
26 //
27 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
28 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
30 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
31 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
32 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
33 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
34 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
35 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
36 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
37 // POSSIBILITY OF SUCH DAMAGE.
38 ///////////////////////////////////////////////////////////////////////////////
39
40 #include "dpl/Opendp.h"
41
42 #include <cmath>
43 #include <limits>
44
45 #include "opendb/dbTransform.h"
46 #include "utl/Logger.h"
47
48 namespace dpl {
49
50 using std::max;
51 using std::min;
52
53 using utl::DPL;
54
55 using odb::dbBox;
56 using odb::dbTransform;
57
58 void
initGrid()59 Opendp::initGrid()
60 {
61 // Make pixel grid
62 if (grid_ == nullptr) {
63 grid_ = new Pixel *[row_count_];
64 for (int y = 0; y < row_count_; y++)
65 grid_[y] = new Pixel[row_site_count_];
66 }
67
68 // Init pixels.
69 for (int y = 0; y < row_count_; y++) {
70 for (int x = 0; x < row_site_count_; x++) {
71 Pixel &pixel = grid_[y][x];
72 pixel.cell = nullptr;
73 pixel.group_ = nullptr;
74 pixel.util = 0.0;
75 pixel.is_valid = false;
76 }
77 }
78
79 // Fragmented row support; mark valid sites.
80 for (auto db_row : block_->getRows()) {
81 int orig_x, orig_y;
82 db_row->getOrigin(orig_x, orig_y);
83
84 int x_start = (orig_x - core_.xMin()) / site_width_;
85 int x_end = x_start + db_row->getSiteCount();
86 int y = (orig_y - core_.yMin()) / row_height_;
87
88 for (int x = x_start; x < x_end; x++) {
89 grid_[y][x].is_valid = true;
90 }
91 }
92 }
93
94 void
deleteGrid()95 Opendp::deleteGrid()
96 {
97 if (grid_) {
98 for (int i = 0; i < row_count_; i++) {
99 delete [] grid_[i];
100 }
101 delete [] grid_;
102 }
103 grid_ = nullptr;
104 }
105
106 Pixel *
gridPixel(int grid_x,int grid_y) const107 Opendp::gridPixel(int grid_x,
108 int grid_y) const
109 {
110 if (grid_x >= 0 && grid_x < row_site_count_
111 && grid_y >= 0 && grid_y < row_count_)
112 return &grid_[grid_y][grid_x];
113 else
114 return nullptr;
115 }
116
117 ////////////////////////////////////////////////////////////////
118
119 void
visitCellPixels(Cell & cell,bool padded,const std::function<void (Pixel * pixel)> & visitor) const120 Opendp::visitCellPixels(Cell &cell,
121 bool padded,
122 const std::function <void (Pixel *pixel)>& visitor) const
123 {
124 dbInst *inst = cell.db_inst_;
125 dbMaster *master = inst->getMaster();
126 auto obstructions = master->getObstructions();
127 bool have_obstructions = false;
128 for (dbBox *obs : obstructions) {
129 if (obs->getTechLayer()->getType() == odb::dbTechLayerType::Value::OVERLAP) {
130 have_obstructions = true;
131
132 Rect rect;
133 obs->getBox(rect);
134 dbTransform transform;
135 inst->getTransform(transform);
136 transform.apply(rect);
137 int x_start = gridX(rect.xMin() - core_.xMin());
138 int x_end = gridEndX(rect.xMax() - core_.xMin());
139 int y_start = gridY(rect.yMin() - core_.yMin());
140 int y_end = gridEndY(rect.yMax() - core_.yMin());
141 for (int x = x_start; x < x_end; x++) {
142 for (int y = y_start; y < y_end; y++) {
143 Pixel *pixel = gridPixel(x, y);
144 if (pixel)
145 visitor(pixel);
146 }
147 }
148 }
149 }
150 if (!have_obstructions) {
151 int x_start = padded ? gridPaddedX(&cell) : gridX(&cell);
152 int x_end = padded ? gridPaddedEndX(&cell) : gridEndX(&cell);
153 int y_start = gridY(&cell);
154 int y_end = gridEndY(&cell);
155 for (int x = x_start; x < x_end; x++) {
156 for (int y = y_start; y < y_end; y++) {
157 Pixel *pixel = gridPixel(x, y);
158 if (pixel)
159 visitor(pixel);
160 }
161 }
162 }
163 }
164
165 void
setFixedGridCells()166 Opendp::setFixedGridCells()
167 {
168 for (Cell &cell : cells_) {
169 if (isFixed(&cell))
170 visitCellPixels(cell, true,
171 [&] (Pixel *pixel) { setGridCell(cell, pixel); } );
172 }
173 }
174
175 void
setGridCell(Cell & cell,Pixel * pixel)176 Opendp::setGridCell(Cell &cell,
177 Pixel *pixel)
178 {
179 pixel->cell = &cell;
180 pixel->util = 1.0;
181 }
182
183 void
groupAssignCellRegions()184 Opendp::groupAssignCellRegions()
185 {
186 for (Group &group : groups_) {
187 int64_t site_count = 0;
188 for (int x = 0; x < row_site_count_; x++) {
189 for (int y = 0; y < row_count_; y++) {
190 Pixel *pixel = gridPixel(x, y);
191 if (pixel->is_valid && pixel->group_ == &group) {
192 site_count++;
193 }
194 }
195 }
196 int64_t site_area = site_count * site_width_ * row_height_;
197
198 int64_t cell_area = 0;
199 for (Cell *cell : group.cells_) {
200 cell_area += cell->area();
201
202 for (Rect &rect : group.regions) {
203 if (isInside(cell, &rect)) {
204 cell->region_ = ▭
205 }
206 }
207 if (cell->region_ == nullptr) {
208 cell->region_ = &group.regions[0];
209 }
210 }
211 group.util = static_cast<double>(cell_area) / site_area;
212 }
213 }
214
215 void
groupInitPixels2()216 Opendp::groupInitPixels2()
217 {
218 for (int x = 0; x < row_site_count_; x++) {
219 for (int y = 0; y < row_count_; y++) {
220 Rect sub;
221 sub.init(x * site_width_,
222 y * row_height_,
223 (x + 1) * site_width_,
224 (y + 1) * row_height_);
225 Pixel *pixel = gridPixel(x, y);
226 for (Group &group : groups_) {
227 for (Rect &rect : group.regions) {
228 if (!isInside(sub, rect) && checkOverlap(sub, rect)) {
229 pixel->util = 0.0;
230 pixel->cell = &dummy_cell_;
231 pixel->is_valid = false;
232 }
233 }
234 }
235 }
236 }
237 }
238
239 /* static */
240 bool
isInside(const Rect & cell,const Rect & box)241 Opendp::isInside(const Rect &cell, const Rect &box)
242 {
243 return cell.xMin() >= box.xMin()
244 && cell.xMax() <= box.xMax()
245 && cell.yMin() >= box.yMin()
246 && cell.yMax() <= box.yMax();
247 }
248
249 bool
checkOverlap(const Rect & cell,const Rect & box)250 Opendp::checkOverlap(const Rect &cell, const Rect &box)
251 {
252 return box.xMin() < cell.xMax() && box.xMax() > cell.xMin() && box.yMin() < cell.yMax() && box.yMax() > cell.yMin();
253 }
254
255 void
groupInitPixels()256 Opendp::groupInitPixels()
257 {
258 for (int x = 0; x < row_site_count_; x++) {
259 for (int y = 0; y < row_count_; y++) {
260 Pixel *pixel = gridPixel(x, y);
261 pixel->util = 0.0;
262 }
263 }
264
265 for (Group &group : groups_) {
266 for (Rect &rect : group.regions) {
267 int row_start = divCeil(rect.yMin(), row_height_);
268 int row_end = divFloor(rect.yMax(), row_height_);
269
270 for (int k = row_start; k < row_end; k++) {
271 int col_start = divCeil(rect.xMin(), site_width_);
272 int col_end = divFloor(rect.xMax(), site_width_);
273
274 for (int l = col_start; l < col_end; l++) {
275 Pixel *pixel = gridPixel(l, k);
276 pixel->util += 1.0;
277 }
278 if (rect.xMin() % site_width_ != 0) {
279 Pixel *pixel = gridPixel(col_start, k);
280 pixel->util -= (rect.xMin() % site_width_) / static_cast<double>(site_width_);
281 }
282 if (rect.xMax() % site_width_ != 0) {
283 Pixel *pixel = gridPixel(col_end - 1, k);
284 pixel->util -= ((site_width_ - rect.xMax()) % site_width_)
285 / static_cast<double>(site_width_);
286 }
287 }
288 }
289 for (Rect &rect : group.regions) {
290 int row_start = divCeil(rect.yMin(), row_height_);
291 int row_end = divFloor(rect.yMax(), row_height_);
292
293 for (int k = row_start; k < row_end; k++) {
294 int col_start = divCeil(rect.xMin(), site_width_);
295 int col_end = divFloor(rect.xMax(), site_width_);
296
297 // Assign group to each pixel.
298 for (int l = col_start; l < col_end; l++) {
299 Pixel *pixel = gridPixel(l, k);
300 if (pixel->util == 1.0) {
301 pixel->group_ = &group;
302 pixel->is_valid = true;
303 pixel->util = 1.0;
304 }
305 else if (pixel->util > 0.0 && pixel->util < 1.0) {
306 pixel->cell = &dummy_cell_;
307 pixel->util = 0.0;
308 pixel->is_valid = false;
309 }
310 }
311 }
312 }
313 }
314 }
315
316 void
erasePixel(Cell * cell)317 Opendp::erasePixel(Cell *cell)
318 {
319 if (!(isFixed(cell) || !cell->is_placed_)) {
320 int x_end = gridPaddedEndX(cell);
321 int y_end = gridEndY(cell);
322 for (int x = gridPaddedX(cell); x < x_end; x++) {
323 for (int y = gridY(cell); y < y_end; y++) {
324 Pixel *pixel = gridPixel(x, y);
325 pixel->cell = nullptr;
326 pixel->util = 0;
327 }
328 }
329 cell->is_placed_ = false;
330 cell->hold_ = false;
331 }
332 }
333
334 void
paintPixel(Cell * cell,int grid_x,int grid_y)335 Opendp::paintPixel(Cell *cell, int grid_x, int grid_y)
336 {
337 assert(!cell->is_placed_);
338 int x_end = grid_x + gridPaddedWidth(cell);
339 int grid_height = gridHeight(cell);
340 int y_end = grid_y + grid_height;
341
342 setGridPaddedLoc(cell, grid_x, grid_y);
343 cell->is_placed_ = true;
344
345 debugPrint(logger_, DPL, "place", 1, " paint {} ({}-{}, {}-{})",
346 cell->name(), grid_x, x_end - 1, grid_y, y_end - 1);
347
348 for (int x = grid_x; x < x_end; x++) {
349 for (int y = grid_y; y < y_end; y++) {
350 Pixel *pixel = gridPixel(x, y);
351 if (pixel->cell) {
352 logger_->error(DPL, 13, "Cannot paint grid because it is already occupied.");
353 }
354 else {
355 pixel->cell = cell;
356 pixel->util = 1.0;
357 }
358 }
359 }
360 // This is most likely broken. -cherry
361 if (have_multi_row_cells_) {
362 if (grid_height % 2 == 1) {
363 if (rowTopPower(grid_y) != topPower(cell)) {
364 cell->orient_ = dbOrientType::MX;
365 }
366 else {
367 cell->orient_ = dbOrientType::R0;
368 }
369 }
370 }
371 else {
372 cell->orient_ = rowOrient(grid_y);
373 }
374 }
375
376 } // namespace opendp
377