#include "arch_types.h"
#include "util.h"

Include dependency graph for cluster_placement.h:

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

Functions
t_cluster_placement_stats *	alloc_and_load_cluster_placement_stats (void)

boolean	get_next_primitive_list (INOUTP t_cluster_placement_stats cluster_placement_stats, INP t_pack_molecule molecule, INOUTP t_pb_graph_node **primitives_list, INP int clb_index)

void	commit_primitive (INOUTP t_cluster_placement_stats cluster_placement_stats, INP t_pb_graph_node primitive)

void	set_mode_cluster_placement_stats (INP t_pb_graph_node *complex_block, int mode)

void	reset_cluster_placement_stats (INOUTP t_cluster_placement_stats *cluster_placement_stats)

void	free_cluster_placement_stats (INOUTP t_cluster_placement_stats *cluster_placement_stats)

int	get_array_size_of_molecule (t_pack_molecule *molecule)

boolean	exists_free_primitive_for_logical_block (INOUTP t_cluster_placement_stats *cluster_placement_stats, INP int ilogical_block)

void	reset_tried_but_unused_cluster_placements (INOUTP t_cluster_placement_stats *cluster_placement_stats)

Function Documentation

t_cluster_placement_stats* alloc_and_load_cluster_placement_stats ( void )

[0..num_pb_types-1] array of cluster placement stats, one for each type_descriptors

Definition at line 56 of file cluster_placement.c.

                                                                         {
     t_cluster_placement_stats *cluster_placement_stats_list;
     int i;
 
     cluster_placement_stats_list = (t_cluster_placement_stats *) my_calloc(num_types,
             sizeof(t_cluster_placement_stats));
     for (i = 0; i < num_types; i++) {
         if (EMPTY_TYPE != &type_descriptors[i]) {
             cluster_placement_stats_list[i].valid_primitives = (t_cluster_placement_primitive **) my_calloc(
                     get_max_primitives_in_pb_type(type_descriptors[i].pb_type)
                             + 1, sizeof(t_cluster_placement_primitive*)); /* too much memory allocated but shouldn't be a problem */
             cluster_placement_stats_list[i].curr_molecule = NULL;
             load_cluster_placement_stats_for_pb_graph_node(
                     &cluster_placement_stats_list[i],
                     type_descriptors[i].pb_graph_head);
         }
     }
     return cluster_placement_stats_list;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void commit_primitive	(	INOUTP t_cluster_placement_stats *	cluster_placement_stats,
		INP t_pb_graph_node *	primitive
	)

Commit primitive, invalidate primitives blocked by mode assignment and update costs for primitives in same cluster as current Costing is done to try to pack blocks closer to existing primitives actual value based on closest common ancestor to committed placement, the farther the ancestor, the less reduction in cost there is Side effects: All cluster_placement_primitives may be invalidated/costed in this algorithm Al intermediate queues are requeued

Definition at line 347 of file cluster_placement.c.

                                         {
     t_pb_graph_node *pb_graph_node, *skip;
     float incr_cost;
     int i, j, k;
     int valid_mode;
     t_cluster_placement_primitive *cur;
 
     /* Clear out intermediate queues */
     flush_intermediate_queues(cluster_placement_stats);
 
     /* commit primitive as used, invalidate it */
     cur = primitive->cluster_placement_primitive;
     assert(cur->valid == TRUE);
 
     cur->valid = FALSE;
     incr_cost = -0.01; /* cost of using a node drops as its neighbours are used, this drop should be small compared to scarcity values */
 
     pb_graph_node = cur->pb_graph_node;
     /* walk up pb_graph_node and update primitives of children */
     while (pb_graph_node->parent_pb_graph_node != NULL) {
         skip = pb_graph_node; /* do not traverse stuff that's already traversed */
         valid_mode = pb_graph_node->pb_type->parent_mode->index;
         pb_graph_node = pb_graph_node->parent_pb_graph_node;
         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++) {
                     if (&pb_graph_node->child_pb_graph_nodes[i][j][k] != skip) {
                         update_primitive_cost_or_status(
                                 &pb_graph_node->child_pb_graph_nodes[i][j][k],
                                 incr_cost, (boolean)(i == valid_mode));
                     }
                 }
             }
         }
         incr_cost /= 10; /* blocks whose ancestor is further away in tree should be affected less than blocks closer in tree */
     }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

boolean exists_free_primitive_for_logical_block	(	INOUTP t_cluster_placement_stats *	cluster_placement_stats,
		INP int	ilogical_block
	)

