MulticoreBSP for C  Version 1.2
Data Structures | Functions
mcutil.h File Reference
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <string.h>
#include <unistd.h>
#include <stdint.h>
#include <pthread.h>
#include <stdbool.h>
#include "mcbsp.h"
#include "mcbsp-affinity.h"
Include dependency graph for mcutil.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  mcbsp_util_machine_partition
 Structure representing a part of the current machine. More...
 
struct  mcbsp_util_machine_info
 Structure representing the machine hardware information. More...
 
struct  mcbsp_util_address_map
 A map from pointers to unsigned long ints. More...
 
struct  mcbsp_util_address_table_entry
 A single address table entry. More...
 
struct  mcbsp_util_stack
 Self-growing stack. More...
 
struct  mcbsp_util_address_table
 A table of local address locations per SPMD variable. More...
 
struct  mcbsp_util_pinning_info
 Return type of mcbsp_util_pinning. More...
 

Functions

void mcbsp_util_stack_initialise (struct mcbsp_util_stack *const stack, const size_t elementSize)
 Initialises the mcbsp_util_stack struct. More...
 
void mcbsp_util_stack_grow (struct mcbsp_util_stack *const stack)
 Doubles the capacity of a given stack. More...
 
bool mcbsp_util_stack_empty (const struct mcbsp_util_stack *const stack)
 Checks whether a given stack is empty. More...
 
void * mcbsp_util_stack_pop (struct mcbsp_util_stack *const stack)
 Returns the newest item in the stack. More...
 
void * mcbsp_util_stack_peek (const struct mcbsp_util_stack *const stack)
 Returns the top stack item. More...
 
void mcbsp_util_stack_push (struct mcbsp_util_stack *const stack, const void *const item)
 Pushes a new item on the stack. More...
 
void mcbsp_util_stack_destroy (struct mcbsp_util_stack *const stack)
 Frees all memory related to a given stack. More...
 
void mcbsp_util_varstack_grow (struct mcbsp_util_stack *const stack)
 Doubles the capacity of a given stack. More...
 
void * mcbsp_util_varstack_pop (struct mcbsp_util_stack *const stack, const size_t size)
 Returns the top variable stack item. More...
 
void * mcbsp_util_varstack_regpop (struct mcbsp_util_stack *const stack)
 Returns the top fixed-size item of the stack. More...
 
void * mcbsp_util_varstack_peek (const struct mcbsp_util_stack *const stack, const size_t size)
 Peeks for a variably-sized item on the stack. More...
 
void * mcbsp_util_varstack_regpeek (const struct mcbsp_util_stack *const stack)
 Peeks for a fixed-sized item on the stack. More...
 
void mcbsp_util_varstack_push (struct mcbsp_util_stack *const stack, const void *const item, const size_t size)
 Pushes a variably-sized item on the stack. More...
 
void mcbsp_util_varstack_regpush (struct mcbsp_util_stack *const stack, const void *const item)
 Pushes a fixed-size item on the stack. More...
 
void mcbsp_util_address_table_initialise (struct mcbsp_util_address_table *const table, const unsigned long int P)
 Initialises the mcbsp_util_address_table struct. More...
 
void mcbsp_util_address_table_grow (struct mcbsp_util_address_table *const table)
 Doubles the capacity of a given address table. More...
 
void mcbsp_util_address_table_setsize (struct mcbsp_util_address_table *const table, const unsigned long int target_size)
 Ensures the address table is of at least the given size. More...
 
void mcbsp_util_address_table_destroy (struct mcbsp_util_address_table *const table)
 Frees the memory associated with a given address table. More...
 
void mcbsp_util_address_table_set (struct mcbsp_util_address_table *const table, const unsigned long int key, const unsigned long int version, void *const value, const size_t size)
 Sets an entry in a given address table. More...
 
struct
mcbsp_util_address_table_entry
mcbsp_util_address_table_get (const struct mcbsp_util_address_table *const table, const unsigned long int key, const unsigned long int version)
 Gets an entry from a given address table. More...
 
