The WS-Simulator is used to experimentally analyze different variants of Work Stealing. Thus, it should handle the different variants of Work Stealing Algorithm. Moreover, the simulator needs to manage the different types of application, the different topologies and all other variants.

WS-Simulator is designed to be sufficiently flexible in order to simulate different Work Stealing models. Its flexibility aims to allow us to experiment with different Work Stealing algorithms, different topologies, different steal strategies and different types of application. The simulator should also generate a sufficient amount of logs for a detailed analysis each tested scenario.

The overall architecture of WS-Simulator is composed of six main engines, as seen on Figure. The event engine is the core of our simulator, it manages the processors events during the time to run the simulation of a scenario. The events are executed through the processor engine which provides different functionalities to perform the Work Stealing algorithm. The processor engine uses the task engine to manage the execution of tasks and uses the topology engine to manage the interactions between the processors. During the execution of a simulation, the log engine keeps track ofdifferent information and generates different logs.

---

In the Work Stealing algorithm, a processor switches between different possible states : Each processor interacts when it becomes idle, when it receives a steal request or when it receives a steal answer. The global idea of our simulator consists in simulating a set of discrete events through time instead of simulating the whole execution time, where an event stands for changing the state of a processor at a specific time. For that:

Event engine

The event engine represents the kernel of the simulator. it lists the available events on a heap and executes them sequentially according to their time. The execution of events follows different steps to update the system and creates new events in the global heap, these events will be executed following the same mechanism. We define an event by its time, its related processors and its type. The execution of an event interacts on the related processors and orders it to update its state and creates other events. The execution time is defined by the last executed event.

Processor engine

The processor engine manages the processors state on the simulator, it offers all necessary functionalities to update aprocessor when a related event occurs. These functions apply the mechanism of Work Stealing algorithm. The processor engine uses topology engine to manage communications and interactions between the processors, The processor engine uses task engine to manage the execution of their tasks.

Topology engine

A topology defines the distribution of the processors on the platform and the communication characteristics between them. The topology engine is used for knowing the communication time between two processors during a steal operation. Moreover, since the victim selection strategy depends on the processor topology, the topology engine is also used to manage different victim selection strategies. The topology engine is also used to manage different parameters which are used by the Work Stealing algorithm during an execution, for example, is_simultaneous is used to determine if a processor can send work to several processors atthe same time. It also defines steal threshold parameters which can be static or depend on the communication time.

Task engine

The task engine is used to handle everything related to the application duringa simulation. It provides an operating interface which offers all the needed functionalities to manage tasks (create a new task during a simulation, split tasks during a steal request, generates the merge task if necessary, update the task dependencies, activate one or more tasks as in case of DAG task, ...) The task engine offers the mechanism to detect the end of an execution. It uses two global variables, one to compute the number of created tasks in the system, and the second to compute the number of completed tasks. The execution finishes when the created tasks are equal to the completed tasks. The task engine offers also different functions that automatically generate different application based on DAG tasks. It also offers a function to use a predefined application as input. For this, the predefined application must be described in JSON format.

Log engine

The simulator is used to experimentally analyze different models of Work Stealing algorithm. It should therefore generate sufficient results that simplify the analysis of the execution of a scenario. For this reason, the log engine isused to provide different functionalities to keep trace of different information during the execution. Several pieces of information are needed to analyze the execution of a scenario. For instance, we need the global execution information such as execution time and the number of steal requests. These results are presented in digital format. Other information are useful like the processes state over the whole execution or the final shape of the application executed. The log engine uses processor engine and task engine functionalities to keep track of simulation information. the overall results like (execution time, number of successful and failed steal requests, total workexecuted, etc...) are displayed in the console in digital format. Moreover, other logs need to be transformed into graphic format using standard trace analysis tools. The log are expained in details in this link : ws-simulator logs

---