# Affinity-Based Task Scheduling on Heterogeneous Multicore Systems Using CBS and QBICTM
## 1 Introduction  
Multicore systems usually operate in a shared resource environment. They must cooperate in order to process sharable resources, especially the cache. Caches in multicore systems are private as well as shared. Task scheduling in heterogeneous multicore systems is mainly dependent on how the various tasks are distributed among all available cores [1]. The processing power of each core in a heterogeneous system is different, so distributing the workload according to each core's maximum capacity or efficiency is essential. Thus, the computing power of each core has to be considered. Shared caches play a vital role in increasing the throughput of the overall system, but dependent tasks need to be scheduled concurrently [2]. The prime objective of multicore systems is to execute many tasks in considerably less time. In such circumstances, the role of the cache memory is vital and, if tasks are scheduled on a non-affinity basis, the cache miss rate will increase significantly [3]. When a higher priority task requests use of the CPU, the system grants that task processing priority over the currently running lower priority task. In granting this priority, the higher priority task wipes the data of the previously running lower priority task from the cache resulting in wastage of time as the system will have to bring back the same data into the cache from off chip memory when processing of the lower priority task resumes [4]. The affinity-based scheduling of tasks maximizes the cache hit rate which reduces the overall execution time of the total volume of tasks [5, 6]. The slower nature of some cores in aheterogeneous multicore system negatively affects the overall performance of the system. The cores in heterogeneous systems operate at different computing speeds, thus, even after equal distribution of the workload, the slowest core might end up being overloaded while, at the same time, the fastest core remains idle, doing nothing [7]. Heuristics have been proposed for affinity-based scheduling of tasks using task migration in NUMA (non-uniform memory access) multicore systems [8]. The identical or dependent tasks in a multicore system are scheduled on the same core, thereby reducing the cache thrashing while maximizing the cache hit rate [9]. In multicore systems, shared caches operate between the CPU and the off-chip memory, mainly random access memory (RAM). [PERSON] et al. [10] proposed a completely fair scheduler (CFS) that uses classification to allocate the tasks on the cores in a way that tasks scheduled on the same core use the core's shared cache without thrashing the data of other tasks in the cache. Several heuristics are proposed for the concurrent scheduling of tasks that share the same cache content and cooperate to improve cache performance [11; 12]. The overhead of shared caches in multicore systems has been considered in the context of WCET (worst case execution time) analysis [13]. Several shared cache partitioning mechanisms have been proposed to reduce cache interference and thrashing [14; 15]. Classifying the dependent tasks together into a same cluster using different algorithmic approaches is proposed [16; 17]. Algorithms have been proposed to predict the possible dependency ratios among the tasks that are to be processed [18; 19; 20]. Some tasks have read or write dependencies on other tasks for certain memory locations; in such cases, the task waits for a certain memory location to be written which is later read by that task and then carries on with its execution [21; 22]. The total number of interactions between certain tasks indicates the level of dependency the tasks are having [23]. The affinity relations between multiple queries is checked and closely related queries are assigned to the same cache structure [24]. Affinity scheduling allows multiple tasks to execute more quickly due to locality of the data, cache utilization or interaction with other tasks [25].