vpr/SRC/timing/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) |
| float ** | alloc_and_load_pre_packing_timing_graph (float block_delay, float inter_cluster_net_delay, t_model *models) |
| 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) |
| 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, float constant_net_delay_value) |
| void | print_timing_graph_as_blif (char *fname, t_model *models) |
Function Documentation
| float** alloc_and_load_pre_packing_timing_graph | ( | float | block_delay, |
| float | inter_cluster_net_delay, | ||
| t_model * | models | ||
| ) |
This routine builds the graph used for timing analysis. Every technology mapped netlist 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].
Definition at line 172 of file path_delay.c.
{
/* The are below are valid only for CBs, not pads. */
/* 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 CLBs, all OPEN pins on the cb have their mapping *
* set to OPEN so I won't use it by mistake. */
int num_sinks;
float **net_slack;
/************* 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);
}
num_timing_nets = num_logical_nets;
timing_nets = vpack_net;
alloc_and_load_tnodes_from_prepacked_netlist(block_delay, inter_cluster_net_delay);
num_sinks = alloc_and_load_timing_graph_levels();
net_slack = alloc_net_slack();
#ifdef CREATE_ECHO_FILES
print_timing_graph("pre_packing_timing_graph.echo");
print_timing_graph_as_blif("pre_packing_timing_graph_as_blif.blif", models);
#endif
check_timing_graph(num_sinks);
return net_slack;
}
Here is the call graph for this function:
Here is the caller graph for this function:
| float** alloc_and_load_timing_graph | ( | t_timing_inf | timing_inf | ) |
This routine builds the graph used for timing analysis. Every cb 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].
Definition at line 127 of file path_delay.c.
{
/* The are below are valid only for CBs, not pads. */
/* 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 CLBs, all OPEN pins on the cb have their mapping *
* set to OPEN so I won't use it by mistake. */
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);
}
num_timing_nets = num_nets;
timing_nets = clb_net;
alloc_and_load_tnodes(timing_inf);
num_sinks = alloc_and_load_timing_graph_levels();
#ifdef CREATE_ECHO_FILES
print_timing_graph("initial_timing_graph.echo");
#endif
check_timing_graph(num_sinks);
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 | ) |
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.
Definition at line 1286 of file path_delay.c.
{
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, |
| 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.
Definition at line 1379 of file path_delay.c.
{
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);
net_delay = alloc_net_delay(&net_delay_chunk_list_head, timing_nets, num_timing_nets);
load_constant_net_delay(net_delay, constant_net_delay_value, timing_nets, num_timing_nets);
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");
print_timing_graph("timing_graph.echo");
print_net_slack("net_slack.echo", net_slack);
print_net_delay(net_delay, "net_delay.echo", timing_nets, num_timing_nets);
#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 | ) |
Frees the timing graph data.
Definition at line 265 of file path_delay.c.
{
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(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;
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 | ||
| ) |
Returns the index of the block that this tnode is part of. If the tnode is a CB_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.
Definition at line 1348 of file path_delay.c.
{
int inet, ipin, iblk;
t_tnode_type tnode_type;
iblk = tnode[inode].block;
tnode_type = tnode[inode].type;
if(tnode_type == CB_OPIN)
{
ipin = tnode[inode].pb_graph_pin->pin_count_in_cluster;
inet = block[iblk].pb->rr_graph[ipin].net_num;
assert(inet != OPEN);
inet = vpack_to_clb_net_mapping[inet];
}
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 | ||
| ) |
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.
Definition at line 1038 of file path_delay.c.
{
float T_crit, T_arr, Tdel, T_cycle, T_req;
int inode, ilevel, num_at_level, i, num_edges, iedge, to_node;
int total;
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. */
long max_critical_input_paths = 0;
long max_critical_output_paths = 0;
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.;
}
total = 0;
for(ilevel = 0; ilevel < num_tnode_levels; ilevel++)
{
num_at_level = tnodes_at_level[ilevel].nelem;
total += num_at_level;
for(i = 0; i < num_at_level; i++)
{
inode = tnodes_at_level[ilevel].list[i];
if(i == 0) {
tnode[i].num_critical_input_paths = 1;
}
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;
/* Update number of near critical paths entering tnode */
/*check for approximate equality*/
if (fabs(tnode[to_node].T_arr - (T_arr + Tdel)) < EQUAL_DEF){
tnode[to_node].num_critical_input_paths += tnode[inode].num_critical_input_paths;
}
else if (tnode[to_node].T_arr < T_arr + Tdel) {
tnode[to_node].num_critical_input_paths = tnode[inode].num_critical_input_paths;
}
if (tnode[to_node].num_critical_input_paths > max_critical_input_paths)
max_critical_input_paths = tnode[to_node].num_critical_input_paths;
tnode[to_node].T_arr =
max(tnode[to_node].T_arr, T_arr + Tdel);
}
}
}
assert(total == num_tnodes);
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(ilevel == 0) {
assert(tnode[inode].type == INPAD_SOURCE || tnode[inode].type == FF_SOURCE || tnode[inode].type == CONSTANT_GEN_SOURCE);
} else {
assert(!(tnode[inode].type == INPAD_SOURCE || tnode[inode].type == FF_SOURCE || tnode[inode].type == CONSTANT_GEN_SOURCE));
}
if(num_edges == 0)
{ /* sink */
assert(tnode[inode].type == OUTPAD_SINK || tnode[inode].type == FF_SINK);
tnode[inode].T_req = T_cycle;
tnode[inode].num_critical_output_paths = 1;
}
else
{
assert(!(tnode[inode].type == OUTPAD_SINK || tnode[inode].type == FF_SINK));
tedge = tnode[inode].out_edges;
to_node = tedge[0].to_node;
Tdel = tedge[0].Tdel;
T_req = tnode[to_node].T_req - Tdel;
tnode[inode].num_critical_output_paths = tnode[to_node].num_critical_output_paths;
if (tnode[to_node].num_critical_output_paths > max_critical_output_paths)
max_critical_output_paths = tnode[to_node].num_critical_output_paths;
for(iedge = 1; iedge < num_edges; iedge++)
{
to_node = tedge[iedge].to_node;
Tdel = tedge[iedge].Tdel;
/* Update number of near critical paths affected by output of tnode */
/*check for approximate equality*/
if (fabs(tnode[to_node].T_req - Tdel - T_req) < EQUAL_DEF){
tnode[inode].num_critical_output_paths += tnode[to_node].num_critical_output_paths;
}
else if (tnode[to_node].T_req - Tdel < T_req) {
tnode[inode].num_critical_output_paths = tnode[to_node].num_critical_output_paths;
}
if (tnode[to_node].num_critical_output_paths > max_critical_output_paths)
max_critical_output_paths = tnode[to_node].num_critical_output_paths;
T_req =
min(T_req,
tnode[to_node].T_req - Tdel);
}
tnode[inode].T_req = T_req;
}
}
}
normalize_costs(T_crit, max_critical_input_paths, max_critical_output_paths);
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 | ) |
Sets the delays of the inter-CLB 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.
Definition at line 244 of file path_delay.c.
{
int inet, ipin, inode;
t_tedge *tedge;
for(inet = 0; inet < num_timing_nets; inet++)
{
inode = net_to_driver_tnode[inet];
tedge = tnode[inode].out_edges;
/* Note that the edges of a tnode corresponding to a CLB or INPAD opin must *
* be in the same order as the pins of the net driven by the tnode. */
for(ipin = 1; ipin < (timing_nets[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 | ) |
Prints out the critical path to a file.
Definition at line 1218 of file path_delay.c.
{
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", 0);
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);
inode = critical_path_node->data;
type = tnode[inode].type;
tnodes_on_crit_path++;
if(type == CB_OPIN)
{
get_tnode_block_and_output_net(inode, &iblk, &inet);
if(!timing_nets[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 | ||
| ) |
Prints the net slacks into a file.
Definition at line 293 of file path_delay.c.
{
int inet, ipin;
FILE *fp;
fp = my_fopen(fname, "w", 0);
fprintf(fp, "Net #\tSlacks\n\n");
for(inet = 0; inet < num_timing_nets; inet++)
{
fprintf(fp, "%5d", inet);
for(ipin = 1; ipin < (timing_nets[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 | ) |
Prints the timing graph into a file.
Definition at line 958 of file path_delay.c.
{
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", "CB_IPIN", "CB_OPIN", "INTERMEDIATE_NODE", "PRIMITIVE_IPIN", "PRIMITIVE_OPIN",
"FF_IPIN", "FF_OPIN",
"FF_SINK", "FF_SOURCE",
"CONSTANT_GEN_SOURCE"
};
fp = my_fopen(fname, "w", 0);
fprintf(fp, "num_tnodes: %d\n", num_tnodes);
fprintf(fp, "Node #\tType\t\tipin\tiblk\t# edges\t"
"Edges (to_node, Tdel)\n\n");
for(inode = 0; inode < num_tnodes; inode++)
{
fprintf(fp, "%d\t", inode);
itype = tnode[inode].type;
fprintf(fp, "%-15.15s\t", tnode_type_names[itype]);
if(tnode[inode].pb_graph_pin != NULL) {
fprintf(fp, "%d\t%d\t", tnode[inode].pb_graph_pin->pin_count_in_cluster,
tnode[inode].block);
} else {
fprintf(fp, "%d\t", tnode[inode].block);
}
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:
| void print_timing_graph_as_blif | ( | char * | fname, |
| t_model * | models | ||
| ) |
Prints out the critical path to a file.
Definition at line 1423 of file path_delay.c.
{
struct s_model_ports *port;
struct s_linked_vptr *p_io_removed;
FILE *fp;
int i, j;
fp = my_fopen(fname, "w", 0);
fprintf(fp, ".model %s\n", blif_circuit_name);
fprintf(fp, ".inputs ");
for(i = 0; i < num_logical_blocks; i++) {
if(logical_block[i].type == VPACK_INPAD) {
fprintf(fp, "\\\n%s ", logical_block[i].name);
}
}
p_io_removed = circuit_p_io_removed;
while(p_io_removed) {
fprintf(fp, "\\\n%s ", (char *) p_io_removed->data_vptr);
p_io_removed = p_io_removed->next;
}
fprintf(fp, "\n");
fprintf(fp, ".outputs ");
for(i = 0; i < num_logical_blocks; i++) {
if(logical_block[i].type == VPACK_OUTPAD) {
/* Outputs have a "out:" prepended to them, must remove */
fprintf(fp, "\\\n%s ", &logical_block[i].name[4]);
}
}
fprintf(fp, "\n");
fprintf(fp, ".names unconn\n");
fprintf(fp, " 0\n\n");
/* Print out primitives */
for(i = 0; i < num_logical_blocks; i++) {
print_primitive_as_blif(fp, i);
}
/* Print out tnode connections */
for(i = 0; i < num_tnodes; i++) {
if(tnode[i].type != PRIMITIVE_IPIN && tnode[i].type != FF_SOURCE && tnode[i].type != INPAD_SOURCE && tnode[i].type != OUTPAD_IPIN) {
for(j = 0; j < tnode[i].num_edges; j++) {
fprintf(fp, ".names tnode_%d tnode_%d\n", i, tnode[i].out_edges[j]);
fprintf(fp, "1 1\n\n");
}
}
}
fprintf(fp, ".end\n\n");
/* Print out .subckt models */
while(models) {
fprintf(fp, ".model %s\n", models->name);
fprintf(fp, ".inputs ");
port = models->inputs;
while(port) {
if(port->size > 1) {
for(j = 0; j < port->size; j++) {
fprintf(fp, "%s[%d] ", port->name, j);
}
} else {
fprintf(fp, "%s ", port->name);
}
port = port->next;
}
fprintf(fp, "\n");
fprintf(fp, ".outputs ");
port = models->outputs;
while(port) {
if(port->size > 1) {
for(j = 0; j < port->size; j++) {
fprintf(fp, "%s[%d] ", port->name, j);
}
} else {
fprintf(fp, "%s ", port->name);
}
port = port->next;
}
fprintf(fp, "\n.blackbox\n.end\n\n");
fprintf(fp, "\n\n");
models = models->next;
}
fclose(fp);
}
Here is the call graph for this function:
Here is the caller graph for this function:
