VPR-7.0
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros
prepack.c File Reference
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include "read_xml_arch_file.h"
#include "util.h"
#include "vpr_types.h"
#include "globals.h"
#include "hash.h"
#include "prepack.h"
#include "vpr_utils.h"
#include "ReadOptions.h"
+ Include dependency graph for prepack.c:

Go to the source code of this file.

Functions

static int add_pattern_name_to_hash (INOUTP struct s_hash **nhash, INP char *pattern_name, INOUTP int *ncount)
 
static void discover_pattern_names_in_pb_graph_node (INOUTP t_pb_graph_node *pb_graph_node, INOUTP struct s_hash **nhash, INOUTP int *ncount)
 
static void forward_infer_pattern (INOUTP t_pb_graph_pin *pb_graph_pin)
 
static void backward_infer_pattern (INOUTP t_pb_graph_pin *pb_graph_pin)
 
static t_pack_patternsalloc_and_init_pattern_list_from_hash (INP int ncount, INOUTP struct s_hash **nhash)
 
static t_pb_graph_edgefind_expansion_edge_of_pattern (INP int pattern_index, INP t_pb_graph_node *pb_graph_node)
 
static void forward_expand_pack_pattern_from_edge (INP t_pb_graph_edge *expansion_edge, INOUTP t_pack_patterns *list_of_packing_patterns, INP int curr_pattern_index, INP int *L_num_blocks, INP boolean make_root_of_chain)
 
static void backward_expand_pack_pattern_from_edge (INP t_pb_graph_edge *expansion_edge, INOUTP t_pack_patterns *list_of_packing_patterns, INP int curr_pattern_index, INP t_pb_graph_pin *destination_pin, INP t_pack_pattern_block *destination_block, INP int *L_num_blocks)
 
static int compare_pack_pattern (const t_pack_patterns *pattern_a, const t_pack_patterns *pattern_b)
 
static void free_pack_pattern (INOUTP t_pack_pattern_block *pattern_block, INOUTP t_pack_pattern_block **pattern_block_list)
 
static t_pack_moleculetry_create_molecule (INP t_pack_patterns *list_of_pack_patterns, INP int pack_pattern_index, INP int block_index)
 
static boolean try_expand_molecule (INOUTP t_pack_molecule *molecule, INP int logical_block_index, INP t_pack_pattern_block *current_pattern_block)
 
static void print_pack_molecules (INP const char *fname, INP t_pack_patterns *list_of_pack_patterns, INP int num_pack_patterns, INP t_pack_molecule *list_of_molecules)
 
static t_pb_graph_nodeget_expected_lowest_cost_primitive_for_logical_block (INP int ilogical_block)
 
static t_pb_graph_nodeget_expected_lowest_cost_primitive_for_logical_block_in_pb_graph_node (INP int ilogical_block, INP t_pb_graph_node *curr_pb_graph_node, OUTP float *cost)
 
static int find_new_root_atom_for_chain (INP int block_index, INP t_pack_patterns *list_of_pack_pattern)
 
t_pack_patternsalloc_and_load_pack_patterns (OUTP int *num_packing_patterns)
 
void free_list_of_pack_patterns (INP t_pack_patterns *list_of_pack_patterns, INP int num_packing_patterns)
 
static void forward_expand_pack_pattern_from_edge (INP t_pb_graph_edge *expansion_edge, INOUTP t_pack_patterns *list_of_packing_patterns, INP int curr_pattern_index, INP int *L_num_blocks, INOUTP boolean make_root_of_chain)
 
t_pack_moleculealloc_and_load_pack_molecules (INP t_pack_patterns *list_of_pack_patterns, INP int num_packing_patterns, OUTP int *num_pack_molecule)
 

Function Documentation

static int add_pattern_name_to_hash ( INOUTP struct s_hash **  nhash,
INP char *  pattern_name,
INOUTP int *  ncount 
)
static

Adds pack pattern name to hashtable of pack pattern names.

Definition at line 130 of file prepack.c.

131  {
132  struct s_hash *hash_value;
133 
134  hash_value = insert_in_hash_table(nhash, pattern_name, *ncount);
135  if (hash_value->count == 1) {
136  assert(*ncount == hash_value->index);
137  (*ncount)++;
138  }
139  return hash_value->index;
140 }
int count
Definition: hash.h:6
int index
Definition: hash.h:5
int hash_value(char *name)
Definition: hash.c:140
struct s_hash * insert_in_hash_table(struct s_hash **hash_table, char *name, int next_free_index)
Definition: hash.c:76
Definition: hash.h:3

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static t_pack_patterns * alloc_and_init_pattern_list_from_hash ( INP int  ncount,
INOUTP struct s_hash **  nhash 
)
static

Allocates memory for models and loads the name of the packing pattern so that it can be identified and loaded with more complete information later

Definition at line 298 of file prepack.c.

299  {
300  t_pack_patterns *nlist;
301  struct s_hash_iterator hash_iter;
302  struct s_hash *curr_pattern;
303 
304  nlist = (t_pack_patterns*)my_calloc(ncount, sizeof(t_pack_patterns));
305 
306  hash_iter = start_hash_table_iterator();
307  curr_pattern = get_next_hash(nhash, &hash_iter);
308  while (curr_pattern != NULL) {
309  assert(nlist[curr_pattern->index].name == NULL);
310  nlist[curr_pattern->index].name = my_strdup(curr_pattern->name);
311  nlist[curr_pattern->index].root_block = NULL;
312  nlist[curr_pattern->index].is_chain = FALSE;
313  nlist[curr_pattern->index].index = curr_pattern->index;
314  curr_pattern = get_next_hash(nhash, &hash_iter);
315  }
316  return nlist;
317 }
struct s_hash_iterator start_hash_table_iterator(void)
Definition: hash.c:38
int index
Definition: hash.h:5
boolean is_chain
Definition: cad_types.h:38
void * my_calloc(size_t nelem, size_t size)
Definition: util.c:132
char * name
Definition: hash.h:4
Definition: util.h:12
struct s_hash * get_next_hash(struct s_hash **hash_table, struct s_hash_iterator *hash_iterator)
Definition: hash.c:51
char * my_strdup(const char *str)
Definition: util.c:101
t_pack_pattern_block * root_block
Definition: cad_types.h:33
Definition: hash.h:3

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

t_pack_molecule* alloc_and_load_pack_molecules ( INP t_pack_patterns list_of_pack_patterns,
INP int  num_packing_patterns,
OUTP int *  num_pack_molecule 
)

Pre-pack atoms in netlist to molecules

  1. Single atoms are by definition a molecule.
  2. Forced pack molecules are groupings of atoms that matches a t_pack_pattern definition.
  3. Chained molecules are molecules that follow a carry-chain style pattern: ie. a single linear chain that can be split across multiple complex blocks

Definition at line 756 of file prepack.c.

