This graph shows which files directly or indirectly include 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)

void	free_trace_structs (void)

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

void	free_chunk_memory_trace (void)

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 898 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 785 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) {
         vpr_printf(TIO_MESSAGE_ERROR, "in alloc_and_load_rr_node_route_structs: old rr_node_route_inf array exists.\n");
         exit(1);
     }
 
     rr_node_route_inf = (t_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_POSITIVE_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 ( void )

Definition at line 623 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 991 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_chunk_memory_trace ( void )

Definition at line 1287 of file route_common.c.

                                    {
     if (trace_ch.chunk_ptr_head != NULL) {
         free_chunk_memory(&trace_ch);
     }
 }

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 1019 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 828 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 733 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);
 
     if(trace_head) {
         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 587 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;
 
     if(trace_head == NULL) {
         return;
     }
 
     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 )

Definition at line 949 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. */
             vpr_printf(TIO_MESSAGE_WARNING, "Empty heap occurred in get_heap_head.\n");
             vpr_printf(TIO_MESSAGE_WARNING, "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 532 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 394 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) {
         vpr_printf(TIO_MESSAGE_ERROR, "in init_route_structs. List of modified rr nodes is not empty.\n");
         exit(1);
     }
 
     if (heap_tail != 1) {
         vpr_printf(TIO_MESSAGE_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 1028 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 944 of file route_common.c.

                             {
     return (boolean)(heap_tail == 1);
 }

void mark_ends ( int inet )

Definition at line 546 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 <= 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
	)

Definition at line 562 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 363 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 315 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 **	clb_opins_used_locally
	)

Definition at line 1208 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 )

Definition at line 490 of file route_common.c.

                             {
 
     /* The routine sets the path_cost to HUGE_POSITIVE_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_POSITIVE_FLOAT;
             mod_ptr = mod_ptr->next;
 #ifdef DEBUG
             num_mod_ptrs++;
 #endif
         }
         *(mod_ptr->fptr) = HUGE_POSITIVE_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 )

Definition at line 809 of file route_common.c.

                                        {
 
     /* Allocates some extra information about each rr_node that is used only   *
      * during routing.                                                         */
 
     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_POSITIVE_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
	)

Definition at line 421 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) {
         vpr_printf(TIO_MESSAGE_ERROR, "in update_traceback. Expected type = SINK (%d).\n", SINK);
         vpr_printf(TIO_MESSAGE_ERROR, "\tGot 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 23 of file route_common.c.

t_rr_node_route_inf* rr_node_route_inf

Definition at line 21 of file route_common.c.

Data Structures

Functions

Variables

Function Documentation

Variable Documentation