cluster.c

fpga设计评估软件

#include <stdio.h>
#include "util.h"
#include "vpack.h"
#include "globals.h"
#include "cluster.h"
#include "output_clustering.h"
#include "path_length.h"


enum e_gain_update {GAIN, NO_GAIN};
enum e_feasibility {FEASIBLE, INFEASIBLE};
enum e_gain_type {HILL_CLIMBING, NOT_HILL_CLIMBING};
enum e_removal_policy {REMOVE_CLUSTERED, LEAVE_CLUSTERED};
enum e_net_relation_to_clustered_block {INPUT, OUTPUT};


/* Linked list structure.  Stores one integer (iblk). */
struct s_ilink {int iblk; struct s_ilink *next;};

/* 1/MARKED_FRAC is the fraction of nets or blocks that must be *
 * marked in order for the brute force (go through the whole    *
 * data structure linearly) gain update etc. code to be used.   *
 * This is done for speed only; make MARKED_FRAC whatever       *
 * number speeds the code up most.                              */
#define MARKED_FRAC 2   

/* [0..num_blocks-1].  Which cluster (numbered from 0 to num_cluster - 1) *
 * is this block in?  If not assigned to a cluster yet, it is NO_CLUSTER. *
 * this value is also used in path_length.c*/
int *cluster_of_block;

/* [0..num_nets-1].  How many pins of each net are contained in the *
 * currently open cluster?                                          */
static int *num_pins_of_net_in_cluster;

/* [0..num_nets-1].  Is the driver for this net in the open cluster? */
static boolean *net_output_in_cluster;

/* [0..num_blocks-1]. How suitable is this block for absorbtion into the*
 * current cluster. Calculated using the cost function                  *
 * gain[i]=alpha*lengthgain[i] + (1-alpha)*sharinggain[i]/(lut_size+x)  *
 * where alpha is the tradeoff variable that determines wheter timing or*
 * area is more important, and x is 1 if gloabal clocks, 2 otherwise */
static float *gain;


/* [0..num_blocks-1]. What is the criticality score of this block? This*
 * is determined by the most critical net between this block and any   *
 * block in the current cluster */
static float *lengthgain;


/* [0..num_blocks-1]. How many connections will be absorbed if this block*
 * is placed in the cluster under consideration */
static int *connectiongain;

/* [0..num_blocks-1]. How many nets on this block are already in the    *
 * cluster under consideration */
static int *sharinggain;

/* [0..num_blocks-1]. This is the gain used for hill-climbing. It stores*
 * the reduction in the number of pins that adding this block to the the*
 * current cluster will have. This reflects the fact that sometimes the *
 * addition of a block to a cluster may reduce the number of inputs     *
 * required if it shares inputs with all other BLEs and it's output is  *
 * used by all other BLEs in the cluster.                               */
static int *hillgain;

/* [0..num_marked_nets] and [0..num_marked_blocks] respectively.  List  *
 * the indices of the nets and blocks that have had their num_pins_of_  *
 * net_in_cluster and gain entries altered.                             */
static int *marked_nets, *marked_blocks;
static int num_marked_nets, num_marked_blocks;

/* To speed up some linear searches and such, I store the index of the *
 * first clusterable (LUT, LATCH, etc.) block.                         */
static int first_clusterable_block = -1;

/* Keeps a linked list of the unclustered blocks to speed up looking for *
 * unclustered blocks with a certain number of *external* inputs.        *
 * [0..lut_size].  Unclustered_list_head[i] points to the head of the    *
 * list of LUTs with i inputs to be hooked up via external interconnect. */
static struct s_ilink *unclustered_list_head;
static struct s_ilink *memory_pool; /*Declared here so I can free easily.*/


/* What is the increase in a blocks gain for each net that it shares    *
 * with blocks that are already in the cluster. Set to be               *
 * (1-alpha)/(lut_size+x), where x is 1 if global clocks, or 2 otherwise*/   
static float gain_for_each_net_shared;

/* Does the block that drives the output of this net also appear as a   *
 * receiver (input) pin of the net?  [0..num_nets-1].  This is used     *
 * in the gain routines to avoid double counting the connections from   *
 * the current cluster to other blocks (hence yielding better           *
 * clusterings).  The only time a block should connect to the same net  *
 * twice is when one connection is an output and the other is an input, *
 * so this should take care of all multiple connections.                */
static boolean *net_output_feeds_driving_block_input;
/*****************************************/
/*globally accessable function*/
int num_input_pins (int iblk) {

/* Returns the number of used input pins on this block. */

 int conn_inps;

 switch (block[iblk].type) {

 case LUT:
    conn_inps = block[iblk].num_nets - 1;   /* -1 for output. */
    break;

 case LUT_AND_LATCH:
    conn_inps = block[iblk].num_nets - 2;  /* -2 for output + clock */
    break;

 case LATCH:
    conn_inps = block[iblk].num_nets - 2;  /* -2 for output + clock */
    break;

 default:
/* This routine should only be used for logic blocks. */
    printf("Error in num_input_pins:  Unexpected block type %d"
           "\n for block %d.  Aborting.\n", block[iblk].type, iblk);
    exit(1);
    break;
 }
 
 return (conn_inps);
}
/*****************************************/
/*globally accessable function*/
int get_cluster_of_block(int blkidx) {

  return(cluster_of_block[blkidx]);
}

/*****************************************/
static int num_ext_inputs (int iblk, int lut_size) {

/* Returns the number of input pins on this block that must be hooked * 
 * up through external interconnect.  That is, the number of input    *
 * pins used - the number which connect (internally) to the output.   */

 int ext_inps, output_net, ipin;

 ext_inps = num_input_pins(iblk);

 output_net = block[iblk].nets[0];
 
/* NB:  I could speed things up a bit by computing the number of inputs *
 * and number of external inputs for each logic block at the start of   *
 * clustering and storing them in arrays.  Look into if speed is a      *
 * problem.                                                             */

 for (ipin=1;ipin<=lut_size;ipin++) {
    if (block[iblk].nets[ipin] == output_net)
       ext_inps--;
 }

 return (ext_inps);
}


/*****************************************/
static void check_clocks (boolean *is_clock, int lut_size) {

/* Checks that nets used as clock inputs to latches are never also used *
 * as LUT inputs.  It's electrically questionable, and more importantly *
 * would break the clustering code.                                     */

 int inet, iblk, ipin;

 for (iblk=0;iblk<num_blocks;iblk++) {
    if (block[iblk].type == LUT || block[iblk].type == LATCH || 
             block[iblk].type == LUT_AND_LATCH) {
       for (ipin=1;ipin<lut_size+1;ipin++) {
          inet = block[iblk].nets[ipin]; 
          if (inet != OPEN) {
             if (is_clock[inet]) {
                printf("Error in check_clocks.  Net %d (%s) is a clock, but "
                       "also\n"
                       "\tconnects to a LUT input on block %d (%s).\n", inet, 
                       net[inet].name, iblk, block[iblk].name);
                printf("This would break the current clustering "
                       "implementation and is electrically\n"
                       "\tquestionable, so clustering has been aborted.\n");
                exit (1);
             }
          }
       }
    }
 }
}


/*****************************************/
static void check_for_duplicate_inputs (int lut_size) {

/* Checks that each input pin of a LUT connects to a distinct net.  *
 * It doesn't make sense from a tech-mapping point of view to feed  *
 * the same input into a LUT more than once, and more importantly,  *
 * some of the clustering code assumes that all LUT inputs are      *
 * unique.                                                          */

 int iblk, ipin, inet;
 int *num_conns_to_net;
 
 num_conns_to_net = (int*) my_malloc (num_nets * sizeof(net));

 for (inet=0;inet<num_nets;inet++) 
    num_conns_to_net[inet] = 0;

 for (iblk=0;iblk<num_blocks;iblk++) {
    if (block[iblk].type == LUT || block[iblk].type == LATCH ||
          block[iblk].type == LUT_AND_LATCH) {
       for (ipin=1;ipin<=lut_size;ipin++) {
          inet = block[iblk].nets[ipin];
          if (inet != OPEN) {
             num_conns_to_net[inet]++;
             if (num_conns_to_net[inet] != 1) {
                printf("\nError in check_for_duplicate_inputs.\n"
                       "Block #%d (%s) connects multiple input pins to"
                       " net #%d (%s).\n", iblk, block[iblk].name, inet,
                           net[inet].name);
                printf("Multiple connections to a LUT's inputs doesn't "
                       "make sense from a technology \n"
                       "mapping standpoint, and the clusterer assumes "
                       "LUT inputs are unique.\n"
                       "Aborting.\n");
                exit(1);
             }
          }
       }

/* Reset count for next block. */
       for (ipin=1;ipin<=lut_size;ipin++) {
          inet = block[iblk].nets[ipin];
          if (inet != OPEN) 
             num_conns_to_net[inet] = 0;
       }
    }
 }

 free (num_conns_to_net);
}


/*****************************************/
static void alloc_and_init_clustering (int lut_size, int cluster_size,
				       boolean global_clocks, float alpha) {

/* Allocates the main data structures used for clustering and properly *
 * initializes them.                                                   */

 int i, ext_inps, ipin, driving_blk, inet;
 struct s_ilink *next_ptr;

 cluster_of_block = (int *) my_malloc (num_blocks * sizeof(int));
 gain = (float *) my_malloc (num_blocks * sizeof (float));
 lengthgain=(float*) my_malloc (num_blocks * sizeof (float));
 sharinggain=(int*) my_malloc (num_blocks * sizeof (int));
 hillgain =(int*) my_malloc (num_blocks * sizeof (int));
 connectiongain = (int*) my_malloc (num_blocks * sizeof (int));


 if (global_clocks)
   gain_for_each_net_shared=(1.0-alpha)/(float)(lut_size+1);
 else
   gain_for_each_net_shared=(1.0-alpha)/(float)(lut_size+2);

 for (i=0;i<num_blocks;i++) {

    gain[i] = 0.0;
    lengthgain[i]= 0.0;
    connectiongain[i] = 0;
    sharinggain[i]=NOT_VALID;
    hillgain[i]=NOT_VALID;

    if (block[i].type == LUT || block[i].type == LUT_AND_LATCH ||
                 block[i].type == LATCH) {
        cluster_of_block[i] = NO_CLUSTER;
        if (first_clusterable_block == -1)
           first_clusterable_block = i;
    }
    else
        cluster_of_block[i] = NEVER_CLUSTER; 
 }

#ifdef DEBUG
    if (first_clusterable_block != num_p_inputs + num_p_outputs) {
       printf("Error in alloc_and_init_clustering.\n");
       printf("first_clusterable_block = %d, expected %d.\n",
            first_clusterable_block, num_p_inputs + num_p_outputs);
       exit (1);
    }
#endif

 num_pins_of_net_in_cluster = (int *) my_malloc (num_nets * sizeof(int));
 net_output_in_cluster = (boolean *) my_malloc (num_nets * sizeof(boolean));

 for (i=0;i<num_nets;i++) {
    num_pins_of_net_in_cluster[i] = 0;
    net_output_in_cluster[i] = FALSE;
 }

 marked_nets = (int *) my_malloc ((lut_size + 2) * cluster_size * sizeof(int));
 marked_blocks = (int *) my_malloc (num_blocks * sizeof(int));

 num_marked_nets = 0;
 num_marked_blocks = 0;

 unclustered_list_head = (struct s_ilink *) my_malloc ((lut_size+1) * 
                        sizeof(struct s_ilink));
 for (i=0;i<=lut_size;i++)
    unclustered_list_head[i].next = NULL;
 
 memory_pool = (struct s_ilink *) my_malloc ((num_blocks - 
             first_clusterable_block) * sizeof (struct s_ilink));
 next_ptr = memory_pool;
 
 for (i=first_clusterable_block;i<num_blocks;i++) {
    if (block[i].type == LUT || block[i].type == LUT_AND_LATCH ||
                 block[i].type == LATCH) {
       ext_inps = num_ext_inputs(i, lut_size);
       next_ptr->next = unclustered_list_head[ext_inps].next;
       unclustered_list_head[ext_inps].next = next_ptr;
       next_ptr->iblk = i;
       next_ptr++;
    }
 }


 net_output_feeds_driving_block_input = (boolean *) my_malloc (
                 num_nets * sizeof (boolean));

 for (inet=0;inet<num_nets;inet++) {
    net_output_feeds_driving_block_input[inet] = FALSE;
    driving_blk = net[inet].pins[0];
    for (ipin=1;ipin<net[inet].num_pins;ipin++) {
       if (net[inet].pins[ipin] == driving_blk) {
          net_output_feeds_driving_block_input[inet] = TRUE;
          break;
       }
    }
 }
}


/*****************************************/
static void free_clustering (void) {

/* Releases all the memory used by clustering data structures.   */

 free (cluster_of_block);
 free (gain);
 free (hillgain);
 free (lengthgain);
 free (sharinggain);
 free (connectiongain);
 free (num_pins_of_net_in_cluster);
 free (net_output_in_cluster);
 free (marked_nets);
 free (marked_blocks);
 free (unclustered_list_head);
 free (memory_pool); 
 free (net_output_feeds_driving_block_input);
}


/*****************************************/
static boolean clocks_feasible (int iblk, int idummy, int clocks_avail,
                int lut_size, boolean *dummy) {

/* Checks if block iblk could be adding to the open cluster without *
 * violating clocking constraints.  Returns TRUE if it's OK.  Some  *
 * parameters are unused since this function needs the same inter-  *
 * face as the other feasibility checkers.                          */

 int inet;
 
/* Recall that LUT output can't internally connect to clocks. */

 inet = block[iblk].nets[lut_size+1];
 if (inet != OPEN) {
    if (num_pins_of_net_in_cluster[inet] == 0) {
       clocks_avail--;
    }   
    else if (num_pins_of_net_in_cluster[inet] == 1 &&
                net_output_in_cluster[inet]) {
       clocks_avail--;
    }   
 }

 if (clocks_avail >= 0) 
    return (TRUE);
 else
    return (FALSE);
}


/*****************************************/
static int get_block_by_num_ext_inputs (int ext_inps, int lut_size, int 
      clocks_avail, enum e_removal_policy remove_flag) {