PPL Logo

CharmScheduler

The portion of Charm++ responsible for scheduling the execution of Charm++ entry methods. More...


Files

file  modifyScheduler.C
 Routines for modifying the Charm++ prioritized message queue.
file  converse.h
 Main Converse header file.
file  queueing.c
 Implementation of queuing data structure functions.
file  queueing.h
 Declarations of queuing data structure functions.

Data Structures

struct  prio_struct
 Stores a variable bit length priority. More...
struct  deq_struct
 A double ended queue of void* pointers stored in a circular buffer, with internal space for 4 entries. More...
struct  prioqelt_struct
 A bucket in a priority queue which contains a deque(storing the void* pointers) and references to other buckets in the hash table. More...
struct  prioq_struct
 A priority queue, implemented as a heap of prioqelt_struct buckets (each bucket represents a single priority value and contains a deque of void* pointers). More...
struct  Queue_struct
 A set of 3 queues: a positive priority prioq_struct, a negative priority prioq_struct, and a zero priority deq_struct. More...

Typedefs

typedef struct prio_struct * _prio
typedef struct deq_struct * _deq
typedef struct prioqelt_struct * _prioqelt
typedef struct prioq_struct * _prioq
typedef struct Queue_struct * Queue

Functions

int CqsFindRemoveSpecificPrioq (_prioq q, void *&msgPtr, const int *entryMethod, const int numEntryMethods)
 Find and remove the first 1 occurences of messages that matches a specified entry method index.
int CqsFindRemoveSpecificDeq (_deq q, void *&msgPtr, const int *entryMethod, const int numEntryMethods)
 Find and remove the first 1 occurences of messages that matches a specified entry method index.
void CqsIncreasePriorityForEntryMethod (Queue q, const int entrymethod)
 Search Queue for messages associated with a specified entry method.
void CqsIncreasePriorityForMemCriticalEntries (Queue q)
 Search Queue for messages associated with memory-critical entry methods.
static void CqsDeqInit (_deq d)
 Initialize a deq.
static void CqsDeqExpand (_deq d)
 Double the size of a deq.
void CqsDeqEnqueueFifo (_deq d, void *data)
 Insert a data pointer at the tail of a deq.
void CqsDeqEnqueueLifo (_deq d, void *data)
 Insert a data pointer at the head of a deq.
void * CqsDeqDequeue (_deq d)
 Remove a data pointer from the head of a deq.
static void CqsPrioqInit (_prioq pq)
 Initialize a Priority Queue.
static void CqsPrioqExpand (_prioq pq)
 Double the size of a Priority Queue's heap.
void CqsPrioqRehash (_prioq pq)
 Double the size of a Priority Queue's hash table.
int CqsPrioGT_ (unsigned int ints1, unsigned int *data1, unsigned int ints2, unsigned int *data2)
int CqsPrioGT (_prio prio1, _prio prio2)
 Compare two priorities (treated as unsigned).
_deq CqsPrioqGetDeq (_prioq pq, unsigned int priobits, unsigned int *priodata)
 Find or create a bucket in the hash table for the specified priority.
void * CqsPrioqDequeue (_prioq pq)
 Dequeue an entry.
Queue CqsCreate (void)
 Initialize a Queue and its three internal queues (for positive, negative, and zero priorities).
void CqsDelete (Queue)
 Delete a Queue.
unsigned int CqsLength (Queue q)
unsigned int CqsMaxLength (Queue q)
int CqsEmpty (Queue q)
void CqsEnqueueGeneral (Queue, void *msg, int strategy, int priobits, unsigned int *prioPtr)
 Enqueue something (usually an envelope*) into the queue in a manner consistent with the specified strategy and priority.
void CqsEnqueueFifo (Queue, void *msg)
 Enqueue behind other elements of priority 0.
void CqsEnqueueLifo (Queue, void *msg)
 Enqueue ahead of other elements of priority 0.
void CqsEnqueue (Queue, void *msg)
 Enqueue with priority 0.
void CqsDequeue (Queue, void **msgPtr)
 Retrieve the highest priority message (one with most negative priority).
_prio CqsGetPriority (Queue)
 Get the priority of the highest priority message in q.
void ** CqsEnumerateDeq (_deq q, int *num)
 Produce an array containing all the entries in a deq.
void ** CqsEnumeratePrioq (_prioq q, int *num)
 Produce an array containing all the entries in a prioq.
void CqsEnumerateQueue (Queue q, void ***resp)
 Produce an array containing all the entries in a Queue.
int CqsRemoveSpecificDeq (_deq q, const void *msgPtr)
 Remove first occurence of a specified entry from the deq by setting the entry to NULL.
int CqsRemoveSpecificPrioq (_prioq q, const void *msgPtr)
 Remove first occurence of a specified entry from the prioq by setting the entry to NULL.
void CqsRemoveSpecific (Queue, const void *msgPtr)
 Remove an occurence of a specified entry from the Queue by setting its entry to NULL.

Variables

int schedAdaptMemThresholdMB
 A memory limit threshold for adaptively scheduling.
static struct prio_struct kprio_zero = { 0, 0, {0} }
static struct prio_struct kprio_max = { 32, 1, {((unsigned int)(-1))} }
int numMemCriticalEntries = 0
int * memCriticalEntries = NULL
int schedAdaptMemThresholdMB
 A memory limit threshold for adaptively scheduling.

Detailed Description

The portion of Charm++ responsible for scheduling the execution of Charm++ entry methods.

CqsEnqueueGeneral() is the main function that is responsible for enqueueing messages. It will store the messages in one of three queues based on the specified priorities or strategies. The Charm++ message queue is really three queues, one for positive priorities, one for zero priorities, and one for negative priorities. The positive and negative priorty queues are actually heaps.

The charm++ messages are only scheduled after the converse message queues have been emptied:

Typedef Documentation

typedef struct prio_struct * _prio

typedef struct deq_struct * _deq

typedef struct prioqelt_struct * _prioqelt

typedef struct prioq_struct * _prioq

typedef struct Queue_struct * Queue

Function Documentation

int CqsFindRemoveSpecificPrioq ( _prioq  q,
void *&  msgPtr,
const int *  entryMethod,
const int  numEntryMethods 
)

Find and remove the first 1 occurences of messages that matches a specified entry method index.

The size of the prioq will not change, it will just contain an entry for a NULL pointer.

Returns:
number of entries that were replaced with NULL
Parameters:
[in] q A priority queue
[out] msgPtr returns the message that was removed from the prioq
[in] entryMethod An array of entry method ids that should be considered for removal
[in] numEntryMethods The number of the values in the entryMethod array.

< An iterator used to iterate through a circular queue

< The end of the circular queue

Definition at line 127 of file modifyScheduler.C.

References prioqelt_struct::data, ForArrayEltMsg, ForChareMsg, envelope::getMsgtype(), envelope::getsetArrayEp(), deq_struct::head, prioq_struct::heap, prioq_struct::heapnext, and deq_struct::tail.

Referenced by CqsIncreasePriorityForEntryMethod(), and CqsIncreasePriorityForMemCriticalEntries().

int CqsFindRemoveSpecificDeq ( _deq  q,
void *&  msgPtr,
const int *  entryMethod,
const int  numEntryMethods 
)

Find and remove the first 1 occurences of messages that matches a specified entry method index.

The size of the deq will not change, it will just contain an entry for a NULL pointer.

Returns:
number of entries that were replaced with NULL
Parameters:
[in] q A circular double ended queue
[out] msgPtr returns the message that was removed from the prioq
[in] entryMethod An array of entry method ids that should be considered for removal
[in] numEntryMethods The number of the values in the entryMethod array.

< An iterator used to iterate through the circular queue

Definition at line 84 of file modifyScheduler.C.

References deq_struct::bgn, deq_struct::end, ForArrayEltMsg, ForChareMsg, envelope::getMsgtype(), envelope::getsetArrayEp(), deq_struct::head, and deq_struct::tail.

Referenced by CqsIncreasePriorityForEntryMethod(), and CqsIncreasePriorityForMemCriticalEntries().

void CqsIncreasePriorityForEntryMethod ( Queue  q,
const int  entrymethod 
)

Search Queue for messages associated with a specified entry method.

Definition at line 22 of file modifyScheduler.C.

References CqsEnqueueGeneral(), CqsFindRemoveSpecificDeq(), CqsFindRemoveSpecificPrioq(), Queue_struct::negprioq, Queue_struct::posprioq, prio, traceUserSuppliedNote(), and Queue_struct::zeroprio.

void CqsIncreasePriorityForMemCriticalEntries ( Queue  q  ) 

Search Queue for messages associated with memory-critical entry methods.

Definition at line 50 of file modifyScheduler.C.

References CqsEnqueueGeneral(), CqsFindRemoveSpecificDeq(), CqsFindRemoveSpecificPrioq(), memCriticalEntries, Queue_struct::negprioq, numMemCriticalEntries, Queue_struct::posprioq, prio, traceUserSuppliedNote(), and Queue_struct::zeroprio.

Referenced by CqsDequeue().

