route_common.c

fpga设计评估软件

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

 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;
}


static void add_to_heap (struct s_heap *hptr) {

/* Adds an item to the heap, expanding the heap if necessary.             */

 int ito, ifrom;
 struct s_heap *temp_ptr;
   
 if (heap_tail > heap_size ) {          /* Heap is full */
    heap_size *= 2;
    heap = my_realloc ((void *)(heap + 1), heap_size * 
       sizeof (struct s_heap *));
    heap--;     /* heap goes from [1..heap_size] */
 }

 heap[heap_tail] = hptr;
 ifrom = heap_tail;
 ito = ifrom/2;
 heap_tail++;

 while ((ito >= 1) && (heap[ifrom]->cost < heap[ito]->cost)) {
    temp_ptr = heap[ito];
    heap[ito] = heap[ifrom];
    heap[ifrom] = temp_ptr;
    ifrom = ito;
    ito = ifrom/2;
 } 
}


struct s_heap *get_heap_head (void) {

/* 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);
}


void empty_heap (void) {

 int i;

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

 heap_tail = 1;
}

#define NCHUNK 200  /* # of various structs malloced at a time. */


static struct s_heap *alloc_heap_data (void) {

 int i;
 struct s_heap *temp_ptr;

 if (heap_free_head == NULL) {   /* No elements on the free list */
    heap_free_head = (struct s_heap *) my_malloc (NCHUNK *
       sizeof(struct s_heap));

/* If I want to free this memory, I have to store the original pointer *
 * somewhere.  Not worthwhile right now -- if you need more memory     *
 * for post-routing stages, look into it.                              */

    for (i=0;i<NCHUNK-1;i++) 
       (heap_free_head + i)->u.next = heap_free_head + i + 1;
    (heap_free_head + NCHUNK - 1)->u.next = NULL;
 }

 temp_ptr = heap_free_head;
 heap_free_head = heap_free_head->u.next;
#ifdef DEBUG
    num_heap_allocated++;
#endif
 return (temp_ptr);
}


void free_heap_data (struct s_heap *hptr) {

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


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


static struct s_trace *alloc_trace_data (void) {

 int i;
 struct s_trace *temp_ptr;
 
 if (trace_free_head == NULL) {   /* No elements on the free list */
    trace_free_head = (struct s_trace *) my_malloc (NCHUNK *
       sizeof(struct s_trace));
 
/* If I want to free this memory, I have to store the original pointer *
 * somewhere.  Not worthwhile right now -- if you need more memory     *
 * for post-routing stages, look into it.                              */
 
    for (i=0;i<NCHUNK-1;i++)
       (trace_free_head + i)->next = trace_free_head + i + 1;
    (trace_free_head + NCHUNK-1)->next = NULL;
 }
 temp_ptr = trace_free_head;
 trace_free_head = trace_free_head->next;
#ifdef DEBUG
    num_trace_allocated++;
#endif
 return (temp_ptr);
}


static void free_trace_data (struct s_trace *tptr) {

/* Puts the traceback structure pointed to by tptr on the free list. */
 
 tptr->next = trace_free_head;
 trace_free_head = tptr;
#ifdef DEBUG
    num_trace_allocated--;
#endif
}


static struct s_linked_f_pointer *alloc_linked_f_pointer (void) {
 
/* This routine returns a linked list element with a float pointer as *
 * the node data.                                                     */
 
 int i;  
 struct s_linked_f_pointer *temp_ptr;
 
 if (linked_f_pointer_free_head == NULL) {
    /* No elements on the free list */
    linked_f_pointer_free_head = (struct s_linked_f_pointer *)
        my_malloc (NCHUNK * sizeof(struct s_linked_f_pointer));
 
/* If I want to free this memory, I have to store the original pointer *
 * somewhere.  Not worthwhile right now -- if you need more memory     * 
 * for post-routing stages, look into it.                              */
 
    for (i=0;i<NCHUNK-1;i++) {
       (linked_f_pointer_free_head + i)->next = linked_f_pointer_free_head
                          + i + 1;
    }
    (linked_f_pointer_free_head + NCHUNK-1)->next = NULL;
 }
 
 temp_ptr = linked_f_pointer_free_head;
 linked_f_pointer_free_head = linked_f_pointer_free_head->next;
 
#ifdef DEBUG     
    num_linked_f_pointer_allocated++;
#endif

 return (temp_ptr);
}


void print_route (char *route_file) {

/* Prints out the routing to file route_file.  */

 int inet, inode, ipin, bnum, ilow, jlow, blk_pin, iclass;
 t_rr_type rr_type;
 struct s_trace *tptr;
 char *name_type[] = {"SOURCE", "SINK", "IPIN", "OPIN", "CHANX","CHANY"};
 FILE *fp;

 fp = my_fopen (route_file, "w", 0);

 fprintf (fp, "Array size: %d x %d logic blocks.\n", nx, ny);
 fprintf(fp,"\nRouting:");
 for (inet=0;inet<num_nets;inet++) {
    if (is_global[inet] == FALSE) {
       fprintf(fp, "\n\nNet %d (%s)\n\n",inet, net[inet].name);
       tptr = trace_head[inet]; 

       while (tptr != NULL) {
          inode = tptr->index;
          rr_type = rr_node[inode].type;
          ilow = rr_node[inode].xlow;
          jlow = rr_node[inode].ylow;
          
          fprintf(fp, "%6s (%d,%d) ", name_type[rr_type], ilow, jlow);

          if ((ilow != rr_node[inode].xhigh) || (jlow != 
                    rr_node[inode].yhigh)) 
             fprintf (fp, "to (%d,%d) ", rr_node[inode].xhigh, 
                  rr_node[inode].yhigh);

          switch (rr_type) {
          
          case IPIN: case OPIN:
             if (clb[ilow][jlow].type == CLB) {
                fprintf (fp, " Pin: ");
             }
             else {   /* IO Pad. */
                fprintf (fp, " Pad: ");
             }
             break;

          case CHANX: case CHANY:
             fprintf (fp, " Track: "); 
             break;

          case SOURCE: case SINK:
             if (clb[ilow][jlow].type == CLB) {
                fprintf (fp, " Class: ");
             }
             else {   /* IO Pad. */
                fprintf (fp, " Pad: ");
             }
             break;

          default:
             printf ("Error in print_route:  Unexpected traceback element "
                     "type: %d (%s).\n", rr_type, name_type[rr_type]);
             exit (1);
             break;
          }

          fprintf(fp, "%d  ", rr_node[inode].ptc_num);

/* Uncomment line below if you're debugging and want to see the switch types *
 * used in the routing.                                                      */
/*          fprintf (fp, "Switch: %d", tptr->iswitch);    */
          
          fprintf (fp, "\n");

          tptr = tptr->next;
       }
    }

    else {    /* Global net.  Never routed. */
       fprintf(fp, "\n\nNet %d (%s): global net connecting:\n\n", inet,
              net[inet].name);

       for (ipin=0;ipin<net[inet].num_pins;ipin++) {
          bnum = net[inet].blocks[ipin];
          if (block[bnum].type == CLB) {
             blk_pin = net[inet].blk_pin[ipin];
             iclass = clb_pin_class[blk_pin];
          }
          else {              /* IO pad */
             iclass = OPEN;   /* Class not relevant */
          }
     
          fprintf(fp, "Block %s (#%d) at (%d, %d), Pin class %d.\n",
             block[bnum].name, bnum, block[bnum].x, block[bnum].y, 
             iclass);
       }
    }
 }

 fclose (fp);

#ifdef DEBUG
   fp = my_fopen ("mem.echo","w",0);
   fprintf(fp, "\nNum_heap_allocated: %d   Num_trace_allocated: %d\n",
      num_heap_allocated, num_trace_allocated);
   fprintf(fp, "Num_linked_f_pointer_allocated: %d\n", 
      num_linked_f_pointer_allocated);
   fclose (fp);
#endif

}


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

/* If some subblock outputs are hooked directly to CLB outputs, then      *
 * some CLB outputs are occupied if their associated subblock is used     *
 * locally, even though the inter-CLB 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 CLB 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;

 if (rip_up_local_opins) {
    for (iblk=0;iblk<num_blocks;iblk++) {
       for (iclass=0;iclass<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++) {
    for (iclass=0;iclass<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_clb_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 ();
       }
    }
 }
}


static void adjust_one_rr_occ_and_pcost (int inode, int add_or_sub, float
            pres_fac) {

/* Increments or decrements (depending on add_or_sub) the occupancy of    *
 * one rr_node, and adjusts the present cost of that node appropriately.  */
 
 int occ, capacity;

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

 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;
 }
}