path_length.c

fpga设计评估软件

	    block_timing[block_discovered].num_max_outputs = 
	      block_timing[sink_block].num_max_outputs;
	  else
	    block_timing[block_discovered].num_max_outputs = 1;
	}

	if (block_timing[block_discovered].num_max_outputs > loc_biggest_num_max_outputs)
	  loc_biggest_num_max_outputs=block_timing[block_discovered].num_max_outputs;


	/* update arrival times of blocks that are not sinks *
	 * (sinks already have valid values)                 */
	if (!block_is_in_initial_sink_q[block_discovered])
	  if (block_timing[block_discovered].required_arrival_time > required_arrival_t)
	    block_timing[block_discovered].required_arrival_time=required_arrival_t;


	if (block_out_remaining[block_discovered] == 0) {

	  /*previously added blocks are not added to the queue.*/
	  if (!block_is_in_req_arr_time_q[block_discovered]){
	    block_has_req_arr_time_q[next_blk_to_add_to_req_arr_time_q]=block_discovered;
	    next_blk_to_add_to_req_arr_time_q++;
	    block_is_in_req_arr_time_q[block_discovered]=TRUE;
	  }
	}
      } /* block[sink_block]...*/
  
    } /*for (i=start....*/

    q_head++;
  }

  *biggest_num_max_outputs=loc_biggest_num_max_outputs;
}
/******************************/
static void calculate_slack_and_criticality(float inter_cluster_net_delay,
					    float intra_cluster_net_delay,
					    float max_arrival_time, 
					    long sum_biggest_max,
					    int *num_critical_connections) {
  /*assign slack and criticality values to the net_timing structure. It *
   *is calculated for each pin on each net except for the pins which    *
   *are driving the net (they are left at the undefined value of -1).   *
   *Also compute for the criticality array (which is parallel to the    *
   *block array) */

  /*The criticality of a block is determined primarily by the slack on  *
   *it's input nets using the one that has the smallest value. It is    *
   * modified as described below.                                       */


  /*Criticality is determined by three factors.                         *
   *1. The most important, and most highly weighted factor is the slack *
   *   on the nets. A net with very little slack will be assigned a high*
   *   criticality value, as will the block which is being driven by the*  
   *   net.                                                             *
   *The next two factors are used only as a tie-breaking mechanisim for *
   *nets that have the same criticality values. They will never cause a *
   *net with more slack to become more critical than a net with less    *
   *slack.                                                              *
   *2. The number of paths passing through a block adjacent to a net is *
   *   the primary tie breaker for selecting between nets that have     *
   *   equal slacks. The net_forward_criticality of a net is affected   *
   *   by the block driving the net, the net_backward_criticality is    *
   *   affected by the block that is being driven by the net.           *
   *   There are two parameters which keep track of the number of paths *
   *   which pass through a block. The num_max_inputs keeps track of how*
   *   many paths that are on the input side of each block that can be  *
   *   be affected by making a block clustered. The num_max_outputs     *
   *   keeps track of how many paths that are on the output side of each*
   *   block that can be affected by making a block clustered. We weight*
   *   blocks that affect more paths slightly higher than blocks that   *
   *   do not affect as many.                                           *
   *3. Given that there is more than one net with the same slack, and *
   *   same number of paths, the third, and least weighted tie breaker  *
   *   is the distance from the sources. If two blocks have the same    *
   *   value for num_max_inputs and num_max_outputs, then the farther of*
   *   the two blocks and the nets that they are driving are assigned a *
   *   slightly higher criticality.                                     *
   *   Remember, that this is only a tie breaker if number 1. and 2. are*
   *   equal, otherwise it has no effect. The weighting of this         *
   *   parameter is set in SCALE_DISTANCE_VAL, which is small enough to *
   *   ensure that it is only a tie breaker.                            */

  int iblk,iblkpin;
  int startidx,endidx;
  int netpin;
  int currentnet;
  int drivingblock;

  static float *max_num_paths_scaling_value=NULL;
  static float *distance_scaling_value=NULL;

  float currslack, maxslack, minslack;
  float currcriticality;

  int critical_connection_count;

  critical_connection_count = 0;


  /*find slack values*/

  maxslack=0.0;
  minslack = MAX_ALLOWED_PATH_LEN;

  /*define the max_num_paths_scaling_value array if it is undefined*/
  if (max_num_paths_scaling_value == NULL) {
    max_num_paths_scaling_value=(float*)my_malloc(num_blocks * sizeof(float));
    distance_scaling_value=(float*)my_malloc(num_blocks * sizeof(float));
  }

  /*calculate slack values*/
  for (iblk=0;iblk<num_blocks;iblk++) {

    if (block[iblk].type != INPAD) {

      /*if this is an output pad, then the input to the pad is net[0]*/
      if (block[iblk].type == OUTPAD) {
	startidx=0;
	endidx=0;
      }
      else {
	startidx=1;
	endidx=lut_size;
      }


      for (iblkpin=startidx;iblkpin<=endidx;iblkpin++) {

	currentnet=block[iblk].nets[iblkpin];

	if (currentnet!=OPEN) {
	  
	  netpin=block_timing[iblk].net_pin_index[iblkpin];

	  currslack=block_timing[iblk].required_arrival_time-
	    net_timing[currentnet].net_pin_arrival_time[netpin];
	  
	  if (currslack < MIN_SLACK_ALLOWED) 
	    currslack = 0;
	 	  
	  net_timing[currentnet].net_slack[netpin] = currslack;

	  if (fabs(currslack - minslack) < EQUAL_DEF) {
	    critical_connection_count ++;
	  }
	  else if (currslack < minslack) {
	    minslack = currslack;
	    critical_connection_count = 1;
	  }

	  if (currslack > maxslack)
	    maxslack=currslack;
	}    
      }
    }
  }

  /*Initialize the scaling values*/
  for (iblk=0;iblk<num_blocks;iblk++) {

    max_num_paths_scaling_value[iblk]=
      SCALE_NUM_PATHS * 
      ((float)block_timing[iblk].num_max_inputs + 
      (float)block_timing[iblk].num_max_outputs)/(float)sum_biggest_max;

    distance_scaling_value[iblk]=
      SCALE_DISTANCE_VAL *
      block_timing[iblk].delay_from_source/max_arrival_time;
  }

  /*calculate criticality values*/

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

    if (block[iblk].type != INPAD) {

      /*if this is an output pad, then the input to the pad is net[0]*/
      if (block[iblk].type == OUTPAD) {
	startidx=0;
	endidx=0;
      }
      else {
	startidx=1;
	endidx=lut_size;
      }

      for (iblkpin=startidx;iblkpin<=endidx;iblkpin++) {

	currentnet=block[iblk].nets[iblkpin];

	if (currentnet != OPEN) {

	  drivingblock=net[currentnet].pins[0];

	  netpin=block_timing[iblk].net_pin_index[iblkpin];

	  currslack=net_timing[currentnet].net_slack[netpin];


	  /*calculate the criticality of the nets*/

	  /*Net forward criticality tie-breakers are determined by the block *
	   *that is driving the net    */
	  if (maxslack > MIN_SLACK_ALLOWED)
	    currcriticality= (1-currslack/maxslack)+ 
	      max_num_paths_scaling_value[drivingblock] +
	      distance_scaling_value[drivingblock];
	  else
	    currcriticality=1.0 + max_num_paths_scaling_value[drivingblock] +
	      distance_scaling_value[drivingblock];

	  net_timing[currentnet].net_forward_criticality[netpin]=currcriticality; 
	  

	  /*now calculate the criticality of the blocks, and the *
	  * net_backward_criticality values*/

	  /*net_backward_criticality tie-breakers are determined by the block*
	   *that is being driven by the net */

	  /*block criticality tie-breakers are determined by the block under *
           *consideration. Most of the criticality score of a block is       *
	   *determined by the slack on the input net with the smallest       *
           *slack value */
	  if (maxslack > MIN_SLACK_ALLOWED)
	    currcriticality= (1-currslack/maxslack)+ 
	      max_num_paths_scaling_value[iblk] +
	      distance_scaling_value[iblk];
	  else
	    currcriticality=1.0 + max_num_paths_scaling_value[iblk] +
	      distance_scaling_value[iblk];

	  net_timing[currentnet].net_backward_criticality[netpin]=currcriticality; 

	  if (get_cluster_of_block(iblk) == NO_CLUSTER) {
	    if (currcriticality > criticality[iblk]) {
	     criticality[iblk] = currcriticality;
	    }
	  }	  
	}  
      }
    }
  }
  
  *num_critical_connections = critical_connection_count;
}

