Top Up Prev Next Bottom Contents Index Search

15.1 ParNode

This class represents a node in the APEG for parallel schedulers, thus contains additional members for parallel scheduling besides what are inherited from class EGNode. It has the same two-argument constructor as class EGNode.

ParNode(DataFlowStar* Mas, int invoc_no);
Initializes data members. If the argument star is at the wormhole boundary, we do not parallelize the invocations. Therefore, we create precedence relations between invocations by calling claimSticky of EGNode class in the constructor. If this constructor is called, the type protected member is set 0.

The ParNode class has another constructor with one argument.

ParNode(int type); 
The scheduling result is stored in UniProcessor class as a list of ParNodes. This constructor is to model idle time (type = 1), or communication time (type = -1 for sending time, type = -2 for receiving time) as a ParNode. It initializes data members.

15.1.1 ParNode protected members

int StaticLevel; 
Is set to the longest execution path to a termination node in the APEG. It defines the static level (or priority) of the node in Hu's scheduling algorithm. Initially it is set to 0.

int procId 
Is the processor index on which this ParNode is scheduled. Initially it is set to 0.

int scheduledTime; 
int finishTime;
Indicate when the node is scheduled and finished, respectively.

int exTime; 
Is the execution time of the node. If it is a regular node (type = 0), it is set to the execution time of the original DataFlowStar. Otherwise, it is set to 0.

int waitNum; 
Indicates the number of ancestors to be scheduled before scheduling this node. during the scheduling procedure. Initially it is set to 0. At a certain point of scheduling procedure, we can schedule a ParNode only when all ancestors are already assigned, or waitNum is 0.

EGNodeList tempAncs; 
EGNodeList tempDescs;
These list members are copies of the ancestors and descendants of the node. While EGGateLists, ancestors and descendants, may not be modified during scheduling procedure, these lists can be modified.

15.1.2 Other ParNode public members

void assignSL(int SL);
int getSL();
virtual int getLevel();
The first two methods set and get the StaticLevel member. The last one returns the priority of the node, which is just StaticLevel by default. In the derived classes, this method can be redefined, for example in Dynamic Level Scheduling, to return the dynamic level of the node.

int getType(); 
Returns the type of the node.

void setProcId(int i); 
int getProcId();
These two methods set and get the procId member.

void setScheduledTime(int i); 
int getScheduledTime();
void setFinishTime(int i);
int getFinishTime();
These methods are used to set or get the time when the node is scheduled first and finished.

void setExTime(int i); 
int getExTime();
These methods are used to set and get the execution time of the node.

void resetWaitNum(); 
void incWaitNum();
Resets the waitNum variable to the number of ancestors, and increases it by 1.

int fireable(); 
This method decreases waitNum by one, and return TRUE or FALSE, based on whether waitNum reaches zero or not. If it reaches 0, the node is declared "fireable".

void copyAncDesc(ParGraph* g, int flag); 
void removeDescs(ParNode* n);
void removeAncs(ParNode* n);
void connectedTo(ParNode* to);
The first method initializes the lists of temporary ancestors and descendants, tempAncs and tempDescs, from ancestors and descendants that are inherited members from EGNode class. List tempAncs is sorted smallest StaticLevel first while list tempDescs is sorted largest StaticLevel first. The first argument is necessary to call the sorting routine which is defined in the ParGraph class . By virtue of sorting, we can traverse descendant with larger StaticLevel first. If the second argument is not 0, we switch the lists: copy ancestors to tempDescs and descendants to tempAncs.

The second and the third methods remove the argument node from the temporary descendant list or from the temporary ancestor list. In the latter case, we decrease waitNum by one.

The last method above is to make a temporary connection between the node as the source and the argument node as the destination. The temporary descendant list of the current node is added the argument node while the temporary ancestor list of the argument node is added the current node (also increase waitNum of the argument node by 1).

CGStar* myStar(); 
Returns the original DataFlowStar after casting the type to CGStar, star class type of the CG domain.

int amIBig(); 
Returns TRUE or FALSE, based on whether myStar is a wormhole or not. Before the scheduling is performed in the top-level graph, the wormhole executes scheduling the inside galaxy and stores the scheduling results in the Profile object . The ParNode keeps the pointer to the Profile object if it is an invocation of the wormhole. In the general context, the node will be considered "Big" if the master star can be scheduled onto more than one processors. Then, the star is supposed to keep the Profile object to store the schedules on the processors. A wormhole is a special case of those masters.

void setOSOPflag(int i);
int isOSOP();
After scheduling is performed, we set a flag to indicate whether all invocations of a star are assigned to the same processor or not, using the first method. The second method queries the flag. Note that only the first invocation has the valid information.

void setCopyStar(DataFlowStar* s, ParNode* prevN);
DataFlowStar* getCopyStar();
ParNode* getNextNode();
ParNode* getFirstNode();
int numAssigned();
The above methods are used to create sub-universes . When we create a sub-universe, we make a copy of the master star if some invocations are assigned to the processor. Then, these invocations keep the pointer to the cloned star. Since all invocations may not be assigned to the same processor, we maintain the list of invocations assigned to the given processor. The first and second methods set and get the pointer to the cloned star. The first method also make a chain of the invocations assigned to the same processor. The third method returns the next invocation chained from the current node, while the fourth method returns the starting invocation of the chain. The last method returns the total number of invocations in the chain. It should be called at the starting invocation of the chain.

void setOrigin(EGGate* g);
EGGate* getOrigin();
void setPartner(ParNode* n);
ParNode* getPartner();
These methods manipulate the connection information of communication nodes. If two adjacent nodes in an APEG are assigned to two different processors, we insert communication nodes between them: Send and Receive nodes. As explained earlier, a communication node is created by one-argument constructor. The first two methods are related to which EGGate the communication node is connected. The last two methods concern the other communication node inserted.

15.1.3 Iterators for ParNode

There are two types of iterators associated with ParNode class: ParAncestorIter, ParDescendantIter. As their names suggest, ParAncestorIter class returns the ParNodes in the temporary ancestor list (tempAncs), and ParDescendantIter class returns the ParNodes in the temporary descendant list (tempDescs).

Top Up Prev Next Bottom Contents Index Search
Copyright © 1990-1997, University of California. All rights reserved.