758  {
759  int i, j, best_pattern;
760  t_pack_molecule *list_of_molecules_head;
761  t_pack_molecule *cur_molecule;
762  boolean *is_used;
763 
764  is_used = (boolean*)my_calloc(num_packing_patterns, sizeof(boolean));
765 
766  cur_molecule = list_of_molecules_head = NULL;
767 
768  /* Find forced pack patterns */
769  /* Simplifying assumptions: Each atom can map to at most one molecule, use first-fit mapping based on priority of pattern */
770  /* TODO: Need to investigate better mapping strategies than first-fit */
771  for (i = 0; i < num_packing_patterns; i++) {
772  best_pattern = 0;
773  for(j = 1; j < num_packing_patterns; j++) {
774  if(is_used[best_pattern]) {
775  best_pattern = j;
776  } else if (is_used[j] == FALSE && compare_pack_pattern(&list_of_pack_patterns[j], &list_of_pack_patterns[best_pattern]) == 1) {
777  best_pattern = j;
778  }
779  }
780  assert(is_used[best_pattern] == FALSE);
781  is_used[best_pattern] = TRUE;
782  for (j = 0; j < num_logical_blocks; j++) {
783  cur_molecule = try_create_molecule(list_of_pack_patterns, best_pattern, j);
784  if (cur_molecule != NULL) {
785  cur_molecule->next = list_of_molecules_head;
786  /* In the event of multiple molecules with the same logical block pattern, bias to use the molecule with less costly physical resources first */
787  /* TODO: Need to normalize magical number 100 */
788  cur_molecule->base_gain = cur_molecule->num_blocks
789  - (cur_molecule->pack_pattern->base_cost / 100);
790  list_of_molecules_head = cur_molecule;
791  if(logical_block[j].packed_molecules == NULL || logical_block[j].packed_molecules->data_vptr != cur_molecule) {
792  /* molecule did not cover current atom (possibly because molecule created is part of a long chain that extends past multiple logic blocks), try again */
793  j--;
794  }
795  }
796  }
797  }
798  free(is_used);
799 
800  /* List all logical blocks as a molecule for blocks that do not belong to any molecules.
801  This allows the packer to be consistent as it now packs molecules only instead of atoms and molecules
802 
803  If a block belongs to a molecule, then carrying the single atoms around can make the packing problem
804  more difficult because now it needs to consider splitting molecules.
805  */
806  for (i = 0; i < num_logical_blocks; i++) {
808  if (logical_block[i].packed_molecules == NULL) {
809  cur_molecule = (t_pack_molecule*) my_calloc(1,
810  sizeof(t_pack_molecule));
811  cur_molecule->valid = TRUE;
812  cur_molecule->type = MOLECULE_SINGLE_ATOM;
813  cur_molecule->num_blocks = 1;
814  cur_molecule->root = 0;
815  cur_molecule->num_ext_inputs = logical_block[i].used_input_pins;
816  cur_molecule->chain_pattern = NULL;
817  cur_molecule->pack_pattern = NULL;
818  cur_molecule->logical_block_ptrs = (t_logical_block**) my_malloc(
819  1 * sizeof(t_logical_block*));
820  cur_molecule->logical_block_ptrs[0] = &logical_block[i];
821  cur_molecule->next = list_of_molecules_head;
822  cur_molecule->base_gain = 1;
823  list_of_molecules_head = cur_molecule;
824 
826  sizeof(struct s_linked_vptr));
827  logical_block[i].packed_molecules->data_vptr = (void*) cur_molecule;
828  }
829  }
830 
833  list_of_pack_patterns, num_packing_patterns,
834  list_of_molecules_head);
835  }
836 
837  return list_of_molecules_head;
838 }
void * my_calloc(size_t nelem, size_t size)
Definition: util.c:132
struct s_linked_vptr * packed_molecules
Definition: vpr_types.h:228
boolean getEchoEnabled(void)
Definition: ReadOptions.c:67
t_pack_patterns * pack_pattern
Definition: vpr_types.h:246
static void print_pack_molecules(INP const char *fname, INP t_pack_patterns *list_of_pack_patterns, INP int num_pack_patterns, INP t_pack_molecule *list_of_molecules)
Definition: prepack.c:1009
Definition: util.h:12
static void * my_malloc(int ibytes)
Definition: graphics.c:499
static int compare_pack_pattern(const t_pack_patterns *pattern_a, const t_pack_patterns *pattern_b)
Definition: prepack.c:1124
boolean isEchoFileEnabled(enum e_echo_files echo_option)
Definition: ReadOptions.c:115
struct s_pack_molecule * next
Definition: vpr_types.h:257
void * data_vptr
Definition: util.h:35
int num_logical_blocks
Definition: globals.c:17
enum e_pack_pattern_molecule_type type
Definition: vpr_types.h:245
static t_pack_molecule * try_create_molecule(INP t_pack_patterns *list_of_pack_patterns, INP int pack_pattern_index, INP int block_index)
Definition: prepack.c:867
char * getEchoFileName(enum e_echo_files echo_option)
Definition: ReadOptions.c:122
t_logical_block ** logical_block_ptrs
Definition: vpr_types.h:248
static t_pb_graph_node * get_expected_lowest_cost_primitive_for_logical_block(INP int ilogical_block)
Definition: prepack.c:1063
boolean valid
Definition: vpr_types.h:249
struct s_logical_block * logical_block
Definition: globals.c:20
Definition: util.h:12
t_pb_graph_node * expected_lowest_cost_primitive
Definition: vpr_types.h:230
float base_cost
Definition: cad_types.h:34
t_model_chain_pattern * chain_pattern
Definition: vpr_types.h:247

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

t_pack_patterns* alloc_and_load_pack_patterns ( OUTP int *  num_packing_patterns)

Find all packing patterns in architecture [0..num_packing_patterns-1]

Limitations: Currently assumes that forced pack nets must be single-fanout as this covers all the reasonable architectures we wanted. More complicated structures should probably be handled either downstream (general packing) or upstream (in tech mapping) If this limitation is too constraining, code is designed so that this limitation can be removed

Definition at line 75 of file prepack.c.

75  {
76  int i, j, ncount, k;
77  int L_num_blocks;
78  struct s_hash **nhash;
79  t_pack_patterns *list_of_packing_patterns;
80  t_pb_graph_edge *expansion_edge;
81 
82  /* alloc and initialize array of packing patterns based on architecture complex blocks */
83  nhash = alloc_hash_table();
84  ncount = 0;
85  for (i = 0; i < num_types; i++) {
87  type_descriptors[i].pb_graph_head, nhash, &ncount);
88  }
89 
90  list_of_packing_patterns = alloc_and_init_pattern_list_from_hash(ncount,
91  nhash);
92 
93  /* load packing patterns by traversing the edges to find edges belonging to pattern */
94  for (i = 0; i < ncount; i++) {
95  for (j = 0; j < num_types; j++) {
96  expansion_edge = find_expansion_edge_of_pattern(i,
97  type_descriptors[j].pb_graph_head);
98  if (expansion_edge == NULL) {
99  continue;
100  }
101  L_num_blocks = 0;
102  list_of_packing_patterns[i].base_cost = 0;
104  list_of_packing_patterns, i, NULL, NULL, &L_num_blocks);
105  list_of_packing_patterns[i].num_blocks = L_num_blocks;
106 
107  /* Default settings: A section of a netlist must match all blocks in a pack pattern before it can be made a molecule except for carry-chains. For carry-chains, since carry-chains are typically
108  quite flexible in terms of size, it is optional whether or not an atom in a netlist matches any particular block inside the chain */
109  list_of_packing_patterns[i].is_block_optional = (boolean*) my_malloc(L_num_blocks * sizeof(boolean));
110  for(k = 0; k < L_num_blocks; k++) {
111  list_of_packing_patterns[i].is_block_optional[k] = FALSE;
112  if(list_of_packing_patterns[i].is_chain && list_of_packing_patterns[i].root_block->block_id != k) {
113  list_of_packing_patterns[i].is_block_optional[k] = TRUE;
114  }
115  }
116  break;
117  }
118  }
119 
120  free_hash_table(nhash);
121 
122  *num_packing_patterns = ncount;
123 
124  return list_of_packing_patterns;
125 }
struct s_hash ** alloc_hash_table(void)
Definition: hash.c:7
boolean * is_block_optional
Definition: cad_types.h:36
Definition: util.h:12
void free_hash_table(struct s_hash **hash_table)
Definition: hash.c:18
static void * my_malloc(int ibytes)
Definition: graphics.c:499
static void discover_pattern_names_in_pb_graph_node(INOUTP t_pb_graph_node *pb_graph_node, INOUTP struct s_hash **nhash, INOUTP int *ncount)
Definition: prepack.c:147
static t_pack_patterns * alloc_and_init_pattern_list_from_hash(INP int ncount, INOUTP struct s_hash **nhash)
Definition: prepack.c:298
int num_types
Definition: globals.c:37
struct s_type_descriptor * type_descriptors
Definition: globals.c:38
static void backward_expand_pack_pattern_from_edge(INP t_pb_graph_edge *expansion_edge, INOUTP t_pack_patterns *list_of_packing_patterns, INP int curr_pattern_index, INP t_pb_graph_pin *destination_pin, INP t_pack_pattern_block *destination_block, INP int *L_num_blocks)
Definition: prepack.c:572
static t_pb_graph_edge * find_expansion_edge_of_pattern(INP int pattern_index, INP t_pb_graph_node *pb_graph_node)
Definition: prepack.c:341
Definition: hash.h:3
Definition: util.h:12
float base_cost
Definition: cad_types.h:34

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static void backward_expand_pack_pattern_from_edge ( INP t_pb_graph_edge expansion_edge,
INOUTP t_pack_patterns list_of_packing_patterns,
INP int  curr_pattern_index,
INP t_pb_graph_pin destination_pin,
INP t_pack_pattern_block destination_block,
INP int *  L_num_blocks 
)
static

