Samarjit Chakraborty
email: samarjit@comp.nus.edu.sg

Lothar Thiele
email: thiele@tik.ee.ethz.ch

A New Task Model for Streaming Applications and its Schedulability Analysis

In this paper we introduce a new task model that is specifically targeted towards representing stream processing applications. Examples of such applications are those involved in network packet processing (such as a software-based router) and multimedia processing (such as an MPEG decoder application). Our task model is made up of two parts: (i) a new task structure to accurately model the software structures of stream processing applications such as conditional branches and different end-to-end deadlines for different types of input data items, and (ii) a new event model to represent the arrival pattern of the data items to be processed, which triggers the task structure. This event model is more expressive than classical models such as purely periodic, periodic with jitter or sporadic event models. We then present algorithms for the schedulability analysis of this task model. The basic scheme underlying our algorithms is a generalization of the techniques used for the schedulability analysis of the recently proposed generalized multiframe and the recurring real-time task models.

Introduction

Of late, there has been a lot of interest in the design of hardware and software architectures of embedded systems specifically targeted towards running stream processing applications. Such systems range from hand-held computers, portable audio/video players and mobile phones, to network processors used for implementing complex packet processing tasks in a high-speed router. Many of these devices have very stringent constraints pertaining to cost, size and power consumption, and have posed several challenges towards developing appropriate models, methodologies, languages and tools for designing them (for example, see [START_REF] Maxiaguine | Rate analysis for streaming applications with on-chip buffer constraints[END_REF][START_REF] Thies | StreamIt: A language for streaming applications[END_REF]).

A natural representation of the software structure of a stream processing application is a directed acyclic graph whose nodes represent different processing tasks and the edges represent precedence constraints among these tasks. An example of such a graph, representing a simple network packet processing application is shown in Figure 1. This graph represents the processing of two different classes of packets: VoIP packets, which have real-time constraints on their processing time, and all other packet types, which do not have real-time constraints on their processing time. The processing of any VoIP packet follows the right hand side path in this task graph, and the processing of all other packet types follows the left hand side path in this graph. The arrival of any packet causes an interrupt, which is processed by the receive packet task. This is followed by packet header parsing and classification, after which the packet type is known and based on this type either the right or the left hand side of the task graph is executed. Let us assume that all the tasks in this task graph are executed on the same processor. Since the packet type is not known before the first two tasks are completed, there is a deadline (d 1 in the figure) within which the first two tasks are to be executed after the arrival of any packet. d 1 would usually be determined by the line speed or the minimum interarrival time between two packets. VoIP packets have an additional end-to-end deadline, say d 2 (not shown in the figure), within which all the relevant tasks in the task graph (starting from receive packet to route lookup) have to be completed from the arrival time of the packet. d 2 is determined independently from d 1 , and depends only on the QoS requirements of the application which is fed by the VoIP packets processed by this task graph.

The arrival process of packets which triggers this task graph is usually bursty in nature and can not be accurately captured by event models (such as periodic or sporadic) traditionally studied in the real-time systems literature. Such an arrival process is usually characterized by bounds on the burstiness over different time scales and by long-term arrival rates. In the communication networks domain, such a characterization is done using the theory of Network Calculus [START_REF] Cruz | A calculus for network delay, Parts 1 & 2[END_REF][START_REF] Boudec | Network Calculus -A Theory of Deterministic Queuing Systems for the Internet[END_REF], and we formally define this in Section 2.

Typically, a router will have several network interfaces and each such interface will be associated with a different packet arrival rate. Corresponding to each interface there will be a task graph such as the one shown in Figure 1, which will be triggered by a potentially infinite sequence of packets coming in through this interface. The structure of such a task graph and the different tasks in it might vary from one interface to the other. In the case of a software-based router, all the tasks belonging to such task graphs might be executed on a single processor and it is relevant to ask if all the associated deadlines can be met, given some bounds on the arrival process of packets at each of the interfaces.

Our results and relation to previous work:

To the best of our knowledge, none of the task models studied in the real-time systems literature naturally model the setup described above. Most of well known task models either do not model conditional branches, and those that model conditional branches (such as the recently proposed recurring real-time task model [START_REF] Baruah | Dynamic-and static-priority scheduling of recurring real-time tasks[END_REF]) associate deadlines with the individual nodes of the task graphs. Note that the setup described above requires deadlines to be associated with different paths in a task graph, all of which start from the source node. However, a path can not be "collapsed" into a node, because there might be deadlines associated with subpaths and multiple paths might overlap. Additionally, the event model which triggers our task graphs, has not be studied in the real-time systems literature from the standpoint of schedulability analysis. In fact, the main complication of the schedulability analysis problem that we solve in this paper stems from this event model.

We present algorithms for both static and dynamic priority schedulability analysis. Our basic technique is a generalization of the schedulability analysis developed for the generalized multiframe [START_REF] Baruah | Generalized multiframe tasks[END_REF] and the recently proposed recurring real-time task model [START_REF] Baruah | Dynamic-and static-priority scheduling of recurring real-time tasks[END_REF], and is based on the concept of demand bound and resource bound functions. One of the main contributions of this paper is a method for computing these functions when the task graphs are triggered by our new event model described in the next section. In [START_REF] Baruah | Generalized multiframe tasks[END_REF] and [START_REF] Baruah | Dynamic-and static-priority scheduling of recurring real-time tasks[END_REF] these functions were computed for the case where the task graphs are triggered by a sporadic event model.

In the next section we formally define our task model and also describe the concepts of demand bound and resource

v 1 v 2 v 3 v 4 v 5 g 1 v 0 (6, (3, (15, (14, (9,12) (3,
g 1 ∈ G is shown in detail. Each node v i of g 1 is associated with a tuple (c(v i ), d(v i ))
, where c(v i ) is the node's worst case resource demand and d(v i ) is its relative deadline.

bound functions. This is followed by our algorithms for schedulability analysis in Section 3. Finally, in Section 4 we outline some directions for future work.

Stream Based Task Model

In this section we formally define the task model we motivated above. For the purpose of schedulability analysis, we consider a set of task graphs G, each of which are triggered independently of each other by data or event streams (where the arrival of a data item may be considered as an event). The goal of the schedulability analysis is to ascertain if for all graphs g ∈ G, all the associated deadlines are met for all possible legal triggering sequences. In this paper we are only concerned with schedulability analysis under preemption. An example task set is shown in Figure 2.

Definition 2.1 (Task Graph) An acyclic, directed task graph g = (V, A) consists of nodes v ∈ V and edges a = (v, w) ∈ A. A node represents a task of the application, an edge represents a precedence relation. There is a unique source node v 0 ∈ V having no incoming edges. To each node v there are associated the quantities c(v) ∈ R ≥0 and d(v) ∈ R >0 ∪ {∞} which denote the worst case resource demand and the deadline of the task associated to v respectively.

The interpretation of the precedence relations and deadlines is defined by the dynamic model associated with a task graph. A task graph is instantiated by a timed event, e.g. at time t 0 (which can be the arrival of a packet in the example described in the previous section). The release time of the source task v 0 is t 0 . The execution follows a path (sequence of nodes)

(v 0 , v 1 , ••• , v n-1
) through g where the nodes are connected by edges (v i , v i+1 ) ∈ A. The release time of a task v i+1 is the finishing time of task v i . Each task v requires a maximal resource demand of c(v), given in terms of the number of required processor cycles, the worst case execution time or any other reasonable unit that describes the service of the resource (i.e. the processor on which all the tasks are executed). In addition, each task has a relative deadline d(v) with respect to the instantiation time t 0 of g. Therefore, its finishing time must be equal or smaller than t 0 + d(v). All events in an event stream need not be processed in the same way. Depending on the type of an event or its associated data, different paths through the task graph may be chosen (see Figure 1). In addition, the processing of each event type might be associated with a different deadline constraint. If the deadline associated with a node is ∞ (see Figure 2), it implies that there are no deadline constraints on the path starting from the source node to this node, although there might be deadlines associated with subpaths of this path.

As we are concerned with the processing of event streams, a task graph can be instantiated by successive timed events. We suppose that even a concurrent instantiation is possible, i.e. there can be a new timed event before the last task of the previous instance is completely executed. The timing of any event stream triggering a task graph is bounded by an arrival function defined as follows.

Definition 2.2 (Arrival Function)

The arrival function α(∆) ∈ R ≥0 , ∆ ∈ R provides an upper bound on the number of events that can arrive within any time interval of length ∆. In particular, there are at most α(∆) events within the time interval [t,t + ∆) for all t ≥ 0 and α(∆) = 0, ∀∆ ≤ 0.

In practice, α(∆) will be defined only for a finite number of values of ∆, and not for all ∆ ≥ 0. An example of such a specification is: there can not be more than 20 events within any time interval of duration 2 and no more than 25 events within any time interval of duration 5 time units. We denote such a specification using an arrival sequence.

Definition 2.3 (Arrival Sequence) An arrival sequence is given as

: α = α 1 , ∆ 1 , α 2 , ∆ 2 , ••• , α n , ∆ n (1)
It is called proper, if in addition δ i < δ i+1 and α i < α i+1 for all 1 ≤ i ≤ n -1 hold. An arrival function α corresponding to an arrival sequence α can be determined by the operator F α(∆) defined as follows

F α(∆) = min {α i |∆ i ≥ ∆} ∀ 0 < ∆ ≤ ∆ n (2) and F α(∆) = 0, ∀∆ ≤ 0 and F α(∆) = ∞, ∀∆ > ∆ n .
Given an arrival sequence, we can extend and tighten it using the sub-additivity property of arrival functions, i.e. α(s + t) ≤ α(s) + α(t). To this end, we at first add linear combinations of tuples to the sequence, i.e. tuples of the form a, d where a = ∑ n i=1 α i x i and d = ∑ n i=1 ∆ i x i for all x i ∈ Z ≥0 . Finally, we remove redundant tuples, i.e. we remove a tuple a, d , if there exists another tuple α i , ∆ i with ∆ i ≥ d and α i ≤ a.

In the example arrival sequence mentioned above, we at first have the following sequence: In case of several task graphs, we assume that each one g k ∈ G is triggered by its own event stream characterized by the corresponding arrival function α k (∆). For example, if the task graph g 1 in Figure 2 is triggered by an event stream characterized by one of the arrival functions in Figure 3, then the additional task graphs (g 2 , g 3 , ...) in the task set will be triggered by other streams which are characterized by other arrival functions. As mentioned in the previous section, the different event streams and task graphs are independent of each other; they only share the common resource.

For our schedulability analysis, we use the concept of demand and resource bound functions, similar to the ones introduced by Baruah in [START_REF] Baruah | Dynamic-and static-priority scheduling of recurring real-time tasks[END_REF]. The demand bound function of a task graph describes the minimal amount of resource necessary within any time interval, to satisfy its realtime constraints in the case of a single instantiation of the graph. We later introduce the concept of a composite demand bound function, which takes into account the triggering of the graph by a stream of events.

Definition 2.4 (Demand Bound Function (DBF))

The demand bound function dbf (∆) ∈ R ≥0 with ∆ ∈ R ≥0 of a task graph g ∈ G denotes the minimal amount of resource necessary within any time interval of length ∆ such that all its associated deadlines can be satisfied when the task graph is instantiated by a single event. The composite demand bound function (CDBF) dbf C (∆) extends the above definition to the case where the task graph is triggered by a sequence of events whose arrival process is bounded by an arrival function.

For example, the deadline 6 associated with the node v 2 of the task graph shown in Figure 2 implies that within any time interval of length 6 there must be at least c(v 0 ) + c(v 1 ) + c(v 2 ) = 24 resource units available. Otherwise, the relative deadline of v 2 can not be guaranteed. In a similar way, all other deadlines impose additional constraints. However, if the task graph is triggered not once, but by a stream of events, then the resource demand is characterized by a composite demand bound function which we formally define in Section 3.2.

Similarly, the resource bound function denotes the maximal load that a task graph can possibly impose on the resource within any time interval of a specified length.

Definition 2.5 (Resource Bound Function (RBF)) The resource bound function rbf

(∆) ∈ R ≥0 with ∆ ∈ R ≥0 of

a task graph g ∈ G denotes the maximal amount of resource load within any time interval of length ∆ that can be imposed by a singly instantiated task graph. The composite remand bound function (CRBF) rbf C (∆) extends the above definition to the case where the task graph is triggered by a sequence of events whose arrival process is bounded by an arrival function.

The use of the above functions in our schedulability analysis problem is shown in Section 3.3.

Schedulability Analysis

Demand and Resource Bound Functions

We will describe the demand and resource bound functions in the form of (proper) sequences similar to the one defined in Def. 2.3, i.e. dbf = dbf 1 , δ 1 , dbf 2 , δ 2 , ... and rbf = rbf 1 , δ 1 , rbf 2 , δ 2 , ... . The values of these functions can be determined using the operator G dbf (∆) defined as follows (the same definition holds for the resource bound sequence also):

G dbf (∆) = max {dbf i | δ i ≤ ∆} ∀ ∆ ≥ δ 1
and G dbf (∆) = 0 for all 0 ≤ ∆ < δ 1 . Now, we can determine a demand bound function of a given task graph g. To this end, let us define C(v i ) as the length of the longest path from the source v 0 of g to v i using the worst case resource demand c(v) of the node v:

C(v i ) = max{ ∑ v j ∈P i c(v j ) | for all paths P i }
where P i denotes a path from source node v 0 to node v i . Using Def. 2.4, we understand that each node of the task graph g defines a new constraint for the demand bound sequence. Therefore, we at first construct a sequence that contains a tuple for each node v i of the task graph g, each tuple containing as its elements the length of the longest source path C(v i ) and the deadline d(v i ): In order to get a proper demand bound sequence dbf , we must sort these tuples according to the deadlines d(v i ) and remove all tuples that correspond to redundant constraints.

C(v 0 ), d(v 0 ) , C(v 1 ), d(v 2 ) , ... ( 3
)
In particular, we remove a tuple c, d , if there exists another tuple c i , d i with d i ≤ d and c i ≥ c.

In a similar way, we can conclude that the resource bound sequence is simply given by

rbf = C max , 0 (4)
where C max denotes the longest source path in the task graph g, i.e.

C max = max{C(v i )|v i ∈ V }.
Using the task graph g 1 shown in Figure 2, we first obtain the sequence (3), which is equal to 24, 6 , 23, 10 , 36, 12 .

Here each tuple corresponds to one node with a finite relative deadline, i.e. nodes v 2 , v 3 and v 5 . As the second tuple corresponds to a redundant constraint, we obtain dbf = 24, 6 , 36, 12 . The resource bound function is constant, i.e. rbf (∆) = 36, ∀∆ > 0. The demand bound function corresponding to the task graph g 1 in Figure 2 is shown in Figure 4. Now, it remains to determine the composite demand and resource bound functions by taking into account the instantiation of a task graph by an event stream that is bounded by an arrival function α(∆) or an arrival sequence α.

Composite Demand and Resource Bound Functions

The computation of the composite demand bound function of a task graph is given by the following theorem.

Theorem 3.1 (Composite Demand Bound Function)

Given a demand bound sequence dbf = dbf 1 , δ 1 , dbf 2 , δ 2 , ..

. and an arrival function as defined in Def. 2.2. Then the composite demand bound function according to Def. 2.4 is given by dbf

C (∆) = m ∑ i=1 (dbf i -dbf i-1 ) • α(∆ -δ i )
where dbf 0 = 0. Proof: The proof uses induction on the number of tuples in the demand bound sequence. Let us first suppose that dbf = dbf 1 , δ 1 . Then for one triggering event, the demand is 0 for all 0 ≤ ∆ < δ 1 and it is dbf 1 for all δ 1 ≤ ∆. Now, there are at most α(∆) events in any interval of size ∆. Each event triggers the graph g and generates a demand according to the demand bound sequence dbf . Further note, that the demand of independent tasks is additive. Using this, one can conclude that the composite demand in an interval of ∆+δ 1 is at most

dbf 1 •α(∆), i.e α D (∆+δ 1 ) = dbf 1 •α(∆).
As a result, we obtain that dbf C (∆) = 0 for ∆ < δ 1 and dbf C (∆) = dbf 1 • α(∆ -δ 1 ) for ∆ ≥ δ 1 . Using Eq. ( 2), we obtain the relation given in the theorem. Now, we will use induction on the number of tuples in the DBF sequence. Let us suppose that Theorem 3.1 holds for m elements of the sequence

dbf m = dbf 1 , δ 1 , ••• , dbf m , δ m , i.e. dbf C m (∆) = ∑ m i=1 (dbf i - dbf i-1 ) • α(∆ -δ i ).
From the transformation between a sequence and the corresponding function in Eq. ( 2) we know that dbf m+1 (∆)dbf m (∆) = 0 for ∆ < δ m+1 and dbf m+1 (∆)dbf m (∆) = dbf m+1dbf m if ∆ ≥ δ m+1 . Taking into account again the additivity of demands, we can conclude the following. The difference in demand between m and m + 1 sequence elements is given by the demand bound function that is defined by the sequence dbf m+1dbf m , δ m+1 . Following the arguments in the first paragraph of the proof, this leads to an additional composite demand of (dbf m+1dbf m )•α(∆-δ m+1 ) if the task graph g is triggered by an event stream bounded by α(∆). Therefore,

dbf C m+1 (∆) = dbf C m (∆) + (dbf m+1 -dbf m ) • α(∆ -δ m+1 ) = ∑ m+1 i=1 (dbf i -dbf i-1 ) • α(∆ -δ i ).
If the triggering event stream is described by an arrival sequence according to Def. 2.3, then we can construct a sequence representation of the composite demand bound function by including all tuples of the form

(dbf i -dbf i-1 )α j , ∆ j + δ i ∀ 1 ≤ i ≤ m, 1 ≤ j ≤ n
and then removing all redundant constraints, i.e. we remove a tuple c, d , if there exists another tuple c i , d i with d i ≤ d and c i ≥ c.

The composite resource bound function can be constructed in a similar way.

Theorem 3.2 (Composite Resource Bound Function)

Given a resource bound function rbf = rbf 1 , δ 1 , rbf 2 , δ 2 , ..

. and an arrival function in accordance with Def. 2.2. Then the composite resource bound function according to Def. 2.5 is given by rbf

C (∆) = m ∑ i=1 (rbf i -rbf i-1 ) • α(∆ -δ i )
where rbf 0 = 0. Using Eq. ( 4), the composite resource bound function can be determined as rbf C 4, Figure 5 shows the resulting composite resource and demand bound functions.

(∆) = C max • α(∆), or rbf C = C max α 1 , ∆ 1 , ..., C max α m , ∆ m

Conditions for Schedulability

In order to perform a schedulability analysis for our task, we make use of known results based on the resource and demand bound functions for static and dynamic priority schedulability analysis (see [START_REF] Baruah | Dynamic-and static-priority scheduling of recurring real-time tasks[END_REF] for details). We can use these results because of our task independence assumptions.

Let us suppose that the task graphs g k ∈ G for 1 ≤ k ≤ N are ordered according to the priority of their tasks, i.e. all nodes of g k have a higher priority than those of g k+1 . Moreover, we assume that the resource (or the processor) delivers at least β(∆) resource units within any time interval of length ∆. For example, if the resource demand is directly given in terms of time, then we have β(∆) = ∆ for an unloaded processor. We then have the following result:

A set of task graphs g ∈ G is schedulable under a fixed priority scheme, if and only if

dbf C k (∆) ≤ sup 0≤λ≤∆ β(λ) - k-1 ∑ j=1 rbf C j (λ) (5)
holds for all graphs g k and for all ∆ > 0. Intuitively, the right hand side represents the remaining resource capability after the maximum resource load due to all higher priority tasks has been taken into account. The left hand side represents the composite demand by the tasks of graph g k . Using this test, one can also determine a feasible priority assignment efficiently (again, see [START_REF] Baruah | Dynamic-and static-priority scheduling of recurring real-time tasks[END_REF] for details).

In a similar way, we can perform a schedulability analysis for preemptive dynamic priority scheduling. In this case, a set of task graphs g k ∈ G is schedulable if and only if

N ∑ k=1 dbf C k (∆) ≤ β(∆) (6)
holds for all ∆ ≥ 0. The right hand side represents the accumulated resource demand of all tasks graphs g k and the left hand side denotes the available resource capacity. In the particular case where the task graphs are scheduled using an EDF scheduling policy, the relative deadlines associated with the nodes of a graph might have to be adjusted (since some of them might be equal to ∞) in a way such that they are still compatible with the demand bound function. The new relative deadline of a node v i can be assigned as the minimum of its specified deadline d(v i ) and deadlines of all its direct and indirect successors in the task graph. In the case of the graph g 1 shown in Figure 2, the new deadlines are

d(v 0 ) = 6, d(v 1 ) = 6, d(v 2 ) = 9, d(v 3 ) = 10, d(v 4 ) = 12 and d(v 5 ) = 12.
The nodes of this graph can now be scheduled with these deadlines. Just for the purpose of illustration, let us assume that there is only one input stream with a composite demand bound function as depicted in Figure 4. Figure 6 represents a schedulability test for EDF according to Eq. ( 6), with the assumption that the computing resource can deliver 195 resource units per time unit, i.e. β(∆) = 195 • ∆. As it turns out, the stream is just schedulable.

The schedulability tests given above can also be applied to sequence representations of the composite demand and resource bound functions. But the way they have been formulated so far, the relations in Eqs. ( 5) and ( 6) need to be checked for all ∆ ≥ 0, at least in principle. Even if we restrict ourselves to ∆ ∈ Z ≥0 , this is virtually infeasible. Therefore, we are interested in a maximal value ∆ max with the following property. If the inequalities hold for all 0 ≤ ∆ ≤ ∆ max then they hold for all ∆ ≥ 0. In what follows, we derive such a bound for dynamic priority schedulability analysis. The derivation for the fixed priority case is similar.

We bound all the arrival functions α k (associated with the graph g k ∈ G) by a linear function: α k (∆) ≤ s α k +t α k •∆ for all ∆ ≥ 0. In a similar way, we can bound β(∆) using β(∆) ≥ s β + t β • ∆. Now, we know from Eq. (3) that the demand bound functions can be bounded by dbf k = C max k , d min k where C max k denotes the maximal accumulated weight of any path in the task graph g k using weights c(v j ) and d min k denotes the smallest deadline in the task graph g k . Therefore, we can derive the bound

N ∑ k=1 dbf C k (∆) ≤ N ∑ k=1 C max k (s α k -d min k t α k ) + ( N ∑ k=1 C max k t α k )∆
From Eq. ( 6), we can conclude that the above expression needs to be equal to s β + t β • ∆ max , and therefore

∆ max = (∑ N k=1 C max k (s α k -d min k t α k ) -s β t β -(∑ N k=1 C max k t α k )
In our running example, we have s α = 46, t α = 5 (see Figure 3) and s β = 0, t β = 195 (see Figure 6). From the task graph in Figure 2, we conclude that C max = 36 and d min = 6. Therefore, we obtain ∆ max = 36(46 -30)/(195 -36 * 5) = 38.4, i.e. we would need to check the inequality given by Eq. ( 6) for all 0 ≤ ∆ ≤ 38.4. The same holds, if the bound functions are represented in the form of sequences.

Concluding Remarks

In this paper we introduced a new task model that naturally captures some of the essential properties of stream processing applications. For this class of applications, we believe that our model is more pragmatic compared to the task models recently studied in the real-time systems literature (such as [START_REF] Baruah | Dynamic-and static-priority scheduling of recurring real-time tasks[END_REF]), although they can also model program structures like conditional branches. We did not present a formal complexity analysis of our scheduling algorithms. In all realistic setups, there will only be a small number of deadline constraints associated with any task graph (although the graph might have exponential number of paths from its source to its sink node). Bounds on typical event streams will also be specified using a small number of tuples (such as a burst and a long-term rate). In such cases, our schedulability analysis will certainly have a reasonably low computational cost. It should be noted that even in such cases, it might not be possible to ascertain schedulability by avoiding the test we presented, and instead using some straightforward calculation. In future, we plan to extend this model to incorporate variable task execution times (packet payload processing) and timeouts.

Figure 1 :

 1 Figure 1: Task graph for a network packet processing application, which processes two different packet types.

Figure 2 :

 2 Figure 2: Only one sample task graphg 1 ∈ G is shown in detail. Each node v i of g 1 is associated with a tuple (c(v i ), d(v i )), where c(v i ) is the node's worst case resource demand and d(v i ) is its relative deadline.

Figure 3 :

 3 Figure 3: Two possible representations of an event stream associated with a task graph. The right hand side shows a continuous arrival function defined using piecewise linear segments, with three pieces starting at ∆ = 0, 1 and 3 with slopes 30, 15 and 5 respectively. The left hand side depicts F α(∆) corresponding to the sequence α = 20, 2 , 25, 5 after its sub-additive extension. 20, 2 , 25, 5 .This sequence can be extended to 20, 2 , 40, 4 , 25, 5 , 60, 6 , 45, 7 , 80, 8 , 65, 9 ,.. . After removing all the redundant tuples, we get 20, 2 , 25, 5 , 45, 7 , 50, 10 , 70, 12 , 75, 15 ,.. . Following this concept, two possible representations of example event streams (one discrete and the other continuous) are depicted in Figure3.In case of several task graphs, we assume that each one g k ∈ G is triggered by its own event stream characterized by the corresponding arrival function α k (∆). For example, if the task graph g 1 in Figure2is triggered by an event stream characterized by one of the arrival functions in Figure3, then the additional task graphs (g 2 , g 3 , ...) in the task set will be triggered by other streams which are characterized by other arrival functions. As mentioned in the previous section, the different event streams and task graphs are independent of each other; they only share the common resource.For our schedulability analysis, we use the concept of demand and resource bound functions, similar to the ones introduced by Baruah in[START_REF] Baruah | Dynamic-and static-priority scheduling of recurring real-time tasks[END_REF]. The demand bound function of a task graph describes the minimal amount of resource necessary within any time interval, to satisfy its realtime constraints in the case of a single instantiation of the graph. We later introduce the concept of a composite demand bound function, which takes into account the triggering of the graph by a stream of events.

Figure 4 :

 4 Figure 4: Demand bound function corresponding to the task graph in Figure 2

Figure 5 :

 5 Figure 5: Composite resource and demand bound functions corresponding to the task graph g 1 in Figure 2 and the arrival function shown at the right hand side of Figure 3. in case of an arrival sequence in accordance with Def. 2.3. As an example, let us suppose that the task graph g 1 in Figure 2 is triggered by an event stream characterized by the continuous arrival function shown at the right hand side of Figure 3. Based on the demand bound function in Figure4, Figure5shows the resulting composite resource and demand bound functions.

Figure 6 :

 6 Figure 6: EDF schedulability test for the composite demand bound function given in Figure 4 and β(∆) = 195 • ∆.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)


Mirko Loghi
email: loghi@sci.univr.itmassimo.poncino@polito.it

Massimo Poncino

Exploring Energy/Performance Tradeoffs in Shared Memory MPSoCs: Snoop-Based Cache Coherence vs. Software Solutions

Shared memory is a common interprocessor communication paradigm for single-chip multi-processor platforms. Snoop-based cache coherence is a very successful technique that provides a clean shared-memory programming abstraction in general-purpose chip multi-processors, but there is no consensus on its usage in resource-constrained multiprocessor systems on chips (MPSoCs) for embedded applications.

This work aims at providing a comparative energy and performance analysis of cache coherence support schemes in MPSoCs. Thanks to the use of a complete multiprocessor simulation platform, which relies on accurate technology-homogeneous power models, we were able to explore different cache-coherent shared-memory communication schemes for a number of cache configurations and workloads.

Introduction

The rapid advances of silicon technology have made it possible to build small-to medium-scale single-chip multiprocessors. These devices can be coarsely distinguished in two classes: general purpose chip multiprocessors [START_REF]Broadening the Reach of the Intel Itanium 2 Processor Family[END_REF][START_REF] Tremblay | The MAJC Architecture: A Synthesis of Parallelism and Scalability[END_REF][START_REF] Tendler | POWER4 System Microarchitecture[END_REF] (GPCMs) which integrate a small number of advanced processor cores (e.g. Itanium 2, UltraSPARC) and large caches in a tightly connected cluster, and Multi-Processor Systemson-Chip (MPSoC) [START_REF] Cumming | The TI OMAP Platform Approach to SoC[END_REF][START_REF] Richardson | MPOC: A Chip Multiprocessor for Embedded Systems[END_REF][START_REF] Ackland | A Single Chip, 1.6 Billion, 16-b MAC/s Multiprocessor DSP[END_REF][START_REF] Semiconductor | Philips Nexperia Platform[END_REF][START_REF] Grammatikakis | Software for Multiprocessor Networks-on-Chip[END_REF], which contain simpler cores and many application-specific heterogeneous coprocessors, embedded memories and peripherals. These two classes have completely different application targets and design constraints. GPCMs target the high-end server market and are also often used as building blocks for large scale supercomputers. In contrast, MPSoC are targeted for embedded applications (multimedia, video, graphics) in tightly cost-and power-constrained markets (e.g., smart phones, home entertainment centers, etc.). The focus of this paper is the study of power-performance tradeoffs in supporting shared memory programming models in MPSoCs. Needless to say, power consumption is also a concern in GPCMs. In the case of GPCMs, however, fully hardware supported cache coherence is an undisputed requirement, because it makes much easier to support gen-eral purpose application workloads. Recent papers by Ekman et al. [START_REF] Ekman | Evaluation of Snoop-Energy Reduction Techniques for Chip-Multiprocessors[END_REF][START_REF] Ekman | TLB and Snoop Energy-Reduction Using Virtual Caches in Low-Power Chip-Multiprocessors[END_REF] have studied the power consumption of snoop-based cache coherence using a full-system simulation approach targeted to GCMPs. The picture is much less clear in MPSoCs; although some MPSoCs explicitly support cache coherence in HW (e.g., [START_REF] Ackland | A Single Chip, 1.6 Billion, 16-b MAC/s Multiprocessor DSP[END_REF]), other devices on the market rely on non-cachecoherent architectures (e.g., [START_REF] Cumming | The TI OMAP Platform Approach to SoC[END_REF]). This is motivated by the fact that embedded applications are usually carefully tuned to the target hardware platform, and interprocessor communication is often performed by explicitly managing shared memory areas, without much hardware support for a full shared-memory abstraction. Clearly, the ease of programming in a fully cache coherent memory space could simplify embedded application development, but designers would reluctantly accept this approach if this should affect the energy efficiency of the architecture. Our work sheds some light on this open issue. We set up a complete and accurate environment for exploring the energy efficiency of cache coherence in a MPSoC context, using cycle-accurate simulation and power models which are technology-homogeneous (i.e., all obtained from characterization in the same .13µm technology). We compared three alternative approaches to cache-coherence: in the first one (hardware-based), cache coherence is imposed by a specific device implementing a snoopy protocol; in the second one (software-based), coherence is enforced by preventing the caching of shared data. In the third scheme (OS-based), the burden of coherence is left to the operating systems IPC primitives (based on message passing). Our analysis allows us to derive some interesting and nontrivial conclusions. First, results show that an OS-based coherence solution is extremely inefficient both power-and performance-wise (up to 7x), independently of the benchmark and of the cache configuration. Second, we show that cache coherence is not always convenient in terms of either performance and energy; this strongly depends on hardware features such as cache size, as well as on the characteristics of the application such as the access patterns for shared variables. The latter in particular, allows to define some high-level guidelines for writing embedded software for cache-coherent MPSoCs.

Background and Previous Work

The problem of cache coherence has been thoroughly studied by researchers, and a vast literature on the subject is available. Widely speaking, approaches for solving the cache coherence problem in multiprocessor systems fall into two major classes: hardware-based approaches, and software-based ones. The former impose cache coherence by adding suitable hardware which guarantees coherence of cached data, whereas the latter impose coherence by limiting the caching of some shared data to when it is safe to do it; this can be done by the programmer, the compiler, or the operating system. For a survey of hardwarebased cache coherence solutions the reader is referred to [START_REF] Stenström | A Survey of Cache Coherence Schemes for Multiprocessors[END_REF][START_REF] Tomasevic | Hardware Approaches to Cache Coherence in Shared-Memory Multiprocessors[END_REF][START_REF] Culler | Parallel Computer Architecture: A Hardware/Software Approach[END_REF]; software-based cache coherence solutions are reviewed in [START_REF] Tartalja | Classifying Software-Based Cache Coherence Solutions[END_REF]. Hardware-based cache coherence solutions (called cache coherence protocols hereafter) can be further classified according to two orthogonal dimensions [START_REF] Stenström | A Survey of Cache Coherence Schemes for Multiprocessors[END_REF]:

1. The type of interconnect of the multiprocessor architecture. When processors are connected through a shared medium (such as a bus), protocols can use broadcasting to enforce coherence. These protocols are called snoopy protocols. These schemes apply to small-scale bus-based multiprocessors, due to the limited scalability of buses. In absence of a shared medium as interconnect (e.g., if a crossbar connection is used) snoopy protocols are replaced by directorybased protocols (which are outside the scope of this paper). 2. The type of cache coherence policy. There are essentially two options: a write-invalidate and a writeupdate policy. In the former scheme, whenever any cache line L is written the coherence protocol invalidates all copies of L in other caches; in the latter one, the protocol updates those lines with the new value which is being written. Invalidation-based solutions are more common in coherence protocols because they are easier to implement in hardware; they are also more efficient than updatebased one for large cache line sizes, since updates requires multiple bus transfers. Update-based protocols become more efficient when accessing heavily contended lines, since subsequent accesses to those lines will result in a cache hit thanks to the update. Multiprocessor architectures (and hence cache coherence) have been historically designed with performance in mind. Therefore, the impact of coherence schemes on energy has not been considered until the tight energy constraints of single-chip multiprocessors made the problem relevant. Early work on this topic include the Jetty scheme [START_REF] Moshovos | JETTY: Filtering Snoops for Reduced Energy Consumption in SMP Servers[END_REF], where a small structure (Jetty) is attached to each cache so as to filter out useless snoop accesses. Instead of doing a tag-lookup directly, the Jetty is checked first; if no copies of data do exist, a cache access is avoided, thus achieving significant energy savings. Another approach is serial snooping [START_REF] Saldanha | Power Efficient Cache Coherence[END_REF], based on the assumption that if a miss occurs in one cache, it is possible to find the block in another cache without having to check all the other caches. Both schemes have been devised for multi-chip SMPs; they have been evaluated on GPCMs in [START_REF] Ekman | Evaluation of Snoop-Energy Reduction Techniques for Chip-Multiprocessors[END_REF], where it was shown that these solutions are quite ineffective. The same authors have also proposed an energy-efficient cache coherence scheme for virtual caches in GPCMs [START_REF] Ekman | TLB and Snoop Energy-Reduction Using Virtual Caches in Low-Power Chip-Multiprocessors[END_REF]. None of these approaches is explicitly meant for MPSoCs, for which much tighter energy and area constraints do exist. As a matter of fact, all these schemes require quite high computational and/or hardware overhead, and assume nonrealistic software architectures. For example, in [START_REF] Ekman | Evaluation of Snoop-Energy Reduction Techniques for Chip-Multiprocessors[END_REF][START_REF] Ekman | TLB and Snoop Energy-Reduction Using Virtual Caches in Low-Power Chip-Multiprocessors[END_REF] no operating system is assumed to be executing in the system. In this work, we propose the first energy/performance analysis in MPSoCs, that includes an embedded operating system. The result is a comparison of basic hardware-based coherence schemes, with minimal impact on the architecture, with respect to schemes imposed at the software level.

The Multiprocessor Platform

Figure 1 shows the architectural template of the multiprocessor simulation platform used in this work, called MPARM [START_REF] Loghi | Analyzing On-Chip Communication in a MPSoC Environment[END_REF]. It consists of (i) a configurable number of 32-bit ARM processors, (ii) their private memories, (iii) a shared memory, (iv) a hardware interrupt module, (v) a hardware semaphore module, and (vi) the interconnect.

¡ £ ¥ ¦ § ¦ ¨ ! " # $ % ¥ ¡ £ ¥ ¦ § ¦ ¨ ¡ £ ¥ ¦ § ¦ ¨ ¡ £ ¥ ¦ § ¦ ¨ % $ & ( % % ) 0 ! Figure 1. Hardware Architecture.
The processor cores are modeled by means of an adapted version of a GPL-licensed Instruction-Set-simulator (ISS) called SWARM [18], written in C++ and embedded into a SystemC wrapper. Each ISS contains his own cache. Memories and all other devices are implemented in SystemC in a straightforward fashion. The semaphore module and the interrupt device are used to handle the synchronization among the cores. The former provides a test-and-set operation to the software, while the latter allows a processor to send an interrupt request to another core. The platform is entirely described in SystemC at the signal level, except the ISS which performs cycle-accurate simulations of the cores. The platform is configurable, and it allows to specify several parameters, such as the type of interconnect (AMBA vs. ST-Bus), the number of processing elements, and the cache and memory parameters (cache size, line size, cache type, memory size and latency, etc.) A port of a real-time operative system called RTEMS [START_REF]RTEMS home page[END_REF] is available for the platform. RTEMS offers support for multiprocessing, and native calls for process communication and synchronization. Inter-process and inter-thread communication in RTEMS rely on message queues; threads communicate using the a send primitive to put data into the queue, and a receive primitive to retrieve data, both provided by RTEMS as system calls. Concerning power analysis, the platform provides accurate power models associated to each component. All models are cycle accurate, and have been characterized on a 0.13 µm technology by STMicroelectronics and validated on silicon implementations of the various components. For the processor cores we have used an instruction-based power model (see [START_REF] Benini | A power modeling and estimation framework for VLIW-based embedded systems[END_REF] for details). For the memories (both caches and private memories) we have used an analytical model derived from the work presented in [START_REF] Chinosi | Automatic Characterization and Modeling of Power Consumption in Static RAMs[END_REF], whereas the power model for the STbus interconnect has been taken from [START_REF] Bona | System-Level Power Modeling and Simulation of High-End Industrial Network-on-chip[END_REF].

Cache Coherence Support

The base MPARM architecture does not support cache coherence, in the sense that no hardware support is used to enforce it. We have enhanced the platform by adding a hardware coherence support based on a write-through policy, which comes into two variants: one based on an invalidate policy (Write-Through Invalidate, WTI), the other based on an update policy (Write-Through Update, WTU). The devices are quite similar: when a write request on the shared memory is coming from another processor (detected from the observation of the corresponding bus signals), The corresponding action is taken (invalidate or update). Notice that the update device is slightly more complex. It features extra I/O interface for the data, since in this case we are writing a value to the updated locations. The hardware snoop devices are in charge to enforce the cache coherence protocols. The snoop devices sample the bus signals to detect the transaction on the bus, its relevant data and the core involved. When a write operation is flagged, the corresponding action is performed, i.e., invalidation for the WTI policy, rewriting of the data for the WTU one. Write operations are performed in two steps. The first one is performed by the core, which asserts the signals on the bus, while the second one is performed by the target memory, which sends its acknowledge. The write ends when the second step is complete and when it is the right time, for the snoop device, to interact with the cache. Of course, the device must ignore writes issued by its core.

In our simulation model, synchronization between the core and the snoop device is handled using shared variables. During a clock cycle only one of them can access the cache memory; therefore the other one must be locked, waiting for the cache accessibility.

Energy Impact of Cache Coherence

To assess the energy/performance efficiency of cache coherence in MPSoCs, we compared three different schemes for enforcing cache coherence, each one corresponding to a different programming model, i.e., the way coherence is made available to the programmer. It is worth emphasizing that all the three models assume strict memory consistency [START_REF] Culler | Parallel Computer Architecture: A Hardware/Software Approach[END_REF]. The following sub-sections describe these three schemes. For each scheme, its corresponding programming model will be illustrated through a simple example, namely, a 1-item producer-consumer application.

Hardware-Based Coherence

Under this model, cache coherence is imposed by the snoop devices attached to the cores and their caches. This scheme implies a program semantics similar to that of an uniprocessor context; shared data can be cached because caches are guaranteed to be coherent. However, the programmer must explicitly deal with synchronization (e.g., for mutual exclusion) of shared data.

Figure 3 shows a typical textbook pseudocode for our working example. The use of the shared variable value is guaranteed to be coherent. However, the programmer must use a synchronization variable (a semaphore, in the example) to regulate access to the data.

void I P Q R S T U P V voidW X while (TRUE) Y `a b c d f g h c p q r s c q t u `a b c d g v c f x t u y S U P Q R S T U V W b a r d g v c f x t u b a r d b r r f q r s c q t u void T Q S U P V voidW Y while (TRUE) Y `a b c d b r r f q r s c q t u `a b c d g v c f x t u Q S U V y S U W b a r d g v c f x t u b a r d f g h c p q r s c q t u d e f g h int y S U d e f g h sem S j U k m o p q U R Q j r o U I j t Q j m

Software-Based Coherence

The second coherence scheme is straightforward: shared data are not cached. Although this solution may appear trivial, it is the basis of typical software-based schemes [START_REF] Tartalja | Classifying Software-Based Cache Coherence Solutions[END_REF].

More advanced schemes belonging to this class require compiler support to perform accurate analysis, which allows caching of some shared data when it is safe to do it.

In our example, the code differs only marginally from the one in Figure 3, namely, the shared keyword used on a variable automatically implies the fact that it cannot be cached.

OS-based Coherence

The third scheme consists of leaving to the OS do the task of guaranteeing coherence, through its IPC abstraction offered by its API. Specifically, RTEMS offers a communication infrastructure based on message queues [START_REF]RTEMS home page[END_REF], shared objects implemented as a pool of buffers called packets. In order to communicate with each other, remote processes obtain packet buffers using the the global identifier of the queue. Synchronized accesses to these buffers are realized by means of locks, which can be thought of as an equivalent of a hardware Test-and-Set primitive, implemented by polling a given location of the shared memory.

From the programming model point of view, not just coherence, but even the notion of shared data is hidden by the OS primitives. The producer-consumer example becomes then as shown in Figure 4, where send and receive denote the generic primitives for communication between remote processes. In the example, communication is established by explicitly specifying the peer process involved in the communication.

Experimental Results

Benchmark Description

In order to accurately compare the schemes described in the previous section, we have chosen a set of parallel programs, which exhibit different access patterns to the shared memory. The synchronization among processes relies on OS primitives, for the applications which use the OS, and on explicit manipulation of the hardware semaphore module for the others. In particular, the synchronization is always based on the test-and-set hardware feature. Addresses corresponding to semaphores are never cached, because it is not possible to perform a test-and-set access on a cache memory. The benchmarks are split into two sets. The first set includes two synthetic parametric benchmarks:

1. A producer-consumer application (PCx,y,z). The application is parameterized with respect to the number of producers x, consumers y, and the size of the FIFO queue z. All the producers write their data in a queue and all the consumers read from the same queue.

When the queue is full, the producers busy-stall polling the semaphore, while consumers busy-stall when the queue is empty. It is not relevant which consumer gets the data written by a producer, so the only synchronization point is related to the queue access. Each process performs a fixed number (N, set at 1000 in our experiments) of operations (reads or writes to the queue). 2. An application implementing the readers-writers problem (RWx,y,z,w). The meaning of x, y, and z is the same as for the PC application, while w denotes the relative speed of the readers with respect to the writers. The writers and the readers use the same shared object for data exchange. Here the aim of synchronization is to avoid multiple, simultaneous write accesses, while simultaneous reads must be allowed. Furthermore, no reads are allowed during a write, and each writer must to have exclusive access to the shared data. Unlike the previous case, multiple writes before one read and multiple reads before one write are possible Also in this case, each process (reader or writer) accesses the same number of times N the shared object.

Varying the relative speed of the processes will change the order of the memory accesses, but not their total number. The second set of benchmarks consists of a set of small kernels implementing well-defined functionalities:

1. A parallel matrix multiplication (MM). Each processor uses the entire source matrices and produces a slice of the result matrix. This program is written so as to maximize the sharing of the read-only variables (the source matrices) and to minimize the sharing of the variables that are written. 2. A parallel FFT.

A parallel LU matrix decomposition (LU).

The last two application are taken from the SPLASH-2 benchmark suite [START_REF] Singh | SPLASH: Stanford Parallel Applications for Shared-Memory[END_REF].

Analysis

We have compared the cache coherency schemes using power P , execution time T (in cycles), energy E = P T and the energy-delay product EDP = ET = P T 2 . To allow an uniform comparison, all results are normalized with respect to the case of SW cache coherence. As a first experiment, we compared the three coherence schemes on the producer-consumer application (PC2,2,16). Figure 5 shows performance, energy and power results of the various coherence schemes. WTI (WTU) denotes hardware-based coherence using invalidate (update) protocol, SW denotes software-based coherence and OS denotes coherence imposed by OS communication primitives. The most striking results emerging from this comparison is the intrinsic inefficiency of OS-based coherence. The results show that in MPSoCs the price paid in terms of performance and energy for an OS-based user-friendly programming model is very high. The existence of some overhead due to the OS is generally to be expected, but in this case it appears to be quite significant. Since the penalties due to the OS are very similar for all the applications used and for all the platform configurations, results relative to OS-based coherence will not be considered further.

Synthetic Benchmarks.

For the producerconsumer benchmark, the experiments show limited sensitivity to the parameters (# of producers/consumers and buffer size). This is due to the nature of the application; in fact, the average speed for each process is forced to be the same. If the consumer is faster than the producer, the buffer will tend to empty and the consumer will wait for the producer. Conversely, if the producer is faster, the buffer will tend to fill up and the producer will have to wait for the consumer. In case of speed mismatches, there are substantial differences on the access patterns only for the hardware lock and, due to the non-cacheability of its address space, this variations have the same impact on system performance and power consumption for the cache coherent solutions as well as for the non-coherent one. The WTU solution results slightly more efficient than the SW one in terms of execution time; however, it also has larger energy consumption. The WTI scheme has a worse behavior for the energy consumption and has an execution time which can be worst or slightly better than the SW one, but always worse than the WTU one. The second set of experiments refers to the RW application, relative to the case of 3 readers and 1 writer (similar results have been obtained for other numbers of readers and writers). We have run three sets of simulations corresponding to the variation of three different parameters: two relative to the application (buffer size and relative speed), the other relative to the platform (cache size). This benchmark is more interesting than the producers-consumer; here, changing the application parameters (and in particular the speed ratio) significantly changes the access pattern to the shared memory and thus the behavior of the coherence scheme involved. In simple terms, hardware cache coherence makes it possible to cache the shared variables. Consequently, the power consumption breakdown shows an increased impact of cache power with respect to bus and shared memory. Therefore, there are access sequences which benefit from this fact, but also sequences which are penalized. For instance, consider a WTU scheme, and a sequence of consecutive writes in a shared memory location; each write will cause a sequence of update command on some data cache. The only useful update command however is the one which occurs just before a read access on the cache, because the values carried by the other ones are lost. For this access pattern the WTU scheme is thus quite inefficient. Conversely, in a sequence of accesses where each write is followed by a read, WTU will be effective, since the update command issued during the write access will load the cache with the data and the following read access will not need a memory and bus access. Note that an useless update command is negative for both power and performance; in fact, since the core cannot access the cache when it is used by the snoop device, some cycles may be wasted. Figure 6 shows performance, power, energy, and EDP, where the relative speed of readers and writers has been set to 1. In this application the resulting access patterns to the shared object involved in the communication are favorable to the HW-based schemes. The readers and the writers run at the same speed, so the reads and the writes tend to be interleaved. A cache coherent platform can be more efficient, since it allows to cache shared data, as the experiments show. By increasing the cache size, we can observe an improvement of performance for both the HW solutions, until the gain saturates. The saturation is due to the point after which the cache is bigger than the whole working set (and further increase of the cache size do not provide any benefit). Furthermore, in this situation, the WTU solution is more efficient than WTI because the invalidation of a cache line will force a read from the shared memory. While enlarging the cache size is always beneficial for performance, it negatively impacts energy. In larger caches the energy required for a single access is larger. Therefore, we can observe an optimal size corresponding to the point where the hit ratio compensates the energy access cost. Moreover, notice that the SW solution is very competitive from an energy point of view, because it reduces the number of accesses to the high-performance, power-hungry data cache. The analysis of the sensitivity to the size of the object involved in the communication (i.e., the buffer) show a similar trend as for the cache size. In fact, the relation between the object used and the cache size determines the cache hit ratio and the performance. Clearly, using bigger objects causes an increase of the execution time, but this increase is the same for all the cache coherence schemes adopted. Still, using small objects for the data interchange moves the load of the application from the communication to the synchronization, and the usefulness of the cache coherent scheme tends to decrease. This is shown in Figure 7, where a shared object of 256 bytes appears to be the best choice, with respect to the 16-byte buffer (too small, synchronization issues became dominant) and with respect to the 1KB bytes case too (the object is too large for the cache used). The impact of the speed ratio between readers and the writers on the various metrics is also interesting. In fact, it directly affects the access patterns on the shared memory and, as a consequence, on data caches. If the writer is faster than the readers, there will be many consecutive writes on the shared object before a read happens. As mentioned above, this is the most negative condition for a cache coherent architecture. This explain why the WTU solution is ineffective when the speed ratio equal to 0.1. The application with speed ratio equal to 10 is also penalized. Again, this occurs because of the unfavorable access pattern. The quicker reader finishes its work when the writer is still running. Thus, the final section of the access sequence is again composed of writes only.

Application Kernels

The analysis of the synthetic applications shows that caching a variable is an energyefficient solution when more reads than writes occurs on that variable; this rule can be used as a guideline when developing applications. This is what have been done with the MM application which shows both an energy and a performance improvements when shared data are cached. This application, indeed, uses many shared variables as read-only objects (the source operands). Moreover, the variables accessed for writing (the result matrix slices), even if shared in principle, are actually used by just one processor. This is because each processor is in charge of computing a mutually exclusive portion of the result. For applications that are not written with the optimization of the access patterns to shared variables in mind, the results are less effective. Both the FFT and the LU applications use shared data to perform their computation. Such data are accessed with several different patterns and it is unlikely that a "good" pattern does exist. Therefore both applications show slightly better performance, but, at the same time, a higher energy consumption, due to the energy wasted to keep the data synchronized and consistent into different caches. Concerning power, we notice that power increases even when energy is decreased when cache coherence is involved. This is because when the energy decreases the performance increase even more, and their ratio increases. In practice, the whole system is working with a higher efficiency, removing CPU stall cycles which unfavorably consume energy without doing any useful work. Conversely, when enforcing coherence wastes energy, performance are impacted less significantly, because the high speed of the cache memories allows to recover many of the cycles wasted to keep data consistence.

Conclusions

This paper compares three different approaches for guaranteeing cache coherence for MPSoC architectures, namely, snoop-based coherence, a software-based approach which prevents caching of shared data, and an OS-based approach.

All three solutions are in principle viable for tightly constrained architectures, because they have limited overhead. Our analysis reveals that the OS-based approach has excessively high cost. Hardware-based cache coherence appears to be competitive in terms of performance, but it has significant power cost when coherence traffic grows, thereby casting some doubts on its viability when power constraints become tighter and the degree of multiprocessing grows. Light-weight schemes which avoid caching of non-shared data are scalable and energy efficient, but they imply maximum programming effort.

Figure 2 .

 2 Figure 2. Operations of the Snoop Device for the Invalidate (a) and Update (b) Policies.

Figure 3 .

 3 Figure 3. Producer-Consumer Pseudo-Code with 1-item buffer.

  Figure 4. Producer-Consumer Pseudo-Code with 1-element buffer.

Figure 5 .

 5 Figure 5. Relative Energy and Performance for the Producer-Consumer Application.

Figure 6 .

 6 Figure 6. Relative Performance, Power, Energy and EDP for the RW Application for Varying Cache Sizes.

Figure 7 .

 7 Figure 7. Relative Energy, Performance, Power and EDP for the RW Application for Varying Buffer Sizes.

Figure 8 .

 8 Figure 8. Relative Energy, Performance, Power and EDP for the RW Application for Varying Execution Speed Ratios.

Figure 9 .

 9 Figure 9. Relative Energy, Performance, Power and EDP for the Application Kernels.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Acknowledgements

We wish to thank Prof. Luca Benini from Università di Bologna for the helpful suggestions on the experimental analysis.


Mirko Loghi
email: loghi@sci.univr.itazzoni@sci.univr.itmassimo.poncino@polito.it

Paolo Azzoni

Massimo Poncino

Tag Overflow Buffering: An Energy-Efficient Cache Architecture

We propose a novel energy-efficient memory architecture which relies on the use of cache with a reduced number of tag bits. The idea behind the proposed architecture is based on moving a large number of the tag bits from the cache into an external register (Tag Overflow Buffer) that identifies the current locality of the memory references; additional hardware allows to dynamically update the value of the reference locality contained in the buffer. Energy efficiency is achieved by using, for most of the memory accesses, a reduced-tag cache.

This architecture is minimally intrusive for existing designs, since it assumes the use of a regular cache, and does not require any special circuitry internal to the cache such as row or column activation mechanisms. Average energy savings are 51% on tag energy, corresponding to about 20% saving on total cache energy, measured on a set of typical embedded applications.

Introduction

Unlike their general-purpose counterparts, embedded systems typically execute a well-defined application mix, which results in a higher predictability of the execution and memory access patterns. This fact offers additional opportunities for optimizing the performance or the energy consumption of the system, by allowing powerful applicationspecific optimizations that have been particularly successful in the design of the memory hierarchy (see [START_REF] Macii | Memory Design Techniques for Low-Energy Embedded Systems[END_REF][START_REF] Wolf | Memory System Optimization of Embedded Software[END_REF] for a survey). Such type of optimizations is also suitable for caches, in spite of their natural adaptation to different workloads, and thus, to different application mixes. One of the most natural way of exploiting the predictability of a given application mix in a cache is that of constructively using the high locality of its memory references. As experimentally observed in several works, typical embedded applications can be decomposed into a few localities, each one accessing a small number of memory regions. In the context of a cache, this translates to a limited number of tags which could potentially be used for comparison. The most interesting property of these localities is their size; experiments show that, regardless of how many localities an application may contain, each locality span a limited range of addresses, which very seldom exceeds the size of a few tens of cache lines. This translates into the use of no more than 5-6 tag bits for most memory accesses. Using a reduced number of tags in a cache, however, may result in incorrectly classifying an actual miss as a hit, since matching two values will in general require the comparison of the full tags. This false positive is called false hit, which cannot obviously be allowed in the execution of a program. At the same time, however, this solution seems to be quite appealing, since, the area and energy consumption of the tag portion can be sizable, especially for relatively small caches, like those typically used in embedded systems. The use of partial tags in a cache has already been proposed in the literature [START_REF] Fagin | Partial Resolution in Branch Target Buffers[END_REF][START_REF] Choi | Cost-Effective Value Prediction Micro-Operation using Partial Tag and Narrow-Width Operands[END_REF][START_REF] Liu | Partial Address Directory for Cache Access[END_REF][START_REF] Min | Partial Tag Comparison: A New Technology for Power-Efficient Set-Associative Cache Designs VLSID'04[END_REF][START_REF] Petrov | Data Cache Energy Minimizations Through Programmable Tag Size Matching to the Applications[END_REF]; most solution, however, require complex cache arrangements (such as the circuitry for selectively activating or disactivating columns of the cell array), or even external hardware. In this work, we propose an energy-efficient cache structure which relies on the partial tag mechanism and a minimal amount of additional hardware external to the cache. The scheme is based on bringing most of the tag bits outside the cache, into a register which works as a sort of level-0 cache, and identifies the current locality. On a memory access, this register is first checked against the most significant bits of the address to determine whether we are inside the current locality or not. On a hit, the partial-tag cache is accessed normally (yet with a small cost); on a miss, the normal miss procedure is followed, with minor modifications. Two are the main strengths of the proposed scheme. First, it uses a fixed number of tag bits in the cache; thus, it does not require any activation circuitry for changing the number of active tags, thus allowing to use a regular, yet smaller cache. Second, it achieves a tag energy reduction comparable to other schemes, yet with a much smaller hardware overhead (one register, two comparators, and a 3 bit-counter in the most complex configuration). The proposed architecture allows to save 51% on tag energy (corresponding to a 20% saving on total cache energy) on average, measured on a set of typical embedded applications [START_REF] Malik | A Lower Power Unified Cache Architecture Providing Power and Performance Flexibility[END_REF].

Motivation

Tags may take a significant portion of cache area and power, especially for relatively small caches, as those typically used in resource-constrained embedded systems. Their contribution is approximately proportional to the rel-ative weight of the tags with respect to the total number of bits in a cache line. For instance, for a 4KB cache with a line size of 4 bytes and 32-bit address, tags take 20 bits, which roughly translates to 20/52 = 38.4% of total cache power. This figures can even be much larger in the case virtual caches (i.e., where the core accesses the cache using virtual addresses) in 64-bit address spaces, although the latter are not very common in the embedded systems domain. In these cases, all processes see the entire virtual address space and the cache must in principle store the entire tags. The relative weight of tags in caches motivates the use of techniques that reduce the size of the tags. Experimental evidence, on the other hand, shows that it is actually possible to reduce them. Typical embedded applications, in fact, due to their high locality of execution, tend to access a small number of memory regions, which would require a limited number of tags for identification. As a matter of fact, previous works [START_REF] Choi | Cost-Effective Value Prediction Micro-Operation using Partial Tag and Narrow-Width Operands[END_REF][START_REF] Min | Partial Tag Comparison: A New Technology for Power-Efficient Set-Associative Cache Designs VLSID'04[END_REF] have shown that using as few as 5-6 tag bits for address matching provides hit rates that are almost identical to full tag matching. This is confirmed by our analysis on a different platform and using different applications, as shown in Figure 1. The plot, referred to one of the PowerStone benchmarks [START_REF] Malik | A Lower Power Unified Cache Architecture Providing Power and Performance Flexibility[END_REF], shows that four bits suffice to achieve the same hit rate of a full-tag comparison. Similar plots have been observed for the other benchmarks. Notice also that even using a zero-tag comparison would provide in this case a hit rate that is only marginally degraded. However, how it will be shown later, other issues than just hit rate must be considered in deciding the optimal number of tag bits to be considered.

¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ £ £ £ £ £ £ £ £ £ £ £ £ £ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¥ ¦ ¥ § ¥ ¥ © ¥ ! " $ & ( ) 1 3

Previous Work

The vast literature on application-specific memory optimizations only marginally involves caches, mainly because the terms "application-specific" and "cache" have historically been intrinsically contrasting terms. More recently, many authors have begun to use the high predictability of memory access patterns of embedded systems for cache optimization.

One class of solutions leverage a configurable cache structure in which line sizes, associativity, and other features can be dynamically reconfigured at runtime, upon detection of a decrease in performance, such as an increased miss rate ( [START_REF] Balasubramonian | Memory Hierarchy Reconfiguration for Energy and Performance in General Purpose Processor Architectures[END_REF][START_REF] Malik | A Low-Power Unified Cache Architecture Providing Power and Performance Flexibility[END_REF][START_REF] Petrov | Towards Effective Embedded Processors in Codesigns: Customizable Partitioned Caches[END_REF][START_REF] Zhang | A Self-Tuning Cache Architecture for Embedded Systems[END_REF][START_REF] Gordon-Ross | Automatic Tuning of Two-Level Caches to Embedded Applications[END_REF]). The technique proposed by Villa et al. exploits the dominance of 0's in cached values by dynamically compressing zeroed data in the cache [START_REF] Villa | Dynamic Zero Compression for Cache Energy Reduction[END_REF], resulting in lower energy thanks to reduced traffic. Givargis [START_REF] Givargis | Improved Indexing for Cache Miss Reduction in Embedded Systems[END_REF] proposes an application-specific cache indexing mechanism based on bit selection. Although the approach is meant for reduction of miss rate, energy efficiency is achieved as a byproduct.

A totally different class of approaches targets the optimization of the consumption of tag memory. In these approaches, power reduction is achieved through the reduction of the number of tag bits to be used for the comparisons; yet they differ in the choice of what and how many tag bits must actually be considered. The knowledge of the memory access pattern of the application may then be used to make this choice more effective.

Comparing addresses using a reduced number of tags, however, may result in incorrectly classifying an actual miss as a hit. We call this situation a false hit, which cannot obviously be tolerated because it does alter the correct behavior of a program. For this reason, matching with reduced tags must be used carefully. For instance, some authors have used it where the cost of a misprediction is not critical, such as in branch prediction engines [START_REF] Fagin | Partial Resolution in Branch Target Buffers[END_REF][START_REF] Choi | Cost-Effective Value Prediction Micro-Operation using Partial Tag and Narrow-Width Operands[END_REF]. The solutions proposed in [START_REF] Liu | Partial Address Directory for Cache Access[END_REF][START_REF] Min | Partial Tag Comparison: A New Technology for Power-Efficient Set-Associative Cache Designs VLSID'04[END_REF] deal instead with false hits by combining a detection scheme with a two-level comparison. On detection of a false hit, the remaining tag bits are enabled and used to complete the comparison. These solutions are indeed effective, but require a re-design of the caches, in order to accommodate the activation/deactivation mechanisms.

A completely different solution is proposed by Petrov and Orailoglu [START_REF] Petrov | Data Cache Energy Minimizations Through Programmable Tag Size Matching to the Applications[END_REF], in which addresses belonging to different localities of the application are encoded into a minimal-length tag. Encoding is implemented by an external block, which can be programmable. This solution, besides needing a relatively complex encoder, requires the capability of selectively disabling a sparse subset of the tag bits in the cache, since they can be dynamically adapted to the program locality.

Our approach is closer to [START_REF] Petrov | Data Cache Energy Minimizations Through Programmable Tag Size Matching to the Applications[END_REF], in that it is a combination of an architectural arrangement (the encoder) and a re-organization of the cache structure. However, it substantially differs in several aspects. First, it does not require any custom modification to the cache structure; no shutdown or selective activation circuitry whatsoever is required. We rather use a regular cache, yet with a reduced number of tags which is predefined up-front. Second, the complexity of the extra logic required by our solution is almost negligible.

Since our approach does not require modification of the cache structure, it might seems comparable to purely architectural techniques, such as the method proposed by of Bellas et al. [START_REF] Bellas | Using Dynamic Cache Management Techniques to Reduce Energy in a High-Performance Processor[END_REF], in which a small L0 instruction cache is employed to store only the most frequently executed basic blocks. Our method, however, sensibly differs from this approach because it does not increase the depth of the memory hierarchy, and therefore, the additional register does not work as a filter of cache accesses;

Reduced-Tag Cache Architecture

Let n be the number of bits of the address, split into b bits of byte offset, s index bits, and t tag bits. The cache will thus consist of S = 2 s lines, each one with size L = 2 b bytes. The proposed architecture is based on using a cache with k < t tag bits; this implies that, of the t tag bits of the address, only k bits are actually fed to the cache. The actual value of k is determined up-front by profiling of the application mix during the software development phase, using a criterion which will be discussed later. The remaining t-k bits represent the locality around which the application is supposed to evolve for a large number of memory accesses. This implies that, except when locality changes, these t -k bits do not change. The idea is thus to store this value and use it as a reference one, against which each memory access is compared. We called this locality value tag overflow value, and tag overflow buffer (TOB) the register used to store it; the name emphasizes that fact that the TOB represents an extension of the cache tag array. In practice, since we assume that for most of the cache lines these tag bits are identical, it is more energy efficient to take it out from the cache.

TOB-Based Architecture

Figure 2 shows a block diagram of the reduced-tag architecture. The shaded box represents the block which implements the TOB-based operations.

The figure emphasizes the fact that the TOB does not filter the accesses to the cache; rather, the TOB and the cache are always accessed in parallel at each memory reference. The outcome of the TOB lookup tells whether an access to the reduced-tag cache is feasible. The functional operations are as follows. On a memory reference, the t -k most significant bits of the address are fed to the TOB. If the two values match (a TOB hit), then we can safely access the reduced-tag cache without worrying about false hits. Clearly, the lookup in the cache may result in a hit or miss as any access to a regular cache. In case of cache miss, the missed line would be replaced using some replacement strategy.

¡ ¢ ¡ ¤ ¥ § ¨© ¥ ! " # $ % & ( 0 2 3 4 5 6 7 " 9 $ # @ 9 0 3 A B C D E F C G H I ¤ ¥ § ¨© ¥ P Q P T V X Y `a X Y `b 5 c c d e f g h i e p q r t u v w x y u x t x w r
A TOB miss, conversely, regardless of the possible cache outcome, results in an equivalent cache miss. In fact, a TOB miss corresponds to a change in locality; a corresponding hit in the cache would result in a false hit, since the full tag does not actually match. There is however one important difference with respect to a regular cache miss: on a TOB miss, we do not fetch the corresponding line into the cache, that is, we do not replace the missed line in the cache. In fact, since we are referring to a single locality value, we regard a change in locality (a TOB miss) as a "sporadic" event.

Therefore, the data contained in the cache are not modified.

In other words, the replacement of a cache line occurs only within the context of the pre-defined locality value.

From the above discussion, it clearly emerges that a key issue for the efficient operations of this scheme is the choice of value of the TOB. The most reasonable choice, at a slight expense of hardware complexity, is to allow the TOB value to change and to dynamically adapt to possible changes in locality. This is the task of the block labeled "Locality Change Detection", which, based on the observation of both the address and TOB miss output decides whether or not to enable the loading of a new locality value (i.e., the t -k bits of the current address). When this occurs, the cache must be flushed, since all the values it contains actually refer to the previous locality. The functional operations of the dynamic architecture are summarized in Table 1.

Concerning the actual implementation of the locality change detection, we opted for a very simple realization, based on the sole observation of the TOB miss output. Specifically, a change in locality is determined as the number of consecutive TOB misses exceeding a given threshold.

The value of the threshold may be critical, since we want to avoid an excessive number of locality switches. An explorative analysis has experimentally shown that a threshold of 7 suffices to track the actual locality changes. Although more sophisticated schemes do exist for locality detection (e.g., [START_REF] Johnson | Run-Time Spatial Locality Detection and Optimization[END_REF]), the simple scheme of Figure 3 works reasonably fine, and meets the tight constraints of embedded systems.

It is important to emphasize that that the TOB-based architecture exhibits a tradeoff between the access to a reducedtag, energy-efficient cache and an increase of the miss rate.

In fact, a TOB miss will always be considered as a cache miss, regardless of what the result of a cache lookup would be. Clearly, the overall scheme is advantageous, energywise, if (i) the TOB miss rate is very low, and (ii) the access to the reduced cache (i.e., the common case) is more energyefficient than the conventional cache. Section 4.2 discusses an analytical solution to this tradeoff.

Choosing the Optimal Tag Size

In the above discussion we have assumed that the value of k is given; however, its choice is actually the most critical design issue for making the TOB architecture effective. In the following, we propose a derivation of the optimal value of k, based on an analytical formulation of the total memory energy E mem as a function of k.

Let E cache (k) the energy consumed by a single cache access. For simplicity, in this discussion we do not distinguish between read and write energy. E cache (k) is monotonically increasing with respect to k; for k = 0 (i.e., no tag) E cache is the energy of the data array only, whereas for k = t E cache is the energy of a full-tag cache. To decouple the dependence of E cache versus k, we can express it as the sum of a constant term (the energy per access in the data array) plus the tag contribution, that is,

E cache (k) = E data + E tag (k).
As discussed in Section 4, the use of the TOB trades off a reduced energy access cost in the cache (E cache (k)) for a slight increase in the overall miss rate (in correspondence of TOB misses). Clearly, the miss rate will also depend on k: as k increases and tends to t, the miss rate will tend to reach the miss rate value of the full-tag cache. In other terms, the miss rate is monotonically decreasing with respect to k. We denote the miss rate with MR(k). The total energy of memory accesses is thus given by:

E tot (k) = E cache (k) + MR(k) • E miss (1)
where E miss denotes the energy cost of a miss penalty, and can be assumed as a constant. Equation 1 consists of the sum of two quantities with opposite behavior with respect to k. Therefore, there must be a value k opt of k which minimizes the expression for E tot , which is used as a value for k in the architecture of Figure 2.

Figure 4 shows the plots of the quantities of Equation 1for the same benchmark used for Figure 1, for a value of miss penalty of 5 (i.e., E miss /E cache = 5). This value, although apparently small, is typical of systems-on-chip architectures, where even the background memory is on-chip, connected through a fast interconnect. Notice how M R(k) (the middle curve) is not actually monotonically decreasing up to the value k that saturates the miss rate (k = 3, from Figure 1). Notice also the linear behavior of E cache . In general, the energy is maximally reduced by applying Equation 1 for each individual application, in order to determine an optimal value of k for each application. The application-specific nature of the architecture could be partially relaxed, however, by computing an "average" value of k opt , derived from the memory access characteristic of a set of applications, at the expense of reduced energy savings.

¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ £ £ £ £ £ £ £ £ £ £ £ £ £ £ £ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¥ ¥ ¥ ¥ ¥ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ § § § § § § § § § § § § § § § ¨© ¨ ¨ © ¨ ¨ © ¨ ¨ © ¨ ! © ¨ ¨ ! © ¨ " © ¨ ¨ " © ¨ # # # $ # % $ & $ ' $ ( $ ) $ 0 $ 1 $ 2 $ # $ $ $ % & ' ( ) 0 1 2 # $ % 3 4 5 6 7 8 9 8 @ A B C D E F B C D I P Q R R S T S B C D

Architectural Refinement

Some applications, such as loop-intensive kernels (e.g., FFT), may be highly localized so that a single main locality does exist; in these cases, the dynamic locality detection mechanism is somehow wasted, since it will not detect any significant locality change. These situations, which can be identified during the profiling phase, a static TOB-based architecture may be as effective as the dynamic one, yet with a smaller hardware overhead. By static we mean that the value in the TOB does not change during system operations; this fixed value represents the most "typical" locality value of the application. Although a static arrangement seems to be overly simplistic, it actually eliminates the possibility of a cache flush: in a static scheme, since no change in locality is allowed, a TOB miss always incurs only in the penalty of an ordinary cache miss. As Section 5 will show, some embedded applications may benefit from the use of a fixed locality value. The static scheme simplifies the architecture of Figure 2 by eliminating the counter and the comparison with the threshold value, so that the additional hardware consists just of the TOB register and a comparator; besides reduced capacitance, switching activity is also much lower, since they switch only in correspondence of TOB misses.

Performance Issues

One important point to emphasize is that the above architecture do not affect the cycle time of the cache, since the TOB and the cache are accessed in parallel, and the former has a much shorter delay than the cache. Rather, these schemes actually improve cache access time, as a byproduct. Since the tag has reduced size, any access to the cache (be it a miss or a hit) will require a shorter time (not just less energy) than accessing a full-tag cache.

Experimental Results

We have applied to proposed architecture to the PowerStone suite, a set of widely used embedded benchmarks, which includes typical multimedia, control, filtering, decoding, and communication kernels [START_REF] Malik | A Lower Power Unified Cache Architecture Providing Power and Performance Flexibility[END_REF]. Memory reference traces have been derived after compilation and execution of the benchmarks on the Platune simulation platform [START_REF] Givargis | Platune: A Tuning Framework for System-on-a-Chip Platforms[END_REF]. Simulations of the architecture have been carried out using a in-house cache simulator, augmented with energy and performance models. The latter are based on an empirical model, derived from interpolation of data extracted from a memory generator by STMicroelectronics in a 0.13 µm technology. The model is parameterized with respect to the number of rows and column, and has been derived by least-mean square regression of a set of energy values obtained with the memory generator for different memory sizes. The intrinsic error of the energy and cycle time models, with respect to actual data, is below Tables 2 and3 show the energy saving results for a 1KB, direct-mapped cache with a 4-byte line size, for instruction and data cache, respectively. Reported data include tag energy, as well as total cache energy, with the relative savings, plus, for each benchmark, the corresponding value of k opt . The average tag energy savings are 51% for the I-cache and 38% for the D-cache; these figures translate into a 21% and a 16% for the total cache energy. The first comment is related to the quantification of the savings. Since the TOB-based architecture targets the reduction of tag energy only, there is an upper bound to the achievable energy savings; in the best case, we can reduce tag energy to zero, and cache energy proportionally to the ratio t/(t + l), where t is the original number of tag bits, and l the size of a line in bits. The cache configuration of Tables 1 and 2 corresponds to a t = 22 bit tag cache, with a l = 32 bit line; therefore, we can achieve no more than 22/(22 + 32) = 40% saving on cache energy, neglecting the overhead. This bound, however, is simplistic and it is based on the assumption that energy perfectly scales with respect to the width (in bits) of the cache; the actual bound is in fact lower because of the design rules of the memory array, which tends to keep the aspect ratio as square as possible. This fact is reflected in the memory models we have used, and explains why the tag energy savings reported are smaller than the expected value; for instance, benchmarks that use only 1 bit of tag actually save less than the simple ratio ((22 -21)/22). This is also important when comparing our results to those of other approaches which are based on less accurate models ( [START_REF] Liu | Partial Address Directory for Cache Access[END_REF][START_REF] Min | Partial Tag Comparison: A New Technology for Power-Efficient Set-Associative Cache Designs VLSID'04[END_REF][START_REF] Petrov | Data Cache Energy Minimizations Through Programmable Tag Size Matching to the Applications[END_REF]. The second observation is concerned with the limited effectiveness of the method for data streams. This is somehow expected, since it is a well-known fact that data references exhibit smallesmaller locality than instruction ones. Entries in tables which are marked with an asterisk denote benchmarks for which the static scheme proved more effective than the dynamic one. For the I-cache, these cases (adpcm and des) correspond to the situation in which the locality detection hardware would force to use an unnecessarily large number of bits in the tag memory, to avoid a large number of cache flushes (402 for adpcm and 191 for des, using a 1-bit dynamic TOB).

For the D-cache, the saving for the blit benchmark actually exceeds the above mentioned upper bound. As a matter of fact, this is due to the cache pollution that occurs for the full-tag cache, while the use of a reduced tag avoids the loading of non useful data into the cache.

Sensitivity to Cache Parameters

The data of Tables 2 and3 refer to a good cache configuration for the TOB scheme, since it has a large number of tags bits. In this section we report cache energy results for different cache configurations, in order to assess when and how much the proposed architecture can be reasonably used as an energy-efficient optimization.

Figure 5 shows how energy savings scales with respect to line size. Larger lines imply a reduced weight of the tags compared to the number of bits of a cache line. The plot confirms this, by showing a consistent decrease of cache energy savings (from an average 20% for a 4-byte line to an average 10% for a 16-byte line). Figure 6 shows how energy savings scales with respect to cache size. Larger cache also imply a reduced weight of the tags because of the increased number of index bits. In addition, since the energy model depends on both the number of rows and columns of the cache, the increase in the number of rows (i.e, cache lines) partially offsets the decrease in the number of columns due to reduced tags. The plot shows a progressive decrease of the energy savings from 20% to about 10%. Finally, Figure 7 shows how energy savings scales with respect to cache associativity. In principle, associativity should not affect the savings significantly, since doubling the number of ways should even reduce the number of index bits, and each way has its own set of tags. The plot confirms this trend, showing that the effectiveness of the method is nearly unchanged for 2-and 4-way associative caches. From the above analysis we can conclude that the proposed technique is maximally effective in the case of small caches and with small line sizes, that is, the typical scenario of small-scale, resource-constrained embedded systems. Large caches, conversely, tend to rapidly nullify the benefits of the TOB-based architecture, since their large access cost reduces the "importance" of tag energy reduction.

¡ ¢ £ ¡ ¢ ¤ ¡ ¢ ¤ £ ¡ ¢ ¥ ¡ ¢ ¥ £ ¡ ¢ ¦ ¡ ¢ ¦ £ ¡ ¢ § ¨© § ¨© § ¨© ¤ ! " # $ % & ' ( "

Encoder Implementation

We have implemented the TOB encoder, synthesizing a RTL description of the architecture of Figure 2 using Synopsys DesignCompiler and a 0.13µm technology library by STMicroelectronics. An encoder with a 15-bit TOB consumes about 0.09 pJ per access. This figure compare favorably to the energy per access of the cache. As a reference value, the energy per access a 16KB, direct-mapped cache with 16 bytes per line is 166.8 pJ. This makes the worst case overhead around 0.6%, and 0.0048% for the best case. Concerning delay, the arrival time of the TOB hit output is 80 ps, and 140 ps for the cache flush output. As a reference figure, the access time for a 16KB cache (on a low-power version of the technology library) is 5ns.

Conclusions

Embedded applications which exhibit high locality may benefit from an architectural arrangement where most of the cache tag bits are moved out of the cache into a special device called tag overflow buffer (TOB). The TOB-based scheme allows to use a reduced-tag cache on most memory references, thus providing a low-overhead and minimally intrusive technique to improve the energy consumption of the memory subsystem. The proposed technique is orthogonal to many similar cache optimization techniques, and provides tag energy savings of 51% on average, corresponding to a 20% average saving of total cache energy.

Figure 1 .

 1 Figure 1. Hit Ratio vs. Number of Tag Bits.

Figure 2 .

 2 Figure 2. Dynamic TOB-Based Architecture.

Figure 3 .

 3 Figure 3. Detailed TOB Implementation.

Figure 4 .

 4 Figure 4. Energy vs. Number of Tag Bits.

Figure 5 .

 5 Figure 5. Effect of Line Size (1 KB Direct-Mapped I-Cache).

FFigure 6 .

 6 Figure 6. Effect of Cache Size (Direct-Mapped I-Cache, Line Size = 4).

  Figure 7. Effect of Associativity (1KB I-Cache, Line Size = 4).

Table 1 . Summary of TOB-Based Operations.

 1

	TOB Cache	Description
	H	H	Regular cache hit, no replacement
	H	M	Regular cache miss, with replacement
			If a change in locality is detected
	M	-	cache flush; otherwise, regular cache
			miss, without replacement.

Table 2 . Energy Results (1KB Direct-Mapped I-Cache, Line Size = 4B).

 2

	Benchmark	kopt		Tag Energy (pJ)		Cache Energy (pJ)
			Original	Optimized	∆	Original	Optimized	∆
	adpcm	10	1,31e5	9,51e4	27,3%	3.06e5	2.70e5	11.7%
	bcnt	0	4,45e3	0	100%	1.05e4	7.23e3	31.6%
	*blit	0	5,91e4	0	100%	1.41e5	5.88e4	58.5%
	compress	10	5,59e5	4,05e5	27,6%	1.32e6	1.17e6	11.7%
	crc	10	2,18e4	1,58e4	27,5%	5.12e4	4.52e4	11.7%
	des	10	2,17e5	1,56e5	27,9%	5.16e5	4.56e5	11.7%
	engine	10	1,44e6	1,05e6	27,2%	3.37e6	2.98e6	11.6%
	fir	10	4,00e4	2,91e4	27,3%	9.38e4	8.28e4	11.7%
	g3fax	10	2,02e6	1,46e6	27,7%	4.77e6	4.21e6	11.7%
	jpeg	10	1,04e7	7,53e6	27,5%	2.44e7	2.16e7	11.7%
	pocsag	10	1,02e5	7,38e4	27,4%	2.38e5	2.10e5	11.7%
	qurt	10	4,32e3	3,11e3	27,9%	1.01e4	8.97e3	12.0%
	ucbqsort	10	4,33e5	3,15e5	27,3%	1.01e6	8.95e5	11.6%
	v42	10	5,68e6	4,11e6	27,6%	1.34e7	1.19e7	11.7%

Table 3 . Energy Results (1KB, Direct-Mapped D-Cache, Line Size = 4B).

 3

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)