asg/n2a.c

   1 /************************************************************
   2 **
   3 **       COPYRIGHT (C) 1993 UNIVERSITY OF PITTSBURGH
   4 **       COPYRIGHT (C) 1996 GANNON UNIVERSITY
   5 **                  ALL RIGHTS RESERVED
   6 **
   7 **        This software is distributed on an as-is basis
   8 **        with no warranty implied or intended.  No author
   9 **        or distributor takes responsibility to anyone
  10 **        regarding its use of or suitability.
  11 **
  12 **        The software may be distributed and modified
  13 **        freely for academic and other non-commercial
  14 **        use but may NOT be utilized or included in whole
  15 **        or part within any commercial product.
  16 **
  17 **        This copyright notice must remain on all copies
  18 **        and modified versions of this software.
  19 **
  20 ************************************************************/
  21
  22
  23 /* file n2a.c */
  24 /* ------------------------------------------------------------------------
  25  * main file manipulation routines                         spl 7/89
  26  *
  27  * ------------------------------------------------------------------------
  28  */
  29
  30 #include <stdio.h>
  31 #include <ctype.h>
  32 #include <string.h>
  33 #include <sys/time.h>
  34 #include <sys/resource.h>
  35
  36 /*---------------------------------------------------------------
  37  * External functions
  38  *---------------------------------------------------------------
  39  */
  40
  41 #include "externs.h"
  42
  43 /*---------------------------------------------------------------
  44  * Global Variable Definitions
  45  *---------------------------------------------------------------
  46  */
  47
  48 mlist *modules;         /* M the set of all modules */
  49 nlist *nets;            /* N the set of all nets */
  50 tlist *ext_terms;       /* ST the set of all system terminals */
  51 mlist *ext_mods;        /* the modules associated with each element of ST */
  52
  53 /* NOT USED*/
  54 tlist *int_terms;       /* T the set of all inter-module terminals */
  55
  56 /* FOR THE ROUTER (only) */
  57 int currentPartition;
  58 tile **routingRoot[2];
  59
  60 /* NOT USED ENOUGH */
  61 int lcount = 0;                    /* number of input lines read */
  62 int module_count = 0;              /* number of modules/objects read in */
  63 int node_count = 0;                /* number of nodes/signals read in */
  64 int terminal_count = 0;            /* number of terminals read in */
  65 int connected[MAX_MOD][MAX_MOD];   /* BIG array of connection counts */
  66 info_type module_info[MAX_MOD];/* re-used array of inter module connections */
  67 float partition_ratio=DEF_PARTITION_RATIO;      /* -r qualifier, used for clustering */
  68 /* command-line parameters: */
  69 int compute_aspect_ratios = FALSE;              /* -a flag, in parsing - compute aspect ratios*/
  70 int Xcanvas_scaling = FALSE;                    /* -b flag (use XCanvas scaling) */
  71 int max_partition_conn =  MAX_PARTITION_CONN;   /* -c qualifier, used for clustering */
  72 int debug_level = 11;                           /* -d qualifier, sets the debug level */
  73 int stopAtFirstCut = FALSE;                     /* -f flag; terminates GR early */
  74 int congestion_rule = 2;                        /* -g qualifier, used for conGestion */
  75 int do_hand_placement = FALSE;                  /* -h flag */
  76 int includeSysterms = FALSE;                    /* -i flag; excludes system terminals */
  77
  78 int cc_search_level = CC_SEARCH_LEVEL;          /* -l qualifier, limits cc search */
  79 int matrix_type = UNSIGNED;                     /* -m qualifier, sets signal-flow style*/
  80 int do_routing = TRUE;                          /* -n qualifier, inhibits routing */
  81 FILE *outputFile;                               /* -o qualifier, opens an Output file */
  82 int partition_rule =  DEF_PARTITION_RULE;       /* -p qualifier, used for clustering */
  83 int recordStats = FALSE;                        /* -q flag; quality stats collection on*/
  84 int max_partition_size =  MAX_PARTITION_SIZE;   /* -s qualifier, used for clustering */
  85 int turn_mode = TIGHT;                          /* Used to choose the cornering alg */
  86 int useSlivering = TRUE;                        /* -v flag; removes sliVer corrections */
  87 int useAveraging = FALSE;                       /* -w flag; turns Weighted averaging on*/
  88 int latex = FALSE;                              /* -x flag; modified PostScript header */
  89 int recordTiming = FALSE;                       /* -y flag; turns time collection on */
  90 int xcircuit= TRUE;                             /* -z flag;to launch spar into xcircuit*/
  91 FILE *stats;                                    /* quality statistics file */
  92
  93 /* NOT USED MUCH */
  94 mlist **boxes;          /* the sets of boxes */
  95 mlist **strings;        /* the set of strings */
  96 ctree **parti_stats;    /* partition statistics */
  97 int *str_length;        /* the length of each string */
  98 int *str_height;        /* the height of each string */
  99 int *x_sizes;           /* the max x size of each partition */
 100 int *y_sizes;           /* the max y size of each partition */
 101 int *x_positions;       /* and their postions, after placement */
 102 int *y_positions;
 103 int xfloor, yfloor;     /* the origin for the current partition */
 104
 105 mlist **partitions;     /* the set of PARTITIONS (lists) of modules */
 106 tile **rootTiles;       /* The tile spaces that correspond to the partitions */
 107 int partition_count;    /* the total number of partitions created */
 108
 109 #define USEC 1000000
 110
 111 /*--------------------------------------------------------------*/
 112 /* record the time, and mark it in the <timingFile>:            */
 113 /*--------------------------------------------------------------*/
 114
 115 mark_time(tf, name, dTime)
 116     FILE *tf;
 117     char *name;
 118     long *dTime;
 119 {
 120     double t;
 121     int cTime, maxMemory = 0;
 122     struct rusage ru;
 123
 124     getrusage(RUSAGE_SELF, &ru);
 125     cTime = USEC * ru.ru_utime.tv_sec + ru.ru_utime.tv_usec;
 126     maxMemory = MAX(ru.ru_maxrss, maxMemory);
 127     t = (double)(cTime - *dTime)/(double)USEC;
 128     *dTime = cTime;
 129
 130     fprintf(tf, "%s time = %f, time elapsed = %f\n",
 131             name, t, (double)cTime/(double)USEC);
 132 }
 133
 134 /*------------------------------------------------------------------*/
 135 /* Given a list of modules, count the number of terminals contained */
 136 /*------------------------------------------------------------------*/
 137
 138 int count_terminals(mods)
 139     mlist *mods;
 140 {
 141     int c = 0;
 142     mlist *ml;
 143     for (ml = mods; ml != NULL; ml = ml->next)
 144         c += list_length(ml->this->terms);
 145     return(c);
 146 }
 147
 148 /*-------------------------------------------------------------------*/
 149 /*-------------------------------------------------------------------*/
 150
 151 int allocate_globals(p)
 152     int p;                      /* Number of partitions */
 153 {
 154     x_sizes = (int *)calloc((p+1), sizeof(int));
 155     y_sizes = (int *)calloc((p+1), sizeof(int));
 156     x_positions = (int *)calloc((p+1), sizeof(int));
 157     y_positions = (int *)calloc((p+1), sizeof(int));
 158     partitions = (mlist **)calloc((p+3), sizeof(mlist *));
 159     rootTiles = (tile **)calloc((p+1), sizeof(tile *));
 160 }
 161
 162 /*-------------------------------------------------------------------*/
 163 /*-------------------------------------------------------------------*/
 164
 165 int separate_systerms(intModules, sysModules, sysNets)
 166     mlist **intModules, **sysModules;
 167     nlist **sysNets;
 168 {
 169     mlist *ml, *sysMods = NULL;
 170
 171     /* First, Do some of the background work done in "place.c" */
 172     allocate_globals(currentPartition);
 173     partitions[0] = partitions[1] = partitions[2] = NULL;
 174
 175     for (ml = modules; ml != NULL; ml = ml->next) {
 176         if ((!strcmp(ml->this->type, INOUT_TERM)) ||
 177                 (!strcmp(ml->this->type, INPUT_TERM))) {
 178             push(ml->this, sysModules);
 179             push(ml->this, &partitions[2]);
 180         }
 181         else if (!strcmp(ml->this->type, OUTPUT_TERM)) {
 182             push(ml->this, sysModules);
 183             push(ml->this, &partitions[1]);
 184         }
 185         else push(ml->this, intModules);
 186     }
 187     partitions[0] = *intModules;
 188
 189
 190     for (ml = *sysModules; ml != NULL; ml = ml->next) {
 191         /* Collect the nets that connect to the system terminals: */
 192         /* Assume there is only one terminal for each system terminal: */
 193         push(ml->this->terms->this->nt, sysNets);
 194     }
 195 }
 196
 197 /*--------------------------------------------------------------*/
 198 /* Routine to set the debug level from an external routine.     */
 199 /*--------------------------------------------------------------*/
 200
 201 int SetDebugLevel(int *level)
 202 {
 203     if (level != NULL)
 204        debug_level = *level;
 205     return debug_level;
 206 }
 207
 208 /*--------------------------------------------------------------*/
 209 /* Route --                                                     */
 210 /*                                                              */
 211 /* This method is used to route all the modules....             */
 212 /*--------------------------------------------------------------*/
 213
 214 void Route(XCWindowData *areastruct, Boolean bIsSparmode)
 215 {
 216     FILE *timingFile;
 217     int c,  errflg = 0, x1, y1, x2, y2;
 218     nlist *nl = NULL, *systermNets = NULL;
 219     mlist *modulesJustPlaced, *ml;
 220     mlist *systerms = NULL, *internalModules = NULL;
 221
 222     /* for date and time */
 223
 224     long starTime, diffTime;
 225     tile *r;
 226     extern int optind;
 227     extern char *optarg;
 228     int collapseNullModules = FALSE;
 229     int useBlockPartitioning = FALSE;
 230
 231     outputFile = stdout;
 232
 233     if (recordTiming == TRUE)
 234        mark_time(timingFile, "parse", &diffTime);
 235
 236     /* place */
 237
 238     if (do_hand_placement == FALSE) {
 239         fprintf(stderr,"Placing internal modules...");
 240         if (useBlockPartitioning == FALSE)
 241            partition_count = partition();
 242         else partition_count = blockPartition();
 243
 244         if (collapseNullModules == TRUE) clip_null_gates();
 245
 246         erase_systerms();
 247         place_first_strings();
 248         box_placement();
 249         placement_prep();
 250         modulesJustPlaced = partition_placement();
 251         /* Setup the bounding box */
 252         systerms = make_room_for_systerm_placement(&systermNets, &x1, &y1, &x2, &y2);
 253         fprintf(stderr,"\nAutomatic placement ");
 254     }
 255     fprintf(stderr, "completed.\n");
 256
 257     if (includeSysterms == TRUE) {
 258
 259         /* routing */
 260         if (do_routing == TRUE) {
 261
 262             currentPartition = 0;
 263             for(ml = systerms; ml != NULL; ml = ml->next) pull_terms_from_nets(ml->this);
 264             routingRoot[VERT] = (tile **)calloc(partition_count + 2, sizeof(tile *));
 265             routingRoot[HORZ] = (tile **)calloc(partition_count + 2, sizeof(tile *));
 266
 267             fprintf(stderr,"Routing for Systerm Placement...");
 268
 269             create_routing_space(modulesJustPlaced, currentPartition,
 270                                  x_sizes[currentPartition], y_sizes[currentPartition],
 271                                  xfloor, yfloor);
 272
 273             nl = first_global_route(modulesJustPlaced, currentPartition,
 274                                     TRUE, congestion_rule);
 275             if (recordTiming == TRUE)
 276                 mark_time(timingFile, "central global route", &diffTime);
 277
 278             /* Create a local route to use to locate the system terminals */
 279             local_route(systermNets, currentPartition, FALSE);
 280             if (recordTiming == TRUE)
 281                 mark_time(timingFile, "central local route", &diffTime);
 282             fprintf(stderr,"placing systerms...");
 283
 284             /* Add the system terminals (systerms) to the diagram: */
 285             modulesJustPlaced = fine_systerm_placement(&x1, &y1, &x2, &y2);
 286             if (recordTiming == TRUE)
 287                mark_time(timingFile, "systerm placement", &diffTime);
 288
 289             fprintf(stderr,"completed. \n");
 290         }
 291
 292         if (do_routing != TRUE) {
 293             gross_systerm_placement(&x1, &y1, &x2, &y2);
 294             if (recordTiming == TRUE)
 295                mark_time(timingFile, "gross systerm placement", &diffTime);
 296         }
 297
 298         /* Add the system terminals back to their respective nets: */
 299
 300         for (ml = systerms; ml != NULL; ml = ml->next)
 301            add_terms_to_nets(ml->this);
 302
 303         fprintf(stderr,"System Terminals being added to diagram...\n");
 304
 305         /* finish the routing */
 306
 307         if (do_routing == TRUE) {
 308             fprintf(stderr,"Adding systerms to routing space, "
 309                         "Global Routing commenced...");
 310
 311             /* Deal with resetting the boundaries to include the system terminals: */
 312
 313             reset_boundaries(routingRoot[HORZ][currentPartition], x1, y1, x2, y2);
 314             reset_boundaries(routingRoot[VERT][currentPartition], y1, x1, y2, x2);
 315             xfloor = x1;
 316             x_sizes[currentPartition] = x2 - x1;
 317             yfloor = y1;
 318             y_sizes[currentPartition] = y2 - y1;
 319
 320             nl = incremental_global_route(modulesJustPlaced, modules, nl,
 321                                 currentPartition);
 322
 323             if (recordTiming == TRUE)
 324                mark_time(timingFile, "complete global route", &diffTime);
 325
 326             fprintf(stderr,"completed...Local Routing commenced...");
 327             local_route(nets, currentPartition, TRUE);
 328             if (recordTiming == TRUE)
 329                mark_time(timingFile, "complete local route", &diffTime);
 330             fprintf(stderr,"completed.\n");
 331         }
 332     }
 333     else if (do_routing == TRUE) {
 334
 335         /* TEST! Tim 4/30/2012 --- put a large buffer area around the   */
 336         /* area.  Area calculation seems to assume that lower bound is  */
 337         /* zero and _sizes seem to be calculated from zero to max so    */
 338         /* that negative numbers are not represented.  Below is just a  */
 339         /* hack---we need to calculate the bounding box of the space    */
 340         /* needed for the routing, correctly.                           */
 341
 342         xfloor = yfloor = -72;
 343
 344         /* No terminals are to be placed, hence no incremental routing. */
 345
 346         routingRoot[VERT] = (tile **)calloc(partition_count + 3, sizeof(tile *));
 347         routingRoot[HORZ] = (tile **)calloc(partition_count + 3, sizeof(tile *));
 348
 349         fprintf(stderr,"Adding modules to routing space, Global Routing commenced...");
 350
 351         create_routing_space(modulesJustPlaced, currentPartition,
 352                         x_sizes[currentPartition] - xfloor,
 353                         y_sizes[currentPartition] - yfloor,
 354                         xfloor, yfloor);
 355
 356         nl = first_global_route(modulesJustPlaced, currentPartition,
 357                                 FALSE, congestion_rule);
 358         if (recordTiming == TRUE)
 359            mark_time(timingFile, "complete global route", &diffTime);
 360
 361         fprintf(stderr,"completed...Local Routing commenced...");
 362         local_route(nets, currentPartition, TRUE);
 363         fprintf(stderr,"completed.\n");
 364         if (recordTiming == TRUE)
 365            mark_time(timingFile, "complete local route", &diffTime);
 366     }
 367
 368     if (recordStats == TRUE) print_distance_matricies();
 369
 370     /* Finish up */
 371
 372     if (debug_level > 20) {
 373        print_modules(stderr);
 374        print_nets(stderr);
 375        print_info(stderr);
 376        print_strings(stderr);
 377     }
 378
 379     if (do_routing != TRUE) {
 380         draft_statistics();
 381         print_module_placement(currentPartition, outputFile);
 382     }
 383     else {
 384         if (turn_mode != TIGHT)
 385            print_global_route(outputFile);
 386         else
 387            // Dump the spar structures into Xcircuit
 388            xc_print_local_route(areastruct, nets);
 389
 390         if (recordStats == TRUE) {
 391             draft_statistics();
 392             collect_congestion_stats(currentPartition);
 393         }
 394
 395         fprintf(stderr, "\n %d Lines read, %d Modules, %d Nodes, %d Partitions\n",
 396                 lcount, module_count, node_count, partition_count);
 397         fprintf(stderr, "\nMax partition size: %d Max Connections: "
 398                 "%d Ratio: %-5.3f Rule #%d\n",
 399                 max_partition_size, max_partition_conn,
 400                 partition_ratio, partition_rule);
 401
 402         if (recordTiming == TRUE) {
 403             mark_time(timingFile, "Generation time", &diffTime);
 404             fprintf(timingFile,"%d Modules, %d Nets, %d Terminals, %d partitions\n\n",
 405                 list_length(modules), list_length(nets),
 406                 count_terminals(modules), partition_count);
 407             fclose(timingFile);
 408         }
 409     }
 410 }