An extensible framework for multicore response time analysis

The rest of the paper is organised as follows. Section 2 discusses the related work. Section 3 describes the system model and notation used. Sections 4 and 5 show how the effects of a local memory and the common interconnect can be modelled. Section 6 presents the nucleus of our framework, interference-aware MRTA. This analysis integrates processor and memory demands accounting for cross-core interference. Extensions to the presented analysis are discussed in Sect. 7. Section 8 describes a cycle-accurate simulator used to verify the precision of the analysis. Section 9 provides the results of an experimental evaluation using the MRTA framework, and Sect. 10 concludes with a summary and perspectives on future work.

Although listed in this category, some of the works cited below also consider interference at the cache(s) or main memory level as well. However, they typically make either pessimistic or simplistic assumptions (like having private caches only) at those levels in order to simplify the model and thus focus on the contention for the shared memory bus.

Rosen et al. (2007) proposed an analysis technique for systems in which the shared memory bus uses TDMA arbitration and the time slots are statically assigned to the cores. This technique relies on (i) the availability of a user-programmable table-driven bus arbiter, which is typically not available in real hardware, and (ii) on the knowledge at design time of the characteristics of the entire workload that executes on each core.

In the same vein, also relying on TDMA arbitration of the memory bus, Chattopadhyay et al. (2010) and Kelter et al. (2011) proposed a response time analysis technique that considers a shared bus and an instruction cache, assuming separate buses and memories for both code and data. Their methods have limited applicability though, as they do not address data accesses to memory.

Paolieri et al. (2009) proposed a multicore architecture with hardware that enforces a constant upper bound on the latency of each access to a shared L2 memory through a shared bus. This approach enables the analysis of tasks in isolation since the interference on other tasks can be conservatively accounted for using this bound on the latency of each access. Similarly, the PTARM (Liu et al. 2012) enforces constant latencies for all instructions, including loads and stores; however, both cases represent customized hardware.

Lv et al. (2010) used timed automata to model the memory bus and the memory request patterns. Their method handles instruction accesses only and may suffer from state-space explosion when applied to data accesses. Another method employing timed automata was proposed by Gustavsson et al. (2010) in which the WCET is obtained by proving special predicates through model checking. This approach enables detailed system modelling, but is also prone to the problem of state-space explosion.

Schliecker et al. (2010) proposed a method that employs a general event-based model to estimate the maximum load on a shared resource. This approach makes few assumptions about the task model and is thus quite generally applicable; however, it only supports a single unspecified work-conserving bus arbiter.

Yun et al. (2012) proposed a software-based memory throttling mechanism to explicitly limit the memory request rate of each core and thereby control the memory interference. They also developed analytical solutions to compute proper throttling parameters that ensure the schedulability of critical tasks while minimising the performance impact of throttling.

Kelter et al. (2014) analysed the maximum bus arbitration delays for multicore systems sharing a TDMA bus and using both (private) L1 and (shared) L2 instruction and data caches.

Dasari et al. (2016) proposed a general framework to compute the maximum interference caused by the shared memory bus and its impact on the execution time of the tasks running on the cores. This method is more complex than the one proposed in this paper, and may be more accurate when it estimates the delay due to the shared bus; however, it assumes partitioned caches and therefore does not take cache-related effects into account, which makes it less general than the framework proposed here.

Jacobs et al. (2016) proposed a formal framework for the derivation of sound WCET analyses for multi-core processors. They show how to apply their analysis to account for interference on shared buses, accounting for cumulative information about the interference from tasks on other cores.

Huang et al. (2016) presented a response-time analysis that applies to multicores with one shared resource under fixed-priority arbitration. They give a simple task-to-core allocation algorithm and show that in conjunction with their response-time analysis it has a speedup factor of 7. Unlike the work in this paper, their model neither accounts for cache-related pre-emption delays nor for DRAM refreshes. Huang et al. (2016) also provide an improved response-time analysis for the case where tasks suspend from their processing core when accessing a shared resource. This is a reasonable assumption for DMA transfers, but not for individual memory accesses.

Most of the related work on memory controllers proposes scheduling algorithms that improve the controller performance, i.e., the average time to serve a sequence of requests, by (re)ordering the incoming requests at the controller level. Typically, these techniques are aimed at reducing the number of transitions between read and write modes. They seek to get the best performance from an open page policy by exploiting data locality.

Targeting real-time systems and thus time-predictability rather than performance, Kim et al. (2014a, 2016) presented a model to upper bound the memory interference delay caused by concurrent accesses to shared DRAM. Their work differs from this paper in that they primarily focus on the contention at the DRAM controller, assuming either fully-partitioned private caches or shared caches. For shared caches, they simply assume that either task preemption does not incur cache-related preemption delays (assuming in this case that cache coloring mechanisms are employed), or that the extra number of memory requests resulting from cache line evictions at runtime is given. Any further delays from shared resources, such as the memory bus, are simply assumed to be accounted for in the tasks’ WCETs.

Regarding the problem of estimating the WCET of tasks running in systems with shared caches, Yan and Zhang (2008) proposed a solution assuming direct-mapped, shared L2 instruction caches on multicores. The applicability of the approach is unfortunately limited as it makes very restrictive assumptions such as (i) data caches are perfect, i.e. all accesses are hits, and (ii) data references from different threads will not interfere with each other in the shared L2 cache.

Li et al. (2009a) proposed a method to estimate the worst-case response time of concurrent programs running on multicores with shared L2 caches, assuming set-associative instruction caches using the LRU replacement policy. Their work was later extended by Chattopadhyay et al. (2010) by adding a TDMA bus analysis technique to bound the memory access delay.

Regarding flash memory, Li and Mayer (2016) proposed a post-processing analysis methodology to acquire precise information about task flash memory contentions based on non-intrusive traces. For scratchpad memory, most of the works aim at reducing the WCET by proposing optimized stack management techniques (Lu et al. 2013) or dynamic code management techniques (Kim et al. 2014b), for loading program code from the main memory to the scratchpad.

Considering shared caches, there are a plethora of works that aim at reducing the impact of task pre-emptions and hence also the cache related pre-emption delays. Solutions to that problem are various: some address the problem at the task scheduling level Davis et al. (2013, 2015) by adding restrictions on the time at which tasks may be pre-empted, or at the cache management policy level (Ward et al. 2013; Mancuso et al. 2013; Slijepcevic et al. 2014). It is outside the scope of this paper to discuss all these research works.

Rather than computing a unique upper-bound on the tasks’ context independent WCET, some works propose solutions to characterize the WCET as a function of the platform characteristics and environment.

Paolieri et al. (2011) introduced an interference-aware task allocation algorithm that considers a set of WCET estimations per task, where each WCET estimation corresponds to a different execution environment (e.g. number of contending cores in a multicore system). The sensitivity of the WCET estimates to changes in the execution environment is used to guide the task to core allocation.

Reineke and Doerfert (2014) introduced architecture-parametric WCET analysis, which determines a function that bounds a task’s WCET in terms of the amount and speed of resources allocated to that task. If a temporal-isolation approach is taken then such an analysis is required to partition shared resources in an informed manner. This analysis can also be adapted to determine WCET bounds in terms of the amount of interference on shared resources.

Most of the related work assumes independent tasks and only a few approaches have been proposed so far that consider task dependencies to some extent. Among them, the approach proposed by Li et al. (2009b) analyzes the worst-case cache access scenario of parallelized applications modeled by Message Sequence Graphs. The approach suffers from a very high time-complexity and assumes that the cache access behaviors are known and finite. Choi et al. (2016) used a more general model, comprising an event stream model for resource access and a task graph model for dependent tasks, in order to support a wider range of resource access patterns and parallelized execution of an application.

Schranzhofer et al. (2010) developed a framework based on a TDMA-arbitrated bus. This was followed by work on resource adaptive arbiters (Schranzhofer et al. 2011). Their work assumes a task model where each task consists of sequences of super-blocks, themselves divided into phases that represent implicit communication (fetching or writing of data to/from memory), computation (processing the data), or both. In contrast to the techniques presented in this paper, their approach requires major program intervention and compiler assistance to prefetch data. Adopting a similar model, Pellizzoni et al. (2010) compute an upper bound on the contention delay incurred by periodic tasks, for systems comprising any number of cores and peripheral buses sharing a single main memory. Their method does not cater for sporadic tasks and does not apply to systems with shared caches. In addition it relies on accurate profiling of cache utilization, suitable assignment of the TDMA time-slots to the tasks’ super-blocks, and imposes a restriction on where the tasks can be pre-empted.

Pellizzoni et al. (2011) introduced the PRedictable Execution Model (PREM) framework. This framework considers tasks as consisting of memory phases where they pre-fetch instructions and data, and execution phases where they execute without the need to access memory or I/O devices. The aim is to enable more efficient operation whereby the memory phase of one task overlaps with the execution phase of another. Yao et al. (2012) presented a TDMA scheduling algorithm for PREM tasks on a multicore, and Wasly and Pellizzoni (2014) provided schedulability analysis for non-preemptable PREM tasks on a partitioned multicore. Lampka et al. (2014) proposed a formal approach for bounding the worst-case response time of concurrently executing real-time tasks under resource contention and almost arbitrarily complex resource arbitration policies, with a focus on main memory as a shared resource. Global scheduling of PREM tasks has also been considered by Alhammad and Pellizzoni (2014) and Alhammad et al. (2015).

COTS multicore processors are typically designed to optimize average-case performance and most of their internal mechanisms are usually not documented. For such multicore platforms, Yun et al. (2015) proposed a worst-case memory interference delay analysis under the assumptions that (i) multiple memory requests can be simultaneously outstanding and (ii) the COTS DRAM controller has a separate read and write request buffer, prioritizes reads over writes, and supports out-of-order request processing. In contrast with this work, they assume non-blocking caches (common in COTS processors) that can handle multiple simultaneous cache-misses and focus solely on non-shared LLC (last level of cache) and DRAM bank partitioned systems. Non blocking caches have been the focus a multiple studies recently; however, we do not cover those techniques here. The main problem with non-blocking caches is that the miss status holding registers (MSHRs), special hardware registers which track the status of outstanding cache-misses, can be a significant source of contention (Valsan et al. 2016).

Trilla et al. (2016) proposed a timing model to predict the performance of applications at an early design stage. Their approach is based on generating an execution profile for each application that allows contention analysis on the shared processor resources. The main difference with our approach resides in their assumption that most of the hardware arbitration mechanisms are undocumented and therefore the applications’ execution profiles are obtained based on an empirical analysis.

Most work on response time analysis for multicores, including this paper, assumes timing compositionality (Hahn et al. 2013). Intuitively, for a timing-compositional multicore, it is safe to separately account for delays from different sources, such as computation on a given core, additional cache misses due to preemptions, and interference on a shared bus. Unfortunately, recent results by (Hahn et al. 2015) indicate that even simple commercial multicores are non-compositional, rendering most existing analyses unsound for these architectures. Hahn et al. (2016), however, introduced an extended WCET analysis that enables compositional response time analysis for arbitrary, non-compositional multicores.

We model a generic multicore platform with \(\ell \) timing-compositional cores \(P_1,\ldots P_\ell \) as depicted in Fig. 1. By timing-compositional cores we mean cores where it is safe to separately account for delays from different sources, such as computation on a given core and interference on a shared bus (Hahn et al. 2013).

The set of cores is defined as \(\mathbb {P}\). Each core has a local memory which is connected via a shared bus to a global memory and IO interface. We assume constant delays \({d_{\text {main}}}\) to retrieve data from global memory under the assumption of an immediate bus access, i.e., no wait-cycles or contention on the bus. We assume atomic bus transactions, i.e., no split transactions, which furthermore are not re-ordered, and non-preemptable busy waiting on the core for requests to be serviced. Further, we assume that bus access may be given to cores for one access at a time. The types of the memories and the bus policy are parameters that can be instantiated to model different multicore systems.

In this paper we assume write-through caches only and omit consideration of delays due to cache coherence and synchronization. We also consider write-through and write-back scratchpads.

We assume a set of n sporadic tasks \(\{\tau _1,\ldots ,\tau _n\}\); each task \(\tau _i\) has a minimum period or inter-arrival time \(T_i\) and a deadline \(D_i\). Deadlines are assumed to be constrained, hence \(D_i \le T_i\).

We assume that the tasks are statically partitioned to the set of \(\ell \) identical cores \(\{P_1,\ldots ,P_\ell \}\), and scheduled on each core using fixed-priority pre-emptive scheduling. The set of tasks assigned to core \(P_x\) is denoted by \(\Gamma _x\).

The index of each task is unique and thus provides a global priority order, with \(\tau _1\) having the highest priority and \(\tau _n\) the lowest. The global priority of each task translates to a local priority order on each core which is used for scheduling purposes. We use \({\text {hp}}(i)\) (\({\text {lp}}(i)\)) to denote the set of tasks with higher (lower) priority than that of task \(\tau _i\), and we use \({\text {hep}}(i)\) (\({\text {lep}}(i)\)) to denote the set of tasks with higher or equal (lower or equal) priority to task \(\tau _i\).

We initially assume that the tasks are independent, in so far as they do not share mutually exclusive software resources (discussed in Sect. 7); nevertheless, the tasks compete for hardware resources such as the processor core, local memory, and the memory bus.

The execution of task \(\tau _i\) is modelled using a set of traces \(O_i\), where each trace \(o = [\iota _1, \ldots \iota _k]\) is an ordered list of instructions. For ease of notation, we treat the ordered list of instructions as a multi-set, whenever we can abstract away from the specific order. We distinguish three types of instruction it:An instruction \(\iota \) is a triple consisting of the instruction’s memory address \(m^{\text {in}}\), its execution time \(\Delta \) without memory delays, i.e., assuming a perfect local memory, and the instruction type it:We use m to denote a memory block, and the set of memory blocks is defined as \(\mathbb {M}\). \(\mathbb {M}^{\text {in}}\) denotes the instruction memory blocks and \(\mathbb {M}^{\text {da}}\) the data memory blocks. \(m^{\text {in}}\) and \(m^{\text {da}}\) are defined accordingly. We assume that data memory and instruction memory are disjoint, i.e, \(\mathbb {M}^{\text {in}}\cap \mathbb {M}^{\text {da}}= \emptyset \).

We now extend the task model introduced above to include pre-emption costs. These costs occur when the pre-empting task evicts cache blocks of the pre-empted task that have to be reloaded after the pre-empted task resumes. To analyse the effect of pre-emption on a pre-empted task, Lee et al. (1998) introduced the concept of a useful cache block. Applying this concept to traces, a memory block m is referred to as a useful cache block (UCB) at a program point corresponding to instruction \(\iota \) on trace o, if (i) m is cached at that program point and (ii) m is reused by a later instruction in the trace without prior eviction. In the case of pre-emption at the program point corresponding to instruction \(\iota \) on trace o, only the memory blocks that (i) are cached and (ii) will be reused, may cause additional reloads. Hence, the number of UCBs at a program point gives an upper bound on the number of additional reloads due to a pre-emption at that point in the trace. A tighter definition is presented by Altmeyer and Burguière (2009); however, in this paper we need only the basic concept.

The worst-case impact of a pre-empting task is given by the number of cache blocks that the task may evict during its execution. A memory block accessed during the execution of a trace o is referred to as an evicting cache block (ECB). Accessing an ECB may evict a cache block of a pre-empted task. The intersection of UCBs of the pre-empted tasks with ECBs of the pre-empting task provides a tight upper bound on the cache-related pre-emption costs.

In this paper, we represent the sets of ECBs and UCBs as sets of integers with the following meaning: We note that a separate computation of the pre-emption cost is restricted to architectures without timing anomalies (Lundqvist and Stenström 1999) but is independent of the type of cache used, i.e. data, instruction or unified cache. For examples of the use of UCBs and ECBs to compute pre-emption costs, see the work of Altmeyer et al. (2012).

Table 1 provides a quick reference for the notation used in this paper. Much of this notation is introduced and defined in later sections. Note we do not include in this table notation that is only used locally for the purpose of simplifying expressions.

Assuming a system with no cache, considering instruction memory, the number of bus accesses \({\text {MD}}_o\) for a trace o is given by the number of instructions k in the trace. The sets of UCBs and ECBs are empty, as pre-emption has no effect on the performance of the local memory, since there is none.Considering data memory, we have to account for the number of data accesses, irrespective of whether they are read or write accesses. The number of accesses \({\text {MD}}_o\) is thus equal to the number of data access instructions.

Scratchpads are explicitly managed local memories that exhibit higher predictability and less dynamic behavior than caches. Hence, scratchpads are commonly advocated for embedded multicore systems.

Scratchpads can implement a write-back or, less commonly, a write-through policy for write accesses. Furthermore scratchpad management may be either static or dynamic. With a static scratchpad management, the scratchpad contents remain constant throughout operation, whereas with dynamic scratchpad management, scratchpad blocks can be reloaded as needed, for example on pre-emptions, which makes better use of the available scratchpad memory (Whitham et al. 2012, 2014).

Caches are commonly used in multicore systems to bridge the performance gap between processor and main memory speeds. Unlike scratchpads they require no explicit management, rather the eviction of cache blocks is determined by the cache replacement policy. In this section, we consider both cold caches, representing the pessimistic case where the cache is empty or contains no useful blocks when a job of task starts to execute, and warm caches, where some useful blocks may persist from the execution of previous jobs of the same task.

To allow different combinations of local memories, for example scratchpad memory for instructions and an LRU cache for data, we define the combination of instruction memory \({\text {MEM}}^{\text {in}}\) and data memory \({\text {MEM}}^{\text {da}}\) as followswith \({\text {MEM}}^{\text {in}}(o) = \left( {\text {MD}}^{\text {in}}_o, \overline{{\text {UCB}}}^{\text {in}}_o, {\text {ECB}}^{\text {in}}_o\right) \) being the result for the instruction memory and \({\text {MEM}}^{\text {da}}(o) = \left( {\text {MD}}^{\text {da}}_o, \overline{{\text {UCB}}}^{\text {da}}_o, {\text {ECB}}^{\text {da}}_o\right) \) the result for the data memory.

We compute the maximal processor demand \({\text {PD}}_i\) for each task \(\tau _i\) as follows:where \(\Delta \) is the execution time of an instruction without memory delays. Task \(\tau _i\) suffers interference \(I^{\text {PROC}}(i,x,t)\) on its core \(P_x\) due to tasks of higher priority running on the same core within a time interval of length t starting from the critical instant:

Local memory improves a task’s execution time by reducing the number of accesses to main memory. The memory demand of a trace gives the number of accesses that go to main memory and hence the bus, despite the presence of the local memory. The maximal memory demand \({\text {MD}}_i\) of a task \(\tau _i\) is defined by the maximum number of bus accesses of any of its traces:Note that the maximal memory demand refers to the demand of the combined instruction and data memory as defined in Eq. (20).

The memory demand \({\text {MD}}_i\) is derived assuming non-preemptive execution, i.e. that the task runs to completion without interference on the local memory. The sets of UCBs and ECBs are used to compute the additional overhead due to pre-emption. In the computation of this overhead, we use the sets of UCBs per trace o to preserve precision,and derive the maximal set of ECBs per task \(\tau _i\) as the union of the ECBs on all traces.We use \({\gamma }_{i,j,x}\) (with \(j \in {\text {hp}}(i)\)) to denote the overhead (additional accesses) due to a pre-emption of task \(\tau _i\) by task \(\tau _j\) on core \(P_x\).

We use the ECB-Union (Altmeyer et al. 2011, 2012) approach as an exemplar of CRPD analysis, as it provides a reasonably precise bound on the pre-emption overhead with low complexity. (Other CRPD analysis techniques (Altmeyer et al. 2012; Lee et al. 2001) could also be integrated into this framework). The ECB-Union approach first computes the union of all ECBs that may affect a pre-empted task. The intuition here is that direct pre-emption by task \(\tau _j\) is represented by the pessimistic assumption that task \(\tau _j\) has itself already been pre-empted by all of the tasks of higher priority and hence may result in evictions due to the set \(\bigcup _{h \in {\text {hep}}(j) \wedge h \in \Gamma _x} {\text {ECB}}_h\). Note that a CRPD analysis has to correctly account for all pre-emption scenarios including nested pre-emption, as it otherwise may compute optimistic bounds on the CRPD (Altmeyer et al. 2011). The ECB-Union approach considers the maximum impact of these evicting cache blocks on any job of a task \(\tau _k\) that could be running during the response time of task \(\tau _i\), where \(\tau _i\) is the task of interest in the response time analysis. Such a task \(\tau _k\) must have a priority equal to or higher than that of task \(\tau _i\) (otherwise it could not run in the busy period), but lower than that of the pre-empting task \(\tau _j\) (otherwise it could not be pre-empted). These are referred to as the set of affected tasks \({\text {aff}}(i,j) ={\text {hep}}(i) \cap {\text {lp}}(j)\). Further, task \(\tau _k\) must also be on core \(P_x\). Thus the set of potentially pre-empted tasks is therefore indicated by \(k \in {\text {aff}}(i,j) \wedge k \in \Gamma _x\). Further, pre-emption may take place at any program point in any trace of task \(\tau _k\). Putting all this together, the follow expression upper bounds the pre-emption cost by determining the maximum intersection between the evicting cache blocks of task \(\tau _j\) and higher priority tasks and the useful cache blocks at any program point in any trace of any task that can be pre-empted by task \(\tau _j\) during the response time of task \(\tau _i\).For dynamic shared scratchpads, our slight abuse of notation in defining ECBs and UCBs enables the above analysis of pre-emption costs to be used. Recall that for dynamic shared scratchpads, (9) and (10) define the ECBs for a trace as all of the memory blocks that the trace stores in the scratchpad. The UCBs are then defined as equal to the ECBs. With these definitions, the pre-emption cost analysis effectively assumes that at any program point in any trace in any pre-empted task, all of the UCBs (i.e. memory blocks stored in the scratchpad) for that trace are useful and will need reloading if they are evicted by the ECBs (i.e. memory blocks transferred to the scratchpad) by a pre-empting task.

In this section, we instantiate the functions \(S^x_i(t)\), \(A^y_j(t)\), and \(L^y_j(t)\) that count the number of accesses from the cores and are used as input to the BUS function (see Sect. 5), which we use to derive the maximum bus delay that task \(\tau _i\) on core \(P_x\) can experience during a time interval of length t:where \({d_{\text {main}}}\) is the bus access latency to the global memory.

We first compute \(S^x_i(t)\), an upper bound on the total number of bus accesses that can occur due to tasks of priority i or higher running on core \(P_x\) during an interval of length t, while one job of task \(\tau _i\) is active, i.e. within its response time. Since lower priority tasks cannot execute on \(P_x\) during the response time of task \(\tau _i\) (a priority level-i processor busy period), the only contribution from those tasks is a single blocking access as discussed in Sect. 5. The maximum number of accesses is computed assuming task \(\tau _i\) is released simultaneously with all higher priority tasks that run on \(P_x\), and subsequent releases of those tasks occur as soon as possible, while also assuming that the maximum possible number of pre-emptions occur. \({\text {MD}}_k\) denotes the memory demand of task \(\tau _k\) and \(\gamma _{i,k,x}\) accounts for the pre-emption costs on core \(P_x\) due to jobs of task \(\tau _k\).

In the appendix, we show that in the context of the response time analysis given in this paper, it is correct to compute \(S^x_i(t)\) assuming synchronous release with higher priority tasks on the same core.

Recall that we use \(A^y_j(t)\) to denote an upper bound on the total number of bus accesses due to all tasks of priority j or higher executing on core \(P_y \ne P_x\) during an interval of length t. A special case is \(A^y_n(t)\): since \(\tau _n\) is the lowest priority task, this term includes accesses due to all tasks running on core \(P_y\). In contrast to the derivation of \(S^x_i(t)\), for \(A^y_j(t)\) we can make no assumptions about the synchronisation or otherwise of tasks on core \(P_y\) with respect to the release of task \(\tau _i\) on core \(P_x\). The value of \(A^y_j(t)\) is therefore obtained by upper bounding, for each task \(\tau _k\) running on some other core \(P_y\), the number of memory accesses that it could produce in an interval of length t, considering only the time constraints on when jobs of that task can execute. The worst-case scenario is illustrated in Fig. 2. The first job of task \(\tau _k\) executes as late as possible, i.e. just prior to its worst-case response time, while the next and subsequent jobs execute as early as possible. Further, we assume that the first job of task \(\tau _k\) has all of its memory accesses in a region as late as possible during its execution, while for subsequent jobs we assume the opposite is true, with execution and a region of memory accesses occurring as early as possible after release of the job. This scenario maximizes the number of memory accesses from task \(\tau _k\) in an interval of length t, as shown in Fig. 2. This is similar to the concept of carry-in interference used in the analysis of global multiprocessor fixed-priority scheduling (Bertogna and Cirinei 2007; Davis and Burns 2010). Effectively due to local interference from higher priority tasks on its core, the memory accesses of the first job are carried-in to the interval of interest leading to increased interference on the bus during the interval.

In the following, the number of memory accesses in each region, shown in dark grey in Fig. 2, is given by \({ MD}_k + \gamma _{j,k,y}\) and thus the length of each region is \(({ MD}_k + \gamma _{j,k,y}) \cdot {d_{\text {main}}}\). We now upper bound the largest number of memory accesses in an interval of length t due to task \(\tau _k\) executing on core \(P_k\) along with its cache related pre-emption effects. The next job release of task \(\tau _k\) after the carried-in memory accesses (first dark grey region) occurs at a time \(({ MD}_k + \gamma _{j,k,y}) \cdot {d_{\text {main}}}+ T_k - R_k\) after the start of the interval of length t. Subsequent jobs of \(\tau _k\) are then released periodically every \(T_k\). The number of complete periods (by this we mean from the start of one memory access region to the start of the next one) that contribute memory accesses in the interval of length t is given by:The remaining incomplete period in which further memory accesses can occur is therefore of length \(t + R_k - ({ MD}_k + \gamma _{j,k,y}) \cdot {d_{\text {main}}}- N^y_{j,k}(t) \cdot T_k\). In this time at most one memory access can occur every \({d_{\text {main}}}\), up to \({ MD}_k + \gamma _{j,k,y}\) accesses in total. Putting all this together, the total number of accesses possible in an interval of length t due to task \(\tau _k\) (on core \(P_y\)) and its cache related pre-emption effects is given by:We note that \(W^y_{j,k}(t)\) is sustainable (Baruah and Burns 2006) with respect to a reduction in the number of memory accesses per job, and also to the spreading out of memory accesses within a job. Neither can cause the value of \(W^y_{j,k}(t)\) to increase. This can be seen graphically by considering, in Fig. 2, what happens if the number of memory accesses is reduced i.e. the size of the grey regions is reduced, or if the memory accesses are spread out within the jobs. \(W^y_{j,k}(t)\) is also monotonically non-decreasing with respect to t.

Using \(W^y_{j,k}(t)\), we obtain an expression for \( A^y_j(t)\), an upper bound on the total number of bus accesses due to all tasks of priority j or higher executing on core \(P_y \ne P_x\) during an interval of length t, as follows:The value of \(L^y_j(t)\) is obtained in a similar way to \(A^y_j\), but considering accesses with lower priority than j:We note that the carry-in interference was not accounted for in the analysis given by Kim et al. (2014a) (Eqs. (5) and (6) in that paper), resulting in potentially optimistic bounds on the number of competing memory requests.

Global memory is usually realized based on dynamic random-access memory (DRAM), which needs to be refreshed periodically. During a refresh, memory accesses cannot be serviced by the DRAM, and hence DRAM refreshes cause interference on tasks. Now, we show how to take into account delays imposed by refreshes. We assume a DRAM controller with a First Come First Served (FCFS) scheduling policy so that memory accesses cannot be reordered within the controller. Further, we assume a closed-page policy to minimize the effect of the memory access history on access latencies. We consider two refresh strategies (Micron Technologies, Inc. 1999): distributed refresh where the controller refreshes each row at a different time, at regular intervals, and burst refresh where all rows are refreshed immediately one after another.

Under distributed refresh, an upper bound on the maximum number of refreshes within an interval of length t in which m memory accesses occur is given by:where \(\#\text {rows}\) is the number of rows in the DRAM module, and \(T_\text {refresh}\) is the interval at which each row needs to be refreshed. \(T_\text {refresh}\) is usually 64 ms for DDR2 and DDR3 modules. This formula holds, since at most one memory access can be delayed by each of the refreshes, whereas under burst refresh, a single memory access can be delayed by \(\#\text {rows}\) many refreshes. Under burst refresh, the upper bound is given by:Note that the parameter m is redundant in (40); however, we keep it to retain the same signature for the function.

As the number of memory accesses within t is equal to the number of BUS accesses, we can bound the interference due to DRAM refreshes on task \(\tau _i\) on core \(P_x\) as follows:where \(d_\text {refresh}\) is the refresh latency.

The response time \(R_i\) of task \(\tau _i\) is given by the smallest solution to the following recurrence relation:where \({\text {PD}}_i\) is the processor demand for task \(\tau _i\) given by (27), \(I^{\text {PROC}}(i,x,R_i)\) is the interference due to processor demand from higher priority tasks running on the same core assuming no misses on the local memory, given by (28), \(I^{\text {BUS}}(i,x,R_i)\) is the delay due to bus accesses from tasks running on all cores and includes \({\text {MD}}_i\), given by (33), and \(I^{{\text {DRAM}}}(i,x,R_i)\) is the delay due to DRAM refreshes, given by (41).

Since the response time of each task can depend on the response times of other tasks via the functions (37) and (38) describing memory accesses \(A^y_j(t)\) and \(L^y_j(t)\), we use an outer loop around a set of fixed-point iterations to compute the response times of all the tasks, and so deal with the apparent circular dependency. Iteration starts with \(\forall _i:R_i = {\text {PD}}_i+ {\text {MD}}_i\cdot {d_{\text {main}}}\) and ends when all the response times have converged (i.e. no response time changes w.r.t. the previous iteration), or the response time of a task exceeds its deadline in which case that task is unschedulable. See Algorithm 1 for the pseudo-code of the response time calculation. Since the response time \(R_i\) of a task \(\tau _i\) is monotonically increasing w.r.t. increases in the response time of any other task, convergence or exceeding a deadline is guaranteed in a bounded number of iterations.

We note that the analysis is sustainable (Baruah and Burns 2006) with respect to the processor \({\text {PD}}_j\) and memory demands \({\text {MD}}_j\) of each task, since values that are smaller than the upper bounds used in the analysis cannot result in a larger response time. This sustainability extends to traces; if any trace of task execution results in practice in a lower processor or memory demand than that considered by the analysis, then this also cannot result in an increase in the response time. Similarly, a decrease in the set of UCBs or ECBs such that they are a subset of those considered by the analysis cannot increase the worst-case response time.

Note that the definitions of \({\text {MD}}_i\), \({\text {PD}}_i\) and \({\text {ECB}}_i\) completely decouple the traces from the response time analysis. This comes at the cost of possible pessimism, but strongly reduces the complexity of the analysis. Different traces may maximize different parameters, meaning that the combination of the parameters in this way may represent a synthetic worst-case that cannot occur in practice. An alternative solution is to define a multicore response time analysis that is parametric in the execution traces. In the extreme, completely expanding the analysis to explore every combination of traces from different tasks would be intractable. However, as a first step in this direction, response times could be computed for each individual trace of the task of interest \(\tau _i\), using combined traces for all other tasks. The maximum such response time would then provide an improved upper bound.

We note that the presented analysis framework is not fine-tuned to specific hardware features or execution scenarios such as burst accesses, since this counteracts its extensibility and generality.

The analysis presented so far only considers tasks and their execution, as represented by traces. We now outline how the MRTA framework can be extended to cover RTOS and interrupt handler behaviour.

We assume that task release is triggered via interrupts from a timer/counter or other interrupt sources. When an interrupt is raised, the appropriate handler is dispatched and may pre-empt the currently executing task.² When the interrupt handler returns, then if a higher priority task has been released, the scheduler will run and dispatch that task, otherwise control returns to the previously running task. When a task completes, then the scheduler again runs and chooses the next highest priority task to execute.

The behaviour of each interrupt handler is represented by a set of execution traces similar to those for tasks. Thus interrupt handlers can be included in the MRTA framework in a similar way to tasks, but at higher priorities. (We note that there may be some differences if all interrupts share the same interrupt priority level; however due to the wide variety of possible arrangements of interrupt priorities, we do not go into details here). In some cases, interrupt handlers may be prohibited from using the cache, have their own cache partition, or have their code permanently locked into a scratchpad. All of these possibilities can be covered using variants of the analysis described in Sect. 6.

The RTOS is different from interrupt handlers and tasks in that it is not a schedulable entity in itself, rather RTOS code is run as part of each task, typically before and after the actual task code, and interleaved with it in the form of system calls. Similarly with interrupt handlers that release tasks, RTOS code is typically called as the handler returns. With our representation of tasks and interrupt handlers as sets of traces, execution of the RTOS can be fully accounted for by a concatenation of the appropriate sub-traces for the RTOS onto the start and end of the traces for tasks and interrupt handlers.

The analysis presented in Sect. 6 assumes that tasks are independent in the sense that they do not share software resources that must be accessed in mutual exclusion, rather the only contention is over hardware resources. We now consider how that restriction can be lifted.

We assume that tasks executing on the same core may share software resources that are accessed in mutual exclusion according to the stack resource protocol (SRP)  (Baker 1991). Under SRP, a task \(\tau _i\) may be blocked from executing by at most a single critical section where a task of priority lower than i locks a resource shared with task \(\tau _i\) or a task of higher priority. Further, under SRP, blocking only occurs before a task starts to execute, thus SRP introduces no extra context switches. We assume a set of traces \(O^B_i\) for all of the critical sections that may block task \(\tau _i\).

In the MRTA framework, the impact of blocking needs to be considered in terms of both processor and memory demand. This can be achieved by considering the traces \(O^B_i\) as belonging to a single virtual task with higher priority than \(\tau _i\). Thus we obtain a contribution \(PD^B_i\) to the processor demand which is added into \(I_i(i,x,t)\) and a contribution \(MD^B_i\) to the memory demand which contributes to \(S^x_i(t)\).

Accounting for the CRPD effects due to blocking are more complex, here we make use of the approach given by Altmeyer et al. (2012) to extend the ECB-Union approach to accounting for pre-emption costs to take account of blocking.

Specifically, we extend the formula for the pre-emption cost (32) to include the UCBs of tasks in the set b(i, j), where b(i, j) is defined as the set of tasks with priorities lower than that of task \(\tau _i\) that lock a resource with a ceiling priority higher than or equal to the priority of task \(\tau _i\) but lower than that of task \(\tau _j\). These tasks can block task \(\tau _i\), but can also be pre-empted by task \(\tau _j\). Hence they need to be included in the set of tasks \({\text {aff}}(i,j)\) whose UCBs are considered when determining the pre-emption cost \(\gamma _{i,j,x}\) due to task \(\tau _j\):Tasks in b(i, j) have lower priorities than task \(\tau _i\) and so cannot pre-empt during the response time of task \(\tau _i\), hence their ECBs do not need to be considered when computing \(\gamma _{i,j,x}\). Using (43) extends the ECB-Union approach (32) to correctly account for pre-emption costs when tasks share resources according to the SRP. We note that the simplest form of resource locking, sometimes called critical sections has the resource accesses at the highest priority. In that case, there is no additional pre-emption cost, since no tasks can pre-empt the critical sections, and so b(i, j) is empty.

Blocking due to software resources accessed by tasks on other cores does not affect the term \(A^y_n(t)\) since SRP introduces no additional context switches, and at the lowest priority level n, there are no extra tasks to include in the CRPD computation (b(n, j) is empty, since there are no tasks of priority lower than n). The value of \(A^y_j(t)\) used in the analysis of a Fixed-Priority bus is also unchanged due to resource accesses, since we assume that the bus access priority reflects only a task’s base priority, rather than any raised priority as a result of SRP.

We note that accounting for resources that are shared between tasks on different cores using for example the MSRP (Gai et al. 2001) or MrsP (Burns and Wellings 2013) protocols is beyond the scope of this paper.

The basic analysis for the MRTA framework given in the paper assumes that we have information (i.e. traces etc.) for all of the tasks in the system. There are a number of reasons why this may not be the case: (i) the system may be open, with tasks on one or more cores loadable post deployment, (ii) the system may be under development and the tasks on another core not yet known, (iii) incremental verification may be required, so no assumption can be made about the tasks executing on another core, (iv) the system may be mixed criticality and tasks on another core may not be developed to the same criticality level, and hence cannot be assumed to be well behaved. Instead we must assume they may exhibit the worst possible behaviour.

For a core \(P_y\) where we have no information, or need to assume the worst, we may replace \(A^y_j(t)\) and \(A^y_n(t)\) with a function that represents continual generation of memory accesses at the maximum possible rate. In practice, this may be equivalent to simply setting \(A^y_j(t) = A^y_n(t) = \infty \). We note that analysis for TDMA and Round-Robin bus arbitration still results in bounded response times in this case, while the analysis for FIFO and Fixed-Priority arbitration will result in unbounded response times. With arbitration based on processor priority, then bounded response times can only be obtained if \(P_y\) is a lower priority processor than \(P_x\). We note that the use of memory throttling mechanisms may result in a bounded number of memory accesses from a core \(P_y\) in any given time interval, independent of the tasks running on that core. Such a bound can be used to define an appropriate interference function \(A^y_j(t)\).

In our first set of experiments, we examine derivatives of the reference architecture assuming the different bus arbitration policies presented in Sect. 5 and also a hypothetical perfect bus which eliminates all bus interference if the bus utilization is \(\le \)1.

Figure 5 shows the number of schedulable task sets plotted against the core utilization (computed using the base WCETs on the reference architecture) and Fig. 6 against the bus utilization \(U^{\text {BUS}}\).

Most traces from Table 2 have a high memory demand, which results in a large number of bus accesses even at low core utilizations. Consequently, many task sets are not schedulable even with a perfect bus. The Fixed-Priority bus (green line) where the memory accesses inherit the task priority shows the best performance, followed by Round-Robin (black line) and then TDMA (purple line). Note for TDMA and Round-Robin, we assume a cycle with 2 slots per core.

The FIFO bus shows the lowest performance, closely followed by the Processor-Priority bus (PP). The worst-case arrival pattern for a FIFO bus (yellow line) assumes that each potentially co-running task has issued bus requests just before the release of the task of interest, which results in a very pessimistic bus contention and response times. The analysis for the Processor-Priority bus (light blue line) assumes that only accesses due co-running tasks assigned to a core of higher priority cause interference, which explains the improved performance compared to the FIFO bus. We note that the task set generation does not optimize the task assignment with respect to the Processor-Priority bus. Such an optimization could greatly improve the relative performance of this policy by assigning tasks with shorter deadlines to a core with higher priority.

The difference between the Fixed-Priority and Round-Robin/TDMA policies shows the MRTA framework is able to guarantee good real-time performance even if the bus policy does not provide a tightly bounded bus latency for single accesses, as is the case with TDMA and Round-Robin.

In our third set of experiments, we examine derivatives of the reference architecture assuming the different types of local memory as presented in Sect. 4, a hypothetical perfect cache which eliminates all memory accesses, and a configuration without any caches. Local caches are either partitioned per task, with a uniform partition size, or unconstrained, meaning that all tasks on the same core share the same local cache and can potentially use all of it. The scratchpads are partitioned per task and are configured statically to store the most frequently used memory blocks. We present results for the partitioned and unconstrained cases assuming either a cold cache, or a warmed-up cache where memory blocks have been loaded into the cache by running all tasks once during a warm-up phase (see Sect. 4). Irrespective of the type of local memory, its size remains constant at 16kB.

Figure 10 shows the number of schedulable task sets plotted against the core utilization (computed using the base WCETs on the reference architecture), and Fig. 11 the number of schedulable task sets plotted against the bus utilization \(U^{\text {BUS}}\).

In our third set of experiments, we compare the reference architecture with two alternatives. The first, referred to as the full-isolation architecture is a derivative of the reference architecture that implements complete spatial and temporal isolation. The local caches are partitioned with an equal partition size for each task and the bus uses a TDMA arbitration policy. All other parameters remain the same as for the reference architecture. Performance on the isolation architecture corresponds to the traditional two-step approach to timing verification with context-independent WCETs. In addition, we note that the isolation architecture can be considered as a software configuration of the reference architecture. The second alternative, referred to as the predictable architecture, has been designed to maximize the guaranteed real-time performance. From the previous evaluation, we found that using scratchpad memory with a write-back policy and a Fixed-Priority bus outperforms all other configurations in terms of guaranteed real-time performance. These components and policies were therefore chosen for the predictable architecture.

Figure 15 shows the number of schedulable task sets plotted against the core utilization (computed using the base WCETs on the reference architecture).

For the reference architecture and the full-isolation architecture, we assumed warmed-up caches as detailed in Sect. 4.

We observe that the predictable architecture, tailored towards guaranteed real-time performance, accumulates the performance benefits of both scratchpads and a Fixed-Priority bus; its performance far exceeds that of the full-isolation architecture, which uses partitioned caches and a TDMA bus, and that of the reference architecture, which uses shared caches and a Round-Robin bus.

Based on our experiments, we were able to identify three main sources of over-approximation (pessimism) in the MRTA framework: The number of memory accesses on the same core cannot be precisely estimated due to imprecision in the pre-emption cost analysis. The interference due to bus accesses may be pessimistic as not all tasks running on another core can simultaneously access the bus. The DRAM refreshes are assumed to occur too frequently if the number of main memory accesses are over-approximated. In this section, we examine the precision of the analysis for the different architectures using the simulator described in Sect 8.

In the previous experiments, we investigated architectures and configurations assuming a total of 32 tasks distributed over 4 cores. Since all tasks are assumed to be sporadic with no relationship between their release times, we cannot reduce the state space of possible scenarios that could be simulated. Consequently, the multicore simulator is only able to cover a negligibly small fraction of the total state space. In order to achieve a meaningful level of coverage, we reduced the number of tasks in the system to 8. The simulation runs for \(10^9\) cycles or until it detects a deadline miss. Further, we use the WCET in isolation on the predictable architecture, instead of on the reference architecture for the task-set generation.⁵

The results are shown in Fig. 16. The dashed lines indicate results from the simulator and solid lines results from the MRTA analysis.

The predictable architecture not only provides the highest level of guaranteed real-time performance, but also the tightest results. Both lines, the solid line for the results of the analysis and the dashed line for results from the simulator are close, which indicates a high precision in the analysis. For the other two architectures, i.e., the reference architecture and the full-isolation architecture, we cannot draw the same conclusion. In these cases, there are large differences between the lower and upper bounds on the number of schedulable task sets. We note that this could be due to imprecision in the necessary test formed by the simulation, imprecision in the sufficient test given by the MRTA framework, or both.

The reference architecture is optimized towards achieving good average case performance, whereas the predictable architecture is optimized towards guaranteed real-time performance. From the results of the simulation, we observe that the optimization targets may have been achieved. The upper bound on the number of schedulable task sets for the reference architecture is well above the upper bound for the predictable architecture. On the other hand, the predictable architecture provides significantly better guaranteed performance. The results provide an indication that multicore architectures should be tailored towards their intended use.