relatedwork.tex

\vspace{1mm} \noindent \textbf{Real-time scheduling in heterogeneous systems.} The real-time scheduling of sporadic task systems on a homogeneous multiprocessors has received an enormous amount of attention~\cite{andersson2003, baker2007, funk2005, Baruah2006a, chattopadhyay2011, baruah2005a, baruah2008, bertogna2011b, BC, baruah1996, goossens2003, baker2003, Cluster1, davis2011a, devi2005, baruah1996, baruah2007, G, Par}.  On a heterogeneous multiprocessor that contains processor cores with varying speeds, several works~\cite{raravi2014task, raravi2013assigning, niemeier2011partitioned} have been conducted, which showed that partitioned scheduling-based approaches are able to yield HRT and SRT schedulability tests with various degrees of capacity loss. In a recent work~\cite{Tong14a}, PI Liu's research group  developed the first optimality result for this problem, which presents a global scheduling algorithm and its associated schedulability test that guarantees SRT correctness with no capacity loss. Another recent work~\cite{Chwa15} developed a new global scheduling algorithm and the associated schedulability test that guarantees HRT correctness with no capacity loss. 

\vspace{1mm} \noindent \textbf{Exploring timing-energy tradeoffs in heterogeneous systems.} For systems without timing requirements, a number of approaches have been proposed to explore the performance-energy tradeoffs (e.g., throughput versus energy)~\cite{muthukaruppan2014price, chen2014adaptive, muck2015run, sarma2015smartbalance, lin2014energy, tan2015approximation, elewi2014energy, annamalai2014reducing, yavits2014effect, beaumont2014analysis, gutierrez2014evaluating}. DVFS and dynamic power management policies have been used in such work to reduce energy consumption. %For the specific big.LITTLE platform, \cite{kim2015fair} proposed a new fair scheduler which is aware of the asymmetric platform and implemented in Linux on top of the big.LITTLE scheduler. In \cite{muthukaruppan2014price}, a price theory-based dynamic power management framework is designed to save energy on ARM's big.LITTLE.\cite{kim2014utilization} proposed utilization-aware load balancing mechanism target for energy efficiency of big.LITTLE processor. \cite{pathania2015power} developed an performance-aware Governor for mobile games to reduce energy consumption by leveraging power management tools such as DVFS.
 For systems with timing requirements, a couple of recent works~\cite{liuenergy, colin2014energy} have been conducted exploring the timing-energy tradeoffs in a heterogeneous computing system.  Besides yielding rather pessimistic schedulability tests (possibly due to the mere consideration of partitioned scheduling), these works apply a similar design philosophy as those designed for homogeneous platforms, where only timing-related concerns are considered when making scheduling decisions. Energy saving techniques such as DVFS are applied afterwards to the maximum degree to save energy while not causing timing violations. As will be discussed next in Section~\ref{sec:step1Motivation}, we believe that fundamental energy efficiency due to using a heterogeneous platform can only be achieved if  a scheduler considers the \textit{heterogeneous energy characteristics of tasks exhibited on different processors} when making scheduling decisions at the beginning.

%\paragraph{Schedulers native to big.LITTLE.} Clustered switching, in-kernel switcher, and global task scheduling are the three open-source scheduling modules native to the big.LITTLE architecture. Clustered switching is a simple implementation, arranging the processor into identically sized clusters of ``big'' or ``LITTLE'' cores. The OS scheduler can only see one cluster at a time and decides the specific cluster to execute a task. The in-kernel switcher pairs one big core with a LITTLE core. Each pair operates as one virtual core and only one real core is (fully) powered up and running at a time. For the pair in operation, one core is executing tasks while the other core is inactivated.   The most powerful native scheduler of big.LITTLE is global task scheduling, which enables the use of all physical cores at the same time. Computation-intensive tasks can be allocated to big cores while tasks with less resource-demanding requirements can be simultaneously allocated to little cores for energy efficiency purposes. The software are available on the Linaro git tree \cite{https://git.linaro.org/arm/big.LITTLE/switcher.git} as a patch set to the Linux kernel. 

\paragraph{DVFS approach overview.} DVFS has been proven to be an effective technique that reduces energy consumption through dynamically adjusting the supply voltage and operating frequency of processors. DVFS has also been widely studied in real-time embedded systems (see \cite{bhatti2011energy} for a detailed survey on this topic). DVFS-based real-time scheduling algorithms can be generally divided into three categories: (\textit{i}) \textit{static} DVFS, where DVFS are statically applied offline after all scheduling decisions (based on tasks' worst-case execution times) are made such that the frequency on every processor is minimized while still being able to guarantee timing correctness, (\textit{ii}) \textit{dynamic intra-task} DVFS, where variations (often called slack) in jobs' actual execution time and their pre-defined worst-case execution times are exploited. Slacks are dynamically reallocated inside the same task to further lower the frequency at runtime, and (\textit{iii}) \textit{dynamic inter-task} DVFS, which is similar to the dynamic intra-task DVFS approach but redistributes dynamic slack among other ready tasks. We will explore all these three DVFS approaches in our solution space.