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

Introduction

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)

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)

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.