Find if driver of edge is in the same pattern, if yes, add to pattern Convention: Connections are made on backward expansion only (to make future multi-fanout support easier) so this function must update both source and destination blocks

Definition at line 572 of file prepack.c.

576  {
577  int i, j, k;
578  int iport, ipin, iedge;
579  boolean found; /* Error checking, ensure only one fan-out for each pattern net */
580  t_pack_pattern_block *source_block = NULL;
581  t_pb_graph_node *source_pb_graph_node = NULL;
582  t_pack_pattern_connections *pack_pattern_connection = NULL;
583 
584  found = expansion_edge->infer_pattern;
585  for (i = 0; !found && i < expansion_edge->num_pack_patterns; i++) {
586  if (expansion_edge->pack_pattern_indices[i] == curr_pattern_index) {
587  found = TRUE;
588  }
589  }
590  if (!found) {
591  return;
592  }
593 
594  found = FALSE;
595  for (i = 0; i < expansion_edge->num_input_pins; i++) {
596  if (expansion_edge->input_pins[i]->parent_node->pb_type->num_modes
597  == 0) {
598  source_pb_graph_node = expansion_edge->input_pins[i]->parent_node;
599  assert(found == FALSE);
600  /* Check assumption that each forced net has only one fan-out */
601  /* This is the source node for destination */
602  found = TRUE;
603 
604  /* If this pb_graph_node is part not of the current pattern index, put it in and expand all its edges */
605  source_block =
606  (t_pack_pattern_block*) source_pb_graph_node->temp_scratch_pad;
607  if (source_block == NULL
608  || source_block->pattern_index != curr_pattern_index) {
609  source_block = (t_pack_pattern_block *)my_calloc(1, sizeof(t_pack_pattern_block));
610  source_block->block_id = *L_num_blocks;
611  (*L_num_blocks)++;
612  list_of_packing_patterns[curr_pattern_index].base_cost +=
613  compute_primitive_base_cost(source_pb_graph_node);
614  source_pb_graph_node->temp_scratch_pad = (void *) source_block;
615  source_block->pattern_index = curr_pattern_index;
616  source_block->pb_type = source_pb_graph_node->pb_type;
617 
618  if (list_of_packing_patterns[curr_pattern_index].root_block
619  == NULL) {
620  list_of_packing_patterns[curr_pattern_index].root_block =
621  source_block;
622  }
623 
624  for (iport = 0; iport < source_pb_graph_node->num_input_ports;
625  iport++) {
626  for (ipin = 0;
627  ipin < source_pb_graph_node->num_input_pins[iport];
628  ipin++) {
629  for (iedge = 0;
630  iedge
631  < source_pb_graph_node->input_pins[iport][ipin].num_input_edges;
632  iedge++) {
634  source_pb_graph_node->input_pins[iport][ipin].input_edges[iedge],
635  list_of_packing_patterns,
636  curr_pattern_index,
637  &source_pb_graph_node->input_pins[iport][ipin],
638  source_block, L_num_blocks);
639  }
640  }
641  }
642  for (iport = 0; iport < source_pb_graph_node->num_output_ports;
643  iport++) {
644  for (ipin = 0;
645  ipin < source_pb_graph_node->num_output_pins[iport];
646  ipin++) {
647  for (iedge = 0;
648  iedge
649  < source_pb_graph_node->output_pins[iport][ipin].num_output_edges;
650  iedge++) {
652  source_pb_graph_node->output_pins[iport][ipin].output_edges[iedge],
653  list_of_packing_patterns,
654  curr_pattern_index, L_num_blocks, FALSE);
655  }
656  }
657  }
658  for (iport = 0; iport < source_pb_graph_node->num_clock_ports;
659  iport++) {
660  for (ipin = 0;
661  ipin < source_pb_graph_node->num_clock_pins[iport];
662  ipin++) {
663  for (iedge = 0;
664  iedge
665  < source_pb_graph_node->clock_pins[iport][ipin].num_input_edges;
666  iedge++) {
668  source_pb_graph_node->clock_pins[iport][ipin].input_edges[iedge],
669  list_of_packing_patterns,
670  curr_pattern_index,
671  &source_pb_graph_node->clock_pins[iport][ipin],
672  source_block, L_num_blocks);
673  }
674  }
675  }
676  }
677  if (destination_pin != NULL) {
678  assert(
679  ((t_pack_pattern_block*)source_pb_graph_node->temp_scratch_pad)->pattern_index == curr_pattern_index);
680  source_block =
681  (t_pack_pattern_block*) source_pb_graph_node->temp_scratch_pad;
682  pack_pattern_connection = (t_pack_pattern_connections *)my_calloc(1,
684  pack_pattern_connection->from_block = source_block;
685  pack_pattern_connection->from_pin =
686  expansion_edge->input_pins[i];
687  pack_pattern_connection->to_block = destination_block;
688  pack_pattern_connection->to_pin = destination_pin;
689  pack_pattern_connection->next = source_block->connections;
690  source_block->connections = pack_pattern_connection;
691 
692  pack_pattern_connection = (t_pack_pattern_connections *)my_calloc(1,
694  pack_pattern_connection->from_block = source_block;
695  pack_pattern_connection->from_pin =
696  expansion_edge->input_pins[i];
697  pack_pattern_connection->to_block = destination_block;
698  pack_pattern_connection->to_pin = destination_pin;
699  pack_pattern_connection->next = destination_block->connections;
700  destination_block->connections = pack_pattern_connection;
701 
702  if (source_block == destination_block) {
703  vpr_printf(TIO_MESSAGE_ERROR, "Invalid packing pattern defined. Source and destination block are the same (%s).\n",
704  source_block->pb_type->name);
705  }
706  }
707  } else {
708  if(expansion_edge->input_pins[i]->num_input_edges == 0) {
709  if(expansion_edge->input_pins[i]->parent_node->pb_type->parent_mode == NULL) {
710  /* This pack pattern extends to CLB input pin, thus it extends across multiple logic blocks, treat as a chain */
711  list_of_packing_patterns[curr_pattern_index].is_chain = TRUE;
713  expansion_edge,
714  list_of_packing_patterns,
715  curr_pattern_index, L_num_blocks, TRUE);
716  }
717  } else {
718  for (j = 0; j < expansion_edge->input_pins[i]->num_input_edges;
719  j++) {
720  if (expansion_edge->input_pins[i]->input_edges[j]->infer_pattern
721  == TRUE) {
723  expansion_edge->input_pins[i]->input_edges[j],
724  list_of_packing_patterns, curr_pattern_index,
725  destination_pin, destination_block, L_num_blocks);
726  } else {
727  for (k = 0;
728  k
729  < expansion_edge->input_pins[i]->input_edges[j]->num_pack_patterns;
730  k++) {
731  if (expansion_edge->input_pins[i]->input_edges[j]->pack_pattern_indices[k]
732  == curr_pattern_index) {
733  assert(found == FALSE);
734  /* Check assumption that each forced net has only one fan-out */
735  found = TRUE;
737  expansion_edge->input_pins[i]->input_edges[j],
738  list_of_packing_patterns,
739  curr_pattern_index, destination_pin,
740  destination_block, L_num_blocks);
741  }
742  }
743  }
744  }
745  }
746  }
747  }
748 }
t_pb_graph_pin ** clock_pins
const t_pb_type * pb_type
Definition: cad_types.h:14
t_pack_pattern_block * from_block
Definition: cad_types.h:21
struct s_pb_graph_edge ** output_edges
void * my_calloc(size_t nelem, size_t size)
Definition: util.c:132
t_pb_graph_pin ** output_pins
t_pack_pattern_block * to_block
Definition: cad_types.h:24
t_pb_graph_pin * to_pin
Definition: cad_types.h:25
Definition: util.h:12
struct s_pb_graph_edge ** input_edges
float compute_primitive_base_cost(INP t_pb_graph_node *primitive)
Definition: vpr_utils.c:452
t_pb_graph_pin * from_pin
Definition: cad_types.h:22
struct s_pb_graph_node * parent_node
struct s_pack_pattern_connections * next
Definition: cad_types.h:27
struct s_pack_pattern_connections * connections
Definition: cad_types.h:15
static void forward_expand_pack_pattern_from_edge(INP t_pb_graph_edge *expansion_edge, INOUTP t_pack_patterns *list_of_packing_patterns, INP int curr_pattern_index, INP int *L_num_blocks, INP boolean make_root_of_chain)
struct s_pb_type * pb_type
messagelogger vpr_printf
Definition: util.c:17
static void backward_expand_pack_pattern_from_edge(INP t_pb_graph_edge *expansion_edge, INOUTP t_pack_patterns *list_of_packing_patterns, INP int curr_pattern_index, INP t_pb_graph_pin *destination_pin, INP t_pack_pattern_block *destination_block, INP int *L_num_blocks)
Definition: prepack.c:572
t_pb_graph_pin ** input_pins
Definition: util.h:12

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static void backward_infer_pattern ( INOUTP t_pb_graph_pin pb_graph_pin)
static

