cluster.c

fpga设计评估软件

                "%d is out of range.\n", icluster, iblk);
          exit (1);
       } 
 
       cluster_occupancy[icluster]++;
       if (cluster_occupancy[icluster] > cluster_size) {
          printf("Error in alloc_and_load_cluster_info:  "
                 "cluster %d contains more than\n"
                 "%d blocks.\n", icluster, cluster_size);
          exit (1);
       } 
       cluster_contents[icluster][cluster_occupancy[icluster]-1] = iblk;
 
    }
 
    else {    /* INPAD or OUTPAD */
       icluster = cluster_of_block[iblk];
       if (icluster != NEVER_CLUSTER) {
          printf("Error in alloc_and_load_cluster_info:  "
                 "block %d is a pad but has\n"
                 "been assigned to cluster %d.\n", iblk, icluster);
          exit (1);
       } 
    }
 }

 *cluster_occupancy_ptr = cluster_occupancy;
 *cluster_contents_ptr = cluster_contents;
}


/*****************************************/
static void check_clustering (int num_clusters, int cluster_size, 
        int inputs_per_cluster, int clocks_per_cluster, int lut_size,
        boolean *is_clock, int **cluster_contents, int *cluster_occupancy) {

/* This routine checks that the clustering we have found is indeed a *
 * legal clustering.  It also outputs various statistics about the   *
 * clustering.                                                       */
 
 int iblk, inet, icluster, i, ipin;
 int inputs_used, clocks_used;
 int max_inputs_used, min_inputs_used, summ_inputs_used;
 int max_clocks_used, min_clocks_used, summ_clocks_used;
 int max_occupancy, min_occupancy, num_logic_blocks;

/* Note:  some checking was already done in alloc_and_load_cluster_info. */

/* Brute-force reset of data structures I will need during checking.  */

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

/* Check that each cluster satisifies the input and clock pin  *
 * constraints and computes some statistics.                   */

 max_inputs_used = -1;
 max_clocks_used = -1;
 max_occupancy = -1;
 min_inputs_used = inputs_per_cluster + 1;
 min_clocks_used = clocks_per_cluster + 1;
 min_occupancy = cluster_size + 1;
 summ_inputs_used = 0;
 summ_clocks_used = 0;

 for (icluster=0;icluster<num_clusters;icluster++) {

    if (cluster_occupancy[icluster] <= 0) {
       printf("Error:  cluster %d contains %d logic blocks.\n", icluster, 
               cluster_occupancy[icluster]);
       exit (1);
    }

    inputs_used = 0; 

    clocks_used = 0;

    for (i=0;i<cluster_occupancy[icluster];i++) {
       iblk = cluster_contents[icluster][i];

       inet = block[iblk].nets[0];              /* Output */
       if (num_pins_of_net_in_cluster[inet] > 0 && !is_clock[inet]) 
          inputs_used--;
       num_pins_of_net_in_cluster[inet]++;
       net_output_in_cluster[inet] = TRUE;
       
       for (ipin=1;ipin<=lut_size;ipin++) {  /* LUT inputs */
          inet = block[iblk].nets[ipin];
          if (inet != OPEN) {
             if (num_pins_of_net_in_cluster[inet] == 0)  
                inputs_used++;
             num_pins_of_net_in_cluster[inet]++;
          }
       }

       inet = block[iblk].nets[lut_size+1];     /* Clock */
          if (inet != OPEN) {
             if (num_pins_of_net_in_cluster[inet] == 0 ||
                     (num_pins_of_net_in_cluster[inet] == 1 && 
                     net_output_in_cluster[inet])) 
                clocks_used++;
             num_pins_of_net_in_cluster[inet]++;
  
          }
    }

    if (inputs_used > inputs_per_cluster) {
       printf("Error in check_clustering:  cluster %d uses %d inputs.\n",
               icluster, inputs_used);
       exit (1);
    }
    if (clocks_used > clocks_per_cluster) {
       printf("Error in check_clustering:  cluster %d uses %d clocks.\n",
               icluster, clocks_used);
       exit (1);
    }
    
/* Reset data structures for check of next cluster */

    for (i=0;i<cluster_occupancy[icluster];i++) {
       iblk = cluster_contents[icluster][i];
       inet = block[iblk].nets[0];
       num_pins_of_net_in_cluster[inet] = 0;
       net_output_in_cluster[inet] = FALSE;

       for (ipin=1;ipin<=lut_size+1;ipin++) {
          inet = block[iblk].nets[ipin];
          if (inet != OPEN) 
             num_pins_of_net_in_cluster[inet] = 0;
       }
    }

/* Compute statistical information. */

    min_inputs_used = min (min_inputs_used, inputs_used);
    max_inputs_used = max (max_inputs_used, inputs_used);
    summ_inputs_used += inputs_used;

    min_clocks_used = min (min_clocks_used, clocks_used);
    max_clocks_used = max (max_clocks_used, clocks_used);
    summ_clocks_used += clocks_used;
 
    min_occupancy = min (min_occupancy, cluster_occupancy[icluster]);
    max_occupancy = max (max_occupancy, cluster_occupancy[icluster]);

 }      /* End for loop over all clusters. */


 printf("Completed clustering consistency check successfully.\n\n");

 printf("Clustering Statistics:\n\n");
 num_logic_blocks = num_blocks - num_p_inputs - num_p_outputs;
 printf("%d Logic Blocks packed into %d Clusters.\n", num_logic_blocks,
         num_clusters);
 printf("\n\t\t\tAverage\t\tMin\tMax\n");
 printf("Logic Blocks / Cluster\t%f\t%d\t%d\n", (float) num_logic_blocks /
        (float) num_clusters, min_occupancy, max_occupancy);
 printf("Used Inputs / Cluster\t%f\t%d\t%d\n", (float) summ_inputs_used /
        (float) num_clusters, min_inputs_used, max_inputs_used);
 printf("Used Clocks / Cluster\t%f\t%d\t%d\n", (float) summ_clocks_used / 
        (float) num_clusters, min_clocks_used, max_clocks_used);
 printf("\n");
}


