A Machine Learning based Resource Efficient Task Scheduler for Heterogeneous Computer Systems

doi:10.21203/rs.3.rs-2250556/v1

Download PDF

Research Article

A Machine Learning based Resource Efficient Task Scheduler for Heterogeneous Computer Systems

https://doi.org/10.21203/rs.3.rs-2250556/v1

This work is licensed under a CC BY 4.0 License

You are reading this latest preprint version

Heterogeneous computer systems are becoming mainstream due to disparate processing and performance capabilities of multi-core architectures. It consists of different type of devices, i.e., Central Processing Units (CPUs), accelerators, and Graphics Processing Units (GPUs). In the heterogeneous computing environment, if one device is more powerful in terms of computing capability, the scheduling schemes generally favor the powerful device, and that device becomes overloaded while the other device is underutilized. This load imbalance problem results in increased execution time. In this research, we propose load-balanced task scheduler combined with machine learning based device predictor. The device predictor is used to predict execution time both on CPU and GPU devices, and a device with shorter predicted execution time is considered as a suitable device for that particular task. However, it may happen that a high fraction of tasks map only on one type of device since that device is a suitable device for them. Such situation leads to the problem of load imbalance. We use work stealing based task scheduler as part of our solution that allows an idle device to process tasks from the queue of another’s device. In this way we can avoid load imbalance, minimize the overall execution time of tasks, and maximize the device utilization and throughput. We evaluate the performance of our proposed solution into two stages. Firstly, we measure the error rate of our machine learning predictor using three different algorithms (i.e., random forest, gradient boosting, and multiple linear regression). We demonstrate that random forest performs better with marginal error rate. Secondly, we compare the performance of work stealing task scheduler with other scheduling alternatives. Our results show that the proposed solution reduces execution time by 65.63%, increased resource utilization by 93.3%, and throughput by 65.5% in comparison to baseline scheduling schemes.

Heterogeneous Computing

Machine Learning

Gradient Boosting

Work Stealing

OpenCL

Now a days heterogenous computer systems are commonly used to execute computationally intensive computer programs. A heterogenous computer system consists of multiple different processor types such as Central Processing Unit (CPU) and Graphics Processing Unit (GPU). Normally a CPU device executes sequential programs with latency optimization and GPU device executes parallel programs with throughput optimization [1] [2] [3].

Open Compute Language (OpenCL) is developed as an industry standard for data-parallel computer applications which can be executed on heterogeneous computer systems to achieve better performance [4]. We consider OpenCL framework in this research due to its portability and having wide range of supported computing devices.

In a heterogenous system, it is required to decide that a job should be mapped on a CPU queue or a GPU queue. There are multiple scheduling techniques for the mapping of jobs to CPU and GPU device in the heterogeneous system [5]. The scheduler determines a specific data-parallel job should be allocated to which executing device i.e., CPU or GPU [6]. However, it is not obvious that which type of processing device is suitable for a particular OpenCL application. In fact, some OpenCL applications may perform better on CPU while others perform better on GPU.

Some researchers suggest mapping jobs on devices at runtime [7][8]. The advantage of scheduling tasks on runtime is that the decision of job mapping is more efficient and can be adjusted at runtime, but it increases the complexity and higher the scheduling overhead. For instance, [9][10] Splits the code and maps each part on a suitable computing device. Splitting the code requires high programming skills.

A machine learning predictor can also be used to suggest a suitable device for a given job. In this regard, static and dynamic code features are widely used to characterize a given program [11][12].. The machine learning model (i.e., predictor) is trained against static and dynamic code features to predict the suitable device (CPU or GPU) for a job. For instance, number of multiplications, number of float data types, number of functions, etc. are the static code features whereas input workload is a dynamic code feature [13]. Most of the scheduling mechanisms schedule a single data-parallel program that depends on code splitting and requires application profiling [14].

The longer execution time of applications is the main concern while executing data-parallel applications. When only GPU executes jobs from the job pool, it takes a long execution time as the CPU is not taking part in application execution. The overall execution time of the job pool can be reduced by assigning jobs to both CPU and GPU simultaneously. However, generally CPU only performs the management of assignment of jobs to GPU and does not take part in the actual execution of programs, this causes load imbalance between the computing devices [15].

Figure 1 shows the execution of programs on different processing devices. It shows that executing programs on CPU only takes more execution time and under-utilization of processing devices as GPU remains idle. Executing all programs on GPU only also causes an increase in execution time and under-utilization of CPU device.

By assigning a program to a suitable device can reduce the execution time to some extent, but still the under-utilization of a processing device occurs. For instance, more jobs mapped on GPU which means CPU remains idle. As we see in Fig. 1 that CPU becomes idle after 19.8 seconds whereas GPU processing continues until 39.6 seconds. Although we have reduction in overall execution time as compared to other two cases, but CPU remains idle for around 50% of time which is indeed inefficient use of CPU.

In this context we believe that a scheduler which utilizes both CPU and GPU in a load balanced manners can further reduce execution time. So, both CPU and GPU devices process load in parallel and complete the assigned tasks ideally at the same time. It can reduce the overall execution time of job pool, maximize throughput and device utilization.

In this research, we propose combining a machine learning based predictor with a load balancer task scheduler. The predictor is used to predict the suitable device for a given job whereas task scheduler ensures load balancing between CPU and GPU. For instance, if predictor suggests most of the jobs to execute on GPU, and GPU has a long queue whereas CPU queue becomes empty, our load balancer task scheduler allows CPU to steal a job from GPU queue. The main contributions of our work are as follow:

A machine learning based model development for the prediction of the program execution time on a CPU device and on GPU device. We compare the accuracy of three different machine learning algorithms (i.e., random forest, gradient boosting, and multiple linear regression) in this regard.

Combining the predictor with load balanced task scheduler to reduce overall execution time of the programs in job pool and maximize the device utilization.

Analysis and performance comparison of different scheduling alternatives with our proposed solution.

The rest of paper is organized as follows: in section 2 we present related work and make a comparison with our proposed solution. The design of proposed solution is present in section 3 whereas section 4 further elaborates components of the proposed solutions. In section 5, we evaluation the performance of our solution and make a comparison with other scheduling alternatives. The paper is concluded in section 6.

There are many studies that suggest different task schedulers for heterogenous computer systems. However, there are some studies that propose machine learning predictor along task scheduler whereas other studies focus only on efficient task scheduler. These studies are categorized into two subsections. The section 2.1 discusses those scheduling schemes where machine learning predictor is not the part of proposed solution, whereas section 2.2 present studies that use machine learning predictor as a part of proposed solution. Section 2.3 summarize our findings from literature review and compare existing work with our proposed solution.

2.1 Scheduling Schemes for Heterogeneous Computer Systems

In study of [7], Proposed Heterogeneous Dynamic Self-Scheduler HDSS scheduling mechanism that divides workload among processing devices. It improves execution time of kernel in two phases, profiling phase, and adaptive phase. In profiling phase, each processing unit has assigned some loop operations to evaluate computation power while in adaptive phase remaining loop operations are assigned on base of processing speed.

In [16], the proposed technique consists of Static and dynamic approach. It automatically compiles and executes only single OpenCL programs on CPU GPU devices considering issues of communications, load-balancing, and load-variations. In static phase kernel code is partitioned and mapped to different processing devices and execution time of each kernel is noted. In dynamic phase, Partitioned kernel queuing is adapted to achieve optimization.

Co-scheduling Asymptotic Profiling is two-phase scheduling method designed for heterogeneous computing [18]. In first step, a small amount of workload is fairly assigned to both CPU and GPU devices and execution time is measured. Based on previous execution time, amount of work is doubled on a faster device. The scheduling is carried out with elevated workload before difference between present and former executions are fewer than the predefined threshold. In the second step according to computing units, the remaining workload is split as per the first step of the sampling.

Mostly programmers map suitable program to suitable device that causes load imbalance and under-utilization of the processing devices [19]. To remove burden of data management and device connectivity from programmers, EngineCL is extended with help of OpenCL and FPGA devices. The proposed model performs management of data as well overlapping of commands through different benchmarks for experimentation purposes.

In [20], researcher introduced Maat, a library by which programmers build a parallel version of a kernel program that selects a load balancing method and run the program on all available resources. This method utilizes the same kernel code and needs no effort for extra programming while Simhash is a commonly used tool capable of attributing a bit string existence to a word so that identical texts have identities that are similar. The researcher [21], proposed a real-time solution for a simhash measurement in OpenCL and illustrates how multi-core CPUs, GPUs, and FPGAs can make use of it. Random text generation methodology is used for evaluation.

2.2 Scheduling Schemes based on Prediction Models

In study of Smart Multi-Task Scheduling for OpenCL Programs on CPU GPU Heterogeneous Platforms [2], Schedules multiple kernels on CPU and GPU devices and determines best utilization of kernel at run-time. The kernel speedup is predicted by SVM model on base of static code features extracted through clang and LLVM along with input data size for scheduling jobs while [3] map OpenCL applications based on process capability and device suitability through machine learning classifier that predicts computational compatibility of processors.

OpenCL can execute a program on multiple devices like CPU, GPU, and FPGA [11]. The researcher estimates best application speed-up for each device using machine learning classifier based on dynamic code-feature extraction through LLVM framework. This approach is platform dependent, does not work properly on complex programs and takes more time as compared to static code features.

The researcher [14] proposed a static feature and predictive modeling-based program that partition OpenCL programs on CPU and GPU devices using SVM machine learning along with Principal Component Analysis (PCA) for dimensionality reduction. The model is evaluated on GPU-friendly, CPU-friendly, and other benchmarks while the proposed model predicts the execution time of jobs and schedules them to reduce the overall execution time of the job pool.

In [13], researcher consider job requirements, device suitability, and performance predicted on a processor for a program. Programs are combined in a job pool based on suitability of device and sorted on base of predicted speedup through predicting models. The OpenCL programs, extracted code features, and input data size are provided to speedup predictor to predict speedup. The programs are sorted in descending order on base of speedup and E-OSched maps the jobs to CPU, GPU devices.

The researcher [17] presents a run-time model that schedules the tasks on a suitable CPU or GPU device. The model predicts at run-time whether to merge or schedule separately OpenCL programs in a job pool using a decision tree machine learning model. The model is based on both static code feature and dynamic code features. The model first separates the kernel to CPU device and GPU device based on estimated device affinity and then determines whether to merge or not the kernels. The merging of programs is done through the JIT compiler and scheduling by a thin run-time layer.

Resource Aware Load Balancer for Heterogeneous Cluster [5] RALB-HC is a supervised machine learning-based approach that distributes workload in multi-node heterogeneous computing environments based on the computing capabilities of resources and needs of applications computing. The model considers device suitability, expected speedup, and load balancing for job mapping in heterogeneous environments.

Machine learning classifiers do not perform well in high-density computing requirements because of execution of instructions in sequential way. So, [22] designed a learning model in which GPUs are used for training purposes and FPGAs are used as inference models using a model converter. The approach is evaluated through neural networks models while the researcher [8] estimated execution time to determine application scheduling on processing devices. The model is trained through the execution history of an application and maps new programs to devices that have finished their job earlier.

2.3 Analysis of Existing Literature

After comprehensive analysis of different approaches, there are multiple techniques for scheduling in heterogeneous environment. Some scheduling techniques creates load unbalancing while scheduling as CPU only manages kernel execution and does not take part in actual computation [23][18][24]. The CPU waits until GPU completes their execution that is not desirable. In other studies [25][20] split program code between CPU and GPU device. Similarly, [11] does not consider the load balancing for mapping jobs to the scheduler.

In [15][26] authors map a single program to either CPU or GPU device while creates a job scheduler to schedule jobs from job pool in heterogeneous system considering reduction in overall execution time of jobs, increase in throughput, and utilization of processing device. Predictive machine learning modeling is also an effective technique for optimizing parallel programs and Several learning models are trained [12][17][27]. However, we believe following are the limitations of the existing work:

Most of the scheduling techniques require code splitting. They split the program to execute on CPU and GPU. This code-splitting results in additional time overhead.

Some researchers map a single job in a heterogeneous environment that causes time overhead.

To the best of our knowledge, no prior work on load-balanced task scheduling using a machine learning model in a heterogeneous computer system.

In a heterogeneous computing environment, a task scheduler can map a task either on a CPU or GPU device. Ideally, a device with a shorter execution time for a particular task should be selected (i.e., suitable device). However, it is difficult for a scheduler to make a device suitability decision because of two reasons. Firstly, the estimated execution time for a particular device is not known in advance. Secondly, there are variety of tasks from a pool of jobs [4] having many different types of programming attributes (e.g. total number of control statements, total number of functions etc.) which may or may not favor a particular device (i.e. CPU or GPU).

Generally, programmers use the default scheduling strategy for mapping tasks on a heterogeneous system [3]. In this strategy, the CPU executes the serial portion (host part) of the program while GPU runs the parallel portion (kernel part) of the program. This strategy causes CPU idle as all computation is performed by GPU. In such a situation, a GPU may become overload and results in high execution time for many tasks. In addition, the CPU remains idle (consuming power for nothing) during this time which is inefficient use of resource. Therefore, we believe it is challenging for the developers to map tasks on a heterogeneous system in an optimal way.

In this work, we aim to design a task scheduler that could predict a device with a shorter execution time. However, it might be possible that a high percentage of tasks map only on a one device which is predicted as a suitable with shorter execution time. It may result in an overloaded device while the other device might be underloaded at that time. To avoid such a situation and make an efficient use of both CPU and GPU, we suggest a load balancing strategy which works in the combination of our machine learning predictive model. The details of both predictive model and load balancer are given below.

3.1 Device selection using machine learning based predictive model

The architecture of the proposed solution is shown in Fig. 3.1. The user submits data parallel OpenCL programs and then proposed scheduling system assess the submitted jobs. Our machine learning based predictor predicts the execution time of a task both on CPU and GPU device. The device with shorter predicted time is selected for execution of a task. It is shown as a CPU suitable or GPU suitable in Fig. 3.1. To predict the execution time, the predictor is provided with two types of inputs. The first is the input data size of an application. The second is the code features (program attributes). We use the static code analyzer to extract the code features and then find out correlation between the features through correlation analysis. The purpose is to select only important and influential features for the training of our predictor. In short, the static code features and the dynamic workload (i.e., input size) of the jobs are used for predicting the execution time of each job on both CPU and GPU. The details of predictor training and testing are presented in section 4.

After selection of a suitable device, the task is placed on an associated queue for that device. We have one queue for CPU suitable tasks whereas the other queue is for GPU suitable tasks. It is now responsibility of work stealing scheduler [6], [28] to select a task from these two queues for execution either on CPU or GPU. We use work stealing scheduler since it is useful to balance the offered load between CPU and GPU. The load balancing leads to reduce the overall execution time of the submitted jobs and efficient utilization of the processing devices (i.e., CPU or GPU). The details of work stealing scheduler are given below.

3.2 Load Balancer

Work stealing is a scheduling algorithm that is widely used for the mapping of programs in heterogeneous environment having multi-core processing devices [6], [28]. The basic theme of the work stealing scheduler is distributing the workload on the idle processing devices which ultimately causes the reduction in overall execution time of jobs and efficient utilization of the processing devices.

In work stealing scheduler (Fig. 3.2), each processing device have a double ended queue (i.e., deque) to hold the tasks assigned to it. The jobs in the deque are sorted in the descending order on base of their execution time. A processing device takes one job at a time from the associated deque. When a processing device executes all their assigned jobs and the deque of processing unit becomes empty, the device becomes thief and steals a job from the bottom of another processing device deque (which is known as victim processor). When the thief processor executes the job and more jobs are present in victim processor deque, the thief processor steal another job from the bottom of deque (last in first out). This process remains until all the available processing devices executes all the available jobs. It is important to mention that stealing of jobs starts only when a processing device has executed all their assigned jobs and then becomes idle. In our work the concept of work-stealing scheduling algorithm is used for load balancing between CPU and GPU devices. Each device has an associated deque. CPU deque is created for the jobs to be executed on CPU and GPU deque is created for the jobs to be executed on GPU. However, we believe that in most of the cases the CPU is not as much loaded as a GPU [13] and work-stealing algorithm allows to pick up a job from GPU deque (at the end) for execution on CPU.

The proposed system is shown in Fig. 3.3. First, the execution time of jobs on CPU as well as on GPU is predicted through machine learning model. For finding the suitable device for a job, the predicted execution time of GPU (G_time) is subtracted from predicted execution time of CPU (C_time). The difference of C_time and G_time is known as D_time.

D_time = C_time – G_time. (1)

The D_time consists of both positive and negative values. A job having negative D_time value is considered as CPU suitable as it has less predicted execution time on CPU. A job having a positive D_time value is GPU suitable as it has more execution time on CPU. A job having D_time value equal to zero is considered as CPU suitable to break the tie.

The jobs sorted on the bases of D_time are moved to the job pool where two deque are maintained. The jobs with negative D_time values are placed on CPU deque whereas jobs with positive values are placed on GPU deque in descending order. When both devices have jobs in their dequeues, a job in front of a respective deque is selected for execution. Thus, both CPU and GPU work in parallel by picking up jobs in order from their associated deques. However, when a processing device completes its execution of all assigned jobs, it steals the jobs from another processing device. For instance, suppose CPU completes the execution of the jobs available in the CPU deque, and GPU has jobs remaining in the GPU deque, the CPU will become thief and steal a job from the end of the GPU deque. Although CPU is not selected a suitable device (with higher predicted execution time than GPU execution time) for the steal job since the job is picked up from GPU deque, however, GPU is busy at the moment in processing of other jobs, and it is likely that last job would be completed in parallel on CPU. In this way we aim for the reduction in overall jobs execution time through efficient resource utilization.

This section covers the details of the machine learning prediction model. The first step is the selection of OpenCL applications and then predict whether CPU or GPU is a suitable device for that particular application. We select applications from two benchmark suites i.e., Polybench benchmark and AMD benchmark suite. Polybench and AMD are set of computation kernels used to test the performance of compilers and related applications, such as matrix multiplication, 2D convolution, 3D convolution, or linear equation solver. Applications of polybench are considered as a core of many applications for high-performance like image processing [30]. The details of selected applications and prediction model are presented in following subsections:

4.1 Application Dataset Generation

We have selected 20 applications in total from both Polybench and AMD benchmarks. These applications are executed with different input data sizes both on CPU and GPU. The details of benchmark suit, their application, and input size is given in Table 4.1. A total 13 applications from Polybench and 7 applications from AMD suite are executed. There are 1165 jobs in total which are executed on both CPU device and GPU device. The CPU time is the execution time of the application on CPU device whereas the GPU time is the execution time of application on GPU device.

Table 4.1

Detail of Benchmark Suite and Input Size
Serial #	Suits	Benchmark Applications	Input Data Size
1	Polybench	GEMM	1–4600
2	Polybench	3MM	1–4600
3	Polybench	GESUMMV	1–14500
4	Polybench	ATAX	1–22000
5	Polybench	2MM	1–22000
6	Polybench	MVT	1–15500
7	Polybench	BICG	1–22000
8	Polybench	CORRELATION	1–2800
9	Polybench	COVARIANCE	1–2600
10	Polybench	FDTD-2D	1 − 12000
11	Polybench	GRAMSCHMIDT	1–8800
12	Polybench	SYR2K	1–2200
13	Polybench	SYRK	1–3000
14	AMD	Binomial Option	1–20000000
15	AMD	Bitonic Sort	512–20000000
16	AMD	Discrete Cosine Transformation	1–8192
17	AMD	Fast Walsh Transform	1–100000000
18	AMD	Floyd Warshall	1–15500
19	AMD	Matrix Multiplication	128–12500
20	AMD	Matrix Transpose	1024–10000000000

The results of our application testing on CPU and GPU are as follows. We discover that FDTD-2D application have less execution time on GPU device at every input size. The ATAX application have less execution time on CPU device at every input size (starting from 1 and maximum of 22000 as shown in Table 4.1). For all other applications, less execution time on CPU at some input sizes whereas less execution time on GPU device is observed for some other input sizes. We generate two datasets with input size and execution time of the program. One dataset contains input sizes and corresponding execution times on CPU device whereas the other dataset contains the program execution times on GPU device for the same list of input sizes.

4.2 Feature Extraction

In addition to input size and execution time, the program features are also part of our dataset. The static code analyzer is designed for the extraction of features from the kernel code of OpenCL programs of two benchmark suite i.e., Polybench and AMD. The extracted features set shows the behavior of the programs. The aim of the extraction of features from the code is to collect the attributes of the OpenCL programs from both benchmarks. The Clang (front end) compiles the code of OpenCL programs to ensure the code is error free. The LLVM passes extracts the code features. Figure 4.1 shows the complete methodology of extraction of the features from the OpenCL programs.

In this work we have extracted 22 features from the OpenCL application programs. These features consist of number of loops, number of int data types, number of float data types, total number of functions etc. Table 4.2 demonstrates all the extracted features from OpenCL programs through clang and LLVM.

Table 4.2

Static Code Extracted Features
Serial Number	Feature Name
1	Total number of Return Statement
2	Total number of Control Statement
3	Total number of Allocation Instruction
4	Total number of Load Instruction
5	Total number of Store Instruction
6	Total number of Multiplication (Float Data type) Operation
7	Total number of Multiplication (Integer Data type) Instruction
8	Total number of Division (Float Data type) Instruction
9	Total number of Division (Integer Data type) Instruction
10	Total number of Condition Check Instruction
11	Total number of Addition (Float Data type) Instruction
12	Total number of Addition (Integer Data type) Instruction
13	Total number of Subtraction (Float Data type) Instruction
14	Total number of Subtraction (Integer Data type) Instruction
15	Total number of Function Call Instruction
16	Total number of Functions
17	Total number of Blocks
18	Total number of Instructions
19	Total number of Float Operation
20	Total number of Integer Operation
21	Total number of Loop Operation
22	Total number of Loops

Two datasets are generated from the static code features and input size along with the execution time of the program on processing devices. One dataset contains the code feature set, input size and the program execution time on CPU device and the other dataset contain the code feature set, input size and program execution time on GPU device. These datasets (after feature selection as explained below) are used for training and testing of machine learning predictor. The details regarding training and testing of different machine learning models are presented in Section 5.

4.3 Feature Selection

Our next task is to identify more relevant features out of these 22 extracted features. The feature selection means to find out importance of features by finding correlation of each feature with another feature. The selection of important feature is very crucial because it causes reduction in over fitting, improves the accuracy, and reduces the training time of the classifier. We use Pearson correlation [32] which is a filter-based correlation analysis method and widely used for finding correlation between features.

According to Pearson correlation method the two features are correlated if change in the value of one feature causes change in another feature’s value. If increase in one feature’s value causes increase in other feature’s or decrease in one feature’s value causes a decrease in another feature’s value, the two features are correlated positively. Similarly, if decrease in the value of a feature causes increase in other feature’s value or increase in one feature’s value causes decrease in another feature’s value, the two features are correlated negatively. Using positively correlated features for training purposes causes lower prediction accuracy as demonstrated in [33]. Therefore, in our study we select negatively correlated features.

In this study we use Heatmap [34] which is a tool to visualize the correlation between features. Figure 4.2 shows the matrix of the correlation of features which are listed in Table 4.2. The two features having value 1 or tends to 1 are positively correlated and features having values negative or tends to a negative value are negatively correlated. Out of 22 features, we find that 8 features have positive while 14 features have negative correlation with other features. The following 8 features have positively correlation with other features: “Total number of Return Statements”, “Total number of Store Instructions”, “Total number of Division (Integer Data type) Instruction”, “Total number of Subtraction (Integer Data type) Instruction”, “Total number of Functions”, “Total number of Blocks”, “Total number of Float Operation”, and “Total number of Loops”. Similarly, for the following 14 features the negative correlation is found with the other features: “Total number of Control Statement”, “Total number of Allocation Instruction”, “Total number of Load Instruction”, “Total number of Multiplication (Float Data type) Operation”, “Total number of Multiplication (Integer Data type) Operation”, “Total number of Division (Float Data type) Instruction”, “Total number of Condition Check Instruction”, “Total number of Addition (Float Data type) Instruction”, “Total number of Addition (Integer Data type) Instruction”, “Total number of Subtraction (Float Data type) Instruction”, “Total number of Function Call Instruction”, “Total number of Functions”, “Total number of Integer Operation”, and “Total number of Loop Operation” are negatively correlated features.

The features having correlation value less than or equal to -0.1 are selected and used by the machine learning model for predicting execution time on CPU and GPU devices. The selected features are shown in Table 4.3.

Table 4.2

List of Selected Features
Serial Number	Feature Name
1	Total number of Allocation Instruction
2	Total number of Multiplication (Float Data type) Operation
3	Total number of Division (Float Data type) Instruction
4	Total number of Condition Check Instruction
5	Total number of Subtraction (Float Data type) Instruction
6	Total number of Function Call Instruction
7	Total number of Instructions
8	Total number of Integer Operation
9	Total number of Loop Operation

4.4 Machine Learning Model Selection

The next step is to use our datasets (with selected code features and input size) for the training of machine learning model. We use supervised machine learning models. The supervised machine learning has further two types: classification and regression. Classification is type of supervised learning in which the output class label is categorical (discrete) while the regression has numerical (continuous) output class label. In this research regression models are used since our output class labels are CPU execution time and GPU execution time are numeric values.

The complete working strategy is depicted in Fig. 4.3. After the Pre-processing completes, feature selection is applied on the dataset, important and influential features are selected from the available extracted features for training and testing of the machine learning models. We use three different machine learning models in this regard i.e., Multiple Linear Regression, Random Forest Regression, and Gradient Boosting Regression models. The comparative study and results of these models are presented in next section.

We first discuss our experimental setup in section 5.1 and then the results are presented in section 5.2 and 5.3 respectively. In section 5.2, we measure the error margins of our machine learning predictor. For instance, the difference between the predicted execution time on a device (CPU or GPU) and actual execution time that depicts the error. In section 5.3, we compare the performance of work stealing scheduling algorithm (as a part of proposed solution) with other scheduling schemes.

5.1 Experimental Setup

We use two computer systems to perform the experiments. The first system is used for the generation of dataset. Once the dataset is generated it is passed to second computer system where the machine learning predictor is implemented. Once the decision is made by the predictor regarding device suitability the tasks are handed over to the scheduler. The scheduler (work stealing and others for comparison described later in section 5.3) is implemented on the same first machine which is used earlier for the generation of dataset.

The hardware specification of computer system used to implement machine learning predictor are provided in Table 5.1 For the implementation of the machine learning model, the Python programming language is used on windows platform. We use PyCharm version 2019.2.3 professional edition toolkit and Jupiter notebook IDE along with Python version 3.6. As mentioned earlier, we have evaluated different regression models which are multiple linear regression, random forest, and gradient boosting.

Table 5.1

Hardware specification of computer system used to implement ML predictor
Device	Specification
Operating System	Windows 10 pro
CPU	Intel Core M-7Y30
System type	64 bits
Processors	1.00 GHz and 1.6 GHz
Primary Memory	8.00 GB
Secondary Memory	1 TB

The hardware specifications of the computer system used to implement task scheduler are provided in Table 5.2. It is a CPU (Intel)-GPU (NVIDIA) system with Linux Ubuntu 16.04 Operating system installed.

Table 5.2

Hardware specification of computer system used to implement task scheduler
Device	CPU	GPU
Architecture	Haswell	Kepler
Processor Number	Intel Core i5-4460	GeForce GTX 760
Number of Cores	4	1152
Number of Thread	4	-
Memory	8.00 GB	2 GB
Memory Bandwidth	25.6 GB/s	192.2 GB/s
Performance	409.6 GFLOPS	2257.9 GFLOPS
ISP	32	2
Memory Speed	1600Mhz	6.0 Gbps
OpenCL SDK	Intel SDK for OpenCL 2016	CUDA 8.0
Compiler	GCC 5.4.0	Nvcc

5.2 Machine Learning Predictor

We execute applications both on CPU and GPU devices and record their execution times. This information is used to create two datasets i.e., CPU dataset and GPU dataset. The CPU dataset contains values of nine important features, input size, and execution time on CPU device whereas GPU dataset contains same nine features, input size, and execution time on GPU device. These datasets are used for training and testing the machine learning model for the prediction of the execution time of programs on CPU device and GPU device. The shape of datasets is 1165 tuples (rows) and 11 columns (nine selected features from code as listed in Table 4.2, input size and execution time). We train two models i.e., CPU model and GPU model. The CPU model is trained on CPU dataset to predict the execution time on CPU whereas GPU model is trained on GPU dataset to predict execution time of programs on GPU. We split our dataset (either CPU or GPU model) into two parts with the ratio of 20% and 80%. Table 5.3 shows that 80% of the dataset is provided to machine learning model for training purpose. The remaining 20% is used for testing and evaluating the trained model.

Table 5.3

Detail of Dataset used for Prediction
Set	Instances	Percentage
Training set	931	80%
Testing set	234	20%
Complete dataset	1165	100%

The concept of performance evaluation in regression is that comparing the predicted values with the actual values. The predicted execution time on CPU device using all three machine learning models is compared to the actual execution time as measured manually and added as actual execution time in dataset.

The Fig. 5.1 (a-f) shows the correlation of actual and predicted values of machine learning models. When the actual and predicted values are overlapped it indicates that the model has predicted the execution time with maximum accuracy. In Fig. 5.1 (a-c) we compare actual and predicted values (of execution time) on CPU device using random forest, gradient boosting and multiple linear regression models respectively.

Similarly, in Fig. 5.1 (d-f), we compare actual and predicted execution time on GPU device instead. In both cases, it can be noticed that actual and predicted curves are overlapped mostly in case of random forest and gradient boosting whereas a clear difference between predict and actual values can be noticed for multiple linear regression. These results indicate that prediction of random forest and gradient boosting is better than multiple linear regression. However, there is no clear difference is noticed between the accuracy of random forest and gradient boosting.

To get better insight about the accuracy of the machine learning models, we measure the error rate of the predictive machine learning models for regression by evaluating multiple performance metrics like R², Root Mean Square Error (RMSE), and Mean Absolute Error (MAE).

Mean Absolute Error (MAE) shows the difference of the actual values and predicted values. It is the average absolute difference on the dataset. The formula of Mean Absolute Error is:

MAE = \(\frac{1}{N}{\sum }_{i=1}^{N}|yi-\widehat{y}|\) (2)

N - total number of tuples

Yi – Actual value

\(\widehat{y}\) \(–\) Predicted value of y

Figure 5.2 is the representation of MAE. In the case of mean absolute error, the lower the value the precise the model is and vice versa. In our prediction analysis the random forest has the smallest values as compared to both gradient boosting and multiple linear regression.

Root Mean Square Error is the square root of the Mean Square Error.

RMSE = \(\sqrt{MSE}\) = \(\sqrt{{\sum }_{i=1}^{N}{(yi-\widehat{y})}^{2}}\) (3)

It is the standard deviation of the prediction error from the line of best fit. In case of root mean square error the smaller the value the lower the error in the model and vice versa. Figure 5.3 shows the comparison of the values of the RMSE of the machine learning models. It can be noticed that random forest performed the best with minimum value of 1.63 for GPU and 8.68 for CPU.

R² is co-efficient of determination. It shows the co-efficient that how accurate the predicted values fit as compared to the actual values. R-Squared is normally in the range of 0 and 1. The higher the R-Squared value the better the model is and smaller the R-Squared value inferior the model is. The formula of the R-Squared is

R-Squared = 1 - \(\frac{{\sum (yi-\widehat{y})}^{2}}{{\sum \left(yi-\stackrel{-}{y}\right)}^{2}}\) (4)

\(\stackrel{-}{y}\) – Mean value of y

R² is in the range of 0 and 1. The 0 mean 0% and 1 mean 100% but the percentage does not show the accuracy. It only indicates the fitting of actual and predicted values. The Fig. 5.4 shows the comparison of R² values of multiple linear regression, gradient boosting, and random forest models. In our case the random forest and gradient boosting models fits very accurately as compared to multiple linear regression. However, the random forest is slightly better than gradient boosting models. But multiple linear regression model is almost 88% lower than both models. The poor performance of multiple linear regression is likely because the data is not in linear form.

Our results demonstrate that random forest provides more accurate predicted values as compared to gradient boosting and multiple linear regression. Therefore, predicted execution time by random forest model is further utilized for the designing of task scheduler. To be more precise, in our proposed solution, we combine random forest machine learning model (for device prediction) with work stealing task scheduler.

5.2 Performance evaluation of work stealing based task scheduler

As we discussed in section 3.2, after predictor’s decision tasks are placed either on CPU queue or GPU queue. It is then responsibility of task scheduler to select a program for processing on a device. In this context, we compare the performance of work stealing algorithm with other scheduling alternatives. It is important to mention that work stealing algorithm itself is not our contribution since the algorithm is the part of existing literature. However, we propose work stealing algorithm as a part of our proposed solution. We believe that work stealing algorithm is well suited in our scenario where CPU becomes idle (more likely) after running the host part of a program and work stealing makes it busy by selecting jobs from GPU queue. We describe some other scheduling alternatives as well and make a performance comparison of these alternatives with work stealing based task scheduler.

CPU Only

In CPU Only, all programs are executed only on the CPU device without any evaluation that a program is CPU suitable or GPU suitable (GPU remains idle). It is considered as a baseline and is used as standard for the evaluation of the proposed work-stealing scheduler [13].

GPU Only

In GPU Only, all the programs are assigned to only GPU device and in this case CPU remains idle [13]. The GPU Only is also considered as baseline and standard for evaluation of the work-stealing scheduler.

First Come First Serve

In First Come First Serve (FCFS) scheduling, programs are processed in the order of arrival and a free device is used for the processing of the program. For instance, both CPU and GPU are free in the beginning and program P1 is assigned to CPU. Now the only free device is GPU and therefore program P2 will be processed on GPU and so on.

Device Suitability

In device suitability evaluation, the programs are assigned to their suitable devices. Suitable device means a job has less execution time on that device [13]. It is different than our proposed solution since we combine device suitability with work stealing algorithm. In device suitability only, it is not possible to select a job from another queue. For instance, it is not allowed to select a job from GPU queue for execution on CPU device (although the CPU is idle at that time).

Alternate Assignment

In alternate assignment the programs (in a queue) are first shuffled and then assigned alternatively to the CPU and GPU processing device [13]. For instance. First program will be assigned to CPU, second will be assigned to GPU, third to CPU, fourth to GPU and so on. In this research the programs are randomly shuffled many times. We have evaluated many different combinations in this regard. When we shuffle programs once it is called as Alternate Assignment 1, when shuffled twice it is called Alternate Assignment 2. Similarly, we have tried Alternate Assignment 3, Alternate Assignment 4, and Alternate Assignment 5 (i.e., shuffled five times before assignment on a device).

Input Size

All the jobs are sorted in descending order based on their input sizes. Half of the jobs from the top of the queue are assigned to GPU device while the remaining jobs are assigned to CPU device. The job having largest value of input size is executed on GPU device while the job having smallest input size is executed on CPU device [2].

The performance of work stealing based task scheduler is compared against aforementioned scheduling alternatives. In this research, total 120 programs are selected from two benchmarks suits polybench and AMD. The job pool contains 35 CPU suitable jobs and 85 GPU suitable jobs that are determined by predictor. CPU suitable means the jobs have less predicted execution time on CPU while GPU suitable jobs have less predicted execution time on GPU. Three performance metrics are used for evaluation which are execution time, throughput, and utilization of devices. The Fig. 5.5 provides the comparison of all aforementioned scheduling heuristics in terms of execution time. This is the total execution time taken by either CPU or GPU to execute all assigned program according to a specific scheduling heuristic.

The Fig. 5.5 shows that all assigned tasks are completed in 34.5 seconds in case of work stealing based scheduler which depicts the overall best performance as compared to other approaches. The CPU bar for work stealing based scheduler shows that all tasks assigned to CPU are completed in 32.2 seconds whereas all tasks assigned to GPU are completed in 34.5 seconds. It means that after 32.2 seconds CPU becomes idle, but GPU continues job execution that completes at 34.5 seconds. Thus, all assigned tasks are completed in 34.5 seconds which is the best result in comparison to other approaches. The difference between CPU and GPU execution time is marginal for work stealing whereas it is quite significant for other approaches. It is because of load balancing attribute of work stealing algorithm.

We also notice that CPU execution time of work stealing is lower than all other approaches except device suitability where execution time is 19.8 seconds as compared to 32.2 seconds for work stealing. However, the load is not balanced on device suitability, and it results in a higher execution time for GPU device. It is 39.6 seconds for device suitability as compared to 34.5 seconds for work stealing based scheduler. It means work stealing is better in overall performance since it completes all tasks in 34.5 seconds whereas device suitability takes 39.6 seconds. Similarly, GPU execution time of proposed solution is the lowest except the alternate assignment 5. The alternate assignment 5 has lower execution time on GPU device but more execution time on CPU device as compared to the proposed scheduler. As a result, the overall performance of proposed solution is better.

The Fig. 5.6 shows comparison of throughput of the proposed scheduler with other heuristics. The throughput is defined as follows:

Throughput = Total execution time of programs/ total number of programs (5)

Since the total execution time of work stealing based scheduler is the minimum whereas the total number of programs are the same for all alternatives, it results in maximum throughput for our proposed solution.

The Fig. 5.7 shows the utilization of devices by different schedulers. It is the measure of time for which a device remains idle. For instance, in case of work stealing, the CPU becomes idle at 32.2 seconds and remains idle until 34.5 seconds when GPU completes the assigned tasks. In this case, the idle time of CPU is 2.3 seconds which is 6.66% of total time of 34.5 seconds. In this case we have 100% GPU utilization whereas CPU utilization is 93.34% as shown in Fig. 5.7 (0.93). The graph shows that none of the schedulers have more utilization of devices than the proposed scheduler. When all jobs are executed on CPU device only, it means 0% utilization of GPU device since it remains idle all the time. Similarly, for GPU device only, CPU remains idle all the time. When the jobs are executed using first come first serve scheduler, 82% device utilization is achieved. Similarly, the device utilization is below 93% for all other scheduler which depicts best resource utilization of the proposed solution.

The experimental results in Fig. 5.5, 5.6, and 5.7 shows that the proposed scheduling scheme outperforms all other schemes in terms of overall execution time of job, utilization of processing devices and throughput. We believe that better performance of our proposed approach is because of two factors. First, we use machine learning based predictor to find a suitable device for a task (with less execution time). Second, we use load balancing using work stealing algorithm that exploit efficient utilization of both (CPU and GPU) devices. The rest of the scheduling heuristics are not considering or combining these two factors while making a scheduling decision. For instance, device suitability is not considered except for device suitability scheduling algorithm. However, device suitability is not incorporating load balancing which make it less efficient than proposed solution.

In this research, a novel framework is proposed that is based on machine learning based job execution time predictor and load balancer using work stealing algorithm. The programmer maps jobs to processing devices (i.e., CPU and GPU) in a heterogeneous system However, it is not always straightforward to find a suitable device for a particular task. Therefore, we have proposed a machine learning based predictor that can predict suitable device with a marginal error rate. We have compared three different machine learning algorithms and our results demonstrate that random forest performed better with minimum error as compared to other alternatives of multiple linear regression and gradient boosting.

To predicting the device suitability alone is not enough to efficiently utilize the system resources. The mapping of a job to a suitable device may cause offered load imbalance between devices. For instance, one device might be overloaded since it is suitable device for many jobs and thus the other device is under loaded and becomes underutilized. The decision of the job’s assignment should be balanced to achieve the maximum utilization of devices and reduction in execution time of all jobs. We have demonstrated that work stealing based task scheduler balances the workload on both devices and thus achieves much better performance (in terms of total execution time, throughput and device utilization) as compared to other scheduling heuristics.

In our proposed solution, scheduler maps only static jobs to processing devices and considers only the integrated Graphics processing units. In future, this framework can be extended to dynamic allocation of jobs to processing devices along the usage of discrete graphic processing units.

Ethical Approval

Not applicable

Competing interests

I declare that the authors have no competing interests as defined by Springer, or other interests that might be perceived to influence the results and/or discussion reported in this paper.

Authors' contributions

Mr. Asad Hayat is the lead author in this research. He conducts this research work under the supervision of Dr. Yasir Noman Khalid and Dr. Muhammad Siraj Rathore. He performed all experiments and wrote up the first draft.

Dr. Yasir as a supervisor helped Asad Hayat in formulating research problem statement. In addition, in regular meetings he helped Asad Hayat to find out the answers of the following questions. How performance of difference applications should be compared? What are the important performance metrics? Which are the interesting experiments to be performed. He also reviewed the second draft of the paper. The outcome of this review work was the third draft.

Dr. Siraj also supervised Mr. Asad. He helped Asad mainly in paper write up. How this research article should be organised? how to present data in a structured form? what figures and tables are interesting to include in this paper? where to place different figures and tables? The first draft is written by Asad, which is then extensively reviewed (and re-written at some places where needed) by Dr. Siraj. The outcome of this work was the second draft.

Mr. Muhammad Nadeem Nadir contributed by plotting all figures in this research article. He also proof-read the third draft. The final draft is an outcome of this proof reading.

Funding

Not applicable. No funding

Availability of data and materials

Available on request

