Control-theoretic adaptive cache-fair scheduling of chip multiprocessor systems

Abstract

In chip multiprocessor scheduling, cache memory awareness is critical. However, most existing cache-aware multiprocessor scheduling methods are static and open-loop and thus do not work well in dynamic environments. To address this challenging problem, a control-theoretic approach is presented in this paper for adaptive cache-fair multiprocessor scheduling. The adaptive cache-fair multiprocessor scheduling uses process models to estimate the shared cache size requirements and the instruction count variations of the threads running on multiprocessor cores. Then, it feeds the estimated information back to an adaptive controller. Designed from the process models, the controller decides processor cycle re-allocation through model computation to maintain the instruction counts of the multiple threads at their desired values. The effectiveness of the adaptive cache-fair multiprocessor scheduling is demonstrated through examples.

Keywords

Scheduling feedback scheduling chip multiprocessor modelling adaptive control

Introduction

A chip multiprocessor (CMP) system is a system with two or more cores integrated on a single chip. It is designed to improve the overall computation throughput of the system while reducing power consumption and design complexity. It is widely used in general-purpose and embedded applications (Cui et al., 2014; Pricopi and Mitra, 2014; Zhuravlev et al., 2012). As shown in Figure 1, each of the CMP cores in a CMP system consists of L1 instruction and data caches, and is able to process multiple threads simultaneously. Also, there is an on-chip L2 cache memory, which is shared by all cores and aims to reduce off-chip memory access latency.

Figure 1.

Chip multiprocessor (CMP) architecture.

Scheduling of CMP systems is a typical application of the general technique of resource scheduling. The concept and theory of resource scheduling are widely employed in various applications, such as computing (Wang et al., 2016), communications (Dong et al., 2014), control and general complex systems (Bogdan and Zhou, 2011). The proliferation of general-purpose and embedded CMP systems leads to an imminent challenge to guarantee the scheduling performance of multiple tasks or threads on shared computing resources (Cui et al., 2014; Pricopi and Mitra, 2014; Yu et al., 2013; Zhuravlev et al., 2012). However, the shared cache memory architecture outdates conventional time-centric approaches to multi-thread scheduling due to the lack of cache memory awareness in the scheduling decisions. Cache unawareness of these algorithms results in poor utilization of processor cycles, and memory stalls with this poor utilization lead to thread execution performance degradation and processor cycle wastes.

To tackle this challenging problem, cache-aware multiprocessor scheduling has attracted increasing interests, e.g. see the work by Ebrahimi et al. (2010) and Zhou et al. (2009a,b). However, the majority of existing cache-aware scheduling methods, such as those presented by Ebrahimi et al. (2010); Jahre and Natvig (2009) and Zhou et al. (2009b), are static and open-loop. They cannot dynamically adapt against the dynamic transitions of the processor states, such as varying cache demands of the threads.

Addressing cache-fair CMP scheduling in dynamic environments, this paper describes the CMP scheduling from a feedback control perspective (Lu et al., 2002), and then presents a control-theoretic approach for adaptive cache-fair multiprocessor scheduling (ACMS). The main objective is to reduce cache memory dependence on the execution performance of threads under time-varying cache dynamics. The ACMS avoids memory stalls in thread executions with additional processor cycles while estimating the instant cache size requirement of the thread. Thus, it maintains the instruction counts of the multiple threads at their respective desired values through manipulating the processor cycles. This is achieved through real-time estimation of the dynamic variations in thread cache size requirements and instruction counts of the threads, together with processor cycle re-allocation decided by an adaptive controller (Park et al., 2012). For controller design, the system dynamics is mathematically described with a thread execution pattern model. The parameters of the model are identified in real-time through a QR-decomposition based recursive least square (QR-RLS) algorithm. The controller is designed using the pole placement technique with system modelling.

The paper is organized as follows. Following this brief introductory section is a section on related work and motivations. Then, a section is dedicated to the ACMS framework. After that, thread execution pattern modelling is developed. This is followed by developments of model identification, real-time scheduling control strategies and pole placement for controller design, respectively. Furthermore, experiments are conducted for benchmark examples. Finally, conclusions are drawn at the end of the paper.

Related work and motivations

Multiprocessor scheduling is an active topic of research (Pricopi and Mitra, 2014; Zhuravlev et al., 2012). For example, it has also been investigated for energy savings through software controlled dynamic voltage scaling (Mishra and Tripathi, 2014). Recently, with the proliferation of CMP architecture, multiprocessor scheduling faces new challenges in scheduling resources with share memory access constraints (Schliecker et al., 2009). The work in this paper deals with CMP scheduling with consideration of shared memory.

As multiprocessors in a CMP system share the limited memory, memory awareness becomes critical in achieving satisfactory scheduling performance of the system. Conventional time-centric scheduling algorithms, e.g. the earliest-deadline-first (EDF) (Anderson and Srinivasan, 2000; Stankovic et al., 1998), the least-laxity-first (LLF) and proportionate fair (Pfair) (Stankovic et al., 1998), lack cache memory awareness. Memory stalls and poor utilization of processor cycles lead to thread execution performance degradation and processor cycle wastes. Thus, cache-aware scheduling methods have been proposed to address this problem. This paper will present a new cache-aware CMP scheduling approach, which we refer to as ACMS.

Cache-aware scheduling can be categorized into cache-fair scheduling (Ebrahimi et al., 2010; Fedorova et al., 2006; Jahre and Natvig, 2009; Kim et al., 2004) and cache pattern-aware scheduling (placement) (Fedorova et al., 2005; Rajagopalan et al., 2007; Sato et al., 2013; Zhou et al., 2009a). The former comes from the fact that fair sharing of the resources among multiple threads will minimize the resource conflicts and bottlenecks. The latter is based on partitioning scheduling algorithms, in which tasks statically execute among the available cores according to the underlying scheduling criteria. Cache pattern-aware scheduling analyses the data patterns of the threads at application levels and places the threads into the most convenient cores according to their cache data pattern behaviours. The ACMS to be presented in this paper is a cache-fair scheduling approach.

However, the majority of existing cache-aware scheduling methods, e.g. those presented by Ebrahimi et al. (2010); Fedorova et al. (2006); Jahre and Natvig (2009); Kim et al. (2004) and Zhou et al. (2009b), are static and open-loop, implying that the actual scheduling performance is not fed back to the scheduler for dynamic adaptation of the scheduling decision. Open-loop cache-fair scheduling algorithms are diversified according to the specific methodology employed in the scheduling. For instance, Jahre and Natvig (2009) use interference points (IPs) to measure unfairness, while Fedorova et al. (2006) identify fairness based on the central processing unit (CPU) latency or cycle per instruction (CPI). However, the general inclination in all these methods is to use execution time metric (Ebrahimi et al., 2010; Kim et al., 2004). Regarding fairness enforcement strategies, there are different approaches. For example, Fedorova et al. (2006) enforce fairness by adapting processor cycles of threads. A general trend is to enforce fairness using cache related parameters such as cache allocation and partitions (Ebrahimi et al., 2010; Jahre and Natvig, 2009; Kim et al., 2004; Zhou et al., 2009b).

Existing studies (Tam et al., 2009) have shown significant differences in the cache size requirements among a number of applications or threads, indicating high uncertainty of the cache size requirement and cache miss rate due to the highly correlated nature of the co-runner threads. However, operating on a single operating point efficiently, open-loop cache-fair scheduling fails to consider dynamic variation in an operating environment. Even for the single operating point, the efficiency of the existing open-loop cache-aware algorithms is only verifiable on a specific system state, and the performance of the open-loop algorithms may degrade significantly in a changing environment such as varying cache demands of the threads. Therefore, there is a demand of closed-loop CMP scheduling to deal with this problem, motivating the research of our work in this paper on control-theoretic closed-loop cache-fair CMP scheduling.

Indirectly related to the topic of this paper, investigating scheduling from the feedback control perspective was reported in a single processor (Lu et al., 2002). The basic concept in the work by Lu et al. (2002) was to measure the actual scheduling performance and then feed the measured performance back to the scheduler, thus forming feedback scheduling. Feedback scheduling is a broad area in real-time scheduling. Similar work on feedback scheduling includes the works by Buttazzo and Aneni (2002); Tian and Gui (2011) and Tian et al. (2010).

There are a few closed-loop frameworks for CMP resource allocation despite the fact that none of them have directly tackled the fairness of the allocation at cache level. Srikantaiah et al. (2009) developed a SHArd Resource Partitioning (SHARP) control framework, which was an adaptive cache-aware scheduling framework for CMP systems. They used control theory for dynamic partitioning of the multiprocessor shared last-level caches, and this was achieved by optimizing the last level cache utilization among multiple concurrently executing applications on a well-defined service level platform. The SHARP control framework (Srikantaiah et al., 2009) uses a utilization metric and instruction count per cycle of an application, and updates cache ways for an application based on this metric. In comparison, the ACMS to be presented in this paper measures cache performance dependence on the utilization of a thread and avoids negative cache dependence by allocating more processor cycles to that particular thread.

Another set of articles on feedback control theory applications on CMP systems includes the work by Brinkschulte and Pacher (2008) and Velusamy et al. (2002), which inspire the research of our work in the present paper as an applied control example on a CMP platform. Brinkschulte and Pacher (2008) have proposed a closed-loop feedback framework with consideration of only branch mis-prediction as a slowdown factor for the throughput of a thread. From this slowdown metric, a new thread priority is defined for a thread on each control cycle. Velusamy et al. (2002) provided a general guideline on applications of the controller-design technique for tracing a desired adaptive behaviour. Their discussions covered modelling of the underlying system behaviour, determination of a setpoint (target metric) and sampling rate, and hardware controller implementation. They also defined cache decay, which is a technique for leakage energy savings. The introduction of the cache decay concept gives the flexibility of waiting for a pre-determined time duration, which is called the decay interval, before concluding that the data of a cache line is no longer in use and the cache line can be deactivated.

Compared with other adaptive or closed-loop control frameworks, the ACMS in this paper is a more advanced control framework with self-tuning capability. It is able to lean time-varying system dynamics and re-design the closed-loop system in each control period, making it more robust and less prone to uncertainties in CMP systems. So far, adaptive self-tuning control theory has not been well applied in robust and real-time cache-fair CMP scheduling.

In various approaches to the resource allocation fairness on CMP systems, a general strategy can be formulated in three stages:

fairness measurement;

resource allocation;

fairness enforcement.

These stages will be addressed in this paper in the ACMS development.

ACMS framework

Extending conventional single-dimensional scheduling, the ACMS has additional capability such as online learning and adaptive re-designable closed-loop architecture. It is constructed as a self-tuning adaptive control system, as depicted in Figure 2. The primary goal of the ACMS is to drive the actual instruction count ( $IC$ ) per sampling period of the target thread towards its reference ( $I C^{D}$ ), which is the instruction count per sampling period of the thread in a dedicated cache environment. This is achieved through manipulation of processor cycles ( $c$ ) assigned to each thread. In other words, the controller decides the number of processor cycles ( $c$ ) assigned to the thread based on the error $I C^{D} - IC$ . In control theory terminology, $IC$ , $I C^{D}$ and $c$ are controlled variable (or system output), controller reference (or setpoint) and controller output (or manipulated variable), respectively. Thus, instruction count degradation due to the shared cache environment is avoided by allocating additional processor cycles.

Figure 2.

The framework of the ACMS. Notations in the figure: processor cycles $c$ , instruction count $IC$ , desired instruction count $I C^{D}$ , miss count $m_{c}$ , co-runner miss count $c_{mc}$ , identified parameters from the QR-RSL model to the adaptive pole placement module $(a_{0}, a_{1}, a_{2}, b_{0}, b_{1})$ , parameters output from the adaptive pole placement module to the controller $(p_{0}, p_{1}, p_{2}, q_{0}, q_{1})$ .

As shown in Figure 2, the ACMS consists of four main components:

CMP system plant demonstrating thread execution dynamics;

QR-RLS model identification for plant model identification;

pole placement controller design module for adaptive adjustment of the controller parameters;

scheduling controller for dynamic CMP scheduling control.

In addition, a thread execution pattern model has to be established to describe the thread execution dynamics. This can be considered as an additional and hidden component of the ACMS.

The four components of the ACMS in Figure 2 are interconnected into two separate loops: a conventional feedback loop with the plant and the controller, and a parameter adjustment loop including the online model identification and adaptive controller parameter adjustment.

The conventional feedback loop tracks the actual $IC$ of the thread in a shared cache environment according to the reference $I C^{D}$ . This is achieved by manipulating the allocation of processor cycles $c$ by the scheduler controller.

With the hidden execution pattern model, the parameter adjustment loop provides online learning and adaptive re-designable closed-loop architecture to guarantee controller parameter adaptation against the characteristics and uncertainties of the time-varying cache size requirement. The hidden model relates to cache size requirement variables such as miss count and co-runner miss counts as well as processor cycles assigned to that particular thread. The QR-RLS model identification module is designed for parameter identification of the thread execution pattern model. With the identified model, the pole placement controller design module updates the controller parameters in real time. The detailed design of the ACMS components is discussed in the next few sections.

Thread execution pattern model

To design an adaptive control system for CMP scheduling, a dynamic model is essential to capture the thread execution pattern for the threads in a CMP system. This section builds such a model, which describes the relationships between processor cycle, miss count ( $m_{c}$ ) and the $IC$ of the thread and co-runner threads in a discrete-time domain. Then, we constrain the nonlinear model into a linear deterministic autoregressive moving average regression (DARMA) model for simplified control design. The model is further expressed in a $z$ transfer function, a standard tool for digital control design. This linear model is used in designing the QR-RLS module, the closed-loop system response, and the scheduling controller.

The execution performance of a thread can be modelled by formulating the impact of a cache miss on the cycles per instruction (CPI) of the thread. As the ACMS aims to maintain the ICs of the multiple threads at their respective desired values through manipulating the processor cycle re-allocation, the model will relate the CPI with IC. From the work by Matick et al. (2001), the actual CPI vector, $CP I_{Actual}$ , can be modelled by

CP I_{Actual} = CP I_{Ideal} + FCP

(1)

where $FCP$ is a finite cache penalty (FCP), which is the execution stall in cycles due to a cache miss. All three variables in equation (2) are vectors with the dimension equal to the number of threads in the CMP system. This means that equation (2) describes the dynamics of the whole system involving all threads.

Equation (1) can be reformulated to a discrete-time state space model for practical computation

\begin{matrix} IC [k + 1] = IC [k] + (IP C_{Actual}) \cdot c [k] \\ = IC [k] + IP C_{Ideal} \cdot c [k] + F (m_{c} [k]) c [k] \end{matrix}

(2)

where $IPC$ (instructions per cycle) is the inverse of CPI, $k$ stands for the $k$ th sampling period, $m_{c} [k]$ represents miss counts and $c [k]$ refers to processor cycles allocated to the thread, respectively. $F (\cdot)$ is a linear function of $m_{c} [k]$

F (m_{c} [k]) = C_{P} \cdot m_{c} [k]

(3)

where $C_{P}$ is a cache miss penalty in processor cycles. For simplicity, $C_{P}$ is assumed to be constant over a control period $t_{c}$ . It follows from equations (2) and (3) that

IC [k + 1] = IC [k] + (IP C_{Ideal} + C_{P} \cdot m_{c} [k]) c [k]

(4)

In this state space model, $IC$ is a state vector, and $m (k)$ and $c (k)$ are two input vectors of appropriate dimensions.

As $m_{c} [k]$ and $c [k]$ are dynamic variables, equation (4) can be considered as a bilinear system in state space. However, it is computationally expensive to solve a bilinear system model. Hence, equation (4) is decomposed into two coupled dynamic linear systems when $IC [k]$ and $m_{c} [k]$ are considered to be independent. The first linear system is to derive $IC [k + 1]$ from $IC [k]$ , $c [k]$ and measured or predicted $m_{c} [k]$ , implying that $k$ is dropped from $m_{c} [k]$ . This gives

IC [k + 1] = IC [k] + (IP C_{Ideal} + C_{P} \cdot m_{c}) c [k]

(5)

where $IC$ is the actual output of the system and both $m_{c}$ and $c$ are inputs to the system. The second linear system is to derive the miss count through a dynamic model

\begin{matrix} M_{C} [k + 1] & = \hat{A} [k] M_{C} [k] + \hat{B} [k] C_{MC} [k] \\ m_{c} & = [\underset{n}{\underset{︸}{1, 0, \dots, 0}}]^{T} M_{C} [k] \end{matrix}

(6)

where $\hat{A}$ and $\hat{B}$ are unknown state and input matrices, respectively, of appropriate dimensions, and are to be identified via model identification

\begin{matrix} M_{C} [k] = [m_{c} [k], m_{c} [k - 1], \dots, m_{c} [k - n]] \\ C_{MC} [k] = [c_{mc} [k - d], c_{mc} [k - d - 1], \dots, c_{mc} [k - d - m + 1]] \end{matrix}

(7)

where $c_{mc} [k]$ is a miss count average of co-runner threads, $d$ is the time delay between the input and output, and $m$ and $n$ are respectively the orders of corresponding state vectors.

Considering ${\hat{A}}_{1} [k]$ and ${\hat{B}}_{1} [k]$ as unknown row vectors with coefficients $a_{0}$ , …, $a_{n}$ and $b_{0}, \dots, b_{m - 1}$ , the following deterministic autoregressive moving average regression (DARMA) is derived

m_{c} [k + 1] = \sum_{j = 0}^{n} a_{j} m_{c} [k - j] + \sum_{j = 0}^{m - 1} b_{j} c_{mc} [k - d - j]

(8)

It can be re-written in a compact form as

\begin{matrix} m_{c} [k + 1] & = w \cdot φ [k] \\ w & = [a_{0}, a_{1}, \dots, a_{n}, b_{0}, b_{1}, \dots, b_{m - 1}] \\ φ [k] & = {[m_{c} [k], \dots, m_{c} [k - n], c_{mc} [k - d], \dots, c_{mc} [k - d - m + 1]]}^{T} \end{matrix}

(9)

The corresponding discrete-time transfer function of the system plant is expressed as $H (z^{- 1}) = B (z^{- 1}) / A (z^{- 1})$ , where $A (z^{- 1})$ and $B (z^{- 1})$ are polynomials of $z^{- 1}$ .

QR-RLS model identification

The cache size requirement of a thread in equation (8) is a linear combination of $m_{c}$ and $c_{mc}$ , and the system uncertainty is formulated as an unknown coefficient vector. To identify the unknown coefficient vector, a QR-RLS algorithm is embedded into the ACMS. In our work, the QR decomposition approach, which is numerically well-conditioned, is employed to guarantee the non-singularity of the RLS problem. It uses a special transformation technique rather than calculating the inverse of the auto-correlation matrix. At the end of the series transformations, the QR-RLS algorithm derives the weighting vector $w = {[a_{0}, \dots, a_{N}, b_{0}, \dots, b_{N}]}^{T}$ .

The QR-RLS algorithm in our work is given in adaptive QR-RSL algorithm steps 1 to 3. In the QR-RLS algorithm, it is assumed that $n = m = N$ and $d = 0$ . As shown in the algorithm, the QR-RLS algorithm consists of three main steps:

initialization and basic assignments;

input data matrix triangularization;

back-substitution to find $w$ .

It is worth mentioning that the convergence of the system model largely depends on both the coefficients $λ$ (in Step 1a) and $γ$ (in Step 2). The coefficient $γ$ is progressively computed in the algorithm. As a cost coefficient, $λ$ needs to be determined with consideration of how much weight or cost is allocated to an estimation error. From the mathematics perspective, it is basically a forgetting factor satisfying $0 < λ \leq 1$ . To capture the long-term behaviour of the cache miss, $λ$ should be set to a value close to 1. It will be shown later that $λ = 0.9$ is set in our experiments. For detailed theoretic developments for each of these steps, please refer to the thesis from Arslan ( 2011).

Adaptive QR-RSL Algorithm – Step 1 Initialization and basic assignments.
(1a) Initialize $w$ , $\underline{Φ} (N)$ , upper triangular matrix $U_{0} (N + 1)$ , $m c_{q 2_{0}} (N + 1)$ . $φ (0) = [m_{c} (k), \dots, m_{c} (k - N), c_{mc} (k), \dots, c_{mc} (k - N + 1)]^{T}$ (10) $For i = 1 to 2 N DO$ $For j = 1 to N DO$ $If (N + 2 - i - j > 0) Then$ $\underline{Φ} (i, j) = - λ^{\frac{i - 1}{2}} \cdot m_{c} (N + 2 - j - i)$ (11) $EndFor$ $For j = N + 1 to 2 N DO$ $If ((2 N + 2 - j - i) > 0) Then$ $\underline{Φ} (N) (i, j) = λ^{(i - 1) / 2} \cdot c_{mc} (2 N + 2 - j - i)$ (12) $EndFor$ $EndFor$ $For k = 1 to N DO$ $For i = 1 to k DO$ $w_{i} (k) = \frac{\sum_{j = 1}^{i} φ (j) w_{i - j} (k) + m_{c} (i)}{φ (0)}$ (13) $EndFor$ $EndFor$ ${U^{'}}_{0} (2 N + 1) = λ^{1 / 2} \underline{Φ} (2 N + 1)$ (14) ${m'_{c}}_{q 2_{0}} (2 N + 1) = {[\begin{matrix} λ^{1 / 2} m_{c} (2 N) \\ ⋮ \\ λ^{(N + 1) / 2} m_{c} (0) \end{matrix}]}^{T}$ (15) (1b) For each time cycle $k$ , $2 N + 1 \leq k$ , compute $γ_{- 1} = 1, m'_{c_{0}} (k) = m_{c} (k), φ'_{0} = φ^{T} (k)$ (16)

Adaptive QR-RSL Algorithm – Step 1 Initialization and basic assignments.

(1a) Initialize

w

\underline{Φ} (N)

, upper triangular matrix

U_{0} (N + 1)

m c_{q 2_{0}} (N + 1)

φ (0) = [m_{c} (k), \dots, m_{c} (k - N), c_{mc} (k), \dots, c_{mc} (k - N + 1)]^{T}

(10)

For i = 1 to 2 N DO

For j = 1 to N DO

If (N + 2 - i - j > 0) Then

\underline{Φ} (i, j) = - λ^{\frac{i - 1}{2}} \cdot m_{c} (N + 2 - j - i)

(11)

EndFor

For j = N + 1 to 2 N DO

If ((2 N + 2 - j - i) > 0) Then

\underline{Φ} (N) (i, j) = λ^{(i - 1) / 2} \cdot c_{mc} (2 N + 2 - j - i)

(12)

EndFor

EndFor

For k = 1 to N DO

For i = 1 to k DO

w_{i} (k) = \frac{\sum_{j = 1}^{i} φ (j) w_{i - j} (k) + m_{c} (i)}{φ (0)}

(13)

EndFor

EndFor

{U^{'}}_{0} (2 N + 1) = λ^{1 / 2} \underline{Φ} (2 N + 1)

(14)

{m'_{c}}_{q 2_{0}} (2 N + 1) = {[\begin{matrix} λ^{1 / 2} m_{c} (2 N) \\ ⋮ \\ λ^{(N + 1) / 2} m_{c} (0) \end{matrix}]}^{T}

(15)
(1b) For each time cycle

k

2 N + 1 \leq k

, compute

γ_{- 1} = 1, m'_{c_{0}} (k) = m_{c} (k), φ'_{0} = φ^{T} (k)

(16)

Adaptive QR-RSL Algorithm – Step 2 Triangularization of $Φ$ and output vector $m_{c}$ .
Rotation matrices elements $\cos θ_{i}$ and $\sin θ_{i}$ : $For i = 0 to 2 N DO$ $c_{i} = \sqrt{[{U'}_{i} (k)]_{i + 1, 2 N + 1 - i}^{2} + φ'_{i}^{2} (2 N + 1 - i)}$ $\cos (θ_{i}) = [U'_{i} (k)]_{i + 1, 2 N + 1 - i} / c_{i}$ $\sin (θ_{i}) = φ'_{i}^{2} (2 N + 1 - i) / c_{i}$ $[\begin{matrix} φ_{i + 1}^{'} (k) \\ {U^{'}}_{i + 1} (k) \end{matrix}] = {Q^{'}}_{θ_{i}} (k) [\begin{matrix} φ_{i}^{'} \\ {U^{'}}_{i} (k) \end{matrix}]$ $γ'_{i} = γ'_{i - 1} \cos (θ_{i})$ $[\begin{matrix} m_{c_{i + 1}}^{'} (k) \\ {m'}_{c}_{q 2 (i + 1)} (k) \end{matrix}] = Q'_{θ_{i}} (k) [\begin{matrix} {m'}_{c i} \\ m_{c_{q 2 i}}^{'} (k) \end{matrix}]$ (17) $EndFor$ $m_{c_{q 2_{0}}}^{'} (k + 1) = λ^{1 / 2} m'_{c q 2_{(2 N + 1)}} (k + 1)$ $U'_{0} (k + 1) = λ^{1 / 2} U'_{2 N + 1} (k)$ $γ (k) = γ'_{2 N} ε (k) = d'_{2 N + 1} (k) γ (k)$ (18)

Adaptive QR-RSL Algorithm – Step 2 Triangularization of

Φ

and output vector

m_{c}

Rotation matrices elements

\cos θ_{i}

and

\sin θ_{i}

For i = 0 to 2 N DO

c_{i} = \sqrt{[{U'}_{i} (k)]_{i + 1, 2 N + 1 - i}^{2} + φ'_{i}^{2} (2 N + 1 - i)}

\cos (θ_{i}) = [U'_{i} (k)]_{i + 1, 2 N + 1 - i} / c_{i}

\sin (θ_{i}) = φ'_{i}^{2} (2 N + 1 - i) / c_{i}

[\begin{matrix} φ_{i + 1}^{'} (k) \\ {U^{'}}_{i + 1} (k) \end{matrix}] = {Q^{'}}_{θ_{i}} (k) [\begin{matrix} φ_{i}^{'} \\ {U^{'}}_{i} (k) \end{matrix}]

γ'_{i} = γ'_{i - 1} \cos (θ_{i})

[\begin{matrix} m_{c_{i + 1}}^{'} (k) \\ {m'}_{c}_{q 2 (i + 1)} (k) \end{matrix}] = Q'_{θ_{i}} (k) [\begin{matrix} {m'}_{c i} \\ m_{c_{q 2 i}}^{'} (k) \end{matrix}]

(17)

EndFor

m_{c_{q 2_{0}}}^{'} (k + 1) = λ^{1 / 2} m'_{c q 2_{(2 N + 1)}} (k + 1)

U'_{0} (k + 1) = λ^{1 / 2} U'_{2 N + 1} (k)

γ (k) = γ'_{2 N} ε (k) = d'_{2 N + 1} (k) γ (k)

(18)

Adaptive QR-RSL Algorithm – Step 3 Back substitution to find $w$ .
$\underline{m_{c}} = [\begin{matrix} m_{c_{2 N + 1}}^{'}, & m_{c_{q 2_{(2 N + 1)}}}^{'} (k) \end{matrix}]$ (19) $w_{0} (k) = m_{c_{(2 N + 1)}} (k) / U_{2 N, 1} (k)$ (20) $For i = 1 to 2 N :$ $w_{i} (k) = \frac{- \sum_{j = 1}^{i} U_{2 N + 1 - i, i - j + 1} w_{i - j} (k)}{U_{2 N + 1 - i, i + 1} (k)} + \frac{\underline{m_{c_{(2 N + 2 - i)}} (k)}}{U_{2 N + 1 - i, i + 1} (k)}$ (21) $EndFor$

Structure of the scheduling controller

After the model parameters of equation (9) are identified, an algebraic pole placement algorithm can be designed to update the controller parameters, i.e. the coefficients of the polynomials $P (z^{- 1})$ and $Q (z^{- 1})$ in the controller transfer function $Q (z^{- 1}) / P (z^{- 1})$ . This section determines the orders of $P (z^{- 1})$ and $Q (z^{- 1})$ .

A pre-designed or desired closed-loop system response enables determination of the closed-loop system stability and other desired close-loop system characteristics such as settling time, maximal overshoot and damping ratio. This increases the flexibility and applicability of the approach for a range of scheduling control scenarios.

For the given model in equation (4), considering the plant transfer function $B (z^{- 1}) / A (z^{- 1})$ and the controller transfer function $Q (z^{- 1}) / P (z^{- 1})$ , the overall desired closed-loop transfer function $G_{Des} (z^{- 1})$ of the system is $N_{G_{Des}} / D_{G_{Des}}$ , where $N_{G_{Des}}$ and $D_{G_{Des}}$ are numerator and denominator components of $G_{Des} (z^{- 1})$ . Denote $K = IP C_{Ideal}$ . It follows that

G_{Des} (z^{- 1}) = \frac{Q (z^{- 1}) (KA (z^{- 1}) + CP \cdot B (z^{- 1}))}{P (z^{- 1}) A (z^{- 1}) + z^{- 1} Q (z^{- 1}) (K \cdot A (z^{- 1}) + CP \cdot B (z^{- 1}))}

(22)

From equation (22), solvable algebraic polynomial equations, also known as Diophantine equations, are derived

D_{G_{Des}} (z^{- 1}) = A (z^{- 1}) P (z^{- 1}) + z^{- 1} Q (z^{- 1}) [K \cdot A (z^{- 1}) + CP \cdot B (z^{- 1})]

(23)

It follows that the error tracking function $E (z^{- 1})$ of the closed-loop scheduling system is formulated as

E (z^{- 1}) = I C^{D} (z^{- 1}) - IC (z^{- 1})

(24)

where $IC (z^{- 1})$ is the actual instruction count (IC); $I C^{D} (z^{- 1})$ is the reference input, i.e. the dedicated instruction count, which is expressed as a transfer function $I C^{D} (z^{- 1}) = N_{IC} (z^{- 1}) / D_{IC} (z^{- 1})$ . $N_{IC}$ and $D_{IC}$ are numerator and denominator components of the transfer function, respectively. We have

E (z^{- 1}) = \frac{N_{IC} (z^{- 1})}{D_{IC} (z^{- 1})} [1 - G_{Des} (z^{- 1})]

(25)

where $G_{Des} (z^{- 1})$ is given in equation (22). Considering the Diophantine in equation (23) and the assumption that $D_{IC} (z^{- 1})$ divides the numerator of the tracking error transfer function in equation (25) and denotes this ratio as $S (z^{- 1})$ , the second Diophantine is derived as

S (z^{- 1}) = \frac{D_{G_{Des}} (z^{- 1}) - Q (z^{- 1}) (K \cdot A (z^{- 1}) + CP \cdot B (z^{- 1}))}{D_{IC} (z^{- 1})}

(26)

which can be re-written as

D_{G_{Des}} (z^{- 1}) = S (z^{- 1}) D_{IC} (z^{- 1}) + Q (z^{- 1}) [K \cdot A (z^{- 1}) + CP \cdot B (z^{- 1})]

(27)

From Bobál et al. (2005), consider the following criterion

\partial D_{G_{D} es} (z^{- 1}) \leq \partial A (z^{- 1}) + \partial max (A (z^{- 1}), B (z^{- 1})) + 1

(28)

If this is met, the polynomial degree relation is defined as

\partial S (z^{- 1}) = max (\partial A (z^{- 1}) \partial B (z^{- 1})) - 1

\partial Q (z^{- 1}) = \partial D_{IC} (z^{- 1}) - 1 \partial Q (z^{- 1}) = \partial A (z^{- 1}) - 1,

\partial P (z^{- 1}) = max (\partial B (z^{- 1}), \partial A (z^{- 1}))

(29)

If the criterion in equation (28) is not met, $\partial P (z^{- 1})$ and $\partial Q (z^{- 1})$ cannot be uniquely determined.

From the assumption of $n = m = N$ and the work of Tam et al. (2009) on miss rate curves, both orders $n$ and $m$ can be heuristically determined to be 2, i.e., $N = m = n = 2$

\partial A (z^{- 1}) = \partial B (z^{- 1}) = 2

(30)

When equation (28) is met, it is feasible to assume the polynomial degrees of the whole system dynamics to be

\partial D_{G_{Des}} (z^{- 1}) \leq 4, \partial A (z^{- 1}) = 2, \partial B (z^{- 1}) = 2, \partial P (z^{- 1}) = 2, \partial Q (z^{- 1}) = 1

(31)

Thus, given equation (22), the polynomial degrees of the closed-loop system can be derived as

\partial D_{G_{Des}} (z^{- 1}) = max [\partial A (z^{- 1}) + \partial P (z^{- 1}), \partial A (z^{- 1}) + 1 + \partial Q (z^{- 1})]

(32)

Equation (32) shows that the closed-loop polynomial degree is four. Thus, a fourth-order desired closed-loop response needs to be designed, as will be shown below.

Pole placement controller design

In the previous section, the orders of $Q (z^{- 1})$ and $P (z^{- 1})$ have been determined to be 1 and 2, respectively. The order of the desired closed-loop transfer function has also been determined to be 4. This section designs the actual coefficients of $Q (z^{- 1})$ and $P (z^{- 1})$ by using the pole placement technique.

The response of the forth-order closed-loop system is designed based on a desired damping ratio and oscillation frequency for a given sampling period $T_{0}$ . In this work, $T_{0} = 1.5$ $μ s$ is set, and the discrete-time poles of the closed-loop system are desired to be

z_{1, 2} = - 0.4 \pm 0.3 i, z_{3} = 0.22, z_{4} = 0.32

(33)

This gives a damping ratio of about 0.54 with the maximum overshoot of about 13% for the closed-loop system. The oscillation frequency is about 231.46 Hz. The resulting closed-loop system is stable with gain and phase margins of about 104 dB and 113∘, respectively.

With the desired poles given in equation (33), the characteristic polynomial $D_{G_{D} es} (z^{- 1})$ of the closed-loop system is obtained as

\begin{array}{l} D_{G_{D e s}} (z^{- 1}) = 1 - 0.2596 z^{- 1} - 0.0201 z^{- 2} \\ - 0.0131 z^{- 3} + 0.0043 z^{- 4} \end{array}

(34)

From equation (32), re-write equation (23) as

\begin{matrix} (p_{0} + p_{1} \cdot z^{- 1} + p_{2} \cdot z^{- 2}) (a_{0} + a_{1} \cdot z^{- 1} + a_{2} \cdot z^{- 2}) \\ + (q_{0} + q_{1} \cdot z^{- 1}) K (a_{0} + a_{1} \cdot z^{- 1} + a_{2} \cdot z^{- 2}) \\ + (q_{0} + q_{1} \cdot z^{- 1}) CP (b_{0} + b_{1} \cdot z^{- 1} + b_{2} \cdot z^{- 2}) \\ = d_{0} + d_{1} z^{- 1} + d_{2} z^{- 2} + d_{3} z^{- 3} + d_{4} z^{- 4} \end{matrix}

(35)

Re-arranging equation (35) gives

[\begin{matrix} a_{0} & 0 & 0 & 0 & 0 \\ a_{0} & a_{0} & 0 & K a_{0} + CP b_{0} & 0 \\ a_{2} & a_{1} & a_{0} & K a_{1} + CP b_{1} & K a_{0} + CP b_{0} \\ 0 & a_{2} & a_{1} & K a_{2} + CP b_{2} & K a_{1} + CP b_{1} \\ 0 & 0 & a_{2} & 0 & K a_{2} + CP b_{2} \end{matrix}] [\begin{matrix} p_{0} \\ p_{1} \\ p_{2} \\ q_{0} \\ q_{1} \end{matrix}] = [\begin{matrix} d_{0} \\ d_{1} \\ d_{2} \\ d_{3} \\ d_{4} \end{matrix}]

(36)

Let us denote

\begin{matrix} H_{1} = K a_{2} + CP b_{2} - (K a_{0} + CP b_{0}) (a_{2} / a_{0}) \\ H_{2} = K a_{1} + CP b_{1} - (K a_{2} + CP b_{2}) (a_{1} / a_{2}) \\ H_{3} = a_{1} K + CP b_{1} - (a_{1} / a_{0}) (K a_{0} + CP b_{0}) \\ H_{4} = K a_{0} + CP b_{0} - (a_{0} / a_{2}) (K a_{2} + CP b_{2}) \\ H_{5} = d_{2} - (d_{0} / a_{0}) a_{2} - (a_{1} / a_{0}) d_{1} + (d_{0} / a_{0}^{2}) a_{1}^{2} - a_{0} (d_{4} / a_{2}) \\ H_{6} = d_{3} - d_{4} (a_{1} / a_{2}) - d_{1} (a_{2} / a_{0}) + (d_{0} / a_{0}^{2}) a_{2} a_{1} \end{matrix}

(37)

From equations (36) and (37), the polynomial coefficients of the controller transfer function are derived as

\begin{matrix} q_{0} = (H_{5} \cdot H_{2} - H_{4} \cdot H_{6}) / (H_{3} \cdot H_{2} - H_{4} \cdot H_{1}) \\ q_{1} = (H_{6} - H_{1} \cdot q_{0}) / H_{2}, p_{0} = d_{0} / a_{0} \\ p_{1} = d_{1} / a_{0} - d_{0} (a_{1} / a_{0}^{2}) - (K a_{0} + CP b_{0}) (q_{0} / a_{0}) \\ p_{2} = d_{4} / a_{2} - [(K a_{2} + CP b_{2}) / a_{2}] \cdot q_{1} \end{matrix}

(38)

Experimental results

Simulation experiments are designed to validate the effectiveness of the scheduling controller in execution performance improvement of the active thread through improved $IC$ . They also demonstrate the convergence of the ACMS in driving adaptive $IC$ to the reference $IC$ obtained from a dedicated cache environment. The results will be compared with those from conventional cache scheduling and dedicated cache allocation. The conventional cache scheduling means single-dimensional scheduling with cache memory sharing by multiple threads (multi-threading) without dynamic adaptation; while the dedicated cache scheduling indicates that each of the threads runs on a dedicated platform without cache memory sharing (single-threading).

Selected specifications of the hardware CMP architecture are shown in Table 1. Experiments are conducted in simulations with various cache utilization scenarios simulated by controlled co-runner pairs. Each thread of the pairs is chosen from compiled benchmarking binaries of the Standard Performance Evaluation Corporation (SPEC) (KleinOsowski and Lilja, 2002). The controlled co-runner thread pairs are formed from the chosen threads as listed in Table 2.

Table 1.

Multi-core CMP architecture constraints.

Constraint	L1 Cache	L2 Cache
specifications	Data, Instructions	Data
Number of sets	512, 512	512
Block size	64, 64	64
Associativity	4, 2	16
Replacement policy	LRU, LRU	LRU
L2Penalty:
(L3Latency+PhyMemLatency) $30 + 60 = 90$ cycles

SMT multi-core processor
Number of cores:		4
Max context (threads) per core:		3
Number of instructions per cycle:		8

Table 2.

Workload/thread definition and scope (KleinOsowski and Lilja, 2002).

Thread	Description	Type
art	Image recognition/neural network	Floating
mcf	Combinatorial optimization thread	Integer
gcc	C compiler	Integer
applu	Parabolic/elliptic PDEs solver	Floating
mesa	3D graphic library thread	Floating
vpr	FPGA circuit placement & routing	Integer
crafty	Gaming, particularly chess, thread	Integer

The SPEC benchmarking suite offers a number of workload levels to represent different memory access characteristics and thread execution patterns. For our purpose, the SPEC co-runner thread pairs are classified into heavy-weight and light-weight co-runner pairs. The co-runner pairs chosen in this work are shown in Table 3, in which some statistics of our simulation results are also tabulated. They include both heavy- and light-weight co-runner pairs. For example, mcf-art is a heavy-weight co-runner pair while mcf-vpr is a light-weight co-runner pair. In all these co-runner pairs, the first thread of each pair always refers to the thread with higher cache requirement and thus is the target thread for performance improvement.

Table 3.

Average miss count ( $M_{C}$ ) and average instruction count ( $IC$ ) calculated in an interval of 5 ms.

Co-runner	Conventional		ACMS		Dedicated
pair	$M_{C}$	$IC$	$M_{C}$	$IC$	$IC$
mcf, art	35	331	48	551	654.54
mcf, vpr	34	590	42	578	654.54
gcc, art	5	271	4.50	375	615.55
gcc, crafty	3.79	557	3.38	525	615.55
applu, art	6	721	5.08	1138	1196
applu, vpr	7	1137	6.04	1198	1196
mesa, applu	23.82	397	32	933	757.15
mesa, crafty	12	704	12.61	1135	757.15

Other experimental settings include the following parameters. The cache miss penalty $C_{p} = 120$ cycles. Sampling period $T_{0} = 1.5$ $μ$ s. Delay $d = 12$ sampling periods between input and output. The forgetting factor $λ = 0.9$ .

Heavy-weight co-runner pair mcf-art

As both mcf and art threads are cache demanding, mcf-art is a heavy-weight co-runner pair. Thus, a significant level of miss count can be expected, as demonstrated in Table 3, e.g. 35 and 48 from the conventional scheduling and ACMS, respectively. As a result, the average $IC$ from the conventional CMP scheduling is as low as 331, which is significantly lower than 654.54 achievable in an ideal and dedicated cache environment. In comparison, the ACMS improves the average $IC$ from 331 to 551, representing a significant increase of 66.47%.

The average $IC$ does not capture the dynamics of the cache size requirements over time. Figure 3 shows that the dynamic $IC$ of the ACMS becomes significantly superior over the conventional scheduling after a short transition.

Figure 3.

mcf-art co-runner pair: adaptive $IC$ of the ACMS vs actual $IC$ of the conventional CMP scheduling.

Figure 4 shows that after a short transition, the adaptive $IC$ of the ACMS converges dynamically to the mean of the reference $IC$ of about 654.54 (Table 3). However, the actual $IC$ of the conventional scheduling is mostly lower than the reference $IC$ , as clearly shown in Figure 5. This indicates that the conventional scheduling leads to a significant cache miss and consequently cache stall, which degrade the cycles per instruction and $IC$ .

Figure 4.

mcf-art: adaptive $IC$ of ACMS vs dedicated (reference) cache $IC$ .

Figure 5.

mcf-art: actual $IC$ of the conventional CMP scheduling versus dedicated (reference) cache $IC$ .

Light-weight co-runner pair mcf-vpr

The light-weight co-runner pair mcf-vpr is a combination of a heavy-weight thread mcf and a light-weight thread vpr. Table 3 shows that the average $IC$ of the ACMS over the timespan (about 1500 cycles) is slightly lower than that of the conventional scheduling (578 vs 590). The main reason is that the heavy-weight thread mcf has sufficient cache resources to use. This is evidenced by the fact that the actual $IC$ of the conventional scheduling is already close to the reference $IC$ , as shown in Figure 6. Thus, the ACMS does not need to be activated when sufficient cache resources are available to the target thread.

Figure 6.

mcf-vpr: dedicated (reference) cache $IC$ vs actual $IC$ of conventional scheduling.

However, the quality of the ACMS in improving the performance of the thread mcf increases over time. Figure 7 shows that after a short transient process, the ACMS becomes better than the conventional CMP scheduling in terms of the $IC$ performance.

Figure 7.

Co-runner pair mcf-vpr: $IC$ performance of the ACMS and the conventional CMP scheduling.

ACMS is designed to drive the $IC$ towards the reference $IC$ . This is achieved in the mcf-vpr scenario, as seen in Figure 8. Noticeably, Figure 8 shows that the adaptive $IC$ of the ACMS approaches the mean value of the reference $IC$ , which is 654.54 as shown in Table 3.

Figure 8.

mcf-vpr: adaptive $IC$ of the ACMS vs reference $IC$ .

Further discussions

In our experiments, the ACMS has improved the average $IC$ performance over the conventional CMP scheduling in six out of the eight scenarios in Table 3. The performance improvements in these six scenarios are significant, as measured by 66.47%, 38.38%, 57.84%, 5.36%, 135.01% and 61.22% for mcf-art, gcc-art, applu-art, applu-vpr, mesa-applu and mesa-crafty co-runner pairs, respectively. Among these six co-runner pairs is the heavy-weight pair mcf-art, as discussed previously in the subsection under the heading of ‘Light-weight co-runner pair mcf-vpr’. Other heavy-weight co-runner pairs behave with similar dynamics to those of the mcf-art co-runner pair.

Two exceptions are light-weight co-runner pairs mcf-vpr and gcc-crafty. While the mcf-vpr exhibits a slight deterioration in the average $IC$ , the dynamic $IC$ of the ACMS is successfully driven towards the reference $IC$ (654.54), which is clearly higher than that of the conventional scheduling (590). For the co-runner pair gcc-crafty, degradation in the average $IC$ is 5.75%. But the ACMS drives the dynamic $IC$ to its reference (615.55), which is significantly higher than that of the conventional scheduling (557).

Conclusion

This paper has shown that the multiprocessor scheduling problem in dynamic environments can be tackled from the feedback control perspective through process modelling, model computation and adaptive control. A control-theoretic approach has been presented for closed-loop adaptive cache-aware chip multiprocessor scheduling (ACMS). It maintains the instruction counts at their respective desired values through process cycle manipulation computed from an adaptive controller, which is designed from CMP models. The real-time and proactive estimation of the cache size requirements of the multiple threads executing on the processors is an input to the adaptive controller. Through some benchmark examples, the ACMS has been demonstrated to be effective in improving the thread execution performance, particularly for a thread in a highly utilized L2 cache environment.

Footnotes

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported in part by the Shanxi Provincial Government of China under the International Collaboration Projects Scheme (grant number 2015081007), and the Talent and Technological Innovation Projects Grant Scheme (grant number 201605D211021), both to authors Y-C Tian and F Li. The work is also supported by Shanghai Science and Technology Commission of China under the International Corporation Projects Scheme (grant numbers 14510722500 and 15220710400) to Y-C Tian, M-R Fei and C Peng.

References

Anderson

Srinivasan

(2000) Early release fair scheduling. In: Proceedings of the 12th Euromicro conference on real-time systems (Euromicro RTS 2000), Stockholm, Sweden, 19–21 June 2000, pp.35–43. IEEE.

Arslan

(2011) Adaptive cache aware multiprocessor scheduling framework. Masters Thesis, Queensland University of Technology, Australia.

Bobál

Böhm

Fessl

et al . (2005) Digital Self-Tuning Controllers: Algorithms, Implementation and Applications. London: Springer-Verlag.

Bogdan

Zhou

(2011) Editorial: Planning and scheduling in complex systems. Transactions of the Institute of Measurement and Control 33(3-4): 315–316.

Brinkschulte

Pacher

(2008) A control theory approach to improve the real-time capability of multi-threaded microprocessors. In: Proceedings of the 11th IEEE international symposium on object oriented real-time distributed computing (ISORC 2008), Orlando, FL, USA, 5–7 May 2008, pp.399–404. IEEE Computer Society.

Buttazzo

Aneni

(2002) Adaptive workload management through elastic scheduling. Real-Time Systems 23(1-2): 7–24.

Cui

Wang

Chen

et al . (2014) Mitigating resource contention on multicore systems via scheduling. The Computer Journal 57(8): 1178–1194.

Dong

Zeng

et al . (2014) Design and implementation of heterogeneous IOT gateway based on dynamic priority scheduling algorithm. Transactions of the Institute of Measurement and Control 36(7): 452–462.

Ebrahimi

Lee

Mutlu

et al . (2010) Fairness via source throttling: A configurable and high-performance fairness substrate for multi-core memory systems. In: ASPLOS XV proceedings of the 15th edition of ASPLOS on architectural support for programming languages and operating systems (ASPLOS’10), Pittsburgh, PA, USA, 17–19 March 2010, pp.335–346.

10.

Fedorova

Seltzer

Small

et al . (2005) Performance of multithreaded chip multiprocessors and implications for operating system design. In: ATEC’05 proceedings of the annual conference on USENIX annual technical conference, Anaheim, CA, USA, 10–15 April 2005, pp.26–26.

11.

Fedorova

Seltzer

Smith

(2006) Cache-fair thread scheduling for multicore processors. Report, Harvard University, USA.

12.

Jahre

Natvig

(2009) A light-weight fairness mechanism for chip multiprocessor memory systems. In: CF’09 proceedings of the 6th ACM conference on computing frontiers. Cagliari, Italy, 18–20 May 2009, pp.1–10.

13.

Kim

Chandra

Solihin

(2004) Fair cache sharing and partitioning in a chip multiprocessor architecture. In: Proceedings of the 13th international conference on parallel architectures and compilation techniques (PACT 2004). Antibes Juan-les-Pins, France, 29 September–3 October 2004, pp.111–122.

14.

KleinOsowski

Lilja

(2002) MinneSPEC: A new SPEC benchmark workload for simulation-based computer architecture research. Computer Architecture Letters 1(1): 7–7.

15.

Stankovic

Son

et al . (2002) Feedback control real-time scheduling: Framework, modeling, and algorithms. Real-Time Systems 23(1-2): 85–126.

16.

Matick

Heller

Ignatowski

(2001) Analytical analysis of finite cache penalty and cycles per instruction of a multiprocessor memory hierarchy using miss rates and queuing theory. IBM Journal of Research and Development 45(6): 819–842.

17.

Mishra

Tripathi

(2014) Energy efficient voltage scheduling for multi-core processors with software controlled dynamic voltage scaling. Applied Mathematical Modelling 38(14): 3456–3466.

18.

Park

Lee

Park

et al . (2012) Adaptive control for input-constrained linear systems. International Journal of Control, Automation & Systems 10(5): 890–896.

19.

Pricopi

Mitra

(2014) Task scheduling on adaptive multi-core. IEEE Transactions on Computers 63: 2590–2603.

20.

Rajagopalan

Lewis

Anderson

(2007) Thread scheduling for multi-core platforms. In: HOTOS’07 proceedings of the 11th USENIX workshop on hot topics in operating systems, San Diego, CA, USA, 7–9 May 2007, pp.1–6.

21.

Sato

Egawa

Takizawa

et al . (2013) A capacity-aware thread scheduling method combined with cache partitioning to reduce inter-thread cache conflicts. IEICE Transactions on Information and Systems E96.D(9): 2047–2054.

22.

Schliecker

Negrean

Ernst

(2009) Response time analysis on multicore ECUs with shared resources. IEEE Transactions on Industrial Informatics 5(4): 402–413.

23.

Srikantaiah

Kandemir

Wang

(2009) SHARP control: Controlled shared cache management in chip multiprocessors. In: MICRO-42 proceedings of the 42nd annual IEEE/ACM international symposium on microarchitecture, New York, NY, USA, 12–16 December 2009, pp.517–528.

24.

Stankovic

Ramamritham

Spuri

(1998) Deadline Scheduling for Real-Time Systems: EDF and Related Algorithms. Norwell: Kluwer Academic Publishers.

25.

Tam

Azimi

Soares

et al . (2009) RapidMRC: Approximating L2 miss rate curves on commodity systems for online optimizations. In: ASPLOS XIV proceedings of the 14th international conference on architectural support for programming languages and operating systems, Washington, DC, USA, 7–11 March 2009, pp.121–132.

26.

Tian

Gui

(2011) QoC elastic scheduling for real-time control systems. Real-Time Systems 47(6): 534–561.

27.

Tian

Jiang

Levy

et al . (2010) Local adjustment and global adaptation of control periods for QoC management of control systems. IEEE Transactions on Control Systems Technology 20(3): 846–854.

28.

Velusamy

Sankaranarayanan

Parikh

et al . (2002) Adaptive cache decay using formal feedback control. In: The 2002 workshop on memory performance issues, in conjunction with ISCA-29 the 29th annual international symposium on computer architecture. Anchorage, AK, USA, 25 May 2002.

29.

Wang

Gong

Liu

et al . (2016) Model and algorithm for heterogeneous scheduling integrated with energy-efficiency awareness. Transactions of the Institute of Measurement and Control 38(4): 452–462.

30.

Veeravalli

(2013) Quality-driven dynamic scheduling for real-time adaptive applications on multiprocessor systems. IEEE Transactions on Computers 62(10): 2026–2040.

31.

Zhou

Qiao

Lin

(2009a) Research on synthesis parameter real-time scheduling algorithm on multi-core architecture. In: Proceedings of the Chinese control & decision conference (CCDC’09), Guilin, China, 17–19 June 2009a, pp.5116–5120.

32.

Zhou

Chen

Zheng

(2009b) Cache sharing management for performance fairness in chip multiprocessors. In: Proceedings of the 18th international conference on parallel architectures & compilation tech (PACT’09), Raleigh, NC, USA, 12–16 September 2009, pp.384–393.

33.

Zhuravlev

Carlos Saez

Blagodurov

(2012) Survey of scheduling techniques for addressing shared resources in multicore processors. ACM Computing Surveys 45(1): 4:1–4:28.