|
Packit |
577717 |
/*
|
|
Packit |
577717 |
* File: papi_bipartite.h
|
|
Packit |
577717 |
* Author: Dan Terpstra
|
|
Packit |
577717 |
* terpstra@eecs.utk.edu
|
|
Packit |
577717 |
* Mods:
|
|
Packit |
577717 |
*
|
|
Packit |
577717 |
*/
|
|
Packit |
577717 |
/* This file contains one function: _papi_bipartite_alloc()
|
|
Packit |
577717 |
Its role is to act as an execution harness for implementing a recursive
|
|
Packit |
577717 |
Modified Bipartite Graph allocation of counter resources for those
|
|
Packit |
577717 |
platforms that don't have built-in smart counter allocation.
|
|
Packit |
577717 |
It is intended to be #included in the cpu component source to minimize
|
|
Packit |
577717 |
other disruption to the build process.
|
|
Packit |
577717 |
|
|
Packit |
577717 |
This routine presumes the existence of a half dozen "bpt_" helper routines.
|
|
Packit |
577717 |
Prototypes for these routines are given below.
|
|
Packit |
577717 |
|
|
Packit |
577717 |
success return 1
|
|
Packit |
577717 |
fail return 0
|
|
Packit |
577717 |
*/
|
|
Packit |
577717 |
|
|
Packit |
577717 |
/* This function examines the event to determine
|
|
Packit |
577717 |
if it can be mapped to counter ctr.
|
|
Packit |
577717 |
Returns true if it can, false if it can't. */
|
|
Packit |
577717 |
static int
|
|
Packit |
577717 |
_bpt_map_avail( hwd_reg_alloc_t * dst, int ctr );
|
|
Packit |
577717 |
|
|
Packit |
577717 |
/* This function forces the event to
|
|
Packit |
577717 |
be mapped to only counter ctr.
|
|
Packit |
577717 |
Returns nothing. */
|
|
Packit |
577717 |
static void
|
|
Packit |
577717 |
_bpt_map_set( hwd_reg_alloc_t * dst, int ctr );
|
|
Packit |
577717 |
|
|
Packit |
577717 |
/* This function examines the event to determine
|
|
Packit |
577717 |
if it has a single exclusive mapping.
|
|
Packit |
577717 |
Returns true if exlusive, false if non-exclusive. */
|
|
Packit |
577717 |
static int
|
|
Packit |
577717 |
_bpt_map_exclusive( hwd_reg_alloc_t * dst );
|
|
Packit |
577717 |
|
|
Packit |
577717 |
/* This function compares the dst and src events
|
|
Packit |
577717 |
to determine if any resources are shared. Typically the src event
|
|
Packit |
577717 |
is exclusive, so this detects a conflict if true.
|
|
Packit |
577717 |
Returns true if conflict, false if no conflict. */
|
|
Packit |
577717 |
static int
|
|
Packit |
577717 |
_bpt_map_shared( hwd_reg_alloc_t * dst, hwd_reg_alloc_t * src );
|
|
Packit |
577717 |
|
|
Packit |
577717 |
/* This function removes shared resources available to the src event
|
|
Packit |
577717 |
from the resources available to the dst event,
|
|
Packit |
577717 |
and reduces the rank of the dst event accordingly. Typically,
|
|
Packit |
577717 |
the src event will be exclusive, but the code shouldn't assume it.
|
|
Packit |
577717 |
Returns nothing. */
|
|
Packit |
577717 |
static void
|
|
Packit |
577717 |
_bpt_map_preempt( hwd_reg_alloc_t * dst, hwd_reg_alloc_t * src );
|
|
Packit |
577717 |
|
|
Packit |
577717 |
static void
|
|
Packit |
577717 |
_bpt_map_update( hwd_reg_alloc_t * dst, hwd_reg_alloc_t * src );
|
|
Packit |
577717 |
|
|
Packit |
577717 |
|
|
Packit |
577717 |
static int
|
|
Packit |
577717 |
_papi_bipartite_alloc( hwd_reg_alloc_t * event_list, int count, int cidx )
|
|
Packit |
577717 |
{
|
|
Packit |
577717 |
int i, j;
|
|
Packit |
577717 |
char *ptr = ( char * ) event_list;
|
|
Packit |
577717 |
int idx_q[count]; /* queue of indexes of lowest rank events */
|
|
Packit |
577717 |
int map_q[count]; /* queue of mapped events (TRUE if mapped) */
|
|
Packit |
577717 |
int head, tail;
|
|
Packit |
577717 |
int size = _papi_hwd[cidx]->size.reg_alloc;
|
|
Packit |
577717 |
|
|
Packit |
577717 |
/* build a queue of indexes to all events
|
|
Packit |
577717 |
that live on one counter only (rank == 1) */
|
|
Packit |
577717 |
head = 0; /* points to top of queue */
|
|
Packit |
577717 |
tail = 0; /* points to bottom of queue */
|
|
Packit |
577717 |
for ( i = 0; i < count; i++ ) {
|
|
Packit |
577717 |
map_q[i] = 0;
|
|
Packit |
577717 |
if ( _bpt_map_exclusive( ( hwd_reg_alloc_t * ) & ptr[size * i] ) )
|
|
Packit |
577717 |
idx_q[tail++] = i;
|
|
Packit |
577717 |
}
|
|
Packit |
577717 |
/* scan the single counter queue looking for events that share counters.
|
|
Packit |
577717 |
If two events can live only on one counter, return failure.
|
|
Packit |
577717 |
If the second event lives on more than one counter, remove shared counter
|
|
Packit |
577717 |
from its selector and reduce its rank.
|
|
Packit |
577717 |
Mark first event as mapped to its counter. */
|
|
Packit |
577717 |
while ( head < tail ) {
|
|
Packit |
577717 |
for ( i = 0; i < count; i++ ) {
|
|
Packit |
577717 |
if ( i != idx_q[head] ) {
|
|
Packit |
577717 |
if ( _bpt_map_shared( ( hwd_reg_alloc_t * ) & ptr[size * i],
|
|
Packit |
577717 |
( hwd_reg_alloc_t * ) & ptr[size *
|
|
Packit |
577717 |
idx_q
|
|
Packit |
577717 |
[head]] ) ) {
|
|
Packit |
577717 |
/* both share a counter; if second is exclusive, mapping fails */
|
|
Packit |
577717 |
if ( _bpt_map_exclusive( ( hwd_reg_alloc_t * ) &
|
|
Packit |
577717 |
ptr[size * i] ) )
|
|
Packit |
577717 |
return 0;
|
|
Packit |
577717 |
else {
|
|
Packit |
577717 |
_bpt_map_preempt( ( hwd_reg_alloc_t * ) &
|
|
Packit |
577717 |
ptr[size * i],
|
|
Packit |
577717 |
( hwd_reg_alloc_t * ) & ptr[size *
|
|
Packit |
577717 |
idx_q
|
|
Packit |
577717 |
[head]] );
|
|
Packit |
577717 |
if ( _bpt_map_exclusive( ( hwd_reg_alloc_t * ) &
|
|
Packit |
577717 |
ptr[size * i] ) )
|
|
Packit |
577717 |
idx_q[tail++] = i;
|
|
Packit |
577717 |
}
|
|
Packit |
577717 |
}
|
|
Packit |
577717 |
}
|
|
Packit |
577717 |
}
|
|
Packit |
577717 |
map_q[idx_q[head]] = 1; /* mark this event as mapped */
|
|
Packit |
577717 |
head++;
|
|
Packit |
577717 |
}
|
|
Packit |
577717 |
if ( tail == count ) {
|
|
Packit |
577717 |
return 1; /* idx_q includes all events; everything is successfully mapped */
|
|
Packit |
577717 |
} else {
|
|
Packit |
577717 |
char *rest_event_list;
|
|
Packit |
577717 |
char *copy_rest_event_list;
|
|
Packit |
577717 |
int remainder;
|
|
Packit |
577717 |
|
|
Packit |
577717 |
rest_event_list =
|
|
Packit |
577717 |
papi_calloc( _papi_hwd[cidx]->cmp_info.num_cntrs,
|
|
Packit |
577717 |
size );
|
|
Packit |
577717 |
|
|
Packit |
577717 |
copy_rest_event_list =
|
|
Packit |
577717 |
papi_calloc( _papi_hwd[cidx]->cmp_info.num_cntrs,
|
|
Packit |
577717 |
size );
|
|
Packit |
577717 |
|
|
Packit |
577717 |
if ( !rest_event_list || !copy_rest_event_list ) {
|
|
Packit |
577717 |
if ( rest_event_list )
|
|
Packit |
577717 |
papi_free( rest_event_list );
|
|
Packit |
577717 |
if ( copy_rest_event_list )
|
|
Packit |
577717 |
papi_free( copy_rest_event_list );
|
|
Packit |
577717 |
return ( 0 );
|
|
Packit |
577717 |
}
|
|
Packit |
577717 |
|
|
Packit |
577717 |
/* copy all unmapped events to a second list and make a backup */
|
|
Packit |
577717 |
for ( i = 0, j = 0; i < count; i++ ) {
|
|
Packit |
577717 |
if ( map_q[i] == 0 ) {
|
|
Packit |
577717 |
memcpy( ©_rest_event_list[size * j++], &ptr[size * i],
|
|
Packit |
577717 |
( size_t ) size );
|
|
Packit |
577717 |
}
|
|
Packit |
577717 |
}
|
|
Packit |
577717 |
remainder = j;
|
|
Packit |
577717 |
|
|
Packit |
577717 |
memcpy( rest_event_list, copy_rest_event_list,
|
|
Packit |
577717 |
( size_t ) size * ( size_t ) remainder );
|
|
Packit |
577717 |
|
|
Packit |
577717 |
/* try each possible mapping until you fail or find one that works */
|
|
Packit |
577717 |
for ( i = 0; i < _papi_hwd[cidx]->cmp_info.num_cntrs; i++ ) {
|
|
Packit |
577717 |
/* for the first unmapped event, try every possible counter */
|
|
Packit |
577717 |
if ( _bpt_map_avail( ( hwd_reg_alloc_t * ) rest_event_list, i ) ) {
|
|
Packit |
577717 |
_bpt_map_set( ( hwd_reg_alloc_t * ) rest_event_list, i );
|
|
Packit |
577717 |
/* remove selected counter from all other unmapped events */
|
|
Packit |
577717 |
for ( j = 1; j < remainder; j++ ) {
|
|
Packit |
577717 |
if ( _bpt_map_shared( ( hwd_reg_alloc_t * ) &
|
|
Packit |
577717 |
rest_event_list[size * j],
|
|
Packit |
577717 |
( hwd_reg_alloc_t * )
|
|
Packit |
577717 |
rest_event_list ) )
|
|
Packit |
577717 |
_bpt_map_preempt( ( hwd_reg_alloc_t * ) &
|
|
Packit |
577717 |
rest_event_list[size * j],
|
|
Packit |
577717 |
( hwd_reg_alloc_t * )
|
|
Packit |
577717 |
rest_event_list );
|
|
Packit |
577717 |
}
|
|
Packit |
577717 |
/* if recursive call to allocation works, break out of the loop */
|
|
Packit |
577717 |
if ( _papi_bipartite_alloc
|
|
Packit |
577717 |
( ( hwd_reg_alloc_t * ) rest_event_list, remainder,
|
|
Packit |
577717 |
cidx ) )
|
|
Packit |
577717 |
break;
|
|
Packit |
577717 |
|
|
Packit |
577717 |
/* recursive mapping failed; copy the backup list and try the next combination */
|
|
Packit |
577717 |
memcpy( rest_event_list, copy_rest_event_list,
|
|
Packit |
577717 |
( size_t ) size * ( size_t ) remainder );
|
|
Packit |
577717 |
}
|
|
Packit |
577717 |
}
|
|
Packit |
577717 |
if ( i == _papi_hwd[cidx]->cmp_info.num_cntrs ) {
|
|
Packit |
577717 |
papi_free( rest_event_list );
|
|
Packit |
577717 |
papi_free( copy_rest_event_list );
|
|
Packit |
577717 |
return 0; /* fail to find mapping */
|
|
Packit |
577717 |
}
|
|
Packit |
577717 |
for ( i = 0, j = 0; i < count; i++ ) {
|
|
Packit |
577717 |
if ( map_q[i] == 0 )
|
|
Packit |
577717 |
_bpt_map_update( ( hwd_reg_alloc_t * ) & ptr[size * i],
|
|
Packit |
577717 |
( hwd_reg_alloc_t * ) & rest_event_list[size
|
|
Packit |
577717 |
*
|
|
Packit |
577717 |
j++] );
|
|
Packit |
577717 |
}
|
|
Packit |
577717 |
papi_free( rest_event_list );
|
|
Packit |
577717 |
papi_free( copy_rest_event_list );
|
|
Packit |
577717 |
return 1;
|
|
Packit |
577717 |
}
|
|
Packit |
577717 |
}
|
|
Packit |
577717 |
|