Multithreading

Multithreading - Multithreading implementation in GridLAB-D

Synopsis

typedef struct s_mtiteratorlist MTI;
typedef struct s_mtifunctions MTIFUNCTIONS;
typedet struct void *MTIITEM;
typedef struct void *MTIDATA;
MTI *mti_init(const char *name, MTIFUNCTIONS *fns, size_t minitems);
int mti_run(MTIDATA result, MTI *iterator, MTIDATA input);

Description

Multithread iterators are special iteration control objects that allow multiple thread to be created and staged for activation at particular times to perform large scale iterative operations. Usually more than 1 thread but fewer than the number of available processors are allocated to an iterator. The only exception is if the iteration process involves blocking events such as I/O operations, in which case more threads may be allocated than the number of available processors.

The MTI structure containers the data required to manage the iterator. It must be allocated and initialized once per run of GridLAB-D. The mti_init function is used to initialize the iterator. The MTIFUNCTIONS structure contains the iteration control function table required to run the iterator. The mti_run function is used to start the iterator. The MTI_DATA structure is used to pass data to and from the iteration control functions.

See source documentation for details.

MTI

A multithread iterator is setup once during initialization. Typically, the iterator will be a static allocation, such as

static MTI *my_mti = NULL;

MTIFUNCTIONS

The iteration control functions are required to provide the iterator access to the functions needed to perform the iterative process. The declaration of the iteration control function is of the form

static MTIFUNCTIONS fns = {get, call, set, compare, gather, reject};

Note that fns must be statically allocated although the contents may be dynamically changed when mti_run is not currently being executed.

get

The get iteration control function is used by the iterator to retrieve the next item in the iteration list. The function prototype is

MTIITEM get(MTIITEM item);

If item is NULL, the get function must return the first item in the list. If item is the last item in the list the get function must return NULL.

call

The call iteration control function is used by the iterator to call the iterative process on an individual iteration list item. The function prototype is

void call(MTIDATA output, MTIITEM item, MTIDATA input);

The call function may set the output data.

set

The set iteration control function is used by the iterator to set the data for an iterative process. The function prototype is

MTIDATA set(MTIDATA to, MTIDATA from);

When to is NULL, the return value should be a new MTIDATA. When from a NULL the contents of to should be cleared or reset to the default or initial value, depending on the purpose of the iteration process.

compare

The compare iteration control function compare two MTIDATAs and returns the boolean relationship between them. The function prototype is

int compare(MTIDATA a, MTIDATA b);

If a or b is NULL, the cleared/default/initial value is used. If a < b, then -1 is returned. If a == b, then 0 is returned. If a > b, then 1 is returned.

gather

The gather iteration control function is used to merge a MTIDATA into another. The function prototype is

void gather(MTIDATA to, MTIDATA from);

If either to or from is NULL, nothing is done. The merge operation is presumed to be contingent on the values of to and from depending on the purpose of the iterator.

reject

The reject iteration control function is used to determine whether a MTIDATA item should be considered for an iteration update. This allows the iterator to avoid unnecessary or undesired calls to call during the iteration process. If reject is NULL, no items will be rejected. The function prototype is

int reject(MTI mti, MTIDATA data);

MTIITEM

The MTIITEM typedef allows references to individual items in the iteration list. It is used by the get and call iteration control functions.

MTIDATA

MTIDATA input = (MTIDATA)&my_input;
MTIDATA output = (MTIDATA)&my_output;

mti_init

The mti_init function is used to initialize the iterator. The function prototype is

MTI *mti_init(const char *mti-name, MTIFUNCTIONS fns, size_t min-items);

The mti-name may be any string constant and is used for debugging, verbose, warning and error output messages. The iteration control function table is passed using the fns variable. The minimum number of items per thread is provided using the min-items variable.

When mti_init is called, the global variable mti_debug is consulted. If mti_debug is boolean#TRUE then debugging output will be produced while iterators work.

mti_run

The mti_run function is used to start the iterator. The function will return only after all the items have been processed.

int mti_run(MTIDATA output,MTI *mti,MTIDATA input);

The input and output variables are used to provide and collect data from the iterator. The mti variable is the iterator handle returned by mti_init. When iterator run succeeds, the return value is non-zero. When the iterator run fails, the return value is zero and the single-threaded iterator should be run instead.

Example

