e76deaef431923705090bba5e93e1b6ff3e59670
2 * yosys -- Yosys Open SYnthesis Suite
4 * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at>
6 * Permission to use, copy, modify, and/or distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20 #include "kernel/yosys.h"
21 #include "kernel/sigtools.h"
27 PRIVATE_NAMESPACE_BEGIN
29 static uint32_t xorshift32_state
;
31 static double xorshift32()
33 xorshift32_state
^= xorshift32_state
<< 13;
34 xorshift32_state
^= xorshift32_state
>> 17;
35 xorshift32_state
^= xorshift32_state
<< 5;
36 return (xorshift32_state
% 1000000) / 1e6
;
45 std::ofstream dump_file
;
64 // pos = position in current direction
65 // alt_pos = position in the other direction
73 alt_pos
= xorshift32();
81 void alt_tie(double v
) {
87 std::swap(tied
, alt_tied
);
88 std::swap(pos
, alt_pos
);
91 void proj_left(double midpos
) {
93 tie(pos
> midpos
? midpos
: pos
);
96 void proj_right(double midpos
) {
98 tie(pos
< midpos
? midpos
: pos
);
103 dict
<pair
<int, int>, double> edges
;
104 dict
<Cell
*, int> cell_to_node
;
106 // worker state variables
112 QwpWorker(QwpConfig
&config
, Module
*module
, char direction
= 'x') : config(config
), module(module
), direction(direction
)
114 log_assert(direction
== 'x' || direction
== 'y');
119 log_assert(direction
== 'x');
121 SigMap
sigmap(module
);
122 dict
<SigBit
, pool
<int>> bits_to_nodes
;
124 if (config
.ltr
|| config
.alpha
)
126 dict
<Wire
*, double> alpha_inputs
, alpha_outputs
;
130 dict
<string
, Wire
*> alpha_order
;
132 for (auto wire
: module
->wires()) {
133 if (wire
->port_input
|| wire
->port_output
)
134 alpha_order
[wire
->name
.str()] = wire
;
139 for (auto &it
: alpha_order
) {
140 if (it
.second
->port_input
) {
141 int idx
= GetSize(alpha_inputs
);
142 alpha_inputs
[it
.second
] = idx
+ 0.5;
144 if (it
.second
->port_output
) {
145 int idx
= GetSize(alpha_outputs
);
146 alpha_outputs
[it
.second
] = idx
+ 0.5;
151 for (auto wire
: module
->wires())
153 if (!wire
->port_input
&& !wire
->port_output
)
156 int idx
= GetSize(nodes
);
157 nodes
.push_back(Node());
160 if (wire
->port_input
)
167 if (wire
->port_input
)
168 nodes
[idx
].alt_tie(alpha_inputs
.at(wire
) / GetSize(alpha_inputs
));
170 nodes
[idx
].alt_tie(alpha_outputs
.at(wire
) / GetSize(alpha_outputs
));
173 for (auto bit
: sigmap(wire
))
174 bits_to_nodes
[bit
].insert(idx
);
178 for (auto cell
: module
->selected_cells())
180 log_assert(cell_to_node
.count(cell
) == 0);
181 int idx
= GetSize(nodes
);
182 nodes
.push_back(Node());
184 cell_to_node
[cell
] = GetSize(nodes
);
185 nodes
[idx
].cell
= cell
;
187 for (auto &conn
: cell
->connections())
188 for (auto bit
: sigmap(conn
.second
))
189 bits_to_nodes
[bit
].insert(idx
);
192 for (auto &it
: bits_to_nodes
)
194 if (GetSize(it
.second
) > 100)
197 for (int idx1
: it
.second
)
198 for (int idx2
: it
.second
)
200 edges
[pair
<int, int>(idx1
, idx2
)] += 1.0 / GetSize(it
.second
);
206 int observation_matrix_m
= GetSize(edges
) + GetSize(nodes
);
207 int observation_matrix_n
= GetSize(nodes
);
209 // Column-major order
210 vector
<double> observation_matrix(observation_matrix_m
* observation_matrix_n
);
211 vector
<double> observation_rhs_vector(observation_matrix_m
);
214 for (auto &edge
: edges
) {
215 int idx1
= edge
.first
.first
;
216 int idx2
= edge
.first
.second
;
217 double weight
= edge
.second
* (1.0 + xorshift32() * 1e-3);
218 observation_matrix
[i
+ observation_matrix_m
*idx1
] = weight
;
219 observation_matrix
[i
+ observation_matrix_m
*idx2
] = -weight
;
224 for (auto &node
: nodes
) {
225 double weight
= 1e-6;
226 if (node
.tied
) weight
= 1e3
;
227 weight
*= (1.0 + xorshift32() * 1e-3);
228 observation_matrix
[i
+ observation_matrix_m
*j
] = weight
;
229 observation_rhs_vector
[i
] = node
.pos
* weight
;
235 for (int i
= 0; i
< observation_matrix_m
; i
++) {
236 for (int j
= 0; j
< observation_matrix_n
; j
++)
237 log(" %10.2e", observation_matrix
[i
+ observation_matrix_m
*j
]);
238 log(" |%9.2e\n", observation_rhs_vector
[i
]);
242 // A := observation_matrix
243 // y := observation_rhs_vector
251 vector
<double> M(observation_matrix_n
* (observation_matrix_n
+1));
252 int N
= observation_matrix_n
;
254 for (int i
= 0; i
< N
; i
++)
255 for (int j
= 0; j
< N
; j
++) {
257 for (int k
= 0; k
< observation_matrix_m
; k
++)
258 sum
+= observation_matrix
[k
+ observation_matrix_m
*i
] * observation_matrix
[k
+ observation_matrix_m
*j
];
259 M
[(N
+1)*i
+ j
] = sum
;
262 for (int i
= 0; i
< N
; i
++) {
264 for (int k
= 0; k
< observation_matrix_m
; k
++)
265 sum
+= observation_matrix
[k
+ observation_matrix_m
*i
] * observation_rhs_vector
[k
];
266 M
[(N
+1)*i
+ N
] = sum
;
271 for (int i
= 0; i
< N
; i
++) {
272 for (int j
= 0; j
< N
+1; j
++)
273 log(" %10.2e", M
[(N
+1)*i
+ j
]);
279 // (least squares fit for "A*x = y")
281 // Using gaussian elimination (no pivoting) to get M := [Id x]
283 // eliminate to upper triangular matrix
284 for (int i
= 0; i
< N
; i
++)
287 for (int j
= i
+1; j
< N
+1; j
++)
288 M
[(N
+1)*i
+ j
] /= M
[(N
+1)*i
+ i
];
289 M
[(N
+1)*i
+ i
] = 1.0;
292 for (int j
= i
+1; j
< N
; j
++) {
293 double d
= M
[(N
+1)*j
+ i
];
294 for (int k
= 0; k
< N
+1; k
++)
296 M
[(N
+1)*j
+ k
] -= d
*M
[(N
+1)*i
+ k
];
298 M
[(N
+1)*j
+ k
] = 0.0;
303 for (int i
= N
-1; i
>= 0; i
--)
304 for (int j
= i
+1; j
< N
; j
++)
306 M
[(N
+1)*i
+ N
] -= M
[(N
+1)*i
+ j
] * M
[(N
+1)*j
+ N
];
307 M
[(N
+1)*i
+ j
] = 0.0;
312 for (int i
= 0; i
< N
; i
++) {
313 for (int j
= 0; j
< N
+1; j
++)
314 log(" %10.2e", M
[(N
+1)*i
+ j
]);
319 // update node positions
320 for (int i
= 0; i
< N
; i
++)
322 nodes
[i
].pos
= M
[(N
+1)*i
+ N
];
325 void log_cell_coordinates(int indent
, bool log_all_nodes
= false)
327 for (auto &node
: nodes
)
329 if (node
.cell
== nullptr && !log_all_nodes
)
332 for (int i
= 0; i
< indent
; i
++)
335 if (direction
== 'x')
336 log("X=%.2f, Y=%.2f", node
.pos
, node
.alt_pos
);
338 log("X=%.2f, Y=%.2f", node
.alt_pos
, node
.pos
);
341 log(" [%c-tied]", direction
);
344 log(" [%c-tied]", direction
== 'x' ? 'y' : 'x');
346 if (node
.cell
!= nullptr)
347 log(" %s (%s)", log_id(node
.cell
), log_id(node
.cell
->type
));
355 void dump_svg(const pool
<int> *green_nodes
= nullptr)
357 config
.dump_file
<< stringf("<svg height=\"200\" width=\"200\">\n");
358 config
.dump_file
<< stringf("<rect width=\"200\" height=\"200\" style=\"fill:rgb(200,200,200);\" />\n");
360 double x_center
= direction
== 'x' ? midpos
: alt_midpos
;
361 double y_center
= direction
== 'y' ? midpos
: alt_midpos
;
363 double x_radius
= direction
== 'x' ? radius
: alt_radius
;
364 double y_radius
= direction
== 'y' ? radius
: alt_radius
;
366 for (auto &edge
: edges
)
368 auto &node1
= nodes
[edge
.first
.first
];
369 auto &node2
= nodes
[edge
.first
.second
];
371 double x1
= direction
== 'x' ? node1
.pos
: node1
.alt_pos
;
372 double y1
= direction
== 'y' ? node1
.pos
: node1
.alt_pos
;
374 double x2
= direction
== 'x' ? node2
.pos
: node2
.alt_pos
;
375 double y2
= direction
== 'y' ? node2
.pos
: node2
.alt_pos
;
377 x1
= 100 + 100 * (x1
- x_center
) / x_radius
;
378 y1
= 100 + 100 * (y1
- y_center
) / y_radius
;
380 x2
= 100 + 100 * (x2
- x_center
) / x_radius
;
381 y2
= 100 + 100 * (y2
- y_center
) / y_radius
;
383 config
.dump_file
<< stringf("<line x1=\"%.2f\" y1=\"%.2f\" x2=\"%.2f\" y2=\"%.2f\" "
384 "style=\"stroke:rgb(0,0,0);stroke-width:1\" />\n", x1
, y1
, x2
, y2
);
387 for (int i
= 0; i
< GetSize(nodes
); i
++)
389 auto &node
= nodes
[i
];
391 double x
= direction
== 'x' ? node
.pos
: node
.alt_pos
;
392 double y
= direction
== 'y' ? node
.pos
: node
.alt_pos
;
394 x
= 100 + 100 * (x
- x_center
) / x_radius
;
395 y
= 100 + 100 * (y
- y_center
) / y_radius
;
397 const char *color
= node
.cell
== nullptr ? "blue" : "red";
399 if (green_nodes
!= nullptr && green_nodes
->count(i
))
402 config
.dump_file
<< stringf("<circle cx=\"%.2f\" cy=\"%.2f\" r=\"3\" fill=\"%s\"/>\n", x
, y
, color
);
405 config
.dump_file
<< stringf("</svg>\n");
408 void run_worker(int indent
)
412 for (auto &node
: nodes
)
413 if (node
.cell
!= nullptr)
416 for (int i
= 0; i
< indent
; i
++)
421 if (direction
== 'x')
422 range_str
= stringf("X=%.2f:%.2f, Y=%.2f:%.2f",
423 midpos
- radius
, midpos
+ radius
,
424 alt_midpos
- alt_radius
, alt_midpos
+ alt_radius
);
426 range_str
= stringf("X=%.2f:%.2f, Y=%.2f:%.2f",
427 alt_midpos
- alt_radius
, alt_midpos
+ alt_radius
,
428 midpos
- radius
, midpos
+ radius
);
430 log("%c-qwp on %s with %d cells, %d nodes, and %d edges.\n", direction
,
431 range_str
.c_str(), count_cells
, GetSize(nodes
), GetSize(edges
));
435 for (auto &node
: nodes
) {
436 log_assert(node
.pos
+ 0.1 >= midpos
- radius
);
437 log_assert(node
.pos
- 0.1 <= midpos
+ radius
);
438 log_assert(node
.alt_pos
+ 0.1 >= alt_midpos
- alt_radius
);
439 log_assert(node
.alt_pos
- 0.1 <= alt_midpos
+ alt_radius
);
442 // detect median position and check for break condition
444 vector
<pair
<double, int>> sorted_pos
;
445 for (int i
= 0; i
< GetSize(nodes
); i
++)
446 if (nodes
[i
].cell
!= nullptr)
447 sorted_pos
.push_back(pair
<double, int>(nodes
[i
].pos
, i
));
449 std::sort(sorted_pos
.begin(), sorted_pos
.end());
451 if (config
.dump_file
.is_open())
453 config
.dump_file
<< stringf("<h4>LSQ %c-Solution for %s:</h4>\n", direction
, range_str
.c_str());
455 pool
<int> green_nodes
;
456 for (int i
= 0; i
< GetSize(sorted_pos
)/2; i
++)
457 green_nodes
.insert(sorted_pos
[i
].second
);
459 dump_svg(&green_nodes
);
462 if (GetSize(sorted_pos
) < 2 || (2*radius
<= config
.grid
&& 2*alt_radius
<= config
.grid
)) {
463 log_cell_coordinates(indent
+ 1);
467 // create child workers
469 char child_direction
= direction
== 'x' ? 'y' : 'x';
471 QwpWorker
left_worker(config
, module
, child_direction
);
472 QwpWorker
right_worker(config
, module
, child_direction
);
474 // duplicate nodes into child workers
476 dict
<int, int> left_nodes
, right_nodes
;
478 for (int k
= 0; k
< GetSize(sorted_pos
); k
++)
480 int i
= sorted_pos
[k
].second
;
482 if (k
< GetSize(sorted_pos
) / 2) {
483 left_nodes
[i
] = GetSize(left_worker
.nodes
);
484 left_worker
.nodes
.push_back(nodes
[i
]);
485 if (left_worker
.nodes
.back().pos
> midpos
)
486 left_worker
.nodes
.back().pos
= midpos
;
487 left_worker
.nodes
.back().swap_alt();
489 right_nodes
[i
] = GetSize(right_worker
.nodes
);
490 right_worker
.nodes
.push_back(nodes
[i
]);
491 if (right_worker
.nodes
.back().pos
< midpos
)
492 right_worker
.nodes
.back().pos
= midpos
;
493 right_worker
.nodes
.back().swap_alt();
497 // duplicate edges into child workers, project nodes as needed
499 for (auto &edge
: edges
)
501 int idx1
= edge
.first
.first
;
502 int idx2
= edge
.first
.second
;
503 double weight
= edge
.second
;
505 if (nodes
[idx1
].cell
== nullptr && nodes
[idx2
].cell
== nullptr)
508 int left_idx1
= left_nodes
.count(idx1
) ? left_nodes
.at(idx1
) : -1;
509 int left_idx2
= left_nodes
.count(idx2
) ? left_nodes
.at(idx2
) : -1;
511 int right_idx1
= right_nodes
.count(idx1
) ? right_nodes
.at(idx1
) : -1;
512 int right_idx2
= right_nodes
.count(idx2
) ? right_nodes
.at(idx2
) : -1;
514 if (nodes
[idx1
].cell
&& left_idx1
>= 0 && left_idx2
< 0) {
515 left_idx2
= left_nodes
[idx2
] = GetSize(left_worker
.nodes
);
516 left_worker
.nodes
.push_back(nodes
[idx2
]);
517 left_worker
.nodes
.back().proj_left(midpos
);
518 left_worker
.nodes
.back().swap_alt();
520 if (nodes
[idx2
].cell
&& left_idx2
>= 0 && left_idx1
< 0) {
521 left_idx1
= left_nodes
[idx1
] = GetSize(left_worker
.nodes
);
522 left_worker
.nodes
.push_back(nodes
[idx1
]);
523 left_worker
.nodes
.back().proj_left(midpos
);
524 left_worker
.nodes
.back().swap_alt();
527 if (nodes
[idx1
].cell
&& right_idx1
>= 0 && right_idx2
< 0) {
528 right_idx2
= right_nodes
[idx2
] = GetSize(right_worker
.nodes
);
529 right_worker
.nodes
.push_back(nodes
[idx2
]);
530 right_worker
.nodes
.back().proj_right(midpos
);
531 right_worker
.nodes
.back().swap_alt();
533 if (nodes
[idx2
].cell
&& right_idx2
>= 0 && right_idx1
< 0) {
534 right_idx1
= right_nodes
[idx1
] = GetSize(right_worker
.nodes
);
535 right_worker
.nodes
.push_back(nodes
[idx1
]);
536 right_worker
.nodes
.back().proj_right(midpos
);
537 right_worker
.nodes
.back().swap_alt();
540 if (left_idx1
>= 0 && left_idx2
>= 0)
541 left_worker
.edges
[pair
<int, int>(left_idx1
, left_idx2
)] += weight
;
543 if (right_idx1
>= 0 && right_idx2
>= 0)
544 right_worker
.edges
[pair
<int, int>(right_idx1
, right_idx2
)] += weight
;
549 left_worker
.midpos
= right_worker
.midpos
= alt_midpos
;
550 left_worker
.radius
= right_worker
.radius
= alt_radius
;
552 left_worker
.alt_midpos
= midpos
- radius
/2;
553 right_worker
.alt_midpos
= midpos
+ radius
/2;
554 left_worker
.alt_radius
= right_worker
.alt_radius
= radius
/2;
556 left_worker
.run_worker(indent
+1);
557 right_worker
.run_worker(indent
+1);
559 // re-integrate results
561 for (auto &it
: left_nodes
)
562 if (left_worker
.nodes
[it
.second
].cell
!= nullptr) {
563 nodes
[it
.first
].pos
= left_worker
.nodes
[it
.second
].alt_pos
;
564 nodes
[it
.first
].alt_pos
= left_worker
.nodes
[it
.second
].pos
;
567 for (auto &it
: right_nodes
)
568 if (right_worker
.nodes
[it
.second
].cell
!= nullptr) {
569 nodes
[it
.first
].pos
= right_worker
.nodes
[it
.second
].alt_pos
;
570 nodes
[it
.first
].alt_pos
= right_worker
.nodes
[it
.second
].pos
;
576 log("Running qwp on module %s..\n", log_id(module
));
578 if (config
.dump_file
.is_open())
579 config
.dump_file
<< stringf("<h3>QWP protocol for module %s:</h3>\n", log_id(module
));
589 for (auto &node
: nodes
)
590 if (node
.cell
!= nullptr)
591 node
.cell
->attributes
["\\qwp_position"] = stringf("%f %f", node
.pos
, node
.alt_pos
);
595 struct QwpPass
: public Pass
{
596 QwpPass() : Pass("qwp", "quadratic wirelength placer") { }
599 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
601 log(" qwp [options] [selection]\n");
603 log("This command runs quadratic wirelength placement on the selected modules and\n");
604 log("annotates the cells in the design with 'qwp_position' attributes.\n");
607 log(" Add left-to-right constraints: constrain all inputs on the left border\n");
608 log(" outputs to the right border.\n");
611 log(" Add constraints for inputs/outputs to be placed in alphanumerical\n");
612 log(" order along the y-axis (top-to-bottom).\n");
615 log(" Number of grid divisions in x- and y-direction. (default=16)\n");
617 log(" -dump <html_file_name>\n");
618 log(" Dump a protocol of the placement algorithm to the html file.\n");
620 log("Note: This implementation of a quadratic wirelength placer uses unoptimized\n");
621 log("dense matrix operations. It is only a toy-placer for small circuits.\n");
624 virtual void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
)
627 xorshift32_state
= 123456789;
629 log_header("Executing QWP pass (quadratic wirelength placer).\n");
632 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
633 if (args
[argidx
] == "-ltr") {
637 if (args
[argidx
] == "-alpha") {
641 if (args
[argidx
] == "-grid" && argidx
+1 < args
.size()) {
642 config
.grid
= 1.0 / atoi(args
[++argidx
].c_str());
645 if (args
[argidx
] == "-dump" && argidx
+1 < args
.size()) {
646 config
.dump_file
.open(args
[++argidx
], std::ofstream::trunc
);
651 extra_args(args
, argidx
, design
);
653 for (auto module
: design
->selected_modules())
655 QwpWorker
worker(config
, module
);
660 log("plt.figure(figsize=(10, 10));\n");
662 for (auto &edge
: worker
.edges
) {
663 log("plt.plot([%.2f, %.2f], [%.2f, %.2f], \"r-\");\n",
664 worker
.nodes
[edge
.first
.first
].pos
,
665 worker
.nodes
[edge
.first
.second
].pos
,
666 worker
.nodes
[edge
.first
.first
].alt_pos
,
667 worker
.nodes
[edge
.first
.second
].alt_pos
);
670 for (auto &node
: worker
.nodes
) {
671 const char *style
= node
.cell
!= nullptr ? "ko" : "ks";
672 log("plt.plot([%.2f], [%.2f], \"%s\");\n", node
.pos
, node
.alt_pos
, style
);
679 PRIVATE_NAMESPACE_END