SRC/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	free_trace_structs (void)
void	reserve_locally_used_opins (float pres_fac, boolean rip_up_local_opins, t_ivec **fb_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

)

Definition at line 1018 of file route_common.c.

{

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

    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

)

Definition at line 909 of file route_common.c.

{

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

    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 empty_heap

(

void

)

Definition at line 1127 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 1173 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

)

Definition at line 939 of file route_common.c.

{

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

    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

)

Definition at line 847 of file route_common.c.

{
    /*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 */
    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

)

Definition at line 680 of file route_common.c.

{

/* 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.            */

    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]

Definition at line 1077 of file route_common.c.

{

/* 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.                                   */

    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

)

Definition at line 611 of file route_common.c.

{

/* Returns the *congestion* cost of using this rr_node. */

    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

)

Definition at line 451 of file route_common.c.

{

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

    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
	)

Definition at line 1185 of file route_common.c.

{

/* 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.                                */

    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

)

Definition at line 1071 of file route_common.c.

{
    return (heap_tail == 1);
}

Here is the caller graph for this function:

void mark_ends

(

int

inet

)

Definition at line 628 of file route_common.c.

{

/* 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).                      */

    int ipin, inode;

    for(ipin = 1; ipin <= 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
	)

Definition at line 648 of file route_common.c.

{

/* 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.           */

    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
	)

Definition at line 412 of file route_common.c.

{

/* 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.                                                                     */

    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
	)

Definition at line 355 of file route_common.c.

{

/* 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.                                    */

    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 **	fb_opins_used_locally
	)

Definition at line 1418 of file route_common.c.

{

/* If some subblock outputs are hooked directly to FB outputs, then      *
 * some FB outputs are occupied if their associated subblock is used     *
 * locally, even though the inter-FB netlist does not say those outputs  *
 * have to connect to anything.  This is important when you have          *
 * logically equivalent outputs.  Code below makes sure any FB outputs   *
 * that are used by being directly hooked to subblocks get properly       *
 * reserved.                                                              */

    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 =
                                fb_opins_used_locally[iblk][iclass].nelem;
                            /* Always 0 for pads and for RECEIVER (IPIN) classes */
                            for(ipin = 0; ipin < num_local_opin; ipin++)
                                {
                                    inode =
                                        fb_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 =
                        fb_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);
                                    fb_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

)

Definition at line 564 of file route_common.c.

{

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

    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:

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

Definition at line 484 of file route_common.c.

{

/* 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).    */

    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

Definition at line 22 of file route_common.c.

t_rr_node_route_inf* rr_node_route_inf

Definition at line 20 of file route_common.c.