Multi-Processor Job Scheduling in High-Performance Computing (HPC) Systems

Multi-Processor Job Scheduling in High-Performance Computing (HPC) Systems

Annu Priya (Birla Institute of Technology, Mesra, India) and Sudip Kumar Sahana (Birla Institute of Technology, Mesra, India)
Copyright: © 2020 |Pages: 36
DOI: 10.4018/978-1-5225-9806-0.ch009


Processor scheduling is one of the thrust areas in the field of computer science. The future technologies use a huge amount of processors for execution of their tasks like huge games, programming software, and in the field of quantum computing. In hard real-time, many complex problems are solved by GPU programming. The primary concern of scheduling is to reduce the time complexity and manpower. There are several traditional techniques for processor scheduling. The performance of traditional techniques is reduced when it comes under huge processing of tasks. Most scheduling problems are NP-hard in nature. Many of the complex problems are recently solved by the GPU programming. GPU scheduling is another complex issue as it runs thousands of threads in parallel and needs to be scheduled efficiently. For such large-scale scheduling problem, the performance of state-of-the-art algorithms is very poor. It is observed that evolutionary and genetic-based algorithms exhibit better performance for large-scale combinatorial problems.
Chapter Preview


The science of scheduling is not new; the first citation of scheduling was seen 3000 years ago by Egyptians. After that, 2500 years ago, Sun Tzu wrote a scheduling strategy for military perspective. In the 1980s scheduling was only used for very expensive assets that required significant training and skill for lengthy manual scheduling calculations. Changing and development continuously increase in the field of the industry by the arrival of scheduling tools with GUI. The scheduling is required in every field such as the business sector, cooperate, etc. In a computing environment, the scheduling algorithm is used to organize the data correctly. It also helps to create plans and structure the complex tasks in an efficient and reliable manner. Task scheduling is one of the tedious operations in computer science for that the scheduler requires a highly precise algorithm to reduce the time frame of the task in the waiting queue for execution. There are various stochastic process is present for processor scheduling. Processor scheduling is the way to determine which process will get the computer power to run while another process is on hold condition. The process that assigns by CPU has various states. CPU decisions may take place by considering the following four circumstances which is shown below in Figure 1 (Cera et al, 2007).

Figure 1.

Process state of CPU various states


The Data Flow Diagram (DFD) represents various states of the process in CPU. The start state shows the process has been created and wait for the ready queue. In the ready state, the initialize process is waiting for the queue and assign to the processor. Running state is used some instruction set to assign the process to the processor. The process is waiting for some event to occur (such as an I/O completion or reception of a signal) in the waiting state. Finally, in the termination state, the process is executed. There are various criteria for CPU scheduling such as:

CPU Utilization: The amount of work is handled by CPU at a certain period of time. It is also used for estimating the performance of the system. The CPU utilization is varied according to the type of task because some tasks require heavy CPU time while others require less CPU time. The other name of CPU time is process time, where the amount of time is used by CPU to process the instruction of an operating system. The unit of CPU time is clock ticks or seconds. CPU utilization represents the burden on the processor in terms of percentage. It means that if there are any changes to be made in the system or otherwise it may get exhausted by capacity. Let us define CPU utilization as U = 100% - (Percentage of time that is spent in the idle task) then, Percentage of time in idle task calculation is given below in Eq. (1)


Throughput: It is measured that the amount of data is transferred from one place to another or processed in a specified amount of time. Data transfer rates for disk drives and networks are measured in terms of throughput. Typically, throughputs are measured in kbps, Mbps and Gbps.

Turnaround Time (TAT): It is the time taken by the task for the submission to the completion of the process. Turnaround time is an important metric for the evaluation of the scheduling algorithm. Which is given below in Eq. (2)

Turnaround_Time (TAT) = Compeltion_Time (CT) – Arrival_Time (AT)(2)

Waiting Time: The task has to wait after placing a request for action and before the action/service actually occurs. Waiting time is calculated based on Eq. (3)

Waiting_Time (wt) = Turnaround_Time (TAT) – Burst_time (BT)(3)

Response time: It is the elapsed time between the request and the response of the request. It is mainly used for performance measurement. Low response times may be critical to successful computing.

Complete Chapter List

Search this Book: