btreeanneal.cxx

Go to the documentation of this file.

/**************************************************************************
***    
*** Copyright (c) 1995-2000 Regents of the University of California,
***               Andrew E. Caldwell, Andrew B. Kahng and Igor L. Markov
*** Copyright (c) 2000-2004 Regents of the University of Michigan,
***               Saurabh N. Adya, Jarrod A. Roy and Igor L. Markov
***
***  Contact author(s): abk@cs.ucsd.edu, imarkov@umich.edu
***  Original Affiliation:   UCLA, Computer Science Department,
***                          Los Angeles, CA 90095-1596 USA
***
***  Permission is hereby granted, free of charge, to any person obtaining 
***  a copy of this software and associated documentation files (the
***  "Software"), to deal in the Software without restriction, including
***  without limitation 
***  the rights to use, copy, modify, merge, publish, distribute, sublicense, 
***  and/or sell copies of the Software, and to permit persons to whom the 
***  Software is furnished to do so, subject to the following conditions:
***
***  The above copyright notice and this permission notice shall be included
***  in all copies or substantial portions of the Software.
***
*** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
*** EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
*** OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
*** IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
*** CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT
*** OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
*** THE USE OR OTHER DEALINGS IN THE SOFTWARE.
***
***
***************************************************************************/














#include "btreeanneal.h"
#include "btreecompact.h"
#include "basepacking.h"
#include "mixedpacking.h"
#include "mixedpackingfromdb.h"
#include "pltobtree.h"

#include "debugflags.h"

// parquet data-structures, commented out in order to compile
// #include "FPcommon.h"
// #include "DB.h"
// #include "AnalytSolve.h"
// #include "CommandLine.h"
#include "allparquet.h"

#include <cmath>
#include <cfloat>
#include <algorithm>
#include <iterator>
using namespace std;

using parquetfp::Nodes;
using parquetfp::DB;
using parquetfp::Command_Line;
using parquetfp::AnalytSolve;

