12 #ifndef _LIMBO_ALGORITHMS_PARTITION_FM_H
13 #define _LIMBO_ALGORITHMS_PARTITION_FM_H
20 #include <boost/array.hpp>
21 #include <boost/unordered_map.hpp>
31 using boost::unordered_map;
46 template <
typename NodeType>
50 typedef NodeType node_type;
51 typedef typename node_type::tie_id_type tie_id_type;
52 typedef typename node_type::weight_type node_weight_type;
57 static tie_id_type
tie_id(node_type
const& n)
61 static node_weight_type
weight(node_type
const& n)
71 template <
typename NodeType,
typename NetWeightType =
double>
76 typedef NodeType node_type;
77 typedef NetWeightType net_weight_type;
108 net_weight_type g = 0;
109 for (
typename vector<FM_net_type*>::const_iterator itNet = vNet.begin();
110 itNet != vNet.end(); ++itNet)
113 for (
typename vector<FM_node_type*>::const_iterator itNode = (*itNet)->vNode.begin();
114 itNode != (*itNet)->vNode.end(); ++itNode)
116 assert((*itNode)->partition == 0 || (*itNode)->partition == 1);
118 if (
this == *itNode)
continue;
119 else if (this->partition == (*itNode)->partition)
120 g -= (*itNet)->weight;
122 g += (*itNet)->weight;
125 int exclusivePartition = (*itNet)->exclusive_partition(*
this);
126 if (exclusivePartition != 2)
129 if (this->partition == exclusivePartition)
130 g -= (*itNet)->weight;
133 g += (*itNet)->weight;
151 if (vNode.size() < 2)
return 0;
152 for (
typename vector<FM_node_type*>::const_iterator itNode = vNode.begin()+1;
153 itNode != vNode.end(); ++itNode)
155 assert((*itNode)->partition == 0 || (*itNode)->partition == 1);
156 if ((*(itNode-1))->partition != (*itNode)->partition)
168 int prevPartition = -1;
169 int exclusivePartition = -1;
173 for (
typename vector<FM_node_type*>::const_iterator itNode = vNode.begin();
174 itNode != vNode.end(); ++itNode)
176 assert((*itNode)->partition == 0 || (*itNode)->partition == 1);
178 if (fmNode.
pNode == (*itNode)->pNode)
continue;
179 else if (prevPartition < 0)
181 prevPartition = (*itNode)->partition;
182 exclusivePartition = prevPartition;
184 else if (prevPartition != (*itNode)->partition)
186 exclusivePartition = 2;
190 return exclusivePartition;
195 struct compare_type1;
196 struct compare_type2;
208 return pFMNode1->
gain() > pFMNode2->
gain();
214 bool operator()(net_weight_type
const& g1, net_weight_type
const& g2)
const
219 bool operator()(set<FM_node_type*, compare_type2>
const& s1, set<FM_node_type*, compare_type2>
const& s2)
const
221 assert(!s1.empty() && !s2.empty());
222 return (*
this)(*s1.begin(), *s2.begin());
243 class gain_bucket_type :
public map<net_weight_type, set<FM_node_type*, compare_type2>, compare_type1>
247 typedef set<FM_node_type*, compare_type2> nested_type;
248 typedef map<net_weight_type, nested_type, compare_type1> base_type;
261 net_weight_type gain = pFMNode->
gain();
262 typename base_type::iterator found = this->find(gain);
263 if (found == this->end())
265 set<FM_node_type*, compare_type2> sTmp;
266 sTmp.insert(pFMNode);
267 this->base_type::insert(make_pair(gain, sTmp));
271 found->second.insert(pFMNode);
278 net_weight_type gain = pFMNode->
gain();
279 typename base_type::iterator found = this->find(gain);
280 if (found != this->end())
282 if (found->second.empty())
return;
283 else if (found->second.size() == 1 && found->second.count(pFMNode))
284 this->base_type::erase(found);
286 found->second.erase(pFMNode);
294 for (
typename base_type::const_iterator it1 = this->begin();
295 it1 != this->end(); ++it1)
296 for (
typename nested_type::const_iterator it2 = it1->second.begin();
297 it2 != it1->second.end(); ++it2)
304 cout <<
"------- gain_bucket -------" << endl;
305 cout <<
"total # element = " << this->
element_size() << endl;
306 for (
typename base_type::const_iterator it1 = this->begin();
307 it1 != this->end(); ++it1)
309 cout <<
"gain = " << it1->first <<
": ";
310 for (
typename nested_type::const_iterator it2 = it1->second.begin();
311 it2 != it1->second.end(); ++it2)
323 for (
typename unordered_map<node_type*, FM_node_type*>::const_iterator it =
m_hNode.begin();
326 for (
typename vector<FM_net_type*>::const_iterator it =
m_vNet.begin();
334 bool add_node(node_type* pNode,
int initialPartition)
336 assert(initialPartition == 0 || initialPartition == 1);
339 pFMNode->
pNode = pNode;
342 return m_hNode.insert(make_pair(pNode, pFMNode)).second;
353 template <
typename Iterator>
354 bool add_net(net_weight_type
const& weight, Iterator first, Iterator last)
359 for (Iterator it = first; it != last; ++it)
361 typename unordered_map<node_type*, FM_node_type*>::const_iterator found =
m_hNode.find(*it);
369 pFMNet->
vNode.push_back(found->second);
372 for (
typename vector<FM_node_type*>::const_iterator itNode = pFMNet->
vNode.begin();
373 itNode != pFMNet->
vNode.end(); ++itNode)
374 (*itNode)->vNet.push_back(pFMNet);
382 net_weight_type cs = 0;
383 for (
typename vector<FM_net_type*>::const_iterator it =
m_vNet.begin();
385 cs += (*it)->cutsize();
394 return this->
run(ratio1, ratio2);
399 cout <<
"------- partitions -------" << endl;
400 vector<typename FM_node_traits<node_type>::tie_id_type> vPartition[2];
402 for (
typename unordered_map<node_type*, FM_node_type*>::const_iterator it =
m_hNode.begin();
411 it != vPartition[0].end(); ++it)
412 cout << (*it) <<
" ";
415 it != vPartition[1].end(); ++it)
416 cout << (*it) <<
" ";
422 cout <<
"------- connections -------" << endl;
423 for (
typename vector<FM_net_type*>::const_iterator itNet =
m_vNet.begin();
424 itNet !=
m_vNet.end(); ++itNet)
427 for (
typename vector<FM_node_type*>::const_iterator itNode = pFMNet->
vNode.begin();
428 itNode != pFMNet->
vNode.end(); ++itNode)
431 if (itNode != pFMNet->
vNode.begin())
434 cout << FM_node_traits<node_type>::tie_id(*(pFMNode->
pNode));
442 cout <<
"------- nodes -------" << endl;
443 for (
typename unordered_map<node_type*, FM_node_type*>::const_iterator it =
m_hNode.begin();
449 cout << FM_node_traits<node_type>::tie_id(*(pFMNode->
pNode)) <<
": ";
450 cout <<
"partition = " << pFMNode->
partition <<
"; ";
451 cout <<
"partition_bak = " << pFMNode->
partition_bak <<
"; ";
452 cout <<
"locked = " << pFMNode->
locked <<
"; ";
453 cout <<
"weight = " << pFMNode->
weight <<
"; ";
454 cout <<
"gain = " << pFMNode->
gain() <<
"; ";
463 net_weight_type
run(
double ratio1,
double ratio2)
465 net_weight_type prev_cutsize;
466 net_weight_type cur_cutsize = this->
cutsize();
468 unsigned int iter_cnt = 0;
471 cout <<
"######### iteration #" << iter_cnt++ <<
" #########" << endl;
473 prev_cutsize = cur_cutsize;
475 pair<net_weight_type, int> trial_pass = this->
single_pass(ratio1, ratio2, -1);
479 pair<net_weight_type, int> actual_pass = this->
single_pass(ratio1, ratio2, trial_pass.second);
483 assert(trial_pass == actual_pass &&
limbo::abs(actual_pass.first-this->cutsize()) < 1e-6);
486 cur_cutsize = actual_pass.first;
487 }
while (cur_cutsize < prev_cutsize);
496 pair<net_weight_type, int>
single_pass(
double ratio1,
double ratio2,
int target_cnt)
501 cout <<
"======= trial phase =======" << endl;
502 for (
typename unordered_map<node_type*, FM_node_type*>::const_iterator it =
m_hNode.begin();
509 else cout <<
"======= actual phase w. target_cnt = " << target_cnt <<
" =======" << endl;
515 node_weight_type total_weight[2] = {0, 0};
516 net_weight_type cur_cutsize = this->
cutsize();
517 net_weight_type best_cutsize = cur_cutsize;
518 for (
typename unordered_map<node_type*, FM_node_type*>::const_iterator it =
m_hNode.begin();
524 gain_bucket.
insert(pFMNode);
532 for (
typename unordered_map<node_type*, FM_node_type*>::const_iterator it =
m_hNode.begin();
541 cout <<
"initial cutsize = " << this->
cutsize() << endl;
546 while (!gain_bucket.empty())
548 if (cur_cnt == target_cnt)
break;
554 for (
typename gain_bucket_type::const_iterator it1 = gain_bucket.begin();
555 it1 != gain_bucket.end(); ++it1)
557 for (
typename gain_bucket_type::nested_type::const_iterator it2 = it1->second.begin();
558 it2 != it1->second.end(); ++it2)
562 node_weight_type tmp_total_weight[2] = {
571 double cur_ratio = (double)total_weight[0]/total_weight[1];
572 double tmp_ratio = (double)tmp_total_weight[0]/tmp_total_weight[1];
578 pFMNodeBest = pFMNode;
582 if (pFMNodeBest)
break;
585 if (!pFMNodeBest)
break;
596 gain_bucket.
erase(pFMNodeBest);
597 for (
typename vector<FM_net_type*>::const_iterator itNet = pFMNodeBest->
vNet.begin();
598 itNet != pFMNodeBest->
vNet.end(); ++itNet)
600 for (
typename vector<FM_node_type*>::const_iterator itNode = (*itNet)->vNode.begin();
601 itNode != (*itNet)->vNode.end(); ++itNode)
604 if (*itNode == pFMNodeBest || (*itNode)->
locked)
continue;
608 gain_bucket.
erase(*itNode);
618 for (
typename vector<FM_net_type*>::const_iterator itNet = pFMNodeBest->
vNet.begin();
619 itNet != pFMNodeBest->
vNet.end(); ++itNet)
622 for (
typename vector<FM_node_type*>::const_iterator itNode = (*itNet)->vNode.begin();
623 itNode != (*itNet)->vNode.end(); ++itNode)
626 if (*itNode == pFMNodeBest)
continue;
628 if (pFMNodeBest->
partition == (*itNode)->partition)
629 cur_cutsize += (*itNet)->weight;
631 cur_cutsize -= (*itNet)->weight;
634 int exclusivePartition = (*itNet)->exclusive_partition(*pFMNodeBest);
635 if (exclusivePartition != 2)
638 if (pFMNodeBest->
partition == exclusivePartition)
639 cur_cutsize += (*itNet)->weight;
642 cur_cutsize -= (*itNet)->weight;
648 pFMNodeBest->
locked =
true;
650 for (
typename vector<FM_net_type*>::const_iterator itNet = pFMNodeBest->
vNet.begin();
651 itNet != pFMNodeBest->
vNet.end(); ++itNet)
653 for (
typename vector<FM_node_type*>::const_iterator itNode = (*itNet)->vNode.begin();
654 itNode != (*itNet)->vNode.end(); ++itNode)
656 if (*itNode == pFMNodeBest || (*itNode)->
locked)
continue;
657 gain_bucket.
insert(*itNode);
668 cout <<
"move cnt = " << cur_cnt <<
", current cutsize = " << this->
cutsize() << endl;
671 if (cur_cutsize < best_cutsize)
673 best_cutsize = cur_cutsize;
680 for (
typename unordered_map<node_type*, FM_node_type*>::const_iterator it =
m_hNode.begin();
688 return make_pair(best_cutsize, best_cnt);
691 unordered_map<node_type*, FM_node_type*>
m_hNode;
void print_node() const
print node
static node_weight_type weight(node_type const &n)
net type for the algorithm
node_type * pNode
node in the graph
int partition
partition id: 0 or 1, -1 for uninitialized
net_weight_type gain() const
compute gain
Implementation of FM partitioning algorithm.
T abs(T const &t)
generalized api can handle both integer and floating points
net_weight_type operator()(double ratio1, double ratio2)
net_weight_type weight
net weight
gain_bucket_type m_gain_bucket
gain buckets
virtual void erase(FM_node_type *const &pFMNode)
bool operator()(net_weight_type const &g1, net_weight_type const &g2) const
API for comparison.
static tie_id_type tie_id(node_type const &n)
virtual void insert(FM_node_type *const &pFMNode)
node type for the algorithm
unordered_map< node_type *, FM_node_type * > m_hNode
FM nodes.
pair< net_weight_type, int > single_pass(double ratio1, double ratio2, int target_cnt)
one pass of moving nodes
mathematical utilities such as abs
bool add_node(node_type *pNode, int initialPartition)
add node
FM_node_type()
constructor
node_weight_type weight
node weight for balancing constraint, like area
gain_bucket_type(gain_bucket_type const &rhs)
vector< FM_net_type * > vNet
nets related to the node
size_t element_size() const
int partition_bak
back up partition for trial pass
net_weight_type run(double ratio1, double ratio2)
kernel function to run the algorithm
int exclusive_partition(FM_node_type const &fmNode) const
partition excludes a certain node
vector< FM_node_type * > vNode
nodes in the net
void print() const
print function
void print_connection() const
print connection
bool operator()(FM_node_type *pFMNode1, FM_node_type *pFMNode2) const
API for comparison.
void print() const
print gain bucket
vector< FM_net_type * > m_vNet
FM nets.
gain_bucket_type()
constructor
bool add_net(net_weight_type const &weight, Iterator first, Iterator last)
add nets
net_weight_type cutsize() const
compute cut size for the net
bool operator()(FM_node_type *pFMNode1, FM_node_type *pFMNode2) const
API for comparison.
net_weight_type cutsize() const