Definition at line 285 of file prepack.c.

285  {
286  if (pb_graph_pin->num_input_edges == 1 && pb_graph_pin->input_edges[0]->num_pack_patterns == 0 && pb_graph_pin->input_edges[0]->infer_pattern == FALSE) {
287  pb_graph_pin->input_edges[0]->infer_pattern = TRUE;
288  if (pb_graph_pin->input_edges[0]->num_input_pins == 1) {
289  backward_infer_pattern(pb_graph_pin->input_edges[0]->input_pins[0]);
290  }
291  }
292 }
Definition: util.h:12
static void backward_infer_pattern(INOUTP t_pb_graph_pin *pb_graph_pin)
Definition: prepack.c:285
Definition: util.h:12

+ Here is the caller graph for this function:

static int compare_pack_pattern ( const t_pack_patterns pattern_a,
const t_pack_patterns pattern_b 
)
static

Definition at line 1124 of file prepack.c.

1124  {
1125  float base_gain_a, base_gain_b, diff;
1126 
1127  /* Bigger patterns should take higher priority than smaller patterns because they are harder to fit */
1128  if (pattern_a->num_blocks > pattern_b->num_blocks) {
1129  return 1;
1130  } else if (pattern_a->num_blocks < pattern_b->num_blocks) {
1131  return -1;
1132  }
1133 
1134  base_gain_a = pattern_a->base_cost;
1135  base_gain_b = pattern_b->base_cost;
1136  diff = base_gain_a - base_gain_b;
1137 
1138  /* Less costly patterns should be used before more costly patterns */
1139  if (diff < 0) {
1140  return 1;
1141  }
1142  if (diff > 0) {
1143  return -1;
1144  }
1145  return 0;
1146 }
float base_cost
Definition: cad_types.h:34

+ Here is the caller graph for this function:

static void discover_pattern_names_in_pb_graph_node ( INOUTP t_pb_graph_node pb_graph_node,
INOUTP struct s_hash **  nhash,
INOUTP int *  ncount 
)
static

Locate all pattern names Side-effect: set all pb_graph_node temp_scratch_pad field to NULL For cases where a pattern inference is "obvious", mark it as obvious.

Definition at line 147 of file prepack.c.

149  {
150  int i, j, k, m;
151  int index;
152  boolean hasPattern;
153  /* Iterate over all edges to discover if an edge in current physical block belongs to a pattern
154  If edge does, then record the name of the pattern in a hash table
155  */
156 
157  if (pb_graph_node == NULL) {
158  return;
159  }
160 
161  pb_graph_node->temp_scratch_pad = NULL;
162 
163  for (i = 0; i < pb_graph_node->num_input_ports; i++) {
164  for (j = 0; j < pb_graph_node->num_input_pins[i]; j++) {
165  hasPattern = FALSE;
166  for (k = 0; k < pb_graph_node->input_pins[i][j].num_output_edges;
167  k++) {
168  for (m = 0;
169  m
170  < pb_graph_node->input_pins[i][j].output_edges[k]->num_pack_patterns;
171  m++) {
172  hasPattern = TRUE;
173  index =
175  pb_graph_node->input_pins[i][j].output_edges[k]->pack_pattern_names[m],
176  ncount);
177  if (pb_graph_node->input_pins[i][j].output_edges[k]->pack_pattern_indices
178  == NULL) {
179  pb_graph_node->input_pins[i][j].output_edges[k]->pack_pattern_indices = (int*)
180  my_malloc(
181  pb_graph_node->input_pins[i][j].output_edges[k]->num_pack_patterns
182  * sizeof(int));
183  }
184  pb_graph_node->input_pins[i][j].output_edges[k]->pack_pattern_indices[m] =
185  index;
186  }
187  }
188  if (hasPattern == TRUE) {
189  forward_infer_pattern(&pb_graph_node->input_pins[i][j]);
190  backward_infer_pattern(&pb_graph_node->input_pins[i][j]);
191  }
192  }
193  }
194 
195  for (i = 0; i < pb_graph_node->num_output_ports; i++) {
196  for (j = 0; j < pb_graph_node->num_output_pins[i]; j++) {
197  hasPattern = FALSE;
198  for (k = 0; k < pb_graph_node->output_pins[i][j].num_output_edges;
199  k++) {
200  for (m = 0;
201  m
202  < pb_graph_node->output_pins[i][j].output_edges[k]->num_pack_patterns;
203  m++) {
204  hasPattern = TRUE;
205  index =
207  pb_graph_node->output_pins[i][j].output_edges[k]->pack_pattern_names[m],
208  ncount);
209  if (pb_graph_node->output_pins[i][j].output_edges[k]->pack_pattern_indices
210  == NULL) {
211  pb_graph_node->output_pins[i][j].output_edges[k]->pack_pattern_indices = (int*)
212  my_malloc(
213  pb_graph_node->output_pins[i][j].output_edges[k]->num_pack_patterns
214  * sizeof(int));
215  }
216  pb_graph_node->output_pins[i][j].output_edges[k]->pack_pattern_indices[m] =
217  index;
218  }
219  }
220  if (hasPattern == TRUE) {
221  forward_infer_pattern(&pb_graph_node->output_pins[i][j]);
222  backward_infer_pattern(&pb_graph_node->output_pins[i][j]);
223  }
224  }
225  }
226 
227  for (i = 0; i < pb_graph_node->num_clock_ports; i++) {
228  for (j = 0; j < pb_graph_node->num_clock_pins[i]; j++) {
229  hasPattern = FALSE;
230  for (k = 0; k < pb_graph_node->clock_pins[i][j].num_output_edges;
231  k++) {
232  for (m = 0;
233  m
234  < pb_graph_node->clock_pins[i][j].output_edges[k]->num_pack_patterns;
235  m++) {
236  hasPattern = TRUE;
237  index =
239  pb_graph_node->clock_pins[i][j].output_edges[k]->pack_pattern_names[m],
240  ncount);
241  if (pb_graph_node->clock_pins[i][j].output_edges[k]->pack_pattern_indices
242  == NULL) {
243  pb_graph_node->clock_pins[i][j].output_edges[k]->pack_pattern_indices = (int*)
244  my_malloc(
245  pb_graph_node->clock_pins[i][j].output_edges[k]->num_pack_patterns
246  * sizeof(int));
247  }
248  pb_graph_node->clock_pins[i][j].output_edges[k]->pack_pattern_indices[m] =
249  index;
250  }
251  }
252  if (hasPattern == TRUE) {
253  forward_infer_pattern(&pb_graph_node->clock_pins[i][j]);
254  backward_infer_pattern(&pb_graph_node->clock_pins[i][j]);
255  }
256  }
257  }
258 
259  for (i = 0; i < pb_graph_node->pb_type->num_modes; i++) {
260  for (j = 0; j < pb_graph_node->pb_type->modes[i].num_pb_type_children;
261  j++) {
262  for (k = 0;
263  k
264  < pb_graph_node->pb_type->modes[i].pb_type_children[j].num_pb;
265  k++) {
267  &pb_graph_node->child_pb_graph_nodes[i][j][k], nhash,
268  ncount);
269  }
270  }
271  }
272 }
int index
Definition: hash.h:5
static int add_pattern_name_to_hash(INOUTP struct s_hash **nhash, INP char *pattern_name, INOUTP int *ncount)
Definition: prepack.c:130
Definition: util.h:12
static void * my_malloc(int ibytes)
Definition: graphics.c:499
static void discover_pattern_names_in_pb_graph_node(INOUTP t_pb_graph_node *pb_graph_node, INOUTP struct s_hash **nhash, INOUTP int *ncount)
Definition: prepack.c:147
static void forward_infer_pattern(INOUTP t_pb_graph_pin *pb_graph_pin)
Definition: prepack.c:277
static void backward_infer_pattern(INOUTP t_pb_graph_pin *pb_graph_pin)
Definition: prepack.c:285
Definition: util.h:12

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static t_pb_graph_edge * find_expansion_edge_of_pattern ( INP int  pattern_index,
INP t_pb_graph_node pb_graph_node 
)
static

