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

/*
  November 2006		Modified by Yu Chi Wai at the Imperial
					College of London to support adding 
					virtual embedded block (VEB) to the circuit
 */

#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 if (block[iblk].type == DSP) {
      startidx=0;
      endidx=block[iblk].num_nets-1;
      block_timing[iblk].net_pin_index=(int*)my_malloc((endidx+1)*sizeof(int));
    } else if (block[iblk].type == MEMORY) {
      startidx=0;
      endidx=block[iblk].num_nets-1;
      block_timing[iblk].net_pin_index=(int*)my_malloc((endidx+1)*sizeof(int));
	} else if (block[iblk].type == VEB) {
      startidx=0;
      endidx=block[iblk].num_nets-1;
      block_timing[iblk].net_pin_index=(int*)my_malloc((endidx+1)*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 if (block[blk].type == DSP) {
			startidx=0;
			endidx=block[blk].num_of_each_type[0];
			for (blockpin=startidx;blockpin<=endidx;blockpin++){
				if (block[blk].nets[blockpin] == inet){
					block_timing[blk].net_pin_index[blockpin]=netpin;
				}
			}
		} else if (block[blk].type == MEMORY) {
			startidx=0;
			endidx=block[blk].num_of_each_type[0] +
				   block[blk].num_of_each_type[1];
			for (blockpin=startidx;blockpin<=endidx;blockpin++){
				if (block[blk].nets[blockpin] == inet){
			      block_timing[blk].net_pin_index[blockpin]=netpin;
				}
			}
		}else if (block[blk].type == VEB) {
			startidx=0;
			endidx=block[blk].num_of_each_type[0];
			for (blockpin=startidx;blockpin<=endidx;blockpin++){
				if (block[blk].nets[blockpin] == inet){
					block_timing[blk].net_pin_index[blockpin]=netpin;
				}
			}
		} 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;
  int i;

  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 == DSP)
      block_in_count[blkidx]=block[blkidx].num_of_each_type[0];
    else if (block[blkidx].type == MEMORY)
      block_in_count[blkidx]=block[blkidx].num_of_each_type[0]
                              +block[blkidx].num_of_each_type[1];
	else if (block[blkidx].type == VEB)
      block_in_count[blkidx]=block[blkidx].num_of_each_type[0];
    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 {
      if (block[blkidx].type == DSP) {
  		block_out_count[blkidx]=0;

         for(i=0;i<block[blkidx].num_of_each_type[0];i++) {
            outnet=block[blkidx].nets[i];

            if (!is_clock[outnet])
			   block_out_count[blkidx] +=net[outnet].num_pins-1;
		}
      } else if (block[blkidx].type == MEMORY) {
  		block_out_count[blkidx]=0;
			for(i=0;i<block[blkidx].num_of_each_type[0]+
				block[blkidx].num_of_each_type[1];i++) {
				outnet=block[blkidx].nets[i];

				if (!is_clock[outnet])
					block_out_count[blkidx] +=net[outnet].num_pins-1;
			}
		
	  } else if (block[blkidx].type == VEB) {
  		block_out_count[blkidx]=0;

         for(i=0;i<block[blkidx].num_of_each_type[0];i++) {
            outnet=block[blkidx].nets[i];

            if (!is_clock[outnet])
			   block_out_count[blkidx] +=net[outnet].num_pins-1;
		}
      } 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;
  int i;

  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;
    }
    else if (block[blkidx].type == DSP) {
       if (block[blkidx].num_of_each_type[2] > 0) {
/*          for(i=0;i<block[blkidx].num_out;i++) {*/
             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;
/*          }*/
       }
    } else if (block[blkidx].type == MEMORY) {
       if (block[blkidx].num_of_each_type[3] > 0) {
/*          for(i=0;i<block[blkidx].num_out;i++) {*/
             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;
/*          }*/
       }
    }
	else if (block[blkidx].type == VEB) {
       if (block[blkidx].num_of_each_type[2] > 0) {
/*          for(i=0;i<block[blkidx].num_out;i++) {*/
             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) {

      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;
    }
    else if (block[blkidx].type == DSP) {
       if (block[blkidx].num_of_each_type[2] > 0) {
         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;
       }
    }
    else if (block[blkidx].type == MEMORY) {
       if (block[blkidx].num_of_each_type[3] > 0) {
         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;
       }
    }
	else if (block[blkidx].type == VEB) {
       if (block[blkidx].num_of_each_type[2] > 0) {
         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;
  int si,ei,i;


  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 == DSP) {
       si = block[parent_block].num_of_each_type[0]; 
       ei = block[parent_block].num_of_each_type[1] + si - 1;
    } else if (block[parent_block].type == MEMORY) {
       si = block[parent_block].num_of_each_type[0] +
            block[parent_block].num_of_each_type[1]; 
       ei = block[parent_block].num_of_each_type[2] + si - 1;
	} else if (block[parent_block].type == VEB) {
       si = block[parent_block].num_of_each_type[0]; 
       ei = block[parent_block].num_of_each_type[1] + si - 1;
    } else {
       si = 0;
       ei = 0;
    }

    for(i=si;i<=ei;i++) {
    if (block[parent_block].type == OUTPAD)
      outnet=OPEN;
    else
      outnet=block[parent_block].nets[i];

    /*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 if (block[sink_block].type == DSP) {
      startidx=0;
      endidx = block[sink_block].num_of_each_type[0]-1;
    } else if (block[sink_block].type == MEMORY) {
      startidx=0;
      endidx = block[sink_block].num_of_each_type[0] +
               block[sink_block].num_of_each_type[1]-1;
	} else if (block[sink_block].type == VEB) {
      startidx=0;
      endidx = block[sink_block].num_of_each_type[0]-1;
    } 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])
	    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 if (block[iblk].type == DSP) {
		startidx=0;
		endidx=block[iblk].num_of_each_type[0]-1;
      } else if (block[iblk].type == MEMORY) {
		startidx=0;
		endidx=block[iblk].num_of_each_type[0] +
               block[iblk].num_of_each_type[1]-1;
	  } else if (block[iblk].type == VEB) {
		startidx=0;
		endidx=block[iblk].num_of_each_type[0]-1;
      } 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 if (block[iblk].type == DSP) {
		startidx=0;
		endidx=block[iblk].num_of_each_type[0]-1;
      } else if (block[iblk].type == MEMORY) {
		startidx=0;
		endidx=block[iblk].num_of_each_type[0] +
               block[iblk].num_of_each_type[1]-1;
	  } else if (block[iblk].type == VEB) {
		startidx=0;
		endidx=block[iblk].num_of_each_type[0]-1;
      } 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.*/

  vpr_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 if (block[blkidx].type == DSP) {
		startidx=0;
		endidx=block[blkidx].num_of_each_type[0]-1;
    } else if (block[blkidx].type == MEMORY) {
		startidx=0;
		endidx=block[blkidx].num_of_each_type[0] +
               block[blkidx].num_of_each_type[1]-1;
	} else if (block[blkidx].type == VEB) {
		startidx=0;
		endidx=block[blkidx].num_of_each_type[0]-1;
    } 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 if (block[blkidx].type == DSP) {
		startidx=0;
		endidx=block[blkidx].num_of_each_type[0]-1;
    } else if (block[blkidx].type == MEMORY) {
		startidx=0;
		endidx=block[blkidx].num_of_each_type[0] + 
               block[blkidx].num_of_each_type[1]-1;
	} else if (block[blkidx].type == VEB) {
		startidx=0;
		endidx=block[blkidx].num_of_each_type[0]-1;
    } 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]);

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

  fclose(debuglogfile);

}
#endif



/*****************************************/
#ifdef CRITICAL_LENGTH_STATS
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) {

  static int previous_cluster = -1;
  int cluster_num;
  cluster_num = num_clusters - 1;

  if (cluster_num != previous_cluster) {
    previous_cluster = cluster_num;
    fprintf (length_f, "\n");
  }

  fprintf (length_f, "%7d %7d  %7.2f %7d %8.5f %8.5f\n", 
	   cluster_num, num_blocks_clustered,
	   farthest_distance, num_critical_conn, avg_dist_to_sinks, 
	   avg_point_to_point_dist);

}
#endif
/******************** Globally Accessable Function Definitions *******************/
/*****************************************/
int get_net_pin_number(int blk, int blkpin) {
  /*returns the pin number in the net structure that the pin on this block */
  /*corresponds to */

  return(block_timing[blk].net_pin_index[blkpin]);

}

/*****************************************/
float get_net_pin_forward_criticality(int netnum, int pinnum) {
  /*returns the criticality for a particular branch of a net*/

  return(net_timing[netnum].net_forward_criticality[pinnum]);

}
/*****************************************/
float get_net_pin_backward_criticality(int netnum, int pinnum) {
  /*returns the criticality for a particular block*/

   return(net_timing[netnum].net_backward_criticality[pinnum]);
}
/*****************************************/
boolean report_critical_path(float block_delay, float inter_cluster_net_delay, 
			  float intra_cluster_net_delay, int farthest_block,
			  int cluster_size, boolean print_data) {
  /*finds the most critical path (longest path) and reports the length, and *
   *which blocks and nets are used by the path. */

  /*If all blocks on critical path have been clustered this function returns TRUE*
   *otherwise it returns FALSE.*/

  /*do not delete this function, as it is required to know when the critical path has been*/
  /*minimized as much as it possibly can -- this allows us to go into pin-sharing mode and*/
  /*save execution time */


  int pinidx; 
  int currentblock;
  int nextblock;
  int startidx, endidx;
  int inputnet, inputnetpin;
  int critnet;
  int numclusters, num_clusterable_blocks_on_path;
  int total_num_blocks_on_path, num_ext_nets_on_path;
  float mostcrit, netcrit;
  int cluster_of_nextblock;
  boolean all_clustered;
  boolean first_pass;

  all_clustered=TRUE;
  first_pass = TRUE;

#ifdef CRITICAL_PATH_STATS
  if (print_data) {
    fprintf(critical_report_f,"Using the following values, the most critical "
	    "path is determined\n");

    fprintf(critical_report_f,"block_delay=             %5.2f\n",block_delay);
    fprintf(critical_report_f,"inter_cluster_net_delay= %5.2f\n",inter_cluster_net_delay);
    fprintf(critical_report_f,"intra_cluter_net_delay=  %5.2f\n\n",intra_cluster_net_delay);

    fprintf(critical_report_f,"Critical path is reported from output to input\n\n");
  }
#endif

  if (get_cluster_of_block(farthest_block) == NEVER_CLUSTER){
    numclusters=0;
  }
  else{
    numclusters=1;
  }

  num_ext_nets_on_path=0;
  currentblock=farthest_block;
  num_clusterable_blocks_on_path=0;
  total_num_blocks_on_path=0;

  while (1) {
#ifdef CRITICAL_PATH_STATS
    if (print_data) {
      fprintf(critical_report_f,"Block #%5d \tName:%14s \tArrival Time=%7.2f "
	      "\tCluster=%5d\n",
	      currentblock,block[currentblock].name,
	      block_timing[currentblock].delay_from_source,
	      get_cluster_of_block(currentblock));
    }
#endif

    if (get_cluster_of_block(currentblock) == NO_CLUSTER)
      all_clustered=FALSE;

    total_num_blocks_on_path++;

    if (get_cluster_of_block(currentblock) != NEVER_CLUSTER)
      num_clusterable_blocks_on_path++;

    if (block_is_in_initial_source_q[currentblock] && !first_pass) {
      /*we have found the source of this critical path, we are done*/
      break;
    }
 
    first_pass = FALSE;


    if (block[currentblock].type == OUTPAD){
      startidx=0;
      endidx=0;
    } else if (block[currentblock].type == DSP) {

		startidx=0;
		endidx=block[currentblock].num_of_each_type[0]-1;
    } else if (block[currentblock].type == MEMORY) {

		startidx=0;
		endidx=block[currentblock].num_of_each_type[0] +
               block[currentblock].num_of_each_type[1]-1;
	} else if (block[currentblock].type == VEB) {
		startidx=0;
		endidx=block[currentblock].num_of_each_type[0]-1;
    } else {
      startidx=1;
      endidx=lut_size;
    }
    mostcrit=0.0;

    nextblock = NO_CLUSTER; 
    critnet = NO_CLUSTER;

    for (pinidx=startidx; pinidx<=endidx; pinidx++) {
      inputnet=block[currentblock].nets[pinidx];
      if (inputnet != OPEN) {
	inputnetpin=block_timing[currentblock].net_pin_index[pinidx];
	netcrit=net_timing[inputnet].net_forward_criticality[inputnetpin];
	if (netcrit > mostcrit) {
	  mostcrit=netcrit;
	  nextblock=net[inputnet].pins[0];
	  critnet=inputnet;
	}
      }
    }

    if (nextblock != NO_CLUSTER)
      cluster_of_nextblock=get_cluster_of_block(nextblock);
    else 
      cluster_of_nextblock = NO_CLUSTER;

    if (cluster_of_nextblock == NO_CLUSTER ||
	get_cluster_of_block(currentblock) != cluster_of_nextblock){
      if (cluster_of_nextblock != NEVER_CLUSTER){
	numclusters++;
      }
      num_ext_nets_on_path++;
    }

#ifdef CRITICAL_PATH_STATS
    if (print_data) {
      fprintf(critical_report_f,"Net   #%5d \tName:%14s \tCriticality =%9.5f\n", critnet, 
	      net[critnet].name, mostcrit);
    }
#endif
    currentblock=nextblock;
  }

#ifdef CRITICAL_PATH_STATS
  if (print_data) {
    fprintf(critical_report_f, "\n\n%d clusterable blocks packed into %d Clusters of size %d\n", 
	    num_clusterable_blocks_on_path, numclusters, cluster_size);
    fprintf(critical_report_f, "Total Number of Blocks on Crit Path= %d\n",
	    total_num_blocks_on_path);
    fprintf(critical_report_f, "Number of external nets on Crit Path=%d\n",
	    num_ext_nets_on_path);
  }
  fflush(critical_report_f);

  if (print_data)
    fprintf(critical_report_f,"\n\n");
#endif

  return all_clustered;

}

/*****************************************/
void calculate_timing_information(float block_delay, float inter_cluster_net_delay, 
				  float intra_cluster_net_delay,
				  int num_clusters,
				  int num_blocks_clustered,
				  int *farthest_block_discovered){
  /*This should be called whenever it is desired to have the timing and delay *
   *values updated */

  float max_arrival_time;
  long biggest_num_max_inputs;
  long biggest_num_max_outputs;
  long sum_biggest_max;
  float farthest_distance;
  float avg_dist_of_sinks, avg_point_to_point_dist;
  int num_critical_connections;

  reset_blocks_to_initial_state();

  /*first find distances from sources*/

  distance_from_sources(&max_arrival_time, block_delay, inter_cluster_net_delay, 
			intra_cluster_net_delay, 
			farthest_block_discovered, 
			&biggest_num_max_inputs,
			&farthest_distance,
			&avg_dist_of_sinks,
			&avg_point_to_point_dist);

  /*now find distances from sinks*/

  assign_required_arrival_times_to_max(max_arrival_time);

  update_required_arrival_times(block_delay, inter_cluster_net_delay, 
				intra_cluster_net_delay, &biggest_num_max_outputs);
  
  sum_biggest_max = biggest_num_max_inputs+biggest_num_max_outputs;

  calculate_slack_and_criticality(inter_cluster_net_delay, intra_cluster_net_delay, 
				  max_arrival_time, sum_biggest_max, 
				  &num_critical_connections);

  sort_blocks_by_criticality();

#ifdef CRITICAL_LENGTH_STATS
  print_stats(num_blocks_clustered, num_clusters,
	      farthest_distance, num_critical_connections, avg_dist_of_sinks, 
	      avg_point_to_point_dist);
#endif

#ifdef DEBUG_PATH_LENGTH
  /*output debugging information*/
  output_structures();

#endif
}

float get_criticality(int blkidx)
{
  return(criticality[blkidx]);
}


float get_next_criticality()
{
  int critidx, blkidx;

  for (critidx=indexofcrit; critidx<num_blocks; critidx++) 
  {
    blkidx=critindexarray[critidx];
    if (get_cluster_of_block(blkidx) == NO_CLUSTER) 
    {
      return(criticality[blkidx]);
    }
  }

  return -1.0;
}

int get_most_critical_unclustered_block() 
{
  /*calculate_timing_information must be called before this, or this function*
   *will return garbage */

  /*indexofcrit is a global variable that is reset to 0 each time a          *
   *timing analysis is done (reset in  sort_blocks_by_criticality)           */
 
  int critidx, blkidx;

  for (critidx=indexofcrit; critidx<num_blocks; critidx++) {
    blkidx=critindexarray[critidx];
    if (get_cluster_of_block(blkidx) == NO_CLUSTER) {
      indexofcrit=critidx+1;
      return(blkidx);
    }
  }

  /*if it makes it to here , there are no more blocks available*/
  return(NO_CLUSTER);
}


void alloc_and_init_path_length(int lut_sz, boolean *is_clk){
  /*this only needs to be called once*/

  lut_size=lut_sz;
  is_clock=is_clk;
  
#ifdef CRITICAL_PATH_STATS
  critical_report_f = my_fopen("vpack_critical_path.echo","w",0);
#endif

#ifdef CRITICAL_LENGTH_STATS
  length_f = my_fopen("vpack_critical_length.echo","w",0);

  fprintf(length_f, "%7s %7s %7s %7s %8s %8s\n",
	  "", "Num","","Num","Avg", "Avg");
  fprintf(length_f, "%7s %7s %7s %7s %8s %8s\n",
	  "Cluster","Blocks","Crit","Crit", "Dist","Pt to Pt");
  fprintf(length_f, "%7s %7s %7s %7s %8s %8s\n",
	  "Num","Packed","Dist","Conn","Sinks","Dist");
  fprintf(length_f, "%7s %7s %7s %7s %8s %8s\n",
	  "-------","-------","-------","-------",
	  "--------","--------");
#endif

  alloc_and_init_structures();
  get_sources_and_sinks();
  set_block_input_output_counts();
}
/******************************/

void free_path_length_memory(void){
  /*this should only be called when the internal structures are no longer required*/

  int iblk, inet;

  free(block_has_distance_q);
  free(block_has_req_arr_time_q);
  free(block_in_remaining);
  free(block_out_remaining);
  free(block_in_count);
  free(block_out_count);
  free(block_is_in_distance_q);
  free(block_is_in_initial_source_q);
  free(block_is_in_initial_sink_q);
  free(block_is_in_req_arr_time_q);
  free(criticality);
  free(critindexarray);

  for (iblk=0; iblk<num_blocks;iblk++)
    free(block_timing[iblk].net_pin_index);
  free(block_timing);

  for (inet=0;inet<num_nets;inet++) {
    free(net_timing[inet].net_pin_arrival_time);
    free(net_timing[inet].net_slack);
    free(net_timing[inet].net_forward_criticality);
    free(net_timing[inet].net_backward_criticality);
  }
  free(net_timing);

#ifdef CRITICAL_PATH_STATS
  fclose(critical_report_f);
#endif

#ifdef CRITICAL_LENGTH_STATS
  fclose(length_f);
#endif
}
