cdfc_module_binding.hpp

Go to the documentation of this file.

/*
 *
 *                   _/_/_/    _/_/   _/    _/ _/_/_/    _/_/
 *                  _/   _/ _/    _/ _/_/  _/ _/   _/ _/    _/
 *                 _/_/_/  _/_/_/_/ _/  _/_/ _/   _/ _/_/_/_/
 *                _/      _/    _/ _/    _/ _/   _/ _/    _/
 *               _/      _/    _/ _/    _/ _/_/_/  _/    _/
 *
 *             ***********************************************
 *                              PandA Project
 *                     URL: http://panda.dei.polimi.it
 *                       Politecnico di Milano - DEIB
 *                        System Architectures Group
 *             ***********************************************
 *              Copyright (C) 2004-2024 Politecnico di Milano
 *
 *   This file is part of the PandA framework.
 *
 *   The PandA framework is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */
#ifndef CDFC_MODULE_BINDING_HPP
#define CDFC_MODULE_BINDING_HPP

#include "fu_binding_creator.hpp"

#include "graph.hpp"

#include "hash_helper.hpp"

#include <string>

#include <deque>
#include <utility>
#include <vector>

#include "custom_map.hpp"
#include "custom_set.hpp"

//#define HC_APPROACH

CONSTREF_FORWARD_DECL(AllocationInformation);
enum class CliqueCovering_Algorithm;
CONSTREF_FORWARD_DECL(fu_binding);
REF_FORWARD_DECL(fu_binding);
struct spec_hierarchical_clustering;
REF_FORWARD_DECL(CdfcGraph);
CONSTREF_FORWARD_DECL(OpGraph);
class OpVertexSet;
CONSTREF_FORWARD_DECL(Parameter);

class CDFCModuleBindingSpecialization : public HLSFlowStepSpecialization
{
 public:
   const CliqueCovering_Algorithm clique_covering_algorithm;

   explicit CDFCModuleBindingSpecialization(const CliqueCovering_Algorithm clique_covering_algorithm);

   std::string GetKindText() const override;

   std::string GetSignature() const override;
};

template <typename Graph>
struct cdfc_graph_vertex_selector
{
 public:
   using vertex_descriptor = typename boost::graph_traits<Graph>::vertex_descriptor;
   using SET_container = CustomOrderedSet<vertex_descriptor>;
   cdfc_graph_vertex_selector() : all(true), support(nullptr)
   {
   }
   explicit cdfc_graph_vertex_selector(const SET_container* _support) : all(false), support(_support)
   {
   }
   bool operator()(const vertex_descriptor& v) const
   {
      if(all)
      {
         return true;
      }
      else
      {
         return support->find(v) != support->end();
      }
   }

 private:
   bool all;
   const SET_container* support;
};

template <typename Graph>
struct cdfc_graph_edge_selector
{
 private:
   int selector;

   Graph* g;

 public:
   cdfc_graph_edge_selector(const int _selector, Graph* _g) : selector(_selector), g(_g)
   {
   }

   cdfc_graph_edge_selector() : selector(0), g(nullptr)
   {
   }

   template <typename Edge>
   bool operator()(const Edge& e) const
   {
      return selector & (*g)[e].selector;
   }
};

struct edge_cdfc_selector
{
 public:
   int selector;

   int weight;

   edge_cdfc_selector() : selector(0), weight(0)
   {
   }

   explicit edge_cdfc_selector(int _selector) : selector(_selector), weight(0)
   {
   }

   edge_cdfc_selector(int _selector, int _weight) : selector(_selector), weight(_weight)
   {
   }
};

using boost_cdfc_graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS,
                                               boost::property<boost::vertex_index_t, std::size_t>, edge_cdfc_selector>;

using boost_cdfc_graphRef = refcount<boost_cdfc_graph>;
using boost_cdfc_graphConstRef = refcount<const boost_cdfc_graph>;

using cdfc_graph = boost::filtered_graph<boost_cdfc_graph, cdfc_graph_edge_selector<boost_cdfc_graph>,
                                         cdfc_graph_vertex_selector<boost_cdfc_graph>>;

using cdfc_graphRef = refcount<cdfc_graph>;
using cdfc_graphConstRef = refcount<const cdfc_graph>;
using cdfc_vertex = boost::graph_traits<cdfc_graph>::vertex_descriptor;
using cdfc_in_edge_iterator = boost::graph_traits<cdfc_graph>::in_edge_iterator;
using cdfc_out_edge_iterator = boost::graph_traits<cdfc_graph>::out_edge_iterator;
using cdfc_edge_iterator = boost::graph_traits<cdfc_graph>::edge_iterator;
using cdfc_edge = boost::graph_traits<cdfc_graph>::edge_descriptor;

struct CdfcEdgeInfo : public EdgeInfo
{
   const int edge_weight;

   explicit CdfcEdgeInfo(const int edge_weight);
};
using CdfcEdgeInfoRef = refcount<CdfcEdgeInfo>;
using CdfcEdgeInfoConstRef = refcount<const CdfcEdgeInfo>;

struct CdfcGraphInfo : public GraphInfo
{
   const CustomUnorderedMap<vertex, vertex>& c2s;

   const OpGraphConstRef operation_graph;