Locate first edge that belongs to pattern index

Definition at line 341 of file prepack.c.

342  {
343  int i, j, k, m;
344  t_pb_graph_edge * edge;
345  /* Iterate over all edges to discover if an edge in current physical block belongs to a pattern
346  If edge does, then return that edge
347  */
348 
349  if (pb_graph_node == NULL) {
350  return NULL;
351  }
352 
353  for (i = 0; i < pb_graph_node->num_input_ports; i++) {
354  for (j = 0; j < pb_graph_node->num_input_pins[i]; j++) {
355  for (k = 0; k < pb_graph_node->input_pins[i][j].num_output_edges;
356  k++) {
357  for (m = 0;
358  m
359  < pb_graph_node->input_pins[i][j].output_edges[k]->num_pack_patterns;
360  m++) {
361  if (pb_graph_node->input_pins[i][j].output_edges[k]->pack_pattern_indices[m]
362  == pattern_index) {
363  return pb_graph_node->input_pins[i][j].output_edges[k];
364  }
365  }
366  }
367  }
368  }
369 
370  for (i = 0; i < pb_graph_node->num_output_ports; i++) {
371  for (j = 0; j < pb_graph_node->num_output_pins[i]; j++) {
372  for (k = 0; k < pb_graph_node->output_pins[i][j].num_output_edges;
373  k++) {
374  for (m = 0;
375  m
376  < pb_graph_node->output_pins[i][j].output_edges[k]->num_pack_patterns;
377  m++) {
378  if (pb_graph_node->output_pins[i][j].output_edges[k]->pack_pattern_indices[m]
379  == pattern_index) {
380  return pb_graph_node->output_pins[i][j].output_edges[k];
381  }
382  }
383  }
384  }
385  }
386 
387  for (i = 0; i < pb_graph_node->num_clock_ports; i++) {
388  for (j = 0; j < pb_graph_node->num_clock_pins[i]; j++) {
389  for (k = 0; k < pb_graph_node->clock_pins[i][j].num_output_edges;
390  k++) {
391  for (m = 0;
392  m
393  < pb_graph_node->clock_pins[i][j].output_edges[k]->num_pack_patterns;
394  m++) {
395  if (pb_graph_node->clock_pins[i][j].output_edges[k]->pack_pattern_indices[m]
396  == pattern_index) {
397  return pb_graph_node->clock_pins[i][j].output_edges[k];
398  }
399  }
400  }
401  }
402  }
403 
404  for (i = 0; i < pb_graph_node->pb_type->num_modes; i++) {
405  for (j = 0; j < pb_graph_node->pb_type->modes[i].num_pb_type_children;
406  j++) {
407  for (k = 0;
408  k
409  < pb_graph_node->pb_type->modes[i].pb_type_children[j].num_pb;
410  k++) {
411  edge = find_expansion_edge_of_pattern(pattern_index,
412  &pb_graph_node->child_pb_graph_nodes[i][j][k]);
413  if (edge != NULL) {
414  return edge;
415  }
416  }
417  }
418  }
419  return NULL;
420 }
t_pb_graph_pin ** output_pins
struct s_pb_graph_edge ** output_edges
t_pb_graph_pin ** input_pins
static t_pb_graph_edge * find_expansion_edge_of_pattern(INP int pattern_index, INP t_pb_graph_node *pb_graph_node)
Definition: prepack.c:341

+ Here is the caller graph for this function:

static int find_new_root_atom_for_chain ( INP int  block_index,
INP t_pack_patterns list_of_pack_pattern 
)
static

Definition at line 1155 of file prepack.c.

1155  {
1156  int new_index = OPEN;
1157  t_pb_graph_pin *root_ipin;
1158  t_pb_graph_node *root_pb_graph_node;
1159  t_model_ports *model_port;
1160  int driver_net, driver_block;
1161 
1162  assert(list_of_pack_pattern->is_chain == TRUE);
1163  root_ipin = list_of_pack_pattern->chain_root_pin;
1164  root_pb_graph_node = root_ipin->parent_node;
1165 
1166  if(primitive_type_feasible(block_index, root_pb_graph_node->pb_type) == FALSE) {
1167  return OPEN;
1168  }
1169 
1170  /* Assign driver furthest up the chain that matches the root node and is unassigned to a molecule as the root */
1171  model_port = root_ipin->port->model_port;
1172  driver_net = logical_block[block_index].input_nets[model_port->index][root_ipin->pin_number];
1173  if(driver_net == OPEN) {
1174  /* The current block is the furthest up the chain, return it */
1175  return block_index;
1176  }
1177 
1178  driver_block = vpack_net[driver_net].node_block[0];
1179  if(logical_block[driver_block].packed_molecules != NULL) {
1180  /* Driver is used/invalid, so current block is the furthest up the chain, return it */
1181  return block_index;
1182  }
1183 
1184  new_index = find_new_root_atom_for_chain(driver_block, list_of_pack_pattern);
1185  if(new_index == OPEN) {
1186  return block_index;
1187  } else {
1188  return new_index;
1189  }
1190 }
boolean primitive_type_feasible(int iblk, const t_pb_type *cur_pb_type)
Definition: vpr_utils.c:241
t_model_ports * model_port
int ** input_nets
Definition: vpr_types.h:211
int * node_block
Definition: vpr_types.h:507
static int find_new_root_atom_for_chain(INP int block_index, INP t_pack_patterns *list_of_pack_pattern)
Definition: prepack.c:1155
Definition: util.h:12
struct s_pb_graph_node * parent_node
struct s_pb_type * pb_type
Definition: slre.c:50
struct s_net * vpack_net
Definition: globals.c:19
struct s_logical_block * logical_block
Definition: globals.c:20
Definition: util.h:12

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static void forward_expand_pack_pattern_from_edge ( INP t_pb_graph_edge expansion_edge,
INOUTP t_pack_patterns list_of_packing_patterns,
INP int  curr_pattern_index,
INP int *  L_num_blocks,
INP boolean  make_root_of_chain 
)
static

+ Here is the caller graph for this function:

static void forward_expand_pack_pattern_from_edge ( INP t_pb_graph_edge expansion_edge,
INOUTP t_pack_patterns list_of_packing_patterns,
INP int  curr_pattern_index,
INP int *  L_num_blocks,
INOUTP boolean  make_root_of_chain 
)
static

Find if receiver of edge is in the same pattern, if yes, add to pattern Convention: Connections are made on backward expansion only (to make future multi-fanout support easier) so this function will not update connections

Definition at line 426 of file prepack.c.

