Architectural support for real-time task scheduling in SMT processors

Architectural Support for Real-Time Task Scheduling in SMT Processors FranciscoJ. Cazorla1, Peter M.W. Knijnenburg2, Rizos Sakellariou3, Enrique Fernandez4, Alex Ramirez1,5, Mateo Valero1,5 1DAC, UPC, Spain, {fcazorla,aramirez,mateo}@ac.upc.es. 2LIACS, Leiden University, the Netherlands, [email protected]. 3University of Manchester, UK, ri[email protected]n.ac.uk. 4University of Las Palmas de Gran Canaria, Spain. [email protected]. 5Barcelona Supercomputing Center, Spain. Abstract In Simultaneous Multithreaded (SMT) architectures most hardware resources are shared between threads. This provides a good cost/performance trade-off which renders these architectures suitable for use in embedded systems. However, since threads share many resources, like caches, they also interfere with each other. As a result, execution times of applications become highly unpredictable and highly dependent on the context in which an application is executed. Obviously, this poses problems if an SMT is to be used in a (soft) real time system. In this paper, we propose two novel hardware mechanisms that can be used to reduce this performance variability. In contrast to previous approaches, our proposed mechanisms do not need any information beyond the information already known by traditional job schedulers. Neither do they require extensive profiling of workloads to determine optimal schedules. Our mechanisms are based on dynamic resource partitioning. The OS level job scheduler needs to be slightly adapted in order to provide the hardware resource allocator some information on how this resource partitioning needs to be done. We show that our mechanisms provide high stability for SMT architectures to be used in real time systems: the real time benchmarks we used meet their deadlines in more than 98% of the cases considered while the other thread in the workload still achieves high throughput. DAC, UPC. Technical Report. May 2005. Cazorla et al. 1 Introduction Current processors take advantage of Instruction Level Parallelism (ILP) to execute in parallel several independent instructions from a single instruction stream (thread). However, there is only a limited amount of parallelism available in each thread due to data and control dependences [11], which degrades performance. In order to alleviate these problems many hardware resources are required, degrading the performance/cost ratio of these processors. A solution to improve the performance/cost ratio of processors is to allow threads to share hardware resources. In current processors, resource sharing can occur at different ways. At one extreme of the spectrum, there are multiprocessors (MPs) that only share some levels of the memory hierarchy. On the other extreme, there are ‘full-fledged’ simultaneous multithreaded processors (SMTs) that share many hardware resources, improving their performance/cost ratio [8]. However, in SMT processors, threads may also interfere because they share many resources. This implies that the speed a thread obtains in one workload can be very different from the speed it has in another workload [4]. We refer to this by saying that an SMT processor has a high variability. Obviously, high variability is an undesirable property in a real time environment. Not only needs the job scheduler take into account Worst Case Execution Times and deadlines when selecting a workload, it should also know about how the workload can affect the Worst Case Execution Time. Note that redefining WCET as the longest execution time in an arbitrary workload is not an option. By carefully selecting a workload, the WCET could be made arbitrarily large. Moreover, analytical approaches to WCET would fail miserably if they would need to take a context into consideration. The execution time of a thread depends on the amount of execution resources given to it. In a system with single-thread processors, a thread has exclusive access to all available hardware resources, so that this is not a problem. In an SMT processor the amount of resources given to a thread varies dynamically. An instruction fetch policy, e.g., icount [10], decides how instructions are fetched from the threads, thereby implicitly determining the way internal processor resources are allocated to the threads. The key point is that current fetch policies are designed with the main 2 DAC, UPC. Technical Report. May 2005. Cazorla et al. objective of increasing processor throughput, what may differ from the objective of the global system, in our case, a real-time environment. This could compromise the objective of the real-time system meeting tasks deadlines [2] if some measures are not taken. In addition, current OS level job schedulers perceive the different contexts of an SMT as independent processing units and assume that threads have exclusive access to the hardware resources when scheduled on a processing unit. These assumptions are inherited from multiprocessors, but are not valid for SMTs. Threads in an SMT share the same hardware resources, so that the behavior and the resources used by one thread affect all other threads in the workload. To sum up, in current systems the performance/cost versus variability trade-off is clear. MPs have lower variability but bad performance/cost ratio. SMT implies a good cost-performance relation but high variability in the execution time of an application depending on the context in which it is executed. In the literature, several solutions have been proposed in order to improve this trade-off [5][7][9]. The common characteristic of these solutions is that they assume knowledge of the average number of Instructions Per Cycle (IPC) of applications when they are executed in isolation, IP Calone. In other words, these solutions are IPC based. This implies, as we show later, that these solutions are applicable for a subset of real-time applications, where the IP Calone of applications can be a priori obtained. As far as we know there is not any proposal that deals with this problem when the IP Calone of applications is not know. In such a case time-critical threads are given all the performance of the SMT [2]. This, of course, solve the problem but provides low throughput. In this paper we propose a novel mechanism to enforce real time constraints in an SMT based system. This mechanism consists of a small extension of the OS level job scheduler and an extension of the SMT hardware, called a Resource Allocator. Our approach is resource based instead of IPC based. By this we mean that it relies on the amount of resources given to the time-critical thread. The job scheduler assembles a workload for the SMT processor and instructs the Resource Allocator to dedicate at least a certain amount of resources to the time critical thread so that it is guaranteed to meet its deadline. Apart from this, the Resource Allocator tries to adjust the resource allocation in order to maximize performance. The current paper is focused on the Resource Allocator. In future work, we hope to give a working 3 DAC, UPC. Technical Report. May 2005. Cazorla et al. implementation of the job scheduler as well. Our approach is feasible for real-time applications. With our method time-critical applications meet their deadline more than 98% of times while the non-crtical applications still achieve high performance. This paper is structured as follows. Section 2 presents some background on SMTs and real-time scheduling. In Section 3 we present existing approaches to solve the high variability of SMTs. In section 4, we explain the experimental environment. Sections 5 presents our two mechanisms. Section 6 is devoted to show the simulation results. In section 7 we explain the hardware/software changes required to implement our mechanism. Finally, conclusions are given in Section 8. 2 Background on SMTs and Real-Time Scheduling In this section we give some background on SMT processors and real-time scheduling. In particular, we discuss some of the challenges to develop a real-time scheduler for SMT processors. 2.1 SMT processors In an SMT, the front end of a superscalar processor is adapted in order to be able to fetch from several threads while the back end is shared between threads. Thus, the same physical resources, like functional units or the branch predictor, are used by several threads at the same time as schematically depicted Figure 1. Several Program Counters (PCs) are used in the instruction fetch stage and the other stages are shared between the threads. A fetch policy, like icount [10], determines from which threads the next instructions are fetched. Moreover, by doing so, the fetch policy also implicitly determines the way internal processor resources, like physical registers or window entries, are allocated to threads. This is a major cause of performance variability in SMT processors: the speed of a thread highly depends on the context in which it is executed. Next, instructions are decoded and renamed in order to track data dependences. When an instruction is renamed, it is allocated an entry in the window or issue 4 DAC, UPC. Technical Report. May 2005. Cazorla et al. Decode Fetch Rename Instruction Cache PCs LSQ IQ FPQ IREG Read FREG Read IREG Write FREG Write Execution Data Cache ROB Figure 1: Baseline architecute queues (integer, floating point and load/store) until all its operands are ready. Each instruction also allocates one Re-Order Buffer (ROB) entry and a physical register in the register file, if required. ROB entries are assigned in program order and instructions wait in this buffer until all earlier instructions are resolved. When an instruction has all its operands ready, it is issued: it reads its operands, executes, writes its results, and finally commits. 2.2 Real-Time Scheduling Real-time systems are characterized by a group of repetitive tasks, called a task set. For each task, the scheduler knows three main parameters. First, the period, that is, the interval at which new instances of a task are ready for execution. Second, the deadline, that is, the time before which an instance of the task must complete. For simplicity, the deadline is often set equal to the period. This means that a task has to be executed before the next instance of the same task arrives in the system. Third, the Worst Case Execution Time (W CET ) is an upper bound on time required to execute any instance of the task that is guaranteed never to be exceeded. 5 DAC, UPC. Technical Report. May 2005. Cazorla et al. In soft-real time scheduling, the main purpose of the scheduler consists of finding a feasible schedule for the task set. Many algorithms have been proposed to solve this problem in single-threaded systems (e.g., EDF or LLF). However, these algorithms are no longer sufficient in an SMT processor, since the execution time of a thread is unpredictable when this thread is scheduled with other threads. Algorithms should be adapted to meet this new situation. As pointed out in [7], the problem of scheduling a set of tasks turns into two different problems in SMT systems. The first problem is the same as for multiprocessors, namely, to select the set of tasks to run. This problem is called the workload selection problem. The second problem consists of determining how resources are shared between threads. In this paper, we focus on the latter problem that is also known in the literature as the resource sharing problem. The high variability of SMT processors implies that the task of a real-time jobscheduler for SMT processors is much more complex and challenging than for singlethreaded processors. When scheduling a job, the job-scheduler must take into account the amount of resources given to a thread, which is implicitly decided by the instruction fetch policy, in order to ensure that it meets its deadline. 3 Existing Approaches In [2], the authors propose an approach where the WCET is specified assuming a virtual simple architecture (VISA). At execution time, a task is executed on the actual processor. Intermediate virtual deadlines are established based on the VISA. If, during execution, a task fails to meet its intermediate deadlines, the processor is reconfigured to implement the VISA, bounding the execution time of the task. If the actual processor is an SMT using a fetch policy that attempts to maximize throughput, and a task fails to meet its intermediate deadlines, the SMT is switched to single-threaded mode. The authors conclude that fetch policies that attempt to maximize throughput, like icount, should be “balanced” for minimum forward progress of real-time tasks. This is precisely the target of our paper: we ensure a minimum amount of resources for a given time-critical thread so that it meets its deadline regardless of the other threads executed in its workload. Our approach is 6 DAC, UPC. Technical Report. May 2005. Cazorla et al. orthogonal to the VISA framework: a time-critical thread is executed on the actual SMT processor that provides the thread with a given percentage of resources. In the event that the task does not meet its intermediate deadlines, instead of switching the processor to single-threaded mode, we can increase the amount of resources given to it, so that it meets its deadline and total performances does not drop drastically. As far as we know, there are three main studies dealing with real-time scheduling for SMTs. Two of these focus on real-time systems [5][7] while the third focuses on general-purpose systems [9]. In [7], the authors focus on workload selection in soft-real time systems, although they also briefly discuss the resource sharing problem. The authors propose a method to solve the problem of high variability of SMTs that profiles all possible combinations of tasks. By comparing the IPC of a thread when it is executed in a given workload, IP CSMT , with the IPC that threads achieves when it is run in isolation, IP Calone, the slowdown that the thread suffers from being executed in a context is determined. This information is given as additional input to the scheduler that uses this information to maximize performance since the scheduler selects those workloads that lead to the highest symbiosis among threads and thus the highest performance. The main drawback of this solution is the prohibitively large number of profiles required. For a task set of Ktasks and a target processor with Ncontexts, we have to profile all N! K!(N−K)! possible combinations. A similar solution is proposed in [9]. The authors propose several OS level job schedulers to enforce priorities in a general-purpose system. Mostly, these schedulers find co-schedules from a pool of runnable jobs that is larger than the number of hardware contexts. Their SOS policy runs jobs alone on the machine to determine their full speed, runs several job mixes in order to determine the best mix that exhibits symbiosis, and finally runs jobs alone in order to meet priorities. Finally, in [5] we have proposed a hardware mechanism to run a given thread at a given percentage of its full speed, IP Calone, in an arbitrary workload. If it is required to run a thread Aat an target IPC that is X% of the IP Calone of that thread, then the IPC of the critical thread is periodically measured and the mechanism tries to run that thread at X% of the last measured speed. It has been shown that this approach can realize an arbitrary required percentage of the IP Calone of a critical 7 DAC, UPC. Technical Report. May 2005. Cazorla et al. thread in widely different workloads. A common characteristic of these studies is that they are IPC based, that is, they require the IP Calone of threads. By comparing the IPC of a thread in a workload with its IP Calone, these methods converge to a solution. In this paper, we propose a different way of approaching the problem. Instead of using the IPC of applications to drive the solution, we use resource allocation that normally is implicitly driven by the instruction fetch policy. Our method makes explicit to the scheduler the amount of resources used by each thread. The scheduler adjusts this allocation to guarantee that applications meet their deadlines. The main advantage of our method is two-fold. First, it is well known that IPC values can be highly dependent on the input of an application. For some types of real-time applications, such as multimedia applications [6], this dependence is weak: the IPC of such an application is roughly independent from the input. But for other types of applications this is not the case. Our method does not require this information so that it is applicable to all types of real-time applications. Second, we achieve a similar or even better success rate than the approaches discussed above, while improving overall performance. 4 Experimental Environment In this section, we discuss both our baseline architecture used to run our experiments, the benchmarks we use, and the metrics we employ to compare the different proposals. 4.1 SMT Simulator In order to evaluate the performance of the different policies, we use a trace driven SMT simulator derived from smtsim [10]. The simulator consists of our own trace driven front-end and an improved version of smtsim’s back-end. The simulator allows executing wrong path instructions by using a separate basic block dictionary that contains all static instructions. We use an aggressive configuration, shown in Table 1: many shared resources 8 DAC, UPC. Technical Report. May 2005. Cazorla et al. (issue queues register, functional units, etc.), very wide superscalar, and a deep pipeline for high clock rate. These features cause the processor performance to be very unstable, depending on the mix of threads. Thus, this configuration represents an unfavorable scenario where we evaluate our proposals. It is clear that, if those proposals work in this hard configuration they will work better in narrower processors with fewer shared resources. Table 1: Baseline configuration Processor Configuration Default fetch policy icount 2.8 Pipeline depth 12 stages Fetch/Issue/Commit Width 8 Queues Entries 64 int, 64 fp, 64 ld/st Execution Units 6 int, 3 fp, 4 ld/st Physical Registers 256 integer, 256 fp (shared)ROB size 512 entries Branch Predictor 16K entries gshare Branch Target Buffer 256-entry, 4 ways Return Address Stack 256 entries Memory Configuration Icache, Dcache 64 Kbytes, 2-way, 8-bank, 64-byte lines, 1 cycle access L2 cache 2048 Kbytes, 8-way, 8-bank, 64-byte lines, 20 cycle access Main memory latency 300 cycles TLB miss penalty 160 cycles 4.2 Benchmarks We use workloads consisting of two threads. The first thread is the critical thread (CT) that represents the thread with the most critical time restriction or the soft real time thread. The second thread is a non-critical thread (NCT) that is assumed either to have less-critical time restrictions or to have no time restrictions at all. As critical threads we use programs from the MediaBench Benchmark suite, namely, adpcm,epic,g721,gsm and mpeg2. We used both the coder and the decoder of these media applications. Hence, we use 10 media applications as critical threads. Table 4.2 shows the inputs for each of the MediaBench benchmarks. We want to check the efficiency of the resource allocator under scenarios where the NCT requires many resources, and thus, where the performance of the CT could be more affected. For this reason, we use as non-critical threads benchmarks from the SPEC2000 integer and fp benchmark suite that require more resources than media applications. Each of the ten media applications is executed with 8 different benchmarks from the SPEC200 benchmark suite as non-critical thread. We have 9 DAC, UPC. Technical Report. May 2005. Cazorla et al. 5.3.1 Caches and TLBs Regarding TLBs on average for all the experiments made in this paper the number of data TLB miss per instruction is 3.6×10−4and the number of instruction TLB misses is 8.2×10−7. Hence, the influence on the execution time of the CT is small. For this reason we do not control TLBs. Regarding caches, we measure for each multi-media application in all ten workloads the average number of misses in each cache with respect to the number of committed instructions as we vary the amount of resources given to it, see figure 3. We observe that there is an increase in cache miss rate caused by interference by another application in the workload. We observe as well that this interference is lower when the amount of resources given to the CT is higher and vice-versa. This is caused by the fact that if the CT is allowed to use many resources, the NCT executes slower and hence uses caches less frequently and thus produces less interference. The absolute number of misses per committed instruction is low: lower than 2×10−4for the icache, 7 ×10−3for the data cache, and 4 ×10−3for the L2 cache. We can draw two conclusions from these figures. First, in the icache there is almost no interferences between the CT and the NCT. Second, the interference introduced in the caches by a non-critical thread in a workload is so small that we expect that this only slightly affects the execution time of multimedia applications. As a result, we do not need to control how caches are shared between the threads. 5.3.2 Other resources We systematically measured the effect of controlling the resources other than the caches. We looked at the following resource partitions. Nothing means that we do not control any resource inside the SMT. Resources are implicitly shared as determined by the default fetch policy. Fetch means that we prioritize the CT when fetching instructions from the instruction cache. Queues and Registers mean that we give a fixed amount of entries of that resource to the CT. Furthermore, we made all combinations of these resources 2. 2The issue bandwidth provides small variations in the results. For this reason we do not show its results. 16 DAC, UPC. Technical Report. May 2005. Cazorla et al. In Figure 4(a), we show for the gsm decoder benchmark its actual IPC values for two possible ways to partition resources: when we prioritize instruction fetch and when we moreover partition the registers and the issue queues. From this figure, it is immediately clear that controlling the instruction fetch alone gives little control over the speed of the CT and the variability in IPC is large. On the other hand, controlling queues, registers and fetch does give much control over the speed of the CT and hence the variability is low. In order to measure the sensitivity of the variability to resource partitioning more systematically, we proceed as follows. We used all pairs of media benchmarks as CT and spec2000 benchmarks as NCT. We measured execution times of the CT. For each CT from the MediaBench suite, we obtained 8 numbers, one for each spec benchmark. We computed the mean and the standard deviation of these numbers, and the fraction deviation/mean. In this way, we obtain a measure of the variability in execution time of a CT as we change the NCT, expressed relative to the average execution time. This allows us to average these values over all possible critical threads. This final average is the overall measure of variability used in this study. In Figure 4(b) we show these results. We can immediately observe that when we do not control resource allocation, we get a high variability of 40%. This can be interpreted as that in many cases the difference in execution time of a CT in an arbitrary context can be as high as 40% of the total execution time or even higher. If we only prioritize the instruction fetch of the CT, this variability is hardly reduced. The most important resources to control are the registers and the issue queue entries. The best results are obtained when we control everything: we give the CT priority in instruction fetch and reserve a certain amount of registers and issue queue entries for it. These are the resources controlled by our Resource Allocator below. Regarding the percentage of resources given to the CT, we show that as we decrease this amount the variability increases. For low percentages (10%, 20%) variability is even higher than when no control is carried out. This is mainly because when the CT uses few resources the NCT executes more instructions causing more interferences. In addition, every time the CT misses in cache it has not enough resources to hide this latency, even L1 data cache misses. Hence, we conclude that the minimum amount of resources reserved for the CT is 20%. 17 DAC, UPC. Technical Report. May 2005. Cazorla et al. 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 I21 I22 I23 I24 M21 M22 M23 M24 I21 I22 I23 I24 M21 M22 M23 M24 Fetch Control Fetch, IQs & Regs Control IPC of the gsm_d benchmark (a) Raw data when we control only the fetch, and when we control the fetch, the IQs and registers. 0 5 10 15 20 25 30 35 40 45 50 no control Fetch (F) Queues (Q) Q & F Registers(R) R&F R&Q R&Q&F Average (Average Absolute Deviation / Mean) 90% 80% 70% 60% 50% 40% 30% 20% 10% (b) Average of the fraction (Standard Deviation / Mean). Figure 4: Variability in the IPC of the CT for different workloads as we vary the amount of resources under control. 5.4 Static approach In this section, we discuss our static approach to resource partitioning. In this approach, the job scheduler computes a priori the resource partitioning that is used 18 DAC, UPC. Technical Report. May 2005. Cazorla et al. throughout the entire period of the critical thread. In Figure 2, we have plotted to relation between the amount of resources dedicated to the CT and the performance it obtains. It clearly follows that, for all benchmarks considered in this paper, the relation between performance and amount of dedicated resources is super-linear. That is, if we dedicate X% of the resources, we obtain more than X% of IP Calone and in some cases much more. Since the job scheduler knows the WCET of the critical thread and the period in which it should execute, it knows the slow down the CT can suffer: the slow down factor S=P W CET discussed above. Hence, given this fraction Sof the performance of the CT, it needs to compute a function f(S) = Y to determine that the CT needs Y% of the resources to obtain this performance. We call such a function a performance/resource function or p/r function. In this paper, we have experimented with different p/r functions. Hence, when the job scheduler assembles a workload with a certain application as critical thread, it computes the value of Sand determines the corresponding value f(S) for a p/r function f. Then it instructs the resource allocator to reserve f(S)% of the resources for this critical thread. In the next subsection, we discuss performance/resource functions in more detail. 5.4.1 Performance/resource functions Figure 5(a) shows the actual p/r relation of each thread and several p/r functions that approximate this actual p/r relation, which can be used by the job scheduler. These functions are plotted as circles in the figure. We show several functions that are given by r=f(p) = p1/value for value equal to 1 (linear), 0.7, and 0.4. For lower values, the amount of resources given to the CT is reduced and the actual p/r relation is better approximated. This may be positive since we allow the NCT to use more resources. However, this may also compromise the success rate. For our experiments discussed in the next section, we use the p/r functions described above. We moreover use another p/r function that is more directly based on the graphs shown in Figure 2, called adhoc. In order to construct this function, we determine for each Multimedia Benchmark and for each possible value of p, the value of rby reading the curves from x-axis to y-axis. Figure 5(b) shows two examples of how the function adhoc is determined. The diamonds show the actual p/r relation 19 DAC, UPC. Technical Report. May 2005. Cazorla et al. for the adpcm c and gsm d functions benchmarks. The circles show the approximation we used. Note that this approximation is slightly larger than the corresponding value in the curve in Figure 2 in order to take into account interference by the NCT, mainly for low percentages of p. 5.5 Dynamic approach In this approach, the resource allocator dynamically determines the amount of resources given to the critical thread. The main advantage of this method is that it adapts to program execution phases, increasing overall performance. In the next section, we show that the dynamic approach provides better results than the static approach but it is only suitable if the application under consideration has a number of characteristics that we discuss in more detail below. The main advantage of the static approach is that it can be used always. The mechanism bases on the observation that in order to realize X% of the overall IPC for a given job, it is sufficient to realize X% of the maximum possible IPC at every instant throughout its execution. In the present case, if we want to slow down an task with a factor S, it is sufficient to slow it down with a factor Sat every instant. The dynamic approach that exploits this observation is a simplification of the method we proposed in [5], called Predictable Performance or PP. The resource allocator distinguishes two phases that are executed in alternate fashion. We briefly describe these phases below. For more information, please consult [5]. During the first phase, the sample phase, all resources under control are given to the CT and the NCT is temporarily stopped. As a result, we obtain an estimate of the current IP Calone of the CT which we call the local IP Calone. The sample phase starts with a warm up period of 50,000 cycles that is used to remove pollution by the NCT from the shared resources. Next, we measure the IP Calone of the critical thread using a period of 10,000 cycles. During the second phase, the tune phase, the NCT is allowed to run as well. Our mechanism dynamically varies the amount of resources given to the CT to achieve an IPC that is equal to the local IP Calone ×S. The tune phase lasts 300,000 cycles. 20 DAC, UPC. Technical Report. May 2005. Cazorla et al. 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 (p) relative IPC (r) amount of resources adpcm_c adpcm_d epic_c epic_d g721_c g721_d gsm_c gsm_d mpeg2_c mpeg2_d linear(power 1) power 0.7 power 0.4 (a) Different arguments for the Power function 0 10 20 30 40 50 60 70 80 90 100 0 10 20 30 40 50 60 70 80 90 100 (p) relative IPC (%) (r) amount of resources (%) adpcm_c real adpcm_c approx. gsm_d real gsm_d approx. (b) Adhoc function Figure 5: Different performance/resources functions 21 DAC, UPC. Technical Report. May 2005. Cazorla et al. It is divided in periods of 15,000 cycles during which the realized IPC of the critical thread is measured. If this measured value is lower than required, the CT is assigned more resources. If, on the other hand, it is higher than required, resources are taken away from the CT and given to the NCT. The main difference between the present dynamic approach and the Predictable Performance mechanism from [5] is that the present approach controls fewer resources. In particular, we do not exercise control over the caches, in contrast to PP in which L2 cache miss rates of the critical thread are monitored and this information is used to dedicate part of the L2 cache exclusively to the critical thread. Moreover, in PP the real value of IP Calone of the CT is used to compute resource allocations in the tune phase. This value has to be provided by the OS, in contrast to the present approach that does not require this value. The main difficulty in our dynamic method is to measure accurately the local IP Calone of the CT, due to the pollution created by the NCT in the shared resources. As we have shown in [5], the main source of interaction among the CT and the NCT is the L2 cache. This pollution stays for a long time, up to 5 million cycles. We have analyzed the pollution caused by the NCT in this resource in detail. We found that for multi media applications the measured value of the IP Calone is 1% lower than the real value. For SPEC benchmarks used in [5], it is 8% lower. The main reason for this is that media applications have a smaller working set than spec benchmarks. For this reason, an NCT does not interfere as much with media applications as with spec benchmarks. As a result, we can use a more simple resource partitioning algorithm for media applications than the algorithm from [5] that is geared toward general purpose applications. We conclude that, if applications under consideration have a small working set in comparison with the L2 cache size, then they are unlikely to be affected by a NCT with a much larger working set. As a result, the IPC measured in the sample phase is closer to the actual IP Calone, what allows us to leave the L2 miss rate out of consideration, thereby considerably simplifying the mechanism. If this condition is not satisfied, the dynamic approach cannot be applied and we have to resort to either the static approach discussed above or to the expensive mechanism described in [5]. 22 DAC, UPC. Technical Report. May 2005. Cazorla et al. To summarize, in the dynamic approach, the job scheduler provides the value Sto the resource allocator. Next, the resource allocator determines the IP Calone of that instance of the task during a sample phase and reduces its IPC by a factor of Sduring the subsequent tune phases. This implies that the CT can meet its deadline and that we minimize the amount of resources given to the CT, enabling high performance of the NCT. 6 Simulation Results In this section, we present the results of the static and dynamic approaches. Moreover, we show the results obtained using the Predictable Performance mechanism we presented in [5] and a fetch control like mechanism [2][9]. 6.1 Static method Figure 6 shows the success rate and the performance for the different p/r functions used in the static method. In figure 6(a) bars show the success rate and are measured in the left y-axis. Lines show the Mean5WorstVariance and are measured in the right y-axis. In figure 6(a), we can see that the linear relation provides the best success rate. We also observe that when the p/r function is more aggressive, the success rate decreases. This is intuitively clear, since we reduce the amount of resources given to the CT. All functions, except the function f(p) = p1/0.4, achieve a good success rate and Mean5WorstVariance. As we move from high to low utilization scenarios, the success rate improves. On average, the success rate is 0.9875, 0.979, and 0.671 for the linear, f(p) = p1/0.7, and f(p) = p1/0.4functions, respectively. For the adhoc function the success rate is 0.975. The Mean5WorstVariance is 1%, 2.6%, and 87% and 2.4%, respectively. Figure 6(b) shows the average IPC of the NCT, averaged over all experiments. We see that the function f(p) = p1/0.4achieves the best performance results. However, this is at the cost of success rate. Hence, we conclude that this function is too aggressive. From the other p/r functions, we observe that as we increase the 23 DAC, UPC. Technical Report. May 2005. Cazorla et al. 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 high medium low Success Rate 0 20 40 60 80 100 120 140 160 180 200 variation respect to deadline (%) linear (power 1) power 0.7 power 0.4 adhoc Mean5WorseVariance 0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8 2.0 high medium low NCT Performance linear power 0.7 power0.4 adhoc (a) success rate and Mean5WorstVariance (b) Throughput Figure 6: Success rate and throughput for different p/r functions aggressiveness of the p/r function, we obtain more performance for the NCT. This is because more aggressive p/r functions provide the CT with fewer resources. We conclude that the adhoc performance/resource function performs best. If this function is too difficult to obtain in some circumstances, the p/r function f(p) = p1/0.7 performs only slightly worse. Recall that a p/r function is computed by the OS level job scheduler and hence is implemented in software. Hence we can easily use complex functions like the functions discussed above. 6.2 Dynamic method In this section, we present the results of the dynamic method and moreover compare this mechanism with previous approaches. For this experiment, we have also considered the Predictable Performance mechanism used in [5] and a prioritization-aware fetch policy [2][9] which we call fetch control in this section. This mechanism always prioritizes the CT when fetching instructions. We also compare our results with the adhoc p/r function for the static method. Figure 7(a) shows the success rate for the different approaches. If we just control fetch, we see that we obtain a low success rate and a high Mean5Variation, even for the low utilization scenario. The predictable performance approach obtains a success rate of 1, and hence a Mean5WorstVariation of 0. This is mainly due to the fact that this policy requires knowledge of the IP Calone of each CT that allows it to compute dynamically how far the current IPC of the CT is from the target IPC. In this way, this mechanism can converge to the target IPC. Our mechanism does not require 24 DAC, UPC. Technical Report. May 2005. Cazorla et al. 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 high medium low Success Rate 0 50 100 150 200 250 300 350 variation respect to deadline (%) Fetch control Resource Allocator (static) Resource Allocator (dynamic) Predictable Performance Mean5WorseVariance 0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8 2.0 high medium low NCT IPC Fetch control Resource Allocator (static) Resource Allocator (dynamic) Predictable Performance (a) success rate and Mean5WorstVariance (b) Throughput Figure 7: Success Rate and throughput of our approach and previous approaches this information but achieves a success rate of 0.9875 nevertheless. It also has a low Mean5WorstVariance of 1.63%. In the static method using the adhoc p/r function, the success rate is 0.975 and the Mean5WorstVariance is 2.4%. Regarding throughput, we can see that our dynamic method achieves the same performance as Predictable Performance. Our static method achieves 9% less performance, but still much more performance than the fetch control method, up to 56% more in the low utilization scenario. 6.3 Discussion In this section, we briefly summarize the results presented above and discuss some other issues, namely, the cost and the applicability of the mechanisms discussed above. Concerning the cost of the different mechanisms, the fetch control mechanism proposed in [3][9] only prioritizes the fetch of the critical thread and hence has lowest cost. Our static mechanism needs to keep track of how many resources are used by each thread and hence is more expensive. However, the cost for doing this is not high as we show in section 7. Since the required percentage that the critical thread should receive is provided by the job scheduler, the base resource allocator is enough to implement our static method. Our dynamic method is more complex. Apart from the resource allocator that is required to monitor that threads do not exceed their share of the resources, a mechanism in hardware is required to sample the IP Calone of the critical thread during the sample phase and to periodically determine the 25