Program Listing for File LegacyRefine.h

↰ Return to documentation for file (src/partition/refine/strategy/LegacyRefine.h)

#ifndef PARTITION_REFINE_STRATEGY_LEGACYREFINE_H_
#define PARTITION_REFINE_STRATEGY_LEGACYREFINE_H_

#include "refine/bucket/MoveBucket.h"
#include "refine/engine/GainEvaluator.h"
#include "refine/engine/MoveApplier.h"
#include "refine/strategy/IRefineStrategy.h"


class Refine {
 protected:
  int max_hop;
  int large_net_threshold;
  double penalty;
  vector<vector<int>> &cut_weights;
  const fpga &fpgas;
  TimingRefineConfig timing_cfg;

  GainEvaluatorContext makeGainEvalContext() const
  {
    return GainEvaluatorContext{
        max_hop, large_net_threshold, penalty, cut_weights, fpgas, timing_cfg};
  }

  MoveApplierContext makeMoveApplierContext()
  {
    return MoveApplierContext{large_net_threshold, cut_weights, fpgas,
                              timing_cfg};
  }

  Gain pickMove(PerPartBucketSet &buckets, const graph &finest,
                const vector<VectorXi> &occupied_resources);

  template <typename PickFn, typename AcceptFn, typename UpdateFn,
            typename ClearFn>
  double runFMLoop(int max_move, int max_neg_move, const graph &finest,
                   vector<int> &parts, vector<VectorXi> &occupied_resources,
                   vector<bool> &visited_vertices_flag,
                   vector<NetPartition> &partition, PickFn pickFn,
                   AcceptFn acceptFn, UpdateFn updateFn, ClearFn clearFn)
  {
    vector<Gain> moves_trace;
    double total_delta_gain = 0.0;
    double best_gain        = 0.0;
    int best_vertex_id      = -1;
    int neg_move_count      = 0;

    for (int i = 0; i < max_move; i++) {
      const Gain candidate = pickFn();
      const int vertex     = candidate.get_id();
      if (vertex < 0)
        break;

      if (candidate.get_gain() < 0) {
        if (++neg_move_count > max_neg_move)
          break;
      } else {
        neg_move_count = 0;
      }

      acceptFn(candidate, moves_trace, total_delta_gain);
      updateFn(vertex);

      if (total_delta_gain >= best_gain) {
        best_gain      = total_delta_gain;
        best_vertex_id = vertex;
      }
    }

    // 回滚最优位置之后的所有移动。
    auto ctx = makeMoveApplierContext();
    for (auto it = moves_trace.rbegin(); it != moves_trace.rend(); ++it) {
      if (it->get_id() == best_vertex_id)
        break;
      MoveStateApplierCore::cancelMove(ctx, *it, finest, visited_vertices_flag,
                                       parts, occupied_resources, partition);
    }
    moves_trace.clear();
    clearFn();
    return best_gain;
  }

 public:
  Refine(int max_hop, int large_net_threshold, double penalty,
         vector<vector<int>> &cut_weights, const fpga &fpgas,
         const TimingRefineConfig &timing_cfg)
      : max_hop(max_hop),
        large_net_threshold(large_net_threshold),
        penalty(penalty),
        cut_weights(cut_weights),
        fpgas(fpgas),
        timing_cfg(timing_cfg)
  {
  }
};

class PMRefine : public Refine, public IRefineStrategy {
 private:
  int max_move;
  int max_neg_move;

 public:
  PMRefine(int max_hop, int large_net_threshold, double penalty,
           vector<vector<int>> &cut_weights, const fpga &fpgas,
           const TimingRefineConfig &timing_cfg, int max_move, int max_neg_move)
      : Refine(max_hop, large_net_threshold, penalty, cut_weights, fpgas,
               timing_cfg),
        max_move(max_move),
        max_neg_move(max_neg_move)
  {
  }
  const char *name() const override;
  double run(RefinePassContext &context) override;
  double refinement(const graph &finest, vector<int> &parts,
                    vector<VectorXi> &occupied_resources,
                    vector<bool> &visited_vertices_flag,
                    vector<NetPartition> &partition);

 private:
  double pairFM(const graph &finest, vector<int> &parts,
                vector<VectorXi> &occupied_resources,
                vector<bool> &visited_vertices_flag,
                vector<NetPartition> &partition, PerPartBucketSet &buckets,
                const pair<int, int> &match);
};

class DSFM_M_Refine : public Refine, public IRefineStrategy {
 private:
  int max_move;
  int max_neg_move;

 public:
  DSFM_M_Refine(int max_hop, int large_net_threshold, double penalty,
                vector<vector<int>> &cut_weights, const fpga &fpgas,
                const TimingRefineConfig &timing_cfg, int max_move,
                int max_neg_move)
      : Refine(max_hop, large_net_threshold, penalty, cut_weights, fpgas,
               timing_cfg),
        max_move(max_move),
        max_neg_move(max_neg_move)
  {
  }
  const char *name() const override;
  double run(RefinePassContext &context) override;
  double refinement(const graph &finest, vector<int> &parts,
                    vector<VectorXi> &occupied_resources,
                    vector<bool> &visited_vertices_flag,
                    vector<NetPartition> &partition);
  Gain pickMove_DSFM(PerPartBucketSet &buckets, const graph &finest,
                     const vector<VectorXi> &occupied_resources,
                     vector<vector<Gain>> &violating);
  void acceptMove_DSFM(const Gain &gain_cell, PerPartBucketSet &buckets,
                       vector<Gain> &moves_trace, double &total_delta_gain,
                       vector<bool> &visited_vertices_flag, const graph &finest,
                       vector<int> &parts, vector<VectorXi> &occupied_resources,
                       vector<NetPartition> &partition,
                       vector<vector<Gain>> &violating);
};

class DSFM_S_Refine : public Refine, public IRefineStrategy {
 private:
  int max_move;
  int max_neg_move;

 public:
  DSFM_S_Refine(int max_hop, int large_net_threshold, double penalty,
                vector<vector<int>> &cut_weights, const fpga &fpgas,
                const TimingRefineConfig &timing_cfg, int max_move,
                int max_neg_move)
      : Refine(max_hop, large_net_threshold, penalty, cut_weights, fpgas,
               timing_cfg),
        max_move(max_move),
        max_neg_move(max_neg_move)
  {
  }
  const char *name() const override;
  double run(RefinePassContext &context) override;
  double refinement(const graph &finest, vector<int> &parts,
                    vector<VectorXi> &occupied_resources,
                    vector<bool> &visited_vertices_flag,
                    vector<NetPartition> &partition);
  Gain pickMove_DSFM(GlobalMoveBucket &buckets, const graph &finest,
                     const vector<VectorXi> &occupied_resources,
                     vector<Gain> &violating);
  void acceptMove_DSFM(const Gain &gain_cell, GlobalMoveBucket &buckets,
                       vector<Gain> &moves_trace, double &total_delta_gain,
                       vector<bool> &visited_vertices_flag, const graph &finest,
                       vector<int> &parts, vector<VectorXi> &occupied_resources,
                       vector<NetPartition> &partition,
                       vector<Gain> &violating);
};

class FMRefine : public Refine, public IRefineStrategy {
 private:
  int max_move;
  int max_neg_move;

 public:
  FMRefine(int max_hop, int large_net_threshold, double penalty,
           vector<vector<int>> &cut_weights, const fpga &fpgas,
           const TimingRefineConfig &timing_cfg, int max_move, int max_neg_move)
      : Refine(max_hop, large_net_threshold, penalty, cut_weights, fpgas,
               timing_cfg),
        max_move(max_move),
        max_neg_move(max_neg_move)
  {
  }
  const char *name() const override;
  double run(RefinePassContext &context) override;
  double refinement(const graph &finest, vector<int> &parts,
                    vector<VectorXi> &occupied_resources,
                    vector<bool> &visited_vertices_flag,
                    vector<NetPartition> &partition);
};

class OldRefine : public Refine, public IRefineStrategy {
 private:
  bool has_fix;
  bool enable_parallel_refine_;
  std::mt19937 gen_;

 public:
  OldRefine(int max_hop, int large_net_threshold, double penalty,
            vector<vector<int>> &cut_weights, const fpga &fpgas,
            const TimingRefineConfig &timing_cfg, bool has_fix,
            bool has_timing = false, bool enable_parallel_refine = false,
            int thread_order = 0, int current_level = 0, int multilevel_id = 0)
      : Refine(max_hop, large_net_threshold, penalty, cut_weights, fpgas,
               timing_cfg),
        has_fix(has_fix),
        enable_parallel_refine_(enable_parallel_refine)
  {
    if (has_timing) {
      const unsigned int seed_base =
          static_cast<unsigned int>(thread_order + 1) ^
          static_cast<unsigned int>(current_level + 1) * 0x9e3779b9u ^
          static_cast<unsigned int>(multilevel_id + 1) * 0x85ebca6bu;
      gen_.seed(seed_base);
    }
  }

  const char *name() const override;
  double run(RefinePassContext &context) override;

  double refinement(const graph &finest, vector<int> &parts,
                    vector<VectorXi> &occupied_resources,
                    vector<NetPartition> &partition, int seed);
  double parallelRefinement(const graph &finest, vector<int> &parts,
                            vector<VectorXi> &occupied_resources,
                            vector<NetPartition> &partition, int seed);
  void updateFullTimingByCut(const graph &finest, vector<int> &parts);
};

class GreedyRefine : public Refine, public IRefineStrategy {
 private:
  bool has_fix;
  bool checkBalanceHyper(const vector<VectorXi> &occupied_resources,
                         const graph &finest, const int &edge,
                         vector<int> &parts, int to);

 public:
  GreedyRefine(int max_hop, int large_net_threshold, double penalty,
               vector<vector<int>> &cut_weights, const fpga &fpgas,
               const TimingRefineConfig &timing_cfg, bool has_fix)
      : Refine(max_hop, large_net_threshold, penalty, cut_weights, fpgas,
               timing_cfg),
        has_fix(has_fix)
  {
  }

  const char *name() const override;
  double run(RefinePassContext &context) override;

  double refinement(const graph &finest, vector<int> &parts,
                    vector<VectorXi> &occupied_resources,
                    vector<NetPartition> &partition);
};

#endif