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 bool	checkAndRemoveMatching (void *&msgPtr, const int *entryMethod, const int numEntryMethods, envelope *env, void **&p)
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	CqsMaxLength (Queue q)
unsigned int	CqsLength (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:

• CsdScheduleForever() is the commonly used Converse scheduler loop
  • CsdNextMessage()
    • First processes converse message from a converse queue if one exists using CdsFifo_Dequeue()
    • Then if no converse message was found, call CqsDequeue() which gets a charm++ message to execute if one exists

---

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 140 of file modifyScheduler.C.

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

Referenced by CqsIncreasePriorityForEntryMethod(), and CqsIncreasePriorityForMemCriticalEntries().

Here is the call graph for this function:

Here is the caller graph for this function:

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 111 of file modifyScheduler.C.

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

Referenced by CqsIncreasePriorityForEntryMethod(), and CqsIncreasePriorityForMemCriticalEntries().

Here is the call graph for this function:

Here is the caller graph for this function:

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, traceUserSuppliedNote(), and Queue_struct::zeroprio.

Here is the call graph for this function:

void CqsIncreasePriorityForMemCriticalEntries

(

Queue

q

)

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

Definition at line 52 of file modifyScheduler.C.

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

Here is the call graph for this function:

static bool checkAndRemoveMatching	(	void *&	msgPtr,
		const int *	entryMethod,
		const int	numEntryMethods,
		envelope *	env,
		void **&	p
	)			[static]

Definition at line 78 of file modifyScheduler.C.

References ForArrayEltMsg, ForChareMsg, envelope::getMsgtype(), and envelope::getsetArrayEp().

Referenced by CqsFindRemoveSpecificDeq(), and CqsFindRemoveSpecificPrioq().

Here is the call graph for this function:

Here is the caller graph for this function:

static void CqsDeqInit

(

_deq

d

)

[static]

Initialize a deq.

Definition at line 51 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().

Here is the caller graph for this function:

static void CqsDeqExpand

(

_deq

d

)

[static]

Double the size of a deq.

Definition at line 60 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().

Here is the call graph for this function:

Here is the caller graph for this function:

void CqsDeqEnqueueFifo	(	_deq	d,
		void *	data
	)

Insert a data pointer at the tail of a deq.

Definition at line 78 of file queueing.C.

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

Here is the call graph for this function:

void CqsDeqEnqueueLifo	(	_deq	d,
		void *	data
	)

Insert a data pointer at the head of a deq.

Definition at line 89 of file queueing.C.

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

Here is the call graph for this function:

void* CqsDeqDequeue

(

_deq

d

)

Remove a data pointer from the head of a deq.

Definition at line 100 of file queueing.C.

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

Referenced by CqsPrioqDequeue().

Here is the caller graph for this function:

static void CqsPrioqInit

(

_prioq

pq

)

[static]

Initialize a Priority Queue.

Definition at line 116 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().

Here is the call graph for this function:

Here is the caller graph for this function:

static void CqsPrioqExpand

(

_prioq

pq

)

[inline, static]

Double the size of a Priority Queue's heap.

Definition at line 132 of file queueing.C.

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

Referenced by CqsPrioqGetDeq().

Here is the call graph for this function:

Here is the caller graph for this function:

void CqsPrioqRehash

(

_prioq

pq

)

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

Definition at line 145 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().

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 182 of file queueing.C.

Referenced by CldPutTokenPrio().

Here is the caller graph for this function:

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 204 of file queueing.C.

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

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

Here is the caller graph for this function:

_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 241 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, parent(), and prioqelt_struct::pri.

Here is the call graph for this function:

void* CqsPrioqDequeue

(

_prioq

pq

)

Dequeue an entry.

Definition at line 355 of file queueing.C.

References deq_struct::bgn, CmiFree(), CqsDeqDequeue(), CqsPrioGT(), prioqelt_struct::data, data, handle, 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.

Here is the call graph for this function:

Queue CqsCreate

(

void

)

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

Definition at line 551 of file queueing.C.

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

void CqsDelete

(

Queue

q

)

Delete a Queue.

Definition at line 566 of file queueing.C.

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

Referenced by CkObjectMsgQ::~CkObjectMsgQ().

Here is the call graph for this function:

Here is the caller graph for this function:

unsigned int CqsMaxLength

(

Queue

q

)

Definition at line 577 of file queueing.C.

References Queue_struct::maxlen, and Queue_struct::stlQ.

unsigned int CqsLength

(

Queue

q

)

Definition at line 588 of file queueing.C.

References Queue_struct::stlQ.

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

Here is the caller graph for this function:

int CqsEmpty

(

Queue

q

)

Definition at line 591 of file queueing.C.

References Queue_struct::stlQ.

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

Here is the caller graph for this function:

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 594 of file queueing.C.

References Queue_struct::stlQ.

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

Here is the caller graph for this function:

void CqsEnqueueFifo	(	Queue	q,
		void *	data
	)

Enqueue behind other elements of priority 0.

Definition at line 606 of file queueing.C.

References Queue_struct::stlQ.

void CqsEnqueueLifo	(	Queue	q,
		void *	data
	)

Enqueue ahead of other elements of priority 0.

Definition at line 609 of file queueing.C.

References Queue_struct::stlQ.

void CqsEnqueue	(	Queue	q,
		void *	data
	)

Enqueue with priority 0.

Definition at line 612 of file queueing.C.

References Queue_struct::stlQ.

Referenced by preProcessReceivedMessage().

Here is the caller graph for this function:

void CqsDequeue	(	Queue	q,
		void **	resp
	)

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

Definition at line 615 of file queueing.C.

References Queue_struct::stlQ.

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

Here is the caller graph for this function:

_prio CqsGetPriority

(

Queue

q

)

Get the priority of the highest priority message in q.

Definition at line 753 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().

Here is the caller graph for this function:

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 776 of file queueing.C.

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

Here is the call graph for this function:

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 812 of file queueing.C.

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

Here is the call graph for this function:

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 852 of file queueing.C.

References CmiAlloc(), conv::msgQ< P >::enumerate(), conv::msgQ< P >::size(), and Queue_struct::stlQ.

Here is the call graph for this function:

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 899 of file queueing.C.

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

Referenced by CqsRemoveSpecific().

Here is the caller graph for this function:

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 927 of file queueing.C.

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

Referenced by CqsRemoveSpecific().

Here is the caller graph for this function:

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 951 of file queueing.C.

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

Here is the call graph for this function:

---

Variable Documentation

int schedAdaptMemThresholdMB

A memory limit threshold for adaptively scheduling.

Definition at line 47 of file queueing.C.

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

Definition at line 750 of file queueing.C.

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

Definition at line 751 of file queueing.C.

int numMemCriticalEntries = 0

Definition at line 962 of file queueing.C.

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

int* memCriticalEntries = NULL

Definition at line 963 of file queueing.C.

Referenced by _initCharm(), and CqsIncreasePriorityForMemCriticalEntries().

int schedAdaptMemThresholdMB

A memory limit threshold for adaptively scheduling.

Definition at line 47 of file queueing.C.