Menu

Alea Simulator

Introduction

Newly proposed scheduling algorithms must be heavily tested and evaluated before they are applied in the real systems. Due to many reasons, such as the cost of resources, the reliability, the varying background load or the dynamic behavior of components, experimental evaluation cannot be mostly performed in the real systems. To obtain reliable results, many simulations with various setups must be performed using the same and controllable conditions that simulate different real life scenarios. This is often unreachable in the real Grid.

For this purpose many simulators have been developed. If properly designed, such simulators are very useful since different setups and different data sets can be used to evaluate existing or proposed solutions. While for some purposes an ad-hoc simulator is sufficient, there are also general Grid and cluster simulators allowing to simulate various scenarios and problems.

Alea Job Scheduling Simulator is an advanced job scheduling simulator which we have been developing since 2007.

Overview

Alea job scheduling simulator is an extension to the widely used GridSim simulation toolkit (http://www.buyya.com/gridsim/). It represents "ready to use" centralized scheduling system allowing to apply and compare various scheduling algorithms similar to those used in the production scheduling systems such as PBS Pro, TORQUE, LSF or CCS. The solution consists of the scheduler entity and other supporting classes which extend the original basic functionality of the GridSim. The main benefit of our solution is that the Alea allows immediate testing by inclusion of several popular and widely used scheduling algorithms such as FCFS, Earliest Deadline First, Shortest Job First, EASY Backfilling, Conservative Backfilling, Flexible Backfilling, etc. Beside the queue-based algorithms, it also enables the use of algorithms that construct the schedule (scheduling plan). Over the time, many core improvements have been done concerning the design, the scalability and the functionality. Also, several new scheduling algorithms and objective functions were included as well as the support of additional job and machine characteristics.

The Alea now also provides complex visualization tool which supports an export of simulation results into several bitmap formats. The simulation speed and the simulator's scalability have been significantly improved through the newly developed or redesigned classes. This covers a new memory-efficient job loader and a redesigned job allocation policy, which speeds up the whole simulation. Moreover, the support of standardized workloads formats has been included as well as the simulation of machine failures using the real life failure traces. All these features are closely discussed in the next section.

Simulator Design

The Alea extends existing GridSim classes and also offers brand new classes to provide a "ready to use" job scheduling simulator. It has been designed with respect to our needs concerning simulation capability. This involves the ability to perform complex simulations that involves realistic features of real systems. To be more precise, Alea is able to simulate sequential and parallel jobs, computational clusters, specific job requirements as well as system dynamics such as machine failures or users' activity. It also supports various optimization criteria including utilization, slowdown, response time, wait time and fairness related criteria such as normalized user wait time.

Same as the GridSim, the Alea is an event-based modular simulator, composed of independent entities which implements the desired simulation functionality (see Figure 1).

Figure 1. Main parts of the Alea simulator.

It consists of new centralized scheduler, the Grid resource(s) with the local job allocation policy, the job loader, the machine and failure loader and additional classes responsible for the simulation setup, the visualization and the generation of simulation output. By now, the Grid users are not directly simulated, but the job loader entity can be used as a parent class for the future implementation of the Grid user. As in GridSim, simulator's behavior is driven by the event-based message passing protocol. The simulator is fully compatible with the latest GridSim 5 release since no changes were made in the GridSim package itself. All extensions were made by implementing child classes which extend the standard GridSim (parent) classes. Similarly, easy extension of current functionality is possible thanks to the object oriented paradigm used by the GridSim and the Alea. In the following text all important extensions on top of the GridSim package are mentioned and explained.

The simulation is initialized by the ExperimentSetup class which creates instances of the scheduler, the job and machine loader, the failure loader and other entities as required by the standard GridSim.

The MachineLoader entity performs the initialization of the simulated computing environment. It reads the data describing the machines from a file and creates Grid resources accordingly. GridSim itself does not provide such functionality and machine parameters must be "hardcoded" in the source java file. Our solution allows to change machines' parameters without the re-compilation of the whole program. The JobLoader reads the file containing the job descriptions and creates jobs' instances dynamically over the time. The JobLoader supports several trace formats including the Grid Workloads Format (GWF) of the Grid Workloads Archive (http://gwa.ewi.tudelft.nl). and the Standard Workloads Format (SWF) of the Parallel Workloads Archive (http://www.cs.huji.ac.il/labs/parallel/workload/). When the simulation time is equal to the job submission time the JobLoader sends the job to the scheduler. The JobLoader reads only one job at a time to limit the required memory space, and to allow the use of very large workload traces. This approach is necessary since the original GridSim's Workload entity reads all data at once which - for large workloads - results in simulation fails due to the Java's Out-Of-Memory error.

The job itself is represented by the instance of the ComplexGridlet class. The GridSim provides only trivial implementation of a job in its Gridlet class. The ComplexGridlet extends this class, allowing to simulate more realistic scenarios where each job may require additional properties such as the deadline, the estimated runtime, the specific machine parameters, and other real life based constraints.

The FailureLoader reads the file containing descriptions of machine failures. Once the simulation time reaches the failure start time, the appropriate machine is set to be failed, killing all jobs being currently executed on that machine. When the failure period passes the machine is restarted. Machine failures can be used to simulate addition of a new machine or permanent machine removal.

As in the GridSim, the resource is represented by the GridResource instance and is managed by the local scheduling policy. Unfortunately none of the currently provided policies support the execution of parallel jobs and the simulation of machine failures at the same time. Also the co-allocation of several machines for job execution is not available. Therefore, new allocation policy called AdvancedSpaceShared was developed for the Alea based on the GridSim's SpaceShared policy. It allows to execute both sequential and parallel jobs on the specified number of CPUs using the space sharing processor allocation policy. It enables to simulate more realistic scenarios involving the parallel jobs as well as the simulations of machine failures. In addition, it includes more efficient implementation of the message passing which allows significant improvements in the simulation speed.

The newly developed Visualizator class generates the simulation's graphical output. The Gridsim itself enables visualizations displaying the process of allocating jobs onto the machines over time as can be seen in Figure 2.

Figure 2. Visualization of the job allocation procedure as provided by the GridSim.

The Visualizator extends this functionality by displaying additional information useful for tuning and debugging of scheduling algorithms. So far, several outputs covering different objectives are supported and displayed. Those are the overall utilization of resources, the cluster utilization, the number of waiting and running jobs and the number of requested, utilized and available CPUs. Beside that, also the percentage of failed and running CPUs per cluster can be displayed. The Visualizator may work in two different fashions. In the first case, the visualization is generated continuously as the simulation proceeds (see Figure 3).

Figure 3. Visualization interface of the Alea during the simulation.

In the second case, the graphs are generated when the simulation is finished, using the simulation results as an input. Results are continuously collected by the ResultCollector. When the simulation completes, the ResultCollector stores them into csv files that can be easily used as an input for other tools (Calc, Excel, Spreadsheet, etc.) and it also saves generated graphs into a preferred bitmap file (png, jpg, bmp, gif).

Scheduler Entity

The Scheduler is the main part of the Alea. Its behavior is driven by events and corresponding messages. Using the events, the Scheduler communicates with the JobLoader (job arrivals), with the GridResources (job submission/completion and failure detection) and with the ResultCollector (periodical result collection). Also the internal events are used to manage the scheduling process. The Scheduler is responsible for performing scheduling decisions according to the selected scheduling policy. It was designed as a modular, extensible entity composed of three main parts (see Figure 4) which are discussed in the following text.

Figure 4. Main parts of the Scheduler entity.

The first part stores dynamic information concerning the Grid resources (see Figure 4 bottom right). For each GridResource, one ResourceInfo object is created that holds up-to-date information regarding the current resource status. It stores information about jobs currently in execution, about jobs that are planned for execution (if the schedule is being constructed) and it implements various functions that help to compute or predict various values, e.g., the next free slot available for specific job, etc.

The second part is responsible for the communication with the remaining simulation entities (see Figure 4 top). It accepts incoming messages (events) and reacts accordingly. Typically, the Scheduler receives newly incoming job from the JobLoader. It takes the incoming job and places it into the queue or schedule according to the applied scheduling algorithm. Next, new scheduling round is performed and an attempt to submit jobs present in the queue or schedule is performed. If some resource is available and a suitable job is selected, it is submitted to the resource where it will be executed. Moreover, appropriate scheduler's ResourceInfo object is updated according to the new situation. Once some job is completed, it is returned to the Scheduler and the ResourceInfo object is updated as a result of the new state. Similar update is performed when some machine fails or restarts. Next, a new scheduling round is started. The cycle finishes when no new job arrivals appear and all submitted jobs have been completed. Then the simulation ends and the results are stored into the output files.

The last part of the Scheduler contains implementations of several popular and widely used scheduling algorithms. Since the recent research in the area of Grid and cluster scheduling focuses on both queue and schedule-based techniques we support both of them. Concerning the queue-based techniques following algorithms are implemented in the Scheduler entity: First Come First Served (FCFS), Earliest Deadline First (EDF), EASY Backfilling (EASY), Conservative Backfilling (CONS), Flexible Backfilling (Flex-BF), and a PBS-like (PBS) multi-queue and priority-based scheduling algorithm. Schedule-based techniques use a schedule - instead of a queue(s) - to store the jobs. In this case, each job is placed into the schedule upon its arrival which defines its expected start time, expected completion time and the target machine(s). The use of the schedule allows to use advanced scheduling and optimization algorithms such as the local search-based methods. These techniques are represented by the Best Gap - Earlier Deadline First (BG-EDF) and Best Gap (BG) policies and local search-based optimization routines Random Search (RS), Gap Search (GS) and Tabu Search (TS).

Several objective functions are supported which can be used for decision making or optimization. During the simulation, the Scheduler is capable of collecting various data such as the number of waiting and running jobs, current machine utilization, etc. Once the simulation is finished, output files containing these data are generated. Moreover, selected objectives can be used as an input for either the "on the fly" or the "post mortem" visualization provided by the Visualizator graphical tool.

Correctness of the Simulator

The correctness of the simulator was checked by analyzing the implementations of algorithms and simulation outputs. First, the implementations of scheduling algorithms were checked against their known pseudo-codes. Next, the simulation outputs of existing algorithms such as FCFS, EDF, EASY or Conservative Backfilling were compared with the known results from the literature. In case of Flexible Backfilling, both the implementation details and the simulation outputs were directly checked by the authors of this algorithm. Proposed policies and optimization algorithms were checked through several experiments where the expected behavior (algorithm's specification) was compared with the simulation trace and simulation outputs. Also the graphical simulation output played an important role when analyzing the implementation. When some anomaly was identified, the code was traced and analyzed using classical debugging techniques and the implementation was fixed accordingly.

More details can be found via the references in the next section.

Publications

• KLUSÁČEK, Dalibor a Šimon TÓTH a Gabriela PODOLNÍKOVÁ. Complex Job Scheduling Simulations with Alea 4. In Ninth EAI International Conference on Simulation Tools and Techniques, Prague, 2016.
• KLUSÁČEK, Dalibor a Hana RUDOVÁ. Alea 2 - Job Scheduling Simulator. In 3rd International Conference on Simulation Tools and Techniques. Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering (ICST), Brussels, 2010.
• KLUSÁČEK, Dalibor a Luděk MATYSKA a Hana RUDOVÁ. Alea - Grid Scheduling Simulation Environment. In Parallel Processing and Applied Mathematics. Springer, Lecture Notes in Computer Science 4967, pages 1029-1038, 2008.
• KLUSÁČEK, Dalibor a Hana RUDOVÁ. Efficient Data Representation of Large Job Schedules. In MEMICS 2011, Revised Selected Papers. Springer, Lecture Notes in Computer Science 7119, pages 103-113, 2011.
• KLUSÁČEK, Dalibor a Hana RUDOVÁ. Efficient Grid Scheduling through the Incremental Schedule-based Approach. Computational Intelligence, Wiley-Blackwell Publishing, Inc, 27(1), pages. 4-22, 2011.
• Alea - GridSim based Job Scheduling Simulator. Webpage: https://github.com/aleasimulator/alea
• KLUSÁČEK, Dalibor. ALEA 3 GridSim based Grid Scheduling Simulator. Webpage: http://www.fi.muni.cz/~xklusac/alea/