path_delay.c

用于学术研究的FPGA布局布线软件VPR

    for(inet = 0; inet < num_nets; inet++)
	{
	    fprintf(fp, "%5d", inet);
	    for(ipin = 1; ipin < (net[inet].num_sinks + 1); ipin++)
		{
		    fprintf(fp, "\t%g", net_slack[inet][ipin]);
		}
	    fprintf(fp, "\n");
	}
}


void
print_timing_graph(char *fname)
{

/* Prints the timing graph into a file.           */

    FILE *fp;
    int inode, iedge, ilevel, i;
    t_tedge *tedge;
    t_tnode_type itype;
    char *tnode_type_names[] = { "INPAD_SOURCE", "INPAD_OPIN",
	"OUTPAD_IPIN", "OUTPAD_SINK", "FB_IPIN", "FB_OPIN",
	"SUBBLK_IPIN", "SUBBLK_OPIN", "FF_SINK", "FF_SOURCE",
	"CONSTANT_GEN_SOURCE"
    };


    fp = my_fopen(fname, "w");

    fprintf(fp, "num_tnodes: %d\n", num_tnodes);
    fprintf(fp, "Node #\tType\t\tipin\tisubblk\tiblk\t# edges\t"
	    "Edges (to_node, Tdel)\n\n");

    for(inode = 0; inode < num_tnodes; inode++)
	{
	    fprintf(fp, "%d\t", inode);

	    itype = tnode_descript[inode].type;
	    fprintf(fp, "%-15.15s\t", tnode_type_names[itype]);

	    fprintf(fp, "%d\t%d\t%d\t", tnode_descript[inode].ipin,
		    tnode_descript[inode].isubblk,
		    tnode_descript[inode].iblk);

	    fprintf(fp, "%d\t", tnode[inode].num_edges);
	    tedge = tnode[inode].out_edges;
	    for(iedge = 0; iedge < tnode[inode].num_edges; iedge++)
		{
		    fprintf(fp, "\t(%4d,%7.3g)", tedge[iedge].to_node,
			    tedge[iedge].Tdel);
		}
	    fprintf(fp, "\n");
	}

    fprintf(fp, "\n\nnum_tnode_levels: %d\n", num_tnode_levels);

    for(ilevel = 0; ilevel < num_tnode_levels; ilevel++)
	{
	    fprintf(fp, "\n\nLevel: %d  Num_nodes: %d\nNodes:", ilevel,
		    tnodes_at_level[ilevel].nelem);
	    for(i = 0; i < tnodes_at_level[ilevel].nelem; i++)
		fprintf(fp, "\t%d", tnodes_at_level[ilevel].list[i]);
	}

    fprintf(fp, "\n");
    fprintf(fp, "\n\nNet #\tNet_to_driver_tnode\n");

    for(i = 0; i < num_nets; i++)
	fprintf(fp, "%4d\t%6d\n", i, net_to_driver_tnode[i]);

    fprintf(fp, "\n\nNode #\t\tT_arr\t\tT_req\n\n");

    for(inode = 0; inode < num_tnodes; inode++)
	fprintf(fp, "%d\t%12g\t%12g\n", inode, tnode[inode].T_arr,
		tnode[inode].T_req);

    fclose(fp);
}


float
load_net_slack(float **net_slack,
	       float target_cycle_time)
{

/* Determines the slack of every source-sink pair of block pins in the      *
 * circuit.  The timing graph must have already been built.  target_cycle_  *
 * time is the target delay for the circuit -- if 0, the target_cycle_time  *
 * is set to the critical path found in the timing graph.  This routine     *
 * loads net_slack, and returns the current critical path delay.            */

    float T_crit, T_arr, Tdel, T_cycle, T_req;
    int inode, ilevel, num_at_level, i, num_edges, iedge, to_node;
    t_tedge *tedge;

/* Reset all arrival times to -ve infinity.  Can't just set to zero or the   *
 * constant propagation (constant generators work at -ve infinity) won't     *
 * work.                                                                     */

    for(inode = 0; inode < num_tnodes; inode++)
	tnode[inode].T_arr = T_CONSTANT_GENERATOR;

/* Compute all arrival times with a breadth-first analysis from inputs to   *
 * outputs.  Also compute critical path (T_crit).                           */

    T_crit = 0.;

/* Primary inputs arrive at T = 0. */

    num_at_level = tnodes_at_level[0].nelem;
    for(i = 0; i < num_at_level; i++)
	{
	    inode = tnodes_at_level[0].list[i];
	    tnode[inode].T_arr = 0.;
	}

    for(ilevel = 0; ilevel < num_tnode_levels; ilevel++)
	{
	    num_at_level = tnodes_at_level[ilevel].nelem;

	    for(i = 0; i < num_at_level; i++)
		{
		    inode = tnodes_at_level[ilevel].list[i];
		    T_arr = tnode[inode].T_arr;
		    num_edges = tnode[inode].num_edges;
		    tedge = tnode[inode].out_edges;
		    T_crit = max(T_crit, T_arr);

		    for(iedge = 0; iedge < num_edges; iedge++)
			{
			    to_node = tedge[iedge].to_node;
			    Tdel = tedge[iedge].Tdel;
			    tnode[to_node].T_arr =
				max(tnode[to_node].T_arr, T_arr + Tdel);
			}
		}

	}

    if(target_cycle_time > 0.)	/* User specified target cycle time */
	T_cycle = target_cycle_time;
    else			/* Otherwise, target = critical path */
	T_cycle = T_crit;

/* Compute the required arrival times with a backward breadth-first analysis *
 * from sinks (output pads, etc.) to primary inputs.                         */

    for(ilevel = num_tnode_levels - 1; ilevel >= 0; ilevel--)
	{
	    num_at_level = tnodes_at_level[ilevel].nelem;

	    for(i = 0; i < num_at_level; i++)
		{
		    inode = tnodes_at_level[ilevel].list[i];
		    num_edges = tnode[inode].num_edges;

		    if(num_edges == 0)
			{	/* sink */
			    tnode[inode].T_req = T_cycle;
			}
		    else
			{
			    tedge = tnode[inode].out_edges;
			    to_node = tedge[0].to_node;
			    Tdel = tedge[0].Tdel;
			    T_req = tnode[to_node].T_req - Tdel;

			    for(iedge = 1; iedge < num_edges; iedge++)
				{
				    to_node = tedge[iedge].to_node;
				    Tdel = tedge[iedge].Tdel;
				    T_req =
					min(T_req,
					    tnode[to_node].T_req - Tdel);
				}

			    tnode[inode].T_req = T_req;
			}
		}
	}

    compute_net_slacks(net_slack);

    return (T_crit);
}


static void
compute_net_slacks(float **net_slack)
{

/* Puts the slack of each source-sink pair of block pins in net_slack.     */

    int inet, iedge, inode, to_node, num_edges;
    t_tedge *tedge;
    float T_arr, Tdel, T_req;

    for(inet = 0; inet < num_nets; inet++)
	{
	    inode = net_to_driver_tnode[inet];
	    T_arr = tnode[inode].T_arr;
	    num_edges = tnode[inode].num_edges;
	    tedge = tnode[inode].out_edges;

	    for(iedge = 0; iedge < num_edges; iedge++)
		{
		    to_node = tedge[iedge].to_node;
		    Tdel = tedge[iedge].Tdel;
		    T_req = tnode[to_node].T_req;
		    net_slack[inet][iedge + 1] = T_req - T_arr - Tdel;
		}
	}
}


void
print_critical_path(char *fname,
		    t_subblock_data subblock_data)
{

/* Prints out the critical path to a file.  */

    t_linked_int *critical_path_head, *critical_path_node;
    FILE *fp;
    int non_global_nets_on_crit_path, global_nets_on_crit_path;
    int tnodes_on_crit_path, inode, iblk, inet;
    t_tnode_type type;
    float total_net_delay, total_logic_delay, Tdel;

    critical_path_head = allocate_and_load_critical_path();
    critical_path_node = critical_path_head;

    fp = my_fopen(fname, "w");

    non_global_nets_on_crit_path = 0;
    global_nets_on_crit_path = 0;
    tnodes_on_crit_path = 0;
    total_net_delay = 0.;
    total_logic_delay = 0.;

    while(critical_path_node != NULL)
	{
	    Tdel =
		print_critical_path_node(fp, critical_path_node,
					 subblock_data);
	    inode = critical_path_node->data;
	    type = tnode_descript[inode].type;
	    tnodes_on_crit_path++;

	    if(type == INPAD_OPIN || type == FB_OPIN)
		{
		    get_tnode_block_and_output_net(inode, &iblk, &inet);

		    if(!net[inet].is_global)
			non_global_nets_on_crit_path++;
		    else
			global_nets_on_crit_path++;

		    total_net_delay += Tdel;
		}
	    else
		{
		    total_logic_delay += Tdel;
		}

	    critical_path_node = critical_path_node->next;
	}

    fprintf(fp,
	    "\nTnodes on crit. path: %d  Non-global nets on crit. path: %d."
	    "\n", tnodes_on_crit_path, non_global_nets_on_crit_path);
    fprintf(fp, "Global nets on crit. path: %d.\n", global_nets_on_crit_path);
    fprintf(fp, "Total logic delay: %g (s)  Total net delay: %g (s)\n",
	    total_logic_delay, total_net_delay);

    printf("Nets on crit. path: %d normal, %d global.\n",
	   non_global_nets_on_crit_path, global_nets_on_crit_path);

    printf("Total logic delay: %g (s)  Total net delay: %g (s)\n",
	   total_logic_delay, total_net_delay);

    fclose(fp);
    free_int_list(&critical_path_head);
}


t_linked_int *
allocate_and_load_critical_path(void)
{

/* Finds the critical path and puts a list of the tnodes on the critical    *
 * path in a linked list, from the path SOURCE to the path SINK.            */

    t_linked_int *critical_path_head, *curr_crit_node, *prev_crit_node;
    int inode, iedge, to_node, num_at_level, i, crit_node, num_edges;
    float min_slack, slack;
    t_tedge *tedge;

    num_at_level = tnodes_at_level[0].nelem;
    min_slack = HUGE_FLOAT;
    crit_node = OPEN;		/* Stops compiler warnings. */

    for(i = 0; i < num_at_level; i++)
	{			/* Path must start at SOURCE (no inputs) */
	    inode = tnodes_at_level[0].list[i];
	    slack = tnode[inode].T_req - tnode[inode].T_arr;

	    if(slack < min_slack)
		{
		    crit_node = inode;
		    min_slack = slack;
		}
	}

    critical_path_head = (t_linked_int *) my_malloc(sizeof(t_linked_int));
    critical_path_head->data = crit_node;
    prev_crit_node = critical_path_head;
    num_edges = tnode[crit_node].num_edges;

    while(num_edges != 0)
	{			/* Path will end at SINK (no fanout) */
	    curr_crit_node = (t_linked_int *) my_malloc(sizeof(t_linked_int));
	    prev_crit_node->next = curr_crit_node;
	    tedge = tnode[crit_node].out_edges;
	    min_slack = HUGE_FLOAT;

	    for(iedge = 0; iedge < num_edges; iedge++)
		{
		    to_node = tedge[iedge].to_node;
		    slack = tnode[to_node].T_req - tnode[to_node].T_arr;

		    if(slack < min_slack)
			{
			    crit_node = to_node;
			    min_slack = slack;
			}
		}

	    curr_crit_node->data = crit_node;
	    prev_crit_node = curr_crit_node;
	    num_edges = tnode[crit_node].num_edges;
	}

    prev_crit_node->next = NULL;
    return (critical_path_head);
}


void
get_tnode_block_and_output_net(int inode,
			       int *iblk_ptr,
			       int *inet_ptr)
{

/* Returns the index of the block that this tnode is part of.  If the tnode *
 * is a FB_OPIN or INPAD_OPIN (i.e. if it drives a net), the net index is  *
 * returned via inet_ptr.  Otherwise inet_ptr points at OPEN.               */

    int inet, ipin, iblk;
    t_tnode_type tnode_type;

    iblk = tnode_descript[inode].iblk;
    tnode_type = tnode_descript[inode].type;

    if(tnode_type == FB_OPIN || tnode_type == INPAD_OPIN)
	{
	    ipin = tnode_descript[inode].ipin;
	    inet = block[iblk].nets[ipin];
	}
    else
	{
	    inet = OPEN;
	}

    *iblk_ptr = iblk;
    *inet_ptr = inet;
}


void
do_constant_net_delay_timing_analysis(t_timing_inf timing_inf,
				      t_subblock_data subblock_data,
				      float constant_net_delay_value)
{

/* Does a timing analysis (simple) where it assumes that each net has a      *
 * constant delay value.  Used only when operation == TIMING_ANALYSIS_ONLY.  */

    struct s_linked_vptr *net_delay_chunk_list_head;
    float **net_delay, **net_slack;

    float T_crit;

    net_slack = alloc_and_load_timing_graph(timing_inf, subblock_data);
    net_delay = alloc_net_delay(&net_delay_chunk_list_head);

    load_constant_net_delay(net_delay, constant_net_delay_value);
    load_timing_graph_net_delays(net_delay);
    T_crit = load_net_slack(net_slack, 0);

    printf("\n");
    printf("\nCritical Path: %g (s)\n", T_crit);

#ifdef CREATE_ECHO_FILES
    print_critical_path("critical_path.echo", subblock_data);
    print_timing_graph("timing_graph.echo");
    print_net_slack("net_slack.echo", net_slack);
    print_net_delay(net_delay, "net_delay.echo");
#endif /* CREATE_ECHO_FILES */

    free_timing_graph(net_slack);
    free_net_delay(net_delay, &net_delay_chunk_list_head);
}