bool mcbsp_util_address_table_delete (struct mcbsp_util_address_table *const table, const unsigned long int key, const unsigned long int version)
 Removes an entry from a given address table. More...
 
void mcbsp_util_address_map_initialise (struct mcbsp_util_address_map *const address_map)
 Initialises a mcbsp_util_address_map struct. More...
 
void mcbsp_util_address_map_grow (struct mcbsp_util_address_map *const address_map)
 Doubles the capacity of a given address map. More...
 
void mcbsp_util_address_map_destroy (struct mcbsp_util_address_map *const address_map)
 Frees the memory related to a given address map. More...
 
size_t mcbsp_util_address_map_get (const struct mcbsp_util_address_map *const address_map, const void *const key)
 Address map accessor. More...
 
void mcbsp_util_address_map_insert (struct mcbsp_util_address_map *const address_map, void *const key, const size_t value)
 Inserts a key-value pair in the map. More...
 
void mcbsp_util_address_map_remove (struct mcbsp_util_address_map *const address_map, void *const key)
 Removes a key-value pair from the map. More...
 
size_t mcbsp_util_address_map_binsearch (const struct mcbsp_util_address_map *const address_map, const void *const key, size_t lo, size_t hi)
 Helper-function for mcbsp_util_address_map_insert, and mcbsp_util_address_map_remove. More...
 
size_t mcbsp_util_detect_hardware_threads (void)
 Attempts to detect the number of hard-ware threads supported on the current machine. More...
 
struct mcbsp_util_machine_infomcbsp_util_createMachineInfo (void)
 Creates a new machine info struct. More...
 
void mcbsp_util_destroyMachineInfo (void *machine_info)
 If a current machine info instance exists, destroys it. More...
 
int mcbsp_util_integer_compare (const void *a, const void *b)
 Comparison function for use with qsort on arrays of size_t's. More...
 
size_t mcbsp_util_log2 (size_t x)
 Binary logarithm, unsigned integer version, rounding up. More...
 
size_t mcbsp_util_sort_unique_integers (size_t *const array, const size_t length, const size_t lower_bound, const size_t upper_bound)
 Sorts an array of integers. More...
 
bool mcbsp_util_contains (const size_t *const array, const size_t value, const size_t lo, const size_t hi)
 Returns whether an array contains a given value. More...
 
struct mcbsp_util_pinning_info mcbsp_util_pinning (const size_t P, struct mcbsp_util_machine_info *const machine, const struct mcbsp_util_machine_partition *const super_machine)
 Function that yields a pinning of P threads according to the given machine info. More...
 
void mcbsp_util_fatal (void)
 Handles a fatal error in a uniform fashion. More...
 
void mcbsp_util_check_machine_info (struct mcbsp_util_machine_info *const machine)
 Function that prepares a mcbsp_util_machine_info for use. More...
 
struct mcbsp_util_machine_partition mcbsp_util_derive_partition (const struct mcbsp_util_machine_info *const info)
 Derives an initial machine partition from a machine_info object. More...
 
struct mcbsp_util_stack mcbsp_util_partition (const struct mcbsp_util_machine_partition subpart, const size_t P, const enum mcbsp_affinity_mode affinity)
 Derives a P-way subpartition from a given machine partition. More...
 
size_t * mcbsp_util_derive_standard_pinning (const struct mcbsp_util_machine_partition *iterator, const size_t size)
 Derives a pinning from an array of machine partitions. More...
 
void mcbsp_util_filter_standard_pinning (const struct mcbsp_util_machine_info *const info, size_t *const array, const size_t P)
 Filters reserved cores from a standard pinning list. More...
 
void mcbsp_util_translate_standard_pinning (const struct mcbsp_util_machine_info *const info, size_t *const array, const size_t P)
 Translates thread numbers in the standard pinning format (consecutive), to the numbering format active on this machine. More...
 
size_t mcbsp_util_array_sizet_lbound (const size_t *const array, const size_t key, size_t lo, size_t hi)
 Searches an array for the largest value lower or equal to a given key. More...
 