N. Tsog, M. Becker, F. Bruhn, M. Behnam, and M. Sjodin, “Static Allocation of Parallel Tasks to Improve Schedulability in CPU-GPU Heterogeneous Real-Time Systems,” IECON Proceedings (Industrial Electronics Conference), vol. 2019-Octob, pp. 4516–4522, 2019, doi: 10.1109/IECON.2019.8926767.
Y. Wen, Z. Wang, and M. F. P. O’Boyle, “Smart multi-task scheduling for Open CL programs on CPU/GPU heterogeneous platforms,” 2014. doi: 10.1109/HiPC.2014.7116910.
U. Ahmed, J. C. W. Lin, G. Srivastava, and M. Aleem, “A load balance multi-scheduling model for OpenCL kernel tasks in an integrated cluster,” Soft Computing, vol. 25, no. 1, pp. 407–420, Jan. 2021, doi: 10.1007/s00500-020-05152-8.
Y. N. Khalid, M. Aleem, R. Prodan, M. A. Iqbal, and M. A. Islam, “E-OSched: a load balancing scheduler for heterogeneous multicores,” Journal of Supercomputing, vol. 74, no. 10, pp. 5399–5431, Oct. 2018, doi: 10.1007/s11227-018-2435-1.
U. Ahmed, M. Aleem, Y. Noman Khalid, M. Arshad Islam, and M. Azhar Iqbal, “RALB-HC: A resource-aware load balancer for heterogeneous cluster,” in Concurrency and Computation: Practice and Experience, Jul. 2021, vol. 33, no. 14. doi: 10.1002/cpe.5606.
T. Wenjie, Y. Yiping, Z. Feng, L. Tianlin, and S. Xiao, A work-stealing based dynamic load balancing algorithm for conservative parallel discrete event simulation. 2017. doi: 10.1109/WSC.2017.8247833.
M. E. Belviranli, L. N. Bhuyan, and R. Gupta, “A dynamic self-scheduling scheme for heterogeneous multiprocessor architectures,” Transactions on Architecture and Code Optimization, vol. 9, no. 4, Jan. 2013, doi: 10.1145/2400682.2400716.
H. J. Choi, D. O. Son, S. G. Kang, J. M. Kim, H. H. Lee, and C. H. Kim, “An efficient scheduling scheme using estimated execution time for heterogeneous computing systems,” Journal of Supercomputing, vol. 65, no. 2, pp. 886–902, Aug. 2013, doi: 10.1007/s11227-013-0870-6.
R. Kaleem, R. Barik, T. Shpeisman, B. T. Lewis, C. Hu, and K. Pingali, “Adaptive heterogeneous scheduling for integrated GPUs,” Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT, vol. 14, pp. 151–162, 2014, doi: 10.1145/2628071.2628088.
A. Ghose, L. Dokara, S. Dey, and P. Mitra, “A Framework for OpenCL Task Scheduling on Heterogeneous Multicores,” Parallel Processing Letters, vol. 27, no. 3–4, Dec. 2017, doi: 10.1142/S0129626417500086.
K. Moren and D. Göhringer, “Automatic Mapping for OpenCL-Programs on CPU/GPU Heterogeneous Platforms,” Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10861 LNCS, pp. 301–314, 2018, doi: 10.1007/978-3-319-93701-4_23.
B. Taylor, V. S. Marco, and Z. Wang, “Adaptive optimization for OpenCL programs on embedded heterogeneous systems,” ACM SIGPLAN Notices, vol. 52, no. 5, pp. 11–20, Sep. 2017, doi: 10.1145/3140582.3081040.
Y. N. Khalid, M. Aleem, U. Ahmed, M. A. Islam, and M. A. Iqbal, “Troodon: A machine-learning based load-balancing application scheduler for CPU–GPU system,” Journal of Parallel and Distributed Computing, vol. 132, pp. 79–94, 2019, doi: 10.1016/j.jpdc.2019.05.015.
D. Grewe and M. F. P. O’Boyle, “A static task partitioning approach for heterogeneous systems using OpenCL,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2011, vol. 6601 LNCS, pp. 286–305. doi: 10.1007/978-3-642-19861-8_16.
M. Boyer, K. Skadron, S. Che, and N. Jayasena, “Load balancing in a changing world: Dealing with heterogeneity and performance variability,” 2013. doi: 10.1145/2482767.2482794.
P. Huchant, M. C. Counilh, and D. Barthou, “Automatic OpenCL task adaptation for heterogeneous architectures,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2016, vol. 9833 LNCS, pp. 684–696. doi: 10.1007/978-3-319-43659-3_50.
Y. Wen and M. F. P. O’Boyle, “Merge or separate? Multi-job scheduling for OpenCL Kernels on CPU/GPU Platforms,” Proceedings of the General Purpose GPUs, GPGPU-10 2017, pp. 22–31, Feb. 2017, doi: 10.1145/3038228.3038235.
Z. Wang, L. Zheng, Q. Chen, and M. Guo, “CAP: Co-scheduling based on asymptotic profiling in CPU+GPU hybrid systems,” in Proceedings of the 2013 International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM 2013, 2013, pp. 107–114. doi: 10.1145/2442992.2443004.
M. A. Dávila Guzmán, R. Nozal, R. Gran Tejero, M. Villarroya-Gaudó, D. Suárez Gracia, and J. L. Bosque, “Cooperative CPU, GPU, and FPGA heterogeneous execution with EngineCL,” Journal of Supercomputing, vol. 75, no. 3, pp. 1732–1746, Mar. 2019, doi: 10.1007/s11227-019-02768-y.
J. Lee, M. Samadi, and S. Mahlke, “Orchestrating Multiple Data-Parallel Kernels on Multiple Devices,” 2015. doi: 10.1109/PACT.2015.14.
E. Canhasi, “Evaluating the efficiency of CPUs, GPUs and FPGAs on a near-duplicate document detection via OpenCL,” Journal of Computer Science, vol. 14, no. 5, pp. 699–704, 2018, doi: 10.3844/jcssp.2018.699.704.
X. Liu, H. A. Ounifi, A. Gherbi, W. Li, and M. Cheriet, “A hybrid GPU-FPGA based design methodology for enhancing machine learning applications performance,” Journal of Ambient Intelligence and Humanized Computing, vol. 11, no. 6, pp. 2309–2323, Jun. 2020, doi: 10.1007/s12652-019-01357-4.
S. Alsubaihi and J. L. Gaudiot, “A runtime workload distribution with resource allocation for CPU-GPU heterogeneous systems,” Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2017, pp. 994–1003, 2017, doi: 10.1109/IPDPSW.2017.19.
J. Lee, M. Samadi, Y. Park, and S. Mahlke, “SKMD: Single kernel on multiple devices for transparent CPU-GPU collaboration,” ACM Transactions on Computer Systems, vol. 33, no. 3, Aug. 2015, doi: 10.1145/2798725.
M. Becchi, S. Byna, S. Cadambi, and S. Chakradhar, “Data-aware scheduling of legacy kernels on heterogeneous platforms with distributed memory,” in Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2010, pp. 82–91. doi: 10.1145/1810479.1810498.
A. Munshi, “The OpenCL specification,” 2009 IEEE Hot Chips 21 Symposium, HCS 2009, pp. 11–314, 2016, doi: 10.1109/HOTCHIPS.2009.7478342.
Z. Wang and M. O’Boyle, “Machine Learning in Compiler Optimization,” 2018. doi: 10.1109/JPROC.2018.2817118.
Y. Wang, W. Ji, F. Shi, and Q. Zuo, A work-stealing scheduling framework supporting fault tolerance. 2013. doi: 10.7873/date.2013.150.
“Scheduler — CAF 0.17.5 documentation.” https://actor-framework.readthedocs.io/en/0.17.5/Scheduler.html (accessed Jul. 21, 2022).
F. Kreiliger, J. Matejka, M. Sojka, and Z. Hanzálek, “Experiments for Predictable Execution of GPU Kernels,” 2019. Accessed: Jul. 21, 2022. [Online]. Available: https://dspace.cvut.cz/handle/10467/86755

No competing interests reported.

Download PDF

Editorial decision: Major revision
11 Mar, 2023
Reviews received at journal
21 Feb, 2023
Reviewers agreed at journal
18 Feb, 2023
Reviewers agreed at journal
18 Feb, 2023
Reviewers invited by journal
18 Feb, 2023
Editor assigned by journal
08 Nov, 2022
Submission checks completed at journal
08 Nov, 2022
First submitted to journal
08 Nov, 2022

You are reading this latest preprint version

A Machine Learning based Resource Efficient Task Scheduler for Heterogeneous Computer Systems

Status:

Version 1

Abstract

Figures

1 Introduction

2 Related Work

2.1 Scheduling Schemes for Heterogeneous Computer Systems

2.2 Scheduling Schemes based on Prediction Models

2.3 Analysis of Existing Literature

3. Design Of Proposed Predict Device Load Balance (Pdlb) Task Scheduler

3.1 Device selection using machine learning based predictive model

3.2 Load Balancer

4. Machine Learning Based Prediction Model

4.1 Application Dataset Generation

4.2 Feature Extraction

4.3 Feature Selection

4.4 Machine Learning Model Selection

5. Results And Discussions

5.1 Experimental Setup

5.2 Machine Learning Predictor

5.2 Performance evaluation of work stealing based task scheduler

6. Conclusion And Future Work

Declarations

References

Additional Declarations

Status:

Version 1