/*===================================================================*/ // // place_genqp.c // // Aaron P. Hurst, 2003-2007 // ahurst@eecs.berkeley.edu // /*===================================================================*/ #include #include #include #include #include #include "place_base.h" #include "place_qpsolver.h" #include "place_gordian.h" ABC_NAMESPACE_IMPL_START // -------------------------------------------------------------------- // Global variables // // -------------------------------------------------------------------- qps_problem_t *g_place_qpProb = NULL; // -------------------------------------------------------------------- // splitPenalty() // /// \brief Returns a weight for all of the edges in the clique for a multipin net. // // -------------------------------------------------------------------- float splitPenalty(int pins) { if (pins > 1) { return 1.0 + CLIQUE_PENALTY/(pins - 1); // return pow(pins - 1, CLIQUE_PENALTY); } return 1.0 + CLIQUE_PENALTY; } // -------------------------------------------------------------------- // constructQuadraticProblem() // /// \brief Constructs the matrices necessary to do analytical placement. // // -------------------------------------------------------------------- void constructQuadraticProblem() { int maxConnections = 1; int ignoreNum = 0; int n,t,c,c2,p; ConcreteCell *cell; ConcreteNet *net; int *cell_numTerms = calloc(g_place_numCells, sizeof(int)); ConcreteNet ***cell_terms = calloc(g_place_numCells, sizeof(ConcreteNet**)); bool incremental = false; int nextIndex = 1; int *seen = calloc(g_place_numCells, sizeof(int)); float weight; int last_index; // create problem object if (!g_place_qpProb) { g_place_qpProb = malloc(sizeof(qps_problem_t)); g_place_qpProb->area = NULL; g_place_qpProb->x = NULL; g_place_qpProb->y = NULL; g_place_qpProb->fixed = NULL; g_place_qpProb->connect = NULL; g_place_qpProb->edge_weight = NULL; } // count the maximum possible number of non-sparse entries for(n=0; nm_numTerms > IGNORE_NETSIZE) { ignoreNum++; } else { maxConnections += net->m_numTerms*(net->m_numTerms-1); for(t=0; tm_numTerms; t++) { c = net->m_terms[t]->m_id; p = ++cell_numTerms[c]; cell_terms[c] = (ConcreteNet**)realloc(cell_terms[c], p*sizeof(ConcreteNet*)); cell_terms[c][p-1] = net; } } } if(ignoreNum) { printf("QMAN-10 : \t\t%d large nets ignored\n", ignoreNum); } // initialize the data structures g_place_qpProb->num_cells = g_place_numCells; maxConnections += g_place_numCells + 1; g_place_qpProb->area = realloc(g_place_qpProb->area, sizeof(float)*g_place_numCells);// "area" matrix g_place_qpProb->edge_weight = realloc(g_place_qpProb->edge_weight, sizeof(float)*maxConnections); // "weight" matrix g_place_qpProb->connect = realloc(g_place_qpProb->connect, sizeof(int)*maxConnections); // "connectivity" matrix g_place_qpProb->fixed = realloc(g_place_qpProb->fixed, sizeof(int)*g_place_numCells); // "fixed" matrix // initialize or keep preexisting locations if (g_place_qpProb->x != NULL && g_place_qpProb->y != NULL) { printf("QMAN-10 :\tperforming incremental placement\n"); incremental = true; } g_place_qpProb->x = (float*)realloc(g_place_qpProb->x, sizeof(float)*g_place_numCells); g_place_qpProb->y = (float*)realloc(g_place_qpProb->y, sizeof(float)*g_place_numCells); // form a row for each cell // build data for(c = 0; c < g_place_numCells; c++) if (g_place_concreteCells[c]) { cell = g_place_concreteCells[c]; // fill in the characteristics for this cell g_place_qpProb->area[c] = getCellArea(cell); if (cell->m_fixed || cell->m_parent->m_pad) { g_place_qpProb->x[c] = cell->m_x; g_place_qpProb->y[c] = cell->m_y; g_place_qpProb->fixed[c] = 1; } else { if (!incremental) { g_place_qpProb->x[c] = g_place_coreBounds.x+g_place_coreBounds.w*0.5; g_place_qpProb->y[c] = g_place_coreBounds.y+g_place_coreBounds.h*0.5; } g_place_qpProb->fixed[c] = 0; } // update connectivity matrices last_index = nextIndex; for(n=0; nm_weight / splitPenalty(net->m_numTerms); for(t=0; tm_numTerms; t++) { c2 = net->m_terms[t]->m_id; if (c2 == c) continue; if (seen[c2] < last_index) { // not seen g_place_qpProb->connect[nextIndex-1] = c2; g_place_qpProb->edge_weight[nextIndex-1] = weight; seen[c2] = nextIndex; nextIndex++; } else { // seen g_place_qpProb->edge_weight[seen[c2]-1] += weight; } } } g_place_qpProb->connect[nextIndex-1] = -1; g_place_qpProb->edge_weight[nextIndex-1] = -1.0; nextIndex++; } else { // fill in dummy values for connectivity matrices g_place_qpProb->connect[nextIndex-1] = -1; g_place_qpProb->edge_weight[nextIndex-1] = -1.0; nextIndex++; } free(cell_numTerms); free(cell_terms); free(seen); } typedef struct reverseCOG { float x,y; Partition *part; float delta; } reverseCOG; // -------------------------------------------------------------------- // generateCoGConstraints() // /// \brief Generates center of gravity constraints. // // -------------------------------------------------------------------- int generateCoGConstraints(reverseCOG COG_rev[]) { int numConstraints = 0; // actual num constraints int cogRevNum = 0; Partition **stack = malloc(sizeof(Partition*)*g_place_numPartitions*2); int stackPtr = 0; Partition *p; float cgx, cgy; int next_index = 0, last_constraint = 0; bool isTrueConstraint = false; int i, m; float totarea; ConcreteCell *cell; // each partition may give rise to a center-of-gravity constraint stack[stackPtr] = g_place_rootPartition; while(stackPtr >= 0) { p = stack[stackPtr--]; assert(p); // traverse down the partition tree to leaf nodes-only if (!p->m_leaf) { stack[++stackPtr] = p->m_sub1; stack[++stackPtr] = p->m_sub2; } else { /* cout << "adding a COG constraint for box " << p->bounds.x << "," << p->bounds.y << " of size" << p->bounds.w << "x" << p->bounds.h << endl; */ cgx = p->m_bounds.x + p->m_bounds.w*0.5; cgy = p->m_bounds.y + p->m_bounds.h*0.5; COG_rev[cogRevNum].x = cgx; COG_rev[cogRevNum].y = cgy; COG_rev[cogRevNum].part = p; COG_rev[cogRevNum].delta = 0; cogRevNum++; } } assert(cogRevNum == g_place_numPartitions); for (i = 0; i < g_place_numPartitions; i++) { p = COG_rev[i].part; assert(p); g_place_qpProb->cog_x[numConstraints] = COG_rev[i].x; g_place_qpProb->cog_y[numConstraints] = COG_rev[i].y; totarea = 0.0; for(m=0; mm_numMembers; m++) if (p->m_members[m]) { cell = p->m_members[m]; assert(cell); if (!cell->m_fixed && !cell->m_parent->m_pad) { isTrueConstraint = true; } else { continue; } g_place_qpProb->cog_list[next_index++] = cell->m_id; totarea += getCellArea(cell); } if (totarea == 0.0) { isTrueConstraint = false; } if (isTrueConstraint) { numConstraints++; g_place_qpProb->cog_list[next_index++] = -1; last_constraint = next_index; } else { next_index = last_constraint; } } free(stack); return --numConstraints; } // -------------------------------------------------------------------- // solveQuadraticProblem() // /// \brief Calls quadratic solver. // // -------------------------------------------------------------------- void solveQuadraticProblem(bool useCOG) { int c; reverseCOG *COG_rev = malloc(sizeof(reverseCOG)*g_place_numPartitions); g_place_qpProb->cog_list = malloc(sizeof(int)*(g_place_numPartitions+g_place_numCells)); g_place_qpProb->cog_x = malloc(sizeof(float)*g_place_numPartitions); g_place_qpProb->cog_y = malloc(sizeof(float)*g_place_numPartitions); // memset(g_place_qpProb->x, 0, sizeof(float)*g_place_numCells); // memset(g_place_qpProb->y, 0, sizeof(float)*g_place_numCells); qps_init(g_place_qpProb); if (useCOG) g_place_qpProb->cog_num = generateCoGConstraints(COG_rev); else g_place_qpProb->cog_num = 0; g_place_qpProb->loop_num = 0; qps_solve(g_place_qpProb); qps_clean(g_place_qpProb); // set the positions for(c = 0; c < g_place_numCells; c++) if (g_place_concreteCells[c]) { g_place_concreteCells[c]->m_x = g_place_qpProb->x[c]; g_place_concreteCells[c]->m_y = g_place_qpProb->y[c]; } // clean up free(g_place_qpProb->cog_list); free(g_place_qpProb->cog_x); free(g_place_qpProb->cog_y); free(COG_rev); } ABC_NAMESPACE_IMPL_END