path_length.c

fpga设计评估软件

      block_has_req_arr_time_q[q_next_sink_to_add]=blkidx;
      q_next_sink_to_add++;

      block_is_in_initial_sink_q[blkidx]=TRUE;
    }
    /*mark other sinks*/
    else if (is_clock[block[blkidx].nets[0]] && block[blkidx].type != INPAD){ 
      /*output from this block is a clock, consider this block a sink*/

      block_has_req_arr_time_q[q_next_sink_to_add]=blkidx;
      q_next_sink_to_add++;

      block_is_in_initial_sink_q[blkidx]=TRUE;
    }  
  }

  initial_num_sinks_in_q=q_next_sink_to_add;
  initial_num_sources_in_q=q_next_source_to_add;
}

/******************************/
static void reset_blocks_to_initial_state(void) {
  /*this procedure sets up the structures so that a new timing analysis can *
   *be done, basically it sets the structures to the state that they were in*
   *after the calls to get_sources_and_sinks, and                           *
   *set_block_input_output_counts                                           */

  int blkidx;

  for (blkidx=0;blkidx<num_blocks;blkidx++){
    block_in_remaining[blkidx]=block_in_count[blkidx];
    block_out_remaining[blkidx]=block_out_count[blkidx];
    block_is_in_distance_q[blkidx]=block_is_in_initial_source_q[blkidx];
    block_is_in_req_arr_time_q[blkidx]=block_is_in_initial_sink_q[blkidx];
    block_timing[blkidx].delay_from_source= 0.0;
    block_timing[blkidx].num_max_inputs=1;
    block_timing[blkidx].num_max_outputs=1;
    criticality[blkidx]= -1.0;
    
  }
}
/******************************/
static float calculate_arrival_time_at_each_pin(int block_discovered,
						int parent_block, float block_delay,
						float inter_cluster_net_delay,
						float intra_cluster_net_delay,
						float *point_to_point_dist_sum) {

  /*Calculate the arrival time at each discovered block*/

  float arrival_t;
  int cluster_of_block_discovered;



  cluster_of_block_discovered=get_cluster_of_block(block_discovered);

  if (cluster_of_block_discovered != NO_CLUSTER &&
      cluster_of_block_discovered == get_cluster_of_block(parent_block)){
    /*the block discovered is in the same cluster as it's parent block*/
    (*point_to_point_dist_sum) += intra_cluster_net_delay + block_delay;

    if (!block_is_in_initial_source_q[parent_block]){
      arrival_t=block_timing[parent_block].delay_from_source +
	intra_cluster_net_delay + block_delay;
    }
    else{ /*the parent is a source, so it contributes no previous delay*/
      arrival_t=intra_cluster_net_delay+block_delay;
    }
  }
  else {/*the discovered block is in a different cluster from the parent block*/
    (*point_to_point_dist_sum) += inter_cluster_net_delay + block_delay;

    if (!block_is_in_initial_source_q[parent_block]){
      arrival_t=block_timing[parent_block].delay_from_source +
	inter_cluster_net_delay+block_delay;	   
    }
    else{ /*the parent is a source, so it contributes no previous delay*/
      arrival_t=inter_cluster_net_delay+block_delay;
    }
  }

  return arrival_t;
}
/******************************/
static void update_paths_through_each_block(int block_discovered, int parent_block,
					    float arrival_time,
					    int *loc_biggest_num_max_inputs)
{

  /*Update the number of paths through each block*/

	  /*check for approximate equality*/
  if (fabs(block_timing[block_discovered].delay_from_source - 
	   arrival_time) <EQUAL_DEF){
    if (!block_is_in_initial_source_q[parent_block])
      block_timing[block_discovered].num_max_inputs +=
	block_timing[parent_block].num_max_inputs;
    else
      block_timing[block_discovered].num_max_inputs += 1;
  }
  else if (block_timing[block_discovered].delay_from_source < arrival_time) {
    if (!block_is_in_initial_source_q[parent_block])
      block_timing[block_discovered].num_max_inputs = 
	block_timing[parent_block].num_max_inputs;
    else
      block_timing[block_discovered].num_max_inputs = 1;
  }

  if (block_timing[block_discovered].num_max_inputs > *loc_biggest_num_max_inputs)
    *loc_biggest_num_max_inputs=block_timing[block_discovered].num_max_inputs;

	 

}

/******************************/
static int calculate_sink_dist_sum(void) {

  int sum, idx, blknum;

  sum = 0;
  
  for (idx = 0; idx<initial_num_sinks_in_q; idx++) {
    blknum = block_has_req_arr_time_q[idx];
    sum += block_timing[blknum].delay_from_source;
  }
  return sum;
}
/******************************/
static void distance_from_sources(float* maximum_arrival_time, float block_delay,
				  float inter_cluster_net_delay, 
				  float intra_cluster_net_delay,
				  int *farthest_block_discovered,
				  long *biggest_num_max_inputs,
				  float *farthest_distance,
				  float *avg_dist_of_sinks,
				  float *avg_point_to_point_dist){

  /*calculate the distances from sources */
  /*maximum_arrival_time returns the distance of the farthest sink*/

  /*This algorithm traverses the netlist from sources using a breadth first traversal*
   *which adds blocks to the block_has_distance_q. Blocks which are farther from     *
   *the sources are added to the queue last. By farther, I am not talking about delay*
   *but rather I am talking about number of blocks between the source and a block    */

  int netpinidx, q_head, outnet, parent_block;
  int block_discovered;
  int startidx,endidx;
  int next_blk_to_add_to_dist_q;
  int farthest_block;
  int loc_biggest_num_max_inputs;

  float arrival_time,max_arrival_time, farthest_delay;
  float sink_dist_sum, point_to_point_dist_sum;
  int point_to_point_num;



  max_arrival_time=0.0;
  farthest_delay = 0.0;
  farthest_block=0;
  q_head=0;
  loc_biggest_num_max_inputs=0;

  sink_dist_sum = 0.0;
  point_to_point_dist_sum = 0.0;
  point_to_point_num = 0;

  next_blk_to_add_to_dist_q=initial_num_sources_in_q;

  while (q_head < next_blk_to_add_to_dist_q) {

    parent_block=block_has_distance_q[q_head];

    /*if this is an outpad then nets[0] is actually an input to the pad, not an output*/
    if (block[parent_block].type == OUTPAD)
      outnet=OPEN;
    else
      outnet=block[parent_block].nets[0];


    /*ignore clock nets, and open nets*/
    if (outnet != OPEN) { 
      if (!is_clock[outnet]) {

	startidx=1;
	endidx=net[outnet].num_pins-1; /* subtract 1 to keep in range*/

	for (netpinidx=startidx;netpinidx<=endidx;netpinidx++){
	  block_discovered=net[outnet].pins[netpinidx];

	  /*Calculate the arrival time at each discovered pin of each block*/
	  arrival_time = calculate_arrival_time_at_each_pin(block_discovered, parent_block, 
							    block_delay, 
							    inter_cluster_net_delay, 
							    intra_cluster_net_delay,
							    &point_to_point_dist_sum);
	  point_to_point_num ++;

	  /*Update the number of paths through each block*/
	  update_paths_through_each_block(block_discovered, parent_block, arrival_time, 
					  &loc_biggest_num_max_inputs);
	  

	  net_timing[outnet].net_pin_arrival_time[netpinidx]=arrival_time;


	  if (arrival_time > block_timing[block_discovered].delay_from_source){
	    block_timing[block_discovered].delay_from_source=arrival_time;
	  }


	  if (fabs(arrival_time - max_arrival_time) >=  EQUAL_DEF && arrival_time > max_arrival_time){
	      max_arrival_time=arrival_time;
	      farthest_block=block_discovered;
	  }

	  block_in_remaining[block_discovered]--;

	  if (block_in_remaining[block_discovered] == 0) {
	    /*all inputs have been discovered, we now know how far this block is from an input*/
	    /*do not add previously added blocks to the queue.*/
	    if (!block_is_in_distance_q[block_discovered]){
	      block_has_distance_q[next_blk_to_add_to_dist_q]=block_discovered;
	      next_blk_to_add_to_dist_q++;
	      block_is_in_distance_q[block_discovered]=TRUE;
	    }
	  }

#ifdef DEBUG
	  else if (block_in_remaining[block_discovered]<0) {
	    printf("ERROR in distance_from_sources, a block has been discovered"
                   "more times than its number of inputs warrants\n");
	    exit(1);
	  }
#endif

	} /*for.....*/
      } /*!is_clock....*/
    } /*outnet...*/

    /*on the first call of this procedure, we print out some statistics*
     *about the circuit which we are packing*/
    q_head++;

  } /*while ....*/

  sink_dist_sum = calculate_sink_dist_sum();

  *farthest_distance = max_arrival_time;
  *farthest_block_discovered=farthest_block;
  *maximum_arrival_time=max_arrival_time;
  *biggest_num_max_inputs=loc_biggest_num_max_inputs;
  *avg_dist_of_sinks = sink_dist_sum / (float)initial_num_sinks_in_q;
  *avg_point_to_point_dist = point_to_point_dist_sum / (float)point_to_point_num;
}

/******************************/
static void assign_required_arrival_times_to_max(float max_arrival_time) {
  /*this procedure assigns max_arrival_time to the required_arrival_time*
   *for all blocks. For any blocks that are not sinks, this value will  *
   *be changed in the update_required_arrival_times procedure. It is    *
   *necessary to assign this "upper bound" value here, so that the      *
   *algorithm can find the smallest required_arrival_time for each node */

  int i;
  
  for (i=0; i<num_blocks; i++)
    block_timing[i].required_arrival_time = max_arrival_time;
}

/******************************/
static void update_required_arrival_times(float block_delay, 
					  float inter_cluster_net_delay, 
					  float intra_cluster_net_delay,
					  long *biggest_num_max_outputs){
  /*calculate the required arrival times for each block*/

  /*this procedure traverses the netlist in a breadth first manner from the sinks*/

  int i, q_head, innet,sink_block;
  int block_discovered;
  int startidx, endidx;
  int next_blk_to_add_to_req_arr_time_q;
  int netpin;
  int cluster_of_block_discovered;
  int loc_biggest_num_max_outputs;

  float required_arrival_t;



  q_head=0;
  next_blk_to_add_to_req_arr_time_q=initial_num_sinks_in_q;
  loc_biggest_num_max_outputs=0;


  while (q_head<next_blk_to_add_to_req_arr_time_q ) {

    sink_block=block_has_req_arr_time_q[q_head];
   
    /*there are no inputs to an inpad*/ 
    if (block[sink_block].type == INPAD) {
      q_head++;
      continue;
    }

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


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

      /*ignore OPEN nets*/
      if (block[sink_block].nets[i] != OPEN) {

	innet=block[sink_block].nets[i];

	block_discovered=net[innet].pins[0];


	netpin=block_timing[sink_block].net_pin_index[i];

	cluster_of_block_discovered=get_cluster_of_block(block_discovered);

	if (cluster_of_block_discovered != NO_CLUSTER &&
	    cluster_of_block_discovered == get_cluster_of_block(sink_block)){
	  required_arrival_t=block_timing[sink_block].required_arrival_time-
	    intra_cluster_net_delay-block_delay;
	}
	else{
	  required_arrival_t=block_timing[sink_block].required_arrival_time-
	    inter_cluster_net_delay-block_delay;
	}

	block_out_remaining[block_discovered]--;


	if (fabs(block_timing[block_discovered].delay_from_source - 
		                               required_arrival_t) < EQUAL_DEF){
	  if (!block_is_in_initial_sink_q[sink_block])
	    block_timing[block_discovered].num_max_outputs +=
	      block_timing[sink_block].num_max_outputs;
	  else
	    block_timing[block_discovered].num_max_outputs += 1;
	}
	else if (block_timing[block_discovered].required_arrival_time > required_arrival_t) {
	  if (!block_is_in_initial_sink_q[sink_block])