static SIMPLELINKLIST my_list = NULL;
static TIMESTAMP my_process(OBJECT *obj, TIMESTAMP t0)
{
  TIMESTAMP t1 = TS_NEVER;
  // implements an iterative process on the obj at the time t0
  return t1;
}
static TIMESTAMP my_iterator_st(TIMESTAMP t0)
{
  OBJECT *obj;
  TIMESTAMP t1 = TS_NEVER;
  for ( obj=object_get_first() ; obj!=NULL ; obj=object_get_next(obj) )
  {
    TIMESTAMP t2 = my_process(t0);
    if ( t2<t1 ) t1 = t2;
  }
  return t1;
}
static size_t my_count(void)
{
  int n = 0;
  OBJECT *obj;
  SIMPLELINKLIST *item;
  for ( obj=object_get_first() ; obj!=NULL ; obj=object_get_next(obj) )
  {
    item = (SIMPLELISTLIST*)malloc(sizeof(SIMPLELINKLIST));
    if ( item==NULL ) throw "memory allocation failed";
    item->data = (void*)objl
    item->next = my_list;
    my_list = item->next;
    n++;
  }
  return n;
}
static MTIITEM my_get(MTIITEM item)
{
  return item==NULL ? my_list : item->next;
}
static void my_call(MTIDATA output, MTIITEM item, MTIDATA input)
{
  OBJECT *obj = (OBJECT*)(((SIMPLELINKLIST*)item)->data);
  TIMESTAMP *t1 = (TIMESTAMP*)output;
  TIMESTAMP *t0 = (TIMESTAMP*)input;
  *t1 = my_process(obj,*t0);
}
static MTIDATA my_set(MTIDATA to, MTIDATA from)
{
  if ( to==NULL ) to = (MTIDATA)malloc(sizeof(TIMESTAMP));
  if ( to==NULL ) throw "memory allocation error";
  if ( from==NULL ) *to = *(TIMESTAMP)to = TS_NEVER;
  else memcpy(to,from,sizeof(TIMESTAMP);
}
static int my_compare(MTIDATA a, MTIDATA b)
{
  TIMESTAMP t0 = (a?*(TIMESTAMP*)a:TS_NEVER);
  TIMESTAMP t1 = (b?*(TIMESTAMP*)b:TS_NEVER);
  if ( t0>t1  ) return 1;
  else if ( t0<t1 ) return -1;
  else return 0;
}
static void my_gather(MTIDATA to, MTIDATA from)
{
  TIMESTAMP *t0 = (TIMESTAMP*)to;
  TIMESTAMP *t1 = (TIMESTAMP*)from;
  if ( to==NULL || from==NULL ) return;
  if ( *t1<*t0 ) *t0 = *t1;
}
static int my_reject(MTI *mti, MTIDATA value)
{
  TIMESTAMP *t1 = (TIMESTAMP*)value;
  TIMESTAMP *t2 = (TIMESTAMP*)mti->output;
  if ( value==NULL ) return 0;
  return ( *t2>*t1 && *t2<TS_NEVER ) ? 1 : 0;
}
static TIMESTAMP my_iterator(TIMESTAMP t)
{
  static MTI *my_mti = NULL;
  MTIDATA my_input = (MTIDATA)&t;
  TIMESTAMP result = TS_NEVER;
  MTIDATA my_output = (MTIDATA)&result;
  if ( my_mti==NULL )
  {
    static MTIFUNCTIONS my_fns = {my_get, my_call, my_set, my_compare, my_gather, my_reject};
    my_mti = mti_init("my_mti", my_fns, my_count);
  }
  if ( my_mti==NULL || !mti_run((MTIDATA)&my_output,my_mti,(MTIDATA)&my_input) )
    my_output = my_iterator_st(my_input);
  return result;
}

Implementation

There are three areas of GridLAB-D that benefit from multiple threads:

SuperLU

The multithreading of SuperLU was addressed by implementing the SuperLU MT library. This library is linked statically and needs to be made to run as a runtime linked object.

Built-in updates

There are four types of built-in objects that are updated frequently. Each type of object update is highly parallel, but the types must be updated sequentially. They are

schedules
loadshapes
transforms
enduses

A threadpool for each of these should be implemented with roughly as many threads as there are available processing units.

Object synchronization

Object synchronization is an intrincate sequence of calls to various object sync functions. They are executed by rank in three passes, followed by a commit pass. The first pass is a top-down pass, the second a bottom-up pass, and the third a top-down pass. All the objects within a rank may be sync'd simultaneously given a sufficient number of threads.

The thread pool should be set up before the first call, and each pass and rank should have as many call lists as there are threads in the pool. Each thread should process each call list and when done rejoin the main thread.

For example, with 4 threads

Top-down pass
1. Rank
  1. Thread: auction:1
2. Rank
  1. Thread: house:1, house:5, house:9
  2. Thread: house:2, house:6, house:10
  3. Thread: house:3, house:7
  4. Thread: house:4, house:8
Bottom-up pass
1. Rank
  1. Thread: house:1, house:5, house:9
  2. Thread: house:2, house:6, house:10
  3. Thread: house:3, house:7
  4. Thread: house:4, house:8
2. Rank
  1. Thread: auction:1
Top-down pass
1. Rank
  1. Thread: auction:1
2. Rank
  1. Thread: house:1, house:5, house:9
  2. Thread: house:2, house:6, house:10
  3. Thread: house:3, house:7
  4. Thread: house:4, house:8

References

Pthreads Tutorial (LLNL)

Multithreading

Views

Contents