static void CqsDeqInit ( _deq  d  )  [static]

Initialize a deq.

Definition at line 45 of file queueing.c.

References deq_struct::bgn, deq_struct::end, deq_struct::head, deq_struct::space, and deq_struct::tail.

Referenced by CqsCreate(), and CqsPrioqGetDeq().

static void CqsDeqExpand ( _deq  d  )  [static]

Double the size of a deq.

Definition at line 54 of file queueing.c.

References deq_struct::bgn, CmiAlloc(), CmiFree(), deq_struct::end, deq_struct::head, deq_struct::space, and deq_struct::tail.

Referenced by CqsDeqEnqueueFifo(), and CqsDeqEnqueueLifo().

void CqsDeqEnqueueFifo ( _deq  d,
void *  data 
)

Insert a data pointer at the tail of a deq.

Definition at line 72 of file queueing.c.

References deq_struct::bgn, CqsDeqExpand(), deq_struct::end, deq_struct::head, and deq_struct::tail.

Referenced by CqsEnqueue(), CqsEnqueueFifo(), and CqsEnqueueGeneral().

void CqsDeqEnqueueLifo ( _deq  d,
void *  data 
)

Insert a data pointer at the head of a deq.

Definition at line 83 of file queueing.c.

References deq_struct::bgn, CqsDeqExpand(), deq_struct::end, deq_struct::head, and deq_struct::tail.

Referenced by CqsEnqueueGeneral(), and CqsEnqueueLifo().

void* CqsDeqDequeue ( _deq  d  ) 

Remove a data pointer from the head of a deq.

Definition at line 94 of file queueing.c.

References deq_struct::bgn, data, deq_struct::end, deq_struct::head, and deq_struct::tail.

Referenced by CqsDequeue(), and CqsPrioqDequeue().

static void CqsPrioqInit ( _prioq  pq  )  [static]

Initialize a Priority Queue.

Definition at line 110 of file queueing.c.

References CmiAlloc(), prioq_struct::hash_entry_size, prioq_struct::hash_key_size, prioq_struct::hashtab, prioq_struct::heap, prioq_struct::heapnext, and prioq_struct::heapsize.

Referenced by CqsCreate().

static void CqsPrioqExpand ( _prioq  pq  )  [inline, static]

Double the size of a Priority Queue's heap.

Definition at line 126 of file queueing.c.

References CmiAlloc(), CmiFree(), prioq_struct::heap, and prioq_struct::heapsize.

Referenced by CqsPrioqGetDeq().

void CqsPrioqRehash ( _prioq  pq  ) 

Double the size of a Priority Queue's hash table.

Definition at line 139 of file queueing.c.

References prio_struct::bits, CmiAlloc(), CmiFree(), prio_struct::data, prioq_struct::hash_key_size, prioq_struct::hashtab, prioqelt_struct::ht_handle, prioqelt_struct::ht_next, prio_struct::ints, and prioqelt_struct::pri.

Referenced by CqsPrioqGetDeq().

int CqsPrioGT_ ( unsigned int  ints1,
unsigned int *  data1,
unsigned int  ints2,
unsigned int *  data2 
)

Definition at line 176 of file queueing.c.

Referenced by CldPutTokenPrio().

int CqsPrioGT ( _prio  prio1,
_prio  prio2 
)

Compare two priorities (treated as unsigned).

Returns:
1 if prio1 > prio2

? if prio1 == prio2

0 if prio1 < prio2

Definition at line 198 of file queueing.c.

References prio_struct::data, and prio_struct::ints.

Referenced by CqsPrioqDequeue(), CqsPrioqGetDeq(), and CsdNextMessage().

_deq CqsPrioqGetDeq ( _prioq  pq,
unsigned int  priobits,
unsigned int *  priodata 
)

Find or create a bucket in the hash table for the specified priority.

Definition at line 235 of file queueing.c.

References prio_struct::bits, CmiAlloc(), CqsDeqInit(), CqsPrioGT(), CqsPrioqExpand(), CqsPrioqRehash(), prioqelt_struct::data, prio_struct::data, prioq_struct::hash_entry_size, prioq_struct::hash_key_size, prioq_struct::hashtab, prioq_struct::heap, prioq_struct::heapnext, prioq_struct::heapsize, prioqelt_struct::ht_handle, prioqelt_struct::ht_left, prioqelt_struct::ht_next, prioqelt_struct::ht_parent, prioqelt_struct::ht_right, and prioqelt_struct::pri.

Referenced by CqsEnqueueGeneral().

void* CqsPrioqDequeue ( _prioq  pq  ) 

Dequeue an entry.

Definition at line 349 of file queueing.c.

References deq_struct::bgn, CmiFree(), CqsDeqDequeue(), CqsPrioGT(), prioqelt_struct::data, data, prioq_struct::hash_entry_size, deq_struct::head, prioq_struct::heap, prioq_struct::heapnext, prioqelt_struct::ht_handle, prioqelt_struct::ht_left, prioqelt_struct::ht_next, prioqelt_struct::ht_parent, prioqelt_struct::ht_right, prioqelt_struct::pri, deq_struct::space, and deq_struct::tail.

Referenced by CqsDequeue().

Queue CqsCreate ( void   ) 

Initialize a Queue and its three internal queues (for positive, negative, and zero priorities).

Definition at line 545 of file queueing.c.

References CmiAlloc(), CqsDeqInit(), CqsPrioqInit(), Queue_struct::length, Queue_struct::maxlen, Queue_struct::negprioq, Queue_struct::posprioq, and Queue_struct::zeroprio.

Referenced by _messageLoggingInit(), CldModuleInit(), CkObjectMsgQ::create(), and CsdInit().

void CqsDelete ( Queue  q  ) 

Delete a Queue.

Definition at line 559 of file queueing.c.

References CmiFree(), prioq_struct::heap, Queue_struct::negprioq, and Queue_struct::posprioq.

Referenced by CkObjectMsgQ::~CkObjectMsgQ().

unsigned int CqsLength ( Queue  q  ) 

Definition at line 566 of file queueing.c.

References Queue_struct::length.

Referenced by CldLoadRank(), getSchedQlen(), CkObjectMsgQ::length(), and retryTicketRequest().

unsigned int CqsMaxLength ( Queue  q  ) 

Definition at line 571 of file queueing.c.

References Queue_struct::maxlen.

int CqsEmpty ( Queue  q  ) 

Definition at line 576 of file queueing.c.

References Queue_struct::length.

Referenced by CsdNextLocalNodeMessage(), CsdNextMessage(), preProcessReceivedMessage(), processDelayedRemoteMsgQueue(), and PumpMsgsBlocking().

void CqsEnqueueGeneral ( Queue  q,
void *  data,
int  strategy,
int  priobits,
unsigned int *  prioptr 
)

Enqueue something (usually an envelope*) into the queue in a manner consistent with the specified strategy and priority.

Definition at line 581 of file queueing.c.

References CmiAbort(), CmiEndianness(), CqsDeqEnqueueFifo(), CqsDeqEnqueueLifo(), CqsPrioqGetDeq(), Queue_struct::length, Queue_struct::maxlen, Queue_struct::negprioq, Queue_struct::posprioq, and Queue_struct::zeroprio.

Referenced by _enqObjQueue(), _ObjectQHandler(), _skipCldEnqueue(), _skipCldHandler(), CqsIncreasePriorityForEntryMethod(), CqsIncreasePriorityForMemCriticalEntries(), preProcessReceivedMessage(), processDelayedRemoteMsgQueue(), and resendMessageForChare().

void CqsEnqueueFifo ( Queue  q,
void *  data 
)

Enqueue behind other elements of priority 0.

Definition at line 661 of file queueing.c.

References CqsDeqEnqueueFifo(), Queue_struct::length, Queue_struct::maxlen, and Queue_struct::zeroprio.

void CqsEnqueueLifo ( Queue  q,
void *  data 
)

Enqueue ahead of other elements of priority 0.

Definition at line 667 of file queueing.c.

References CqsDeqEnqueueLifo(), Queue_struct::length, Queue_struct::maxlen, and Queue_struct::zeroprio.

void CqsEnqueue ( Queue  q,
void *  data 
)

Enqueue with priority 0.

Definition at line 673 of file queueing.c.

References CqsDeqEnqueueFifo(), Queue_struct::length, Queue_struct::maxlen, and Queue_struct::zeroprio.

Referenced by preProcessReceivedMessage().

void CqsDequeue ( Queue  q,
void **  resp 
)

Retrieve the highest priority message (one with most negative priority).

Definition at line 679 of file queueing.c.

References CmiMemoryUsage(), CqsDeqDequeue(), CqsIncreasePriorityForMemCriticalEntries(), CqsPrioqDequeue(), deq_struct::head, prioq_struct::heapnext, Queue_struct::length, Queue_struct::negprioq, Queue_struct::posprioq, deq_struct::tail, and Queue_struct::zeroprio.

Referenced by CpdGetNextMessageConditional(), CsdNextLocalNodeMessage(), CsdNextMessage(), preProcessReceivedMessage(), CkObjectMsgQ::process(), and processDelayedRemoteMsgQueue().

