SRC/path_delay.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
float **	alloc_and_load_timing_graph (t_timing_inf timing_inf, t_subblock_data subblock_data)
t_linked_int *	allocate_and_load_critical_path (void)
void	load_timing_graph_net_delays (float **net_delay)
float	load_net_slack (float **net_slack, float target_cycle_time)
void	free_timing_graph (float **net_slack)
void	print_timing_graph (char *fname)
void	print_net_slack (char *fname, float **net_slack)
void	print_critical_path (char *fname, t_subblock_data subblock_data)
void	get_tnode_block_and_output_net (int inode, int *iblk_ptr, int *inet_ptr)
void	do_constant_net_delay_timing_analysis (t_timing_inf timing_inf, t_subblock_data subblock_data, float constant_net_delay_value)

---

Function Documentation

float** alloc_and_load_timing_graph	(	t_timing_inf	timing_inf,
		t_subblock_data	subblock_data
	)

Definition at line 158 of file path_delay.c.

{

/* This routine builds the graph used for timing analysis.  Every fb or    *
 * subblock pin is a timing node (tnode).  The connectivity between pins is *
 * represented by timing edges (tedges).  All delay is marked on edges, not *
 * on nodes.  This routine returns an array that will store slack values:   *
 * net_slack[0..num_nets-1][1..num_pins-1].                                 */

/* The two arrays below are valid only for FBs, not pads.                  */
    int i;
    int **num_uses_of_fb_ipin;  /* [0..num_blocks-1][0..type->num_pins-1]       */
    int ***num_uses_of_sblk_opin;       /* [0..num_blocks-1][0..type->num_subblocks][0..type->max_subblock_outputs] */

/* Array for mapping from a pin on a block to a tnode index. For pads, only *
 * the first two pin locations are used (input to pad is first, output of   *
 * pad is second).  For fbs, all OPEN pins on the fb have their mapping   *
 * set to OPEN so I won't use it by mistake.                                */

    int **block_pin_to_tnode;   /* [0..num_blocks-1][0..num_pins-1]      */


/* Array for mapping from a pin on a subblock to a tnode index.  Unused     *
 * or nonexistent subblock pins have their mapping set to OPEN.             *
 * [0..num_blocks-1][0..num_subblocks_per_block-1][0..NUM_SUB_PIN_TYPES][0..total_subblock_pins-1]  */

    int ****snode_block_pin_to_tnode;

    int num_sinks;
    float **net_slack;          /* [0..num_nets-1][1..num_pins-1]. */

/************* End of variable declarations ********************************/

    if(tedge_ch_list_head != NULL)
        {
            printf("Error in alloc_and_load_timing_graph:\n"
                   "\tAn old timing graph still exists.\n");
            exit(1);
        }

/* If either of the checks below ever fail, change the definition of        *
 * tnode_descript to use ints instead of shorts for isubblk or ipin.        */

    for(i = 0; i < num_types; i++)
        {
            if(type_descriptors[i].num_pins > MAX_SHORT)
                {
                    printf
                        ("Error in alloc_and_load_timing_graph: pins for type %s is %d."
                         "\tWill cause short overflow in tnode_descript.\n",
                         type_descriptors[i].name,
                         type_descriptors[i].num_pins);
                    exit(1);
                }

            if(type_descriptors[i].max_subblocks > MAX_SHORT)
                {
                    printf
                        ("Error in alloc_and_load_timing_graph: max_subblocks_per_block"
                         "\tis %d -- will cause short overflow in tnode_descript.\n",
                         type_descriptors[i].max_subblocks);
                    exit(1);
                }
        }

    alloc_and_load_fanout_counts(&num_uses_of_fb_ipin,
                                 &num_uses_of_sblk_opin, subblock_data);

    num_tnodes = alloc_and_load_pin_mappings(&block_pin_to_tnode,
                                             &snode_block_pin_to_tnode,
                                             subblock_data,
                                             num_uses_of_sblk_opin);

    alloc_and_load_tnodes_and_net_mapping(num_uses_of_fb_ipin,
                                          num_uses_of_sblk_opin,
                                          block_pin_to_tnode,
                                          snode_block_pin_to_tnode,
                                          subblock_data, timing_inf);

    num_sinks = alloc_and_load_timing_graph_levels();

    check_timing_graph(subblock_data.num_const_gen, subblock_data.num_ff,
                       num_sinks);

    free_fanout_counts(num_uses_of_fb_ipin, num_uses_of_sblk_opin);
    free_pin_mappings(block_pin_to_tnode, snode_block_pin_to_tnode,
                      subblock_data.num_subblocks_per_block);

    net_slack = alloc_net_slack();
    return (net_slack);
}

Here is the call graph for this function:

Here is the caller graph for this function:

t_linked_int* allocate_and_load_critical_path

(

void

)

Definition at line 1551 of file path_delay.c.

{

/* 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);
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 1644 of file path_delay.c.

{

/* 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);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void free_timing_graph

(

float **

net_slack

)

Definition at line 1217 of file path_delay.c.

{

/* Frees the timing graph data. */

    if(tedge_ch_list_head == NULL)
        {
            printf("Error in free_timing_graph: No timing graph to free.\n");
            exit(1);
        }

    free_chunk_memory(tedge_ch_list_head);
    free(tnode);
    free(tnode_descript);
    free(net_to_driver_tnode);
    free_ivec_vector(tnodes_at_level, 0, num_tnode_levels - 1);
    free(net_slack);

    tedge_ch_list_head = NULL;
    tedge_ch_bytes_avail = 0;
    tedge_ch_next_avail = NULL;

    tnode = NULL;
    tnode_descript = NULL;
    num_tnodes = 0;
    net_to_driver_tnode = NULL;
    tnodes_at_level = NULL;
    num_tnode_levels = 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 1613 of file path_delay.c.

{

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

Here is the caller graph for this function:

float load_net_slack	(	float **	net_slack,
		float	target_cycle_time
	)

Definition at line 1345 of file path_delay.c.

{

/* 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);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void load_timing_graph_net_delays

(

float **

net_delay

)

Definition at line 1191 of file path_delay.c.

{

/* Sets the delays of the inter-FB nets to the values specified by          *
 * net_delay[0..num_nets-1][1..num_pins-1].  These net delays should have    *
 * been allocated and loaded with the net_delay routines.  This routine      *
 * marks the corresponding edges in the timing graph with the proper delay.  */

    int inet, ipin, inode;
    t_tedge *tedge;

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

/* Note that the edges of a tnode corresponding to a FB or INPAD opin must  *
 * be in the same order as the pins of the net driven by the tnode.          */

            for(ipin = 1; ipin < (net[inet].num_sinks + 1); ipin++)
                tedge[ipin - 1].Tdel = net_delay[inet][ipin];
        }
}

Here is the caller graph for this function:

void print_critical_path	(	char *	fname,
		t_subblock_data	subblock_data
	)

Definition at line 1480 of file path_delay.c.

{

/* 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);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void print_net_slack	(	char *	fname,
		float **	net_slack
	)

Definition at line 1249 of file path_delay.c.

{

/* Prints the net slacks into a file.                                     */

    int inet, ipin;
    FILE *fp;

    fp = my_fopen(fname, "w");

    fprintf(fp, "Net #\tSlacks\n\n");

    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");
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void print_timing_graph

(

char *

fname

)

Definition at line 1275 of file path_delay.c.

{

/* 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);
}

Here is the call graph for this function:

Here is the caller graph for this function: