RaftLib  0.3a
C++ Stream Processing Template Library
partition.hpp
1 
20 #ifndef _PARTITION_HPP_
21 #define _PARTITION_HPP_ 1
22 #include <cmath>
23 #include <cstdio>
24 #include <cstdlib>
25 #include <cstdint>
26 #include <functional>
28 #include <scotch.h>
29 #include "graph.tcc"
30 #include "graphtools.hpp"
31 
32 class Partition
33 {
34 
35 public:
36  Partition() = delete;
37 
38  template < class Container,
39  class MappingContainer >
40  static
41  void
42  simple( Container &c,
43  MappingContainer &mapping,
44  const std::size_t cores )
45  {
46  if( simple_check( c, mapping, cores ) )
47  {
48  return;
49  }
50  auto weight_func(
51  []( PortInfo &a, PortInfo &b, void *weight_data ) -> std::int32_t
52  {
54  return( 1 );
55  }
56  );
57  run_scotch( c,
58  mapping,
59  cores,
60  weight_func,
61  nullptr );
62  return;
63  }
64 
65  template < class Container,
66  class MappingContainer >
67  static
68  void
69  utilization_weighted( Container &c,
70  MappingContainer &mapping,
71  const std::size_t cores )
72  {
73  if( simple_check( c, mapping, cores ) )
74  {
75  return;
76  }
78  auto weight_func(
79  []( PortInfo &a, PortInfo &b, void *weight_data ) -> std::int32_t
80  {
81  //TODO, add streaming mean to fifo stats
82  return( a.getFIFO()->size() );
83  }
84  );
85  run_scotch( c,
86  mapping,
87  cores,
88  weight_func,
89  nullptr );
90  return;
91  }
92 
93 
94 private:
95 
96  using weight_function_t =
97  typename std::function< std::int32_t( PortInfo&,PortInfo&,void* ) >;
98 
99  using raftgraph_t = raft::graph< std::int32_t,
100  std::int32_t >;
101 
102 
103 
104  template < class Container >
105  static
106  void get_graph_info( Container &c,
107  raftgraph_t &raft_graph,
108  weight_function_t weight_func,
109  void *weight_data )
110  {
111  using nummap_t = std::map< raft::kernel const *,
112  std::size_t >;
114  nummap_t numbering;
115  {
116  auto index( 0 );
117  for( raft::kernel const *k : c )
118  {
119  numbering.insert( std::make_pair( k, index++ ) );
120  }
121  }
122  struct LocalData
123  {
124  LocalData( raftgraph_t &g, nummap_t &m )
125  : graph( g ),
126  num_map( m )
127  {}
128 
129  raftgraph_t &graph;
130  nummap_t &num_map;
131  } d ( raft_graph, numbering );
132  auto graph_function =
133  [&]( PortInfo &a,
134  PortInfo &b,
135  void *data )
136  {
137  if( ! Schedule::isActive( a.my_kernel ) )
138  {
139  return;
140  }
141  auto *local_data(
142  reinterpret_cast< LocalData* >( data ) );
143  const auto num_src( local_data->num_map[ a.my_kernel ] );
144  const auto num_dst( local_data->num_map[ b.my_kernel ] );
145  const auto weight( weight_func( a, b, weight_data ) );
146  local_data->graph.addEdge( num_src, num_dst, weight );
147  return;
148  };
149  GraphTools::BFS( c,
150  graph_function,
151  (void*) &d,
152  false );
153 
154  }
155 
159  template < class Container,
160  class MapContainer >
161  static
162  bool simple_check( Container &c,
163  MapContainer &mapping,
164  const std::size_t cores )
165  {
166  if( c.size() <= cores )
167  {
168  const auto length( c.size() );
169  for( auto i( 0 ); i < length; i++ )
170  {
171  mapping.push_back( i );
172  }
173  return( true );
174  }
176  return( false );
177  }
178 
182  template < class Container,
183  class MapContainer >
184  static
185  void run_scotch( Container &c,
186  MapContainer &mapping,
187  const std::size_t cores,
188  weight_function_t weight_func,
189  void *weight )
190  {
191 #if 0
192  static_assert( std::is_signed<
193  std::remove_reference< decltype( c.end() ) >::type >::value,
194  "Container must have signed types so that -1 may signify no mapping" );
195 #endif
196  raftgraph_t raft_graph;
197  get_graph_info( c,
198  raft_graph,
199  weight_func,
200  nullptr );
201  SCOTCH_Graph graph;
202  if( SCOTCH_graphInit( &graph ) != 0 )
203  {
205  std::cerr << "Failed to initialize graph!!\n";
206  exit( EXIT_FAILURE );
207  }
208  auto table( raft_graph.getScotchTables() );
209  if( SCOTCH_graphBuild(
210  &graph ,
211  0 ,
212  table.num_vertices ,
213  table.vtable ,
214  &table.vtable[ 1 ] ,
215  nullptr ,
216  nullptr ,
217  table.num_edges ,
218  table.etable ,
219  table.eweight
220  ) != 0 )
221  {
223  std::cerr << "Failed to build graph\n";
224  exit( EXIT_FAILURE );
225  }
226  if( SCOTCH_graphCheck( &graph ) != 0 )
227  {
229  std::cerr << "Graph is inconsistent\n";
230  exit( EXIT_FAILURE );
231  }
233  SCOTCH_Arch archdat;
234  if( SCOTCH_archInit( &archdat ) != 0 )
235  {
237  std::cerr << "Architecture initialization failed\n";
238  exit( EXIT_FAILURE );
239  }
241  if( SCOTCH_archCmplt( &archdat, cores ) != 0 )
242  {
244  std::cerr << "Failed to create architecture file\n";
245  exit( EXIT_FAILURE );
246  }
248  SCOTCH_Strat stradat;
249  if( SCOTCH_stratInit( &stradat ) != 0 )
250  {
252  std::cerr << "Failed to init strategy!!\n";
253  exit( EXIT_FAILURE );
254  }
256  if( SCOTCH_stratGraphClusterBuild(
257  &stradat,
258  SCOTCH_STRATRECURSIVE,
259  cores,
260  .7,
261  .0001) != 0 )
262  {
264  std::cerr << "Failed to map strategy graph!!\n";
265  exit( EXIT_FAILURE );
266  }
267  if( SCOTCH_graphMap(
268  &graph ,
269  &archdat,
270  &stradat,
271  table.partition
272  ) != 0 )
273  {
275  std::cerr << "Failed to map!!\n";
276  exit( EXIT_FAILURE );
277  }
289  if( c.size() == table.num_vertices )
290  {
292  for( auto i( 0 ); i < table.num_vertices; i++ )
293  {
294  mapping.push_back( table.partition[ i ] );
295  }
296  }
297  else
298  {
299  const auto &vmapping( raft_graph.getVertexNumbersAtIndicies() );
300  auto it_map_index( vmapping.cbegin() );
301  auto table_index( 0 );
302  const auto size( c.size() );
303  for( auto i( 0 ); i < size; i++ )
304  {
305  if( i == (*it_map_index) && it_map_index != vmapping.cend() )
306  {
307  mapping.push_back( table.partition[ table_index++ ] );
308  ++it_map_index;
309  }
310  else
311  {
312  mapping.push_back( -1 );
313  }
314  }
315  }
317  SCOTCH_graphExit( &graph );
318  SCOTCH_stratExit( &stradat );
319  SCOTCH_archExit ( &archdat );
320  return;
321  }
322 
323 };
324 #endif /* END _PARTITION_HPP_ */
Definition: partition.hpp:32
static void simple(Container &c, MappingContainer &mapping, const std::size_t cores)
Definition: partition.hpp:42
virtual std::size_t size()=0
static void utilization_weighted(Container &c, MappingContainer &mapping, const std::size_t cores)
Definition: partition.hpp:69
FIFO * getFIFO()
Definition: port_info.hpp:93
Definition: port_info.hpp:39
Definition: kernel.hpp:48
static void BFS(std::set< raft::kernel * > &source_kernels, edge_func func, void *data=nullptr, bool connected_error=false)
Definition: graphtools.cpp:36