From ea56dc9d084a694450d995d147b18a4de86e8b7c Mon Sep 17 00:00:00 2001 From: David Shah Date: Thu, 10 Jan 2019 16:42:29 +0000 Subject: HeAP: Add TAUCS wrapper and integration Signed-off-by: David Shah --- CMakeLists.txt | 6 ++++-- common/placer_heap.cc | 47 ++++++++++++++++++++++++++++++++++++++++++++++- common/placer_heap.h | 34 ++++++++++++++++++++++++++++++++++ common/placer_math.c | 43 +++++++++++++++++++++++++++++++++++++++++++ common/placer_math.h | 43 +++++++++++++++++++++++++++++++++++++++++++ ecp5/arch.cc | 2 +- ice40/arch.cc | 6 ++++-- 7 files changed, 175 insertions(+), 6 deletions(-) create mode 100644 common/placer_heap.h create mode 100644 common/placer_math.c create mode 100644 common/placer_math.h diff --git a/CMakeLists.txt b/CMakeLists.txt index 4f29d132..2fbfa735 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -122,6 +122,8 @@ configure_file( ${CMAKE_CURRENT_SOURCE_DIR}/common/version.h.in ${CMAKE_CURRENT_BINARY_DIR}/generated/version.h ) +add_subdirectory(3rdparty/taucs ${CMAKE_CURRENT_BINARY_DIR}/generated/taucs EXCLUDE_FROM_ALL) + if (BUILD_PYTHON) # Find Boost::Python of a suitable version in a cross-platform way # Some distributions (Arch) call it libboost_python3, others such as Ubuntu @@ -180,7 +182,7 @@ if (BUILD_PYTHON) endif () endif() -include_directories(common/ json/ ${Boost_INCLUDE_DIRS} ${PYTHON_INCLUDE_DIRS}) +include_directories(common/ json/ ${Boost_INCLUDE_DIRS} ${PYTHON_INCLUDE_DIRS} 3rdparty/taucs/src ${CMAKE_CURRENT_BINARY_DIR}/generated/taucs/build/linux) aux_source_directory(common/ COMMON_SRC_FILES) aux_source_directory(json/ JSON_PARSER_FILES) set(COMMON_FILES ${COMMON_SRC_FILES} ${JSON_PARSER_FILES}) @@ -244,7 +246,7 @@ foreach (family ${ARCH}) # Include family-specific source files to all family targets and set defines appropriately target_include_directories(${target} PRIVATE ${family}/ ${CMAKE_CURRENT_BINARY_DIR}/generated/) target_compile_definitions(${target} PRIVATE NEXTPNR_NAMESPACE=nextpnr_${family} ARCH_${ufamily} ARCHNAME=${family}) - target_link_libraries(${target} LINK_PUBLIC ${Boost_LIBRARIES} ${link_param}) + target_link_libraries(${target} LINK_PUBLIC ${Boost_LIBRARIES} taucs ${link_param}) if (NOT MSVC) target_link_libraries(${target} LINK_PUBLIC pthread) endif() 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 +#include #include #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 struct EquationSystem } void add_rhs(int row, T val) { rhs[row] += val; } + + void solve(std::vector &x) + { + int nnz = std::accumulate(A.begin(), A.end(), 0, + [](int a, const std::vector> &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 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 &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 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 + * + * 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 + +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 + * + * 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 diff --git a/ecp5/arch.cc b/ecp5/arch.cc index da0f7b1a..8ba8d28e 100644 --- a/ecp5/arch.cc +++ b/ecp5/arch.cc @@ -458,6 +458,7 @@ delay_t Arch::estimateDelay(WireId src, WireId dst) const int dx = abs(src_loc.first - dst_loc.first), dy = abs(src_loc.second - dst_loc.second); return (130 - 25 * args.speed) * (6 + std::max(dx - 5, 0) + std::max(dy - 5, 0) + 2 * (std::min(dx, 5) + std::min(dy, 5))); + } delay_t Arch::predictDelay(const NetInfo *net_info, const PortRef &sink) const @@ -467,7 +468,6 @@ delay_t Arch::predictDelay(const NetInfo *net_info, const PortRef &sink) const return 0; auto driver_loc = getBelLocation(driver.cell->bel); auto sink_loc = getBelLocation(sink.cell->bel); - // Encourage use of direct interconnect if (driver_loc.x == sink_loc.x && driver_loc.y == sink_loc.y) { if ((sink.port == id_A0 || sink.port == id_A1) && (driver.port == id_F1) && diff --git a/ice40/arch.cc b/ice40/arch.cc index fbe882fc..5688b6e6 100644 --- a/ice40/arch.cc +++ b/ice40/arch.cc @@ -26,10 +26,10 @@ #include "log.h" #include "nextpnr.h" #include "placer1.h" +#include "placer_heap.h" #include "router1.h" #include "timing_opt.h" #include "util.h" - NEXTPNR_NAMESPACE_BEGIN // ----------------------------------------------------------------------- @@ -671,7 +671,9 @@ bool Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay bool Arch::place() { - if (!placer1(getCtx(), Placer1Cfg(getCtx()))) + // if (!placer1(getCtx(), Placer1Cfg(getCtx()))) + // return false; + if (!placer_heap(getCtx())) return false; if (bool_or_default(settings, id("opt_timing"), false)) { TimingOptCfg tocfg(getCtx()); -- cgit v1.2.3