Definition at line 701 of file cluster_placement.c.

                                 {
     int i;
     t_cluster_placement_primitive *cur, *prev;
 
     /* might have a primitive in flight that's still valid */
     if (cluster_placement_stats->in_flight) {
         if (primitive_type_feasible(ilogical_block,
                 cluster_placement_stats->in_flight->pb_graph_node->pb_type)) {
             return TRUE;
         }
     }
 
     /* Look through list of available primitives to see if any valid */
     for (i = 0; i < cluster_placement_stats->num_pb_types; i++) {
         if (cluster_placement_stats->valid_primitives[i]->next_primitive == NULL) {
             continue; /* no more primitives of this type available */
         }
         if (primitive_type_feasible(ilogical_block,
                 cluster_placement_stats->valid_primitives[i]->next_primitive->pb_graph_node->pb_type)) {
             prev = cluster_placement_stats->valid_primitives[i];
             cur = cluster_placement_stats->valid_primitives[i]->next_primitive;
             while (cur) {
                 /* remove invalid nodes lazily when encountered */
                 while (cur && cur->valid == FALSE) {
                     prev->next_primitive = cur->next_primitive;
                     cur->next_primitive = cluster_placement_stats->invalid;
                     cluster_placement_stats->invalid = cur;
                     cur = prev->next_primitive;
                 }
                 if (cur == NULL) {
                     break;
                 }
                 return TRUE;
             }
         }
     }
 
     return FALSE;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void free_cluster_placement_stats ( INOUTP t_cluster_placement_stats * cluster_placement_stats_list )

Free linked lists found in cluster_placement_stats_list

Definition at line 214 of file cluster_placement.c.

                                                                         {
     t_cluster_placement_primitive *cur, *next;
     int i, j;
     for (i = 0; i < num_types; i++) {
         cur = cluster_placement_stats_list[i].tried;
         while (cur != NULL) {
             next = cur->next_primitive;
             free(cur);
             cur = next;
         }
         cur = cluster_placement_stats_list[i].in_flight;
         while (cur != NULL) {
             next = cur->next_primitive;
             free(cur);
             cur = next;
         }
         cur = cluster_placement_stats_list[i].invalid;
         while (cur != NULL) {
             next = cur->next_primitive;
             free(cur);
             cur = next;
         }
         for (j = 0; j < cluster_placement_stats_list[i].num_pb_types; j++) {
             cur =
                     cluster_placement_stats_list[i].valid_primitives[j]->next_primitive;
             while (cur != NULL) {
                 next = cur->next_primitive;
                 free(cur);
                 cur = next;
             }
             free(cluster_placement_stats_list[i].valid_primitives[j]);
         }
         free(cluster_placement_stats_list[i].valid_primitives);
     }
     free(cluster_placement_stats_list);
 }

Here is the caller graph for this function:

int get_array_size_of_molecule ( t_pack_molecule * molecule )

Definition at line 692 of file cluster_placement.c.

                                                           {
     if (molecule->type == MOLECULE_FORCED_PACK) {
         return molecule->pack_pattern->num_blocks;
     } else {
         return molecule->num_blocks;
     }
 }

Here is the caller graph for this function:

boolean get_next_primitive_list	(	INOUTP t_cluster_placement_stats *	cluster_placement_stats,
		INP t_pack_molecule *	molecule,
		INOUTP t_pb_graph_node **	primitives_list,
		INP int	clb_index
	)

get next list of primitives for list of logical blocks primitives is the list of ptrs to primitives that matches with the list of logical_blocks (by index), assumes memory is preallocated

if this is a new block, requeue tried primitives and return a in-flight primitive list to try
if this is an old block, put root primitive to tried queue, requeue rest of primitives. try another set of primitives

return TRUE if can find next primitive, FALSE otherwise

cluster_placement_stats - ptr to the current cluster_placement_stats of open complex block molecule - molecule to pack into open complex block primitives_list - a list of primitives indexed to match logical_block_ptrs of molecule. Expects an allocated array of primitives ptrs as inputs. This function loads the array with the lowest cost primitives that implement molecule

Definition at line 88 of file cluster_placement.c.

                                                                                                     {
     t_cluster_placement_primitive *cur, *next, *best, *before_best, *prev;
     int i;
     float cost, lowest_cost;
     best = NULL;
     before_best = NULL;
 
     if (cluster_placement_stats->curr_molecule != molecule) {
         /* New block, requeue tried primitives and in-flight primitives */
         flush_intermediate_queues(cluster_placement_stats);
 
         cluster_placement_stats->curr_molecule = molecule;
     } else {
         /* Hack! Same failed molecule may re-enter if upper stream functions suck, I'm going to make the molecule selector more intelligent, TODO: Remove later */
         if (cluster_placement_stats->in_flight != NULL) {
             /* Hack end */
 
             /* old block, put root primitive currently inflight to tried queue  */
             cur = cluster_placement_stats->in_flight;
             next = cur->next_primitive;
             cur->next_primitive = cluster_placement_stats->tried;
             cluster_placement_stats->tried = cur;
             /* should have only one block in flight at any point in time */
             assert(next == NULL);
             cluster_placement_stats->in_flight = NULL;
         }
     }
 
     /* find next set of blocks 
      1. Remove invalid blocks to invalid queue
      2. Find lowest cost array of primitives that implements blocks
      3. When found, move current blocks to in-flight, return lowest cost array of primitives
      4. Return NULL if not found
      */
     lowest_cost = HUGE_POSITIVE_FLOAT;
     for (i = 0; i < cluster_placement_stats->num_pb_types; i++) {
         if (cluster_placement_stats->valid_primitives[i]->next_primitive == NULL) {
             continue; /* no more primitives of this type available */
         }
         if (primitive_type_feasible(
                 molecule->logical_block_ptrs[molecule->root]->index,
                 cluster_placement_stats->valid_primitives[i]->next_primitive->pb_graph_node->pb_type)) {
             prev = cluster_placement_stats->valid_primitives[i];
             cur = cluster_placement_stats->valid_primitives[i]->next_primitive;
             while (cur) {
                 /* remove invalid nodes lazily when encountered */
                 while (cur && cur->valid == FALSE) {
                     prev->next_primitive = cur->next_primitive;
                     cur->next_primitive = cluster_placement_stats->invalid;
                     cluster_placement_stats->invalid = cur;
                     cur = prev->next_primitive;
                 }
                 if (cur == NULL) {
                     break;
                 }
                 /* try place molecule at root location cur */
                 cost = try_place_molecule(molecule, cur->pb_graph_node,
                         primitives_list, clb_index);
                 if (cost < lowest_cost) {
                     lowest_cost = cost;
                     best = cur;
                     before_best = prev;
                 }
                 prev = cur;
                 cur = cur->next_primitive;
             }
         }
     }
     if (best == NULL) {
         /* failed to find a placement */
         for (i = 0; i < molecule->num_blocks; i++) {
             primitives_list[i] = NULL;
         }
     } else {
         /* populate primitive list with best */
         cost = try_place_molecule(molecule, best->pb_graph_node, primitives_list, clb_index);
         assert(cost == lowest_cost);
 
         /* take out best node and put it in flight */
         cluster_placement_stats->in_flight = best;
         before_best->next_primitive = best->next_primitive;
         best->next_primitive = NULL;
     }
 
     if (best == NULL) {
         return FALSE;
     }
     return TRUE;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void reset_cluster_placement_stats ( INOUTP t_cluster_placement_stats * cluster_placement_stats )

Resets one cluster placement stats by clearing incremental costs and returning all primitives to valid queue

Definition at line 183 of file cluster_placement.c.

                                                                    {
     t_cluster_placement_primitive *cur, *next;
     int i;
 
     /* Requeue primitives */
     flush_intermediate_queues(cluster_placement_stats);
     cur = cluster_placement_stats->invalid;
     while (cur != NULL) {
         next = cur->next_primitive;
         requeue_primitive(cluster_placement_stats, cur);
         cur = next;
     }
     cur = cluster_placement_stats->invalid = NULL;
     /* reset flags and cost */
     for (i = 0; i < cluster_placement_stats->num_pb_types; i++) {
         assert(
                 cluster_placement_stats->valid_primitives[i] != NULL && cluster_placement_stats->valid_primitives[i]->next_primitive != NULL);
         cur = cluster_placement_stats->valid_primitives[i]->next_primitive;
         while (cur != NULL) {
             cur->incremental_cost = 0;
             cur->valid = TRUE;
             cur = cur->next_primitive;
         }
     }
     cluster_placement_stats->curr_molecule = NULL;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void reset_tried_but_unused_cluster_placements ( INOUTP t_cluster_placement_stats * cluster_placement_stats )

Definition at line 744 of file cluster_placement.c.

                                                                    {
     flush_intermediate_queues(cluster_placement_stats);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void set_mode_cluster_placement_stats	(	INP t_pb_graph_node *	pb_graph_node,
		int	mode
	)

Set mode of cluster

Definition at line 394 of file cluster_placement.c.

                   {
     int i, j, k;
     for (i = 0; i < pb_graph_node->pb_type->num_modes; i++) {
         if (i != mode) {
             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++) {
                     update_primitive_cost_or_status(
                             &pb_graph_node->child_pb_graph_nodes[i][j][k], 0,
                             FALSE);
                 }
             }
         }
     }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

Functions

Function Documentation