path_length.c

fpga设计评估软件

/*path_length.c                                                       *
 *originallly created April 16, 1998, Alexander (Sandy) Marquardt     *
 *calculates path lengths and block distances from inputs and outputs *
 *and determines net slacks, as well as criticalities of nets         */

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

#define CRITICAL_LENGTH_STATS  /*this controls whether or not the progam will */
                                    /*print out extra data about  the status of    */
                                    /*the packing after each timing-analysis       */
#define CRITICAL_PATH_STATS  /*print out blocks and nets that vpack thinks are*/
                                  /*the critical path before and after packing     */

/****************** Defines for this module ****************************************/

/*#define DEBUG_PATH_LENGTH 1*/          /*Tells path_length.c to output some   */
                                         /*useful data structures to debugPL.log*/

#define MAX_ALLOWED_PATH_LEN 10000.0/*really big number to initialize required      *
				      arrival times.                                */

/*The following defines assume that the user has assigned a inter_cluster_net_delay *
 *value of 1, and is using the intra_cluster_net_delay values to scale the ratio    *
 *between the two. It is strongly recommended that inter_cluster_net_delay be set to*
 *1 in all cases. */


#define MIN_SLACK_ALLOWED 1e-6  /*any slack values below this number are set to     *
				  *zero since the resulting value is caused by       *
				  *inaccuracies in floating point calculations       */
#define SCALE_NUM_PATHS 1e-2     /*this value is used as a multiplier to assign a    *
				  *slightly higher criticality value to nets that    *
				  *affect a large number of critical paths versus    *
				  *nets that do not have such a broad effect.        *
				  *Note that this multiplier is intentionally very   * 
				  *small compared to the total criticality because   *
				  *we want to make sure that net criticality is      *
				  *primarily determined by slacks, with this acting  *
				  *only as a tie-breaker between otherwise equal nets*/
#define SCALE_DISTANCE_VAL 1e-4  /*this value is used as a multiplier to assign a    *
				  *slightly higher criticality value to nets that    *
				  *are otherwise equal but one is  farther           *
				  *from sources (the farther one being made slightly *
				  *more critical)                                    */
#define EQUAL_DEF 1e-6            /*used in some if == equations to allow very       *
				   *close values to be considered equal              */


/****************** Structures for this module *************************************/

struct s_block_timing {float delay_from_source;
                       float required_arrival_time;
                       int *net_pin_index;  
                       long num_max_inputs;
                       long num_max_outputs;};
/* delay_from_source: delay to block's input from the farthest source    *
 * required_arrival_time: What is the latest that a signal can arrive at *
 *                   an input to this block without becoming critical    *
 * net_pin_index[]:  For each input on this block, this indicates which  *
 *                   pin in nets[].pins[] the input net is corresponds to*
 * num_max_inputs:   How many paths on the inputs to this block have the *
 *                   maximum arrival time of paths that are inputs to    *
 *                   this block.                            .            *
 * num_max_ouputs:   How many paths on the output from this block have   *
 *                   the smallest required arrival time of paths that are*
 *                   driven by this block                                */

struct s_net_timing {float* net_pin_arrival_time;
                     float* net_slack;
                     float* net_forward_criticality;
                     float* net_backward_criticality;};
/*net_pin_arrival_time[]:parallel array to s_net[].pins[]. When does the  *
 *                       output of this net become valid at the pin which *
 *                       it is driving.                                   *
 * net_slack[]:      [0..lut_size], required_arrival_time - net_arrival_  *
 *                   time.                                                *
 * net_forward_criticality[]:[0..lut_size], is set to                     *
 *                   (1-(slack/max_slack)) plus a tie breaker portion     *
 *                   determined by the block driving the net (see the     *
 *                   calculate_slack_and_criticality function for a       *
 *                   description of tie-breakers).                        *
 *                   this has a value between 0 and 1 with higher values  *
 *                   indicating a more critical net.                      *
 * net_backward_criticality[]: [0..lut_size], is set to                   *
 *                   (1-(slack/max_slack). plus a tie-breaker portion     *
 *                   determined by the block being driven by the net.     */


/****************** Variables Global to this module *******************************/
struct s_block_timing *block_timing;
struct s_net_timing *net_timing;

static int *block_has_distance_q; /*which blocks have been allocated distance      *
				  *from sources                                    */
static int *block_has_req_arr_time_q; /*which blocks have been allocated required  *
			               *arrival times                              */

static int *block_in_remaining; /*How many adjacent input blocks have not been     *
				 *discovered. Once all input blocks have been      *
				 *discovered, this block is added to the           *
				 *block_has_distance_q                             */
static int *block_out_remaining; /*How many adjacent blocks on the output net have *
				  *not been discovered yet. Once all output blocks *
				  *have been discovered, this block is added to the*
				  *block_has_req_arr_time_q                        */
static int *block_in_count;      /*How many inputs on this block are valid         */
static int *block_out_count;     /*How many blocks are being driven by the output  */

static boolean *block_is_in_initial_source_q;/*indicates whether a block is a      *
					      *  source or not                     */
static boolean *block_is_in_initial_sink_q;  /*indicates whether a block is a      *
				              *sink or not                         */
static boolean *block_is_in_distance_q;/*indicates whether a block has been        *
				      * already added to the block_has_distance_q  */
static boolean *block_is_in_req_arr_time_q;  /*indicates whether a block has been  *
				      *added to the the block_has_req_arr_time_q   */

static boolean *is_clock; /*pointer to the is_clock array declared in main function*/

static float *criticality; /* [0..num_blocks-1] keeps track of how critical each   *
			    * block is, this is primarily used for determining     *
			    * which block to use as a cluster seed.                *
			    * The criticality of a block is equal to the           *
			    * of the most critical net on its input pins.          */
static int *critindexarray; /* [0..num_blocks-1] Each value in this array is a     *
		             * pointer to the criticality array.  The index of the *
			     * most critical block is first, least critical last   */
static int indexofcrit;     /*next index in the critindexarray that will be  read  *
			     *this value is reset every time a new timing analysis *
			     *and sort is done. It is modified every time          *
			     *get_most_critical_block is called                    */

static int lut_size;      
static int initial_num_sinks_in_q; /* allows us to remember what blocks are sinks  *
				    * even after the queue has been expanded       */
static int initial_num_sources_in_q; /*ditto for sources                           */


#ifdef CRITICAL_PATH_STATS
static FILE *critical_report_f;  /*used for printing out the critical path details*/
#endif

#ifdef CRITICAL_LENGTH_STATS
static FILE *length_f;           /*records the length of the critical path as the *
				  *program proceeds */
#endif


/************* Declarations of subroutines local to this module *************/

static void print_stats(int num_blocks_clustered, int num_clusters,
                 float farthest_distance,
                 int num_critical_conn, float avg_dist_to_sinks,
		 float avg_point_to_point_dist);



/******************** Subroutine Definitions **************************************/

/******************************/

static void alloc_and_init_structures(void)
  /*allocates data structures required for timing analysis and initializes them to*
   *default values   */

{
  int iblk,netpin,inet,blockpin;
  int blk,ipin;
  int numpins;
  int startidx,endidx;

  block_has_distance_q=(int*)my_malloc(num_blocks*sizeof(int));
  block_has_req_arr_time_q=(int*)my_malloc(num_blocks*sizeof(int));
  block_in_remaining=(int*)my_malloc(num_blocks*sizeof(int));
  block_out_remaining=(int*)my_malloc(num_blocks*sizeof(int));
  block_in_count=(int*)my_malloc(num_blocks*sizeof(int));
  block_out_count=(int*)my_malloc(num_blocks*sizeof(int));

  /*calloc inits the following four arrays to FALSE*/
  block_is_in_initial_source_q=(boolean*)my_calloc(num_blocks,sizeof(boolean)); 
  block_is_in_initial_sink_q=(boolean*)my_calloc(num_blocks,sizeof(boolean));
  block_is_in_distance_q=(boolean*)my_calloc(num_blocks,sizeof(boolean)); 
  block_is_in_req_arr_time_q=(boolean*)my_calloc(num_blocks,sizeof(boolean));

  block_timing=(struct s_block_timing*)my_malloc(num_blocks*
					       sizeof(struct s_block_timing));
  criticality=(float*)my_malloc(num_blocks*sizeof(float));
  critindexarray=(int*)my_malloc(num_blocks*sizeof(int));


  /*initialize and allocate the block_timing internal structures*/
  for (iblk=0;iblk<num_blocks;iblk++){   
    
    block_timing[iblk].delay_from_source= -1.0;
    block_timing[iblk].required_arrival_time= MAX_ALLOWED_PATH_LEN;
    block_timing[iblk].num_max_inputs=1;
    block_timing[iblk].num_max_outputs=1;
    criticality[iblk]= -1.0;

    if (block[iblk].type==INPAD || block[iblk].type==OUTPAD){
      startidx=0;
      endidx=0;
      block_timing[iblk].net_pin_index=(int*)my_malloc(sizeof(int));
    }
    else {
      startidx=0;
      endidx=lut_size;
      block_timing[iblk].net_pin_index=(int*)my_malloc((lut_size+1)*sizeof(int));
    }

    for (ipin=startidx;ipin<=endidx;ipin++){
      block_timing[iblk].net_pin_index[ipin]=-1;
    }
  }

  /*update the block_timing.net_pin_index values*/
  for (inet=0;inet<num_nets;inet++) {
    if (net[inet].pins[0] != OPEN) {

      for (netpin=0;netpin<net[inet].num_pins;netpin++){
	blk=net[inet].pins[netpin];
	if (block[blk].type == INPAD)
	  block_timing[blk].net_pin_index[0]=0;  /*pin 0 of net is always on driving block*/
	else if (block[blk].type == OUTPAD)
	  block_timing[blk].net_pin_index[0]=netpin;
	else if (netpin == 0)
	  block_timing[blk].net_pin_index[0]=0;
        else{
	  startidx=1;
	  endidx=lut_size;
	  for (blockpin=startidx;blockpin<=endidx;blockpin++){
	    if (block[blk].nets[blockpin] == inet){
	      block_timing[blk].net_pin_index[blockpin]=netpin;
	    }
	  }
	}
      }
    }
  }
  

  /*allocate and initialize the net_timing structure*/
  net_timing=(struct s_net_timing*)my_malloc(num_nets*sizeof(struct s_net_timing));

  for (inet=0;inet<num_nets;inet++){

    numpins=net[inet].num_pins;

    net_timing[inet].net_pin_arrival_time=(float*)my_malloc(numpins*sizeof(float));
    net_timing[inet].net_slack=(float*)my_malloc(numpins*sizeof(float));
    net_timing[inet].net_forward_criticality=(float*)my_malloc(numpins*sizeof(float));
    net_timing[inet].net_backward_criticality=(float*)my_malloc(numpins*sizeof(float));

    for (ipin=0;ipin<numpins;ipin++) {
      net_timing[inet].net_pin_arrival_time[ipin]=0.0;
      net_timing[inet].net_slack[ipin]=-1.0;
      net_timing[inet].net_forward_criticality[ipin]=-1.0;
      net_timing[inet].net_backward_criticality[ipin]=-1.0;
    }
  }
}
/******************************/

static void set_block_input_output_counts(void)
  /*set number of inputs and outputs that a block can expect to have*/
{
  int blkidx;
  int outnet;

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

    /*set number of inputs for each block*/
    if (block[blkidx].type == OUTPAD)
      block_in_count[blkidx]=1;
    else if (block[blkidx].type == INPAD)
      block_in_count[blkidx]=0;
    else if (block[blkidx].type == LUT)
      block_in_count[blkidx]=block[blkidx].num_nets-1; /*-1 for output*/
    else if (block[blkidx].type == LATCH || block[blkidx].type == LUT_AND_LATCH)
      block_in_count[blkidx]=block[blkidx].num_nets-2; /*-2 for clock+output*/


    /*set number of outputs for each block*/
    if (block[blkidx].type == OUTPAD) {
      outnet=OPEN;
      block_out_count[blkidx]=0;
    }
    else {
      outnet=block[blkidx].nets[0];

      if (is_clock[outnet])
	/*ignore clock nets*/
	block_out_count[blkidx]=0;

      else if (block[blkidx].type == INPAD)
	block_out_count[blkidx]=1;  

      else
	block_out_count[blkidx]=net[outnet].num_pins-1;
    }  
  }
}


/******************************/
static void get_sources_and_sinks(void) {
  /*determines what blocks are sources, and which are sinks, and allocates *
   *the various queue structures to keep track of where the sources and    *
   *sinks are */


  int blkidx;
  int q_next_source_to_add;
  int q_next_sink_to_add;


  q_next_source_to_add=0;
  q_next_sink_to_add=0;

  /* If a block has no inputs, then it is considered to be a source (could happen */
  /* for a constant generator)     */

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

    block_is_in_initial_source_q[blkidx]=FALSE;
    block_is_in_initial_sink_q[blkidx]=FALSE;
    block_has_distance_q[blkidx]=-1;
    block_has_req_arr_time_q[blkidx]=-1;
    
    /*mark sources*/
    if (block[blkidx].type == INPAD || block[blkidx].type == LATCH || 
	block[blkidx].type == LUT_AND_LATCH) {

      block_has_distance_q[q_next_source_to_add]=blkidx;
      q_next_source_to_add++;
      block_timing[blkidx].delay_from_source=0.0;
      block_is_in_initial_source_q[blkidx]=TRUE;
    }
    /*mark other sources*/
    else if (block[blkidx].num_nets == 1 && block[blkidx].type != OUTPAD) { 
      /* a constant generator, consider it a source*/

      block_has_distance_q[q_next_source_to_add]=blkidx;
      q_next_source_to_add++;
      block_timing[blkidx].delay_from_source=0.0;
      block_is_in_initial_source_q[blkidx]=TRUE;
    }

    /*mark sinks*/
    if (block[blkidx].type == OUTPAD || block[blkidx].type == LATCH || 
	block[blkidx].type == LUT_AND_LATCH) {