asg/route.h

   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 route.h
  24  * As part of MS Thesis Work, S T Frezza, UPitt Engineering
  25  * February, 1990
  26  *
  27  * This file contains the global and local routing structures used to perform the routing fns
  28  * in SPAR.
  29  */
  30
  31 #include <math.h>
  32 #include "externs.h"
  33
  34 #define RIPPED 1
  35 #define HASH_SIZE 43
  36
  37 #define NO_SIDE -1
  38 #define TERM_MARGIN 1
  39 #define GRAY_MARGIN 0.05
  40
  41 #define TRACK_WEIGHT 30.0
  42 #define LENGTH_WEIGHT 1.0
  43 #define FORWARD_EST_MULTIPLIER 0.80
  44 #define EXPECTED_CORNERS 3
  45 #define CORNER_COST 4
  46
  47 #define TOP_EDGE 1
  48 #define BOT_EDGE 2
  49 #define LEFT_EDGE 4
  50 #define RIGHT_EDGE 8
  51
  52 #define UPWARD_U 1
  53 #define DOWNWARD_U 2
  54 #define HORZ_JOG 3
  55 #define LEFT_U 4
  56 #define UL_CORNER 5
  57 #define LL_CORNER 6
  58 #define VERT_LT 7
  59 #define RIGHT_U 8
  60 #define UR_CORNER 9
  61 #define LR_CORNER 10
  62 #define VERT_RT 11
  63 #define VERT_JOG 12
  64 #define HORZ_UT 13
  65 #define HORZ_DT 14
  66 #define X_CORNER 15
  67
  68 #define EXPAND_BOTH 2
  69 #define EXPAND_MIN 3
  70 #define EXPAND_MAX 4
  71 #define EXPAND_NONE 5
  72
  73 /* Structure Definitions and type definitions: */
  74 typedef struct arc_struct       asg_arc;
  75 typedef struct arc_list_struct  arclist;
  76 typedef struct expansion_struct expn;
  77 typedef struct expn_list_struct expnlist;
  78 typedef struct trail_struct     trail;
  79 typedef struct trail_ilist_str  trailist;
  80 typedef struct trail_list_str   trlist;
  81 typedef struct range_struct     range;
  82 typedef struct range_list_str   rnglist;
  83 typedef struct corner_struct    corner;
  84 typedef struct corner_list_str  crnlist;
  85
  86 struct arc_struct
  87 /* structure to manage arcs in the global router */
  88 {
  89     nlist *nets;        /* nets that use this arc for their GR */
  90     crnlist *corners;   /* local routing corners that currently use this arc */
  91     int congestion;     /* congestion level */
  92     int page;           /* Indicates which page this tile belongs to. */
  93     int vcap, hcap;     /* Vertical and Horizontal capacities (# of tracks) */
  94     tile *t;            /* tile associated with this arc */
  95     module *mod;        /* Used to hold the original contents of the tile */
  96     trailist *trails[HASH_SIZE];/* pointers to trails that use this tile */
  97     int local, count;           /* used for stats */
  98 };
  99
 100 struct expansion_struct
 101 /* structure to manage multipoint, pseudo-similtaneous expansions within the
 102  * arc/edge configuration.  One of these should be used for every terminal in
 103  * a given net.  */
 104 {
 105     net *n;             /* Net to which the terminal belongs */
 106     term *t;            /* Terminal from which the expansions began */
 107     tilist *seen;       /* list of tiles that this expn has visited */
 108     trailist *queue[HASH_SIZE]; /* Hash table of trails, from which the
 109                                    next move is selected */
 110     expnlist *siblings; /* (shared) list of expns that make up this expansion group */
 111     trlist *connections;/* (shared) list of trails that form complete paths */
 112     int eCount;         /* for statistics */
 113 };
 114
 115 struct trail_struct
 116 {
 117     /* This is a possible global route;  Only if *used is set are there
 118        ranges associated with the trail. */
 119     int cost;
 120     expn *ex;           /* Parent expansion */
 121     expn *jEx;          /* Who was contacted at termination */
 122     tilist *tr;         /* ordered list of tiles traversed */
 123     int page, direction;/* array indecies to the root tile for the next expansion set */
 124     crnlist *used;      /* Pointer to the set of corners that
 125                            comprise this trail (when constructed) */
 126 };
 127
 128
 129 struct trail_ilist_str  /* Indexed form */
 130 {
 131     int index;          /* trail cost */
 132     trail *this;
 133     trailist *next;
 134 };
 135
 136 struct trail_list_str   /* Non-indexed form */
 137 {
 138     trail *this;
 139     trlist *next;
 140 };
 141
 142
 143 struct expn_list_struct
 144 {
 145     expn *this;
 146     expnlist *next;
 147 };
 148
 149 struct arc_list_struct
 150 {
 151     asg_arc *this;
 152     arclist *next;
 153 };
 154
 155
 156 /* The following are used to implement the local router: */
 157 struct range_struct
 158 {
 159     srange *sr;             /* The min/max limits of this range. */
 160     int use, flag;
 161     net *n;                 /* The net that this range is a part of */
 162     crnlist *corners;       /* Corners linked by this range */
 163     crnlist *dep;           /* Corners who's placement this range is constrained by */
 164 };
 165
 166 struct range_list_str
 167 {
 168     range *this;
 169     rnglist *next;
 170 };
 171
 172 struct corner_struct
 173 {
 174     range *cx;
 175     range *cy;
 176     int vertOrder, horzOrder;
 177     arclist *al;
 178     term *t;
 179 };
 180
 181 struct corner_list_str
 182 {
 183     corner *this;
 184     crnlist *next;
 185 };
 186
 187
 188
 189 /* Shared info between global and local router: */
 190 /*---------------------------------------------------------------
 191  * Defined in global_route.c
 192  *---------------------------------------------------------------
 193  */
 194 extern asg_arc *next_arc();
 195 extern int net_using_edge();
 196 extern int congestion_cost();
 197 extern int decision_box[];
 198 extern tilist *collect_tiles();
 199
 200 /*---------------------------------------------------------------
 201  * Defined in local_route.c
 202  *---------------------------------------------------------------
 203  */
 204 extern corner *create_corner();
 205 extern int in_x_order();
 206 extern int divide_sranges();
 207 extern int overlapped_p();