Function Documentation

size_t mcbsp_util_address_map_binsearch ( const struct mcbsp_util_address_map *const  address_map,
const void *const  key,
size_t  lo,
size_t  hi 
)

Helper-function for mcbsp_util_address_map_insert, and mcbsp_util_address_map_remove.

Performs a binary search for key and returns the largest index for which the map key is less or equal to the supplied key value.

Parameters
address_mapPointer to the map to look in.
keyThe key value to look for.
loLower bound on range of the map to look for.
hiupper bound (inclusive) on range of the map to look for.
void mcbsp_util_address_map_destroy ( struct mcbsp_util_address_map *const  address_map)

Frees the memory related to a given address map.

Parameters
address_mapPointer to the struct to destroy.
size_t mcbsp_util_address_map_get ( const struct mcbsp_util_address_map *const  address_map,
const void *const  key 
)

Address map accessor.

Parameters
address_mapPointer to the map to consult.
keyWhich key to search for.
Returns
The value associated with the key.
void mcbsp_util_address_map_grow ( struct mcbsp_util_address_map *const  address_map)

Doubles the capacity of a given address map.

Parameters
address_mapPointer to the struct of the map to increase storage of.
void mcbsp_util_address_map_initialise ( struct mcbsp_util_address_map *const  address_map)

Initialises a mcbsp_util_address_map struct.

Parameters
address_mapPointer to the struct to initialise.
void mcbsp_util_address_map_insert ( struct mcbsp_util_address_map *const  address_map,
void *const  key,
const size_t  value 
)

Inserts a key-value pair in the map.

Parameters
address_mapPointer to the map to insert in.
keyUnder which key to insert the value.
valueThe value to insert.
void mcbsp_util_address_map_remove ( struct mcbsp_util_address_map *const  address_map,
void *const  key 
)

Removes a key-value pair from the map.

Does nothing when the key is not in the map.

Parameters
address_mapPointer to the map to remove from.
keyKey of the key-value pair to remove.
bool mcbsp_util_address_table_delete ( struct mcbsp_util_address_table *const  table,
const unsigned long int  key,
const unsigned long int  version 
)

Removes an entry from a given address table.

Does not do boundary checks.

Parameters
tablePointer to the address table.
keyWhich entry to remove.
versionWhich local version to remove.
Returns
Whether the registration stack at (key,version) is empty.
void mcbsp_util_address_table_destroy ( struct mcbsp_util_address_table *const  table)

Frees the memory associated with a given address table.

Parameters
tablePointer to the struct to destroy.
struct mcbsp_util_address_table_entry* mcbsp_util_address_table_get ( const struct mcbsp_util_address_table *const  table,
const unsigned long int  key,
const unsigned long int  version 
)
read

Gets an entry from a given address table.

Does not do boundary checks.

Parameters
tablePointer to the address table.
keyWhich entry to get.
versionWhich local version to obtain.
Returns
The requested address pointer.
void mcbsp_util_address_table_grow ( struct mcbsp_util_address_table *const  table)

Doubles the capacity of a given address table.

This function is not thread-safe.

Parameters
tablePointer to the struct of the table to increase storage of.
void mcbsp_util_address_table_initialise ( struct mcbsp_util_address_table *const  table,
const unsigned long int  P 
)

Initialises the mcbsp_util_address_table struct.

This function is not thread-safe.

Parameters
tablePointer to the struct to initialise.
PThe number of local versions to maintain for each entry.
void mcbsp_util_address_table_set ( struct mcbsp_util_address_table *const  table,
const unsigned long int  key,
const unsigned long int  version,
void *const  value,
const size_t  size 
)

Sets an entry in a given address table.

Grows table capacity if required.

Parameters
tablePointer to the address table.
keyWhich entry to set.
versionWhich local version to set.
valuePointer to the local memory region..
sizeSize of the local memory region.
void mcbsp_util_address_table_setsize ( struct mcbsp_util_address_table *const  table,
const unsigned long int  target_size 
)

Ensures the address table is of at least the given size.

This function is thread-safe.

Parameters
tablePointer to the struct to initialise.
target_sizeThe (new) minimum size of the table after function exit.
size_t mcbsp_util_array_sizet_lbound ( const size_t *const  array,
const size_t  key,
size_t  lo,
size_t  hi 
)

Searches an array for the largest value lower or equal to a given key.

The array is assumed to be sorted. The array is assumed to contain unique values only. The array has elements of type size_t.

Parameters
arrayThe array to search in.
keyThe key to search for.
loThe lower bound on the index of the elements of array to search in (inclusive).
hiThe higher bound on the index of the elements of array to search in (inclusive).
Returns
The index of the element in array with the largest value lower or equal to key.
void mcbsp_util_check_machine_info ( struct mcbsp_util_machine_info *const  machine)

Function that prepares a mcbsp_util_machine_info for use.

The reserved_cores list will be sorted, and some sanity checks on the supplied information are performed.

Parameters
machineThe struct to check.
bool mcbsp_util_contains ( const size_t *const  array,
const size_t  value,
const size_t  lo,
const size_t  hi 
)

Returns whether an array contains a given value.

Only the range [lo,hi) of array is checked for value.

Parameters
arrayWhere to search in.
valueThe value to search for.
loFrom which index on to search (inclusive).
hiUp to which index to search (exclusive).
Returns
Whether array contains value in the given range.
struct mcbsp_util_machine_info* mcbsp_util_createMachineInfo ( void  )
read

Creates a new machine info struct.

Returns
A pointer to a new machine info struct.
struct mcbsp_util_machine_partition mcbsp_util_derive_partition ( const struct mcbsp_util_machine_info *const  info)
read

Derives an initial machine partition from a machine_info object.

Parameters
infoThe machine info to derive a partitition from.
Returns
The derived initial partitioning.
size_t* mcbsp_util_derive_standard_pinning ( const struct mcbsp_util_machine_partition iterator,
const size_t  size 
)

Derives a pinning from an array of machine partitions.

Should be post-processed to cope with reserved cores and HW thread numbering. If size is smaller than P, multiple threads will pin to the same HW thread, using a wrapping fashion.

Parameters
iteratorPointer to the first element of the array of machine partitions.
sizeNumber of partitions.
Returns
A standard pinning derived from the partitions in consecutive HW thread numbering.
void mcbsp_util_destroyMachineInfo ( void *  machine_info)

If a current machine info instance exists, destroys it.

This function is not thread-safe.

Parameters
machine_infoPointer to the machine info to deallocate properly.
size_t mcbsp_util_detect_hardware_threads ( void  )

Attempts to detect the number of hard-ware threads supported on the current machine.

Returns
Detected number of HW threads.
void mcbsp_util_fatal ( void  )

Handles a fatal error in a uniform fashion.

Only call this function if the error is fatal and unrecoverable, and should thus stop the entire parallel execution.

void mcbsp_util_filter_standard_pinning ( const struct mcbsp_util_machine_info *const  info,
size_t *const  array,
const size_t  P 
)

Filters reserved cores from a standard pinning list.

Will substitute other HW thread numbers if available; otherwise, it will wrap to already-allocated HW threads. Assumes the data in mcbsp_util_machine_info is sorted.

Parameters
infoThe full machine description.
arrayThe standard pinning array to modify.
PThe size of array.
int mcbsp_util_integer_compare ( const void *  a,
const void *  b 
)

Comparison function for use with qsort on arrays of size_t's.

size_t mcbsp_util_log2 ( size_t  x)

Binary logarithm, unsigned integer version, rounding up.

Note: returns 0 for x=0.

struct mcbsp_util_stack mcbsp_util_partition ( const struct mcbsp_util_machine_partition  subpart,
const size_t  P,
const enum mcbsp_affinity_mode  affinity 
)
read

Derives a P-way subpartition from a given machine partition.

Parameters
subpartThe parent partition.
PThe number of subpartitions to create.
affinityThe affinity mode to partition with.
Returns
A mcbsp_util_stack consisting of P subpartitions.
struct mcbsp_util_pinning_info mcbsp_util_pinning ( const size_t  P,
struct mcbsp_util_machine_info *const  machine,
const struct mcbsp_util_machine_partition *const  super_machine 
)
read

Function that yields a pinning of P threads according to the given machine info.

Parameters
PThe number of threads to pin.
machineThe machine to pin for.
super_machineThe top-level machine partition, if any (can be NULL).
Returns
An array R where R[i] gives the core to which thread i should pin to.
size_t mcbsp_util_sort_unique_integers ( size_t *const  array,
const size_t  length,
const size_t  lower_bound,
const size_t  upper_bound 
)

Sorts an array of integers.

The array is assumed to hold unique elements in a given range of values. The algorithm runs linearly in the amount of possible values.

Parameters
arrayThe array to sort.
lengthLength of array.
lower_boundLower bound (inclusive) on values in array.
upper_boundUpper bound (exclusive) on values in array.
Returns
Size of the sorted array.
void mcbsp_util_stack_destroy ( struct mcbsp_util_stack *const  stack)

Frees all memory related to a given stack.

bool mcbsp_util_stack_empty ( const struct mcbsp_util_stack *const  stack)

Checks whether a given stack is empty.

void mcbsp_util_stack_grow ( struct mcbsp_util_stack *const  stack)

Doubles the capacity of a given stack.

void mcbsp_util_stack_initialise ( struct mcbsp_util_stack *const  stack,
const size_t  elementSize 
)

Initialises the mcbsp_util_stack struct.

Parameters
stackThe stack to initialise.
elementSizeThe size of a single element in the stack.
void* mcbsp_util_stack_peek ( const struct mcbsp_util_stack *const  stack)

Returns the top stack item.

Does not remove it from the stack.

Does not do boundary checking! Call mcbsp_util_stack_empty first when unsure if the stack still contains items.

Returns
A pointer to the top element in the stack.
void* mcbsp_util_stack_pop ( struct mcbsp_util_stack *const  stack)

Returns the newest item in the stack.

This function removes that item from the stack.

Does not do boundary checking! Call mcbsp_util_stack_empty first when unsure if the stack still contains items.

Returns
A pointer to the next element in the stack.
void mcbsp_util_stack_push ( struct mcbsp_util_stack *const  stack,
const void *const  item 
)

Pushes a new item on the stack.

void mcbsp_util_translate_standard_pinning ( const struct mcbsp_util_machine_info *const  info,
size_t *const  array,
const size_t  P 
)

Translates thread numbers in the standard pinning format (consecutive), to the numbering format active on this machine.

Parameters
infoThe full machine description.
arrayThe pinning array.
PThe size of array.
void mcbsp_util_varstack_grow ( struct mcbsp_util_stack *const  stack)

Doubles the capacity of a given stack.

void* mcbsp_util_varstack_peek ( const struct mcbsp_util_stack *const  stack,
const size_t  size 
)

Peeks for a variably-sized item on the stack.

void* mcbsp_util_varstack_pop ( struct mcbsp_util_stack *const  stack,
const size_t  size 
)

Returns the top variable stack item.

void mcbsp_util_varstack_push ( struct mcbsp_util_stack *const  stack,
const void *const  item,
const size_t  size 
)

Pushes a variably-sized item on the stack.

void* mcbsp_util_varstack_regpeek ( const struct mcbsp_util_stack *const  stack)

Peeks for a fixed-sized item on the stack.

The fixed size was set at varstack initialisation.

void* mcbsp_util_varstack_regpop ( struct mcbsp_util_stack *const  stack)

Returns the top fixed-size item of the stack.

The fixed size was set at varstack initialisation.

void mcbsp_util_varstack_regpush ( struct mcbsp_util_stack *const  stack,
const void *const  item 
)

Pushes a fixed-size item on the stack.