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
;
46 std::ofstream dump_file
;
66 // pos = position in current direction
67 // alt_pos = position in the other direction
75 alt_pos
= xorshift32();
83 void alt_tie(double v
) {
89 std::swap(tied
, alt_tied
);
90 std::swap(pos
, alt_pos
);
93 void proj_left(double midpos
) {
95 tie(pos
> midpos
? midpos
: pos
);
98 void proj_right(double midpos
) {
100 tie(pos
< midpos
? midpos
: pos
);
105 dict
<pair
<int, int>, double> edges
;
106 dict
<Cell
*, int> cell_to_node
;
108 // worker state variables
114 QwpWorker(QwpConfig
&config
, Module
*module
, char direction
= 'x') : config(config
), module(module
), direction(direction
)
116 log_assert(direction
== 'x' || direction
== 'y');
121 log_assert(direction
== 'x');
123 SigMap
sigmap(module
);
124 dict
<SigBit
, pool
<int>> bits_to_nodes
;
126 if (config
.ltr
|| config
.alpha
)
128 dict
<Wire
*, double> alpha_inputs
, alpha_outputs
;
132 dict
<string
, Wire
*> alpha_order
;
134 for (auto wire
: module
->wires()) {
135 if (wire
->port_input
|| wire
->port_output
)
136 alpha_order
[wire
->name
.str()] = wire
;
141 for (auto &it
: alpha_order
) {
142 if (it
.second
->port_input
) {
143 int idx
= GetSize(alpha_inputs
);
144 alpha_inputs
[it
.second
] = idx
+ 0.5;
146 if (it
.second
->port_output
) {
147 int idx
= GetSize(alpha_outputs
);
148 alpha_outputs
[it
.second
] = idx
+ 0.5;
153 for (auto wire
: module
->wires())
155 if (!wire
->port_input
&& !wire
->port_output
)
158 int idx
= GetSize(nodes
);
159 nodes
.push_back(Node());
162 if (wire
->port_input
)
169 if (wire
->port_input
)
170 nodes
[idx
].alt_tie(alpha_inputs
.at(wire
) / GetSize(alpha_inputs
));
172 nodes
[idx
].alt_tie(alpha_outputs
.at(wire
) / GetSize(alpha_outputs
));
175 for (auto bit
: sigmap(wire
))
176 bits_to_nodes
[bit
].insert(idx
);
180 for (auto cell
: module
->selected_cells())
182 log_assert(cell_to_node
.count(cell
) == 0);
183 int idx
= GetSize(nodes
);
184 nodes
.push_back(Node());
186 cell_to_node
[cell
] = GetSize(nodes
);
187 nodes
[idx
].cell
= cell
;
189 for (auto &conn
: cell
->connections())
190 for (auto bit
: sigmap(conn
.second
))
191 bits_to_nodes
[bit
].insert(idx
);
194 for (auto &it
: bits_to_nodes
)
196 if (GetSize(it
.second
) > 100)
199 for (int idx1
: it
.second
)
200 for (int idx2
: it
.second
)
202 edges
[pair
<int, int>(idx1
, idx2
)] += 1.0 / GetSize(it
.second
);
206 void solve(bool alt_mode
= false)
208 // A := constraint_matrix
209 // y := constraint_rhs_vector
217 log("> System size: %d^2\n", GetSize(nodes
));
220 int N
= GetSize(nodes
), N1
= N
+1;
221 vector
<double> M(N
* N1
);
224 log("> Edge constraints: %d\n", GetSize(edges
));
227 // A[i,:] := [ 0 0 .... 0 weight 0 ... 0 -weight 0 ... 0 0], y[i] := 0
229 // i.e. nonzero columns in A[i,:] at the two node indices.
230 for (auto &edge
: edges
)
232 int idx1
= edge
.first
.first
;
233 int idx2
= edge
.first
.second
;
234 double weight
= edge
.second
* (1.0 + xorshift32() * 1e-3);
236 M
[idx1
+ idx1
*N1
] += weight
* weight
;
237 M
[idx2
+ idx2
*N1
] += weight
* weight
;
239 M
[idx1
+ idx2
*N1
] += -weight
* weight
;
240 M
[idx2
+ idx1
*N1
] += -weight
* weight
;
244 log("> Node constraints: %d\n", GetSize(nodes
));
247 // A[i,:] := [ 0 0 .... 0 weight 0 ... 0 0], y[i] := weight * pos
249 // i.e. nonzero column in A[i,:] at the node index
251 // "tied" nodes have a large weight, pinning them in position. Untied
252 // nodes have a small weight, giving then a tiny preference to stay at
253 // the current position, making sure that AA never is singular.
254 for (int idx
= 0; idx
< GetSize(nodes
); idx
++)
256 auto &node
= nodes
[idx
];
257 double rhs
= (alt_mode
? node
.alt_pos
: node
.pos
);
259 double weight
= 1e-3;
260 if (alt_mode
? node
.alt_tied
: node
.tied
)
262 weight
*= (1.0 + xorshift32() * 1e-3);
264 M
[idx
+ idx
*N1
] += weight
* weight
;
265 M
[N
+ idx
*N1
] += rhs
* weight
* weight
;
270 for (int i
= 0; i
< N
; i
++) {
271 for (int j
= 0; j
< N
+1; j
++)
272 log(" %10.2e", M
[(N
+1)*i
+ j
]);
281 // (least squares fit for "A*x = y")
283 // Using gaussian elimination to get M := [Id x]
285 vector
<int> pivot_cache
;
288 for (int i
= 0; i
< N
; i
++)
291 // gaussian elimination
292 for (int i
= 0; i
< N
; i
++)
294 if (config
.verbose
&& N
> 15 && ((i
+1) % (N
/15)) == 0)
295 log("> Solved %d%%: %d/%d\n", (100*(i
+1))/N
, i
+1, N
);
298 int best_row
= queue
.front();
299 int best_row_queue_idx
= 0;
300 double best_row_absval
= 0;
302 for (int k
= 0; k
< GetSize(queue
); k
++) {
304 double absval
= fabs(M
[i
+ row
*N1
]);
305 if (absval
> best_row_absval
) {
307 best_row_queue_idx
= k
;
308 best_row_absval
= absval
;
313 pivot_cache
.push_back(row
);
315 queue
[best_row_queue_idx
] = queue
.back();
319 for (int k
= i
+1; k
< N1
; k
++)
320 M
[k
+ row
*N1
] /= M
[i
+ row
*N1
];
324 for (int other_row
: queue
) {
325 double d
= M
[i
+ other_row
*N1
];
326 for (int k
= i
+1; k
< N1
; k
++)
327 M
[k
+ other_row
*N1
] -= d
*M
[k
+ row
*N1
];
328 M
[i
+ other_row
*N1
] = 0.0;
335 log_assert(queue
.empty());
336 log_assert(GetSize(pivot_cache
) == N
);
339 for (int i
= N
-1; i
>= 0; i
--)
340 for (int j
= i
+1; j
< N
; j
++)
342 int row
= pivot_cache
[i
];
343 int other_row
= pivot_cache
[j
];
344 M
[N
+ row
*N1
] -= M
[j
+ row
*N1
] * M
[N
+ other_row
*N1
];
350 for (int i
= 0; i
< N
; i
++) {
351 for (int j
= 0; j
< N
+1; j
++)
352 log(" %10.2e", M
[(N
+1)*i
+ j
]);
358 log("> Update nodes\n");
360 // update node positions
361 for (int i
= 0; i
< N
; i
++)
363 double v
= M
[(N
+1)*i
+ N
];
364 double c
= alt_mode
? alt_midpos
: midpos
;
365 double r
= alt_mode
? alt_radius
: radius
;
367 if (std::isfinite(v
)) {
375 if (!nodes
[i
].alt_tied
)
376 nodes
[i
].alt_pos
= v
;
384 void log_cell_coordinates(int indent
, bool log_all_nodes
= false)
386 for (auto &node
: nodes
)
388 if (node
.cell
== nullptr && !log_all_nodes
)
391 for (int i
= 0; i
< indent
; i
++)
394 if (direction
== 'x')
395 log("X=%.2f, Y=%.2f", node
.pos
, node
.alt_pos
);
397 log("X=%.2f, Y=%.2f", node
.alt_pos
, node
.pos
);
400 log(" [%c-tied]", direction
);
403 log(" [%c-tied]", direction
== 'x' ? 'y' : 'x');
405 if (node
.cell
!= nullptr)
406 log(" %s (%s)", log_id(node
.cell
), log_id(node
.cell
->type
));
414 void dump_svg(const pool
<int> *green_nodes
= nullptr, double median
= -1)
416 double x_center
= direction
== 'x' ? midpos
: alt_midpos
;
417 double y_center
= direction
== 'y' ? midpos
: alt_midpos
;
419 double x_radius
= direction
== 'x' ? radius
: alt_radius
;
420 double y_radius
= direction
== 'y' ? radius
: alt_radius
;
422 config
.dump_file
<< stringf("<svg height=\"240\" width=\"470\">\n");
423 config
.dump_file
<< stringf("<rect x=\"0\" y=\"0\" width=\"470\" height=\"240\" style=\"fill:rgb(250,250,200);\" />\n");
424 config
.dump_file
<< stringf("<rect x=\"20\" y=\"20\" width=\"200\" height=\"200\" style=\"fill:rgb(200,200,200);\" />\n");
425 config
.dump_file
<< stringf("<rect x=\"250\" y=\"20\" width=\"200\" height=\"200\" style=\"fill:rgb(200,200,200);\" />\n");
427 double win_x
= 250 + 200 * (direction
== 'x' ? midpos
- radius
: alt_midpos
- alt_radius
);
428 double win_y
= 20 + 200 * (direction
== 'y' ? midpos
- radius
: alt_midpos
- alt_radius
);
430 double win_w
= 200 * (direction
== 'x' ? 2*radius
: 2*alt_radius
);
431 double win_h
= 200 * (direction
== 'y' ? 2*radius
: 2*alt_radius
);
433 config
.dump_file
<< stringf("<rect x=\"%.2f\" y=\"%.2f\" width=\"%.2f\" height=\"%.2f\" "
434 "style=\"stroke:rgb(0,0,0);stroke-width:1;fill:none\" />\n", win_x
, win_y
, win_w
, win_h
);
438 double x1
= 20.0, x2
= 220.0, y1
= 20.0, y2
= 220.0;
440 if (direction
== 'x')
441 x1
= x2
= 120 + 100 * (median
- x_center
) / x_radius
;
443 y1
= y2
= 120 + 100 * (median
- y_center
) / y_radius
;
445 config
.dump_file
<< stringf("<line x1=\"%.2f\" y1=\"%.2f\" x2=\"%.2f\" y2=\"%.2f\" "
446 "style=\"stroke:rgb(150,0,150);stroke-width:1\" />\n", x1
, y1
, x2
, y2
);
449 for (auto &edge
: edges
)
451 auto &node1
= nodes
[edge
.first
.first
];
452 auto &node2
= nodes
[edge
.first
.second
];
454 double x1
= direction
== 'x' ? node1
.pos
: node1
.alt_pos
;
455 double y1
= direction
== 'y' ? node1
.pos
: node1
.alt_pos
;
457 double x2
= direction
== 'x' ? node2
.pos
: node2
.alt_pos
;
458 double y2
= direction
== 'y' ? node2
.pos
: node2
.alt_pos
;
460 x1
= 120 + 100 * (x1
- x_center
) / x_radius
;
461 y1
= 120 + 100 * (y1
- y_center
) / y_radius
;
463 x2
= 120 + 100 * (x2
- x_center
) / x_radius
;
464 y2
= 120 + 100 * (y2
- y_center
) / y_radius
;
466 config
.dump_file
<< stringf("<line x1=\"%.2f\" y1=\"%.2f\" x2=\"%.2f\" y2=\"%.2f\" "
467 "style=\"stroke:rgb(0,0,0);stroke-width:1\" />\n", x1
, y1
, x2
, y2
);
470 for (int i
= 0; i
< GetSize(nodes
); i
++)
472 auto &node
= nodes
[i
];
474 double x
= direction
== 'x' ? node
.pos
: node
.alt_pos
;
475 double y
= direction
== 'y' ? node
.pos
: node
.alt_pos
;
477 x
= 120 + 100 * (x
- x_center
) / x_radius
;
478 y
= 120 + 100 * (y
- y_center
) / y_radius
;
480 const char *color
= node
.cell
== nullptr ? "blue" : "red";
482 if (green_nodes
!= nullptr && green_nodes
->count(i
))
485 config
.dump_file
<< stringf("<circle cx=\"%.2f\" cy=\"%.2f\" r=\"3\" fill=\"%s\"/>\n", x
, y
, color
);
488 config
.dump_file
<< stringf("</svg>\n");
491 void run_worker(int indent
)
495 for (auto &node
: nodes
)
496 if (node
.cell
!= nullptr)
499 for (int i
= 0; i
< indent
; i
++)
504 if (direction
== 'x')
505 range_str
= stringf("X=%.2f:%.2f, Y=%.2f:%.2f",
506 midpos
- radius
, midpos
+ radius
,
507 alt_midpos
- alt_radius
, alt_midpos
+ alt_radius
);
509 range_str
= stringf("X=%.2f:%.2f, Y=%.2f:%.2f",
510 alt_midpos
- alt_radius
, alt_midpos
+ alt_radius
,
511 midpos
- radius
, midpos
+ radius
);
513 log("%c-qwp on %s with %d cells, %d nodes, and %d edges.\n", direction
,
514 range_str
.c_str(), count_cells
, GetSize(nodes
), GetSize(edges
));
519 // detect median position and check for break condition
521 vector
<pair
<double, int>> sorted_pos
;
522 for (int i
= 0; i
< GetSize(nodes
); i
++)
523 if (nodes
[i
].cell
!= nullptr)
524 sorted_pos
.push_back(pair
<double, int>(nodes
[i
].pos
, i
));
526 std::sort(sorted_pos
.begin(), sorted_pos
.end());
527 int median_sidx
= GetSize(sorted_pos
)/2;
528 double median
= sorted_pos
[median_sidx
].first
;
530 double left_scale
= radius
/ (median
- (midpos
- radius
));
531 double right_scale
= radius
/ ((midpos
+ radius
) - median
);
533 if (config
.dump_file
.is_open())
535 config
.dump_file
<< stringf("<h4>LSQ %c-Solution for %s:</h4>\n", direction
, range_str
.c_str());
537 pool
<int> green_nodes
;
538 for (int i
= 0; i
< median_sidx
; i
++)
539 green_nodes
.insert(sorted_pos
[i
].second
);
541 dump_svg(&green_nodes
, median
);
544 for (auto &node
: nodes
)
546 double rel_pos
= node
.pos
- median
;
548 node
.pos
= midpos
+ left_scale
*rel_pos
;
549 if (std::isfinite(node
.pos
)) {
550 node
.pos
= min(node
.pos
, midpos
);
551 node
.pos
= max(node
.pos
, midpos
- radius
);
553 node
.pos
= midpos
- radius
/2;
555 node
.pos
= midpos
+ right_scale
*rel_pos
;
556 if (std::isfinite(node
.pos
)) {
557 node
.pos
= max(node
.pos
, midpos
);
558 node
.pos
= min(node
.pos
, midpos
+ radius
);
560 node
.pos
= midpos
+ radius
/2;
564 if (GetSize(sorted_pos
) < 2 || (2*radius
<= config
.grid
&& 2*alt_radius
<= config
.grid
)) {
565 log_cell_coordinates(indent
+ 1);
569 // create child workers
571 char child_direction
= direction
== 'x' ? 'y' : 'x';
573 QwpWorker
left_worker(config
, module
, child_direction
);
574 QwpWorker
right_worker(config
, module
, child_direction
);
576 // duplicate nodes into child workers
578 dict
<int, int> left_nodes
, right_nodes
;
580 for (int k
= 0; k
< GetSize(sorted_pos
); k
++)
582 int i
= sorted_pos
[k
].second
;
584 if (k
< median_sidx
) {
585 left_nodes
[i
] = GetSize(left_worker
.nodes
);
586 left_worker
.nodes
.push_back(nodes
[i
]);
587 if (left_worker
.nodes
.back().pos
> midpos
)
588 left_worker
.nodes
.back().pos
= midpos
;
589 left_worker
.nodes
.back().swap_alt();
591 right_nodes
[i
] = GetSize(right_worker
.nodes
);
592 right_worker
.nodes
.push_back(nodes
[i
]);
593 if (right_worker
.nodes
.back().pos
< midpos
)
594 right_worker
.nodes
.back().pos
= midpos
;
595 right_worker
.nodes
.back().swap_alt();
599 // duplicate edges into child workers, project nodes as needed
601 for (auto &edge
: edges
)
603 int idx1
= edge
.first
.first
;
604 int idx2
= edge
.first
.second
;
605 double weight
= edge
.second
;
607 if (nodes
[idx1
].cell
== nullptr && nodes
[idx2
].cell
== nullptr)
610 int left_idx1
= left_nodes
.count(idx1
) ? left_nodes
.at(idx1
) : -1;
611 int left_idx2
= left_nodes
.count(idx2
) ? left_nodes
.at(idx2
) : -1;
613 int right_idx1
= right_nodes
.count(idx1
) ? right_nodes
.at(idx1
) : -1;
614 int right_idx2
= right_nodes
.count(idx2
) ? right_nodes
.at(idx2
) : -1;
616 if (left_idx1
>= 0 && left_worker
.nodes
[left_idx1
].cell
&& left_idx2
< 0) {
617 left_idx2
= left_nodes
[idx2
] = GetSize(left_worker
.nodes
);
618 left_worker
.nodes
.push_back(nodes
[idx2
]);
619 left_worker
.nodes
.back().proj_left(midpos
);
620 left_worker
.nodes
.back().swap_alt();
622 if (left_idx2
>= 0 && left_worker
.nodes
[left_idx2
].cell
&& left_idx1
< 0) {
623 left_idx1
= left_nodes
[idx1
] = GetSize(left_worker
.nodes
);
624 left_worker
.nodes
.push_back(nodes
[idx1
]);
625 left_worker
.nodes
.back().proj_left(midpos
);
626 left_worker
.nodes
.back().swap_alt();
629 if (right_idx1
>= 0 && right_worker
.nodes
[right_idx1
].cell
&& right_idx2
< 0) {
630 right_idx2
= right_nodes
[idx2
] = GetSize(right_worker
.nodes
);
631 right_worker
.nodes
.push_back(nodes
[idx2
]);
632 right_worker
.nodes
.back().proj_right(midpos
);
633 right_worker
.nodes
.back().swap_alt();
635 if (right_idx2
>= 0 && right_worker
.nodes
[right_idx2
].cell
&& right_idx1
< 0) {
636 right_idx1
= right_nodes
[idx1
] = GetSize(right_worker
.nodes
);
637 right_worker
.nodes
.push_back(nodes
[idx1
]);
638 right_worker
.nodes
.back().proj_right(midpos
);
639 right_worker
.nodes
.back().swap_alt();
642 if (left_idx1
>= 0 && left_idx2
>= 0)
643 left_worker
.edges
[pair
<int, int>(left_idx1
, left_idx2
)] += weight
;
645 if (right_idx1
>= 0 && right_idx2
>= 0)
646 right_worker
.edges
[pair
<int, int>(right_idx1
, right_idx2
)] += weight
;
651 left_worker
.midpos
= right_worker
.midpos
= alt_midpos
;
652 left_worker
.radius
= right_worker
.radius
= alt_radius
;
654 left_worker
.alt_midpos
= midpos
- radius
/2;
655 right_worker
.alt_midpos
= midpos
+ radius
/2;
656 left_worker
.alt_radius
= right_worker
.alt_radius
= radius
/2;
658 left_worker
.run_worker(indent
+1);
659 right_worker
.run_worker(indent
+1);
661 // re-integrate results
663 for (auto &it
: left_nodes
)
664 if (left_worker
.nodes
[it
.second
].cell
!= nullptr) {
665 nodes
[it
.first
].pos
= left_worker
.nodes
[it
.second
].alt_pos
;
666 nodes
[it
.first
].alt_pos
= left_worker
.nodes
[it
.second
].pos
;
669 for (auto &it
: right_nodes
)
670 if (right_worker
.nodes
[it
.second
].cell
!= nullptr) {
671 nodes
[it
.first
].pos
= right_worker
.nodes
[it
.second
].alt_pos
;
672 nodes
[it
.first
].alt_pos
= right_worker
.nodes
[it
.second
].pos
;
675 if (config
.dump_file
.is_open()) {
676 config
.dump_file
<< stringf("<h4>Final %c-Solution for %s:</h4>\n", direction
, range_str
.c_str());
681 void histogram(const vector
<double> &values
)
683 if (values
.empty()) {
688 double min_value
= values
.front();
689 double max_value
= values
.front();
691 for (auto &v
: values
) {
692 min_value
= min(min_value
, v
);
693 max_value
= max(max_value
, v
);
696 if (fabs(max_value
- min_value
) < 0.001) {
697 log("all values in range %f .. %f\n", min_value
, max_value
);
701 vector
<int> buckets(60);
702 int max_bucket_val
= 0;
704 for (auto &v
: values
) {
705 int idx
= min(int(GetSize(buckets
) * (v
- min_value
) / (max_value
- min_value
)), GetSize(buckets
)-1);
706 max_bucket_val
= max(max_bucket_val
, ++buckets
.at(idx
));
709 for (int i
= 4; i
>= 0; i
--) {
710 for (int k
= 0; k
< GetSize(buckets
); k
++) {
711 int v
= 10 * buckets
[k
] / max_bucket_val
;
713 log(v
== 2*i
+1 ? "." : ":");
715 log(i
== 0 ? (buckets
[k
] > 0 ? "," : "_") : " ");
719 log("%-30f%30f\n", min_value
, max_value
);
725 log("Running qwp on module %s..\n", log_id(module
));
727 if (config
.dump_file
.is_open())
728 config
.dump_file
<< stringf("<h3>QWP protocol for module %s:</h3>\n", log_id(module
));
738 for (auto &node
: nodes
)
739 if (node
.cell
!= nullptr)
740 node
.cell
->attributes
[ID::qwp_position
] = stringf("%f %f", node
.pos
, node
.alt_pos
);
742 vector
<double> edge_lengths
;
743 vector
<double> weighted_edge_lengths
;
745 double total_edge_length
= 0;
746 double total_weighted_edge_length
= 0;
748 for (auto &edge
: edges
)
750 auto &node1
= nodes
[edge
.first
.first
];
751 auto &node2
= nodes
[edge
.first
.second
];
753 double distance
= sqrt(pow(node1
.pos
- node2
.pos
, 2) + pow(node1
.alt_pos
- node2
.alt_pos
, 2));
754 double weighted_distance
= distance
* edge
.second
;
756 edge_lengths
.push_back(distance
);
757 weighted_edge_lengths
.push_back(weighted_distance
);
759 total_edge_length
+= distance
;
760 total_weighted_edge_length
+= weighted_distance
;
764 log("Summary for module %s:\n", log_id(module
));
765 log("Number of edges: %d\n", GetSize(edges
));
766 log("Total edge length: %f\n", total_edge_length
);
767 log("Total weighted edge length: %f\n", total_weighted_edge_length
);
770 log("Histogram over edge lengths:\n");
771 histogram(edge_lengths
);
774 log("Histogram over weighted edge lengths:\n");
775 histogram(weighted_edge_lengths
);
779 struct QwpPass
: public Pass
{
780 QwpPass() : Pass("qwp", "quadratic wirelength placer") { }
781 void help() YS_OVERRIDE
783 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
785 log(" qwp [options] [selection]\n");
787 log("This command runs quadratic wirelength placement on the selected modules and\n");
788 log("annotates the cells in the design with 'qwp_position' attributes.\n");
791 log(" Add left-to-right constraints: constrain all inputs on the left border\n");
792 log(" outputs to the right border.\n");
795 log(" Add constraints for inputs/outputs to be placed in alphanumerical\n");
796 log(" order along the y-axis (top-to-bottom).\n");
799 log(" Number of grid divisions in x- and y-direction. (default=16)\n");
801 log(" -dump <html_file_name>\n");
802 log(" Dump a protocol of the placement algorithm to the html file.\n");
805 log(" Verbose solver output for profiling or debugging\n");
807 log("Note: This implementation of a quadratic wirelength placer uses exact\n");
808 log("dense matrix operations. It is only a toy-placer for small circuits.\n");
811 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
814 xorshift32_state
= 123456789;
816 log_header(design
, "Executing QWP pass (quadratic wirelength placer).\n");
819 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
820 if (args
[argidx
] == "-ltr") {
824 if (args
[argidx
] == "-alpha") {
828 if (args
[argidx
] == "-v") {
829 config
.verbose
= true;
832 if (args
[argidx
] == "-grid" && argidx
+1 < args
.size()) {
833 config
.grid
= 1.0 / atoi(args
[++argidx
].c_str());
836 if (args
[argidx
] == "-dump" && argidx
+1 < args
.size()) {
837 config
.dump_file
.open(args
[++argidx
], std::ofstream::trunc
);
838 yosys_output_files
.insert(args
[argidx
]);
843 extra_args(args
, argidx
, design
);
845 for (auto module
: design
->selected_modules())
847 QwpWorker
worker(config
, module
);
852 log("plt.figure(figsize=(10, 10));\n");
854 for (auto &edge
: worker
.edges
) {
855 log("plt.plot([%.2f, %.2f], [%.2f, %.2f], \"r-\");\n",
856 worker
.nodes
[edge
.first
.first
].pos
,
857 worker
.nodes
[edge
.first
.second
].pos
,
858 worker
.nodes
[edge
.first
.first
].alt_pos
,
859 worker
.nodes
[edge
.first
.second
].alt_pos
);
862 for (auto &node
: worker
.nodes
) {
863 const char *style
= node
.cell
!= nullptr ? "ko" : "ks";
864 log("plt.plot([%.2f], [%.2f], \"%s\");\n", node
.pos
, node
.alt_pos
, style
);
871 PRIVATE_NAMESPACE_END