diff options
Diffstat (limited to 'common')
-rw-r--r-- | common/placer_heap.cc | 47 | ||||
-rw-r--r-- | common/placer_heap.h | 34 | ||||
-rw-r--r-- | common/placer_math.c | 43 | ||||
-rw-r--r-- | common/placer_math.h | 43 |
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 |