Mathematical representation of the Hardware Round-Robin Scheduler analytical model for single-ISA heterogeneous architectures

Introduction Over the past few years, hardware chip manufacturers have been shifting strategies to overcome the well-known Power Wall which imposes the practical limitations to increasing CPU performance by raising the processor’s running frequency. The most recently applied schemes to exploit high single and multi-threaded performance at lower energy costs have been to increase the number of cores per chip as well as their diversity leading to what is commonly referred to as heterogeneous multi or many core architectures. In spite of the visible gains the architectures offer, heterogeneity poses significant challenges to the OS, one of the most critical being thread scheduling[1]. In this paper we provide contributions consisting of 1) a Hardware Round-Robin Scheduling policy motivated by [2] and derivation of a mathematical model for analyzing it, and 2) an analysis and comparison of the performance results obtained through our mathematical model with ones gathered via a simulator and real physical system. HRRS policy and mathematical model In order to effectively enhance the scheduling efficiency on a heterogeneous system within a realistic scope of implementation, we have sought a scheduling scheme that leaves the OS unmodified. To achieve this, we have provided the OS with an abstracted view of the heterogeneous physical hardware as being instead composed of four identical (homogeneous) logical cores. As a consequence, the OS scheduler will now map software threads onto the logical cores which enables the OS scheduling policies and implementation to be left unaltered. Meanwhile, as the OS scheduler maps threads to the logical cores, which may happen at every software-quantum or while handling interrupts, the Hardware Round-Robin Scheduler (HRRS), which is triggered into action at every hardware-quantum, maps the logical cores to the physical cores. In essence, the HRRS remaps the software threads that are abstractly assigned to a logical core by the OS to the physical cores of the underlying hardware which actually execute the threads.