route_timing.c

fpga设计评估软件

/* Puts the entire partial routing below and including rt_node onto the heap *
 * (except for those parts marked as not to be expanded) by calling itself   *
 * recursively.                                                              */

 int inode;
 t_rt_node *child_node;
 t_linked_rt_edge *linked_rt_edge;
 float tot_cost, backward_path_cost, R_upstream;

/* Pre-order depth-first traversal */

 if (rt_node->re_expand) {
    inode = rt_node->inode;
    backward_path_cost = target_criticality * rt_node->Tdel;
    R_upstream = rt_node->R_upstream;
    tot_cost = backward_path_cost + astar_fac * get_timing_driven_expected_cost
                     (inode, target_node, target_criticality, R_upstream); 
    node_to_heap (inode, tot_cost, NO_PREVIOUS, NO_PREVIOUS, 
                  backward_path_cost, R_upstream);
 }

 linked_rt_edge = rt_node->u.child_list;

 while (linked_rt_edge != NULL) {
    child_node = linked_rt_edge->child;
    add_route_tree_to_heap (child_node, target_node, target_criticality, 
                            astar_fac);
    linked_rt_edge = linked_rt_edge->next;
 }
}


static void timing_driven_expand_neighbours (struct s_heap *current, int inet,
          float bend_cost, float criticality_fac, int target_node, float 
          astar_fac) {

/* Puts all the rr_nodes adjacent to current on the heap.  rr_nodes outside *
 * the expanded bounding box specified in route_bb are not added to the     *
 * heap.                                                                    */

 int iconn, to_node, num_edges, inode, iswitch, target_x, target_y;
 t_rr_type from_type, to_type;
 float new_tot_cost, old_back_pcost, new_back_pcost, R_upstream;
 float new_R_upstream, Tdel;

 inode = current->index;
 old_back_pcost = current->backward_path_cost;
 R_upstream = current->R_upstream;
 num_edges = rr_node[inode].num_edges;

 target_x = rr_node[target_node].xhigh;
 target_y = rr_node[target_node].yhigh;

 for (iconn=0;iconn<num_edges;iconn++) {
    to_node = rr_node[inode].edges[iconn];
   
    if (   rr_node[to_node].xhigh < route_bb[inet].xmin ||
           rr_node[to_node].xlow > route_bb[inet].xmax  ||
           rr_node[to_node].yhigh < route_bb[inet].ymin ||
           rr_node[to_node].ylow > route_bb[inet].ymax    )
       continue;      /* Node is outside (expanded) bounding box. */

/* Prune away IPINs that lead to blocks other than the target one.  Avoids  *
 * the issue of how to cost them properly so they don't get expanded before *
 * more promising routes, but makes route-throughs (via CLBs) impossible.   *
 * Change this if you want to investigate route-throughs.                   */

    to_type = rr_node[to_node].type;
    if (to_type == IPIN && (rr_node[to_node].xhigh != target_x || 
                            rr_node[to_node].yhigh != target_y))
       continue;
   

/* new_back_pcost stores the "known" part of the cost to this node -- the   *
 * congestion cost of all the routing resources back to the existing route  *
 * plus the known delay of the total path back to the source.  new_tot_cost *
 * is this "known" backward cost + an expected cost to get to the target.   */

    new_back_pcost = old_back_pcost + (1. - criticality_fac) * 
                                    get_rr_cong_cost (to_node);

    iswitch = rr_node[inode].switches[iconn];
    if (switch_inf[iswitch].buffered) {
       new_R_upstream = switch_inf[iswitch].R;
    }
    else {
       new_R_upstream = R_upstream + switch_inf[iswitch].R;
    }

    Tdel = rr_node[to_node].C * (new_R_upstream + 0.5 * rr_node[to_node].R);
    Tdel += switch_inf[iswitch].Tdel;
    new_R_upstream += rr_node[to_node].R;
    new_back_pcost += criticality_fac * Tdel;

    if (bend_cost != 0.) {
       from_type = rr_node[inode].type;
       to_type = rr_node[to_node].type;
       if ((from_type == CHANX && to_type == CHANY) ||
              (from_type == CHANY && to_type == CHANX))
          new_back_pcost += bend_cost;
    }

    new_tot_cost = new_back_pcost + astar_fac * 
                      get_timing_driven_expected_cost (to_node, target_node, 
                                            criticality_fac, new_R_upstream);

    node_to_heap (to_node, new_tot_cost, inode, iconn, new_back_pcost, 
                  new_R_upstream);

 }  /* End for all neighbours */
}


