# Affinity-Based Task Scheduling on Heterogeneous Multicore Systems Using CBS and QBICTM
## 2 Materials and Methods
### Clunk-Based Scheduler (CBS)  
We performed load balancing on a heterogeneous multicore system by proportionately dividing the total load into multiple chunks of variable sizes according to the various processing speeds of all the respective cores. The Bayesian generative model gives the list of dependent and independent tasks in the form of posterior data as an output. All tasks, whether dependent or independent, are listed together without making clusters. Similar or dependent tasks are listed in a contiguous manner. All tasks that are to be processed are present in a single list that functions like a queue, where each task is requesting allocation to the core in order to be processed. Tasks are then divided into chunks that may differ in size according to the respective processing speeds of the cores. The computing power or capacity of each core in a heterogeneous system is predetermined, with each core taking a job or task from its private queue. The largest chunk of tasks is allocated to the fastest core. All the tasks in a chunk are put into the core's private queue. In the same way, each core gets a chunk of tasks with respect to its computing capacity, the smallest chunk being given to the slowest core in the heterogeneous multicore system. This results in each core being proportionately loaded, the fastest core being more heavily loaded and the slowest core processing fewer jobs or tasks, each according to its capacity. Figure 3 shows how the CBS technique is applied in the system. Workloads consisting of multiple tasks are not distributed evenly and fairly across the cores because that would result in some cores being overloaded but because of the heterogeneous nature of the system under use, the fastest core which processes tasks at much higher speeds receive more of the load. The proportionate allocation of more tasks to the faster cores and fewer to the slower cores means all cores are more fully utilized and jobs or tasks are more likely to be completed in the same time. Ideally, no core is overloaded and no core is left idle. The fastest core might be idle when other cores are still operating and processing the tasks but we have made sure that the fastest core has already executed a larger portion of the tasks that were to be processed. Table 1 provides the description of the terms used in the research. The number of tasks in each chunk is computed using  
\[f_{n}=\sum_{i=1}^{e}f_{i} \tag{7}\]  
\[ \begin{split} pc_{1}&=c_{1}f_{1}\\ pc_{2}&=c_{2}f_{2}\\ &\vdots\\ pc_{p}&=c_{m}f_{e}\end{split}  \tag{8}\] \begin{table}
\begin{tabular}{c c} \hline
**Notation** & **Description** \\ \hline \(C=\{c_{1},c_{2},\dots,c_{m}\}\) & Set of cores in a heterogeneous multicore architecture \\ \(c_{e}\) & Total cores available \\ \(T=\{t_{1},t_{2},\dots,t_{t}\}\) & Set of tasks \\ \(t_{t}\) & Total tasks to be processed \\ \(C_{k}=\{k_{1},k_{2},\dots,k_{c}\}\) & Chunks of tasks equal to the number of cores available \\ \(F=\{f_{1},f_{2},\dots,f_{e}\}\) & Computing max frequency of all the cores \\ \(f_{n}\) & Total/max processing speed of the system \\ \hline \end{tabular}
\end{table} 
Table 1: Description of the terms used. Figure 3: Allocation of tasks to cores by CBS. Each chunk is of variable size and contains different number of tasks. \[ \begin{split} k_{1}&=\left[\frac{pc_{1}}{J_{n}}\times t _{t}\right]\\ k_{2}&=\left[\frac{pc_{2}}{J_{n}}\times t_{t}\right]\\ &\vdots\\ k_{c}&=\left[\frac{pc_{p}}{J_{n}}\times t_{t}\right]\end{split}  \tag{9}\]  
Algorithm 1 describes the working mechanism of CBS. All the tasks that are to be processed are divided into various-sized chunks. The next step is to calculate the processing speed of each of the cores in the multicore architecture. Once the processing speed of each of the cores is determined, the chunks are allocated to the cores by considering each core's speed, i.e., workload is allocated proportionate to each core's processing speed. The fastest core in a multicore architecture gets the largest chunk of tasks, the smallest chunk being allocated to the slowest core.