Claims:1. A method for optimizing scheduling of batch workloads to minimize makespan, the method comprising:
identifying, by one or more hardware processors, one or more batch workloads comprising a first set of batch jobs and a second set of batch jobs, wherein the first set of batch jobs and the second set of batch jobs are represented as a Directed Acyclic Graph (DAG), wherein the first set of batch jobs comprise a plurality of newly arriving jobs to be scheduled on one or more servers, and wherein the second set of batch jobs comprise a plurality of active jobs on the one or more servers (301);
characterizing, via the one or more hardware processors, the first set of batch jobs and the second set of batch jobs, wherein the characterizing comprises (302):
determining a distinct service demand and a memory bandwidth requirement of each thread in each of the first set of batch jobs and the second set of batch jobs; and
deriving an instantaneous utilization of a Central Processing Unit (CPU) of each of the first set of batch jobs and the second set of batch jobs;
simulating, on the one or more servers, a completion time of each of the characterized first set of batch jobs and each of the characterized second set of batch jobs, by individually executing each of the characterized first set of batch jobs concurrently with the characterized second set of batch jobs in a simulation environment, wherein the simulation is performed by implementing one or more simulation based techniques (303); and
optimizing, based upon the simulated completion time of each the first set of batch jobs and each of the second set of batch jobs, scheduling of the one or more batch workloads, wherein the optimizing comprises an optimal mapping of each of the first set of batch jobs on an appropriate server amongst the one or more servers, and wherein the appropriate server is identified based upon a first simulation and a second simulation (304).

2. The method as claimed in claim 1, wherein the step of simulating comprises:
(i) performing, by implementing a Least Execution Time (LET) technique, the first simulation on each of the first set of batch jobs individually, wherein the first simulation is performed when at least one of the first set of batch jobs is executing concurrently with the second set of batch jobs on the one or more servers;
(ii) performing, by implementing a Minimum of Maximum (MOM) technique, the second simulation on each of the first set of batch jobs individually, wherein the second simulation is performed when at least one of the first set of batch jobs is executing concurrently with the second set of batch jobs on the one or more servers; and
(iii) computing, by implementing a Smallest Load First (SLF) technique, a minimum load on the one or more servers.

3. The method as claimed in claim 2, wherein the LET technique and the MOM technique facilitates extracting, from the one or more servers, a current state of the second set of batch jobs executing on the one or more servers for performing the first simulation and the second simulation.

4. The method as claimed in claim 2, wherein the first simulation comprises simulating, via the LET technique, a least execution time of each of the first set of batch jobs individually on the one or more servers.

5. The method as claimed in claim 2, wherein the second simulation comprises simulating, via the MOM technique, a minimum impact of each of the first set of batch jobs on execution time of the second set of batch jobs, and wherein the minimum impact is simulated by executing each of the first set of batch jobs individually with the second set of batch jobs on the one or more servers.

6. The method as claimed in claim 5, wherein the second simulation is performed iteratively until the minimum impact of each of the first set of batch jobs on the execution time of the second set of batch jobs is simulated on the one or more servers.

7. The method as claimed in claim 4, wherein the first simulation is performed iteratively until the least execution of each of the first set of batch jobs is simulated by executing each of the first set of batch jobs individually the second set of batch jobs on the one or more servers.

8. The method as claimed in claim 1, wherein the step of optimizing facilitates minimizing a makespan of the one or more batch workloads.

9. The method as claimed in claim 8, wherein minimizing the makespan facilitates a minimum runtime of overall execution of the one or more batch workloads on the one or more servers using a job scheduler.

10. A system (100) for optimizing scheduling of batch workloads to minimize makespan, the system (100) comprising:
a memory (102) storing instructions;
one or more communication interfaces (106); and
one or more hardware processors (104) coupled to the memory (102) via the one or more communication interfaces (106), wherein the one or more hardware processors (104) are configured by the instructions to:
identify one or more batch workloads comprising a first set of batch jobs and a second set of batch jobs, wherein the first set of batch jobs and the second set of batch jobs are represented as a Directed Acyclic Graph (DAG), wherein the first set of batch jobs comprise a plurality of newly arriving jobs to be scheduled on one or more servers, and wherein the second set of batch jobs comprise a plurality of active jobs on the one or more servers;
characterize the first set of batch jobs and the second set of batch jobs, wherein the characterizing comprises:
determining a distinct service demand and a memory bandwidth requirement of each thread in each of the first set of batch jobs and the second set of batch jobs; and
deriving an instantaneous utilization of a Central Processing Unit (CPU) of each of the first set of batch jobs and the second set of batch jobs;
simulate, on the one or more servers, a completion time of each of the characterized first set of batch jobs and each of the characterized second set of batch jobs, by individually executing each of the characterized first set of batch jobs concurrently with the characterized second set of batch jobs in a simulation environment, wherein the simulation is performed by implementing one or more simulation based techniques; and
optimize, based upon the simulated completion time of each the first set of batch jobs and each of the second set of batch jobs, scheduling of the one or more batch workloads, wherein the optimizing comprises an optimal mapping of each of the first set of batch jobs on an appropriate server amongst the one or more servers, and wherein the appropriate server is identified based upon a first simulation and a second simulation.

11. The system as claimed in claim 10, wherein the step of simulating comprises:
(i) performing, by implementing a Least Execution Time (LET) technique, the first simulation on each of the first set of batch jobs individually, wherein the first simulation is performed when at least one of the first set of batch jobs is executing concurrently with the second set of batch jobs on the one or more servers;
(ii) performing, by implementing a Minimum of Maximum (MOM) technique, the second simulation on each of the first set of batch jobs individually, wherein the second simulation is performed when at least one of the first set of batch jobs is executing concurrently with the second set of batch jobs on the one or more servers; and
(iii) computing, by implementing a Smallest Load First (SLF) technique, a minimum load on the one or more servers.

12. The system (100) as claimed in claim 11, wherein the LET technique and the MOM technique facilitates extracting, from the one or more servers, a current state of the second set of batch jobs executing on the one or more servers for performing the first simulation and the second simulation.

13. The system (100) as claimed in claim 11, wherein the one or more hardware processors (104) are configured to perform the first simulation by simulating, via the LET technique, a least execution time of each of the first set of batch jobs individually on the one or more servers.

14. The system (100) as claimed in claim 11, wherein the one or more hardware processors (104) are configured to perform the second simulation by simulating, via the MOM technique, a minimum impact of each of the first set of batch jobs on execution time of the second set of batch jobs, and wherein the minimum impact is simulated by executing each of the first set of batch jobs individually with the second set of batch jobs on the one or more servers.

15. The system (100) as claimed in claim 14, wherein the one or more hardware processors (104) are configured to perform the second simulation iteratively until the minimum impact of each of the first set of batch jobs on the execution time of the second set of batch jobs is simulated on the one or more servers.