429  {
430  int i, j, k;
431  int iport, ipin, iedge;
432  boolean found; /* Error checking, ensure only one fan-out for each pattern net */
433  t_pack_pattern_block *destination_block = NULL;
434  t_pb_graph_node *destination_pb_graph_node = NULL;
435 
436  found = expansion_edge->infer_pattern;
437  for (i = 0; !found && i < expansion_edge->num_pack_patterns; i++) {
438  if (expansion_edge->pack_pattern_indices[i] == curr_pattern_index) {
439  found = TRUE;
440  }
441  }
442  if (!found) {
443  return;
444  }
445 
446  found = FALSE;
447  for (i = 0; i < expansion_edge->num_output_pins; i++) {
448  if (expansion_edge->output_pins[i]->parent_node->pb_type->num_modes
449  == 0) {
450  destination_pb_graph_node =
451  expansion_edge->output_pins[i]->parent_node;
452  assert(found == FALSE);
453  /* Check assumption that each forced net has only one fan-out */
454  /* This is the destination node */
455  found = TRUE;
456 
457  /* If this pb_graph_node is part not of the current pattern index, put it in and expand all its edges */
458  if (destination_pb_graph_node->temp_scratch_pad == NULL
459  || ((t_pack_pattern_block*) destination_pb_graph_node->temp_scratch_pad)->pattern_index
460  != curr_pattern_index) {
461  destination_block = (t_pack_pattern_block*)my_calloc(1, sizeof(t_pack_pattern_block));
462  list_of_packing_patterns[curr_pattern_index].base_cost +=
463  compute_primitive_base_cost(destination_pb_graph_node);
464  destination_block->block_id = *L_num_blocks;
465  (*L_num_blocks)++;
466  destination_pb_graph_node->temp_scratch_pad =
467  (void *) destination_block;
468  destination_block->pattern_index = curr_pattern_index;
469  destination_block->pb_type = destination_pb_graph_node->pb_type;
470  for (iport = 0;
471  iport < destination_pb_graph_node->num_input_ports;
472  iport++) {
473  for (ipin = 0;
474  ipin
475  < destination_pb_graph_node->num_input_pins[iport];
476  ipin++) {
477  for (iedge = 0;
478  iedge
479  < destination_pb_graph_node->input_pins[iport][ipin].num_input_edges;
480  iedge++) {
482  destination_pb_graph_node->input_pins[iport][ipin].input_edges[iedge],
483  list_of_packing_patterns,
484  curr_pattern_index,
485  &destination_pb_graph_node->input_pins[iport][ipin],
486  destination_block, L_num_blocks);
487  }
488  }
489  }
490  for (iport = 0;
491  iport < destination_pb_graph_node->num_output_ports;
492  iport++) {
493  for (ipin = 0;
494  ipin
495  < destination_pb_graph_node->num_output_pins[iport];
496  ipin++) {
497  for (iedge = 0;
498  iedge
499  < destination_pb_graph_node->output_pins[iport][ipin].num_output_edges;
500  iedge++) {
502  destination_pb_graph_node->output_pins[iport][ipin].output_edges[iedge],
503  list_of_packing_patterns,
504  curr_pattern_index, L_num_blocks, FALSE);
505  }
506  }
507  }
508  for (iport = 0;
509  iport < destination_pb_graph_node->num_clock_ports;
510  iport++) {
511  for (ipin = 0;
512  ipin
513  < destination_pb_graph_node->num_clock_pins[iport];
514  ipin++) {
515  for (iedge = 0;
516  iedge
517  < destination_pb_graph_node->clock_pins[iport][ipin].num_input_edges;
518  iedge++) {
520  destination_pb_graph_node->clock_pins[iport][ipin].input_edges[iedge],
521  list_of_packing_patterns,
522  curr_pattern_index,
523  &destination_pb_graph_node->clock_pins[iport][ipin],
524  destination_block, L_num_blocks);
525  }
526  }
527  }
528  }
529  if (((t_pack_pattern_block*) destination_pb_graph_node->temp_scratch_pad)->pattern_index
530  == curr_pattern_index) {
531  if(make_root_of_chain == TRUE) {
532  list_of_packing_patterns[curr_pattern_index].chain_root_pin = expansion_edge->output_pins[i];
533  list_of_packing_patterns[curr_pattern_index].root_block = destination_block;
534  }
535  }
536  } else {
537  for (j = 0; j < expansion_edge->output_pins[i]->num_output_edges;
538  j++) {
539  if (expansion_edge->output_pins[i]->output_edges[j]->infer_pattern
540  == TRUE) {
542  expansion_edge->output_pins[i]->output_edges[j],
543  list_of_packing_patterns, curr_pattern_index,
544  L_num_blocks, make_root_of_chain);
545  } else {
546  for (k = 0;
547  k
548  < expansion_edge->output_pins[i]->output_edges[j]->num_pack_patterns;
549  k++) {
550  if (expansion_edge->output_pins[i]->output_edges[j]->pack_pattern_indices[k]
551  == curr_pattern_index) {
552  assert(found == FALSE);
553  /* Check assumption that each forced net has only one fan-out */
554  found = TRUE;
556  expansion_edge->output_pins[i]->output_edges[j],
557  list_of_packing_patterns,
558  curr_pattern_index, L_num_blocks, make_root_of_chain);
559  }
560  }
561  }
562  }
563  }
564  }
565 
566 }
t_pb_graph_pin ** clock_pins
const t_pb_type * pb_type
Definition: cad_types.h:14
struct s_pb_graph_edge ** output_edges
void * my_calloc(size_t nelem, size_t size)
Definition: util.c:132
t_pb_graph_pin ** output_pins
Definition: util.h:12
struct s_pb_graph_edge ** input_edges
float compute_primitive_base_cost(INP t_pb_graph_node *primitive)
Definition: vpr_utils.c:452
struct s_pb_graph_node * parent_node
static void forward_expand_pack_pattern_from_edge(INP t_pb_graph_edge *expansion_edge, INOUTP t_pack_patterns *list_of_packing_patterns, INP int curr_pattern_index, INP int *L_num_blocks, INP boolean make_root_of_chain)
struct s_pb_type * pb_type
static void backward_expand_pack_pattern_from_edge(INP t_pb_graph_edge *expansion_edge, INOUTP t_pack_patterns *list_of_packing_patterns, INP int curr_pattern_index, INP t_pb_graph_pin *destination_pin, INP t_pack_pattern_block *destination_block, INP int *L_num_blocks)
Definition: prepack.c:572
t_pb_graph_pin ** input_pins
Definition: util.h:12

+ Here is the call graph for this function:

static void forward_infer_pattern ( INOUTP t_pb_graph_pin pb_graph_pin)
static

In obvious cases where a pattern edge has only one path to go, set that path to be inferred

Definition at line 277 of file prepack.c.

277  {
278  if (pb_graph_pin->num_output_edges == 1 && pb_graph_pin->output_edges[0]->num_pack_patterns == 0 && pb_graph_pin->output_edges[0]->infer_pattern == FALSE) {
279  pb_graph_pin->output_edges[0]->infer_pattern = TRUE;
280  if (pb_graph_pin->output_edges[0]->num_output_pins == 1) {
281  forward_infer_pattern(pb_graph_pin->output_edges[0]->output_pins[0]);
282  }
283  }
284 }
Definition: util.h:12
static void forward_infer_pattern(INOUTP t_pb_graph_pin *pb_graph_pin)
Definition: prepack.c:277
Definition: util.h:12

+ Here is the caller graph for this function:

void free_list_of_pack_patterns ( INP t_pack_patterns list_of_pack_patterns,
INP int  num_packing_patterns 
)

Definition at line 319 of file prepack.c.

319  {
320  int i, j, num_pack_pattern_blocks;
321  t_pack_pattern_block **pattern_block_list;
322  if (list_of_pack_patterns != NULL) {
323  for (i = 0; i < num_packing_patterns; i++) {
324  num_pack_pattern_blocks = list_of_pack_patterns[i].num_blocks;
325  pattern_block_list = (t_pack_pattern_block **)my_calloc(num_pack_pattern_blocks, sizeof(t_pack_pattern_block *));
326  free(list_of_pack_patterns[i].name);
327  free(list_of_pack_patterns[i].is_block_optional);
328  free_pack_pattern(list_of_pack_patterns[i].root_block, pattern_block_list);
329  for (j = 0; j < num_pack_pattern_blocks; j++) {
330  free(pattern_block_list[j]);
331  }
332  free(pattern_block_list);
333  }
334  free(list_of_pack_patterns);
335  }
336 }
void * my_calloc(size_t nelem, size_t size)
Definition: util.c:132
char * name
Definition: hash.h:4
static void free_pack_pattern(INOUTP t_pack_pattern_block *pattern_block, INOUTP t_pack_pattern_block **pattern_block_list)
Definition: prepack.c:841

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static void free_pack_pattern ( INOUTP t_pack_pattern_block pattern_block,
INOUTP t_pack_pattern_block **  pattern_block_list 
)
static

Definition at line 841 of file prepack.c.

