DET Traversal Strategies

ADS-IDAC explores a Dynamic Event Tree (DET) by running one scenario at a time from root to terminal. At each branching point (crew decisions, hardware failures), alternative branches are generated and placed in a queue. The order in which queued branches are processed defines the traversal strategy.

LIFODepth-First (Stack)

 

FIFOBreadth-First (Queue)

 

MPIParallel (3 Ranks)

R1R2R3

LIFO: Depth-First (Stack)

Last In, First Out. The most recently generated branch is explored next.

This produces a depth-first traversal: the engine dives to the deepest terminal, backtracks one level, explores the sibling, backtracks again, and so on. In the tree above, the top half completes entirely before the bottom half begins.

• Minimal memory: only one path's worth of restart data needed at a time
• Sequences share recent restart data (fewer I/O operations)
• The engine does not use this order; it is shown for comparison

FIFO: Breadth-First (Queue)

First In, First Out. The oldest generated branch is explored next.

This produces a breadth-first traversal: all branches at a given depth are explored before going deeper. In the tree above, the engine alternates between the top and bottom halves.

• Higher memory: all pending branches must be stored simultaneously
• Better for finding diverse scenarios quickly
• Explores the shallowest (earliest) branching decisions first
• This is the order of the serial engine: AdsidacCallback::restartForNewSequence() scans the branch points from the oldest and restarts from the first one that still has an unexplored branch

MPI Parallel (Multiple Ranks)

With MPI, rank 0 acts as a server dispatching branches from a FIFO queue to idle client ranks. Multiple scenarios run simultaneously on different ranks.

• Rank 0 dispatches tasks and tracks the tree structure
• Client ranks execute RELAP5 scenarios independently
• Restart data transfers happen peer-to-peer between clients (server never stores restart buffers)
• A child branch can start as soon as its parent has passed the branching point and a worker is free; the parent does not have to finish first
• Speedup depends on tree shape: deeper sequential dependencies limit parallelism

See Running ADS-IDAC for MPI usage and Developer Internals for the implementation.

Key Takeaway

All three strategies explore the same tree and produce identical results: the same 7 end states. The difference is the order and speed at which they are discovered. Watch the sequence numbers (#1 to #7) appear at the terminals in different orders as the animation plays.