// ========================================================
BTreeAreaWireAnnealer::BTreeAreaWireAnnealer(
   MixedBlockInfoType& nBlockinfo)
   : BaseAnnealer(),
     _blockinfo_cleaner(NULL),
     _blockinfo(nBlockinfo),
     blockinfo(nBlockinfo),
     in_curr_solution(_blockinfo.currDimensions),
     in_next_solution(_blockinfo.currDimensions),
     in_best_solution(_blockinfo.currDimensions),
     _slackEval(NULL)
{}
// --------------------------------------------------------
BTreeAreaWireAnnealer::BTreeAreaWireAnnealer(
   MixedBlockInfoType& nBlockinfo,
   const Command_Line *const params,
   DB *const db)
   : BaseAnnealer(params, db),
     _blockinfo_cleaner(NULL),
     _blockinfo(nBlockinfo),
     blockinfo(nBlockinfo),
     in_curr_solution(_blockinfo.currDimensions),
     in_next_solution(_blockinfo.currDimensions),
     in_best_solution(_blockinfo.currDimensions),
     _slackEval(new BTreeSlackEval(in_curr_solution))
{
   constructor_core();
}
// --------------------------------------------------------
BTreeAreaWireAnnealer::BTreeAreaWireAnnealer(
   const Command_Line *const params,
   DB *const db)
   : BaseAnnealer(params, db),
     _blockinfo_cleaner(static_cast<MixedBlockInfoType*>
                        (new MixedBlockInfoTypeFromDB(*db))),
     _blockinfo(*_blockinfo_cleaner),
     blockinfo(_blockinfo),
     in_curr_solution(_blockinfo.currDimensions),
     in_next_solution(_blockinfo.currDimensions),
     in_best_solution(_blockinfo.currDimensions),
     _slackEval(new BTreeSlackEval(in_curr_solution))
{
   constructor_core();
}
// --------------------------------------------------------
void BTreeAreaWireAnnealer::constructor_core()
{
   // initialize the orientation map
   _physicalOrient.resize(in_curr_solution.NUM_BLOCKS);
   for (int i = 0; i < in_curr_solution.NUM_BLOCKS; i++)
   {      
      _physicalOrient[i].resize(blockinfo.ORIENT_NUM);
      for (int theta = 0; theta < blockinfo.ORIENT_NUM; theta++)
      {
         parquetfp::Node& currBlock = _db->getNodes()->getNode(i);
         if (currBlock.isOrientFixed())
            _physicalOrient[i][theta] = parquetfp::N;
         else
            _physicalOrient[i][theta] = parquetfp::ORIENT(theta);
      }
   }
   
   // generate an initial solution
   GenerateRandomSoln(in_curr_solution, blockinfo.currDimensions.blocknum());
   in_best_solution = in_curr_solution;
   in_next_solution = in_curr_solution;
   
   // initialize the orientations of nodes in *_db if necessary
   for (int i = 0; i < in_curr_solution.NUM_BLOCKS; i++)
   {
      int initOrient = int(in_curr_solution.tree[i].orient);
      initOrient = _physicalOrient[i][initOrient];
      
      double initWidth = in_curr_solution.width(i);
      double initHeight = in_curr_solution.height(i);
      
      _db->getNodes()->changeOrient(i, parquetfp::ORIENT(initOrient),
                                    *(_db->getNets()));
      _db->getNodes()->putNodeWidth(i, initWidth);
      _db->getNodes()->putNodeHeight(i, initHeight);
   }


   // -----debug messages-----
   for (int i = 0; i < in_curr_solution.NUM_BLOCKS; i++)
   {
      for (int theta = 0; theta < blockinfo.ORIENT_NUM; theta++)
         if ((_db->getNodes()->getNode(i)).isOrientFixed() &&
             int(in_curr_solution.tree[i].orient) != 0)
         {
            cout << "ctor: orient of block[" << i << "] should be \"n\"" << endl;
            printf("in_curr_solution:orient %d\n",
                   int(in_curr_solution.tree[i].orient));
            cin.get();
         }
      
      if (_params->minWL && (int(in_curr_solution.tree[i].orient) !=
                             int(_db->getNodes()->getNode(i).getOrient())))
      {
         cout << "ctor: orient of block[" << i << "] is not consistent" << endl;
         printf("in_curr_solution:orient %d vs. _db->orient: %d\n",
                int(in_curr_solution.tree[i].orient),
                int(_db->getNodes()->getNode(i).getOrient()));
         cin.get();
      }
      
      int theta = in_curr_solution.tree[i].orient;
      if (fabs(in_curr_solution.width(i) - blockinfo.currDimensions[i].width[theta]) > 1e-6)
      {
         printf("ctor: width of block[%d] is not consistent.  in_curr_soln: %.2f vs. blockinfo: %.2f\n",
                i, in_curr_solution.width(i), blockinfo.currDimensions[i].width[theta]);
         cin.get();
      }
      
      if (fabs(in_curr_solution.height(i) - blockinfo.currDimensions[i].height[theta]) > 1e-6)
      {
         printf("ctor: height of block[%d] is not consistent.  in_curr_soln: %.2f vs. blockinfo: %.2f\n",
                i, in_curr_solution.height(i), blockinfo.currDimensions[i].height[theta]);
         cin.get();
      }
      
      if (_params->minWL && fabs(in_curr_solution.width(i) - _db->getNodes()->getNodeWidth(i)) > 1e-6)
      {
         printf("ctor: width of block[%d] is not consistent.  in_curr_solution: %.2f vs._db: %.2f\n",
                i, in_curr_solution.width(i), _db->getNodes()->getNodeWidth(i));
         cin.get();
      }
   }
}
// --------------------------------------------------------
bool BTreeAreaWireAnnealer::go()
{      
   Timer T;
   T.stop();

   DBfromSoln(in_curr_solution);

   T.start(0.0);
   bool success = false;
   if (in_curr_solution.NUM_BLOCKS > 1)
      success = anneal();
   else
      success = packOneBlock();
   T.stop();

   annealTime += T.getUserTime();

   // update *_db for locs, dimensions and slacks
   DBfromSoln(in_curr_solution);
   in_best_solution = in_curr_solution;

   // print solutions
   SolutionInfo currSoln;
   currSoln.area = in_curr_solution.totalArea();
   currSoln.width = in_curr_solution.totalWidth();
   currSoln.height = in_curr_solution.totalHeight();
   currSoln.HPWL = _db->evalHPWL();
   printResults(T, currSoln);

   return success;
}
// --------------------------------------------------------
void BTreeAreaWireAnnealer::DBfromSoln(const BTree& soln)
{
   _db->updatePlacement(const_cast<vector<double>&>(soln.xloc()),
                        const_cast<vector<double>&>(soln.yloc()));
   for (int i = 0; i < soln.NUM_BLOCKS; i++)
   {
      parquetfp::ORIENT newOrient =
         parquetfp::ORIENT(soln.tree[i].orient);
      _db->getNodes()->changeOrient(i, newOrient, *(_db->getNets()));
      _db->getNodes()->putNodeWidth(i, soln.width(i));
      _db->getNodes()->putNodeHeight(i, soln.height(i));
   }
   
   _slackEval->evaluateSlacks(soln);

   int blocknum = soln.NUM_BLOCKS;
   vector<double> xSlacks(blocknum); // % x-slacks
   vector<double> ySlacks(blocknum); // % y-slacks
   double totalWidth = soln.totalWidth();
   double totalHeight = soln.totalHeight();
   for (int i = 0; i < blocknum; i++)
   {
      xSlacks[i] = (_slackEval->xSlack()[i] / totalWidth) * 100;
      ySlacks[i] = (_slackEval->ySlack()[i] / totalHeight) * 100;
   }      
   _db->updateSlacks(xSlacks, ySlacks);

#ifdef PARQUET_DEBUG_HAYWARD_ASSERT_BTREEANNEAL
   for (int i = 0; i < blocknum; i++)
   {
      int theta = soln.tree[i].orient;
      if (theta != _physicalOrient[i][theta])
      {
         printf("block: %d theta: %d physicalOrient: %d\n",
                i, theta, _physicalOrient[i][theta]);
         cin.get();
      }
   }   
#endif
}
// --------------------------------------------------------
bool BTreeAreaWireAnnealer::packOneBlock()
{
   const double blocksArea = in_curr_solution.blockArea();
   const double reqdAR = _params->reqdAR;
   const double reqdArea = blocksArea * (1+(_params->maxWS/100.0));
   const double reqdWidth = sqrt(reqdArea * reqdAR);
   const double reqdHeight = reqdWidth / reqdAR;
   
   const vector<double> defaultXloc(1, 0); // 1 copy of "0"
   const vector<double> defaultYloc(1, 0);
   const int defaultOrient = 0;

   cout << "Only one block is detected, deterministic algo used." << endl;
   if (_params->reqdAR != FREE_OUTLINE)
      cout << "outline width: " << reqdWidth
           << " outline height: " << reqdHeight << endl;
      
   int bestOrient = defaultOrient; 
   double bestHPWL = basepacking_h::Dimension::INFTY;
   bool success = false;
   for (int theta = 0;
        theta < basepacking_h::Dimension::ORIENT_NUM; theta++) 
   {
      in_curr_solution.rotate(0, theta);

      double blockWidth = in_curr_solution.width(0);
      double blockHeight = in_curr_solution.height(0);
      bool fitsInside = ((_params->reqdAR == FREE_OUTLINE) ||
                         ((blockWidth <= reqdWidth) &&
                          (blockHeight <= reqdHeight)));

      cout << "orient: " << theta
           << " width: " << blockWidth
           << " height: " << blockHeight
           << " inside: " << ((fitsInside)? "T" : "F");
      
      success = success || fitsInside;
      if (fitsInside && _params->minWL)
      {
         DBfromSoln(in_curr_solution);
         double currHPWL = _db->evalHPWL();
         
         cout << " HPWL: " << currHPWL;
         if (currHPWL < bestHPWL)
         {
            bestOrient = theta;
            bestHPWL = currHPWL;
         }
      }
      else if (fitsInside)
         bestOrient = theta;
      
      cout << endl;
   }

   in_curr_solution.rotate(0, bestOrient);
   DBfromSoln(in_curr_solution);

   return success;
}
// ---------------------------------------------------------
bool BTreeAreaWireAnnealer::anneal()
{
   // options
   bool budgetTime = _params->budgetTime;
   double seconds = _params->seconds;  
   bool minWL = _params->minWL;

   // input params
   double wireWeight = _params->wireWeight;
   double areaWeight = _params->areaWeight;
   double ARWeight = max(1 - areaWeight - wireWeight, 0.0);

   // input params
   double blocksArea = _db->getNodesArea();
   double size = in_curr_solution.NUM_BLOCKS;
  
   double currTime = _params->startTime;

   // if any constraint is imposed
   const double reqdAR = _params->reqdAR;
   // const double reqdArea = blocksArea * (1+((_params->maxWS-1)/100.0));
   // const double reqdWidth = sqrt(reqdArea*reqdAR);
   // const double reqdHeight = reqdWidth/reqdAR;

   // const double real_reqdAR = _params->reqdAR;
   const double real_reqdArea = blocksArea * (1+(_params->maxWS/100.0));
   const double real_reqdWidth = sqrt(real_reqdArea*reqdAR);
   const double real_reqdHeight = real_reqdWidth / reqdAR;

   // save attributes of the best solution
   // double bestArea = DBL_MAX;
   // double bestHPWL = DBL_MAX;
   
   // global counters and book-keepers
   int move = UNINITIALIZED;
   int count = 0;
   int prev_move = UNINITIALIZED;
   
   unsigned int timeChangeCtr = 0;
   unsigned int moveSelect = UNSIGNED_UNINITIALIZED;
   unsigned int iter = UNSIGNED_UNINITIALIZED;
   unsigned int masterMoveSel = 0;
   
   bool moveAccepted = false; 
   bool brokeFromLoop = false;

   double unit=0, total=seconds, percent=1;
   unsigned int moves = 2000;

   Timer looptm;
   looptm.stop();

   _db->updatePlacement(const_cast<vector<double>&>(in_curr_solution.xloc()),
                        const_cast<vector<double>&>(in_curr_solution.yloc()));
   double currHPWL = _db->evalHPWL();
   while(currTime > _params->timeCool || budgetTime)
   {
      brokeFromLoop = false;
      iter = 0;

      // ----------------------------------------
      // an iteration under the same termperature
      // ----------------------------------------
      do
      {
         // ------------------------------------
         // special treatment when time is fixed
         // ------------------------------------
         if (budgetTime)
         {
            if (count==0)
            {
               looptm.start(0.0);
            }
            else if (count==1000)
            {  
               looptm.stop();               
               unit = looptm.getUserTime() / 1000;
               if (unit == 0)
               {
                  unit = 10e-6;
               }
               seconds -= looptm.getUserTime();
               cout << int(seconds/unit) << " moves left with "
                    << (unit*1000000) <<" micro seconds per move.\n";
               moves = unsigned(seconds/unit/125);// moves every .08 degree
            }
            else if (count > 1000)
            {
               seconds -= unit;
               if (seconds <= 0)
               {
                  cout << "TimeOut" << endl;
                  return false;
               }
            }
         }
         else
         {
            if (count==0)
            {
               looptm.start(0.0);
            }
            else if (count==1000)
            {  
               looptm.stop();               
               unit = looptm.getUserTime() / 1000;
               if (unit == 0)
               {
                  unit = 10e-6;
               }
               cout << (unit * 1e6) <<" micro seconds per move." << endl;
            }
         }         
         // finish treating time if necessary 

         // -----------------------
         // select and apply a move
         // -----------------------
         
         // current solution, "currHPWL" updated only when necessary
         double currArea = in_curr_solution.totalArea();
         double currHeight = in_curr_solution.totalHeight();
         double currWidth = in_curr_solution.totalWidth();
         double currAR = currWidth / currHeight;

         ++count; 
         ++iter;
         prev_move = move;

         // -----select the types of moves here-----
         if (_params->softBlocks && currTime < 50)
            masterMoveSel = rand() % 1000;
         moveSelect = rand() % 1000;

         // -----take action-----
         int indexOrient = UNSIGNED_UNINITIALIZED;
         parquetfp::ORIENT newOrient = parquetfp::N;
         parquetfp::ORIENT oldOrient = parquetfp::N;

         int index = UNINITIALIZED;
         double newWidth = UNINITIALIZED;
         double newHeight = UNINITIALIZED;

         if(_params->softBlocks && masterMoveSel == 1)
            move = packSoftBlocks(2); // needs its return-value (-1)!!!

         else if(_params->softBlocks && masterMoveSel > 950)
            move = makeSoftBlMove(index, newWidth, newHeight);
         
         else if (((reqdAR-currAR)/reqdAR > 0.00005 || 
                   (currAR-reqdAR)/reqdAR > 0.00005) && 
                  (timeChangeCtr % 4) == 0 && reqdAR != FREE_OUTLINE)
         {            
            move = makeMove(indexOrient, newOrient, oldOrient);
            // move = makeARMove();
         }

         else if (false && !minWL &&
                  currTime < 30 && (timeChangeCtr % 5) == 0)
            move = compactBlocks();
         
         else if (moveSelect < 150)
         {
            if (reqdAR != FREE_OUTLINE)
               move = makeARMove();
            else 
               move = makeMove(indexOrient, newOrient, oldOrient);
         }
         
         else if (moveSelect < 300 && minWL)
         {
            if (reqdAR != FREE_OUTLINE)
               move = makeARWLMove();
            else
               move = makeHPWLMove();
         }
         
         else
            move = makeMove(indexOrient, newOrient, oldOrient);

         // -----additional book-keeping for special moves-----
         // for orientation moves
         if (move == REP_SPEC_ORIENT || move == ORIENT)
         {
            // temp values
            if (minWL)
            {
               _db->getNodes()->changeOrient(indexOrient, newOrient,
                                             *(_db->getNets()));
            }
         }

         // for soft-block moves
         if (move == SOFT_BL)
         {
            int indexTheta = in_curr_solution.tree[index].orient;
            _blockinfo.setBlockDimensions(index,
                                          newWidth, newHeight, indexTheta);
            in_next_solution.evaluate(in_curr_solution.tree);

            if (minWL)
            {
               _db->getNodes()->putNodeWidth(index, newWidth);
               _db->getNodes()->putNodeHeight(index, newHeight);
            }
         }            

         // attributes of "in_next_solution"
         double tempHeight = in_next_solution.totalHeight(); 
         double tempWidth = in_next_solution.totalWidth();  
         double tempArea = in_next_solution.totalArea();
         double tempAR = tempWidth / tempHeight;
         double tempHPWL = UNINITIALIZED;

         // -----------------------------------------------------
         // evaulate the temporary solution and calculate "delta"
         // -----------------------------------------------------
         
         double deltaArea = 0;
         double deltaHPWL = 0;  
         double deltaAR = UNINITIALIZED;
         double delta = UNINITIALIZED;
 
         /* area objective */
         if (currTime > 30)
            deltaArea = ((tempArea-currArea)*1.2*_params->timeInit) / blocksArea;
         else
            deltaArea = ((tempArea-currArea)*1.5*_params->timeInit) / blocksArea;
         
         /* HPWL objective if applicable */ 
         if (minWL)
         {
            _db->updatePlacement(const_cast<vector<double>&>(in_next_solution.xloc()),
                                 const_cast<vector<double>&>(in_next_solution.yloc()));
            
            tempHPWL = _db->evalHPWL();
            if(currHPWL == 0)
              deltaHPWL = 0;
            else
            {
              if(currTime>30)
               deltaHPWL = ((tempHPWL-currHPWL)*1.2*_params->timeInit)/currHPWL; // 1.2
              else
               deltaHPWL = ((tempHPWL-currHPWL)*1.5*_params->timeInit)/currHPWL; // 1.5 
            }
         }
         
         /* AR and overall objective */
         delta = deltaArea;
         if(reqdAR != FREE_OUTLINE)
         {            
            deltaAR = ((tempAR - reqdAR)*(tempAR - reqdAR) -
                       (currAR - reqdAR)*(currAR - reqdAR)) * 20 * _params->timeInit; // 10 // 1.2
            
            if(minWL)
               delta = (areaWeight * deltaArea +
                        wireWeight * deltaHPWL +
                        ARWeight * deltaAR);
            else
               delta = ((areaWeight + wireWeight/2.0) * deltaArea + 
                        (ARWeight + wireWeight/2.0) * deltaAR);
            
         }
         else if(minWL)
         {
            delta = ((areaWeight + ARWeight/2.0)*deltaArea + 
                     (wireWeight + ARWeight/2.0)*deltaHPWL);
         }
         else
            delta = deltaArea;
         // finish calculating "delta"        

         // --------------------------------------------------
         // decide whether a move is accepted based on "delta"
         // --------------------------------------------------
         
         if (delta < 0 || move == MISC)
            moveAccepted = true;         
         else if (currTime > _params->timeCool) 
            // become greedy below time > timeCool
         {
            double ran = rand() % 10000;
            double r = double(ran) / 9999;
            if (r < exp(-1*delta/currTime))
               moveAccepted = true;
            else
               moveAccepted = false;
         }
         else
            moveAccepted = false;

         // -----update current solution if accept-----
         if (moveAccepted && move != MISC)
         {
            in_curr_solution = in_next_solution;
            currHPWL = tempHPWL;
         }

         // -----additional book-keeping for special moves-----
         if (move == REP_SPEC_ORIENT || move == ORIENT)
         {
            // if move not accepted, then put back "oldOrient"
            parquetfp::ORIENT actualOrient =
               parquetfp::ORIENT(in_curr_solution.tree[indexOrient].orient);
            
            if (minWL)
               _db->getNodes()->changeOrient(indexOrient, actualOrient,
                                             *(_db->getNets()));
         }

         if (move == SOFT_BL)
         {
            // if move not accepted, then put back "oldWidth/Height"
            double actualWidth = in_curr_solution.width(index);
            double actualHeight = in_curr_solution.height(index);
            int actualTheta = in_curr_solution.tree[index].orient;
            _blockinfo.setBlockDimensions(index,
                                          actualWidth, actualHeight,
                                          actualTheta);
            
            if (minWL)
            {
               _db->getNodes()->putNodeWidth(index, actualWidth);
               _db->getNodes()->putNodeHeight(index, actualHeight);
            }
         }

//          // update in_best_solution if necessary (doesn't make much diff.)
//          bool updateBest = false;
//          if (_params->reqdAR != FREE_OUTLINE)
//          {
//             if (minWL)
//             {
//                updateBest = (currWidth <= real_reqdWidth &&
//                              currHeight <= real_reqdHeight &&
//                              currHPWL < bestHPWL);
//             }
//             else
//             {
//                updateBest = (currWidth <= real_reqdWidth &&
//                              currHeight <= real_reqdHeight &&
//                              currArea < bestArea);
//             }
//          }
//          else if (minWL)
//          {
//             double currCost =
//                areaWeight * currArea + wireWeight * currHPWL;
//             double bestCost =
//                areaWeight * bestArea + wireWeight * bestHPWL;

//             updateBest = (currCost < bestCost);
//          }
//          else
//             updateBest = (currArea < bestArea);

//          if (updateBest)
//             in_best_solution = in_curr_solution;

         // ------------------------------
         // special terminating conditions
         // ------------------------------
         
         if (minWL/* && _params->startTime > 100*/)//for lowT anneal don't have this condition
         {
            // hhchan TODO:  clean-up this code mess 
            if(currArea <= real_reqdArea && currHeight <= real_reqdHeight && 
               currWidth <= real_reqdWidth && reqdAR != FREE_OUTLINE && currTime < 5)
               return true;

            if (reqdAR != FREE_OUTLINE && currTime < 5 && 
                _params->dontClusterMacros && _params->solveTop)
            {
               double widthWMacroOnly = _db->getXSizeWMacroOnly();
               double heightWMacroOnly = _db->getYSizeWMacroOnly();

               if (widthWMacroOnly <= real_reqdWidth &&
                   heightWMacroOnly <= real_reqdHeight)
                  return true;
            }
         }
         else
         {
            if(currArea <= real_reqdArea && currHeight <= real_reqdHeight && 
               currWidth <= real_reqdWidth && reqdAR != FREE_OUTLINE)
               return true;
         }
          
         if (iter >= moves)
            break;

#ifdef PARQUET_DEBUG_HAYWARD_ASSERT_BTREEANNEAL
         // -----debugging messages-----
         for (int i = 0; i < in_curr_solution.NUM_BLOCKS; i++)
         {
            if (minWL && (int(in_curr_solution.tree[i].orient) !=
                          int(_db->getNodes()->getNode(i).getOrient())))
            {
               cout << "round [" << count << "]: orient of block[" << i << "] is not consistent" << endl;
               printf("in_curr_solution:orient %d vs. _db->orient: %d, move: %d",
                      int(in_curr_solution.tree[i].orient),
                      int(_db->getNodes()->getNode(i).getOrient()), move);
               cin.get();
            }

            int theta = in_curr_solution.tree[i].orient;
            if (theta != int(_physicalOrient[i][theta]))
            {
               printf("round[%d]: orient of block[%d] is not consistent, in_curr_soln: %d vs phyOrient: %d move: %d\n",
                      count, i, theta, _physicalOrient[i][theta], move);
               cin.get();
            }
            
            if (fabs(in_curr_solution.width(i) - blockinfo.currDimensions[i].width[theta]) > 1e-6)
            {
               printf("round[%d]: width of block[%d] is not consistent.  in_curr_soln: %.2f vs. blockinfo: %.2f move: %d prevMove: %d\n",
                      count, i, in_curr_solution.width(i), blockinfo.currDimensions[i].width[theta], move, prev_move);
               printf("round[%d]: oldWidth: %.2f oldHeight: %.2f newWidth: %.2f newHeight: %.2f moveAccepted: %s\n",
                      count, -1.0, -1.0, newWidth, newHeight, (moveAccepted)? "T" : "F");
               cin.get();
            }

            if (fabs(in_curr_solution.height(i) - blockinfo.currDimensions[i].height[theta]) > 1e-6)
            {
               printf("round[%d]: height of block[%d] is not consistent.  in_curr_soln: %.2f vs. blockinfo: %.2f move: %d prevMove: %d\n",
                      count, i, in_curr_solution.height(i), blockinfo.currDimensions[i].height[theta], move, prev_move);
               printf("round[%d]: oldWidth: %.2f oldHeight: %.2f newWidth: %.2f newHeight: %.2f moveAccepted: %s\n",
                      count, -1.0, -1.0, newWidth, newHeight, (moveAccepted)? "T" : "F");
               cin.get();
            }

            if (minWL && fabs(in_curr_solution.width(i) - _db->getNodes()->getNodeWidth(i)) > 1e-6)
            {
               printf("round[%d]: width of block[%d] is not consistent.  in_curr_solution: %.2f vs._db: %.2f move: %d\n",
                      count, i, in_curr_solution.width(i), _db->getNodes()->getNodeWidth(i), move);
               cin.get();
            }

            if (in_curr_solution.width(i) < 1e-10 ||
                in_curr_solution.height(i) < 1e-10)
            {
               printf("round[%d]: width of block[%d]: %f height: %f move: %d\n",
                      count, i, in_curr_solution.width(i), in_curr_solution.height(i), move);
               cin.get();
            }
         }
         // -----end of debugging messages-----
#endif         
      }
      while (iter < 4*size || budgetTime);
      // finish the loop under constant temperature

      // -----------------------------
      // update temperature "currTime"
      // -----------------------------
      
      double alpha = UNINITIALIZED;
      ++timeChangeCtr;
      if (budgetTime)
      {
         percent = seconds/total;
        
         if (percent < 0.66666 && percent > 0.33333)
            alpha = 0.9;
         else if (percent < 0.33333 && percent > 0.16666)
            alpha = 0.95;
         else if (percent < 0.16666 && percent > 0.06666)
            alpha = 0.96;
         else if(percent <.06666 && percent >.00333)
            alpha = 0.8;
         else if(percent <.00333 && percent >.00003)
            alpha = 0.98;
         else
            alpha = 0.85;
      }
      else
      {
         if (currTime < 2000 && currTime > 1000)
            alpha = 0.9;
         else if (currTime < 1000 && currTime > 500)
            alpha = 0.95;
         else if (currTime < 500 && currTime > 200)
            alpha = 0.96;
         else if (currTime < 200 && currTime > 10)
            alpha = 0.96;
         else if (currTime < 15 && currTime > 0.1)
            alpha = 0.98;
         else
            alpha = 0.85;
      }
      currTime *= alpha;
      
      if (brokeFromLoop)
         break;
   }

   cout << "NumMoves attempted: " << count << endl;
   if (reqdAR != FREE_OUTLINE)
      return false;
   else
      return true;
}
// --------------------------------------------------------
void BTreeAreaWireAnnealer::takePlfromDB()
{
   Pl2BTree converter(_db->getXLocs(),
                      _db->getYLocs(),
                      _db->getNodeWidths(),
                      _db->getNodeHeights(),
                      Pl2BTree::TCG);
   in_curr_solution.evaluate(converter.btree());
   in_next_solution = in_curr_solution;
}
// --------------------------------------------------------
void BTreeAreaWireAnnealer::compactSoln()
{
   BTreeCompactor compactor(in_curr_solution);

   int round = 0;
   int numBlkChange = compactor.compact();
   double lastArea = in_curr_solution.totalArea();
   double currArea = compactor.totalArea();
   while (numBlkChange > 0)
   {
      printf("round[%d] %d blks moved, area: %.2f -> %.2f\n",
             round, numBlkChange, lastArea, currArea);

      numBlkChange = compactor.compact();
      round++;
      lastArea = currArea;
      currArea = compactor.totalArea();
   }
   printf("round[%d] %d blks moved, area: %.2f -> %.2f\n",
          round, numBlkChange, lastArea, currArea);

   in_curr_solution = compactor;
   DBfromSoln(in_curr_solution);
}
// --------------------------------------------------------
int BTreeAreaWireAnnealer::makeMove(int& indexOrient,
                                    parquetfp::ORIENT& newOrient,
                                    parquetfp::ORIENT& oldOrient)
{
   BTree::MoveType move = get_move();
   indexOrient = UNSIGNED_UNINITIALIZED;
   newOrient = parquetfp::N;
   oldOrient = parquetfp::N;
   switch(move)
   {
   case BTree::SWAP:
      perform_swap();
      return 1;

   case BTree::ROTATE:
      perform_rotate(indexOrient, newOrient, oldOrient);
      return int(REP_SPEC_ORIENT);

   case BTree::MOVE:
      perform_move();
      return 3;

   default:
      cout << "ERROR: invalid move specified in makeMove()" << endl;
      exit(1);
   }
   return MISC;
}
// --------------------------------------------------------
int BTreeAreaWireAnnealer::makeMoveSlacks()
{
   int movedir = rand() % 100;
   int threshold = 50;
   bool horizontal = (movedir < threshold);

   makeMoveSlacksCore(horizontal);

   static int total = 0;
   static int numHoriz = 0;

   total++;
   numHoriz += ((horizontal)? 1 : 0);

   if (total % 1000 == 0)
      cout << "total: " << total << "horiz: " << numHoriz << endl;
   return SLACKS_MOVE;
}
// --------------------------------------------------------
int BTreeAreaWireAnnealer::makeARMove()
{
   double currWidth = in_curr_solution.totalWidth();
   double currHeight = in_curr_solution.totalHeight();
   double currAR = currWidth / currHeight;

   const double reqdAR = _params->reqdAR;
   bool horizontal = currAR > reqdAR;

   makeMoveSlacksCore(horizontal);
   return AR_MOVE;
}
// --------------------------------------------------------
void BTreeAreaWireAnnealer::makeMoveSlacksCore(bool horizontal)
{
   _slackEval->evaluateSlacks(in_curr_solution);
   
   vector<int> indices_sorted;
   const vector<double>& slacks = (horizontal)?
      _slackEval->xSlack() : _slackEval->ySlack();
   
   sort_slacks(slacks, indices_sorted);

   int blocknum = in_curr_solution.NUM_BLOCKS;
   int range = int(ceil(blocknum / 5.0));
   
   int operand_ptr = rand() % range;
   int operand = indices_sorted[operand_ptr];
   while (operand_ptr > 0 && slacks[operand] > 0)
   {
      operand_ptr--;
      operand = indices_sorted[operand_ptr];
   }
   
   int target_ptr = blocknum - 1 - (rand() % range);
   int target = indices_sorted[target_ptr];
   while (target_ptr < (blocknum-1) && slacks[target] == 0)
   {
      target_ptr++;
      target = indices_sorted[target_ptr];
   }

   in_next_solution = in_curr_solution;
   in_next_solution.move(operand, target, horizontal);
}
// --------------------------------------------------------
int BTreeAreaWireAnnealer::makeHPWLMove()
{
   int size = in_curr_solution.NUM_BLOCKS;
   int operand = rand() % size;
   int target = UNSIGNED_UNINITIALIZED;

   vector<int> searchBlocks;
   locateSearchBlocks(operand, searchBlocks);
   
   if (searchBlocks.size() > 0)
   {
      int temp = rand() % searchBlocks.size();
      target = searchBlocks[temp];
   }
   else
   {
      do
         target = rand() % size;
      while(target == operand);
   }

   bool leftChild = bool(rand() % 2);
   in_next_solution = in_curr_solution;
   in_next_solution.move(operand, target, leftChild);
   return HPWL;
}
// --------------------------------------------------------
int BTreeAreaWireAnnealer::makeARWLMove()
{
   _slackEval->evaluateSlacks(in_curr_solution);

   const double reqdAR = _params->reqdAR;
   const double currAR =
      in_curr_solution.totalWidth() / in_curr_solution.totalHeight();
   const bool horizontal = currAR > reqdAR;
   const vector<double>& slacks = (horizontal)?
      _slackEval->xSlack() : _slackEval->ySlack(); 
   
   vector<int> indices_sorted;
   sort_slacks(slacks, indices_sorted);
   
   int blocknum = in_curr_solution.NUM_BLOCKS;
   int range = int(ceil(blocknum / 5.0));
   
   int operand_ptr = rand() % range;
   int operand = indices_sorted[operand_ptr];
   while (operand_ptr > 0 && slacks[operand] > 0)
   {
      operand_ptr--;
      operand = indices_sorted[operand_ptr];
   }

   vector<int> searchBlocks;
   locateSearchBlocks(operand, searchBlocks);

   int target = UNSIGNED_UNINITIALIZED;
   double maxSlack = -1;
   if (searchBlocks.size() == 0)
   {
      do
         target = rand() % blocknum;
      while(target == operand);
   }
   else
   {
      for (unsigned int i = 0; i < searchBlocks.size(); i++)
      {
         int thisBlk = searchBlocks[i];
         if (slacks[thisBlk] > maxSlack)
         {
            maxSlack = slacks[thisBlk];
            target = thisBlk;
         }
      }
   }

   in_next_solution = in_curr_solution;
   in_curr_solution.move(operand, target, horizontal);
   return ARWL; 
}
// --------------------------------------------------------
int BTreeAreaWireAnnealer::makeSoftBlMove(int& index,
                                          double& newWidth,
                                          double& newHeight)
{
   static const int NOT_FOUND = NOT_FOUND;
   _slackEval->evaluateSlacks(in_curr_solution);
   
   int moveDir = rand() % 2;
   bool horizontal = (moveDir%2 == 0);
   index = getSoftBlIndex(horizontal);

   if (index == NOT_FOUND)
      index = getSoftBlIndex(!horizontal);

   if (index != NOT_FOUND)
   {
      return getSoftBlNewDimensions(index, newWidth, newHeight);
   }
   else
   {
      newWidth = NOT_FOUND;
      newHeight = NOT_FOUND;
      return MISC;
   }
}
// --------------------------------------------------------
int BTreeAreaWireAnnealer::getSoftBlIndex(bool horizontal) const
{
   static const int NOT_FOUND = NOT_FOUND;
   const int blocknum = in_curr_solution.NUM_BLOCKS;
   const vector<double>& slacks = (horizontal)?
      _slackEval->xSlack() : _slackEval->ySlack();

   const vector<double>& orth_slacks = (horizontal)?
      _slackEval->ySlack() : _slackEval->xSlack();

   vector<int> indices_sorted;
   sort_slacks(slacks, indices_sorted);

   int operand = NOT_FOUND; // "-1" stands for not found
   for (int i = 0; (i < blocknum) && (operand == NOT_FOUND); i++)
   {
      int index = indices_sorted[i];
      if (blockinfo.blockARinfo[index].isSoft)
      {
         int theta = in_curr_solution.tree[index].orient;
         double minAR = blockinfo.blockARinfo[index].minAR[theta];
         double maxAR = blockinfo.blockARinfo[index].maxAR[theta];
         
         double currWidth = in_curr_solution.width(index);
         double currHeight = in_curr_solution.height(index);
         double currAR = currWidth / currHeight;

         bool adjustable = (horizontal)?
            (currAR > minAR) : (currAR < maxAR);

         if (orth_slacks[index] > 0 && adjustable)
            operand = index;
      }
   }
   return operand;
}   
// --------------------------------------------------------
int BTreeAreaWireAnnealer::getSoftBlNewDimensions(int index,
                                                  double& newWidth,
                                                  double& newHeight) const
{
   if (blockinfo.blockARinfo[index].isSoft)
   {
      double origWidth = in_curr_solution.width(index);
      double origHeight = in_curr_solution.height(index);
      double indexArea = blockinfo.blockARinfo[index].area;
      
      int theta = in_curr_solution.tree[index].orient;
      double minAR = blockinfo.blockARinfo[index].minAR[theta];
      double maxAR = blockinfo.blockARinfo[index].maxAR[theta];
      
      double maxWidth = sqrt(indexArea * maxAR);
      double maxHeight = sqrt(indexArea / minAR);
      
      double indexSlackX = _slackEval->xSlack()[index];
      double indexSlackY = _slackEval->ySlack()[index];
      if (indexSlackX > indexSlackY)
      {
         newWidth = min(origWidth+indexSlackX, maxWidth);
         newHeight = indexArea / newWidth;
      }
      else
      {
         newHeight = min(origHeight+indexSlackY, maxHeight);
         newWidth = indexArea / newHeight;
      }
      return SOFT_BL;
   }
   else
      return NOOP;
}
// --------------------------------------------------------
int BTreeAreaWireAnnealer::packSoftBlocks(int numIter)
{
   const int NUM_BLOCKS = in_curr_solution.NUM_BLOCKS;
   for (int iter = 0; iter < numIter; iter++)
   {
      bool horizontal = (iter % 2 == 0);
      _slackEval->evaluateSlacks(in_curr_solution);

      const vector<double>& slacks = (horizontal)?
         _slackEval->xSlack() : _slackEval->ySlack();

      vector<int> indices_sorted;
      sort_slacks(slacks, indices_sorted);
      for (int i = 0; i < NUM_BLOCKS; i++)
      {
         int index = indices_sorted[i];
         double origWidth = in_curr_solution.width(index);
         double origHeight = in_curr_solution.height(index);

         double newWidth, newHeight;
         int softDecision = makeIndexSoftBlMove(index, newWidth, newHeight);

         if (softDecision == SOFT_BL)
         {
            // change dimensions only when needed
            int theta = in_curr_solution.tree[index].orient;
            _blockinfo.setBlockDimensions(index, newWidth, newHeight, theta);

            in_next_solution.evaluate(in_curr_solution.tree);

            double origTotalArea = in_curr_solution.totalArea();
            double newTotalArea = in_next_solution.totalArea();
            if (newTotalArea < origTotalArea)
            {
               in_curr_solution = in_next_solution;
               if (_params->minWL)
               {
                  _db->getNodes()->putNodeWidth(index, newWidth);
                  _db->getNodes()->putNodeHeight(index, newHeight);
               }
            }
            else
            {
               _blockinfo.setBlockDimensions(index, origWidth, origHeight, theta);
            }
         }
      }
   }
   return MISC;
}
// --------------------------------------------------------
void BTreeAreaWireAnnealer::locateSearchBlocks(int operand,
                                               vector<int>& searchBlocks)
{
   int size = in_curr_solution.NUM_BLOCKS;
   vector<bool> seenBlocks(size, false);
   seenBlocks[operand] = true;
   double unitRadiusSize = max(in_curr_solution.totalWidth(),
                               in_curr_solution.totalHeight());
   unitRadiusSize /= sqrt(double(size));

   vector<double>& xloc = const_cast<vector<double>&>(in_curr_solution.xloc());
   vector<double>& yloc = const_cast<vector<double>&>(in_curr_solution.yloc());
   parquetfp::Point idealLoc(_analSolve->getOptLoc(operand, xloc, yloc));
   // get optimum location of "operand"

   int searchRadiusNum = int(ceil(size / 5.0));
   double searchRadius = 0;
   for(int i = 0; ((i < searchRadiusNum) &&
                   (searchBlocks.size() < unsigned(searchRadiusNum))); ++i)
   {
      searchRadius += unitRadiusSize;
      for(int j = 0; ((j < size) &&
                      (searchBlocks.size() < unsigned(searchRadiusNum))); ++j)
      {
         if (!seenBlocks[j])
         {
            double xDist = xloc[j] - idealLoc.x;
            double yDist = yloc[j] - idealLoc.y;
            double distance = sqrt(xDist*xDist + yDist*yDist);
            if(distance < searchRadius)
            {
               seenBlocks[j] = true; 
               searchBlocks.push_back(j);
            }
         }
      }
   }
}
// --------------------------------------------------------
void BTreeAreaWireAnnealer::GenerateRandomSoln(BTree& soln,
                                               int blocknum) const
{
   vector<int> tree_bits;
   int balance = 0;
   int num_zeros = 0;
   for (int i = 0; i < 2*blocknum; i++)
   {
      bool assigned = false;
      double rand_num = double(rand()) / (RAND_MAX+1.0);
      double threshold;

      if (balance == 0)
         threshold = 1; // push_back "0" for sure
      else if (num_zeros == blocknum) 
         threshold = 0; // push_back "1" for sure
      else
         threshold = 1; // (rand_num * (balance - rand_num));
         
      if (rand_num >= threshold)
      {
         tree_bits.push_back(1);
         balance--;
         assigned = true;
      }
      else
      {
         tree_bits.push_back(0);
         balance++;
         num_zeros++;
         assigned = true;
      }
   }
   
   vector<int> tree_perm;
   tree_perm.resize(blocknum);
   for (int i = 0; i < blocknum; i++)
      tree_perm[i] = i;
   random_shuffle(tree_perm.begin(), tree_perm.end());

   vector<int> tree_perm_inverse(blocknum);
   for (int i = 0; i < blocknum; i++)
      tree_perm_inverse[tree_perm[i]] = i;

   vector<int> tree_orient(blocknum);
   for (int i = 0; i < blocknum; i++)
   {
      int rand_num = int(8 * (double(rand()) / (RAND_MAX + 1.0)));
      rand_num = _physicalOrient[i][rand_num];

      tree_orient[tree_perm_inverse[i]] = rand_num;
   }

   soln.evaluate(tree_bits, tree_perm, tree_orient);
}
// --------------------------------------------------------

---