841  {
842  t_pack_pattern_connections *connection, *next;
843  if (pattern_block->block_id == OPEN) {
844  /* already traversed, return */
845  return;
846  }
847  pattern_block_list[pattern_block->block_id] = pattern_block;
848  pattern_block->block_id = OPEN;
849  connection = pattern_block->connections;
850  while (connection) {
851  free_pack_pattern(connection->from_block, pattern_block_list);
852  free_pack_pattern(connection->to_block, pattern_block_list);
853  next = connection->next;
854  free(connection);
855  connection = next;
856  }
857 }
t_pack_pattern_block * from_block
Definition: cad_types.h:21
t_pack_pattern_block * to_block
Definition: cad_types.h:24
struct s_pack_pattern_connections * next
Definition: cad_types.h:27
struct s_hash * next
Definition: hash.h:7
Definition: slre.c:50
static void free_pack_pattern(INOUTP t_pack_pattern_block *pattern_block, INOUTP t_pack_pattern_block **pattern_block_list)
Definition: prepack.c:841

+ Here is the caller graph for this function:

static t_pb_graph_node * get_expected_lowest_cost_primitive_for_logical_block ( INP int  ilogical_block)
static

Definition at line 1063 of file prepack.c.

1063  {
1064  int i;
1065  float cost, best_cost;
1066  t_pb_graph_node *current, *best;
1067 
1068  best_cost = UNDEFINED;
1069  best = NULL;
1070  current = NULL;
1071  for(i = 0; i < num_types; i++) {
1072  cost = UNDEFINED;
1073  current = get_expected_lowest_cost_primitive_for_logical_block_in_pb_graph_node(ilogical_block, type_descriptors[i].pb_graph_head, &cost);
1074  if(cost != UNDEFINED) {
1075  if(best_cost == UNDEFINED || best_cost > cost) {
1076  best_cost = cost;
1077  best = current;
1078  }
1079  }
1080  }
1081  return best;
1082 }
#define UNDEFINED
Definition: vpr_types.h:103
static t_pb_graph_node * get_expected_lowest_cost_primitive_for_logical_block_in_pb_graph_node(INP int ilogical_block, INP t_pb_graph_node *curr_pb_graph_node, OUTP float *cost)
Definition: prepack.c:1084
int num_types
Definition: globals.c:37
struct s_type_descriptor * type_descriptors
Definition: globals.c:38

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static t_pb_graph_node * get_expected_lowest_cost_primitive_for_logical_block_in_pb_graph_node ( INP int  ilogical_block,
INP t_pb_graph_node curr_pb_graph_node,
OUTP float *  cost 
)
static

Definition at line 1084 of file prepack.c.

1084  {
1085  t_pb_graph_node *best, *cur;
1086  float cur_cost, best_cost;
1087  int i, j;
1088 
1089  best = NULL;
1090  best_cost = UNDEFINED;
1091  if(curr_pb_graph_node == NULL) {
1092  return NULL;
1093  }
1094 
1095  if(curr_pb_graph_node->pb_type->blif_model != NULL) {
1096  if(primitive_type_feasible(ilogical_block, curr_pb_graph_node->pb_type)) {
1097  cur_cost = compute_primitive_base_cost(curr_pb_graph_node);
1098  if(best_cost == UNDEFINED || best_cost > cur_cost) {
1099  best_cost = cur_cost;
1100  best = curr_pb_graph_node;
1101  }
1102  }
1103  } else {
1104  for(i = 0; i < curr_pb_graph_node->pb_type->num_modes; i++) {
1105  for(j = 0; j < curr_pb_graph_node->pb_type->modes[i].num_pb_type_children; j++) {
1106  *cost = UNDEFINED;
1107  cur = get_expected_lowest_cost_primitive_for_logical_block_in_pb_graph_node(ilogical_block, &curr_pb_graph_node->child_pb_graph_nodes[i][j][0], cost);
1108  if(cur != NULL) {
1109  if(best == NULL || best_cost > *cost) {
1110  best = cur;
1111  best_cost = *cost;
1112  }
1113  }
1114  }
1115  }
1116  }
1117 
1118  *cost = best_cost;
1119  return best;
1120 }
boolean primitive_type_feasible(int iblk, const t_pb_type *cur_pb_type)
Definition: vpr_utils.c:241
#define UNDEFINED
Definition: vpr_types.h:103
static t_pb_graph_node * get_expected_lowest_cost_primitive_for_logical_block_in_pb_graph_node(INP int ilogical_block, INP t_pb_graph_node *curr_pb_graph_node, OUTP float *cost)
Definition: prepack.c:1084
float compute_primitive_base_cost(INP t_pb_graph_node *primitive)
Definition: vpr_utils.c:452

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static void print_pack_molecules ( INP const char *  fname,
INP t_pack_patterns list_of_pack_patterns,
INP int  num_pack_patterns,
INP t_pack_molecule list_of_molecules 
)
static

Definition at line 1009 of file prepack.c.

1011  {
1012  int i;
1013  FILE *fp;
1014  t_pack_molecule *list_of_molecules_current;
1015 
1016  fp = my_fopen(fname, "w", 0);
1017  fprintf(fp, "# of pack patterns %d\n", num_pack_patterns);
1018 
1019  for (i = 0; i < num_pack_patterns; i++) {
1020  fprintf(fp, "pack pattern index %d block count %d name %s root %s\n",
1021  list_of_pack_patterns[i].index,
1022  list_of_pack_patterns[i].num_blocks,
1023  list_of_pack_patterns[i].name,
1024  list_of_pack_patterns[i].root_block->pb_type->name);
1025  }
1026 
1027  list_of_molecules_current = list_of_molecules;
1028  while (list_of_molecules_current != NULL) {
1029  if (list_of_molecules_current->type == MOLECULE_SINGLE_ATOM) {
1030  fprintf(fp, "\nmolecule type: atom\n");
1031  fprintf(fp, "\tpattern index %d: logical block [%d] name %s\n", i,
1032  list_of_molecules_current->logical_block_ptrs[0]->index,
1033  list_of_molecules_current->logical_block_ptrs[0]->name);
1034  } else if (list_of_molecules_current->type == MOLECULE_FORCED_PACK) {
1035  fprintf(fp, "\nmolecule type: %s\n",
1036  list_of_molecules_current->pack_pattern->name);
1037  for (i = 0; i < list_of_molecules_current->pack_pattern->num_blocks;
1038  i++) {
1039  if(list_of_molecules_current->logical_block_ptrs[i] == NULL) {
1040  fprintf(fp, "\tpattern index %d: empty \n", i);
1041  } else {
1042  fprintf(fp, "\tpattern index %d: logical block [%d] name %s",
1043  i,
1044  list_of_molecules_current->logical_block_ptrs[i]->index,
1045  list_of_molecules_current->logical_block_ptrs[i]->name);
1046  if(list_of_molecules_current->pack_pattern->root_block->block_id == i) {
1047  fprintf(fp, " root node\n");
1048  } else {
1049  fprintf(fp, "\n");
1050  }
1051  }
1052  }
1053  } else {
1054  assert(0);
1055  }
1056  list_of_molecules_current = list_of_molecules_current->next;
1057  }
1058 
1059  fclose(fp);
1060 }
FILE * my_fopen(const char *fname, const char *flag, int prompt)
Definition: util.c:54
int index
Definition: hash.h:5
char * name
Definition: hash.h:4
int num_blocks
Definition: globals.c:30
t_pack_patterns * pack_pattern
Definition: vpr_types.h:246
struct s_pack_molecule * next
Definition: vpr_types.h:257
enum e_pack_pattern_molecule_type type
Definition: vpr_types.h:245
t_logical_block ** logical_block_ptrs
Definition: vpr_types.h:248
t_pack_pattern_block * root_block
Definition: cad_types.h:33

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static t_pack_molecule * try_create_molecule ( INP t_pack_patterns list_of_pack_patterns,
INP int  pack_pattern_index,
INP int  block_index 
)
static

Given a pattern and a logical block to serve as the root block, determine if the candidate logical block serving as the root node matches the pattern If yes, return the molecule with this logical block as the root, if not, return NULL Limitations: Currently assumes that forced pack nets must be single-fanout as this covers all the reasonable architectures we wanted More complicated structures should probably be handled either downstream (general packing) or upstream (in tech mapping) If this limitation is too constraining, code is designed so that this limitation can be removed Side Effect: If successful, link atom to molecule

Definition at line 867 of file prepack.c.

869  {
870  int i;
871  t_pack_molecule *molecule;
872  struct s_linked_vptr *molecule_linked_list;
873 
874  molecule = (t_pack_molecule*)my_calloc(1, sizeof(t_pack_molecule));
875  molecule->valid = TRUE;
876  molecule->type = MOLECULE_FORCED_PACK;
877  molecule->pack_pattern = &list_of_pack_patterns[pack_pattern_index];
879  sizeof(t_logical_block *));
880  molecule->num_blocks = list_of_pack_patterns[pack_pattern_index].num_blocks;
881  molecule->root =
882  list_of_pack_patterns[pack_pattern_index].root_block->block_id;
883  molecule->num_ext_inputs = 0;
884 
885  if(list_of_pack_patterns[pack_pattern_index].is_chain == TRUE) {
886  /* A chain pattern extends beyond a single logic block so we must find the block_index that matches with the portion of a chain for this particular logic block */
887  block_index = find_new_root_atom_for_chain(block_index, &list_of_pack_patterns[pack_pattern_index]);
888  }
889 
890  if (block_index != OPEN && try_expand_molecule(molecule, block_index,
891  molecule->pack_pattern->root_block) == TRUE) {
892  /* Success! commit module */
893  for (i = 0; i < molecule->pack_pattern->num_blocks; i++) {
894  if(molecule->logical_block_ptrs[i] == NULL) {
895  assert(list_of_pack_patterns[pack_pattern_index].is_block_optional[i] == TRUE);
896  continue;
897  }
898  molecule_linked_list = (struct s_linked_vptr*) my_calloc(1, sizeof(struct s_linked_vptr));
899  molecule_linked_list->data_vptr = (void *) molecule;
900  molecule_linked_list->next =
901  molecule->logical_block_ptrs[i]->packed_molecules;
902  molecule->logical_block_ptrs[i]->packed_molecules =
903  molecule_linked_list;
904  }
905  } else {
906  /* Does not match pattern, free molecule */
907  free(molecule->logical_block_ptrs);
908  free(molecule);
909  molecule = NULL;
910  }
911 
912  return molecule;
913 }
void * my_calloc(size_t nelem, size_t size)
Definition: util.c:132
struct s_linked_vptr * packed_molecules
Definition: vpr_types.h:228
static int find_new_root_atom_for_chain(INP int block_index, INP t_pack_patterns *list_of_pack_pattern)
Definition: prepack.c:1155
t_pack_patterns * pack_pattern
Definition: vpr_types.h:246
struct s_linked_vptr * next
Definition: util.h:36
void * data_vptr
Definition: util.h:35
Definition: slre.c:50
enum e_pack_pattern_molecule_type type
Definition: vpr_types.h:245
t_logical_block ** logical_block_ptrs
Definition: vpr_types.h:248
boolean valid
Definition: vpr_types.h:249
t_pack_pattern_block * root_block
Definition: cad_types.h:33
Definition: util.h:12
static boolean try_expand_molecule(INOUTP t_pack_molecule *molecule, INP int logical_block_index, INP t_pack_pattern_block *current_pattern_block)
Definition: prepack.c:919

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static boolean try_expand_molecule ( INOUTP t_pack_molecule molecule,
INP int  logical_block_index,
INP t_pack_pattern_block current_pattern_block 
)
static

Determine if logical block can match with the pattern to form a molecule return TRUE if it matches, return FALSE otherwise

Definition at line 919 of file prepack.c.

921  {
922  int iport, ipin, inet;
923  boolean success;
924  boolean is_optional;
925  boolean *is_block_optional;
926  t_pack_pattern_connections *cur_pack_pattern_connection;
927  is_block_optional = molecule->pack_pattern->is_block_optional;
928  is_optional = is_block_optional[current_pattern_block->block_id];
929 
930  /* If the block in the pattern has already been visited, then there is no need to revisit it */
931  if (molecule->logical_block_ptrs[current_pattern_block->block_id] != NULL) {
932  if (molecule->logical_block_ptrs[current_pattern_block->block_id]
933  != &logical_block[logical_block_index]) {
934  /* Mismatch between the visited block and the current block implies that the current netlist structure does not match the expected pattern, return whether or not this matters */
935  return is_optional;
936  } else {
937  molecule->num_ext_inputs--; /* This block is revisited, implies net is entirely internal to molecule, reduce count */
938  return TRUE;
939  }
940  }
941 
942  /* This node has never been visited */
943  /* Simplifying assumption: An atom can only map to one molecule */
944  if(logical_block[logical_block_index].packed_molecules != NULL) {
945  /* This block is already in a molecule, return whether or not this matters */
946  return is_optional;
947  }
948 
949  if (primitive_type_feasible(logical_block_index,
950  current_pattern_block->pb_type)) {
951 
952  success = TRUE;
953  /* If the primitive types match, store it, expand it and explore neighbouring nodes */
954  molecule->logical_block_ptrs[current_pattern_block->block_id] =
955  &logical_block[logical_block_index]; /* store that this node has been visited */
956  molecule->num_ext_inputs +=
957  logical_block[logical_block_index].used_input_pins;
958 
959  cur_pack_pattern_connection = current_pattern_block->connections;
960  while (cur_pack_pattern_connection != NULL && success == TRUE) {
961  if (cur_pack_pattern_connection->from_block
962  == current_pattern_block) {
963  /* find net corresponding to pattern */
964  iport =
965  cur_pack_pattern_connection->from_pin->port->model_port->index;
966  ipin = cur_pack_pattern_connection->from_pin->pin_number;
967  inet =
968  logical_block[logical_block_index].output_nets[iport][ipin];
969 
970  /* Check if net is valid */
971  if (inet == OPEN || vpack_net[inet].num_sinks != 1) { /* One fanout assumption */
972  success = is_block_optional[cur_pack_pattern_connection->to_block->block_id];
973  } else {
974  success = try_expand_molecule(molecule,
975  vpack_net[inet].node_block[1],
976  cur_pack_pattern_connection->to_block);
977  }
978  } else {
979  assert(
980  cur_pack_pattern_connection->to_block == current_pattern_block);
981  /* find net corresponding to pattern */
982  iport =
983  cur_pack_pattern_connection->to_pin->port->model_port->index;
984  ipin = cur_pack_pattern_connection->to_pin->pin_number;
985  if (cur_pack_pattern_connection->to_pin->port->model_port->is_clock) {
986  inet = logical_block[logical_block_index].clock_net;
987  } else {
988  inet =
989  logical_block[logical_block_index].input_nets[iport][ipin];
990  }
991  /* Check if net is valid */
992  if (inet == OPEN || vpack_net[inet].num_sinks != 1) { /* One fanout assumption */
993  success = is_block_optional[cur_pack_pattern_connection->from_block->block_id];
994  } else {
995  success = try_expand_molecule(molecule,
996  vpack_net[inet].node_block[0],
997  cur_pack_pattern_connection->from_block);
998  }
999  }
1000  cur_pack_pattern_connection = cur_pack_pattern_connection->next;
1001  }
1002  } else {
1003  success = is_optional;
1004  }
1005 
1006  return success;
1007 }
boolean primitive_type_feasible(int iblk, const t_pb_type *cur_pb_type)
Definition: vpr_utils.c:241
t_model_ports * model_port
int ** input_nets
Definition: vpr_types.h:211
t_pack_pattern_block * from_block
Definition: cad_types.h:21
boolean is_clock
Definition: logic_types.h:26
t_pack_pattern_block * to_block
Definition: cad_types.h:24
t_pb_graph_pin * to_pin
Definition: cad_types.h:25
t_pb_graph_pin * from_pin
Definition: cad_types.h:22
struct s_pack_pattern_connections * next
Definition: cad_types.h:27
Definition: slre.c:50
struct s_net * vpack_net
Definition: globals.c:19
int ** output_nets
Definition: vpr_types.h:212
struct s_logical_block * logical_block
Definition: globals.c:20
Definition: util.h:12
static boolean try_expand_molecule(INOUTP t_pack_molecule *molecule, INP int logical_block_index, INP t_pack_pattern_block *current_pattern_block)
Definition: prepack.c:919

+ Here is the call graph for this function:

+ Here is the caller graph for this function: