diff options
Diffstat (limited to 'src/phys/place/place_partition.c')
| -rw-r--r-- | src/phys/place/place_partition.c | 1135 |
1 files changed, 0 insertions, 1135 deletions
diff --git a/src/phys/place/place_partition.c b/src/phys/place/place_partition.c deleted file mode 100644 index ea57cd1c..00000000 --- a/src/phys/place/place_partition.c +++ /dev/null @@ -1,1135 +0,0 @@ -/*===================================================================*/ -// -// 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" -#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); -} |