16. The system (100) as claimed in claim 13, wherein the one or more hardware processors (104) are configured to the first simulation iteratively until the least execution of each of the first set of batch jobs is simulated by executing each of the first set of batch jobs individually the second set of batch jobs on the one or more servers.

17. The system (100) as claimed in claim 10, wherein the step of optimizing facilitates minimizing a makespan of the one or more batch workloads.

18. The system (100) as claimed in claim 17, wherein minimizing the makespan facilitates a minimum runtime of overall execution of the one or more batch workloads on the one or more servers using a job scheduler.
, Description:FORM 2

THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003

COMPLETE SPECIFICATION
(See Section 10 and Rule 13)

Title of invention:

SYSTEMS AND METHODS FOR OPTIMIZING SCHEDULING OF BATCH WORKLOADS TO MINIMIZE MAKESPAN

Applicant

Tata Consultancy Services Limited
A company Incorporated in India under the Companies Act, 1956
Having address:
Nirmal Building, 9th floor,
Nariman point, Mumbai 400021,
Maharashtra, India

The following specification particularly describes the invention and the manner in which it is to be performed.


TECHNICAL FIELD
The disclosure herein generally relates to batch scheduling, and, more particularly, to systems and methods for optimizing scheduling of batch workloads to minimize makespan.

BACKGROUND
Complex applications in many research domains such as bioinformatics, earth science, astronomy, physics, and the like are represented as workflows. Jobs in these workflows are generally coupled through control or data dependencies such that execution of a job may start only after the execution of one or more other jobs. Moreover, these jobs are compute intensive or memory intensive and require high performance computing servers. Distributed environment comprising of high-performance servers with large number of cores, high memory bandwidth and high speed inter-connects are used for execution of such workflows. A job scheduler is used to manage the resources available in such distributed environment and schedule jobs on these resources. However, on shared-memory multiprocessor platforms, interconnects between main memory and processors become bottlenecks. Moreover, different jobs have different resource requirements and availability of these resources keeps changing as jobs that are part of the workflow arrive and exit.
Most job schedulers are either load aware or consider contention on only one of the resources such as CPU, IO or network. These job schedulers are not optimal for clusters where resource requirement vary from job to job. For example, co-scheduling multiple CPU and memory bandwidth intensive jobs can result in contention for CPU and memory bandwidth and need to be scheduled using multiple resource aware scheduler.

SUMMARY
Embodiments of the present disclosure present technological improvements as solutions to one or more of the above-mentioned technical problems recognized by the inventors in conventional systems. For example, in one embodiment, a method for optimizing scheduling of batch workloads to minimize makespan, the method comprising: identifying, by one or more hardware processors, one or more batch workloads comprising a first set of batch jobs and a second set of batch jobs, wherein the first set of batch jobs and the second set of batch jobs are represented as a Directed Acyclic Graph (DAG), wherein the first set of batch jobs comprise a plurality of newly arriving jobs to be scheduled on one or more servers, and wherein the second set of batch jobs comprise a plurality of active jobs on the one or more servers; characterizing, via the one or more hardware processors, the first set of batch jobs and the second set of batch jobs, wherein the characterizing comprises: determining a distinct service demand and a memory bandwidth requirement of each thread in each of the first set of batch jobs and the second set of batch jobs; and deriving an instantaneous utilization of a Central Processing Unit (CPU) of each of the first set of batch jobs and the second set of batch jobs; simulating, on the one or more servers, a completion time of each of the characterized first set of batch jobs and each of the characterized second set of batch jobs, by individually executing each of the characterized first set of batch jobs concurrently with the characterized second set of batch jobs in a simulation environment, wherein the simulation is performed by implementing one or more simulation based techniques; optimizing, based upon the simulated completion time of each the first set of batch jobs and each of the second set of batch jobs, scheduling of the one or more batch workloads, wherein the optimizing comprises an optimal mapping of each of the first set of batch jobs on an appropriate server amongst the one or more servers, and wherein the appropriate server is identified based upon a first simulation and a second simulation; performing, by implementing a Least Execution Time (LET) technique, the first simulation on each of the first set of batch jobs individually, wherein the first simulation is performed when at least one of the first set of batch jobs is executing concurrently with the second set of batch jobs on the one or more servers; performing, by implementing a Minimum of Maximum (MOM) technique, the second simulation on each of the first set of batch jobs individually, wherein the second simulation is performed when at least one of the first set of batch jobs is executing concurrently with the second set of batch jobs on the one or more servers; computing, by implementing a Smallest Load First (SLF) technique, a minimum load on the one or more servers; extracting, from the one or more servers, a current state of the second set of batch jobs executing on the one or more servers for performing the first simulation and the second simulation; simulating, via the LET technique, a least execution time of each of the first set of batch jobs individually on the one or more servers; simulating, via the MOM technique, a minimum impact of each of the first set of batch jobs on execution time of the second set of batch jobs, and wherein the minimum impact is simulated by executing each of the first set of batch jobs individually with the second set of batch jobs on the one or more servers; and minimizing the makespan to minimize runtime of overall execution of the one or more batch workloads on the one or more servers using a job scheduler.
In another aspect, there is provided a system for optimizing scheduling of batch workloads to minimize makespan, the system comprising a memory storing instructions; one or more communication interfaces; and one or more hardware processors coupled to the memory via the one or more communication interfaces, wherein the one or more hardware processors are configured by the instructions to: identify one or more batch workloads comprising a first set of batch jobs and a second set of batch jobs, wherein the first set of batch jobs and the second set of batch jobs are represented as a Directed Acyclic Graph (DAG), wherein the first set of batch jobs comprise a plurality of newly arriving jobs to be scheduled on one or more servers, and wherein the second set of batch jobs comprise a plurality of active jobs on the one or more servers; characterize the first set of batch jobs and the second set of batch jobs, wherein the characterizing comprises: determining a distinct service demand and a memory bandwidth requirement of each thread in each of the first set of batch jobs and the second set of batch jobs; and deriving an instantaneous utilization of a Central Processing Unit (CPU) of each of the first set of batch jobs and the second set of batch jobs; simulate, on the one or more servers, a completion time of each of the characterized first set of batch jobs and each of the characterized second set of batch jobs, by individually executing each of the characterized first set of batch jobs concurrently with the characterized second set of batch jobs in a simulation environment, wherein the simulation is performed by implementing one or more simulation based techniques; optimize, based upon the simulated completion time of each the first set of batch jobs and each of the second set of batch jobs, scheduling of the one or more batch workloads, wherein the optimizing comprises an optimal mapping of each of the first set of batch jobs on an appropriate server amongst the one or more servers, and wherein the appropriate server is identified based upon a first simulation and a second simulation; performing, by implementing a Least Execution Time (LET) technique, the first simulation on each of the first set of batch jobs individually, wherein the first simulation is performed when at least one of the first set of batch jobs is executing concurrently with the second set of batch jobs on the one or more servers; performing, by implementing a Minimum of Maximum (MOM) technique, the second simulation on each of the first set of batch jobs individually, wherein the second simulation is performed when at least one of the first set of batch jobs is executing concurrently with the second set of batch jobs on the one or more servers; and computing, by implementing a Smallest Load First (SLF) technique, a minimum load on the one or more servers; extracting, from the one or more servers, a current state of the second set of batch jobs executing on the one or more servers for performing the first simulation and the second simulation; perform the first simulation by simulating, via the LET technique, a least execution time of each of the first set of batch jobs individually on the one or more servers; perform the second simulation by simulating, via the MOM technique, a minimum impact of each of the first set of batch jobs on execution time of the second set of batch jobs, and wherein the minimum impact is simulated by executing each of the first set of batch jobs individually with the second set of batch jobs on the one or more servers; and minimizing the makespan facilitates a minimum runtime of overall execution of the one or more batch workloads on the one or more servers using a job scheduler.
In yet another aspect, there is provided one or more non-transitory machine readable information storage mediums comprising one or more instructions which when executed by one or more hardware processors causes the one or more hardware processors to perform a method for optimizing scheduling of batch workloads to minimize makespan, the method comprising: identifying one or more batch workloads comprising a first set of batch jobs and a second set of batch jobs, wherein the first set of batch jobs and the second set of batch jobs are represented as a Directed Acyclic Graph (DAG), wherein the first set of batch jobs comprise a plurality of newly arriving jobs to be scheduled on one or more servers, and wherein the second set of batch jobs comprise a plurality of active jobs on the one or more servers; characterizing the first set of batch jobs and the second set of batch jobs, wherein the characterizing comprises: determining a distinct service demand and a memory bandwidth requirement of each thread in each of the first set of batch jobs and the second set of batch jobs; and deriving an instantaneous utilization of a Central Processing Unit (CPU) of each of the first set of batch jobs and the second set of batch jobs; simulating, on the one or more servers, a completion time of each of the characterized first set of batch jobs and each of the characterized second set of batch jobs, by individually executing each of the characterized first set of batch jobs concurrently with the characterized second set of batch jobs in a simulation environment, wherein the simulation is performed by implementing one or more simulation based techniques; optimizing, based upon the simulated completion time of each the first set of batch jobs and each of the second set of batch jobs, scheduling of the one or more batch workloads, wherein the optimizing comprises an optimal mapping of each of the first set of batch jobs on an appropriate server amongst the one or more servers, and wherein the appropriate server is identified based upon a first simulation and a second simulation; performing, by implementing a Least Execution Time (LET) technique, the first simulation on each of the first set of batch jobs individually, wherein the first simulation is performed when at least one of the first set of batch jobs is executing concurrently with the second set of batch jobs on the one or more servers; performing, by implementing a Minimum of Maximum (MOM) technique, the second simulation on each of the first set of batch jobs individually, wherein the second simulation is performed when at least one of the first set of batch jobs is executing concurrently with the second set of batch jobs on the one or more servers; computing, by implementing a Smallest Load First (SLF) technique, a minimum load on the one or more servers; extracting, from the one or more servers, a current state of the second set of batch jobs executing on the one or more servers for performing the first simulation and the second simulation; simulating, via the LET technique, a least execution time of each of the first set of batch jobs individually on the one or more servers; simulating, via the MOM technique, a minimum impact of each of the first set of batch jobs on execution time of the second set of batch jobs, and wherein the minimum impact is simulated by executing each of the first set of batch jobs individually with the second set of batch jobs on the one or more servers; and minimizing the makespan to minimize runtime of overall execution of the one or more batch workloads on the one or more servers using a job scheduler.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed.

