X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=passes%2Fcmds%2Fqwp.cc;h=cf0f6d0dea60225d2b772fe26bf802c382a0ef1e;hb=c7d71f436d822bbbe3cda118591ed2b33eae3a7f;hp=e76deaef431923705090bba5e93e1b6ff3e59670;hpb=6329bea8732a777e7e9d1df878e4b96c08517c69;p=yosys.git diff --git a/passes/cmds/qwp.cc b/passes/cmds/qwp.cc index e76deaef4..cf0f6d0de 100644 --- a/passes/cmds/qwp.cc +++ b/passes/cmds/qwp.cc @@ -40,6 +40,7 @@ struct QwpConfig { bool ltr; bool alpha; + bool verbose; double grid; std::ofstream dump_file; @@ -47,6 +48,7 @@ struct QwpConfig QwpConfig() { ltr = false; alpha = false; + verbose = false; grid = 1.0 / 16; } }; @@ -201,69 +203,66 @@ struct QwpWorker } } - 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 M(N * N1); - // Column-major order - vector observation_matrix(observation_matrix_m * observation_matrix_n); - vector 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 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 @@ -275,36 +274,75 @@ struct QwpWorker } #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 pivot_cache; + vector 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 @@ -316,10 +354,31 @@ struct QwpWorker } #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) @@ -352,17 +411,41 @@ struct QwpWorker } } - void dump_svg(const pool *green_nodes = nullptr) + void dump_svg(const pool *green_nodes = nullptr, double median = -1) { - config.dump_file << stringf("\n"); - config.dump_file << stringf("\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("\n"); + config.dump_file << stringf("\n"); + config.dump_file << stringf("\n"); + config.dump_file << stringf("\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("\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("\n", x1, y1, x2, y2); + } + for (auto &edge : edges) { auto &node1 = nodes[edge.first.first]; @@ -374,11 +457,11 @@ struct QwpWorker 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("\n", x1, y1, x2, y2); @@ -391,8 +474,8 @@ struct QwpWorker 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"; @@ -431,13 +514,7 @@ struct QwpWorker 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 @@ -447,16 +524,41 @@ struct QwpWorker sorted_pos.push_back(pair(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("

LSQ %c-Solution for %s:

\n", direction, range_str.c_str()); pool 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)) { @@ -479,7 +581,7 @@ struct QwpWorker { 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) @@ -511,26 +613,26 @@ struct QwpWorker 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); @@ -569,10 +671,57 @@ struct QwpWorker 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("

Final %c-Solution for %s:

\n", direction, range_str.c_str()); + dump_svg(); + } + } + + void histogram(const vector &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 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()) @@ -588,13 +737,48 @@ struct QwpWorker 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 edge_lengths; + vector 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"); @@ -617,16 +801,19 @@ struct QwpPass : public Pass { log(" -dump \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 args, RTLIL::Design *design) + void execute(std::vector 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++) { @@ -638,12 +825,17 @@ struct QwpPass : public Pass { 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;