{
bool ltr;
bool alpha;
+ bool verbose;
double grid;
std::ofstream dump_file;
QwpConfig() {
ltr = false;
alpha = false;
+ verbose = false;
grid = 1.0 / 16;
}
};
}
}
- void solve()
+ void solve(bool alt_mode = false)
{
- int observation_matrix_m = GetSize(edges) + GetSize(nodes);
- int observation_matrix_n = GetSize(nodes);
+ // A := constraint_matrix
+ // y := constraint_rhs_vector
+ //
+ // AA = A' * A
+ // Ay = A' * y
+ //
+ // M := [AA Ay]
+
+ if (config.verbose)
+ log("> System size: %d^2\n", GetSize(nodes));
+
+ // Row major order
+ int N = GetSize(nodes), N1 = N+1;
+ vector<double> M(N * N1);
- // Column-major order
- vector<double> observation_matrix(observation_matrix_m * observation_matrix_n);
- vector<double> observation_rhs_vector(observation_matrix_m);
+ if (config.verbose)
+ log("> Edge constraints: %d\n", GetSize(edges));
- int i = 0;
- for (auto &edge : edges) {
+ // Edge constraints:
+ // A[i,:] := [ 0 0 .... 0 weight 0 ... 0 -weight 0 ... 0 0], y[i] := 0
+ //
+ // i.e. nonzero columns in A[i,:] at the two node indices.
+ for (auto &edge : edges)
+ {
int idx1 = edge.first.first;
int idx2 = edge.first.second;
double weight = edge.second * (1.0 + xorshift32() * 1e-3);
- observation_matrix[i + observation_matrix_m*idx1] = weight;
- observation_matrix[i + observation_matrix_m*idx2] = -weight;
- i++;
- }
- int j = 0;
- for (auto &node : nodes) {
- double weight = 1e-6;
- if (node.tied) weight = 1e3;
- weight *= (1.0 + xorshift32() * 1e-3);
- observation_matrix[i + observation_matrix_m*j] = weight;
- observation_rhs_vector[i] = node.pos * weight;
- i++, j++;
- }
+ M[idx1 + idx1*N1] += weight * weight;
+ M[idx2 + idx2*N1] += weight * weight;
-#ifdef LOG_MATRICES
- log("----\n");
- for (int i = 0; i < observation_matrix_m; i++) {
- for (int j = 0; j < observation_matrix_n; j++)
- log(" %10.2e", observation_matrix[i + observation_matrix_m*j]);
- log(" |%9.2e\n", observation_rhs_vector[i]);
+ M[idx1 + idx2*N1] += -weight * weight;
+ M[idx2 + idx1*N1] += -weight * weight;
}
-#endif
- // A := observation_matrix
- // y := observation_rhs_vector
+ if (config.verbose)
+ log("> Node constraints: %d\n", GetSize(nodes));
+
+ // Node constraints:
+ // A[i,:] := [ 0 0 .... 0 weight 0 ... 0 0], y[i] := weight * pos
//
- // AA = A' * A
- // Ay = A' * y
+ // i.e. nonzero column in A[i,:] at the node index
//
- // M := [AA Ay]
-
- // Row major order
- vector<double> M(observation_matrix_n * (observation_matrix_n+1));
- int N = observation_matrix_n;
+ // "tied" nodes have a large weight, pinning them in position. Untied
+ // nodes have a small weight, giving then a tiny preference to stay at
+ // the current position, making sure that AA never is singular.
+ for (int idx = 0; idx < GetSize(nodes); idx++)
+ {
+ auto &node = nodes[idx];
+ double rhs = (alt_mode ? node.alt_pos : node.pos);
- for (int i = 0; i < N; i++)
- for (int j = 0; j < N; j++) {
- double sum = 0;
- for (int k = 0; k < observation_matrix_m; k++)
- sum += observation_matrix[k + observation_matrix_m*i] * observation_matrix[k + observation_matrix_m*j];
- M[(N+1)*i + j] = sum;
- }
+ double weight = 1e-3;
+ if (alt_mode ? node.alt_tied : node.tied)
+ weight = 1e3;
+ weight *= (1.0 + xorshift32() * 1e-3);
- for (int i = 0; i < N; i++) {
- double sum = 0;
- for (int k = 0; k < observation_matrix_m; k++)
- sum += observation_matrix[k + observation_matrix_m*i] * observation_rhs_vector[k];
- M[(N+1)*i + N] = sum;
+ M[idx + idx*N1] += weight * weight;
+ M[N + idx*N1] += rhs * weight * weight;
}
#ifdef LOG_MATRICES
}
#endif
+ if (config.verbose)
+ log("> Solving\n");
+
// Solve "AA*x = Ay"
// (least squares fit for "A*x = y")
//
- // Using gaussian elimination (no pivoting) to get M := [Id x]
+ // Using gaussian elimination to get M := [Id x]
- // eliminate to upper triangular matrix
+ vector<int> pivot_cache;
+ vector<int> queue;
+
+ for (int i = 0; i < N; i++)
+ queue.push_back(i);
+
+ // gaussian elimination
for (int i = 0; i < N; i++)
{
+ if (config.verbose && N > 15 && ((i+1) % (N/15)) == 0)
+ log("> Solved %d%%: %d/%d\n", (100*(i+1))/N, i+1, N);
+
+ // find best row
+ int best_row = queue.front();
+ int best_row_queue_idx = 0;
+ double best_row_absval = 0;
+
+ for (int k = 0; k < GetSize(queue); k++) {
+ int row = queue[k];
+ double absval = fabs(M[i + row*N1]);
+ if (absval > best_row_absval) {
+ best_row = row;
+ best_row_queue_idx = k;
+ best_row_absval = absval;
+ }
+ }
+
+ int row = best_row;
+ pivot_cache.push_back(row);
+
+ queue[best_row_queue_idx] = queue.back();
+ queue.pop_back();
+
// normalize row
- for (int j = i+1; j < N+1; j++)
- M[(N+1)*i + j] /= M[(N+1)*i + i];
- M[(N+1)*i + i] = 1.0;
+ for (int k = i+1; k < N1; k++)
+ M[k + row*N1] /= M[i + row*N1];
+ M[i + row*N1] = 1.0;
// elimination
- for (int j = i+1; j < N; j++) {
- double d = M[(N+1)*j + i];
- for (int k = 0; k < N+1; k++)
- if (k > i)
- M[(N+1)*j + k] -= d*M[(N+1)*i + k];
- else
- M[(N+1)*j + k] = 0.0;
+ for (int other_row : queue) {
+ double d = M[i + other_row*N1];
+ for (int k = i+1; k < N1; k++)
+ M[k + other_row*N1] -= d*M[k + row*N1];
+ M[i + other_row*N1] = 0.0;
}
}
+ if (config.verbose)
+ log("> Solved\n");
+
+ log_assert(queue.empty());
+ log_assert(GetSize(pivot_cache) == N);
+
// back substitution
for (int i = N-1; i >= 0; i--)
for (int j = i+1; j < N; j++)
{
- M[(N+1)*i + N] -= M[(N+1)*i + j] * M[(N+1)*j + N];
- M[(N+1)*i + j] = 0.0;
+ int row = pivot_cache[i];
+ int other_row = pivot_cache[j];
+ M[N + row*N1] -= M[j + row*N1] * M[N + other_row*N1];
+ M[j + row*N1] = 0.0;
}
#ifdef LOG_MATRICES
}
#endif
+ if (config.verbose)
+ log("> Update nodes\n");
+
// update node positions
for (int i = 0; i < N; i++)
- if (!nodes[i].tied)
- nodes[i].pos = M[(N+1)*i + N];
+ {
+ double v = M[(N+1)*i + N];
+ double c = alt_mode ? alt_midpos : midpos;
+ double r = alt_mode ? alt_radius : radius;
+
+ if (std::isfinite(v)) {
+ v = min(v, c+r);
+ v = max(v, c-r);
+ } else {
+ v = c;
+ }
+
+ if (alt_mode) {
+ if (!nodes[i].alt_tied)
+ nodes[i].alt_pos = v;
+ } else {
+ if (!nodes[i].tied)
+ nodes[i].pos = v;
+ }
+ }
}
void log_cell_coordinates(int indent, bool log_all_nodes = false)
}
}
- void dump_svg(const pool<int> *green_nodes = nullptr)
+ void dump_svg(const pool<int> *green_nodes = nullptr, double median = -1)
{
- config.dump_file << stringf("<svg height=\"200\" width=\"200\">\n");
- config.dump_file << stringf("<rect width=\"200\" height=\"200\" style=\"fill:rgb(200,200,200);\" />\n");
-
double x_center = direction == 'x' ? midpos : alt_midpos;
double y_center = direction == 'y' ? midpos : alt_midpos;
double x_radius = direction == 'x' ? radius : alt_radius;
double y_radius = direction == 'y' ? radius : alt_radius;
+ config.dump_file << stringf("<svg height=\"240\" width=\"470\">\n");
+ config.dump_file << stringf("<rect x=\"0\" y=\"0\" width=\"470\" height=\"240\" style=\"fill:rgb(250,250,200);\" />\n");
+ config.dump_file << stringf("<rect x=\"20\" y=\"20\" width=\"200\" height=\"200\" style=\"fill:rgb(200,200,200);\" />\n");
+ config.dump_file << stringf("<rect x=\"250\" y=\"20\" width=\"200\" height=\"200\" style=\"fill:rgb(200,200,200);\" />\n");
+
+ double win_x = 250 + 200 * (direction == 'x' ? midpos - radius : alt_midpos - alt_radius);
+ double win_y = 20 + 200 * (direction == 'y' ? midpos - radius : alt_midpos - alt_radius);
+
+ double win_w = 200 * (direction == 'x' ? 2*radius : 2*alt_radius);
+ double win_h = 200 * (direction == 'y' ? 2*radius : 2*alt_radius);
+
+ config.dump_file << stringf("<rect x=\"%.2f\" y=\"%.2f\" width=\"%.2f\" height=\"%.2f\" "
+ "style=\"stroke:rgb(0,0,0);stroke-width:1;fill:none\" />\n", win_x, win_y, win_w, win_h);
+
+ if (median >= 0)
+ {
+ double x1 = 20.0, x2 = 220.0, y1 = 20.0, y2 = 220.0;
+
+ if (direction == 'x')
+ x1 = x2 = 120 + 100 * (median - x_center) / x_radius;
+ else
+ y1 = y2 = 120 + 100 * (median - y_center) / y_radius;
+
+ config.dump_file << stringf("<line x1=\"%.2f\" y1=\"%.2f\" x2=\"%.2f\" y2=\"%.2f\" "
+ "style=\"stroke:rgb(150,0,150);stroke-width:1\" />\n", x1, y1, x2, y2);
+ }
+
for (auto &edge : edges)
{
auto &node1 = nodes[edge.first.first];
double x2 = direction == 'x' ? node2.pos : node2.alt_pos;
double y2 = direction == 'y' ? node2.pos : node2.alt_pos;
- x1 = 100 + 100 * (x1 - x_center) / x_radius;
- y1 = 100 + 100 * (y1 - y_center) / y_radius;
+ x1 = 120 + 100 * (x1 - x_center) / x_radius;
+ y1 = 120 + 100 * (y1 - y_center) / y_radius;
- x2 = 100 + 100 * (x2 - x_center) / x_radius;
- y2 = 100 + 100 * (y2 - y_center) / y_radius;
+ x2 = 120 + 100 * (x2 - x_center) / x_radius;
+ y2 = 120 + 100 * (y2 - y_center) / y_radius;
config.dump_file << stringf("<line x1=\"%.2f\" y1=\"%.2f\" x2=\"%.2f\" y2=\"%.2f\" "
"style=\"stroke:rgb(0,0,0);stroke-width:1\" />\n", x1, y1, x2, y2);
double x = direction == 'x' ? node.pos : node.alt_pos;
double y = direction == 'y' ? node.pos : node.alt_pos;
- x = 100 + 100 * (x - x_center) / x_radius;
- y = 100 + 100 * (y - y_center) / y_radius;
+ x = 120 + 100 * (x - x_center) / x_radius;
+ y = 120 + 100 * (y - y_center) / y_radius;
const char *color = node.cell == nullptr ? "blue" : "red";
range_str.c_str(), count_cells, GetSize(nodes), GetSize(edges));
solve();
-
- for (auto &node : nodes) {
- log_assert(node.pos + 0.1 >= midpos - radius);
- log_assert(node.pos - 0.1 <= midpos + radius);
- log_assert(node.alt_pos + 0.1 >= alt_midpos - alt_radius);
- log_assert(node.alt_pos - 0.1 <= alt_midpos + alt_radius);
- }
+ solve(true);
// detect median position and check for break condition
sorted_pos.push_back(pair<double, int>(nodes[i].pos, i));
std::sort(sorted_pos.begin(), sorted_pos.end());
+ int median_sidx = GetSize(sorted_pos)/2;
+ double median = sorted_pos[median_sidx].first;
+
+ double left_scale = radius / (median - (midpos - radius));
+ double right_scale = radius / ((midpos + radius) - median);
if (config.dump_file.is_open())
{
config.dump_file << stringf("<h4>LSQ %c-Solution for %s:</h4>\n", direction, range_str.c_str());
pool<int> green_nodes;
- for (int i = 0; i < GetSize(sorted_pos)/2; i++)
+ for (int i = 0; i < median_sidx; i++)
green_nodes.insert(sorted_pos[i].second);
- dump_svg(&green_nodes);
+ dump_svg(&green_nodes, median);
+ }
+
+ for (auto &node : nodes)
+ {
+ double rel_pos = node.pos - median;
+ if (rel_pos < 0) {
+ node.pos = midpos + left_scale*rel_pos;
+ if (std::isfinite(node.pos)) {
+ node.pos = min(node.pos, midpos);
+ node.pos = max(node.pos, midpos - radius);
+ } else
+ node.pos = midpos - radius/2;
+ } else {
+ node.pos = midpos + right_scale*rel_pos;
+ if (std::isfinite(node.pos)) {
+ node.pos = max(node.pos, midpos);
+ node.pos = min(node.pos, midpos + radius);
+ } else
+ node.pos = midpos + radius/2;
+ }
}
if (GetSize(sorted_pos) < 2 || (2*radius <= config.grid && 2*alt_radius <= config.grid)) {
{
int i = sorted_pos[k].second;
- if (k < GetSize(sorted_pos) / 2) {
+ if (k < median_sidx) {
left_nodes[i] = GetSize(left_worker.nodes);
left_worker.nodes.push_back(nodes[i]);
if (left_worker.nodes.back().pos > midpos)
int right_idx1 = right_nodes.count(idx1) ? right_nodes.at(idx1) : -1;
int right_idx2 = right_nodes.count(idx2) ? right_nodes.at(idx2) : -1;
- if (nodes[idx1].cell && left_idx1 >= 0 && left_idx2 < 0) {
+ if (left_idx1 >= 0 && left_worker.nodes[left_idx1].cell && left_idx2 < 0) {
left_idx2 = left_nodes[idx2] = GetSize(left_worker.nodes);
left_worker.nodes.push_back(nodes[idx2]);
left_worker.nodes.back().proj_left(midpos);
left_worker.nodes.back().swap_alt();
} else
- if (nodes[idx2].cell && left_idx2 >= 0 && left_idx1 < 0) {
+ if (left_idx2 >= 0 && left_worker.nodes[left_idx2].cell && left_idx1 < 0) {
left_idx1 = left_nodes[idx1] = GetSize(left_worker.nodes);
left_worker.nodes.push_back(nodes[idx1]);
left_worker.nodes.back().proj_left(midpos);
left_worker.nodes.back().swap_alt();
}
- if (nodes[idx1].cell && right_idx1 >= 0 && right_idx2 < 0) {
+ if (right_idx1 >= 0 && right_worker.nodes[right_idx1].cell && right_idx2 < 0) {
right_idx2 = right_nodes[idx2] = GetSize(right_worker.nodes);
right_worker.nodes.push_back(nodes[idx2]);
right_worker.nodes.back().proj_right(midpos);
right_worker.nodes.back().swap_alt();
} else
- if (nodes[idx2].cell && right_idx2 >= 0 && right_idx1 < 0) {
+ if (right_idx2 >= 0 && right_worker.nodes[right_idx2].cell && right_idx1 < 0) {
right_idx1 = right_nodes[idx1] = GetSize(right_worker.nodes);
right_worker.nodes.push_back(nodes[idx1]);
right_worker.nodes.back().proj_right(midpos);
nodes[it.first].pos = right_worker.nodes[it.second].alt_pos;
nodes[it.first].alt_pos = right_worker.nodes[it.second].pos;
}
+
+ if (config.dump_file.is_open()) {
+ config.dump_file << stringf("<h4>Final %c-Solution for %s:</h4>\n", direction, range_str.c_str());
+ dump_svg();
+ }
+ }
+
+ void histogram(const vector<double> &values)
+ {
+ if (values.empty()) {
+ log("no data\n");
+ return;
+ }
+
+ double min_value = values.front();
+ double max_value = values.front();
+
+ for (auto &v : values) {
+ min_value = min(min_value, v);
+ max_value = max(max_value, v);
+ }
+
+ if (fabs(max_value - min_value) < 0.001) {
+ log("all values in range %f .. %f\n", min_value, max_value);
+ return;
+ }
+
+ vector<int> buckets(60);
+ int max_bucket_val = 0;
+
+ for (auto &v : values) {
+ int idx = min(int(GetSize(buckets) * (v - min_value) / (max_value - min_value)), GetSize(buckets)-1);
+ max_bucket_val = max(max_bucket_val, ++buckets.at(idx));
+ }
+
+ for (int i = 4; i >= 0; i--) {
+ for (int k = 0; k < GetSize(buckets); k++) {
+ int v = 10 * buckets[k] / max_bucket_val;
+ if (v >= 2*i+1)
+ log(v == 2*i+1 ? "." : ":");
+ else
+ log(i == 0 ? (buckets[k] > 0 ? "," : "_") : " ");
+ }
+ log("\n");
+ }
+ log("%-30f%30f\n", min_value, max_value);
}
void run()
{
+ log("\n");
log("Running qwp on module %s..\n", log_id(module));
if (config.dump_file.is_open())
for (auto &node : nodes)
if (node.cell != nullptr)
- node.cell->attributes["\\qwp_position"] = stringf("%f %f", node.pos, node.alt_pos);
+ node.cell->attributes[ID::qwp_position] = stringf("%f %f", node.pos, node.alt_pos);
+
+ vector<double> edge_lengths;
+ vector<double> weighted_edge_lengths;
+
+ double total_edge_length = 0;
+ double total_weighted_edge_length = 0;
+
+ for (auto &edge : edges)
+ {
+ auto &node1 = nodes[edge.first.first];
+ auto &node2 = nodes[edge.first.second];
+
+ double distance = sqrt(pow(node1.pos - node2.pos, 2) + pow(node1.alt_pos - node2.alt_pos, 2));
+ double weighted_distance = distance * edge.second;
+
+ edge_lengths.push_back(distance);
+ weighted_edge_lengths.push_back(weighted_distance);
+
+ total_edge_length += distance;
+ total_weighted_edge_length += weighted_distance;
+ }
+
+ log("\n");
+ log("Summary for module %s:\n", log_id(module));
+ log("Number of edges: %d\n", GetSize(edges));
+ log("Total edge length: %f\n", total_edge_length);
+ log("Total weighted edge length: %f\n", total_weighted_edge_length);
+
+ log("\n");
+ log("Histogram over edge lengths:\n");
+ histogram(edge_lengths);
+
+ log("\n");
+ log("Histogram over weighted edge lengths:\n");
+ histogram(weighted_edge_lengths);
}
};
struct QwpPass : public Pass {
QwpPass() : Pass("qwp", "quadratic wirelength placer") { }
- virtual void help()
+ void help() override
{
// |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
log("\n");
log(" -dump <html_file_name>\n");
log(" Dump a protocol of the placement algorithm to the html file.\n");
log("\n");
- log("Note: This implementation of a quadratic wirelength placer uses unoptimized\n");
+ log(" -v\n");
+ log(" Verbose solver output for profiling or debugging\n");
+ log("\n");
+ log("Note: This implementation of a quadratic wirelength placer uses exact\n");
log("dense matrix operations. It is only a toy-placer for small circuits.\n");
log("\n");
}
- virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
+ void execute(std::vector<std::string> args, RTLIL::Design *design) override
{
QwpConfig config;
xorshift32_state = 123456789;
- log_header("Executing QWP pass (quadratic wirelength placer).\n");
+ log_header(design, "Executing QWP pass (quadratic wirelength placer).\n");
size_t argidx;
for (argidx = 1; argidx < args.size(); argidx++) {
config.alpha = true;
continue;
}
+ if (args[argidx] == "-v") {
+ config.verbose = true;
+ continue;
+ }
if (args[argidx] == "-grid" && argidx+1 < args.size()) {
config.grid = 1.0 / atoi(args[++argidx].c_str());
continue;
}
if (args[argidx] == "-dump" && argidx+1 < args.size()) {
config.dump_file.open(args[++argidx], std::ofstream::trunc);
+ yosys_output_files.insert(args[argidx]);
continue;
}
break;
projects / yosys.git / blobdiff