_prio CqsGetPriority ( Queue  q  ) 

Get the priority of the highest priority message in q.

Definition at line 703 of file queueing.c.

References deq_struct::head, prioq_struct::heap, prioq_struct::heapnext, Queue_struct::negprioq, Queue_struct::posprioq, prioqelt_struct::pri, deq_struct::tail, and Queue_struct::zeroprio.

Referenced by CsdNextMessage().

void** CqsEnumerateDeq ( _deq  q,
int *  num 
)

Produce an array containing all the entries in a deq.

Returns:
a newly allocated array filled with copies of the (void*) elements in the deq.
Parameters:
[in] q a deq
[out] num the number of pointers in the returned array

Definition at line 724 of file queueing.c.

References deq_struct::bgn, CmiAlloc(), deq_struct::end, deq_struct::head, and deq_struct::tail.

Referenced by CqsEnumerateQueue().

void** CqsEnumeratePrioq ( _prioq  q,
int *  num 
)

Produce an array containing all the entries in a prioq.

Returns:
a newly allocated array filled with copies of the (void*) elements in the prioq.
Parameters:
[in] q a deq
[out] num the number of pointers in the returned array

Definition at line 760 of file queueing.c.

References CmiAlloc(), prioqelt_struct::data, deq_struct::head, prioq_struct::heap, prioq_struct::heapnext, and deq_struct::tail.

Referenced by CqsEnumerateQueue().

void CqsEnumerateQueue ( Queue  q,
void ***  resp 
)

Produce an array containing all the entries in a Queue.

Returns:
a newly allocated array filled with copies of the (void*) elements in the Queue.
Parameters:
[in] q a Queue
[out] resp an array of pointer entries found in the Queue, with as many entries as the Queue's length. The caller must CmiFree this.

Definition at line 799 of file queueing.c.

References CmiAlloc(), CmiFree(), CqsEnumerateDeq(), CqsEnumeratePrioq(), Queue_struct::length, Queue_struct::negprioq, Queue_struct::posprioq, and Queue_struct::zeroprio.

int CqsRemoveSpecificDeq ( _deq  q,
const void *  msgPtr 
)

Remove first occurence of a specified entry from the deq by setting the entry to NULL.

The size of the deq will not change, it will now just contain an entry for a NULL pointer.

Returns:
number of entries that were replaced with NULL

Definition at line 838 of file queueing.c.

References deq_struct::bgn, deq_struct::end, deq_struct::head, and deq_struct::tail.

Referenced by CqsRemoveSpecific().

int CqsRemoveSpecificPrioq ( _prioq  q,
const void *  msgPtr 
)

Remove first occurence of a specified entry from the prioq by setting the entry to NULL.

The size of the prioq will not change, it will now just contain an entry for a NULL pointer.

Returns:
number of entries that were replaced with NULL

Definition at line 866 of file queueing.c.

References prioqelt_struct::data, deq_struct::head, prioq_struct::heap, prioq_struct::heapnext, and deq_struct::tail.

Referenced by CqsRemoveSpecific().

void CqsRemoveSpecific ( Queue  ,
const void *  msgPtr 
)

Remove an occurence of a specified entry from the Queue by setting its entry to NULL.

The size of the Queue will not change, it will now just contain an entry for a NULL pointer.

Definition at line 890 of file queueing.c.

References CmiPrintf(), CqsRemoveSpecificDeq(), CqsRemoveSpecificPrioq(), Queue_struct::negprioq, Queue_struct::posprioq, and Queue_struct::zeroprio.

Variable Documentation

int schedAdaptMemThresholdMB

A memory limit threshold for adaptively scheduling.

Definition at line 41 of file queueing.c.

struct prio_struct kprio_zero = { 0, 0, {0} } [static]

Definition at line 700 of file queueing.c.

struct prio_struct kprio_max = { 32, 1, {((unsigned int)(-1))} } [static]

Definition at line 701 of file queueing.c.

int numMemCriticalEntries = 0

Definition at line 899 of file queueing.c.

Referenced by _initCharm(), CkRegisterEp(), and CqsIncreasePriorityForMemCriticalEntries().

int* memCriticalEntries = NULL

Definition at line 900 of file queueing.c.

Referenced by _initCharm(), and CqsIncreasePriorityForMemCriticalEntries().

int schedAdaptMemThresholdMB

A memory limit threshold for adaptively scheduling.

Definition at line 41 of file queueing.c.

Generated on Fri May 25 08:00:56 2012 for Charm++ by  doxygen 1.5.5