/******************************/
static void sort_blocks_by_criticality(void) {
  /*sorts the critindex array such that the first value is the position in the *
   *criticality array of the most critical block, and the last value is the    *
   *position in the criticality array of the least critical block, blocks that *
   *have already been clustered have been assigned a criticality of -1 so that *
   *they will appear at the end of the sorted list.*/

  heapsort(critindexarray, criticality, num_blocks);
  indexofcrit=0;

}

/******************************/
#ifdef DEBUG_PATH_LENGTH

static void output_structures(void) {

  /*This function prints out the internal net_timing and block_timing data  *
   *values. If a value is -1 (for slack or criticality) then the value is   *
   *undefined, this is expected on the outputs of blocks.                   */
 
  int blkidx,blkpinidx; 
  int netpin;
  int currentnet;
  static FILE *debuglogfile;

  int startidx, endidx;

 
  debuglogfile=my_fopen("debugPL.log","w",0);

  fprintf(debuglogfile,"BEWARE that this file only represents the final values\n\n");

  /*for each block, print out Required arrival time, and slack on each input*/
  fprintf(debuglogfile,"\n\n    NAME            TYPE Dist From    Required Arrive");
  for (blkpinidx=0;blkpinidx<=lut_size;blkpinidx++)
    fprintf(debuglogfile, " slack[%2d]",blkpinidx);
  fprintf(debuglogfile,"\n");
  fprintf(debuglogfile,"                           Source           Time\n\n");

  for (blkidx=0; blkidx<num_blocks; blkidx++) {
    fprintf(debuglogfile,"%2d: %-15.15s %4d %9.2f %18.2f",blkidx,block[blkidx].name, 
	    block[blkidx].type, block_timing[blkidx].delay_from_source,
	    block_timing[blkidx].required_arrival_time);

    /*if this is an output pad, then the input to the pad is block[].nets[0]*/
    if (block[blkidx].type == OUTPAD){
      startidx=0;
      endidx=0;
    }
    else { 
      startidx=0;
      endidx=lut_size;  /* ignore clock nets (which would be in block[].nets[lut+1] )*/
    }
	   

    /*INPADs do not have inputs, so ignore*/
    if (block[blkidx].type != INPAD) {
      for (blkpinidx=startidx;blkpinidx<=endidx;blkpinidx++) {

	currentnet=block[blkidx].nets[blkpinidx];

	if (currentnet != OPEN) { 
	  netpin=block_timing[blkidx].net_pin_index[blkpinidx];
	  fprintf(debuglogfile,"%9.2f ",net_timing[currentnet].net_slack[netpin]);
	}
	else
	  fprintf(debuglogfile,"          ");

      }
    }
    fprintf(debuglogfile,"\n");
  }


  /*print out criticalities of each net*/
  fprintf(debuglogfile,"\n\n    NAME            ");
  for (blkidx=0;blkidx<=lut_size;blkidx++)
    fprintf(debuglogfile, "Crit[%2d] ",blkidx);
  fprintf(debuglogfile,"\n");
  for (blkidx=0; blkidx<num_blocks; blkidx++) {

    fprintf(debuglogfile,"%2d: %-15.15s",blkidx,block[blkidx].name);

    /*if this is an output pad, then the input to the pad is block[].nets[0]*/
    if (block[blkidx].type == OUTPAD){
      startidx=0;
      endidx=0;
    }
    else { 
      startidx=0;
      endidx=lut_size;  /* ignore clock nets (which would be in block[].nets[lut+1] )*/
    }

    /*INPADs do not have inputs, so ignore*/
    if (block[blkidx].type != INPAD) {

      for (blkpinidx=startidx;blkpinidx<=endidx;blkpinidx++) {

	currentnet=block[blkidx].nets[blkpinidx];

	if (currentnet != OPEN) { 

	  netpin=block_timing[blkidx].net_pin_index[blkpinidx];
	  fprintf(debuglogfile,"%8.2f ",
		  net_timing[currentnet].net_forward_criticality[netpin]);