diff options
| -rw-r--r-- | .cirrus/Dockerfile.ubuntu16.04 | 2 | ||||
| -rw-r--r-- | CMakeLists.txt | 11 | ||||
| -rw-r--r-- | common/placer_heap.cc | 49 | ||||
| -rw-r--r-- | common/placer_math.c | 57 | ||||
| -rw-r--r-- | common/placer_math.h | 45 |
5 files changed, 35 insertions, 129 deletions
diff --git a/.cirrus/Dockerfile.ubuntu16.04 b/.cirrus/Dockerfile.ubuntu16.04 index 7de6441e..0c8201b8 100644 --- a/.cirrus/Dockerfile.ubuntu16.04 +++ b/.cirrus/Dockerfile.ubuntu16.04 @@ -8,7 +8,7 @@ RUN set -e -x ;\ apt-get -y install \ build-essential autoconf cmake clang bison wget flex gperf \ libreadline-dev gawk tcl-dev libffi-dev graphviz xdot python3-dev \ - libboost-all-dev qt5-default git libftdi-dev pkg-config libopenblas-dev + libboost-all-dev qt5-default git libftdi-dev pkg-config libeigen3-dev RUN set -e -x ;\ mkdir -p /usr/local/src ;\ diff --git a/CMakeLists.txt b/CMakeLists.txt index 2fbfa735..69089c4c 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -58,7 +58,7 @@ set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} /D_DEBUG /W4 /wd4100 /wd4244 set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} /W4 /wd4100 /wd4244 /wd4125 /wd4800 /wd4456 /wd4458 /wd4305 /wd4459 /wd4121 /wd4996 /wd4127") else() set(CMAKE_CXX_FLAGS_DEBUG "-Wall -fPIC -ggdb -pipe") -set(CMAKE_CXX_FLAGS_RELEASE "-Wall -fPIC -O3 -g -pipe") +set(CMAKE_CXX_FLAGS_RELEASE "-Wall -fPIC -O3 -g -pipe -fopenmp") endif() set(CMAKE_DEFIN) @@ -122,8 +122,6 @@ 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 @@ -182,7 +180,10 @@ if (BUILD_PYTHON) endif () endif() -include_directories(common/ json/ ${Boost_INCLUDE_DIRS} ${PYTHON_INCLUDE_DIRS} 3rdparty/taucs/src ${CMAKE_CURRENT_BINARY_DIR}/generated/taucs/build/linux) +find_package (Eigen3 REQUIRED NO_MODULE) + +include_directories(common/ json/ ${Boost_INCLUDE_DIRS} ${PYTHON_INCLUDE_DIRS} ${EIGEN3_INCLUDE_DIRS}) +add_definitions(${EIGEN3_DEFINITIONS}) aux_source_directory(common/ COMMON_SRC_FILES) aux_source_directory(json/ JSON_PARSER_FILES) set(COMMON_FILES ${COMMON_SRC_FILES} ${JSON_PARSER_FILES}) @@ -246,7 +247,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} taucs ${link_param}) + target_link_libraries(${target} LINK_PUBLIC ${Boost_LIBRARIES} ${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 7a6c2a3e..b6913473 100644 --- a/common/placer_heap.cc +++ b/common/placer_heap.cc @@ -31,6 +31,8 @@ * - To make the placer timing-driven, the bound2bound weights are multiplied by (1 + 10 * crit^2) */ +#include <Eigen/Core> +#include <Eigen/IterativeLinearSolvers> #include <boost/optional.hpp> #include <chrono> #include <deque> @@ -44,7 +46,6 @@ #include "nextpnr.h" #include "place_common.h" #include "placer1.h" -#include "placer_math.h" #include "timing.h" #include "util.h" NEXTPNR_NAMESPACE_BEGIN @@ -55,6 +56,7 @@ namespace { // solves it, and the representation that requires template <typename T> struct EquationSystem { + EquationSystem(size_t rows, size_t cols) { A.resize(cols); @@ -64,7 +66,6 @@ template <typename T> struct EquationSystem // Simple sparse format, easy to convert to CCS for solver std::vector<std::vector<std::pair<int, T>>> A; // col -> (row, x[row, col]) sorted by row std::vector<T> rhs; // RHS vector - void reset() { for (auto &col : A) @@ -93,29 +94,35 @@ template <typename T> struct EquationSystem void add_rhs(int row, T val) { rhs[row] += val; } - void solve(std::vector<double> &x) + void solve(std::vector<T> &x) { + using namespace Eigen; + NPNR_ASSERT(x.size() == A.size()); - 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) { - // log_info("%d %d %f\n", el.first, col, el.second); - taucif_add_matrix_value(sys, el.first, col, el.second); - } + VectorXd vx(x.size()), vb(rhs.size()); + SparseMatrix<T> mat(A.size(), A.size()); - // FIXME: in debug mode, assert really is symmetric - } + std::vector<int> colnnz; + for (auto &Ac : A) + colnnz.push_back(int(Ac.size())); + mat.reserve(colnnz); + for (int col = 0; col < int(A.size()); col++) { + auto &Ac = A.at(col); + for (auto &el : Ac) + mat.insert(el.first, col) = el.second; } - taucif_finalise_matrix(sys); - int result = taucif_solve_system(sys, x.data(), rhs.data()); - NPNR_ASSERT(result == 0); - taucif_free_system(sys); + for (int i = 0; i < int(x.size()); i++) + vx[i] = x.at(i); + for (int i = 0; i < int(rhs.size()); i++) + vb[i] = rhs.at(i); + + ConjugateGradient<SparseMatrix<T>, Lower | Upper> solver; + solver.setTolerance(1e-5); + VectorXd xr = solver.compute(mat).solveWithGuess(vb, vx); + for (int i = 0; i < int(x.size()); i++) + x.at(i) = xr[i]; // for (int i = 0; i < int(x.size()); i++) // log_info("x[%d] = %f\n", i, x.at(i)); } @@ -126,13 +133,13 @@ template <typename T> struct EquationSystem class HeAPPlacer { public: - HeAPPlacer(Context *ctx) : ctx(ctx) {} + HeAPPlacer(Context *ctx) : ctx(ctx) { Eigen::initParallel(); } + bool place() { auto startt = std::chrono::high_resolution_clock::now(); ctx->lock(); - taucif_init_solver(); place_constraints(); build_fast_bels(); seed_placement(); diff --git a/common/placer_math.c b/common/placer_math.c deleted file mode 100644 index b36a9ec5..00000000 --- a/common/placer_math.c +++ /dev/null @@ -1,57 +0,0 @@ -#include "taucs.h" -#include "placer_math.h" -#include <stdio.h> -#include <assert.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 | TAUCS_LOWER); - // Internal pointers - sys->ccs_i = 0; - sys->ccs_col = -1; - return sys; -}; - -void taucif_add_matrix_value(struct taucif_system *sys, int row, int col, double value) { - assert(sys->ccs_col <= col); - 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_finalise_matrix(struct taucif_system *sys) { - sys->mat->colptr[++sys->ccs_col] = sys->ccs_i; -#if 0 - taucs_ccs_write_ijv(sys->mat, "matrix.ijv"); -#endif -} - -int taucif_solve_system(struct taucif_system *sys, double *x, double *rhs) { - if (sys->mat->n <= 2) - return 0; - // FIXME: preconditioner, droptol?? - taucs_ccs_matrix* precond_mat = taucs_ccs_factor_llt(sys->mat, 1e-2, 0); - if (precond_mat == NULL) - return -1; - // 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); - return 0; -} - -void taucif_free_system(struct taucif_system *sys) { - taucs_ccs_free(sys->mat); - taucs_free(sys); -} - diff --git a/common/placer_math.h b/common/placer_math.h deleted file mode 100644 index c197036c..00000000 --- a/common/placer_math.h +++ /dev/null @@ -1,45 +0,0 @@ -/* - * 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_add_matrix_value(struct taucif_system *sys, int row, int col, double value); - -extern void taucif_finalise_matrix(struct taucif_system *sys); - -extern int 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 |