   CdfcGraphInfo(const CustomUnorderedMap<vertex, vertex>& c2s, const OpGraphConstRef operation_graph);
};
using CdfcGraphInfoRef = refcount<CdfcGraphInfo>;
using CdfcGraphInfoConstRef = refcount<const CdfcGraphInfo>;

class CdfcGraphsCollection : public graphs_collection
{
 public:
   CdfcGraphsCollection(const CdfcGraphInfoRef cdfc_graph_info, const ParameterConstRef parameters);

   ~CdfcGraphsCollection() override;

   inline EdgeDescriptor AddEdge(const vertex source, const vertex target, const int selector, const int weight)
   {
      THROW_ASSERT(not ExistsEdge(source, target), "Trying to add an already existing edge");
      return InternalAddEdge(source, target, selector, EdgeInfoRef(new CdfcEdgeInfo(weight)));
   }

   inline EdgeDescriptor AddEdge(const vertex source, const vertex target, const int selector)
   {
      if(ExistsEdge(source, target))
      {
         return AddSelector(source, target, selector);
      }
      else
      {
         return InternalAddEdge(source, target, selector, EdgeInfoRef(new CdfcEdgeInfo(0)));
      }
   }
};
using CdfcGraphsCollectionRef = refcount<CdfcGraphsCollection>;
using CdfcGraphsCollectionConstRef = refcount<const CdfcGraphsCollection>;

class CdfcGraph : public graph
{
 public:
   CdfcGraph(const CdfcGraphsCollectionRef cdfc_graphs_collection, const int selector);

   CdfcGraph(const CdfcGraphsCollectionRef cdfc_graphs_collection, const int selector,
             const CustomUnorderedSet<vertex>& vertices);

   ~CdfcGraph() override;

   inline const CdfcEdgeInfoConstRef CGetCdfcEdgeInfo(const EdgeDescriptor e) const
   {
      return RefcountCast<const CdfcEdgeInfo>(graph::CGetEdgeInfo(e));
   }

   void WriteDot(const std::string& file_name, const int detail_level = 0) const;
};
using CdfcGraphRef = refcount<CdfcGraph>;
using CdfcGraphConstRef = refcount<const CdfcGraph>;

enum conn_code
{
   no_def,
   no_phi_chained,
   no_phi_no_chained,
   phi
};

using connection_relation =
    CustomUnorderedMap<vertex, std::vector<CustomOrderedSet<std::pair<conn_code, std::pair<unsigned int, vertex>>>>>;

class cdfc_module_binding : public fu_binding_creator
{
 protected:
   const double small_normalized_resource_area;

   bool false_loop_search(cdfc_vertex start, unsigned k, const cdfc_graphConstRef& cdfc, const cdfc_graphConstRef& cg,
                          std::deque<cdfc_edge>& candidate_edges);
   bool false_loop_search_cdfc_1(cdfc_vertex src, unsigned int level, unsigned k, cdfc_vertex start,
                                 const cdfc_graphConstRef& cdfc, const cdfc_graphConstRef& cg,
                                 std::deque<cdfc_edge>& candidate_edges, std::vector<bool>& visited,
                                 std::vector<bool>& cg_visited, std::vector<bool>& cdfc_visited);
   bool false_loop_search_cdfc_more(cdfc_vertex src, unsigned int level, unsigned k, cdfc_vertex start,
                                    const cdfc_graphConstRef& cdfc, const cdfc_graphConstRef& cg,
                                    std::deque<cdfc_edge>& candidate_edges, std::vector<bool>& visited,
                                    std::vector<bool>& cg_visited, std::vector<bool>& cdfc_visited);
   bool can_be_clustered(vertex v, OpGraphConstRef fsdg, const fu_bindingConstRef fu,
                         const CustomUnorderedMap<vertex, double>& slack_time, const double mux_time);

   int weight_computation(bool cond1, bool cond2, vertex v1, vertex v2, const double mux_time,
                          const OpGraphConstRef fdfg, const fu_bindingConstRef fu,
                          const CustomUnorderedMap<vertex, double>& slack_time,
                          CustomUnorderedMap<vertex, double>& starting_time,
#ifdef HC_APPROACH
                          spec_hierarchical_clustering& hc,
#endif
                          connection_relation& con_rel, double controller_delay, unsigned long long prec);

   void update_slack_starting_time(const OpGraphConstRef fdfg, OpVertexSet& sorted_vertices,
                                   CustomUnorderedMap<vertex, double>& slack_time,
                                   CustomUnorderedMap<vertex, double>& starting_time, bool update_starting_time,
                                   bool only_backward, bool only_forward);

   void initialize_connection_relation(connection_relation& con_rel, const OpVertexSet& all_candidate_vertices);

   static const int CD_EDGE = 1;
   static const int COMPATIBILITY_EDGE = 2;

   CustomUnorderedMap<vertex, bool> can_be_clustered_table;
   CustomUnorderedMapUnstable<std::pair<vertex, unsigned int>, bool> is_complex;

 public:
   cdfc_module_binding(const ParameterConstRef _parameters, const HLS_managerRef HLSMgr, unsigned int funId,
                       const DesignFlowManagerConstRef design_flow_manager,
                       const HLSFlowStepSpecializationConstRef hls_flow_step_specialization);

   ~cdfc_module_binding() override;

   DesignFlowStep_Status InternalExec() override;
};

#endif