HeAP: Switching from TAUCS to Eigen

Signed-off-by: David Shah <davey1576@gmail.com>

3 files changed, 28 insertions, 123 deletions

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