aboutsummaryrefslogtreecommitdiffstats
path: root/common
diff options
context:
space:
mode:
Diffstat (limited to 'common')
-rw-r--r--common/placer_heap.cc47
-rw-r--r--common/placer_heap.h34
-rw-r--r--common/placer_math.c43
-rw-r--r--common/placer_math.h43
4 files changed, 166 insertions, 1 deletions
diff --git a/common/placer_heap.cc b/common/placer_heap.cc
index 19d5a8e5..9f49e552 100644
--- a/common/placer_heap.cc
+++ b/common/placer_heap.cc
@@ -25,12 +25,13 @@
*/
#include <deque>
+#include <numeric>
#include <unordered_map>
#include "log.h"
#include "nextpnr.h"
#include "place_common.h"
+#include "placer_math.h"
#include "util.h"
-
NEXTPNR_NAMESPACE_BEGIN
namespace {
@@ -76,13 +77,44 @@ template <typename T> struct EquationSystem
}
void add_rhs(int row, T val) { rhs[row] += val; }
+
+ void solve(std::vector<double> &x)
+ {
+ int nnz = std::accumulate(A.begin(), A.end(), 0,
+ [](int a, const std::vector<std::pair<int, T>> &vec) { return a + int(vec.size()); });
+ taucif_system *sys = taucif_create_system(int(rhs.size()), int(A.size()), nnz);
+ for (int col = 0; col < int(A.size()); col++) {
+ auto &Ac = A[col];
+ for (auto &el : Ac) {
+ if (col <= el.first)
+ taucif_set_matrix_value(sys, el.first, col, el.second);
+ // FIXME: in debug mode, assert really is symmetric
+ }
+ }
+ taucif_solve_system(sys, x.data(), rhs.data());
+ taucif_free_system(sys);
+ }
};
+
} // namespace
class HeAPPlacer
{
public:
HeAPPlacer(Context *ctx) : ctx(ctx) {}
+ bool place()
+ {
+ taucif_init_solver();
+ place_constraints();
+ build_fast_bels();
+ seed_placement();
+ update_all_chains();
+
+ EquationSystem<double> es(place_cells.size(), place_cells.size());
+ build_equations(es, false);
+ solve_equations(es, false);
+ return true;
+ }
private:
Context *ctx;
@@ -361,6 +393,19 @@ class HeAPPlacer
});
}
}
+
+ // Build the system of equations for either X or Y
+ void solve_equations(EquationSystem<double> &es, bool yaxis)
+ {
+ // Return the x or y position of a cell, depending on ydir
+ auto cell_pos = [&](CellInfo *cell) { return yaxis ? cell_locs.at(cell->name).y : cell_locs.at(cell->name).x; };
+ build_equations(es, yaxis);
+ std::vector<double> vals;
+ std::transform(place_cells.begin(), place_cells.end(), std::back_inserter(vals), cell_pos);
+ es.solve(vals);
+ }
};
+bool placer_heap(Context *ctx) { return HeAPPlacer(ctx).place(); }
+
NEXTPNR_NAMESPACE_END \ No newline at end of file
diff --git a/common/placer_heap.h b/common/placer_heap.h
new file mode 100644
index 00000000..5eb8a9ba
--- /dev/null
+++ b/common/placer_heap.h
@@ -0,0 +1,34 @@
+/*
+ * nextpnr -- Next Generation Place and Route
+ *
+ * Copyright (C) 2019 David Shah <david@symbioticeda.com>
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * [[cite]] HeAP
+ * Analytical Placement for Heterogeneous FPGAs, Marcel Gort and Jason H. Anderson
+ * https://janders.eecg.utoronto.ca/pdfs/marcelfpl12.pdf
+ *
+ * [[cite]] SimPL
+ * SimPL: An Effective Placement Algorithm, Myung-Chul Kim, Dong-Jin Lee and Igor L. Markov
+ * http://www.ece.umich.edu/cse/awards/pdfs/iccad10-simpl.pdf
+ */
+
+#ifndef PLACER_HEAP_H
+#define PLACER_HEAP
+#include "nextpnr.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+extern bool placer_heap(Context *ctx);
+NEXTPNR_NAMESPACE_END
+#endif \ No newline at end of file
diff --git a/common/placer_math.c b/common/placer_math.c
new file mode 100644
index 00000000..456bc0a1
--- /dev/null
+++ b/common/placer_math.c
@@ -0,0 +1,43 @@
+#include "taucs.h"
+#include "placer_math.h"
+#include <stdio.h>
+
+void taucif_init_solver() {
+ taucs_logfile("stdout");
+}
+
+struct taucif_system {
+ taucs_ccs_matrix* mat;
+ int ccs_i, ccs_col;
+};
+
+struct taucif_system *taucif_create_system(int rows, int cols, int n_nonzero) {
+ struct taucif_system *sys = taucs_malloc(sizeof(struct taucif_system));
+ sys->mat = taucs_ccs_create(cols, rows, n_nonzero, TAUCS_DOUBLE | TAUCS_SYMMETRIC);
+ // Internal pointers
+ sys->ccs_i = 0;
+ sys->ccs_col = -1;
+ return sys;
+};
+
+void taucif_set_matrix_value(struct taucif_system *sys, int row, int col, double value) {
+ while(sys->ccs_col < col) {
+ sys->mat->colptr[++sys->ccs_col] = sys->ccs_i;
+ }
+ sys->mat->rowind[sys->ccs_i] = row;
+ sys->mat->values.d[sys->ccs_i++] = value;
+}
+
+void taucif_solve_system(struct taucif_system *sys, double *x, double *rhs) {
+ // FIXME: preconditioner, droptol??
+ taucs_ccs_matrix* precond_mat = taucs_ccs_factor_llt(sys->mat, 1e-3, 0);
+ // FIXME: itermax, convergetol
+ int cjres = taucs_conjugate_gradients(sys->mat, taucs_ccs_solve_llt, precond_mat, x, rhs, 1000, 1e-6);
+ taucs_ccs_free(precond_mat);
+}
+
+void taucif_free_system(struct taucif_system *sys) {
+ taucs_ccs_free(sys->mat);
+ taucs_free(sys->mat);
+}
+
diff --git a/common/placer_math.h b/common/placer_math.h
new file mode 100644
index 00000000..3782e99f
--- /dev/null
+++ b/common/placer_math.h
@@ -0,0 +1,43 @@
+/*
+ * nextpnr -- Next Generation Place and Route
+ *
+ * Copyright (C) 2019 David Shah <david@symbioticeda.com>
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+
+ */
+
+#ifndef PLACER_MATH_H
+#define PLACER_MATH_H
+// This shim is needed because Tauc is mutually incompatible with modern C++ (implementing macros and functions
+// that collide with max, min, etc)
+#ifdef __cplusplus
+extern "C" {
+#endif
+extern void taucif_init_solver();
+
+struct taucif_system;
+
+extern struct taucif_system *taucif_create_system(int rows, int cols, int n_nonzero);
+
+extern void taucif_set_matrix_value(struct taucif_system *sys, int row, int col, double value);
+
+extern void taucif_solve_system(struct taucif_system *sys, double *x, double *rhs);
+
+extern void taucif_free_system(struct taucif_system *sys);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif \ No newline at end of file
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-25 02:35:09 +0000