E-Cell 4 Top-level Scheduling

This describes the top-level scheduler loop of E-Cell System 4. The top level scheduler schedules execution of step() method of Stepper objects. Stepper class implements a simulation algorithm in conventional terminology. We need this top-level scheduling of Steppers because since E-Cell 3, one of our aims has been to allow multi-algorithm simulation, in which multiple simulator components, each implementing a specific simulation method, run concurrently while these collectively comprise the entire composite model.

Data structure

class Scheduler:

    def pop()

    def push()


class Stepper:

    def __init__():
        self.dt

    def dependsOn( self, stepper ):
        return true if this stepper can read the given stepper's variable(s)

    def step( self ):

        executeSimulationStep()

        dispatchInterruptions()

Sequential

Single thread scheduling.

Equivalent to E-Cell 3.

Pseudo code:

while 1:
    event = scheduler.pop()

    event.stepper.step()

    newEvent = stepper.t + stepper.dt, stepper
    scheduler.push(newEvent)

    if checkTerminationCondition():
        break

Parallel, all deterministic

Multi-thread scheduling. Dependencies between all combinations of Steppers are pre-determined and don't change during simulation.

Equivalent to E-Cell3 multi-thread version (Arjunan, ICSB 2003).

Pseudo code:

threads = []

while 1:

    topEvent = scheduler.top()
    if [ topEvent.stepper.dependsOn( s ) and s.dependsOn( topEvent.stepper )
         for s in threadPool ].allFalse() and
      threads.size < MAX_THREADS:
        scheduler.pop()
        threads.push(thread(topEvent.stepper.step))
    else:
        # wait for one thread to finish.
        joined = False
        while 1:
            for thread in threads:
                if thread.joinable():
                    thread.join()
                    joined = True
                    break
            if joined:
                break

    if checkTerminationCondition():
        join_all_threads()
        break

NOTE: In the code above, I did not explicitly write creation/finalization and synchronization of threads to avoid complexity. Suppose that stepperQueue automatically dispatch a thread and run stepper.step() when a stepper is given, and a stepper item is automatically removed when execution of the step() method is finished and the thread merges.

No dynamic scheduling

Dynamic here means that dependencies between Steppers can change during simulation and it is unpredictable. However, we do not consider this case for E-Cell 4 top-level scheduling.