/*****************************************/
/*globally accessable function*/
void do_clustering (int cluster_size, int inputs_per_cluster,
       int clocks_per_cluster, int lut_size, boolean global_clocks,
       boolean muxes_to_cluster_output_pins,
       boolean *is_clock, boolean hill_climbing_flag, 
       char *out_fname, boolean timing_driven, 
       enum e_cluster_seed cluster_seed_type, float alpha, 
       int recompute_timing_after, float block_delay, 
       float intra_cluster_net_delay, float inter_cluster_net_delay,
       boolean allow_unrelated_clustering, 
       boolean allow_early_exit, boolean connection_driven){

/* Does the actual work of clustering multiple LUT+FF logic blocks *
 * into clusters.                                                  */

  /*note: I allow timing_driven and connection_driven to be simultaneously true*/
  /*in this case, connection_driven is responsible for all clustering decisions*/
  /*but timing analysis is still enabled (useful for viewing the constant delay*/
  /*results) */

 int num_clusters, istart;
 int inputs_used, luts_used, clocks_used, next_blk;
 int *cluster_occupancy, **cluster_contents;
 int blocks_since_last_analysis;
 int farthest_block;
 int *block_in_cluster;
 int next_empty_location_in_cluster;
 int num_blocks_hill_added;
 int num_blocks_clustered;
 boolean critical_path_minimized, dummy_bool;
 boolean early_exit;

 check_clocks (is_clock, lut_size);
 check_for_duplicate_inputs (lut_size);
 alloc_and_init_clustering (lut_size, cluster_size, global_clocks, alpha);

 num_clusters = 0;
 next_empty_location_in_cluster = 0;
 blocks_since_last_analysis = 0;
 critical_path_minimized = FALSE;
 early_exit = FALSE;
 num_blocks_clustered = 0;
 num_blocks_hill_added = 0;

 block_in_cluster = (int*) my_malloc (cluster_size * sizeof (int));

 if (timing_driven){
					
   alloc_and_init_path_length(lut_size, is_clock);
   calculate_timing_information(block_delay, inter_cluster_net_delay, 
				intra_cluster_net_delay, 
				num_clusters,
				num_blocks_clustered,
				&farthest_block);

   /*print out initial critical path before clustering starts */
   dummy_bool = report_critical_path(
                        block_delay, inter_cluster_net_delay,
			intra_cluster_net_delay, farthest_block,
			cluster_size, TRUE);

   if (cluster_seed_type == TIMING){
     istart=get_most_critical_unclustered_block();
   }
   else {/*max input seed*/
     istart=get_free_block_with_most_ext_inputs(lut_size,
						inputs_per_cluster,
						clocks_per_cluster);
   }
 }
 else /*cluster seed is max input (since there is no timing information)*/
   istart=get_free_block_with_most_ext_inputs(lut_size,
					      inputs_per_cluster,
					      clocks_per_cluster);


 while (istart != NO_CLUSTER) {
    reset_cluster(&inputs_used, &luts_used, &clocks_used,
		  &next_empty_location_in_cluster, block_in_cluster,
		  cluster_size);

    num_clusters++;

    block_in_cluster[next_empty_location_in_cluster]=istart;
    next_empty_location_in_cluster++;

    add_to_cluster(istart, num_clusters - 1, lut_size, is_clock, 
         global_clocks, &inputs_used, &luts_used, &clocks_used, 
         alpha, timing_driven, connection_driven);   

    num_blocks_clustered ++;

    if (timing_driven && !early_exit) {
      blocks_since_last_analysis++;
      /*it doesn't make sense to do a timing analysis here since there*
       *is only one block clustered it would not change anything      */
    }

    next_blk = get_lut_for_cluster (inputs_per_cluster - inputs_used, 
               clocks_per_cluster - clocks_used, cluster_size, lut_size,
	       luts_used, is_clock, allow_unrelated_clustering);
    
    while (next_blk != NO_CLUSTER) {

      block_in_cluster[next_empty_location_in_cluster]=next_blk;
      next_empty_location_in_cluster++;

      add_to_cluster(next_blk, num_clusters - 1, lut_size, is_clock, 
                  global_clocks, &inputs_used, &luts_used, &clocks_used, 
		  alpha, timing_driven, connection_driven);

      num_blocks_clustered ++;



      if (timing_driven && !early_exit) {
	blocks_since_last_analysis++;
	if (blocks_since_last_analysis >= recompute_timing_after) {
	  calculate_timing_information(block_delay ,inter_cluster_net_delay, 
				       intra_cluster_net_delay, 
				       num_clusters,
				       num_blocks_clustered,
				       &farthest_block);

	  recompute_length_gain_values(block_in_cluster, 
				       next_empty_location_in_cluster,
				       lut_size,
				       global_clocks, is_clock);

	  critical_path_minimized = report_critical_path(
                        block_delay, inter_cluster_net_delay,
			intra_cluster_net_delay, farthest_block,
			cluster_size, FALSE);

	  /*once we have clustered every block on the most critical path*
	   *no further timing gains can be made. */

	  if (critical_path_minimized) {
	    /*allow unrelateed clustering now, since we are not     *
	     *worried any more about inadvertantly absorbing blocks *
	     *which might be on a critical path (current and future)*/
	    allow_unrelated_clustering=TRUE;

            if (allow_early_exit) {
               /* if the critical path is minimized, and we have set this option*/
               /* there is no need to to any more timing analysis               */
               early_exit = TRUE;
            }
	  }


	  blocks_since_last_analysis=0;
	}
      }

      next_blk = get_lut_for_cluster (inputs_per_cluster - inputs_used, 
                  clocks_per_cluster - clocks_used, cluster_size, 
                  lut_size, luts_used, is_clock, allow_unrelated_clustering);
    }
   
    if (hill_climbing_flag && allow_unrelated_clustering) {
       num_blocks_hill_added=hill_climbing (inputs_per_cluster - inputs_used,
                   clocks_per_cluster - clocks_used, cluster_size, lut_size, 
                   luts_used, num_clusters - 1, is_clock, global_clocks,
		   &next_empty_location_in_cluster, block_in_cluster,
                   timing_driven, connection_driven);
       num_blocks_clustered += num_blocks_hill_added;
    }


    if (timing_driven){

      if (num_blocks_hill_added > 0  && !early_exit) {
	blocks_since_last_analysis += num_blocks_hill_added;
	if (blocks_since_last_analysis >= recompute_timing_after) {

	  calculate_timing_information(block_delay, inter_cluster_net_delay, 
				       intra_cluster_net_delay, 
				       num_clusters,
				       num_blocks_clustered,
				       &farthest_block);

	  blocks_since_last_analysis=0;
	}
      }

      if (cluster_seed_type == TIMING){
	istart=get_most_critical_unclustered_block();
      }
      else { /*max input seed*/
	istart=get_free_block_with_most_ext_inputs(lut_size,
						 inputs_per_cluster,
						 clocks_per_cluster);
      }
    }
    else /*cluster seed is max input (since there is no timing information)*/
      istart=get_free_block_with_most_ext_inputs(lut_size,
						 inputs_per_cluster,
						 clocks_per_cluster);

 }

 if (timing_driven){
   calculate_timing_information(block_delay, inter_cluster_net_delay, 
				intra_cluster_net_delay, 
				num_clusters,
				num_blocks_clustered,
				&farthest_block);

   /*print out critical path after circuit has been fully clustered*/
   dummy_bool = report_critical_path(
			block_delay, inter_cluster_net_delay,
			intra_cluster_net_delay, farthest_block,
			cluster_size, TRUE);
 }

 alloc_and_load_cluster_info (&cluster_contents, &cluster_occupancy, 
               num_clusters, cluster_size); 
 check_clustering (num_clusters, cluster_size, inputs_per_cluster,
               clocks_per_cluster, lut_size, is_clock, cluster_contents,
               cluster_occupancy);
 output_clustering (cluster_contents, cluster_occupancy, cluster_size,
               inputs_per_cluster, clocks_per_cluster, num_clusters, 
               lut_size, global_clocks, muxes_to_cluster_output_pins,
               is_clock, out_fname);

 free (cluster_occupancy);
 free (block_in_cluster);
 free_matrix (cluster_contents, 0, num_clusters-1, 0, 
           sizeof (int));
 free_clustering ();

 if (timing_driven)
  free_path_length_memory();

}