| /*===================================================================*/ |
| // |
| // place_partition.c |
| // |
| // Aaron P. Hurst, 2003-2007 |
| // ahurst@eecs.berkeley.edu |
| // |
| /*===================================================================*/ |
| |
| #include <stdlib.h> |
| #include <math.h> |
| #include <string.h> |
| #include <stdio.h> |
| #include <limits.h> |
| #include <assert.h> |
| //#include <sys/stat.h> |
| //#include <unistd.h> |
| |
| #include "place_base.h" |
| #include "place_gordian.h" |
| |
| #if !defined(NO_HMETIS) |
| #include "libhmetis.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| #endif |
| |
| // -------------------------------------------------------------------- |
| // Global variables |
| // |
| // -------------------------------------------------------------------- |
| |
| Partition *g_place_rootPartition = NULL; |
| ConcreteNet **allNetsR2 = NULL, |
| **allNetsL2 = NULL, |
| **allNetsB2 = NULL, |
| **allNetsT2 = NULL; |
| |
| |
| // -------------------------------------------------------------------- |
| // Function prototypes and local data structures |
| // |
| // -------------------------------------------------------------------- |
| |
| typedef struct FM_cell { |
| int loc; |
| int gain; |
| ConcreteCell *cell; |
| struct FM_cell *next, *prev; |
| bool locked; |
| } FM_cell; |
| |
| void FM_updateGains(ConcreteNet *net, int partition, int inc, |
| FM_cell target [], FM_cell *bin [], |
| int count_1 [], int count_2 []); |
| |
| |
| // -------------------------------------------------------------------- |
| // initPartitioning() |
| // |
| /// \brief Initializes data structures necessary for partitioning. |
| // |
| /// Creates a valid g_place_rootPartition. |
| /// |
| // -------------------------------------------------------------------- |
| void initPartitioning() { |
| int i; |
| float area; |
| |
| // create root partition |
| g_place_numPartitions = 1; |
| if (g_place_rootPartition) free(g_place_rootPartition); |
| g_place_rootPartition = malloc(sizeof(Partition)); |
| g_place_rootPartition->m_level = 0; |
| g_place_rootPartition->m_area = 0; |
| g_place_rootPartition->m_bounds = g_place_coreBounds; |
| g_place_rootPartition->m_vertical = false; |
| g_place_rootPartition->m_done = false; |
| g_place_rootPartition->m_leaf = true; |
| |
| // add all of the cells to this partition |
| g_place_rootPartition->m_members = malloc(sizeof(ConcreteCell*)*g_place_numCells); |
| g_place_rootPartition->m_numMembers = 0; |
| for (i=0; i<g_place_numCells; i++) |
| if (g_place_concreteCells[i]) { |
| if (!g_place_concreteCells[i]->m_fixed) { |
| area = getCellArea(g_place_concreteCells[i]); |
| g_place_rootPartition->m_members[g_place_rootPartition->m_numMembers++] = |
| g_place_concreteCells[i]; |
| g_place_rootPartition->m_area += area; |
| } |
| } |
| } |
| |
| |
| // -------------------------------------------------------------------- |
| // presortNets() |
| // |
| /// \brief Sorts nets by corner positions. |
| // |
| /// Allocates allNetsX2 structures. |
| /// |
| // -------------------------------------------------------------------- |
| void presortNets() { |
| allNetsL2 = (ConcreteNet**)realloc(allNetsL2, sizeof(ConcreteNet*)*g_place_numNets); |
| allNetsR2 = (ConcreteNet**)realloc(allNetsR2, sizeof(ConcreteNet*)*g_place_numNets); |
| allNetsB2 = (ConcreteNet**)realloc(allNetsB2, sizeof(ConcreteNet*)*g_place_numNets); |
| allNetsT2 = (ConcreteNet**)realloc(allNetsT2, sizeof(ConcreteNet*)*g_place_numNets); |
| memcpy(allNetsL2, g_place_concreteNets, sizeof(ConcreteNet*)*g_place_numNets); |
| memcpy(allNetsR2, g_place_concreteNets, sizeof(ConcreteNet*)*g_place_numNets); |
| memcpy(allNetsB2, g_place_concreteNets, sizeof(ConcreteNet*)*g_place_numNets); |
| memcpy(allNetsT2, g_place_concreteNets, sizeof(ConcreteNet*)*g_place_numNets); |
| qsort(allNetsL2, g_place_numNets, sizeof(ConcreteNet*), netSortByL); |
| qsort(allNetsR2, g_place_numNets, sizeof(ConcreteNet*), netSortByR); |
| qsort(allNetsB2, g_place_numNets, sizeof(ConcreteNet*), netSortByB); |
| qsort(allNetsT2, g_place_numNets, sizeof(ConcreteNet*), netSortByT); |
| } |
| |
| // -------------------------------------------------------------------- |
| // refinePartitions() |
| // |
| /// \brief Splits large leaf partitions. |
| // |
| // -------------------------------------------------------------------- |
| bool refinePartitions() { |
| |
| return refinePartition(g_place_rootPartition); |
| } |
| |
| |
| // -------------------------------------------------------------------- |
| // reallocPartitions() |
| // |
| /// \brief Reallocates the partitions based on placement information. |
| // |
| // -------------------------------------------------------------------- |
| void reallocPartitions() { |
| |
| reallocPartition(g_place_rootPartition); |
| } |
| |
| |
| // -------------------------------------------------------------------- |
| // refinePartition() |
| // |
| /// \brief Splits any large leaves within a partition. |
| // |
| // -------------------------------------------------------------------- |
| bool refinePartition(Partition *p) { |
| bool degenerate = false; |
| int nonzeroCount = 0; |
| int i; |
| |
| assert(p); |
| |
| // is this partition completed? |
| if (p->m_done) return true; |
| |
| // is this partition a non-leaf node? |
| if (!p->m_leaf) { |
| p->m_done = refinePartition(p->m_sub1); |
| p->m_done &= refinePartition(p->m_sub2); |
| return p->m_done; |
| } |
| |
| // leaf... |
| // create two new subpartitions |
| g_place_numPartitions++; |
| p->m_sub1 = malloc(sizeof(Partition)); |
| p->m_sub1->m_level = p->m_level+1; |
| p->m_sub1->m_leaf = true; |
| p->m_sub1->m_done = false; |
| p->m_sub1->m_area = 0; |
| p->m_sub1->m_vertical = !p->m_vertical; |
| p->m_sub1->m_numMembers = 0; |
| p->m_sub1->m_members = NULL; |
| p->m_sub2 = malloc(sizeof(Partition)); |
| p->m_sub2->m_level = p->m_level+1; |
| p->m_sub2->m_leaf = true; |
| p->m_sub2->m_done = false; |
| p->m_sub2->m_area = 0; |
| p->m_sub2->m_vertical = !p->m_vertical; |
| p->m_sub2->m_numMembers = 0; |
| p->m_sub2->m_members = NULL; |
| p->m_leaf = false; |
| |
| // --- INITIAL PARTITION |
| |
| if (PARTITION_AREA_ONLY) |
| partitionEqualArea(p); |
| else |
| partitionScanlineMincut(p); |
| |
| resizePartition(p); |
| |
| // --- PARTITION IMPROVEMENT |
| |
| if (p->m_level < REPARTITION_LEVEL_DEPTH) { |
| if (REPARTITION_FM) |
| repartitionFM(p); |
| else if (REPARTITION_HMETIS) |
| repartitionHMetis(p); |
| } |
| |
| resizePartition(p); |
| |
| // fix imbalances due to zero-area cells |
| for(i=0; i<p->m_sub1->m_numMembers; i++) |
| if (p->m_sub1->m_members[i]) |
| if (getCellArea(p->m_sub1->m_members[i]) > 0) { |
| nonzeroCount++; |
| } |
| |
| // is this leaf now done? |
| if (nonzeroCount <= LARGEST_FINAL_SIZE) |
| p->m_sub1->m_done = true; |
| if (nonzeroCount == 0) |
| degenerate = true; |
| |
| nonzeroCount = 0; |
| for(i=0; i<p->m_sub2->m_numMembers; i++) |
| if (p->m_sub2->m_members[i]) |
| if (getCellArea(p->m_sub2->m_members[i]) > 0) { |
| nonzeroCount++; |
| } |
| |
| // is this leaf now done? |
| if (nonzeroCount <= LARGEST_FINAL_SIZE) |
| p->m_sub2->m_done = true; |
| if (nonzeroCount == 0) |
| degenerate = true; |
| |
| // have we found a degenerate partitioning? |
| if (degenerate) { |
| printf("QPART-35 : WARNING: degenerate partition generated\n"); |
| partitionEqualArea(p); |
| resizePartition(p); |
| p->m_sub1->m_done = true; |
| p->m_sub2->m_done = true; |
| } |
| |
| // is this parent now finished? |
| if (p->m_sub1->m_done && p->m_sub2->m_done) p->m_done = true; |
| |
| return p->m_done; |
| } |
| |
| |
| // -------------------------------------------------------------------- |
| // repartitionHMetis() |
| // |
| /// \brief Repartitions the two subpartitions using the hMetis min-cut library. |
| /// |
| /// The number of cut nets between the two partitions will be minimized. |
| // |
| // -------------------------------------------------------------------- |
| void repartitionHMetis(Partition *parent) { |
| #if defined(NO_HMETIS) |
| printf("QPAR_02 : \t\tERROR: hMetis not available. Ignoring.\n"); |
| #else |
| |
| int n,c,t, i; |
| float area; |
| int *edgeConnections = NULL; |
| int *partitionAssignment = (int *)calloc(g_place_numCells, sizeof(int)); |
| int *vertexWeights = (int *)calloc(g_place_numCells, sizeof(int)); |
| int *edgeDegree = (int *)malloc(sizeof(int)*(g_place_numNets+1)); |
| int numConnections = 0; |
| int numEdges = 0; |
| float initial_cut; |
| int targets = 0; |
| ConcreteCell *cell = NULL; |
| int options[9]; |
| int afterCuts = 0; |
| |
| assert(parent); |
| assert(parent->m_sub1); |
| assert(parent->m_sub2); |
| |
| printf("QPAR-02 : \t\trepartitioning with hMetis\n"); |
| |
| // count edges |
| edgeDegree[0] = 0; |
| for(n=0; n<g_place_numNets; n++) if (g_place_concreteNets[n]) |
| if (g_place_concreteNets[n]->m_numTerms > 1) { |
| numConnections += g_place_concreteNets[n]->m_numTerms; |
| edgeDegree[++numEdges] = numConnections; |
| } |
| |
| if (parent->m_vertical) { |
| // vertical |
| initial_cut = parent->m_sub2->m_bounds.x; |
| |
| // initialize all cells |
| for(c=0; c<g_place_numCells; c++) if (g_place_concreteCells[c]) { |
| if (g_place_concreteCells[c]->m_x < initial_cut) |
| partitionAssignment[c] = 0; |
| else |
| partitionAssignment[c] = 1; |
| } |
| |
| // initialize cells in partition 1 |
| for(t=0; t<parent->m_sub1->m_numMembers; t++) if (parent->m_sub1->m_members[t]) { |
| cell = parent->m_sub1->m_members[t]; |
| vertexWeights[cell->m_id] = getCellArea(cell); |
| // pay attention to cells that are close to the cut |
| if (abs(cell->m_x-initial_cut) < parent->m_bounds.w*REPARTITION_TARGET_FRACTION) { |
| targets++; |
| partitionAssignment[cell->m_id] = -1; |
| } |
| } |
| |
| // initialize cells in partition 2 |
| for(t=0; t<parent->m_sub2->m_numMembers; t++) if (parent->m_sub2->m_members[t]) { |
| cell = parent->m_sub2->m_members[t]; |
| vertexWeights[cell->m_id] = getCellArea(cell); |
| // pay attention to cells that are close to the cut |
| if (abs(cell->m_x-initial_cut) < parent->m_bounds.w*REPARTITION_TARGET_FRACTION) { |
| targets++; |
| partitionAssignment[cell->m_id] = -1; |
| } |
| } |
| |
| } else { |
| // horizontal |
| initial_cut = parent->m_sub2->m_bounds.y; |
| |
| // initialize all cells |
| for(c=0; c<g_place_numCells; c++) if (g_place_concreteCells[c]) { |
| if (g_place_concreteCells[c]->m_y < initial_cut) |
| partitionAssignment[c] = 0; |
| else |
| partitionAssignment[c] = 1; |
| } |
| |
| // initialize cells in partition 1 |
| for(t=0; t<parent->m_sub1->m_numMembers; t++) if (parent->m_sub1->m_members[t]) { |
| cell = parent->m_sub1->m_members[t]; |
| vertexWeights[cell->m_id] = getCellArea(cell); |
| // pay attention to cells that are close to the cut |
| if (abs(cell->m_y-initial_cut) < parent->m_bounds.h*REPARTITION_TARGET_FRACTION) { |
| targets++; |
| partitionAssignment[cell->m_id] = -1; |
| } |
| } |
| |
| // initialize cells in partition 2 |
| for(t=0; t<parent->m_sub2->m_numMembers; t++) if (parent->m_sub2->m_members[t]) { |
| cell = parent->m_sub2->m_members[t]; |
| vertexWeights[cell->m_id] = getCellArea(cell); |
| // pay attention to cells that are close to the cut |
| if (abs(cell->m_y-initial_cut) < parent->m_bounds.h*REPARTITION_TARGET_FRACTION) { |
| targets++; |
| partitionAssignment[cell->m_id] = -1; |
| } |
| } |
| } |
| |
| options[0] = 1; // any non-default values? |
| options[1] = 3; // num bisections |
| options[2] = 1; // grouping scheme |
| options[3] = 1; // refinement scheme |
| options[4] = 1; // cycle refinement scheme |
| options[5] = 0; // reconstruction scheme |
| options[6] = 0; // fixed assignments? |
| options[7] = 12261980; // random seed |
| options[8] = 0; // debugging level |
| |
| edgeConnections = (int *)malloc(sizeof(int)*numConnections); |
| |
| i = 0; |
| for(n=0; n<g_place_numNets; n++) if (g_place_concreteNets[n]) { |
| if (g_place_concreteNets[n]->m_numTerms > 1) |
| for(t=0; t<g_place_concreteNets[n]->m_numTerms; t++) |
| edgeConnections[i++] = g_place_concreteNets[n]->m_terms[t]->m_id; |
| } |
| |
| HMETIS_PartRecursive(g_place_numCells, numEdges, vertexWeights, |
| edgeDegree, edgeConnections, NULL, |
| 2, (int)(100*MAX_PARTITION_NONSYMMETRY), |
| options, partitionAssignment, &afterCuts); |
| |
| /* |
| printf("HMET-20 : \t\t\tbalance before %d / %d ... ", parent->m_sub1->m_numMembers, |
| parent->m_sub2->m_numMembers); |
| */ |
| |
| // reassign members to subpartitions |
| parent->m_sub1->m_numMembers = 0; |
| parent->m_sub1->m_area = 0; |
| parent->m_sub2->m_numMembers = 0; |
| parent->m_sub2->m_area = 0; |
| parent->m_sub1->m_members = (ConcreteCell**)realloc(parent->m_sub1->m_members, |
| sizeof(ConcreteCell*)*parent->m_numMembers); |
| parent->m_sub2->m_members = (ConcreteCell**)realloc(parent->m_sub2->m_members, |
| sizeof(ConcreteCell*)*parent->m_numMembers); |
| |
| for(t=0; t<parent->m_numMembers; t++) if (parent->m_members[t]) { |
| cell = parent->m_members[t]; |
| area = getCellArea(cell); |
| if (partitionAssignment[cell->m_id] == 0) { |
| parent->m_sub1->m_members[parent->m_sub1->m_numMembers++] = cell; |
| parent->m_sub1->m_area += area; |
| } |
| else { |
| parent->m_sub2->m_members[parent->m_sub2->m_numMembers++] = cell; |
| parent->m_sub2->m_area += area; |
| } |
| } |
| /* |
| printf("after %d / %d\n", parent->m_sub1->m_numMembers, |
| parent->m_sub2->m_numMembers); |
| */ |
| |
| // cout << "HMET-21 : \t\t\tloc: " << initial_cut << " targetting: " << targets*100/parent->m_members.length() << "%" << endl; |
| // cout << "HMET-22 : \t\t\tstarting cuts= " << beforeCuts << " final cuts= " << afterCuts << endl; |
| |
| free(edgeConnections); |
| free(vertexWeights); |
| free(edgeDegree); |
| free(partitionAssignment); |
| #endif |
| } |
| |
| |
| // -------------------------------------------------------------------- |
| // repartitionFM() |
| // |
| /// \brief Fiduccia-Matheyses mincut partitioning algorithm. |
| // |
| /// UNIMPLEMENTED (well, un-C-ified) |
| // |
| // -------------------------------------------------------------------- |
| void repartitionFM(Partition *parent) { |
| #if 0 |
| assert(!parent->leaf && parent->m_sub1->leaf && parent->m_sub2->leaf); |
| |
| // count of each net's number of cells in each bipartition |
| int count_1[m_design->nets.length()]; |
| memset(count_1, 0, sizeof(int)*m_design->nets.length()); |
| int count_2[m_design->nets.length()]; |
| memset(count_2, 0, sizeof(int)*m_design->nets.length()); |
| |
| FM_cell target[m_design->cells.length()]; |
| memset(target, 0, sizeof(FM_cell)*m_design->cells.length()); |
| FM_cell *bin[FM_MAX_BIN+1]; |
| FM_cell *locked = 0; |
| memset(bin, 0, sizeof(FM_cell *)*(FM_MAX_BIN+1)); |
| |
| int max_gain = 0; |
| int before_cuts = 0, current_cuts = 0; |
| double initial_cut; |
| int targets = 0; |
| long cell_id; |
| double halfArea = parent->m_area / 2.0; |
| double areaFlexibility = parent->m_area * MAX_PARTITION_NONSYMMETRY; |
| ConcreteNet *net; |
| |
| // INITIALIZATION |
| // select cells to partition |
| |
| if (parent->vertical) { |
| // vertical |
| |
| initial_cut = parent->m_sub2->m_bounds.x; |
| |
| // initialize all cells |
| for(h::list<ConcreteCell *>::iterator it = rootPartition->m_members.begin(); !it; it++) { |
| cell_id = (*it)->getID(); |
| if ((*it)->temp_x < initial_cut) |
| target[cell_id].loc = -1; |
| else |
| target[cell_id].loc = -2; |
| target[cell_id].cell = *it; |
| target[cell_id].gain = 0; |
| } |
| |
| // initialize cells in partition 1 |
| for(h::list<ConcreteCell *>::iterator it = parent->m_sub1->m_members.begin(); !it; it++) { |
| cell_id = (*it)->getID(); |
| // pay attention to cells that are close to the cut |
| if (abs((*it)->temp_x-initial_cut) < parent->m_bounds.w*REPARTITION_TARGET_FRACTION) { |
| targets++; |
| target[cell_id].loc = 1; |
| } |
| } |
| |
| // initialize cells in partition 2 |
| for(h::list<ConcreteCell *>::iterator it = parent->m_sub2->m_members.begin(); !it; it++) { |
| cell_id = (*it)->getID(); |
| // pay attention to cells that are close to the cut |
| if (abs((*it)->temp_x-initial_cut) < parent->m_bounds.w*REPARTITION_TARGET_FRACTION) { |
| targets++; |
| target[cell_id].loc = 2; |
| } |
| } |
| |
| // count the number of cells on each side of the partition for every net |
| for(h::hash_map<ConcreteNet *>::iterator n_it = m_design->nets.begin(); !n_it; n_it++) { |
| for(ConcretePinList::iterator p_it = (net = *n_it)->getPins().begin(); !p_it; p_it++) |
| if (abs(target[(*p_it)->getCell()->getID()].loc) == 1) |
| count_1[net->getID()]++; |
| else if (abs(target[(*p_it)->getCell()->getID()].loc) == 2) |
| count_2[net->getID()]++; |
| else if ((*p_it)->getCell()->temp_x < initial_cut) |
| count_1[net->getID()]++; |
| else |
| count_2[net->getID()]++; |
| if (count_1[net->getID()] > 0 && count_2[net->getID()] > 0) before_cuts++; |
| } |
| |
| } else { |
| // horizontal |
| |
| initial_cut = parent->m_sub2->m_bounds.y; |
| |
| // initialize all cells |
| for(h::list<ConcreteCell *>::iterator it = rootPartition->m_members.begin(); !it; it++) { |
| cell_id = (*it)->getID(); |
| if ((*it)->temp_y < initial_cut) |
| target[cell_id].loc = -1; |
| else |
| target[cell_id].loc = -2; |
| target[cell_id].cell = *it; |
| target[cell_id].gain = 0; |
| } |
| |
| // initialize cells in partition 1 |
| for(h::list<ConcreteCell *>::iterator it = parent->m_sub1->m_members.begin(); !it; it++) { |
| cell_id = (*it)->getID(); |
| // pay attention to cells that are close to the cut |
| if (abs((*it)->temp_y-initial_cut) < parent->m_bounds.h*REPARTITION_TARGET_FRACTION) { |
| targets++; |
| target[cell_id].loc = 1; |
| } |
| } |
| |
| // initialize cells in partition 2 |
| for(h::list<ConcreteCell *>::iterator it = parent->m_sub2->m_members.begin(); !it; it++) { |
| cell_id = (*it)->getID(); |
| // pay attention to cells that are close to the cut |
| if (abs((*it)->temp_y-initial_cut) < parent->m_bounds.h*REPARTITION_TARGET_FRACTION) { |
| targets++; |
| target[cell_id].loc = 2; |
| } |
| } |
| |
| // count the number of cells on each side of the partition for every net |
| for(h::hash_map<ConcreteNet *>::iterator n_it = m_design->nets.begin(); !n_it; n_it++) { |
| for(ConcretePinList::iterator p_it = (net = *n_it)->getPins().begin(); !p_it; p_it++) |
| if (abs(target[(*p_it)->getCell()->getID()].loc) == 1) |
| count_1[net->getID()]++; |
| else if (abs(target[(*p_it)->getCell()->getID()].loc) == 2) |
| count_2[net->getID()]++; |
| else if ((*p_it)->getCell()->temp_y < initial_cut) |
| count_1[net->getID()]++; |
| else |
| count_2[net->getID()]++; |
| if (count_1[net->getID()] > 0 && count_2[net->getID()] > 0) before_cuts++; |
| } |
| } |
| |
| // INITIAL GAIN CALCULATION |
| for(long id=0; id < m_design->cells.length(); id++) |
| if (target[id].loc > 0) { |
| assert(target[id].cell != 0); |
| assert(target[id].gain == 0); |
| |
| // examine counts for the net on each pin |
| for(ConcretePinMap::iterator p_it = target[id].cell->getPins().begin(); !p_it; p_it++) |
| if ((*p_it)->isAttached()) { |
| int n_id = (*p_it)->getNet()->getID(); |
| if (target[id].loc == 1 && count_1[n_id] == 1) target[id].gain++; |
| if (target[id].loc == 1 && count_2[n_id] == 0) target[id].gain--; |
| if (target[id].loc == 2 && count_1[n_id] == 0) target[id].gain--; |
| if (target[id].loc == 2 && count_2[n_id] == 1) target[id].gain++; |
| } |
| |
| assert(target[id].cell->getPins().length() >= abs(target[id].gain)); |
| |
| // add it to a bin |
| int bin_num = min(max(0, target[id].gain),FM_MAX_BIN); |
| max_gain = max(max_gain, bin_num); |
| |
| assert(bin_num >= 0 && bin_num <= FM_MAX_BIN); |
| target[id].next = bin[bin_num]; |
| target[id].prev = 0; |
| if (bin[bin_num] != 0) |
| bin[bin_num]->prev = &target[id]; |
| bin[bin_num] = &target[id]; |
| } |
| |
| // OUTER F-M LOOP |
| current_cuts = before_cuts; |
| int num_moves = 1; |
| int pass = 0; |
| while(num_moves > 0 && pass < FM_MAX_PASSES) { |
| pass++; |
| num_moves = 0; |
| |
| // check_list(bin, locked, targets); // DEBUG |
| |
| // move all locked cells back |
| int moved_back = 0; |
| while(locked != 0) { |
| FM_cell *current = locked; |
| current->locked = false; |
| |
| int bin_num = min(max(0, current->gain),FM_MAX_BIN); |
| max_gain = max(max_gain, bin_num); |
| |
| locked = current->next; |
| if (locked != 0) |
| locked->prev = 0; |
| |
| if (bin[bin_num] != 0) |
| bin[bin_num]->prev = current; |
| current->next = bin[bin_num]; |
| bin[bin_num] = current; |
| |
| moved_back++; |
| } |
| // cout << "\tmoved back: " << moved_back << endl; |
| // check_list(bin, locked, targets); // DEBUG |
| |
| max_gain = FM_MAX_BIN; |
| while(bin[max_gain] == 0 && max_gain > 0) max_gain--; |
| |
| // INNER F-M LOOP (single pass) |
| while(1) { |
| |
| int bin_num = FM_MAX_BIN; |
| FM_cell *current = bin[bin_num]; |
| |
| // look for next cell to move |
| while (bin_num > 0 && (current == 0 || |
| (current->loc==1 && current->cell->getArea()+parent->m_sub2->m_area > halfArea+areaFlexibility) || |
| (current->loc==2 && current->cell->getArea()+parent->m_sub1->m_area > halfArea+areaFlexibility))) { |
| |
| if (current == 0) current = bin[--bin_num]; else current = current->next; |
| } |
| if (bin_num == 0) |
| break; |
| |
| num_moves++; |
| current->locked = true; |
| // cout << "moving cell " << current->cell->getID() << " gain=" << current->gain << " pins= " << current->cell->getPins().length() << " from " << current->loc; |
| |
| // change partition marking and areas |
| if (current->loc == 1) { |
| current->loc = 2; |
| parent->m_sub1->m_area -= current->cell->getArea(); |
| parent->m_sub2->m_area += current->cell->getArea(); |
| |
| // update partition counts on all nets attached to this cell |
| for(ConcretePinMap::iterator p_it = current->cell->getPins().begin(); |
| !p_it; p_it++) { |
| |
| if (!(*p_it)->isAttached()) // ignore unattached pins |
| continue; |
| net = (*p_it)->getNet(); |
| |
| count_1[net->getID()]--; |
| count_2[net->getID()]++; |
| |
| // cout << "\tnet " << net->getID() << " was " << count_1[net->getID()]+1 << "/" << count_2[net->getID()]-1 << " now " << count_1[net->getID()] << "/" << count_2[net->getID()] << endl; |
| |
| // if net becomes critical, update gains on attached cells and resort bins |
| if (count_1[net->getID()] == 0) { current_cuts--; FM_updateGains(net, 2, -1, target, bin, count_1, count_2); } |
| if (count_2[net->getID()] == 1) { current_cuts++; FM_updateGains(net, 1, -1, target, bin, count_1, count_2); } |
| |
| // check_list(bin, locked, targets); // DEBUG |
| } |
| |
| } else { |
| current->loc = 1; |
| parent->m_sub2->m_area -= current->cell->getArea(); |
| parent->m_sub1->m_area += current->cell->getArea(); |
| |
| // update gains on all nets attached to this cell |
| for(ConcretePinMap::iterator p_it = current->cell->getPins().begin(); |
| !p_it; p_it++) { |
| |
| if (!(*p_it)->isAttached()) // ignore unattached pins |
| continue; |
| net = (*p_it)->getNet(); |
| count_2[net->getID()]--; |
| count_1[net->getID()]++; |
| |
| // cout << "\tnet " << net->getID() << " was " << count_1[net->getID()]-1 << "/" << count_2[net->getID()]+1 << " now " << count_1[net->getID()] << "/" << count_2[net->getID()] << endl; |
| |
| if (count_2[net->getID()] == 0) { current_cuts--; FM_updateGains(net, 2, -1, target, bin, count_1, count_2); } |
| if (count_1[net->getID()] == 1) { current_cuts++; FM_updateGains(net, 1, -1, target, bin, count_1, count_2); } |
| |
| // check_list(bin, locked, targets); // DEBUG |
| } |
| } |
| |
| //cout << " cuts=" << current_cuts << endl; |
| |
| // move current to locked |
| |
| /* |
| cout << "b=" << bin[bin_num] << " "; |
| cout << current->prev << "-> "; |
| if (current->prev == 0) |
| cout << "X"; |
| else cout << current->prev->next; |
| cout << "=" << current << "="; |
| if (current->next == 0) |
| cout << "X"; |
| else |
| cout << current->next->prev; |
| cout << " ->" << current->next << endl; |
| */ |
| |
| if (bin[bin_num] == current) |
| bin[bin_num] = current->next; |
| if (current->prev != 0) |
| current->prev->next = current->next; |
| if (current->next != 0) |
| current->next->prev = current->prev; |
| |
| /* |
| cout << "b=" << bin[bin_num] << " "; |
| cout << current->prev << "-> "; |
| if (current->prev == 0) |
| cout << "X"; |
| else cout << current->prev->next; |
| cout << "=" << current << "="; |
| if (current->next == 0) |
| cout << "X"; |
| else |
| cout << current->next->prev; |
| cout << " ->" << current->next << endl; |
| */ |
| |
| current->prev = 0; |
| current->next = locked; |
| if (locked != 0) |
| locked->prev = current; |
| locked = current; |
| |
| // check_list(bin, locked, targets); // DEBUG |
| |
| // update max_gain |
| max_gain = FM_MAX_BIN; |
| while(bin[max_gain] == 0 && max_gain > 0) max_gain--; |
| } |
| |
| // cout << "\tcurrent cuts= " << current_cuts << " moves= " << num_moves << endl; |
| } |
| |
| // reassign members to subpartitions |
| cout << "FIDM-20 : \tbalance before " << parent->m_sub1->m_members.length() << "/" |
| << parent->m_sub2->m_members.length() << " "; |
| parent->m_sub1->m_members.clear(); |
| parent->m_sub1->m_area = 0; |
| parent->m_sub2->m_members.clear(); |
| parent->m_sub2->m_area = 0; |
| for(h::list<ConcreteCell *>::iterator it = parent->m_members.begin(); !it; it++) { |
| if (target[(*it)->getID()].loc == 1 || target[(*it)->getID()].loc == -1) { |
| parent->m_sub1->m_members.push_back(*it); |
| parent->m_sub1->m_area += (*it)->getArea(); |
| } |
| else { |
| parent->m_sub2->m_members.push_back(*it); |
| parent->m_sub2->m_area += (*it)->getArea(); |
| } |
| } |
| cout << " after " << parent->m_sub1->m_members.length() << "/" |
| << parent->m_sub2->m_members.length() << endl; |
| |
| |
| cout << "FIDM-21 : \tloc: " << initial_cut << " targetting: " << targets*100/parent->m_members.length() << "%" << endl; |
| cout << "FIDM-22 : \tstarting cuts= " << before_cuts << " final cuts= " << current_cuts << endl; |
| #endif |
| } |
| |
| // ----- FM_updateGains() |
| // moves a cell between bins |
| #if 0 |
| void FM_updateGains(ConcreteNet *net, int partition, int inc, |
| FM_cell target [], FM_cell *bin [], |
| int count_1 [], int count_2 []) { |
| |
| for(ConcretePinList::iterator it = net->getPins().begin(); !it; it++) { |
| FM_cell *current = &(target[(*it)->getCell()->getID()]); |
| assert(current->cell != 0); |
| |
| int old_gain = current->gain; |
| current->gain = 0; |
| |
| // examine counts for the net on each pin |
| for(ConcretePinMap::iterator p_it = current->cell->getPins().begin(); !p_it; p_it++) |
| if ((*p_it)->isAttached()) { |
| int n_id = (*p_it)->getNet()->getID(); |
| if (current->loc == 1 && count_1[n_id] == 1) current->gain++; |
| if (current->loc == 1 && count_2[n_id] == 0) current->gain--; |
| if (current->loc == 2 && count_1[n_id] == 0) current->gain--; |
| if (current->loc == 2 && count_2[n_id] == 1) current->gain++; |
| } |
| |
| if (!current->locked) { |
| // remove cell from existing bin |
| int bin_num = min(max(0, old_gain),FM_MAX_BIN); |
| if (bin[bin_num] == current) |
| bin[bin_num] = current->next; |
| if (current->prev != 0) |
| current->prev->next = current->next; |
| if (current->next != 0) |
| current->next->prev = current->prev; |
| // add cell to correct bin |
| bin_num = min(max(0, current->gain),FM_MAX_BIN); |
| current->prev = 0; |
| current->next = bin[bin_num]; |
| if (bin[bin_num] != 0) |
| bin[bin_num]->prev = current; |
| bin[bin_num] = current; |
| } |
| } |
| |
| } |
| #endif |
| |
| |
| // -------------------------------------------------------------------- |
| // partitionEqualArea() |
| // |
| /// \brief Splits a partition into two halves of equal area. |
| // |
| // -------------------------------------------------------------------- |
| void partitionEqualArea(Partition *parent) { |
| float halfArea, area; |
| int i=0; |
| |
| // which way to sort? |
| if (parent->m_vertical) |
| // sort by X position |
| qsort(parent->m_members, parent->m_numMembers, sizeof(ConcreteCell*), cellSortByX); |
| else |
| // sort by Y position |
| qsort(parent->m_members, parent->m_numMembers, sizeof(ConcreteCell*), cellSortByY); |
| |
| // split the list |
| halfArea = parent->m_area*0.5; |
| parent->m_sub1->m_area = 0.0; |
| parent->m_sub1->m_numMembers = 0; |
| parent->m_sub1->m_members = (ConcreteCell**)realloc(parent->m_sub1->m_members, |
| sizeof(ConcreteCell*)*parent->m_numMembers); |
| parent->m_sub2->m_area = 0.0; |
| parent->m_sub2->m_numMembers = 0; |
| parent->m_sub2->m_members = (ConcreteCell**)realloc(parent->m_sub2->m_members, |
| sizeof(ConcreteCell*)*parent->m_numMembers); |
| |
| for(; parent->m_sub1->m_area < halfArea; i++) |
| if (parent->m_members[i]) { |
| area = getCellArea(parent->m_members[i]); |
| parent->m_sub1->m_members[parent->m_sub1->m_numMembers++] = parent->m_members[i]; |
| parent->m_sub1->m_area += area; |
| } |
| for(; i<parent->m_numMembers; i++) |
| if (parent->m_members[i]) { |
| area = getCellArea(parent->m_members[i]); |
| parent->m_sub2->m_members[parent->m_sub2->m_numMembers++] = parent->m_members[i]; |
| parent->m_sub2->m_area += area; |
| } |
| |
| } |
| |
| |
| // -------------------------------------------------------------------- |
| // partitionScanlineMincut() |
| // |
| /// \brief Scans the cells within a partition from left to right and chooses the min-cut. |
| // |
| // -------------------------------------------------------------------- |
| void partitionScanlineMincut(Partition *parent) { |
| #if 0 |
| int current_cuts = 0; |
| int minimum_cuts = INT_MAX; |
| ConcreteCell *minimum_location = NULL; |
| double currentArea = 0, halfArea = parent->m_area * 0.5; |
| double areaFlexibility = parent->m_area * MAX_PARTITION_NONSYMMETRY; |
| double newLine, oldLine = -DBL_MAX; |
| |
| for(ConcreteNetList::iterator n_it = m_design->nets.begin(); !n_it; n_it++) |
| (*n_it)->m_mark = 0; |
| for(h::list<ConcreteCell *>::iterator i = parent->m_members.begin(); |
| !i.isDone(); i++) { |
| assert(*i); |
| for(ConcretePinMap::iterator j = (*i)->getPins().begin(); |
| !j.isDone(); j++) { |
| assert(*j); |
| if((*j)->isAttached()) { |
| (*j)->getNet()->m_mark = 1; |
| } |
| } |
| } |
| |
| if (parent->vertical) { |
| parent->m_members.sort(sortByX); |
| int all1 = 0, all2 = 0; |
| h::list<ConcreteCell *>::iterator local = parent->m_members.begin(); |
| for(; !local.isDone(); local++) { |
| currentArea += (*local)->getArea(); |
| if (currentArea < halfArea-areaFlexibility) |
| continue; |
| if (currentArea > halfArea+areaFlexibility) |
| break; |
| newLine = (*local)->temp_x; |
| while(all1 < g_place_numNets && allNetsL2[all1]->getBoundingBox().left() <= newLine) { |
| if(allNetsL2[all1]->m_mark) { |
| current_cuts++; |
| } |
| all1++; |
| } |
| while(all2 < g_place_numNets && allNetsR2[all2]->getBoundingBox().right() <= newLine) { |
| if(allNetsR2[all2]->m_mark) { |
| current_cuts--; |
| } |
| all2++; |
| } |
| if (current_cuts < minimum_cuts) { |
| minimum_cuts = current_cuts; |
| minimum_location = *local; |
| } |
| oldLine = newLine; |
| } |
| } |
| else { |
| parent->m_members.sort(sortByY); |
| int all1 = 0, all2 = 0; |
| h::list<ConcreteCell *>::iterator local = parent->m_members.begin(); |
| for(; !local.isDone(); local++) { |
| currentArea += (*local)->getArea(); |
| if (currentArea < halfArea-areaFlexibility) |
| continue; |
| if (currentArea > halfArea+areaFlexibility) |
| break; |
| newLine = (*local)->temp_y; |
| while(all1 < g_place_numNets && allNetsB2[all1]->getBoundingBox().top() <= newLine) { |
| if(allNetsB2[all1]->m_mark) { |
| current_cuts++; |
| } |
| all1++; |
| } |
| while(all2 < g_place_numNets && allNetsT2[all2]->getBoundingBox().bottom() <= newLine) { |
| if(allNetsT2[all2]->m_mark) { |
| current_cuts--; |
| } |
| all2++; |
| } |
| if (current_cuts < minimum_cuts) { |
| minimum_cuts = current_cuts; |
| minimum_location = *local; |
| } |
| oldLine = newLine; |
| } |
| } |
| if (minimum_location == NULL) { |
| return partitionEqualArea(parent); |
| } |
| h::list<ConcreteCell *>::iterator it = parent->m_members.begin(); |
| parent->m_sub1->m_members.clear(); |
| parent->m_sub1->m_area = 0; |
| for(; *it != minimum_location; it++) { |
| parent->m_sub1->m_members.push_front(*it); |
| parent->m_sub1->m_area += (*it)->getArea(); |
| } |
| parent->m_sub2->m_members.clear(); |
| parent->m_sub2->m_area = 0; |
| for(; !it; it++) { |
| parent->m_sub2->m_members.push_front(*it); |
| parent->m_sub2->m_area += (*it)->getArea(); |
| } |
| #endif |
| } |
| |
| |
| // -------------------------------------------------------------------- |
| // reallocPartition() |
| // |
| /// \brief Reallocates a partition and all of its children. |
| // |
| // -------------------------------------------------------------------- |
| void reallocPartition(Partition *p) { |
| |
| if (p->m_leaf) { |
| return; |
| } |
| |
| // --- INITIAL PARTITION |
| |
| if (PARTITION_AREA_ONLY) |
| partitionEqualArea(p); |
| else |
| partitionScanlineMincut(p); |
| |
| resizePartition(p); |
| |
| // --- PARTITION IMPROVEMENT |
| if (p->m_level < REPARTITION_LEVEL_DEPTH) { |
| if (REPARTITION_HMETIS) |
| repartitionHMetis(p); |
| |
| resizePartition(p); |
| } |
| |
| reallocPartition(p->m_sub1); |
| reallocPartition(p->m_sub2); |
| } |
| |
| |
| // -------------------------------------------------------------------- |
| // resizePartition() |
| // |
| /// \brief Recomputes the bounding boxes of the child partitions based on their relative areas. |
| // |
| // -------------------------------------------------------------------- |
| void resizePartition(Partition *p) { |
| // compute the new bounding box |
| p->m_sub1->m_bounds.x = p->m_bounds.x; |
| p->m_sub1->m_bounds.y = p->m_bounds.y; |
| if (p->m_vertical) { |
| p->m_sub1->m_bounds.w = p->m_bounds.w*(p->m_sub1->m_area/p->m_area); |
| p->m_sub1->m_bounds.h = p->m_bounds.h; |
| p->m_sub2->m_bounds.x = p->m_bounds.x + p->m_sub1->m_bounds.w; |
| p->m_sub2->m_bounds.w = p->m_bounds.w*(p->m_sub2->m_area/p->m_area); |
| p->m_sub2->m_bounds.y = p->m_bounds.y; |
| p->m_sub2->m_bounds.h = p->m_bounds.h; |
| } else { |
| p->m_sub1->m_bounds.h = p->m_bounds.h*(p->m_sub1->m_area/p->m_area); |
| p->m_sub1->m_bounds.w = p->m_bounds.w; |
| p->m_sub2->m_bounds.y = p->m_bounds.y + p->m_sub1->m_bounds.h; |
| p->m_sub2->m_bounds.h = p->m_bounds.h*(p->m_sub2->m_area/p->m_area); |
| p->m_sub2->m_bounds.x = p->m_bounds.x; |
| p->m_sub2->m_bounds.w = p->m_bounds.w; |
| } |
| } |
| |
| |
| // -------------------------------------------------------------------- |
| // incrementalSubpartition() |
| // |
| /// \brief Adds new cells to an existing partition. Partition sizes/locations are unchanged. |
| /// |
| /// The function recurses, adding new cells to appropriate subpartitions. |
| // |
| // -------------------------------------------------------------------- |
| void incrementalSubpartition(Partition *p, ConcreteCell *newCells [], const int numNewCells) { |
| int c; |
| ConcreteCell **newCells1 = (ConcreteCell **)malloc(sizeof(ConcreteCell*)*numNewCells), |
| **newCells2 = (ConcreteCell **)malloc(sizeof(ConcreteCell*)*numNewCells); |
| int numNewCells1 = 0, numNewCells2 = 0; |
| float cut_loc; |
| |
| assert(p); |
| |
| // add new cells to partition list |
| p->m_members = (ConcreteCell**)realloc(p->m_members, |
| sizeof(ConcreteCell*)*(p->m_numMembers+numNewCells)); |
| memcpy(&(p->m_members[p->m_numMembers]), newCells, sizeof(ConcreteCell*)*numNewCells); |
| p->m_numMembers += numNewCells; |
| |
| // if is a leaf partition, finished |
| if (p->m_leaf) return; |
| |
| // split new cells into sub-partitions based on location |
| if (p->m_vertical) { |
| cut_loc = p->m_sub2->m_bounds.x; |
| for(c=0; c<numNewCells; c++) |
| if (newCells[c]->m_x < cut_loc) |
| newCells1[numNewCells1++] = newCells[c]; |
| else |
| newCells2[numNewCells2++] = newCells[c]; |
| } else { |
| cut_loc = p->m_sub2->m_bounds.y; |
| for(c=0; c<numNewCells; c++) |
| if (newCells[c]->m_y < cut_loc) |
| newCells1[numNewCells1++] = newCells[c]; |
| else |
| newCells2[numNewCells2++] = newCells[c]; |
| } |
| |
| if (numNewCells1 > 0) incrementalSubpartition(p->m_sub1, newCells1, numNewCells1); |
| if (numNewCells2 > 0) incrementalSubpartition(p->m_sub2, newCells2, numNewCells2); |
| |
| free(newCells1); |
| free(newCells2); |
| } |
| |
| |
| // -------------------------------------------------------------------- |
| // incrementalPartition() |
| // |
| /// \brief Adds new cells to an existing partition. Partition sizes/locations are unchanged. |
| /// |
| /// The function recurses, adding new cells to appropriate subpartitions. |
| // |
| // -------------------------------------------------------------------- |
| void incrementalPartition() { |
| int c = 0, c2 = 0; |
| int numNewCells = 0; |
| ConcreteCell **allCells = (ConcreteCell **)malloc(sizeof(ConcreteCell*)*g_place_numCells), |
| **newCells = (ConcreteCell **)malloc(sizeof(ConcreteCell*)*g_place_numCells); |
| |
| assert(g_place_rootPartition); |
| |
| // update cell list of root partition |
| memcpy(allCells, g_place_concreteCells, sizeof(ConcreteCell*)*g_place_numCells); |
| qsort(allCells, g_place_numCells, sizeof(ConcreteCell*), cellSortByID); |
| qsort(g_place_rootPartition->m_members, g_place_rootPartition->m_numMembers, |
| sizeof(ConcreteCell*), cellSortByID); |
| |
| // scan sorted lists and collect cells not in partitions |
| while(!allCells[c++]); |
| while(!g_place_rootPartition->m_members[c2++]); |
| |
| for(; c<g_place_numCells; c++, c2++) { |
| while(c2 < g_place_rootPartition->m_numMembers && |
| allCells[c]->m_id > g_place_rootPartition->m_members[c2]->m_id) c2++; |
| while(c < g_place_numCells && |
| (c2 >= g_place_rootPartition->m_numMembers || |
| allCells[c]->m_id < g_place_rootPartition->m_members[c2]->m_id)) { |
| // a new cell! |
| newCells[numNewCells++] = allCells[c]; |
| c++; |
| } |
| } |
| |
| printf("QPRT-50 : \tincremental partitioning with %d new cells\n", numNewCells); |
| if (numNewCells>0) incrementalSubpartition(g_place_rootPartition, newCells, numNewCells); |
| |
| free(allCells); |
| free(newCells); |
| } |
| ABC_NAMESPACE_IMPL_END |
| |