BRIEF DESCRIPTION OF THE DRAWINGS
The accompanying drawings, which are incorporated in and constitute a part of this disclosure, illustrate exemplary embodiments and, together with the description, serve to explain the disclosed principles.
FIG. 1 illustrates block diagram of a system for optimizing scheduling of batch workloads to minimize makespan, in accordance with some embodiments of the present disclosure.
FIG. 2 is an architectural diagram depicting components and flow of the system for optimizing the scheduling of batch workloads to minimize the makespan, in accordance with some embodiments of the present disclosure.
FIG. 3 is a flow diagram illustrating the steps involved in the process of optimizing the scheduling of batch workloads to minimize the makespan, in accordance with some embodiments of the present disclosure.
FIG. 4A illustrates graphically a comparison of a makespan observed by implementing a Least Execution Technique (LET technique), a Minimum of Maximum (MOM) technique, and a Smallest Load First (SLF) technique) on a Directed Acyclic Graph (DAG) of 50 bath jobs, via a simulator, in accordance with some embodiments of the present disclosure.
FIG. 4B illustrates graphically the comparison of the makespan observed by implementing the LET technique, the MOM technique, and the SLF technique on a DAG of 100 bath jobs, via the simulator, in accordance with some embodiments of the present disclosure.
FIG. 5A through 5B illustrates graphically a comparison of the makespan obtained by implementing a batch job onto server mapping of simulations using a real job scheduler, in accordance with some embodiments of the present disclosure.
FIG. 6A through 6C illustrates graphically a comparison of an expected execution time of individual jobs of DAG-2, using the SLF technique, the LET technique and the MOM technique on a cluster of 3 servers, in accordance with some embodiments of the present disclosure.

