PAPI  5.3.2.0
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
papi_bipartite.h
Go to the documentation of this file.
1 /*
2 * File: papi_bipartite.h
3 * Author: Dan Terpstra
4 * terpstra@eecs.utk.edu
5 * Mods:
6 *
7 */
8 /* This file contains one function: _papi_bipartite_alloc()
9  Its role is to act as an execution harness for implementing a recursive
10  Modified Bipartite Graph allocation of counter resources for those
11  platforms that don't have built-in smart counter allocation.
12  It is intended to be #included in the cpu component source to minimize
13  other disruption to the build process.
14 
15  This routine presumes the existence of a half dozen "bpt_" helper routines.
16  Prototypes for these routines are given below.
17 
18  success return 1
19  fail return 0
20 */
21 
22 /* This function examines the event to determine
23  if it can be mapped to counter ctr.
24  Returns true if it can, false if it can't. */
25 static int
26 _bpt_map_avail( hwd_reg_alloc_t * dst, int ctr );
27 
28 /* This function forces the event to
29  be mapped to only counter ctr.
30  Returns nothing. */
31 static void
32 _bpt_map_set( hwd_reg_alloc_t * dst, int ctr );
33 
34 /* This function examines the event to determine
35  if it has a single exclusive mapping.
36  Returns true if exlusive, false if non-exclusive. */
37 static int
39 
40 /* This function compares the dst and src events
41  to determine if any resources are shared. Typically the src event
42  is exclusive, so this detects a conflict if true.
43  Returns true if conflict, false if no conflict. */
44 static int
46 
47 /* This function removes shared resources available to the src event
48  from the resources available to the dst event,
49  and reduces the rank of the dst event accordingly. Typically,
50  the src event will be exclusive, but the code shouldn't assume it.
51  Returns nothing. */
52 static void
54 
55 static void
57 
58 
59 static int
61 {
62  int i, j;
63  char *ptr = ( char * ) event_list;
64  int idx_q[count]; /* queue of indexes of lowest rank events */
65  int map_q[count]; /* queue of mapped events (TRUE if mapped) */
66  int head, tail;
67  int size = _papi_hwd[cidx]->size.reg_alloc;
68 
69  /* build a queue of indexes to all events
70  that live on one counter only (rank == 1) */
71  head = 0; /* points to top of queue */
72  tail = 0; /* points to bottom of queue */
73  for ( i = 0; i < count; i++ ) {
74  map_q[i] = 0;
75  if ( _bpt_map_exclusive( ( hwd_reg_alloc_t * ) & ptr[size * i] ) )
76  idx_q[tail++] = i;
77  }
78  /* scan the single counter queue looking for events that share counters.
79  If two events can live only on one counter, return failure.
80  If the second event lives on more than one counter, remove shared counter
81  from its selector and reduce its rank.
82  Mark first event as mapped to its counter. */
83  while ( head < tail ) {
84  for ( i = 0; i < count; i++ ) {
85  if ( i != idx_q[head] ) {
86  if ( _bpt_map_shared( ( hwd_reg_alloc_t * ) & ptr[size * i],
87  ( hwd_reg_alloc_t * ) & ptr[size *
88  idx_q
89  [head]] ) ) {
90  /* both share a counter; if second is exclusive, mapping fails */
92  ptr[size * i] ) )
93  return 0;
94  else {
96  ptr[size * i],
97  ( hwd_reg_alloc_t * ) & ptr[size *
98  idx_q
99  [head]] );
100  if ( _bpt_map_exclusive( ( hwd_reg_alloc_t * ) &
101  ptr[size * i] ) )
102  idx_q[tail++] = i;
103  }
104  }
105  }
106  }
107  map_q[idx_q[head]] = 1; /* mark this event as mapped */
108  head++;
109  }
110  if ( tail == count ) {
111  return 1; /* idx_q includes all events; everything is successfully mapped */
112  } else {
113  char *rest_event_list;
114  char *copy_rest_event_list;
115  int remainder;
116 
117  rest_event_list =
118  papi_calloc( _papi_hwd[cidx]->cmp_info.num_cntrs,
119  size );
120 
121  copy_rest_event_list =
122  papi_calloc( _papi_hwd[cidx]->cmp_info.num_cntrs,
123  size );
124 
125  if ( !rest_event_list || !copy_rest_event_list ) {
126  if ( rest_event_list )
127  papi_free( rest_event_list );
128  if ( copy_rest_event_list )
129  papi_free( copy_rest_event_list );
130  return ( 0 );
131  }
132 
133  /* copy all unmapped events to a second list and make a backup */
134  for ( i = 0, j = 0; i < count; i++ ) {
135  if ( map_q[i] == 0 ) {
136  memcpy( &copy_rest_event_list[size * j++], &ptr[size * i],
137  ( size_t ) size );
138  }
139  }
140  remainder = j;
141 
142  memcpy( rest_event_list, copy_rest_event_list,
143  ( size_t ) size * ( size_t ) remainder );
144 
145  /* try each possible mapping until you fail or find one that works */
146  for ( i = 0; i < _papi_hwd[cidx]->cmp_info.num_cntrs; i++ ) {
147  /* for the first unmapped event, try every possible counter */
148  if ( _bpt_map_avail( ( hwd_reg_alloc_t * ) rest_event_list, i ) ) {
149  _bpt_map_set( ( hwd_reg_alloc_t * ) rest_event_list, i );
150  /* remove selected counter from all other unmapped events */
151  for ( j = 1; j < remainder; j++ ) {
152  if ( _bpt_map_shared( ( hwd_reg_alloc_t * ) &
153  rest_event_list[size * j],
154  ( hwd_reg_alloc_t * )
155  rest_event_list ) )
157  rest_event_list[size * j],
158  ( hwd_reg_alloc_t * )
159  rest_event_list );
160  }
161  /* if recursive call to allocation works, break out of the loop */
163  ( ( hwd_reg_alloc_t * ) rest_event_list, remainder,
164  cidx ) )
165  break;
166 
167  /* recursive mapping failed; copy the backup list and try the next combination */
168  memcpy( rest_event_list, copy_rest_event_list,
169  ( size_t ) size * ( size_t ) remainder );
170  }
171  }
172  if ( i == _papi_hwd[cidx]->cmp_info.num_cntrs ) {
173  papi_free( rest_event_list );
174  papi_free( copy_rest_event_list );
175  return 0; /* fail to find mapping */
176  }
177  for ( i = 0, j = 0; i < count; i++ ) {
178  if ( map_q[i] == 0 )
179  _bpt_map_update( ( hwd_reg_alloc_t * ) & ptr[size * i],
180  ( hwd_reg_alloc_t * ) & rest_event_list[size
181  *
182  j++] );
183  }
184  papi_free( rest_event_list );
185  papi_free( copy_rest_event_list );
186  return 1;
187  }
188 }
189 
static void _bpt_map_preempt(hwd_reg_alloc_t *dst, hwd_reg_alloc_t *src)
static int _papi_bipartite_alloc(hwd_reg_alloc_t *event_list, int count, int cidx)
#define papi_free(a)
Definition: papi_memory.h:35
gc head
Definition: libasync.c:669
static void _bpt_map_set(hwd_reg_alloc_t *dst, int ctr)
int count
Definition: iozone.c:22422
static int _bpt_map_exclusive(hwd_reg_alloc_t *dst)
static void _bpt_map_update(hwd_reg_alloc_t *dst, hwd_reg_alloc_t *src)
int i
Definition: fileop.c:140
static int _bpt_map_shared(hwd_reg_alloc_t *dst, hwd_reg_alloc_t *src)
char *long long size
Definition: iozone.c:12023
static int cidx
Definition: event_info.c:40
static int _bpt_map_avail(hwd_reg_alloc_t *dst, int ctr)
struct papi_vectors * _papi_hwd[]
gc tail
Definition: libasync.c:667
long j
Definition: iozone.c:19135
#define papi_calloc(a, b)
Definition: papi_memory.h:37
char * ptr
Definition: iozone.c:23586