cluster_legality.h File Reference

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

Go to the source code of this file.

Functions
void	alloc_and_load_cluster_legality_checker (void)
void	alloc_and_load_legalizer_for_cluster (INP t_block *clb, INP int clb_index, INP const t_arch *arch)
void	free_legalizer_for_cluster (INP t_block *clb, boolean free_local_rr_graph)
void	free_cluster_legality_checker (void)
void	reset_legalizer_for_cluster (t_block *clb)
void	save_and_reset_routing_cluster (void)
void	setup_intracluster_routing_for_molecule (INP t_pack_molecule *molecule, INOUTP t_pb_graph_node **primitives_list)
boolean	try_breadth_first_route_cluster (void)
void	restore_routing_cluster (void)
void	save_cluster_solution (void)
boolean	is_pin_open (int i)
void	set_pb_graph_mode (t_pb_graph_node *pb_graph_node, int mode, int isOn)
void	alloc_and_load_rr_graph_for_pb_graph_node (INP t_pb_graph_node *pb_graph_node, INP const t_arch *arch, int mode)
void	reload_ext_net_rr_terminal_cluster (void)
void	force_post_place_route_cb_input_pins (int iblock)
void	setup_intracluster_routing_for_logical_block (INP int iblock, INP t_pb_graph_node *primitive)

Function Documentation

void alloc_and_load_cluster_legality_checker

(

void

)

Definition at line 202 of file cluster_legality.c.

                                                   {
    best_routing = (struct s_trace **) my_calloc(num_logical_nets,
            sizeof(struct s_trace *));
    nets_in_cluster = (int *) my_malloc(num_logical_nets * sizeof(int));
    num_nets_in_cluster = 0;
    num_nets = num_logical_nets;

    /* inside a cluster, I do not consider rr_indexed_data cost, set to 1 since other costs are multiplied by it */
    num_rr_indexed_data = 1;
    rr_indexed_data = (t_rr_indexed_data *) my_calloc(1, sizeof(t_rr_indexed_data));
    rr_indexed_data[0].base_cost = 1;

    /* alloc routing structures */
    alloc_route_static_structs();
    alloc_net_rr_terminals_cluster();
}

Here is the call graph for this function:

Here is the caller graph for this function:

void alloc_and_load_legalizer_for_cluster	(	INP t_block *	clb,
		INP int	clb_index,
		INP const t_arch *	arch
	)

Structure: Model external routing and internal routing

1. Model external routing num input pins == num external sources for input pins, fully connect them to input pins (simulates external routing) num output pins == num external sinks for output pins, fully connect them to output pins (simulates external routing) num clock pins == num external sources for clock pins, fully connect them to clock pins (simulates external routing)
2. Model internal routing

Definition at line 421 of file cluster_legality.c.

                                {

    /**
     * Structure: Model external routing and internal routing
     * 
     * 1.  Model external routing
     *   num input pins == num external sources for input pins, fully connect them to input pins (simulates external routing)
     *   num output pins == num external sinks for output pins, fully connect them to output pins (simulates external routing)
     *   num clock pins == num external sources for clock pins, fully connect them to clock pins (simulates external routing)
     * 2.  Model internal routing
     * 
     */
    /* make each rr_node one correspond with pin and correspond with pin's index pin_count_in_cluster */
    int i, j, k, m, index, pb_graph_rr_index;
    int count_pins;
    t_pb_type * pb_type;
    t_pb_graph_node *pb_graph_node;
    int ipin;

    /* Create rr_graph */
    pb_type = clb->type->pb_type;
    pb_graph_node = clb->type->pb_graph_head;
    num_rr_nodes = pb_graph_node->total_pb_pins + pb_type->num_input_pins
            + pb_type->num_output_pins + pb_type->num_clock_pins;

    /* allocate memory for rr_node resources + additional memory for any additional sources/sinks, 2x is an overallocation but guarantees that there will be enough sources/sinks available */
    rr_node = (t_rr_node *) my_calloc(num_rr_nodes * 2, sizeof(t_rr_node));
    clb->pb->rr_graph = rr_node;

    alloc_and_load_rr_graph_for_pb_graph_node(pb_graph_node, arch, 0);

    curr_cluster_index = clb_index;

    /*   Alloc and load rr_graph external sources and sinks */
    ext_input_rr_node_index = pb_graph_node->total_pb_pins;
    ext_output_rr_node_index = pb_type->num_input_pins
            + pb_graph_node->total_pb_pins;
    ext_clock_rr_node_index = pb_type->num_input_pins + pb_type->num_output_pins
            + pb_graph_node->total_pb_pins;
    max_ext_index = pb_type->num_input_pins + pb_type->num_output_pins
            + pb_type->num_clock_pins + pb_graph_node->total_pb_pins;

    for (i = 0; i < pb_type->num_input_pins; i++) {
        index = i + pb_graph_node->total_pb_pins;
        rr_node[index].type = SOURCE;
        rr_node[index].fan_in = 0;
        rr_node[index].num_edges = pb_type->num_input_pins;
        rr_node[index].pack_intrinsic_cost = 1
                + (float) rr_node[index].num_edges / 5; /* need to normalize better than 5 */
        rr_node[index].edges = (int *) my_malloc(
                rr_node[index].num_edges * sizeof(int));
        rr_node[index].switches = (short *) my_calloc(rr_node[index].num_edges,
                sizeof(int));
        rr_node[index].capacity = 1;
    }

    for (i = 0; i < pb_type->num_output_pins; i++) {
        index = i + pb_type->num_input_pins + pb_graph_node->total_pb_pins;
        rr_node[index].type = SINK;
        rr_node[index].fan_in = pb_type->num_output_pins;
        rr_node[index].num_edges = 0;
        rr_node[index].pack_intrinsic_cost = 1
                + (float) rr_node[index].num_edges / 5; /* need to normalize better than 5 */
        rr_node[index].capacity = 1;
    }

    for (i = 0; i < pb_type->num_clock_pins; i++) {
        index = i + pb_type->num_input_pins + pb_type->num_output_pins
                + pb_graph_node->total_pb_pins;
        rr_node[index].type = SOURCE;
        rr_node[index].fan_in = 0;
        rr_node[index].num_edges = pb_type->num_clock_pins;
        rr_node[index].pack_intrinsic_cost = 1
                + (float) rr_node[index].num_edges / 5; /* need to normalize better than 5 */
        rr_node[index].edges = (int *) my_malloc(
                rr_node[index].num_edges * sizeof(int));
        rr_node[index].switches = (short *) my_calloc(rr_node[index].num_edges,
                sizeof(int));
        rr_node[index].capacity = 1;
    }

    ipin = 0;
    for (i = 0; i < pb_graph_node->num_input_ports; i++) {
        for (j = 0; j < pb_graph_node->num_input_pins[i]; j++) {
            pb_graph_rr_index =
                    pb_graph_node->input_pins[i][j].pin_count_in_cluster;
            for (k = 0; k < pb_type->num_input_pins; k++) {
                index = k + pb_graph_node->total_pb_pins;
                rr_node[index].edges[ipin] = pb_graph_rr_index;
                rr_node[index].switches[ipin] = arch->num_switches - 1;
            }
            rr_node[pb_graph_rr_index].pack_intrinsic_cost = MAX_SHORT; /* using an input pin should be made costly */
            ipin++;
        }
    }

    /* Must attach output pins to input pins because if a connection cannot fit using intra-cluster routing, it can also use external routing */
    for (i = 0; i < pb_graph_node->num_output_ports; i++) {
        for (j = 0; j < pb_graph_node->num_output_pins[i]; j++) {
            count_pins = pb_graph_node->output_pins[i][j].num_output_edges
                    + pb_type->num_output_pins + pb_type->num_input_pins;
            pb_graph_rr_index =
                    pb_graph_node->output_pins[i][j].pin_count_in_cluster;
            rr_node[pb_graph_rr_index].edges = (int *) my_realloc(
                    rr_node[pb_graph_rr_index].edges,
                    (count_pins) * sizeof(int));
            rr_node[pb_graph_rr_index].switches = (short *) my_realloc(
                    rr_node[pb_graph_rr_index].switches,
                    (count_pins) * sizeof(int));

            ipin = 0;
            for (k = 0; k < pb_graph_node->num_input_ports; k++) {
                for (m = 0; m < pb_graph_node->num_input_pins[k]; m++) {
                    index =
                            pb_graph_node->input_pins[k][m].pin_count_in_cluster;
                    rr_node[pb_graph_rr_index].edges[ipin
                            + pb_graph_node->output_pins[i][j].num_output_edges] =
                            index;
                    rr_node[pb_graph_rr_index].switches[ipin
                            + pb_graph_node->output_pins[i][j].num_output_edges] =
                            arch->num_switches - 1;
                    ipin++;
                }
            }
            for (k = 0; k < pb_type->num_output_pins; k++) {
                index = k + pb_type->num_input_pins
                        + pb_graph_node->total_pb_pins;
                rr_node[pb_graph_rr_index].edges[k + pb_type->num_input_pins
                        + pb_graph_node->output_pins[i][j].num_output_edges] =
                        index;
                rr_node[pb_graph_rr_index].switches[k + pb_type->num_input_pins
                        + pb_graph_node->output_pins[i][j].num_output_edges] =
                        arch->num_switches - 1;
            }
            rr_node[pb_graph_rr_index].num_edges += pb_type->num_output_pins
                    + pb_type->num_input_pins;
            rr_node[pb_graph_rr_index].pack_intrinsic_cost = 1
                    + (float) rr_node[pb_graph_rr_index].num_edges / 5; /* need to normalize better than 5 */
        }
    }

    ipin = 0;
    for (i = 0; i < pb_graph_node->num_clock_ports; i++) {
        for (j = 0; j < pb_graph_node->num_clock_pins[i]; j++) {
            for (k = 0; k < pb_type->num_clock_pins; k++) {
                index = k + pb_type->num_input_pins + pb_type->num_output_pins
                        + pb_graph_node->total_pb_pins;
                pb_graph_rr_index =
                        pb_graph_node->clock_pins[i][j].pin_count_in_cluster;
                rr_node[index].edges[ipin] = pb_graph_rr_index;
                rr_node[index].switches[ipin] = arch->num_switches - 1;
            }
            ipin++;
        }
    }

    alloc_and_load_rr_node_route_structs();
    num_nets_in_cluster = 0;

}

Here is the call graph for this function:

Here is the caller graph for this function:

void alloc_and_load_rr_graph_for_pb_graph_node	(	INP t_pb_graph_node *	pb_graph_node,
		INP const t_arch *	arch,
		int	mode
	)

Definition at line 237 of file cluster_legality.c.

                                                                              {

    int i, j, k, index;
    boolean is_primitive;

    is_primitive = (boolean) (pb_graph_node->pb_type->num_modes == 0);

    for (i = 0; i < pb_graph_node->num_input_ports; i++) {
        for (j = 0; j < pb_graph_node->num_input_pins[i]; j++) {
            index = pb_graph_node->input_pins[i][j].pin_count_in_cluster;
            rr_node[index].pb_graph_pin = &pb_graph_node->input_pins[i][j];
            rr_node[index].fan_in =
                    pb_graph_node->input_pins[i][j].num_input_edges;
            rr_node[index].num_edges =
                    pb_graph_node->input_pins[i][j].num_output_edges;
            rr_node[index].pack_intrinsic_cost = 1
                    + (float) rr_node[index].num_edges / 5 + ((float)j/(float)pb_graph_node->num_input_pins[i])/(float)10; /* need to normalize better than 5 and 10, bias router to use earlier inputs pins */
            rr_node[index].edges = (int *) my_malloc(
                    rr_node[index].num_edges * sizeof(int));
            rr_node[index].switches = (short *) my_calloc(rr_node[index].num_edges,
                    sizeof(short));
            rr_node[index].net_num = OPEN;
            rr_node[index].prev_node = OPEN;
            rr_node[index].prev_edge = OPEN;
            if (mode == 0) { /* default mode is the first mode */
                rr_node[index].capacity = 1;
            } else {
                rr_node[index].capacity = 0;
            }
            for (k = 0; k < pb_graph_node->input_pins[i][j].num_output_edges;
                    k++) {
                /* TODO: Intention was to do bus-based implementation here */
                rr_node[index].edges[k] =
                        pb_graph_node->input_pins[i][j].output_edges[k]->output_pins[0]->pin_count_in_cluster;
                rr_node[index].switches[k] = arch->num_switches - 1; /* last switch in arch switch properties is a delayless switch */
                assert(
                        pb_graph_node->input_pins[i][j].output_edges[k]->num_output_pins == 1);
            }
            rr_node[index].type = INTRA_CLUSTER_EDGE;
            if (is_primitive) {
                /* This is a terminating pin, add SINK node */
                assert(rr_node[index].num_edges == 0);
                rr_node[index].num_edges = 1;
                rr_node[index].edges = (int *) my_calloc(rr_node[index].num_edges, sizeof(int));
                rr_node[index].switches = (short *) my_calloc(rr_node[index].num_edges, sizeof(short));
                rr_node[index].edges[0] = num_rr_nodes;
                
                /* Create SINK node */
                rr_node[num_rr_nodes].pb_graph_pin = NULL;
                rr_node[num_rr_nodes].fan_in = 1;
                rr_node[num_rr_nodes].num_edges = 0;
                rr_node[num_rr_nodes].pack_intrinsic_cost = 1;
                rr_node[num_rr_nodes].edges = NULL;
                rr_node[num_rr_nodes].switches = NULL;
                rr_node[num_rr_nodes].net_num = OPEN;
                rr_node[num_rr_nodes].prev_node = OPEN;
                rr_node[num_rr_nodes].prev_edge = OPEN;
                rr_node[num_rr_nodes].capacity = 1;
                rr_node[num_rr_nodes].type = SINK;                  
                num_rr_nodes++;

                if(pb_graph_node->pb_type->class_type == LUT_CLASS) {
                    /* LUTs are special, they have logical equivalence at inputs, logical equivalence is represented by a single high capacity sink instead of multiple single capacity sinks */
                    rr_node[num_rr_nodes - 1].capacity = pb_graph_node->num_input_pins[i];                  
                    if(j != 0) {
                        num_rr_nodes--;
                        rr_node[index].edges[0] = num_rr_nodes - 1;
                    }                   
                }               
            }
        }
    }

    for (i = 0; i < pb_graph_node->num_output_ports; i++) {
        for (j = 0; j < pb_graph_node->num_output_pins[i]; j++) {
            index = pb_graph_node->output_pins[i][j].pin_count_in_cluster;
            rr_node[index].pb_graph_pin = &pb_graph_node->output_pins[i][j];
            rr_node[index].fan_in =
                    pb_graph_node->output_pins[i][j].num_input_edges;
            rr_node[index].num_edges =
                    pb_graph_node->output_pins[i][j].num_output_edges;
            rr_node[index].pack_intrinsic_cost = 1
                    + (float) rr_node[index].num_edges / 5; /* need to normalize better than 5 */
            rr_node[index].edges = (int *) my_malloc(
                    rr_node[index].num_edges * sizeof(int));
            rr_node[index].switches = (short *) my_calloc(rr_node[index].num_edges,
                    sizeof(short));
            rr_node[index].net_num = OPEN;
            rr_node[index].prev_node = OPEN;
            rr_node[index].prev_edge = OPEN;
            if (mode == 0) { /* Default mode is the first mode */
                rr_node[index].capacity = 1;
            } else {
                rr_node[index].capacity = 0;
            }
            for (k = 0; k < pb_graph_node->output_pins[i][j].num_output_edges;
                    k++) {
                /* TODO: Intention was to do bus-based implementation here */
                rr_node[index].edges[k] =
                        pb_graph_node->output_pins[i][j].output_edges[k]->output_pins[0]->pin_count_in_cluster;
                rr_node[index].switches[k] = arch->num_switches - 1;
                assert(
                        pb_graph_node->output_pins[i][j].output_edges[k]->num_output_pins == 1);
            }
            rr_node[index].type = INTRA_CLUSTER_EDGE;
            if (is_primitive) {
                rr_node[index].type = SOURCE;
            }
        }
    }

    for (i = 0; i < pb_graph_node->num_clock_ports; i++) {
        for (j = 0; j < pb_graph_node->num_clock_pins[i]; j++) {
            index = pb_graph_node->clock_pins[i][j].pin_count_in_cluster;
            rr_node[index].pb_graph_pin = &pb_graph_node->clock_pins[i][j];
            rr_node[index].fan_in =
                    pb_graph_node->clock_pins[i][j].num_input_edges;
            rr_node[index].num_edges =
                    pb_graph_node->clock_pins[i][j].num_output_edges;
            rr_node[index].pack_intrinsic_cost = 1
                    + (float) rr_node[index].num_edges / 5; /* need to normalize better than 5 */
            rr_node[index].edges = (int *) my_malloc(
                    rr_node[index].num_edges * sizeof(int));
            rr_node[index].switches = (short *) my_calloc(rr_node[index].num_edges,
                    sizeof(short));
            rr_node[index].net_num = OPEN;
            rr_node[index].prev_node = OPEN;
            rr_node[index].prev_edge = OPEN;
            if (mode == 0) { /* default mode is the first mode (useful for routing */
                rr_node[index].capacity = 1;
            } else {
                rr_node[index].capacity = 0;
            }
            for (k = 0; k < pb_graph_node->clock_pins[i][j].num_output_edges;
                    k++) {
                /* TODO: Intention was to do bus-based implementation here */
                rr_node[index].edges[k] =
                        pb_graph_node->clock_pins[i][j].output_edges[k]->output_pins[0]->pin_count_in_cluster;
                rr_node[index].switches[k] = arch->num_switches - 1;
                assert(
                        pb_graph_node->clock_pins[i][j].output_edges[k]->num_output_pins == 1);
            }
            rr_node[index].type = INTRA_CLUSTER_EDGE;
            if (is_primitive) {
                /* This is a terminating pin, add SINK node */
                assert(rr_node[index].num_edges == 0);
                rr_node[index].num_edges = 1;
                rr_node[index].edges = (int *) my_calloc(rr_node[index].num_edges, sizeof(int));
                rr_node[index].switches = (short *) my_calloc(rr_node[index].num_edges, sizeof(short));
                rr_node[index].edges[0] = num_rr_nodes;
                
                /* Create SINK node */
                rr_node[num_rr_nodes].pb_graph_pin = NULL;
                rr_node[num_rr_nodes].fan_in = 1;
                rr_node[num_rr_nodes].num_edges = 0;
                rr_node[num_rr_nodes].pack_intrinsic_cost = 1;
                rr_node[num_rr_nodes].edges = NULL;
                rr_node[num_rr_nodes].switches = NULL;
                rr_node[num_rr_nodes].net_num = OPEN;
                rr_node[num_rr_nodes].prev_node = OPEN;
                rr_node[num_rr_nodes].prev_edge = OPEN;
                rr_node[num_rr_nodes].capacity = 1;
                rr_node[num_rr_nodes].type = SINK;  
                num_rr_nodes++;
            }
        }
    }

    for (i = 0; i < pb_graph_node->pb_type->num_modes; i++) {
        for (j = 0; j < pb_graph_node->pb_type->modes[i].num_pb_type_children;
                j++) {
            for (k = 0;
                    k
                            < pb_graph_node->pb_type->modes[i].pb_type_children[j].num_pb;
                    k++) {
                alloc_and_load_rr_graph_for_pb_graph_node(
                        &pb_graph_node->child_pb_graph_nodes[i][j][k], arch, i);
            }
        }
    }

}

Here is the call graph for this function:

Here is the caller graph for this function:

void force_post_place_route_cb_input_pins

(

int

iblock

)

Definition at line 1207 of file cluster_legality.c.

                                                      {
    int i, j, k, ipin, net_index, ext_net;
    int pin_offset;
    boolean has_ext_source, success;
    int curr_ext_output, curr_ext_input, curr_ext_clock;
    t_pb_graph_node *pb_graph_node;

    pb_graph_node = block[iblock].pb->pb_graph_node;
    pin_offset = block[iblock].z * (pb_graph_node->pb_type->num_input_pins + pb_graph_node->pb_type->num_output_pins + pb_graph_node->pb_type->num_clock_pins);

    curr_ext_input = ext_input_rr_node_index;
    curr_ext_output = ext_output_rr_node_index;
    curr_ext_clock = ext_clock_rr_node_index;

    for (i = 0; i < num_nets_in_cluster; i++) {
        net_index = nets_in_cluster[i];
        has_ext_source = (boolean)
                (logical_block[vpack_net[net_index].node_block[0]].clb_index
                        != curr_cluster_index);
        if(has_ext_source) {
            ext_net = vpack_to_clb_net_mapping[net_index];
            assert(ext_net != OPEN);
            if (vpack_net[net_index].is_global) {
                free(rr_node[curr_ext_clock].edges);
                rr_node[curr_ext_clock].edges = NULL;
                rr_node[curr_ext_clock].num_edges = 0;
                
                success = FALSE;
                ipin = 0;
                /* force intra-cluster net to use pins from ext route */
                for(j = 0; j < pb_graph_node->num_clock_ports; j++) {
                    for(k = 0; k < pb_graph_node->num_clock_pins[j]; k++) {
                        if(ext_net == block[iblock].nets[ipin + pb_graph_node->pb_type->num_input_pins + pb_graph_node->pb_type->num_output_pins + pin_offset]) {
                            success = TRUE;
                            rr_node[curr_ext_clock].num_edges++;
                            rr_node[curr_ext_clock].edges = (int*)my_realloc(rr_node[curr_ext_clock].edges, rr_node[curr_ext_clock].num_edges * sizeof(int));
                            rr_node[curr_ext_clock].edges[rr_node[curr_ext_clock].num_edges - 1] = pb_graph_node->clock_pins[j][k].pin_count_in_cluster;
                        }
                        ipin++;
                    }
                }
                assert(success);
                curr_ext_clock++;
            } else {
                free(rr_node[curr_ext_input].edges);
                rr_node[curr_ext_input].edges = NULL;
                rr_node[curr_ext_input].num_edges = 0;
                
                success = FALSE;
                ipin = 0;
                /* force intra-cluster net to use pins from ext route */
                for(j = 0; j < pb_graph_node->num_input_ports; j++) {
                    for(k = 0; k < pb_graph_node->num_input_pins[j]; k++) {
                        if(ext_net == block[iblock].nets[ipin + pin_offset]) {
                            success = TRUE;
                            rr_node[curr_ext_input].num_edges++;
                            rr_node[curr_ext_input].edges = (int*)my_realloc(rr_node[curr_ext_input].edges, rr_node[curr_ext_input].num_edges * sizeof(int));
                            rr_node[curr_ext_input].edges[rr_node[curr_ext_input].num_edges - 1] = pb_graph_node->input_pins[j][k].pin_count_in_cluster;
                        }
                        ipin++;
                    }
                }
                curr_ext_input++;
                assert(success);
            }           
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void free_cluster_legality_checker

(

void

)

Definition at line 219 of file cluster_legality.c.

                                         {
    int inet;
    free(best_routing);
    free(rr_indexed_data);
    free_rr_node_route_structs();
    free_route_structs();
    free_trace_structs();

    free_chunk_memory(&rr_mem_ch);

    for (inet = 0; inet < num_logical_nets; inet++) {
        free(saved_net_rr_terminals[inet]);
    }
    free(net_rr_terminals);
    free(nets_in_cluster);
    free(saved_net_rr_terminals);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void free_legalizer_for_cluster	(	INP t_block *	clb,
		boolean	free_local_rr_graph
	)

Definition at line 583 of file cluster_legality.c.

                                                                               {
    int i;

    free_rr_node_route_structs();
    if(free_local_rr_graph == TRUE) {
        for (i = 0; i < num_rr_nodes; i++) {
            if (clb->pb->rr_graph[i].edges != NULL) {
                free(clb->pb->rr_graph[i].edges);
            }
            if (clb->pb->rr_graph[i].switches != NULL) {
                free(clb->pb->rr_graph[i].switches);
            }
        }
        free(clb->pb->rr_graph);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

boolean is_pin_open

(

int

i

)

Definition at line 1137 of file cluster_legality.c.

                           {
    return (boolean) (rr_node[i].occ == 0);
}

void reload_ext_net_rr_terminal_cluster

(

void

)

Definition at line 153 of file cluster_legality.c.

                                              {
    int i, j, net_index;
    boolean has_ext_sink, has_ext_source;
    int curr_ext_output, curr_ext_input, curr_ext_clock;

    curr_ext_input = ext_input_rr_node_index;
    curr_ext_output = ext_output_rr_node_index;
    curr_ext_clock = ext_clock_rr_node_index;

    for (i = 0; i < num_nets_in_cluster; i++) {
        net_index = nets_in_cluster[i];
        has_ext_sink = FALSE;
        has_ext_source = (boolean)
                (logical_block[vpack_net[net_index].node_block[0]].clb_index
                        != curr_cluster_index);
        if (has_ext_source) {
            /* Instantiate a source of this net */
            if (vpack_net[net_index].is_global) {
                net_rr_terminals[net_index][0] = curr_ext_clock;
                curr_ext_clock++;
            } else {
                net_rr_terminals[net_index][0] = curr_ext_input;
                curr_ext_input++;
            }
        }
        for (j = 1; j <= vpack_net[net_index].num_sinks; j++) {
            if (logical_block[vpack_net[net_index].node_block[j]].clb_index
                    != curr_cluster_index) {
                if (has_ext_sink || has_ext_source) {
                    /* Only need one node driving external routing, either this cluster drives external routing or another cluster does it */
                    net_rr_terminals[net_index][j] = OPEN;
                } else {
                    /* External sink, only need to route once, externally routing will take care of the rest */
                    net_rr_terminals[net_index][j] = curr_ext_output;
                    curr_ext_output++;
                    has_ext_sink = TRUE;
                }
            }
        }

        if (curr_ext_input > ext_output_rr_node_index
                || curr_ext_output > ext_clock_rr_node_index
                || curr_ext_clock > max_ext_index) {
            /* failed, not enough pins of proper type, overran index */
            assert(0);
        }
    }
}

Here is the caller graph for this function:

void reset_legalizer_for_cluster

(

t_block *

clb

)

Definition at line 600 of file cluster_legality.c.

                                               {
    int i;
    for (i = 0; i < num_nets_in_cluster; i++) {
        free_traceback(nets_in_cluster[i]);
        trace_head[nets_in_cluster[i]] = best_routing[nets_in_cluster[i]];
        free_traceback(nets_in_cluster[i]);
        best_routing[nets_in_cluster[i]] = NULL;
    }

    free_rr_node_route_structs();
    num_nets_in_cluster = 0;
    saved_num_nets_in_cluster = 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void restore_routing_cluster

(

void

)

Definition at line 1048 of file cluster_legality.c.

                                   {

    /* Deallocates any current routing in trace_head, and replaces it with    *
     * the routing in best_routing.  Best_routing is set to NULL to show that *
     * it no longer points to a valid routing.  NOTE:  trace_tail is not      *
     * restored -- it is set to all NULLs since it is only used in            *
     * update_traceback.  If you need trace_tail restored, modify this        *
     * routine.  Also restores the locally used opin data.                    */

    int inet, i, j;

    for (i = 0; i < num_nets_in_cluster; i++) {
        inet = nets_in_cluster[i];

        pathfinder_update_one_cost(trace_head[inet], -1, pres_fac);

        /* Free any current routing. */
        free_traceback(inet);

        /* Set the current routing to the saved one. */
        trace_head[inet] = best_routing[inet];
        best_routing[inet] = NULL; /* No stored routing. */

        /* restore net terminals */
        for (j = 0; j <= vpack_net[inet].num_sinks; j++) {
            net_rr_terminals[inet][j] = saved_net_rr_terminals[inet][j];
        }

        /* restore old routing */
        pathfinder_update_one_cost(trace_head[inet], 1, pres_fac);
    }
    num_nets_in_cluster = saved_num_nets_in_cluster;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void save_and_reset_routing_cluster

(

void

)

Definition at line 1011 of file cluster_legality.c.

                                          {

    /* This routing frees any routing currently held in best routing,       *
     * then copies over the current routing (held in trace_head), and       *
     * finally sets trace_head and trace_tail to all NULLs so that the      *
     * connection to the saved routing is broken.  This is necessary so     *
     * that the next iteration of the router does not free the saved        *
     * routing elements.  Also, the routing path costs and net_rr_terminals is stripped from the
     * existing rr_graph so that the saved routing does not affect the graph */

    int inet, i, j;
    struct s_trace *tempptr;
    saved_num_nets_in_cluster = num_nets_in_cluster;

    for (i = 0; i < num_nets_in_cluster; i++) {
        inet = nets_in_cluster[i];
        for (j = 0; j <= vpack_net[inet].num_sinks; j++) {
            saved_net_rr_terminals[inet][j] = net_rr_terminals[inet][j];
        }

        /* Free any previously saved routing.  It is no longer best. */
        /* Also Save a pointer to the current routing in best_routing. */

        pathfinder_update_one_cost(trace_head[inet], -1, pres_fac);
        tempptr = trace_head[inet];
        trace_head[inet] = best_routing[inet];
        free_traceback(inet);
        best_routing[inet] = tempptr;

        /* Set the current (working) routing to NULL so the current trace       *
         * elements won't be reused by the memory allocator.                    */

        trace_head[inet] = NULL;
        trace_tail[inet] = NULL;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void save_cluster_solution

(

void

)

Definition at line 1082 of file cluster_legality.c.

                                 {

    /* This routine updates the occupancy and pres_cost of the rr_nodes that are *
     * affected by the portion of the routing of one net that starts at          *
     * route_segment_start.  If route_segment_start is trace_head[inet], the     *
     * cost of all the nodes in the routing of net inet are updated.  If         *
     * add_or_sub is -1 the net (or net portion) is ripped up, if it is 1 the    *
     * net is added to the routing.  The size of pres_fac determines how severly *
     * oversubscribed rr_nodes are penalized.                                    */

    int i, j, net_index;
    struct s_trace *tptr, *prev;
    int inode;
    for (i = 0; i < max_ext_index; i++) {
        rr_node[i].net_num = OPEN;
        rr_node[i].prev_edge = OPEN;
        rr_node[i].prev_node = OPEN;
    }
    for (i = 0; i < num_nets_in_cluster; i++) {
        prev = NULL;
        net_index = nets_in_cluster[i];
        tptr = trace_head[net_index];
        if (tptr == NULL) /* No routing yet. */
            return;

        for (;;) {
            inode = tptr->index;
            rr_node[inode].net_num = net_index;
            if (prev != NULL) {
                rr_node[inode].prev_node = prev->index;
                for (j = 0; j < rr_node[prev->index].num_edges; j++) {
                    if (rr_node[prev->index].edges[j] == inode) {
                        rr_node[inode].prev_edge = j;
                        break;
                    }
                }
                assert(j != rr_node[prev->index].num_edges);
            } else {
                rr_node[inode].prev_node = OPEN;
                rr_node[inode].prev_edge = OPEN;
            }

            if (rr_node[inode].type == SINK) {
                tptr = tptr->next; /* Skip next segment. */
                if (tptr == NULL)
                    break;
            }

            prev = tptr;
            tptr = tptr->next;

        } /* End while loop -- did an entire traceback. */
    }
}

Here is the caller graph for this function:

void set_pb_graph_mode	(	t_pb_graph_node *	pb_graph_node,
		int	mode,
		int	isOn
	)

Definition at line 1149 of file cluster_legality.c.

                                                                           {
    int i, j, index;
    int i_pb_type, i_pb_inst;
    const t_pb_type *pb_type;

    pb_type = pb_graph_node->pb_type;
    for (i_pb_type = 0; i_pb_type < pb_type->modes[mode].num_pb_type_children;
            i_pb_type++) {
        for (i_pb_inst = 0;
                i_pb_inst
                        < pb_type->modes[mode].pb_type_children[i_pb_type].num_pb;
                i_pb_inst++) {
            for (i = 0;
                    i
                            < pb_graph_node->child_pb_graph_nodes[mode][i_pb_type][i_pb_inst].num_input_ports;
                    i++) {
                for (j = 0;
                        j
                                < pb_graph_node->child_pb_graph_nodes[mode][i_pb_type][i_pb_inst].num_input_pins[i];
                        j++) {
                    index =
                            pb_graph_node->child_pb_graph_nodes[mode][i_pb_type][i_pb_inst].input_pins[i][j].pin_count_in_cluster;
                    rr_node[index].capacity = isOn;
                }
            }

            for (i = 0;
                    i
                            < pb_graph_node->child_pb_graph_nodes[mode][i_pb_type][i_pb_inst].num_output_ports;
                    i++) {
                for (j = 0;
                        j
                                < pb_graph_node->child_pb_graph_nodes[mode][i_pb_type][i_pb_inst].num_output_pins[i];
                        j++) {
                    index =
                            pb_graph_node->child_pb_graph_nodes[mode][i_pb_type][i_pb_inst].output_pins[i][j].pin_count_in_cluster;
                    rr_node[index].capacity = isOn;
                }
            }

            for (i = 0;
                    i
                            < pb_graph_node->child_pb_graph_nodes[mode][i_pb_type][i_pb_inst].num_clock_ports;
                    i++) {
                for (j = 0;
                        j
                                < pb_graph_node->child_pb_graph_nodes[mode][i_pb_type][i_pb_inst].num_clock_pins[i];
                        j++) {
                    index =
                            pb_graph_node->child_pb_graph_nodes[mode][i_pb_type][i_pb_inst].clock_pins[i][j].pin_count_in_cluster;
                    rr_node[index].capacity = isOn;
                }
            }
        }
    }
}

Here is the caller graph for this function:

void setup_intracluster_routing_for_logical_block	(	INP int	iblock,
		INP t_pb_graph_node *	primitive
	)

Definition at line 947 of file cluster_legality.c.

                                        {

    /* Allocates and loads the net_rr_terminals data structure.  For each net   *
     * it stores the rr_node index of the SOURCE of the net and all the SINKs   *
     * of the net.  [0..num_logical_nets-1][0..num_pins-1].   */
    int ipin, iblk_net;
    t_model_ports *port;

    assert(primitive->pb_type->num_modes == 0);
    /* check if primitive */
    assert(logical_block[iblock].clb_index != NO_CLUSTER);
    /* check if primitive and block is open */

    /* check if block type matches primitive type */
    if (logical_block[iblock].model != primitive->pb_type->model) {
        /* End early, model is incompatible */
        assert(0);
    }

    /* for each net of logical block, check if it is in cluster, if not add it */
    /*   also check if pins on primitive can fit logical block */

    port = logical_block[iblock].model->inputs;

    while (port) {
        for (ipin = 0; ipin < port->size; ipin++) {
            if (port->is_clock) {
                assert(port->size == 1);
                iblk_net = logical_block[iblock].clock_net;
            } else {
                iblk_net = logical_block[iblock].input_nets[port->index][ipin];
            }
            if (iblk_net == OPEN) {
                continue;
            }
            if (!is_net_in_cluster(iblk_net)) {
                nets_in_cluster[num_nets_in_cluster] = iblk_net;
                num_nets_in_cluster++;
            }
            add_net_rr_terminal_cluster(iblk_net, primitive, iblock, port,
                    ipin);
        }
        port = port->next;
    }

    port = logical_block[iblock].model->outputs;
    while (port) {
        for (ipin = 0; ipin < port->size; ipin++) {
            iblk_net = logical_block[iblock].output_nets[port->index][ipin];
            if (iblk_net == OPEN) {
                continue;
            }
            if (!is_net_in_cluster(iblk_net)) {
                nets_in_cluster[num_nets_in_cluster] = iblk_net;
                num_nets_in_cluster++;
            }
            add_net_rr_terminal_cluster(iblk_net, primitive, iblock, port,
                    ipin);
        }
        port = port->next;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void setup_intracluster_routing_for_molecule	(	INP t_pack_molecule *	molecule,
		INOUTP t_pb_graph_node **	primitives_list
	)

boolean try_breadth_first_route_cluster

(

void

)

internal_nets: index of nets to route [0..num_internal_nets - 1]

Definition at line 618 of file cluster_legality.c.

                                              {

    /* Iterated maze router ala Pathfinder Negotiated Congestion algorithm,  *
     * (FPGA 95 p. 111).  Returns TRUE if it can route this FPGA, FALSE if   *
     * it can't.                                                             */

    /* For different modes, when a mode is turned on, I set the max occupancy of all rr_nodes in the mode to 1 and all others to 0 */
    /* TODO: There is a bug for route-throughs where edges in route-throughs do not get turned off because the rr_edge is in a particular mode but the two rr_nodes are outside */

    boolean success, is_routable;
    int itry, inet, net_index;
    struct s_router_opts router_opts;

    /* Usually the first iteration uses a very small (or 0) pres_fac to find  *
     * the shortest path and get a congestion map.  For fast compiles, I set  *
     * pres_fac high even for the first iteration.                            */

    /* sets up a fast breadth-first router */
    router_opts.first_iter_pres_fac = 10;
    router_opts.max_router_iterations = 20;
    router_opts.initial_pres_fac = 10;
    router_opts.pres_fac_mult = 2;
    router_opts.acc_fac = 1;

    reset_rr_node_route_structs(); /* Clear all prior rr_graph history */

    pres_fac = router_opts.first_iter_pres_fac;

    for (itry = 1; itry <= router_opts.max_router_iterations; itry++) {
        for (inet = 0; inet < num_nets_in_cluster; inet++) {
            net_index = nets_in_cluster[inet];

            pathfinder_update_one_cost(trace_head[net_index], -1, pres_fac);

            is_routable = breadth_first_route_net_cluster(net_index);

            /* Impossible to route? (disconnected rr_graph) */

            if (!is_routable) {
                /* TODO: Inelegant, can be more intelligent */
                vpr_printf(TIO_MESSAGE_INFO, "Failed routing net %s\n", vpack_net[net_index].name);
                vpr_printf(TIO_MESSAGE_INFO, "Routing failed. Disconnected rr_graph.\n");
                return FALSE;
            }

            pathfinder_update_one_cost(trace_head[net_index], 1, pres_fac);

        }

        success = feasible_routing();
        if (success) {
            return (TRUE);
        }

        if (itry == 1)
            pres_fac = router_opts.initial_pres_fac;
        else
            pres_fac *= router_opts.pres_fac_mult;

        pres_fac = std::min(pres_fac, static_cast<float>(HUGE_POSITIVE_FLOAT / 1e5));

        pathfinder_update_cost(pres_fac, router_opts.acc_fac);
    }

    return (FALSE);
}

Here is the call graph for this function:

Here is the caller graph for this function: