VPR-6.0
Data Structures | Functions | Variables

vpr/SRC/route/route_common.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  s_heap
struct  t_rr_node_route_inf

Functions

void pathfinder_update_one_cost (struct s_trace *route_segment_start, int add_or_sub, float pres_fac)
void pathfinder_update_cost (float pres_fac, float acc_fac)
struct s_trace * update_traceback (struct s_heap *hptr, int inet)
void reset_path_costs (void)
float get_rr_cong_cost (int inode)
void mark_ends (int inet)
void node_to_heap (int inode, float cost, int prev_node, int prev_edge, float backward_path_cost, float R_upstream)
boolean is_empty_heap (void)
void free_traceback (int inet)
void add_to_mod_list (float *fptr)
struct s_heap * get_heap_head (void)
void empty_heap (void)
void free_heap_data (struct s_heap *hptr)
void invalidate_heap_entries (int sink_node, int ipin_node)
void init_route_structs (int bb_factor)
void free_rr_node_route_structs (void)
void alloc_and_load_rr_node_route_structs (void)
void reset_rr_node_route_structs (void)
void alloc_route_static_structs ()
void free_trace_structs (void)
void reserve_locally_used_opins (float pres_fac, boolean rip_up_local_opins, t_ivec **clb_opins_used_locally)

Variables

t_rr_node_route_inf * rr_node_route_inf
struct s_bb * route_bb

Function Documentation

void add_to_mod_list ( float *  fptr)

This routine adds the floating point pointer (fptr) into a linked list that indicates all the pathcosts that have been modified thus far.

Definition at line 1033 of file route_common.c.

{

    struct s_linked_f_pointer *mod_ptr;

    mod_ptr = alloc_linked_f_pointer();

/* Add this element to the start of the modified list. */

    mod_ptr->next = rr_modified_head;
    mod_ptr->fptr = fptr;
    rr_modified_head = mod_ptr;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void alloc_and_load_rr_node_route_structs ( void  )

Allocates some extra information about each rr_node that is used only during routing.

Definition at line 904 of file route_common.c.

{

    int inode;

    if(rr_node_route_inf != NULL)
        {
            printf("Error in alloc_and_load_rr_node_route_structs:  \n"
                   "old rr_node_route_inf array exists.\n");
            exit(1);
        }

    rr_node_route_inf = my_malloc(num_rr_nodes * sizeof(t_rr_node_route_inf));

    for(inode = 0; inode < num_rr_nodes; inode++)
        {
            rr_node_route_inf[inode].prev_node = NO_PREVIOUS;
            rr_node_route_inf[inode].prev_edge = NO_PREVIOUS;
            rr_node_route_inf[inode].pres_cost = 1.;
            rr_node_route_inf[inode].acc_cost = 1.;
            rr_node_route_inf[inode].path_cost = HUGE_FLOAT;
            rr_node_route_inf[inode].target_flag = 0;
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void alloc_route_static_structs ( )

Definition at line 715 of file route_common.c.

                                  {
    trace_head = (struct s_trace **)my_calloc(num_nets,
                                              sizeof(struct s_trace *));
    trace_tail = (struct s_trace **)my_malloc(num_nets *
                                              sizeof(struct s_trace *));

    heap_size = nx * ny;
    heap = (struct s_heap **)my_malloc(heap_size * sizeof(struct s_heap *));
    heap--;                     /* heap stores from [1..heap_size] */
    heap_tail = 1;

    route_bb = (struct s_bb *)my_malloc(num_nets * sizeof(struct s_bb));
}

Here is the call graph for this function:

Here is the caller graph for this function:

void empty_heap ( void  )

Definition at line 1136 of file route_common.c.

{

    int i;

    for(i = 1; i < heap_tail; i++)
        free_heap_data(heap[i]);

    heap_tail = 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void free_heap_data ( struct s_heap *  hptr)

Definition at line 1182 of file route_common.c.

{

    hptr->u.next = heap_free_head;
    heap_free_head = hptr;
#ifdef DEBUG
    num_heap_allocated--;
#endif
}

Here is the caller graph for this function:

void free_rr_node_route_structs ( void  )

Frees the extra information about each rr_node that is needed only during routing.

Definition at line 954 of file route_common.c.

{

    free(rr_node_route_inf);
    rr_node_route_inf = NULL;   /* Mark as free */
}

Here is the caller graph for this function:

void free_trace_structs ( void  )

the trace lists are only freed after use by the timing-driven placer. Do not free them after use by the router, since stats, and draw routines use the trace values

Definition at line 841 of file route_common.c.

{
    int i;

    for(i = 0; i < num_nets; i++)
        free_traceback(i);

    free(trace_head);
    free(trace_tail);
    trace_head = NULL;
    trace_tail = NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void free_traceback ( int  inet)

Puts the entire traceback (old routing) for this net on the free list and sets the trace_head pointers etc. for the net to NULL.

Definition at line 683 of file route_common.c.

{

    struct s_trace *tptr, *tempptr;

    tptr = trace_head[inet];

    while(tptr != NULL)
        {
            tempptr = tptr->next;
            free_trace_data(tptr);
            tptr = tempptr;
        }

    trace_head[inet] = NULL;
    trace_tail[inet] = NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct s_heap* get_heap_head ( void  ) [read]

Returns a pointer to the smallest element on the heap, or NULL if the heap is empty. Invalid (index == OPEN) entries on the heap are never returned -- they are just skipped over.

Definition at line 1090 of file route_common.c.

{

    int ito, ifrom;
    struct s_heap *heap_head, *temp_ptr;

    do
        {
            if(heap_tail == 1)
                {               /* Empty heap. */
                    printf("Empty heap occurred in get_heap_head.\n");
                    printf
                        ("Some blocks are impossible to connect in this architecture.\n");
                    return (NULL);
                }

            heap_head = heap[1];        /* Smallest element. */

            /* Now fix up the heap */

            heap_tail--;
            heap[1] = heap[heap_tail];
            ifrom = 1;
            ito = 2 * ifrom;

            while(ito < heap_tail)
                {
                    if(heap[ito + 1]->cost < heap[ito]->cost)
                        ito++;
                    if(heap[ito]->cost > heap[ifrom]->cost)
                        break;
                    temp_ptr = heap[ito];
                    heap[ito] = heap[ifrom];
                    heap[ifrom] = temp_ptr;
                    ifrom = ito;
                    ito = 2 * ifrom;
                }

        }
    while(heap_head->index == OPEN);    /* Get another one if invalid entry. */

    return (heap_head);
}

Here is the caller graph for this function:

float get_rr_cong_cost ( int  inode)

Returns the *congestion* cost of using this rr_node.

Definition at line 617 of file route_common.c.

{
    short cost_index;
    float cost;

    cost_index = rr_node[inode].cost_index;
    cost = rr_indexed_data[cost_index].base_cost *
        rr_node_route_inf[inode].acc_cost *
        rr_node_route_inf[inode].pres_cost;
    return (cost);
}

Here is the caller graph for this function:

void init_route_structs ( int  bb_factor)

Call this before you route any nets. It frees any old traceback and sets the list of rr_nodes touched to empty.

Definition at line 461 of file route_common.c.

{

    int i;

    for(i = 0; i < num_nets; i++)
        free_traceback(i);

    load_route_bb(bb_factor);

/* Check that things that should have been emptied after the last routing *
 * really were.                                                           */

    if(rr_modified_head != NULL)
        {
            printf
                ("Error in init_route_structs.  List of modified rr nodes is \n"
                 "not empty.\n");
            exit(1);
        }

    if(heap_tail != 1)
        {
            printf("Error in init_route_structs.  Heap is not empty.\n");
            exit(1);
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void invalidate_heap_entries ( int  sink_node,
int  ipin_node 
)

Marks all the heap entries consisting of sink_node, where it was reached via ipin_node, as invalid (OPEN). Used only by the breadth_first router and even then only in rare circumstances.

Definition at line 1197 of file route_common.c.

{
    int i;

    for(i = 1; i < heap_tail; i++)
        {
            if(heap[i]->index == sink_node
               && heap[i]->u.prev_node == ipin_node)
                heap[i]->index = OPEN;  /* Invalid. */
        }
}

Here is the caller graph for this function:

boolean is_empty_heap ( void  )

WMF: peeking accessor :)

Definition at line 1080 of file route_common.c.

{
    return (heap_tail == 1);
}

Here is the caller graph for this function:

void mark_ends ( int  inet)

Mark all the SINKs of this net as targets by setting their target flags to the number of times the net must connect to each SINK. Note that this number can occassionally be greater than 1 -- think of connecting the same net to two inputs of an and-gate (and-gate inputs are logically equivalent, so both will connect to the same SINK).

Definition at line 636 of file route_common.c.

{

    int ipin, inode;

    for(ipin = 1; ipin <= clb_net[inet].num_sinks; ipin++)
        {
            inode = net_rr_terminals[inet][ipin];
            rr_node_route_inf[inode].target_flag++;
        }
}

Here is the caller graph for this function:

void node_to_heap ( int  inode,
float  cost,
int  prev_node,
int  prev_edge,
float  backward_path_cost,
float  R_upstream 
)

Puts an rr_node on the heap, if the new cost given is lower than the current path_cost to this channel segment. The index of its predecessor is stored to make traceback easy. The index of the edge used to get from its predecessor to it is also stored to make timing analysis, etc. easy. The backward_path_cost and R_upstream values are used only by the timing-driven router -- the breadth-first router ignores them.

Definition at line 656 of file route_common.c.

{

    struct s_heap *hptr;

    if(cost >= rr_node_route_inf[inode].path_cost)
        return;

    hptr = alloc_heap_data();
    hptr->index = inode;
    hptr->cost = cost;
    hptr->u.prev_node = prev_node;
    hptr->prev_edge = prev_edge;
    hptr->backward_path_cost = backward_path_cost;
    hptr->R_upstream = R_upstream;
    add_to_heap(hptr);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void pathfinder_update_cost ( float  pres_fac,
float  acc_fac 
)

This routine recomputes the pres_cost and acc_cost of each routing resource for the pathfinder algorithm after all nets have been routed. It updates the accumulated cost to by adding in the number of extra signals sharing a resource right now (i.e. after each complete iteration) times acc_fac. It also updates pres_cost, since pres_fac may have changed. THIS ROUTINE ASSUMES THE OCCUPANCY VALUES IN RR_NODE ARE UP TO DATE.

Definition at line 428 of file route_common.c.

{

    int inode, occ, capacity;

    for(inode = 0; inode < num_rr_nodes; inode++)
        {
            occ = rr_node[inode].occ;
            capacity = rr_node[inode].capacity;

            if(occ > capacity)
                {
                    rr_node_route_inf[inode].acc_cost +=
                        (occ - capacity) * acc_fac;
                    rr_node_route_inf[inode].pres_cost =
                        1. + (occ + 1 - capacity) * pres_fac;
                }

/* If occ == capacity, we don't need to increase acc_cost, but a change    *
 * in pres_fac could have made it necessary to recompute the cost anyway.  */

            else if(occ == capacity)
                {
                    rr_node_route_inf[inode].pres_cost = 1. + pres_fac;
                }
        }
}

Here is the caller graph for this function:

void pathfinder_update_one_cost ( struct s_trace *  route_segment_start,
int  add_or_sub,
float  pres_fac 
)

This routine updates the occupancy and pres_cost of the rr_nodes that are affected by the portion of the routing of one net that starts at route_segment_start. If route_segment_start is trace_head[inet], the cost of all the nodes in the routing of net inet are updated. If add_or_sub is -1 the net (or net portion) is ripped up, if it is 1 the net is added to the routing. The size of pres_fac determines how severly oversubscribed rr_nodes are penalized.

Definition at line 372 of file route_common.c.

{

    struct s_trace *tptr;
    int inode, occ, capacity;

    tptr = route_segment_start;
    if(tptr == NULL)            /* No routing yet. */
        return;

    for(;;)
        {
            inode = tptr->index;

            occ = rr_node[inode].occ + add_or_sub;
            capacity = rr_node[inode].capacity;

            rr_node[inode].occ = occ;

/* pres_cost is Pn in the Pathfinder paper. I set my pres_cost according to *
 * the overuse that would result from having ONE MORE net use this routing  *
 * node.                                                                    */

            if(occ < capacity)
                {
                    rr_node_route_inf[inode].pres_cost = 1.;
                }
            else
                {
                    rr_node_route_inf[inode].pres_cost =
                        1. + (occ + 1 - capacity) * pres_fac;
                }

            if(rr_node[inode].type == SINK)
                {
                    tptr = tptr->next;  /* Skip next segment. */
                    if(tptr == NULL)
                        break;
                }

            tptr = tptr->next;

        }                       /* End while loop -- did an entire traceback. */
}

Here is the caller graph for this function:

void reserve_locally_used_opins ( float  pres_fac,
boolean  rip_up_local_opins,
t_ivec **  clb_opins_used_locally 
)

Definition at line 1426 of file route_common.c.

{

/* In the past, this function implicitly allowed LUT duplication when there are free LUTs. 
This was especially important for logical equivalence; however, now that we have a very general
logic cluster, it does not make sense to allow LUT duplication implicitly. we'll need to look into how we want to handle this case

*/

    int iblk, num_local_opin, inode, from_node, iconn, num_edges, to_node;
    int iclass, ipin;
    float cost;
    struct s_heap *heap_head_ptr;
    t_type_ptr type;

    if(rip_up_local_opins)
        {
            for(iblk = 0; iblk < num_blocks; iblk++)
                {
                    type = block[iblk].type;
                    for(iclass = 0; iclass < type->num_class; iclass++)
                        {
                            num_local_opin =
                                clb_opins_used_locally[iblk][iclass].nelem;
                            /* Always 0 for pads and for RECEIVER (IPIN) classes */
                            for(ipin = 0; ipin < num_local_opin; ipin++)
                                {
                                    inode =
                                        clb_opins_used_locally[iblk][iclass].
                                        list[ipin];
                                    adjust_one_rr_occ_and_pcost(inode, -1,
                                                                pres_fac);
                                }
                        }
                }
        }

    for(iblk = 0; iblk < num_blocks; iblk++)
        {
            type = block[iblk].type;
            for(iclass = 0; iclass < type->num_class; iclass++)
                {
                    num_local_opin =
                        clb_opins_used_locally[iblk][iclass].nelem;
                    /* Always 0 for pads and for RECEIVER (IPIN) classes */

                    if(num_local_opin != 0)
                        {       /* Have to reserve (use) some OPINs */
                            from_node = rr_blk_source[iblk][iclass];
                            num_edges = rr_node[from_node].num_edges;
                            for(iconn = 0; iconn < num_edges; iconn++)
                                {
                                    to_node = rr_node[from_node].edges[iconn];
                                    cost = get_rr_cong_cost(to_node);
                                    node_to_heap(to_node, cost, OPEN, OPEN,
                                                 0., 0.);
                                }

                            for(ipin = 0; ipin < num_local_opin; ipin++)
                                {
                                    heap_head_ptr = get_heap_head();
                                    inode = heap_head_ptr->index;
                                    adjust_one_rr_occ_and_pcost(inode, 1,
                                                                pres_fac);
                                    clb_opins_used_locally[iblk][iclass].
                                        list[ipin] = inode;
                                    free_heap_data(heap_head_ptr);
                                }

                            empty_heap();
                        }
                }
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void reset_path_costs ( void  )

The routine sets the path_cost to HUGE_FLOAT for all channel segments touched by previous routing phases.

Definition at line 572 of file route_common.c.

{

    struct s_linked_f_pointer *mod_ptr;

#ifdef DEBUG
    int num_mod_ptrs;
#endif

/* The traversal method below is slightly painful to make it faster. */

    if(rr_modified_head != NULL)
        {
            mod_ptr = rr_modified_head;

#ifdef DEBUG
            num_mod_ptrs = 1;
#endif

            while(mod_ptr->next != NULL)
                {
                    *(mod_ptr->fptr) = HUGE_FLOAT;
                    mod_ptr = mod_ptr->next;
#ifdef DEBUG
                    num_mod_ptrs++;
#endif
                }
            *(mod_ptr->fptr) = HUGE_FLOAT;      /* Do last one. */

/* Reset the modified list and put all the elements back in the free   *
 * list.                                                               */

            mod_ptr->next = linked_f_pointer_free_head;
            linked_f_pointer_free_head = rr_modified_head;
            rr_modified_head = NULL;

#ifdef DEBUG
            num_linked_f_pointer_allocated -= num_mod_ptrs;
#endif
        }
}

Here is the caller graph for this function:

void reset_rr_node_route_structs ( void  )

Allocates some extra information about each rr_node that is used only during routing.

Definition at line 933 of file route_common.c.

{
    int inode;

    assert(rr_node_route_inf != NULL);

    for(inode = 0; inode < num_rr_nodes; inode++)
        {
            rr_node_route_inf[inode].prev_node = NO_PREVIOUS;
            rr_node_route_inf[inode].prev_edge = NO_PREVIOUS;
            rr_node_route_inf[inode].pres_cost = 1.;
            rr_node_route_inf[inode].acc_cost = 1.;
            rr_node_route_inf[inode].path_cost = HUGE_FLOAT;
            rr_node_route_inf[inode].target_flag = 0;
        }
}

Here is the caller graph for this function:

struct s_trace* update_traceback ( struct s_heap *  hptr,
int  inet 
) [read]

This routine adds the most recently finished wire segment to the traceback linked list. The first connection starts with the net SOURCE and begins at the structure pointed to by trace_head[inet]. Each connection ends with a SINK. After each SINK, the next connection begins (if the net has more than 2 pins). The first element after the SINK gives the routing node on a previous piece of the routing, which is the link from the existing net to this new piece of the net. In each traceback I start at the end of a path and trace back through its predecessors to the beginning. I have stored information on the predecesser of each node to make traceback easy -- this sacrificies some memory for easier code maintenance. This routine returns a pointer to the first "new" node in the traceback (node not previously in trace).

Definition at line 503 of file route_common.c.

{

    struct s_trace *tptr, *prevptr, *temptail, *ret_ptr;
    int inode;
    short iedge;

#ifdef DEBUG
    t_rr_type rr_type;
#endif

    inode = hptr->index;

#ifdef DEBUG
    rr_type = rr_node[inode].type;
    if(rr_type != SINK)
        {
            printf("Error in update_traceback.  Expected type = SINK (%d).\n",
                   SINK);
            printf("Got type = %d while tracing back net %d.\n", rr_type,
                   inet);
            exit(1);
        }
#endif

    tptr = alloc_trace_data();  /* SINK on the end of the connection */
    tptr->index = inode;
    tptr->iswitch = OPEN;
    tptr->next = NULL;
    temptail = tptr;            /* This will become the new tail at the end */
    /* of the routine.                          */

/* Now do it's predecessor. */

    inode = hptr->u.prev_node;
    iedge = hptr->prev_edge;

    while(inode != NO_PREVIOUS)
        {
            prevptr = alloc_trace_data();
            prevptr->index = inode;
            prevptr->iswitch = rr_node[inode].switches[iedge];
            prevptr->next = tptr;
            tptr = prevptr;

            iedge = rr_node_route_inf[inode].prev_edge;
            inode = rr_node_route_inf[inode].prev_node;
        }

    if(trace_tail[inet] != NULL)
        {
            trace_tail[inet]->next = tptr;      /* Traceback ends with tptr */
            ret_ptr = tptr->next;       /* First new segment.       */
        }
    else
        {                       /* This was the first "chunk" of the net's routing */
            trace_head[inet] = tptr;
            ret_ptr = tptr;     /* Whole traceback is new. */
        }

    trace_tail[inet] = temptail;
    return (ret_ptr);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

struct s_bb* route_bb

[0..num_nets-1]

[0..num_nets-1]. Limits area in which each net must be routed.

Definition at line 24 of file route_common.c.

t_rr_node_route_inf* rr_node_route_inf

[0..num_rr_nodes-1]

Definition at line 22 of file route_common.c.