"> Implementation -- Simulation Overhead Subsystem

Implementation--
Simulation Overhead Subsystem

The simulator does the actual simulation of execution of the test programs. The simulator runs in a series of cycles. First, the simulator chooses a node from the terminal node list using the search algorithm chosen by the user. The simulator, then, gives the location of the chosen node to the search tree for processing.

The simulator goes through all the programs in the program list. If the program has already terminated normally, the simulator passes it by. Otherwise, the search tree builds a child node for each slice that can be traversed from the current program counter position in the program. The simulator finds all the flow control transfers in the program's flow control list that begin at the current program counter position and evaluates the condition under which that transfer may occur using the boolean expression parser/evaluator. If the condition evaluates to FALSE, the transfer is passed.

If the flow control transfer's condition evaluates to TRUE, the search tree creates a new child node to represent the transfer. The program counter position is adjusted to the end of the control transfer. The simulator checks the program's slice list for the slice that begins at the new program counter position. When the appropriate slice is found, the program counter is again adjusted to the end of the slice.

The simulator collects the data to go into the new child node. First, the current state of the existing parent node is copied to the child with the new program counter value inserted. The simulator then makes the variable changes indicated by the slice. The expessions in the variable change list of the slice are evaluated using either the arithmetic or boolean parser/evaluator and the value changes are made in the new child node's current state. The current and goal values of each variable in the Goal List are collected and placed in the List of Changes to the Goal. The Heuristic Value is calculated by summing the differences between the current and goal values for each entry in the List of Changes to the Goal. Finally, the List of Goals Achieved is made by listing all those variables in the List of Changes to the Goal for which the current and goal values are equal.

After the new child node's data has been collected, the simulator makes some checks of the new current state aganst the current state in a couple of groupings of nodes in the tree. Each ancestor node in the tree branch of the selected node is checked for a matching current state. If one is found then the new node shows an entry into an infinite loop and does not need to be expanded farther down. Next, each node referenced on the terminal node list is checked. If a matching node is found, the new node represents the beginning of an identical parallel execution path and does not need to be expanded any farther because its subtree will be covered by the existing node. One last check identifies if there is at least one test program still running. If not, the node cannot be expanded any further.

Any new child nodes found to be expandable are added to the search tree as child nodes of the selected node. Others are deleted. When all processing for the selected node is complete, if the selected node generated no child nodes, the branch is pruned to the next decision point up along the branch. If, on the other hand, one of the new child nodes has a heuristic value of zero, the node's position is returned to the top level for printing. Otherwise, the simulator selects another node for processing.

This cycle continues until the goal state is found, the entire tree has been pruned back to the root node or the simulator uses up all the available memory causing abnormal termination of SimPlan. One of four results is possible. The simulator can find the goal, in which case a result path is printed. SimPlan can terminate normally without finding the goal, in which case a message to that result is printed. SimPlan can terminate abnormally, in which case the simulation got caught in an undetectable infinite loop or there was not enough memory available to complete the simulation. Finally, SimPlan does not terminate at all, in which case the user is usually not letting the simulation run long enough.

Figure of simulator main loop processing

Figure of child node generation loop

Figure of individual child node generation process

Related include files:

Return ...

Andrew Tompkins
Beaverton, OR 97006
Last rev: 17 JUL 03
URL:
http://home.comcast.net/~andytom/simplan.docs/control/simulate.html

Valid XHTML 1.0!