DETAILED DESCRIPTION OF EMBODIMENTS
Exemplary embodiments are described with reference to the accompanying drawings. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. Wherever convenient, the same reference numbers are used throughout the drawings to refer to the same or like parts. While examples and features of disclosed principles are described herein, modifications, adaptations, and other implementations are possible without departing from the spirit and scope of the disclosed embodiments. It is intended that the following detailed description be considered as exemplary only, with the true scope and spirit being indicated by the following claims.
Embodiments of the present disclosure provide systems and methods for optimizing scheduling of batch workloads to minimize makespan. Batch processing constitutes a big portion of complex and large data processing in many organizations. For example, banks generate reports at the end of the day using the batch processing and financial institutions run computationally intensive workloads to model stock performance. Batch jobs may be multi-threaded and threads can have distinct CPU requirements.
Even batch jobs with high Input / Output (IO) requests saturate the CPU due to over subscription, that is, if one job or a thread is waiting for the IO, the CPU will be used by other jobs or threads. Although batch jobs are generally scheduled to run during off business hours, known as a batch window, but the batch jobs may over run long enough in the presence of other batch jobs and thus impact the critical transactions during business hours. Hence, it is very important to estimate the completion time of a job a priori in the presence of other batch jobs.
The problem of job scheduling comprises allocating the available resources such as cores and memory to the jobs and establish an optimal order of their execution by mapping jobs onto the most suitable server. In such a scenario, processor and memory bandwidth aware job scheduling can result in improved performance. Scheduling jobs in a distributed environment is a complex problem even in case of two identical servers. Use of meta-heuristic techniques is the most suitable option to solve job scheduling problems.
Traditional systems and methods implementing such meta-heuristic techniques face numerous challenges in real-world situations where manual tuning of parameters is difficult or where the execution time is small. In such situations, pure heuristics techniques may provide better solutions. However, with the advent of new architectures having large number of cores and high memory bandwidth, there is a need to study the simulation based methods to address the challenges posed by such servers and the complex workloads that run on them. The traditional systems and methods thus face major challenges where workflow can be presented as a direct acyclic graph and there are dependencies among jobs, there are more than one server on which jobs can be scheduled, and multiple jobs may run concurrently on server and there is contention for CPU and memory bandwidth.
The method disclosed attempts to overcome the limitations / challenges faced by the traditional systems and methods. For example, the method disclosed provides for two simulation based job scheduling techniques to minimize the makespan of an application workflow, and cites using CPU and memory bandwidth contention models for batch workflows.
Referring now to the drawings, and more particularly to FIG. 1 through 6C, where similar reference characters denote corresponding features consistently throughout the figures, there are shown preferred embodiments and these embodiments are described in the context of the following exemplary system and/or method.
FIG. 1 illustrates an exemplary block diagram of a system 100 for optimizing scheduling of batch workloads to minimize makespan, in accordance with an embodiment of the present disclosure. In an embodiment, the system 100 includes one or more processors 104, communication interface device(s) or input/output (I/O) interface(s) 106, and one or more data storage devices or memory 102 operatively coupled to the one or more processors 104. The one or more processors 104 that are hardware processors can be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the processor(s) is configured to fetch and execute computer-readable instructions stored in the memory 102. In an embodiment, the system 100 can be implemented in a variety of computing systems, such as laptop computers, notebooks, hand-held devices, workstations, mainframe computers, servers, a network cloud and the like.
The I/O interface device(s) 106 can include a variety of software and hardware interfaces, for example, a web interface, a graphical user interface, and the like and can facilitate multiple communications within a wide variety of networks N/W and protocol types, including wired networks, for example, LAN, cable, etc., and wireless networks, such as WLAN, cellular, or satellite. In an embodiment, the I/O interface device(s) can include one or more ports for connecting a number of devices to one another or to another server.
The memory 102 may include any computer-readable medium known in the art including, for example, volatile memory, such as static random access memory (SRAM) and dynamic random access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes. In an embodiment, the memory 102 can be configured to store any data that is associated with optimizing the scheduling of batch workloads to minimize the makespan. In an embodiment, the information pertaining to any Directed Acyclic Graph (DAG), characterization of batch jobs, simulation and optimizing of simulated batch jobs is stored in the memory 102. Further, all information (inputs, outputs and so on) pertaining to optimizing he scheduling of batch workloads to minimize the makespan, may also be stored in the database, as history data, for reference purpose.
According to an embodiment of the present disclosure, by referring to FIG. 2, the architecture and flow of the system 100 for optimizing the scheduling of batch workloads to minimize the makespan may be considered in detail. By referring to FIG. 2 again, it may be noted that initially, each batch job is characterized in isolation. Job characterization data, the number of available servers and (Directed-Acyclic-Graph) DAG are then given as input to a simulator. The master instance of simulator starts the execution of the workflow from the root node in the DAG.
Upon completion of the job, all successor jobs that are eligible for the execution are derived from the DAG. The execution of each new job is simulated by another instance of simulator called the worker, using contention models, current state of the servers and the status of currently active jobs on these servers. The worker simulator uses the one or more simulation based techniques to find most suitable server for mapping each of the new jobs and returns the job mapping information to the master simulator. Master simulator maps the new job to the server and updates the status of the server.
The simulation process starts from the root job in the DAG and continues till all the jobs and their successors in the DAG are simulated. At the completion of DAG simulation, an execution schedule with job onto the server mapping is generated by the master simulator. The job onto the server mapping generated by the simulator can now be given to a job scheduler (also hereinafter referred to as a real job scheduler) for execution on physical servers.
FIG. 3, with reference to FIG. 1 and FIG. 2, illustrates an exemplary flow diagram of a method for optimizing the scheduling of batch workloads to minimize the makespan, in accordance with some embodiments of the present disclosure. In an embodiment the system 100 comprises one or more data storage devices of the memory 102 operatively coupled to the one or more hardware processors 104 and is configured to store instructions for execution of steps of the method by the one or more processors 104. The steps of the method of the present disclosure will now be explained with reference to the components of the system 100 as depicted in FIG. 1 and the flow diagram. In the embodiments of the present disclosure, the hardware processors 104 when configured the instructions performs one or more methodologies described herein.
According to an embodiment of the present disclosure, at step 301, the one or more hardware processors 104 are configured to identify one or more batch workloads for implementing the method disclosed. As is known in the art, batch workloads generally comprise a plurality of batch jobs and corresponding dependencies. Batch jobs typically involve reading data from a database, processing the data, and then returning the processed data to the database. Batch dependencies facilitate creating tasks that may be scheduled for execution on compute nodes after the completion of one or more parent tasks.
In an embodiment, the one or more batch workloads comprise a first set of batch jobs and a second set of batch jobs wherein the first set of batch jobs comprise a plurality of newly arriving jobs to be scheduled on one or more servers, and wherein the second set of batch jobs comprise a plurality of active jobs (or already executing jobs) on the one or more servers. Further, the first set of batch jobs and the second set of batch jobs are represented as a Directed Acyclic Graph (DAG). The DAG thus facilitates a representation of workflow(s) of the one or more batch workloads. The execution of a workflow for implementing the method disclosed starts from a root node in the DAG.
According to an embodiment of the present disclosure, at step 302, the one or more hardware processors 104 are configured to characterize the first set of batch jobs and the second set of batch jobs by initially determining a distinct service demand and a memory bandwidth requirement of each thread in each of the first set of batch jobs and the second set of batch jobs, and by finally deriving an instantaneous utilization of a Central Processing Unit (CPU) of each of the first set of batch jobs and the second set of batch jobs. Characterization (that is, determining the distinct service demand and the memory bandwidth requirement thread(s) and deriving the instantaneous utilization of the CPU of a job) has been discussed in commonly owned and co-pending Indian application no. “201821022846”, titled “Predicting Execution Time of Multi-threaded and Memory Bandwidth Intensive Batch Jobs” and do not require a separate elaboration.
In an embodiment, each of the first set of batch jobs and the second set of batch jobs represented in the DAG may be characterized in isolation. The distinct service demand comprises a CPU time of each thread in each of the first set of batch jobs and the second set of batch jobs. Generally, fast running threads in a job with low service demand finish early and on completion do not compete for resources with slow running threads of the same batch job or other batch jobs.
Hence, it is very important to measure the service demand (or the distinct service demand) of each thread (amongst the total number of threads) for an accurate simulation and prediction of job completion time of the set of multi-threaded and memory bandwidth intensive batch jobs concurrently running. The distinct service demand of threads in a batch job may be clustered by implementing, for example, a K-means clustering technique.
In an example implementation, suppose the distinct service demand may be determined as below:
job 1 : No. of threads=2, Service demand thread 1=10s, service demand thread 2=12s, average CPU utilization of the job=25%
job 2 : No. of threads=3, Service demand thread 1=25s, service demand thread 2=22s, Service demand thread 3=27s , average CPU utilization of the job=35%.
In an embodiment, the memory bandwidth requirement of each of the total number of threads may be identified for a local access and a remote access, as a local memory bandwidth and a remote memory bandwidth available to each of the total number of threads are different, which may result in different latencies for memory access. Considering an example scenario, the memory bandwidth requirement identified for each of threads (based upon the characterizing) may be from 1700 MB/s to 3500 MB/s.
Finally, the instantaneous utilization of the CPU for each of the first set of batch jobs and each of the second set of batch jobs may be derived as a function of time for a set of time intervals corresponding to each of the total number of threads. In an embodiment, the instantaneous value may be derived based upon the instantaneous utilization of the CPU by one or more multi-threaded and memory bandwidth intensive batch jobs (amongst the set of multi-threaded and memory bandwidth intensive batch jobs).
Considering an example scenario, let the total execution time of each thread (amongst the total number of threads) i is partitioned into the set of small intervals of time n of size T such that n×T=E_i. In an embodiment, within each interval, the idle time t_d and an execution time t_e of each thread may be determined using equations (1) and (2) as below:
t_e=T×C_T equation (1)
t_d=T×(1-C_T) equation (2)
wherein C_T is the CPU utilization of the batch job (amongst the set of multi-threaded batch jobs) defined at time t of execution. The method disclosed selects the idle time and the execution time of the one or more threads from the uniform distribution with average t_d and t_e for considering the fluctuations in the idle time and executions using equations (3) and (4) as below:
[(1-s)×t_e,(1+s)×t_e ]=t_e equation (3)
[(1-s)×t_d,(1+s)×t_e ]=t_d equation (4)
wherein s represents the variation or range around mean CPU utilization of a batch job (amongst the set of multi-threaded batch jobs) measured at the set of small intervals of time.
According to an embodiment of the present disclosure, at step 303, the one or more hardware processors 104 are configured to simulate, on the one or more servers, a completion time of each of the characterized first set of batch jobs and each of the characterized second set of batch jobs, wherein the simulation is performed by individually executing each of the characterized first set of batch jobs concurrently with the second set of batch jobs in a simulation environment. Further, the simulation may be performed by implementing one or more simulation based techniques. The step of simulating the completion time via the one or more simulation based techniques, along with the technical improvements (of simulating) over the traditional systems and methods may now be considered in detail.
Problem Formulation - Suppose, an application batch workflow represented by a DAG G=(V,E), wherein Vertices V=(v_1,v_2,….,v_n) in the graph G represents CPU or memory bandwidth intensive multithreaded batch jobs and E is a set of edges representing the precedence amongst the batch jobs. A dependency (v_i, v_j)?E implies that job v_j can start execution only after the job v_i has finished its execution, which further implies that a child task (or a child job) may only start after all parent jobs of the child job have finished execution.
Suppose, total i machines are available for scheduling represented by M=(m_1,m_2,….,m_i), and let n be the number of jobs in the workflow DAG represented by V=(v_1,v_2,….,v_n). The job v_j executed on the machine m_i in time ?ET?_(i,j). If the job v_j represents the jobs scheduled on machine i, schedule length may be denoted as:
?ET?_i=?_(j?V_j)¦?{E_ij ?} equation (5); and
makespan is ?ET?_max=?max?_(i?M) {?ET?_(i )} equation (6).
Based upon equations (5) and (6), the problem may thus be defined as follows. Given the DAG G representing a batch workflow, find a mapping (that is, a job mapping) for each job v_j (for 1=j=n) onto the available server m_k (for 1=k=i) for execution such that the makespan ?ET?_max of the DAG is minimized.
Simulating Environment and Simulation tool – In an embodiment, execution of the first set of the batch jobs and the second set of batch jobs represented as the DAG may be performed using a simulator called (Discrete Event Simulation Developers Environment) DESiDE (hereinafter also referred to as the simulator). The DESiDE is a discrete event simulation tool which implements CPU and memory contention model for a concurrent run of jobs. Data pertaining to the characterizing (performed in step 302 above), total number of servers available and the DAG may be given as an input to the simulator. The master instance of the simulator starts the execution of the workflow from the root node in the DAG. On completion of the job (that is, the root node job), all successor jobs that are eligible for the execution are derived from the DAG. The DESiDE implements five major functions (or the programming functions) for performing a first simulation and a second simulation, namely, interval_end, schedule_job_execution, interval_start, arrival and departure.
The execution of each new batch job (amongst the plurality of newly arriving jobs on the one or more servers) may be simulated by another instance of the simulator called the worker, using contention models, current state of the servers and the status of currently active jobs on these servers. The worker simulator implements the one or more simulation based techniques to find most suitable server for mapping each of the plurality of newly arriving jobs and returns the job mapping information to the master simulator. Master simulator maps a new job (amongst the plurality of newly arriving jobs) to the server and updates the status of the server. The simulating process starts from the root job in the DAG and continues till all the jobs and their successors in the DAG are simulated.
Simulating via the one or more Simulation based techniques – According to an embodiment of the present disclosure, the one or more hardware processors 104 may be initially configured to perform, via the simulator, a first simulation on each of the first set of batch jobs individually. The first simulation is performed by implementing a Least Execution Time (LET) technique, when at least one of the first set of batch jobs is executing concurrently with the second set of batch jobs on the one or more servers.
In an embodiment, the LET technique simulates (or determines) a least execution time of a job on all available servers as a criteria for mapping onto a server amongst the available servers. Thus, the first simulation comprises simulating (or determining), via the LET technique, a least execution time of each of the first set of batch jobs individually on the one or more servers.
Further, a current state of each of the one or more servers (that is, number of cores available) and a remaining execution time of each active batch job amongst the second set of batch jobs running on them may be extracted. Thus, the LET technique facilitates extracting, from the one or more servers, the current state of each of the second set of batch jobs executing on the one or more servers. The one or more hardware processors 104 may execute a new job individually, for example, a job v_j (amongst the first set of batch jobs) with already active jobs (amongst the second set of batch jobs) on the one or more servers, M=(m_1,m_2,….,m_n), and the simulated execution time of the job v_j, that is, ET(v_j,m_i ) for 1=i=n may be observed. A server m_k may be selected from the one or more servers such that:
m_k=min?{ET(v_j,m_i )}| for 1=i=n equation (7).
The one or more hardware processors 104 map the newly arriving job v_j on the server m_k (amongst the one or more servers) for execution, and the state of the server may be updated. The one or more hardware processor 104 iteratively perform the first simulation until each of the first set of batch jobs is simulated individually on the one or more servers. Upon completion of a job (amongst the second set of batch jobs) in the DAG, new jobs (amongst the first set of batch jobs) may be spawned and required to be mapped on the one or more servers.
In an embodiment, the one or more hardware processors 104 are configured to perform the first simulation iteratively until the least execution of each of the first set of batch jobs is simulated by executing each of the first set of batch jobs individually the second set of batch jobs on the one or more servers. The pseudocode for the algorithm executed by the one or more hardware processors 104 for performing the first simulation is as shown in algorithm 1 below.
Algorithm 1: LET
Data: Input DAG G=(V,E) representing a workflow
Result: Job mapping onto the server and execution time of
the workflow
Schedule ROOT job in the DAG on a server
On completion of ROOT, find successor jobs V_j={v_1,v_2,…,v_m}
while V_j?EMPTY do
for each job v_i in V_j do
for each server m_l,l=1,2,3,…n do
Simulate concurrent execution of the job with
other jobs and find execution time ?ET?_l of v_i
{?ET?_l (v_i,m_l )}
end
find server m_k executing v_i in least time
min?{?ET?_l } for 1=l=n
Allocate job to m_k and update server state
end
On completion of v_i find its successors jobs and update V_j
end
According to an embodiment of the present disclosure, upon completing the first simulation for each of the first set of batch jobs individually, the one or more hardware processors 104 are configured to perform, by implementing a Minimum of Maximum (MOM) technique, the second simulation on each of the first set of batch jobs individually, wherein the second simulation is performed when at least one of the first set of batch jobs is executing concurrently with the second set of batch jobs on the one or more servers. The process of performing the second simulation via the MOM technique to overcome the limitations of the traditional systems and methods may now be discussed in detail.
In an embodiment, by implementing the MOM technique, a minimum impact of each of the first set of batch jobs on the execution time of the one or more servers is simulated by executing each of the first set of batch jobs individually with the second set of batch jobs on the one or more servers, wherein the second set of batch jobs are already active (that is, already executing) on the one or more servers. Thus, an execution of each of a new job, that is, each of the first set of batch jobs is simulated on the one or more servers, that is. M={m_1,m_2,….,m_n} by running individually, each of the first set of batch jobs concurrently with already executing set of jobs A_ni (that is, the second set of batch jobs) on the one or more servers on machine m_i.
Execution time of the longest running job on each server (from the one or more servers), that is, T_l=max?{?ET?_l (A_ni,m_i)} for 1=i=n may be observed. New job (amongst the first set of batch jobs) may then be mapped onto a server m_k amongst the one or more servers, wherein a longest running job on any server is fastest amongst the one or more servers, that is, min?(T_l) for 1=l=n.
In an embodiment, the second simulation is performed iteratively until the minimum impact of each of the first set of batch jobs on the second set of batch jobs is simulated on the one or more servers, that is, the process of second simulation is repeated until each job represented in the DAG is completed. The workload and the state of server may be updated after job allocation, or job mapping onto a server. The pseudocode for the algorithm executed by the one or more hardware processors 104 for performing the first simulation is as shown in algorithm 2 below.
Algorithm 2: MOM
Data: Input DAG G=(V,E) representing a workflow
Result: Job mapping onto the server and execution time of the workflow
Schedule ROOT job in the DAG on a server
On completion of ROOT, find successor jobs V_j={v_1,v_2,…,v_m}
while V_j?EMPTY do
for each job v_i in V_j do
for each machine m_l,l=1,2,3,…n do
Simulate concurrent execution of the job v_i with other jobs A_ni ? V on machine m_l
Find execution time ?ET?_l of longest running job T_l on machine m_l
T_l=max{?ET?_l (A_ni,m_l )}
end
find server m_kwhere longest running job is fastest
amongst all running servers min?(T_l) for 1=l=n
Allocate job to m_k and update server state
end
On completion of v_i find its successors jobs and update V_j
end
According to an embodiment of the present disclosure, upon completing the second simulation, the one or more hardware processors 104 finally are configured to compute, by implementing a Smallest Load First (SLF) technique, a minimum load of executing each of the characterized plurality of batch jobs and the one or more corresponding dependencies on the one or more servers.
As compared to the traditional systems and methods, which compute the average load due of already running jobs on each server, and thereafter map all the newly arriving jobs on a server with minimum average workload, the SLF technique, as implemented by the method disclosed, computes the average load of the second set of batch jobs on the one more servers and then maps each of the first set of batch jobs one by one on one of the one or more the servers with minimum average load.
In the SLF technique implementation, the average load on each server is re-computing each time after mapping one of the jobs from the first set of batch jobs. This process is performed iteratively by the one or more hardware processors 104 until all first set batch jobs are mapped. In an embodiment, the SLF technique computes the load L_l on each of the one or more servers in M={m_1,m_2,….,m_n} instantaneously as below:
L_l=(Number of threads on a server)/(Number of cores on a server) equation (8)
Finally, the one or more hardware processors 104 finally schedule a new job amongst the first set of batch jobs on a server m_k with a minimum load on each server (amongst the one or more servers), that is,
m_k=min?{L_l,m_l}| for 1=l=n equation (9)
The pseudocode for the algorithm executed by the one or more hardware processors 104 for performing the first simulation is as shown in algorithm 3 below.
Algorithm 3: SLF
Data: Input DAG G=(V,E) representing a workflow
Result: Job mapping onto the server and execution time of
the workflow
Schedule ROOT job in the DAG on a server
On completion of ROOT, find successor jobs V_j={1,2,…,n}
while V_j?EMPTY do
for each job v_i in V_j do
for each server m_i,i=1,2,3,…m do
Find load L_i on server
L_i=(Number of threads on a server)/(Number of cores on a server)
find server m_k with least load
min??{(L_i,m_i)}? for 1=i=m
Allocate job to m_k and update server state
end
On completion of v_i find its successors jobs and update V_j
end
It may be noted that algorithm 1, algorithm 2 and algorithm 3 use a job execution model for concurrently executing the first set of batch jobs and the second set of batch jobs, wherein the job execution model comprises a memory contention model designed on top of a CPU contention model. The job execution model has been discussed in commonly owned and co-pending Indian application no. “201821022846”, titled “Predicting Execution Time of Multi-threaded and Memory Bandwidth Intensive Batch Jobs” and do not require a separate elaboration.
According to an embodiment of the present disclosure, at step 304, the one or more hardware processors 104 are configured to optimize, based upon the simulated completion time of each the first set of batch jobs and each of the second set of batch jobs, scheduling of the one or more batch workloads. Scheduling of the one or more batch workloads is optimized as the simulated least execution time (or the completion time) of each of the first set of batch jobs and the simulated completion time of each of the second set of batch jobs (as simulated in step 303 above) facilitates an optimal mapping of each of the first set of batch jobs on an appropriate server amongst the one or more servers, that is, a job (amongst the first set of batch jobs) is scheduled onto the appropriate server on which it completes fastest, that is, takes a minimum execution time.
Thus, the step of optimizing facilitates minimizing a makespan of the one or more batch workloads as a minimum overall runtime is achieved for the DAG by executing them on the appropriate server. Finally, at the end of the first simulation and the second simulation, the one or more hardware processors 104 generate, using a mapping sequence technique, a job onto server mapping sequence with the estimated time of execution of each individual job (amongst the simulated first set of batch jobs) and the makespan of the DAG. The job mappings generated from the first simulation, the second simulation, and via the SLF technique may finally be executed with the real job scheduler, thereby minimizing makespan in production environment, and optimizing scheduling of the one or more batch workloads in the production environment.
According to an embodiment of the present disclosure, the technical improvements of the method disclosed over the traditional systems and techniques may be considered in detail by evaluating and analyzing the experimental data pertaining to the steps 301 through 304 performed. Each experiment was performed on Intel Xeon™ servers running centOS 6.0 Linux™ system. The simulator DESiDE was executed on a single server and the simulator simulated execution of the DAG on clusters of different sizes. The job mappings generated by the first simulation, the second simulation, and via the SLF technique were tested on clusters of 2, 3 and 4 physical servers. Each server comprise 56 logical cores and 80GB/s memory bandwidth available.
Further, a job scheduler called PARLANCE (that is an in-house job scheduler with no full form) was implemented to run the experiments on physical servers. Although the PARLANCE implements average load based scheduling as a default strategy but may also be programmed to follow user defined job onto the server mappings. The performance of the PARLANCE may be compared to other popular job scheduling algorithms that use average load based scheduling strategy such as a Platform Load Sharing Facility (LSF)™ job scheduler. The LSF comprises in-built capabilities that allow users to define job constraints and dependencies among jobs.
STREAM benchmark was used to create various batch workflows for each experiment. The STREAM benchmark workload performs four different vector operations namely copy, add, scalar, triad. The vector operations comprise CPU, memory bandwidth intensive and most suitable for testing contention models and scheduling algorithms. 36 unique STREAM benchmark jobs were generated by varying the number of iterations performed and number of threads in each job. Number of threads per job varies from 4 to 28 and bandwidth requirement per thread varies from 3.8 GB/s to 10.5 GB/s.
A DAG of 50 jobs (DAG-1) and 100 jobs (DAG-2) was constructed via the one or more hardware processors 104 by using the 36 unique STREAM jobs. DAG-1 and DAG-2 were used for the experiments. Each of the STREAM jobs were profiled in isolation. Service demand and CPU utilization of each thread in each job was recorded at fixed intervals. Intel(R)™ Memory Latency Checker tool (mlc) was used to observe the latency due to remote and local memory data access.
In an embodiment, initially, DAG-1 and DAG-2 were given as inputs to the simulator with the job characterization data, wherein the job characterization data comprises the distinct service demand and the memory bandwidth requirement of each thread of each job in DAG-1 and DAG-2. As mentioned above, the simulation starts with a root job in DAG-1 and DAG-2, and upon completion of the root job, the simulator communicates with DAG-1 and DAG-2 to obtain new jobs (that is, the first set of batch jobs) to be spawned. By implementing the LET technique, the MOM technique and the SLF technique, the simulator maps each job from DAG-1 and DAG-2 onto the appropriate server (that is, a most appropriate server).
In an embodiment, as discussed in step 303 above, concurrent execution of jobs on multiple servers is simulated by the simulator. Upon completion of DAG-1 and DAG-2 processing, expected completion time of individual job, makespan of the whole DAG (that is, DAG-1 and DAG-2) and job onto the server mapping is generated as an output. The simulations were conducted for cluster size of 2, 3 and 4 servers. Further, execution of jobs on each server was simulated with 56 logical cores and ˜80GB/s memory bandwidth. The simulations were repeated with three different seeds and the average makespan was calculated by the one or more hardware processors 104. In case job onto the server mapping changes with different seeds, the simulations may be repeated till the dominant mapping is identified. By implementing the method disclosed, simulation time to find a server mapping for a single job on a set of four servers is observed to be less than 1 second. By implementing the method disclosed, the simulation time for generating the job mapping for the complete DAG may be further reduced.
By referring to FIG. 4A, a comparison of a makespan observed by implementing the method disclosed (that is by implementing the LET technique, MOM technique, and the SLF technique) on DAG-1 may be referred. By referring to FIG. 4A again, it may be noted that the MOM technique shows an improvement of approximately 5%, 13% and 12% over the SLF technique using 2, 3 and 4 server clusters respectively. Further, the LET technique shows an improvement of 3%, 5% and 8% over the SLF technique using 2, 3 and 4 servers respectively.
By implementing the method disclosed on DAG-2 comprising 100 jobs, it may be noted that the MOM technique shows an improvement of approximately 3%, 9% and 9% over the SLF technique for 2, 3, 4 servers respectively, as referred to in FIG. 4B. Also, the LET technique also performs better than the SLF technique with an improvement of approximately 3%, 5%, 5% in the makespan for 2, 3, 4 server respectively.
By referring to FIG. 5A, which shows a comparison of a makespan obtained by implementing the job onto server mapping of the simulations using the real job scheduler, for example the PARLANCE, on a cluster of three servers may be observed. The job onto server mapping obtained from the first simulation (by implementing the LET technique), the second simulation by implementing (the MOM technique) and also the SLF technique are finally given as inputs to the real job scheduler. The makespan obtained by using these techniques was compared with makespan generated by using a default average load based job onto server mapping (named as a job scheduler) in the PARLANCE.
By referring to FIG. 5A again, it may be noted that the makespan generated using the mapping obtained from the MOM technique resulted in a minimum makespan followed by the LET technique, the SLF technique, and a traditional job scheduling technique. By implementing the method disclosed, an improvement of 25%, 15%, and 13% over the traditional job scheduling technique was observed for DAG-1. By referring to FIG. 5B, it may be noted that similar results were observed for DAG-2. By implementing the method disclosed on DAG-2, an improvement of 35%, 24%, and 21% may be achieved in comparison to the traditional job scheduling technique.
By referring to FIG. 5A through 5B yet again, it may be noted that although both the SLF technique and the PARLANCE implement the average load based scheduling, however a significant difference in the makespan with job mapping predicted by simulation using the SLF technique, and actual measurement using the PARLANCE with SLF routing (job scheduling) may be observed. The PARLANCE used UNIX load average to determine a least loaded server, wherein the UNIX load average is an average CPU load over the last minute. In case several dependent jobs are launched at the same time, the load may not change when checked while mapping each of these dependent jobs. If there are sufficient cores available, all dependent jobs are likely to be launched on the same server.
The DESiDE uses the instantaneous utilization of the CPU to compute CPU load, that is, when a job is scheduled to launch on a particular server, the load average is instantaneously updated. Other jobs that are to be launched at the same simulation time may find the server loaded and may thus be launched on other less loaded servers. When the job onto server mapping from simulated SLF is given as an input to the PARLANCE, the difference is reduced to 5%.
Finally, by referring to FIG. 6A through 6C yet again, a comparison of an expected execution time of individual jobs of DAG-2, using the SLF technique, the LET technique and the MOM technique on a cluster of 3 servers may be referred. The SLF technique and LET technique map new job to a server where its own execution time is minimum without considering its effect on execution time of already running jobs. This job placement policy may affect the execution time of critical jobs in the sequence and can result in higher makespan, that is, finish time of the last job in the DAG. However, the MOM technique ensures a minimum effect of newly placed jobs on the execution time of pre-running jobs. As a result, critical jobs having further dependent jobs may be relatively unaffected by newly placed jobs. By referring to FIG. 6C yet again, more concurrently running jobs and lower makespan time may be observed.
According to an embodiment of the present disclosure, advantages of the method disclosed may now be considered in detail. As discussed above, the method disclosed results in the optimal mapping, that is, optimal job onto server mapping by simulating execution time of each newly arriving job, a new job is mapped onto the appropriate server based upon the simulated execution time or impact of each of the newly arriving job(s) on already active jobs on the one or more serves. Further, the method disclosed reduces the execution time of a batch job and of batch workflow(s) as a newly arriving job is simulated initially using the LET technique, and then using the MOM technique to determine the optimal mapping.
Further, the method disclosed may be integrated with real schedulers for real life applications such as bioinformatics, physics, earth sciences, and the like. The method disclosed, as mentioned above, uses the CPU and the memory bandwidth contention models and is thus suitable for CPU and memory bandwidth intensive jobs. As the execution time of the batch job workflow(s), the method disclosed reduces the overall cost of executing the batch applications. Finally, the model can be applied to both homogeneous servers and heterogeneous servers with job characterization efforts on each unique server, and can be integrated with the existing resource management tools to improve their job scheduling capabilities.
The written description describes the subject matter herein to enable any person skilled in the art to make and use the embodiments. The scope of the subject matter embodiments is defined by the claims and may include other modifications that occur to those skilled in the art. Such other modifications are intended to be within the scope of the claims if they have similar elements that do not differ from the literal language of the claims or if they include equivalent elements with insubstantial differences from the literal language of the claims.
The embodiments of present disclosure herein addresses unresolved problem of optimal mapping of batch jobs on the appropriate server. The embodiment, thus provides for simulating, on the one or more servers, the completion time of each of the characterized first set of batch jobs, by individually executing each of the characterized first set of batch jobs concurrently with the characterized second set of batch jobs in a simulation environment. Moreover, the embodiments herein further provides for minimizing the makespan of the one or more batch workloads, wherein minimizing the makespan facilitates a minimum runtime of overall execution of the one or more batch workloads on the one or more servers using the real job scheduler.
It is to be understood that the scope of the protection is extended to such a program and in addition to a computer-readable means having a message therein; such computer-readable storage means contain program-code means for implementation of one or more steps of the method, when the program runs on a server or mobile device or any suitable programmable device. The hardware device can be any kind of device which can be programmed including e.g. any kind of computer like a server or a personal computer, or the like, or any combination thereof. The device may also include means which could be e.g. hardware means like e.g. an application-specific integrated circuit (ASIC), a field-programmable gate array (FPGA), or a combination of hardware and software means, e.g. an ASIC and an FPGA, or at least one microprocessor and at least one memory with software modules located therein. Thus, the means can include both hardware means and software means. The method embodiments described herein could be implemented in hardware and software. The device may also include software means. Alternatively, the embodiments may be implemented on different hardware devices, e.g. using a plurality of CPUs.
The embodiments herein can comprise hardware and software elements. The embodiments that are implemented in software include but are not limited to, firmware, resident software, microcode, etc. The functions performed by various modules described herein may be implemented in other modules or combinations of other modules. For the purposes of this description, a computer-usable or computer readable medium can be any apparatus that can comprise, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device.
The illustrated steps are set out to explain the exemplary embodiments shown, and it should be anticipated that ongoing technological development will change the manner in which particular functions are performed. These examples are presented herein for purposes of illustration, and not limitation. Further, the boundaries of the functional building blocks have been arbitrarily defined herein for the convenience of the description. Alternative boundaries can be defined so long as the specified functions and relationships thereof are appropriately performed. Alternatives (including equivalents, extensions, variations, deviations, etc., of those described herein) will be apparent to persons skilled in the relevant art(s) based on the teachings contained herein. Such alternatives fall within the scope and spirit of the disclosed embodiments. Also, the words “comprising,” “having,” “containing,” and “including,” and other similar forms are intended to be equivalent in meaning and be open ended in that an item or items following any one of these words is not meant to be an exhaustive listing of such item or items, or meant to be limited to only the listed item or items. It must also be noted that as used herein and in the appended claims, the singular forms “a,” “an,” and “the” include plural references unless the context clearly dictates otherwise.
Furthermore, one or more computer-readable storage media may be utilized in implementing embodiments consistent with the present disclosure. A computer-readable storage medium refers to any type of physical memory on which information or data readable by a processor may be stored. Thus, a computer-readable storage medium may store instructions for execution by one or more processors, including instructions for causing the processor(s) to perform steps or stages consistent with the embodiments described herein. The term “computer-readable medium” should be understood to include tangible items and exclude carrier waves and transient signals, i.e., be non-transitory. Examples include random access memory (RAM), read-only memory (ROM), volatile memory, nonvolatile memory, hard drives, CD ROMs, DVDs, flash drives, disks, and any other known physical storage media.
It is intended that the disclosure and examples be considered as exemplary only, with a true scope and spirit of disclosed embodiments being indicated by the following claims.