static float get_timing_driven_expected_cost (int inode, int target_node, 
              float criticality_fac, float R_upstream) {

/* Determines the expected cost (due to both delay and resouce cost) to reach *
 * the target node from inode.  It doesn't include the cost of inode --       *
 * that's already in the "known" path_cost.                                   */

 t_rr_type rr_type;
 int cost_index, ortho_cost_index, num_segs_same_dir, num_segs_ortho_dir;
 float expected_cost, cong_cost, Tdel;

 rr_type = rr_node[inode].type;

 if (rr_type == CHANX || rr_type == CHANY) {
    num_segs_same_dir = get_expected_segs_to_target (inode, target_node, 
                         &num_segs_ortho_dir);
    cost_index = rr_node[inode].cost_index;
    ortho_cost_index = rr_indexed_data[cost_index].ortho_cost_index;

    cong_cost = num_segs_same_dir * rr_indexed_data[cost_index].base_cost +
              num_segs_ortho_dir * rr_indexed_data[ortho_cost_index].base_cost;
    cong_cost += rr_indexed_data[IPIN_COST_INDEX].base_cost + 
                 rr_indexed_data[SINK_COST_INDEX].base_cost;
    
    Tdel = num_segs_same_dir * rr_indexed_data[cost_index].T_linear + 
           num_segs_ortho_dir * rr_indexed_data[ortho_cost_index].T_linear + 
           num_segs_same_dir * num_segs_same_dir * 
           rr_indexed_data[cost_index].T_quadratic +
           num_segs_ortho_dir * num_segs_ortho_dir * 
           rr_indexed_data[ortho_cost_index].T_quadratic +
           R_upstream * (num_segs_same_dir * rr_indexed_data[cost_index].C_load
             + num_segs_ortho_dir * rr_indexed_data[ortho_cost_index].C_load);

    Tdel += rr_indexed_data[IPIN_COST_INDEX].T_linear;

    expected_cost = criticality_fac * Tdel + (1. - criticality_fac) * cong_cost;
    return (expected_cost); 
 }

 else if (rr_type == IPIN) {   /* Change if you're allowing route-throughs */
    return (rr_indexed_data[SINK_COST_INDEX].base_cost);
 }

 else {       /* Change this if you want to investigate route-throughs */
    return (0.);
 }
}


/* Macro used below to ensure that fractions are rounded up, but floating   *
 * point values very close to an integer are rounded to that integer.       */

#define ROUND_UP(x) (ceil (x - 0.001))


static int get_expected_segs_to_target (int inode, int target_node, int *
                num_segs_ortho_dir_ptr) {

/* Returns the number of segments the same type as inode that will be needed *
 * to reach target_node (not including inode) in each direction (the same    *
 * direction (horizontal or vertical) as inode and the orthogonal direction).*/

 t_rr_type rr_type;
 int target_x, target_y, num_segs_same_dir, cost_index, ortho_cost_index;
 int no_need_to_pass_by_clb;
 float inv_length, ortho_inv_length, ylow, yhigh, xlow, xhigh;

 target_x = rr_node[target_node].xlow;  
 target_y = rr_node[target_node].ylow;
 cost_index = rr_node[inode].cost_index;
 inv_length = rr_indexed_data[cost_index].inv_length;
 ortho_cost_index = rr_indexed_data[cost_index].ortho_cost_index;
 ortho_inv_length = rr_indexed_data[ortho_cost_index].inv_length;
 rr_type = rr_node[inode].type;

 if (rr_type == CHANX) {
    ylow = rr_node[inode].ylow;
    xhigh = rr_node[inode].xhigh;
    xlow = rr_node[inode].xlow;

   /* Count vertical (orthogonal to inode) segs first. */

    if (ylow > target_y) {         /* Coming from a row above target? */
       *num_segs_ortho_dir_ptr = ROUND_UP ((ylow - target_y + 1.) * 
                                          ortho_inv_length);
       no_need_to_pass_by_clb = 1;
    }
    else if (ylow < target_y - 1) {  /* Below the CLB bottom? */
       *num_segs_ortho_dir_ptr = ROUND_UP ((target_y - ylow) * 
                                           ortho_inv_length);
       no_need_to_pass_by_clb = 1;
    }
    else {              /* In a row that passes by target CLB */
       *num_segs_ortho_dir_ptr = 0;
       no_need_to_pass_by_clb = 0;
    }

   /* Now count horizontal (same dir. as inode) segs. */

    if (xlow > target_x + no_need_to_pass_by_clb) {
       num_segs_same_dir = ROUND_UP ((xlow - no_need_to_pass_by_clb - 
                                target_x) * inv_length);
    }
    else if (xhigh < target_x - no_need_to_pass_by_clb) {
       num_segs_same_dir = ROUND_UP ((target_x - no_need_to_pass_by_clb - 
                                xhigh) * inv_length);
    }
    else {
       num_segs_same_dir = 0;
    }
 }

 else {  /* inode is a CHANY */
    ylow = rr_node[inode].ylow;
    yhigh = rr_node[inode].yhigh;
    xlow = rr_node[inode].xlow;

   /* Count horizontal (orthogonal to inode) segs first. */

    if (xlow > target_x) {         /* Coming from a column right of target? */
       *num_segs_ortho_dir_ptr = ROUND_UP ((xlow - target_x + 1.) * 
                                            ortho_inv_length);
       no_need_to_pass_by_clb = 1;
    }
    else if (xlow < target_x - 1) {  /* Left of and not adjacent to the CLB? */
       *num_segs_ortho_dir_ptr = ROUND_UP ((target_x - xlow) * 
                                            ortho_inv_length);
       no_need_to_pass_by_clb = 1;
    }
    else {              /* In a column that passes by target CLB */
       *num_segs_ortho_dir_ptr = 0;
       no_need_to_pass_by_clb = 0;
    }

   /* Now count vertical (same dir. as inode) segs. */

    if (ylow > target_y + no_need_to_pass_by_clb) {
       num_segs_same_dir = ROUND_UP ((ylow - no_need_to_pass_by_clb - 
                              target_y) * inv_length);
    }
    else if (yhigh < target_y - no_need_to_pass_by_clb) {
       num_segs_same_dir = ROUND_UP ((target_y - no_need_to_pass_by_clb - 
                              yhigh) * inv_length);
    }
    else {
       num_segs_same_dir = 0;
    }
 }

 return (num_segs_same_dir);
}


static void update_rr_base_costs (int inet, float largest_criticality) {

/* Changes the base costs of different types of rr_nodes according to the  *
 * criticality, fanout, etc. of the current net being routed (inet).       */

 float fanout, factor;
 int index;

 fanout = net[inet].num_pins - 1.;
 factor = sqrt (fanout); 
/* factor = fanout; */
/* factor = 1.;    */

 for (index=CHANX_COST_INDEX_START;index<num_rr_indexed_data;index++) {
    if (rr_indexed_data[index].T_quadratic > 0.) {  /* pass transistor */
       rr_indexed_data[index].base_cost = 
             rr_indexed_data[index].saved_base_cost * factor;
    }
    else {
       rr_indexed_data[index].base_cost = 
             rr_indexed_data[index].saved_base_cost;
    }
 }
}


#define ERROR_TOL 0.0001

static void timing_driven_check_net_delays (float **net_delay) {

/* Checks that the net delays computed incrementally during timing driven    *
 * routing match those computed from scratch by the net_delay.c module.      */

 int inet, ipin;
 float **net_delay_check;
 struct s_linked_vptr *ch_list_head_net_delay_check;

 net_delay_check = alloc_net_delay (&ch_list_head_net_delay_check);
 load_net_delay_from_routing (net_delay_check);

 for (inet=0;inet<num_nets;inet++) {
    for (ipin=1;ipin<net[inet].num_pins;ipin++) {
       if (net_delay_check[inet][ipin] == 0.) { /* Should be only GLOBAL nets */
          if (net_delay_check[inet][ipin] != 0.) {
             printf ("Error in timing_driven_check_net_delays: net %d pin %d."
                     "\tIncremental calc. net_delay is %g, but from scratch "
                     "net delay is %g.\n", inet, ipin, net_delay[inet][ipin],
                     net_delay_check[inet][ipin]);
             exit (1);
          }
       }
       else {
          if (fabs (1. - net_delay[inet][ipin] / net_delay_check[inet][ipin]) 
                          > ERROR_TOL) {
             printf ("Error in timing_driven_check_net_delays: net %d pin %d."
                     "\tIncremental calc. net_delay is %g, but from scratch "
                     "net delay is %g.\n", inet, ipin, net_delay[inet][ipin],
                     net_delay_check[inet][ipin]);
             exit (1);
          }
       }
    }
 }
 
 free_net_delay (net_delay_check, &ch_list_head_net_delay_check);
 printf ("Completed net delay value cross check successfully.\n");
}