Uli Fahrenberg
email: ulrich.fahrenberg@irisa.fr

Axel Legay
email: axel.legay@irisa.fr

Andrzej W Ąsowski
email: wasowski@itu.dk

Vision Paper: Make a Difference! (Semantically) ⋆

Syntactic difference between models is a wide research area with applications in tools for model evolution, model synchronization and version control. On the other hand, semantic difference between models is rarely discussed. We point out to main use cases of semantic difference between models, and then propose a framework for defining well-formed difference operators on model semantics as adjoints of model combinators such as conjunction, disjunction and structural composition. The framework is defined by properties other then constructively. We instantiate the framework for two rather different modeling languages: feature models and automata specifications. We believe that the algebraic theory of semantic difference will allow to define practical model differencing tools in the future.

Introduction

The notion of syntactic difference is well established in software engineering. Textual and graphical algorithms are used to identify differences between text files (source code) and models, and then employed to construct versioning systems, which support comparison and merging of files. Semantic difference between models is rarely discussed in the modeling community. This is surprising given the wide recognition of importance of software evolution; semantic difference can support evolution scenarios like bug localization, or incremental verification, and enable model merging that does not fail on ad-hoc syntactic conflicts.

While working on specification theories, within the realm of concurrency and verification, we have observed that many familiar operators on specifications also apply to other models: conjunction -superposition of requirements; parallel compositionstructural composition of models; refinement -subtyping, just to mention the most important ones. However the notion of difference, as a form of (partial) inverse to the above operators, does not attract nearly as much interest in software engineering.

Our objective is to define and present semantic difference between models in a general fashion. We propose an unambiguous definition of difference which emphasizes its algebraic properties. We instantiate it both for a very simple modeling language, feature models [START_REF] Kang | Feature-oriented domain analysis (FODA) feasibility study[END_REF], and also for the mode complicated language of automata specifications [START_REF] Larsen | Modal specifications[END_REF].

Finally, we also try to explain how difference operators can be used to make formal software development more iterative. It is a common belief that development by stepwise refinement, or use of component algebras, requires using a highly planned and waterfalllike development process. See for example the following quote:

⋆ Supported by MT-LAB: a VKR Centre of Excellence in Modeling of IT Systems An important variant of the waterfall model is formal system development, where a mathematical model of a system specification is created. This model is then refined, using mathematical transformations that preserve its consistency, into executable code. Based on the assumption that your mathematical transformations are correct, you can therefore make a strong argument that a program generated in this way is consistent with its specification. [22, p.32] We will point out uses of difference between models involving flow of information between the stages of the development process and abstraction layers in either way. This allows to run the formal development process in a more agile and iterative manner.

Let us give a teaser of our approach to difference with an extremely simple example: the difference operator for integer numbers. Observe that given two integers t and s, the difference ts can be defined as the maximum integer x for which s + x ≤ t. More succinctly: x is a difference of t by s if it holds that for any other integer y:

s + y ≤ t iff y ≤ x.
It is then easy to see that this defines a unique notion of difference. Now observe that we have here defined ts by property rather than construction. To show that such a difference actually exists, one has to do more work; but if it does, we already know that it is unique. We will repeatedly use constructions like the above for defining differences with respect to other binary operators and for other objects than integers.

A similar algebraic structure can be uncovered in the area of software verification: In programming languages, there is a long established notion of weakest precondition, as the proof obligation on the context of a piece of code which suffices to conclude a given goal [START_REF] Dijkstra | Predicate calculus and program semantics[END_REF][START_REF] Hoare | An axiomatic basis for computer programming[END_REF]. Let P be a fragment of imperative code consisting of a number of sequentially composed statements s 1 , . . . , s k . Let the axiomatic semantics for each statement be expressed by a Hoare triple {ϕ i }s i {ψ i }, where ϕ i is a precondition and ψ i is a postcondition, and let ψ be a desired property of the state after executing P . Proving that P is correct, i.e. that {true}P {ψ} describes P , amounts to showing that

true → ϕ 1 , ϕ 1 → ψ 1 , ψ 1 → ϕ 2 , . . . , ψ k → ψ.
However this may not always be possible, since it enforces correctness regardless of the initial state. Instead it is more reasonable to synthesize an assumption X for which

X → ϕ 1 , ϕ 1 → ψ 1 , ψ 1 → ϕ 2 , . . . , ψ k → ψ.
The property X is called a sufficient precondition for P to guarantee ψ. We say that X is the weakest precondition if it is also necessary, i.e. if it holds for all formulae Y that

Y → ϕ 1 , ϕ 1 → ψ 1 , ψ 1 → ϕ 2 , . . . , ψ k → ψ iff X → Y.
The precondition X informs the user of P on what conditions she has to meet. Dually if the precondition ϕ for P is fixed by the users of the program, the strongest post-condition shows the developer what can be guaranteed with P . If this conclusion is unsatisfactory, the developer can use it to improve P , to give stronger guarantees.

In the following section we will see that this weakest precondition structure, will also appear in differencing feature models.

Case Study: Difference for Feature Models

We will now define difference for the language of feature models [START_REF] Kang | Feature-oriented domain analysis (FODA) feasibility study[END_REF]. To the best of our knowledge, semantic differences for feature models have not been studied before.

Definition 1. A feature model is a tuple M = (F, H, G, ϕ). F is a finite set of features, H ⊆ F ×F is a set of directed edges, G ⊆ 2 F
is a set of or-groups, and ϕ is a Boolean formula over F expressing so-called cross-tree constraints. We demand that i) (F, H) is a forest 3 and write parent(f ), for f ∈ F , for the unique p ∈ F for which (p, f ) ∈ H, and that ii) all states in an or-group share the same parent, so for all e, f ∈ g ∈ G, parent(e) = parent(f ).

Fig. 1 presents feature models of two applets (in the spirit of [START_REF] Antkiewicz | Framework-specific modeling languages with round-trip engineering[END_REF]) which we will use as examples. We will use single letter names for features (underlined in the diagram). In applet 1 , the root feature is a and represents the concept of an applet itself. The diagram says that the applet is decomposed into three smaller features (m, d, t). The empty circles above the names of d and t mean that implementing these two features is optional: an applet may, but does not have to override d and t. However, each applet must override (m) at least one of the methods p, s, and i; this necessity is denoted by the filled circle above the feature m and the filled arc in the concrete syntax. In the abstract syntax, this is expressed by or-groups {m}, {p, s, i} ∈ G. Moreover the cross-tree constraint (placed under the diagram) requires that any applet overriding d or s must also override i.

The variant of feature models presented above is among the simplest (and perhaps most popular) in use. The semantics of the language is defined in terms of translation to Boolean logics, see [START_REF] Batory | Feature models, grammars, and propositional formulas[END_REF]. Let M = (F, H, G, ϕ) be a feature model, then

[[M ]] = ϕ ∧ (p,c)∈H c → p ∧ {f1,...,f k }∈G parent(f 1 ) → k i=1 f i .
The generated formula describes the configurations allowed by M . All of them need to satisfy the cross-tree constraint ϕ. Also, whenever a feature f is included in a configuration, its parent must be included, too. Finally, for each group at least one of its members must be present as soon as its (unique) parent is present. The semantics of our example is hence

(d → i) ∧ (t → i) ∧ (m → a) ∧ (d → a) ∧ (t → a) ∧ (p → m) ∧ (s → m) ∧ (i → m) ∧ (a → m) ∧ (m → (p ∨ s ∨ i)) .
Analysis techniques for feature models often rely on SAT solving or BDDs [START_REF] Thüm | Reasoning about edits to feature models[END_REF][START_REF] Mendonca | SAT-based analysis of feature models is easy[END_REF][START_REF] Trinidad | FAMA framework[END_REF][START_REF] Mendonça | Efficient compilation techniques for large scale feature models[END_REF].

Consider now the feature model applet 2 of Fig. 1, which could emerge as a result of the same concept being modeled by another engineer. To focus attention we will assume that this model has been created by a designer of a component that needs to satisfy model applet 1 as a requirement. A few questions arise: How do these two models differ? Are they equivalent? If not, what is the actual difference?

(d → i) ∧ (t → i) applet 1 applet stop destroy paint init must-override start (¬m → i) applet 2 applet stop destroy paint init must-override start (¬m → i)

Quotient approximation

Fig. 1. The two example feature models and an over-approximation of their quotient Syntactic difference algorithms cannot address these questions. A textual difference algorithm applied to the cross-tree constraint would just say that they differ, being unable to qualitatively explain the difference. An edit-distance based algorithm applied to the tree diagram could likely discover that i has been moved to become a parent of d and t, but not more -tree difference algorithms inform about the editing steps, but they cannot explain their impact. Admittedly, syntactic difference has a proven record of usefulness in many situations. However a modeler trying to understand the difference between the two diagrams, would likely ask a non-syntactic question: What does this change mean? Such question is best addressed semantically.

Following the pattern of the examples in the introduction, we will define the semantic difference of formulae ϕ and ψ as the "weakest" solution X to the implication ϕ ∧ X → ψ. Hence: Definition 2. Given two formulae ϕ and ψ, a formula X is an adjoint to the conjunction

ϕ ∧ ψ if it holds for all formulae Y that ϕ ∧ Y → ψ iff Y → X.
Thus X satisfies ϕ ∧ X → ψ and is implied by any Y which also solves this "equation". The next lemma shows that adjoints to conjunction are defined uniquely up to biimplication, hence we may speak of the adjoint to a conjunction ϕ ∧ ψ and denote it X = ψ \ ∧ ϕ (provided that it exists, which we shall show below):

Lemma 1. If X 1 and X 2 are adjoints to the conjunction ϕ ∧ ψ, then X 1 ↔ X 2 . Proof. X 1 → X 1 entails ϕ∧X 1 → ψ and hence X 1 → X 2 . Similarly for X 2 → X 1 . ⊓ ⊔
Existence of adjoints to conjunction is settled by the following lemma, whose proof is a routine verification of the property in the definition.

Lemma 2. For formulae ϕ, ψ, we have ψ

\ ∧ ϕ ≡ ϕ → ψ.
Coming back to our example, a routine computation shows that

[[applet 1 ]] \ ∧ [[applet 2 ]] = m ∨ p ∨ s ∨ ¬ a ∨ ¬ i.
We have computed the weakest cross-tree constraint which needs to be added to applet 2 for it to act like applet 1 . In other cases it might not be useful just to compute a cross-tree constraint as the difference of two feature models; instead one might want a representation which is closer to the concrete feature-model syntax.

QUOTIENT-AND Input: ϕ, ψ : formulae in CNF Output: an over-approx. to

ψ \ ∧ ϕ 1 Let X = ∅ 2 for each clause c ∈ ψ do 3 if SAT(ϕ ∧ ¬c) then add c to X 4 return X
For this the algorithm displayed on the right can be used. It takes as input two formulae ϕ and ψ in conjunctive normal form (note that semantics of feature models are easily converted to CNF) and then finds for the quotient all clauses in ψ which are not entailed by ϕ (through the satisfiability check of ϕ ∧ ¬c in line 3). This is clearly an overapproximation of the quotient, but might fail at maximality. It can still be useful in the software development process as a more syntactic representation.

As an example, the approximation computed for the quotient of applet 1 by applet 2 is

(¬a ∨ m) ∧ (¬i ∨ m) = (a → m) ∧ (i → m),
and this can easily be added to the syntactic representation of applet 2 to signal the changes necessary, see Fig. 1 (rightmost).

In [START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF] we have presented a general feature model synthesis algorithm. The concrete syntax for the difference in the example above could be automatically computed by this algorithm. In general the algorithm could be used in a modeling tool visualizing semantic differences between feature models.

A Categorical Intermezzo

We will now generalize the considerations on adjoints and difference. A preorder category is just a usual preorder, and a functor is a preorder homomorphism. We use categorical language here because adjoints are categorical concepts: In an adjoint pair (L, R), L is called the left and R the right adjoint. The notion of adjoints is important in category theory; note that we have simplified things here by only working in preorder categories, see e.g. [START_REF] Lane | Categories for the Working Mathematician[END_REF]Ch. 4] for the full story. We can generalize the proof of Lemma 1 to show that up to isomorphism, one half of an adjoint pair determines the other:

Lemma 3. If (L 1 , R 1 ), (L 1 , R 2 ), and (L 2 , R 1 ) are adjoint pairs between preorder categories C, D, then R 1 (y) ↔ C R 2 (y) and L 1 (x) ↔ D L 2 (x) for all x ∈ C, y ∈ D.
To apply these considerations to the setting of Section 2, we need only notice that we are working there in the category F with logical formulae as objects and implications as morphisms. If we denote by A ϕ and I ϕ , for ϕ ∈ F, the mappings F → F given by

A ϕ (ψ) = ϕ ∧ ψ, I ϕ (ψ) = ψ \ ∧ ϕ, then the biimplication of Definition 2 reads A ϕ (Y ) → ψ iff Y → I ϕ (ψ),
hence we are defining an adjoint pair (A ϕ , I ϕ ) for all formulae ϕ. Lemma 2 then says that such an adjoint pair exists for each formula ϕ. Another way to state this is that with tensor product ∧, the category F is (strict symmetric) closed monoidal; in this context, the adjoint \ ∧ is also called the exponential to ∧.

Difference and Development Processes

The adjoint to conjunction is useful in a top-down development scenario, when a general requirements model is given (applet 1 ) and a refinement is developed by a component designer (applet 2 ). By visualizing the difference

[[applet 1 ]] \ ∧ [[applet 2 ]
], the designer can monitor his refinement, and see how to constrain it to meet the general requirements.

In this scenario, information flows top-down -as in the quote in the introduction. The difference is used to refine models at lower abstraction levels. As much as this is useful, this is not fully satisfactory. In software engineering processes, information flows both ways. Especially in iterative processes the implementations are continuously adjusted to meet requirements, while requirements themselves are also continuously adjusted as a result of changing business conditions, and learning from experience in implementing the previous iterations. So we need to not only have ways for communicating model changes top-down in the refinement hierarchy, but also bottom-up.

Let us link these observations to differencing feature models. Observe that ϕ ∧ X → ψ is equivalent to ϕ → ¬X ∨ ψ. Moreover, if X is the weakest constraint that makes the former valid, then ¬X is the strongest constraint that makes the latter valid. If interpreted in modeling terms, ¬X represents the least amount of weakening that needs to be added to the model whose semantics is given by ψ (in the example applet 1 ) in order for the requirements to be possible to meet with components satisfying ϕ (applet 2 ). So ¬X represents the information that flows upwards in the refinement hierarchy whenever it is not the component that needs to be 'fixed', but the requirements that need to be relaxed.

In our example, the negation of the difference formula is ¬m ∧ ¬p ∧ ¬s ∧ a ∧ i. It directly describes a configuration of applet 2 that needs to be admitted by applet 1 in order to make the two models equivalent. In general this negation encodes all configurations of applet 2 that need to be admitted by applet 1 in order to make the two models equivalent.

We define the adjoint to disjunction using a universal property as in Def˙2: Given formulae ϕ, ψ, say that a formula X is an adjoint to the disjunction ϕ ∨ ψ if it holds that

ϕ → Y ∨ ψ iff X → Y
for all formulae Y ; hence X is now to be the "strongest" (with respect to implication ordering) solution to the implication ϕ → X ∨ ψ.

If we denote by O ψ the mapping O ψ (ϕ) = ϕ ∨ ψ, the above bi-implication defines a left adjoint J ψ to O ψ , i.e. an adjoint pair (J ψ , O ψ ). By the considerations of Section 3 we know that such left adjoint, if it exists, is unique; using Lemma 2 and self-duality of the category F we can conclude that ψ \ ∨ ϕ := J ψ (ϕ) = ¬(ψ \ ∧ ϕ) = ¬(ϕ → ψ), hence the adjoint to disjunction always exists.

Use Cases for Semantic Difference of Feature Models. Let us conclude the feature modeling example with a list of concrete applications for the difference of feature models, seen as a difference of their semantics (some of them already suggested above):

-Visualizing and explaining difference between models as specifications.

-The difference is a debugging information. Instances satisfying applet 2 but not the adjoint, are examples of configurations that are illegal in the requirements model. -Dually they can be shown to the designer of applet 1 as examples of possible configurations, which might be used to expand requirements.

-If system configurations in [[applet 2 ]] ∧ ¬([[applet 1 ]] \ ∧ [[applet 2 ]]) pass correctness
tests then the modeler should consider communicating them upward, to negotiate relaxation of these (otherwise reuse may be hindered).

Difference for Automata Specifications

We will now briefly show that the same construction of adjoint is applicable (and in fact known) for automata specifications. Assume a fixed alphabet of actions Σ.

Definition 5 ([14]

). A modal specification (MS) is a tuple R = (P, λ 0 , ∆ m , ∆ M ) where P is a set of states, λ 0 ∈ P is the initial state and ∆ M ⊆ ∆ m ⊆ P ×Σ ×P . ∆ M and ∆ m are respectively mustand may-transitions, both deterministic and total: for every state p ∈ P and action a ∈ Σ, there is exactly one λ ∈ P such that (p, a, λ) ∈ ∆ m .

An automaton is a MS where ∆ M = ∆ m . An instance of a MS is an automaton that is obtained by unfolding the modal specification and cutting some may transitions while ensuring that all the must transitions stay present. Formally, let R = (P, λ 0 , ∆ m , ∆ M ) be a MS and A = (M, m 0 , ∆) an automaton. A is an instance of R, written A |= R, if there exists a binary relation ρ ⊆ M × P such that (m 0 , λ 0 ) ∈ ρ, and for all (m, p) ∈ ρ:

(1) for every (p, a, λ) ∈ ∆ M there is a transition (m, a, m ′ ) ∈ ∆ with (m ′ , λ) ∈ ρ (2) for every (m, a, m ′ ) ∈ ∆ there is a transition (p, a, λ) ∈ ∆ m with (m ′ , λ) ∈ ρ. We write [[R]] for the set of instances of a MS R and say that a MS S refines another MS T , written S ≤ T , iff

[[S]] ⊆ [[T ]].
Two modal specifications over the same alphabet can be composed by synchronizing on common actions, similarly to composition for regular transition systems, but with the provision that the composition of two may-transitions is again a may-transition, and the composition of two must-transitions is a must-transition. The composition M 1 M 2 accepts all compositions between models of M 1 and of M 2 , so

[[M 1 M 2 ]] = {(m 1 m 2 ) | m 1 ∈ [[M 1 ]], m 2 ∈ [[M 2 ]]}.
Given specifications S and T , the quotient operation \ computes the greatest specification X (with respect to the refinement order) such that S X ≤ T . So T \ S is essentially the difference between S and T with respect to structural composition -it describes the component that is missing in order to provide T . In a more succinct way we can say that X is a quotient of T by S if it holds that

S Y ≤ T iff Y ≤ X
for all specifications Y . In the spirit of Section 3, we can note that modal specifications and refinements form a preorder category M, and then the bi-implication above means that quotient is the right adjoint to structural composition, i.e. that for any specification S, the functors P S (T ) = S T and Q S (T ) = T \ S form an adjoint pair (P S , Q S ).

Algorithms for computing these quotients are known for many behavioral component algebras [START_REF] David | Timed I/O automata: a complete specification theory for real-time systems[END_REF][START_REF] Bhaduri | Synthesis of synchronous interfaces[END_REF][START_REF] Raclet | Residual for component specifications[END_REF][START_REF] Bertrand | A compositional approach on modal specifications for timed systems[END_REF][START_REF] Goessler | Modal contracts for component-based design[END_REF].

Discussion: Towards Difference Between Languages

We have characterized semantic distance as an adjoint of a composition operator, and exemplified it for conjunction, disjunction, and parallel composition. In this section we want to illustrate an interesting direction into discussing semantic difference, namely characterizing distance between an instance of a modeling language and a subclass of this language.

This problem appears often in practice. For instance model-checkers for automatalike models may assume that models are deterministic to improve efficiency. Similarly, analysis tools for class diagrams may assume use of a subset of OCL, in order to make the validity (or consistency) problem decidable. For feature models, it is sometimes interesting to look at a class of models that are possible to represent purely diagrammatically (i.e. without cross-tree constraints). However modeling using the full power of the language is usually easier. It is efficient to abstract behaviors with nondeterminism; it is easier to write constraints in full OCL; and it is often natural to express some cross-tree constraints in propositional logics. So the problem arises, whether the full-featured instance of the language is far, or not far, from the subclass of models which are easy to analyse. Is it easy to translate into this subclass? How much expressivity is lost (if any)?

Such translation is usually performed by an abstraction operation. Automata can be determinized; OCL (and propositional) constraints can be weakened to approximate their semantics within the sublanguage. Interestingly such an abstraction is also an adjoint, manifesting the same abstract structure as the instance-to-instance differences. Below we detail this for the example of determinization of modal automata.

The essence of a determinization operator det for (non-deterministic) modal specifications is that for any specification S, det(S) is the smallest deterministic overapproximation of S. Hence det(S) is deterministic, S ≤ det(S), and for any deterministic specification D, S ≤ D implies det(S) ≤ D. Now the last two properties can be combined by demanding that S ≤ D iff det(S) ≤ D for all deterministic D, which is almost the property we have encountered earlier.

Now let M be the preorder category of deterministic modal specifications as before, and let N be the larger category of non-deterministic specifications. We have a functor I : M → N (which "forgets" that the specification is deterministic; hence called a forgetful functor), and det is a functor N → M. The equation above then becomes

det(S) ≤ M D iff S ≤ N I(D)
for all S ∈ N , D ∈ M. Hence the determinization functor det is left adjoint to the forgetful functor I; this type of functors is usually called free. We see in this example that existence of a faithful abstraction to the subclass of our modeling language, which maps a model to an abstraction which is "not too far" away, is the same as a free functor from the language to the subclass, left adjoint to the forgetful functor. This is indeed characteristic of a number of other examples, and motivates the search for free functors also in other areas.

Final Remarks and Related Work

We have described a formal approach to defining semantic difference between models. Perhaps somewhat unexpectedly, our proposal relies on using a preorder on models, instead of using equality (equivalence) and attempting to construct some sort of counterpart of subtraction. Our difference is an operator that is defined as an adjoint. In modeling it makes sense to consider differencing with respect to various composition operators, with conjunction and structural composition being the two main contenders.

Let us briefly summarize the process of defining a semantic difference:

1. Identify a set of models S and a preorder ≤ on S×S (here this was a refinement on automata, or implication of formulae; in other contexts it could be subtyping). 2. Choose a binary composition operator (merge) ⊗ : S × S → S. We have used entailment, parallel composition, conjunction and disjunction in this role. 3. The semantics of models is given as a mapping [[•]] : S → D to a semantic domain. 4. Usually the semantic domain D has better algebraic structure than the syntactic domain S. Thus it is easier to define the difference, as an operator \ ⊗ on the semantic domain: \ ⊗ : D × D → D. By definition T \ ⊗ S returns the maximum X for which S ⊗ X ≤ T , or (as for disjunction) the minimum X for which S ≤ X ⊗ T . Not in all semantic domains such a maximum, or minimum, may exist, but if it does, it is unique (up to the equivalence relation induced by the preorder ≤).

In the future we intend to work on semantic differences for other modeling languages, including UML class diagrams. Providing a difference for this language requires that we are able to compute differences for a substantial fragment of first order logics.

Related Work Semantic difference is discussed in [START_REF] Shahar Maoz | A manifesto for semantic model differencing[END_REF], which defines the difference operator between models T -S as a set of witnesses, which are instances of T but not instances of S. While this definition is natural, and can be useful in many practical cases (for example it directly allows providing counterexamples for non-emptiness of difference), it also has drawbacks. Unlike our proposal, such definition of difference defines an operator which has a different co-domain than the domains of operands. A difference between models is no longer a model. Secondly, in most practical cases, the set of witnesses is infinite and cannot easily be enumerated.

Model merging [START_REF] Brunet | A manifesto for model merging[END_REF] is composing overlapping models, typically, without prior computation of differences between them. In [START_REF] Nejati | Matching and merging of statecharts specifications[END_REF] a semantics oriented merge operation is discussed for statecharts. It would be interesting to see whether this work could be extended to provide visualization of semantic differences for statecharts.

Gerth and co-authors [START_REF] Gerth | Precise detection of conflicting change operations using process model terms[END_REF] present a semantic-based notion between change operations in a version control scenario. Two operations are equivalent if they lead to equivalent business process models (in the sense of trace inclusion). They are not concerned with synthesizing difference models, but with detecting and avoiding merge conflicts. Our operator, could potentially be used in conflict resolution or visualizing changelogs.

Segura et al. [START_REF] Segura | Automated merging of feature models using graph transformations[END_REF] define a syntactic merge operator for feature models using graph transformations. Closer to semantics, Thüm et al. [START_REF] Thüm | Reasoning about edits to feature models[END_REF] discuss semantic differences of edits to feature models. They do not compute differences but simply classify them as strengthening, weakening, refactoring, and incomparable.

Semantic difference for programs is understood better than for models. For instance, in [START_REF] Jackson | Semantic diff: A tool for summarizing the effects of modifications[END_REF] differences between procedures are approximated by dependence relations.

Definition 3 .

 3 A preorder category is a class C of objects and a morphism relation → C ⊆ C ×C which is reflexive and transitive. A functor of preorder categories C, D is a mapping F : C → D which respects the morphisms: if x → C y then F (x) → D F (y).

Definition 4 .

 4 Let C, D be preorder categories and L : C → D, R : D → C functors. Then (L, R) is called an adjoint pair if it holds for all x ∈ C, y ∈ D that L(x) → D y iff x → C R(y).

A forest is a finite disjunction of rooted trees, so technically we capture sets of feature models.

Acknowledgments. We thank Krzysztof Czarnecki for indicating the semantic difference problem to us, and Jose Fiadeiro for an encouraging discussion on the subject.


Somayeh Sardashti
email: somayeh@cs.wisc.edu

André Seznec
email: andre.seznec@inria.fr

David A Wood

Skewed Compressed Caches

Keywords: component, cache design, compression, performance, energy, I

Cache compression seeks the benefits of a larger cache with the area and power of a smaller cache. Ideally, a compressed cache increases effective capacity by tightly compacting compressed blocks, has low tag and metadata overheads, and allows fast lookups. Previous compressed cache designs, however, fail to achieve all these goals.

In this paper, we propose the Skewed Compressed Cache (SCC), a new hardware compressed cache that lowers overheads and increases performance. SCC tracks superblocks to reduce tag overhead, compacts blocks into a variable number of sub-blocks to reduce internal fragmentation, but retains a direct tag-data mapping to find blocks quickly and eliminate extra metadata (i.e., no backward pointers). SCC does this using novel sparse super-block tags and a skewed associative mapping that takes compressed size into account. In our experiments, SCC provides on average 8% (up to 22%) higher performance, and on average 6% (up to 20%) lower total energy, achieving the benefits of the recent Decoupled Compressed Cache [26] with a factor of 4 lower area overhead and lower design complexity.

INTRODUCTION

In modern processors, last level caches (LLCs) mitigate the limited bandwidth, high latency, and high energy of offchip main memory. Increasing LLC size can improve system performance and energy, but at the cost of high area and power overheads. Cache compression seeks to achieve the benefits of larger caches, using the area and power of a smaller cache. Compressed caches increase effective capacity by compressing and compacting cache blocks.

A compressed cache design must balance three frequently-conflicting goals: i) tightly compacting variablesize compressed blocks, ii) keeping tag and other metadata overheads low, and iii) allowing fast (e.g., parallel tag/data) lookups. Previous compressed cache designs achieved at most two of these three goals. The earliest compressed caches do not support variable compressed block sizes [START_REF] Kim | Low-Energy Data Cache Using Sign Compression and Cache Line Bisection[END_REF][29] [START_REF] Lee | An on-chip cache compression technique to reduce decompression overhead and design complexity[END_REF], allowing fast lookups with relatively low area overheads, but achieve lower compression effectiveness due to internal fragmentation. More recent designs [START_REF] Sardashti | Decoupled Compressed Cache: Exploiting Spatial Locality for Energy-Optimized Compressed Caching[END_REF][1] [START_REF] Hallnor | A Unified Compressed Memory Hierarchy[END_REF] improve compression effectiveness using variable-size compressed blocks, but at the cost of extra metadata and indirection latency to locate a compressed block.

In this paper, we propose Skewed Compressed Cache (SCC), which achieves all three goals. SCC exploits the fact that most workloads exhibit both (1) spatial locality (i.e., neighboring blocks tend to reside in the cache at the same time), and (2) compression locality (i.e., neighboring blocks tend to compress similarly) [START_REF] Pekhimenko | Linearly Compressed Pages: A Low-Complexity, Low-Latency Main Memory Compression Framework[END_REF]. SCC exploits spatial locality by tracking super-blocks, e.g., an aligned, adjacent group of blocks (e.g., eight 64-byte blocks). Using superblocks allows SCC to track up to eight times as many compressed blocks with little additional metadata. SCC exploits compression locality by compacting neighboring blocks with similar compression ratio into the same physical data entry, tracking them with one tag.

SCC does this using a novel sparse super-block tag, which tracks anywhere from one block to all blocks in a super-block, depending upon their compressibility. For example, a single sparse super-block tag can track: all eight blocks in a super-block, if each block is compressible to 8 bytes; four adjacent blocks, if each is compressible to 16 bytes; two adjacent blocks, if each is compressible to 32 bytes; and only one block, if it is not compressible. By allowing variable compressed block sizes-8, 16, 32, and (uncompressed) 64 bytes-SCC is able to tightly compact blocks and achieve high compression effectiveness.

Using sparse super-block tags allows SCC to retain a direct, one-to-one tag-data mapping, but also means that more than one tag may be needed to map blocks from the same super-block. SCC minimizes conflicts between blocks using two forms of skewing. First, it maps blocks to different cache ways based on their compressibility, using different index hash functions for each cache way [START_REF] Bienia | PARSEC 2.0: A New Benchmark Suite for Chip-Multiprocessors[END_REF]. To spread all the different compressed sizes across all the cache ways, the hash function used to index a given way is a function of the block address. Second, SCC skews compressed blocks across sets within a cache way to decrease conflicts [START_REF] Seznec | A case for two-way skewed-associative caches[END_REF][3] and increase effective cache capacity.

Compared to recent previous work, SCC eliminates the extra metadata needed to locate a block (e.g., the backward pointers in Decoupled Compressed Caches (DCC) [START_REF] Sardashti | Decoupled Compressed Cache: Exploiting Spatial Locality for Energy-Optimized Compressed Caching[END_REF] [START_REF] Baek | ECM: Effective Capacity Maximizer for High-Performance Compressed Caching[END_REF]), reducing tag and metadata overhead. SCC's direct tag-data mapping allows a simpler data access path with no extra latency for a tag-data indirection. SCC also simplifies cache replacement. On a conflict, SCC always replaces one sparse super-block tag and all of the one to eight adjacent blocks packed into the corresponding data entry. This is much simpler than DCC, which may need to replace blocks that correspond to multiple super-blocks as DCC tracks all blocks of a super-block with only one tag.

Compared to conventional uncompressed caches, SCC improves cache miss rate by increasing effective capacity and reducing conflicts. In our experiments, SCC improves system performance and energy by on average 8% and 6% respectively, and up to 22% and 20% respectively. Compared to DCC, SCC achieves comparable or better performance, with a factor of four lower area overhead, a simpler data access path, and a simpler replacement policy.

This paper makes the following contributions:

(1) SCC is the first compressed cache design to achieve all three goals: variable-size compressed blocks, low tag and metadata overhead, and fast lookups.

(2) SCC exploits spatial and compression locality to pack neighboring blocks with similar compressibility in the same data entry, tracking them with one sparse super-block tag.

(3) SCC enables a simple direct tag-data mapping using a skewed-associative lookup, simultaneously searching different cache ways for different sized compressed blocks.

(4) SCC achieves performance and energy comparable to that of a conventional cache with twice the capacity and associativity, while increasing the area by only 1.5%.

This paper is organized as follows. We discuss background on compressed caching in Section 2, skewed associative caching in Section 3. Then, Section 4 presents our proposal: the Skewed Compressed Cache. Section 5 explains our simulation infrastructure and workloads. In Section 6, we discuss the overheads of compressed caches. We present our evaluations in Section 7. Finally, Section 8 discusses related work, and Section 9 concludes the paper.

II. COMPRESSED CACHING

Cache compression is a promising technique for expanding effective cache capacity with little area overhead. Compressed caches can achieve the benefits of larger caches using the area and power of a smaller cache by compressing and compacting more cache blocks in the same cache area. Designing a compressed cache typically has two main parts: a compression algorithm to compress blocks, and a compaction mechanism to fit compressed blocks in the cache. In this work, we focus on compacting compressed blocks in the last-level cache. Prior work has proposed different compression algorithms that tradeoff compression ratio (i.e., original size over compressed size) and decompression latency. We use the C-PACK+Z compression algorithm because it has been shown to have a good compression ratio with moderate decompression latency and hardware overheads [START_REF] Sardashti | Decoupled Compressed Cache: Exploiting Spatial Locality for Energy-Optimized Compressed Caching[END_REF] [START_REF] Chen | C-pack: a high-performance microprocessor cache compression algorithm[END_REF]. In general, SCC is largely independent of the compression algorithm in use.

To achieve the potentials of a given compression algorithm, the compaction mechanism plays a critical role. Table 1 shows a taxonomy of the current state of the art. Previous proposals differ on two main design factors: (1) how to provide the additional tags, and (2) how to find the corresponding block given a matching tag. Traditionally, compressed caches double the number of tags to track up to 2x cache blocks in the cache [START_REF] Alameldeen | Adaptive Cache Compression for High-Performance Processors[END_REF] [START_REF] Hallnor | A Unified Compressed Memory Hierarchy[END_REF]. Further increasing the number of tags is costly as LLC is already one of the largest on-chip components. More recently, DCC [START_REF] Sardashti | Decoupled Compressed Cache: Exploiting Spatial Locality for Energy-Optimized Compressed Caching[END_REF] shows that tracking super-blocks is an effective technique to increase the number of tags with low area overhead. DCC uses the same number of tags as a regular cache (e.g., [START_REF] Lee | An on-chip cache compression technique to reduce decompression overhead and design complexity[END_REF] tags per set in a 16-way associative cache) but at coarser granularity.

Each tag tracks a 4-block super-block, and can map up to four cache blocks. Tracking super-blocks only slightly increases tag area compared to the same size regular cache.

The subsequent issue is how to find a block given a matched tag (i.e., tag-data mapping). Traditional caches maintain a direct one-to-one relationship between tags and data, so a matching tag implicitly identifies the corresponding data. The earliest compressed caches maintain such a direct relationship by allowing only one compressed size (i.e., half the block size) [START_REF] Kim | Low-Energy Data Cache Using Sign Compression and Cache Line Bisection[END_REF] [START_REF] Lee | An on-chip cache compression technique to reduce decompression overhead and design complexity[END_REF]. More recent designs, VSC [START_REF] Alameldeen | Adaptive Cache Compression for High-Performance Processors[END_REF], IIC-C [START_REF] Hallnor | A Unified Compressed Memory Hierarchy[END_REF], and DCC [START_REF] Sardashti | Decoupled Compressed Cache: Exploiting Spatial Locality for Energy-Optimized Compressed Caching[END_REF], reduce internal fragmentation by supporting variable-size blocks. They compact compressed blocks into a variable number of subblocks (e.g., 0-4 16-byte sub-blocks). Supporting multiple compressed sizes requires a decoupled tag-data mapping that adds a level of indirection to find a block. This requires additional metadata-compressed size in VSC, forwarding pointers in IIC-C, and backward pointers in DCC. This additional metadata allows the cache to compact variablesize compressed blocks in the cache, but at the cost of increased area overhead and design complexity.

III. SKEWED ASSOCIATIVE CACHING

SCC builds on ideas first introduced for skewedassociative caches. In a conventional N-way set-associative cache, each way is indexed using the same index hash function. Thus conflict misses arise when more than N cache blocks compete for space in a given set. Increasing associativity reduces conflict misses, but typically causes an increase in cache access latency and energy cost. Skewed associative caches [START_REF] Seznec | A case for two-way skewed-associative caches[END_REF][3] index each way with a different hash function, spreading out accesses and reducing conflict misses.

Figure 1(a) shows a simple 2-way associative cache, which indexes all cache ways with the same function. In this example, blocks A, B, and C all map to the same set. Thus, only two of these blocks can stay in the cache at any time. Figure 1 (b) illustrates a skewed associative cache, which indexes each cache way with a different hash function. In this example, even though blocks A, B, and C map to the same set using function f1, they map to different sets using function f2 in the second cache way. In this way, all three of these blocks can reside in the cache at the same time. By distributing blocks across the sets, skewed associative caches typically exhibit miss ratios comparable to a conventional set-associative cache with twice the ways [START_REF] Seznec | A case for two-way skewed-associative caches[END_REF] [START_REF] Seznec | Concurrent Support of Multiple Page Sizes on a Skewed Associative TLB[END_REF].

Number of Tags 2x Block Tags 1x Super-Block Tags

Tag-Data Mapping

One-to-one or Direct

FixedC [START_REF] Kim | Low-Energy Data Cache Using Sign Compression and Cache Line Bisection[END_REF][16]

SCC [new]

Decoupled VSC [START_REF] Alameldeen | Adaptive Cache Compression for High-Performance Processors[END_REF] IIC-C [START_REF] Hallnor | A Unified Compressed Memory Hierarchy[END_REF] DCC [START_REF] Sardashti | Decoupled Compressed Cache: Exploiting Spatial Locality for Energy-Optimized Compressed Caching[END_REF] TABLE 1: COMPRESSED CACHE TAXONOMY Skewed associativity has also been used to support multiple page sizes in the same TLB [START_REF] Seznec | Concurrent Support of Multiple Page Sizes on a Skewed Associative TLB[END_REF], at the cost of reduced associativity for each page size. Using different, page-size specific hash functions for each way, such a TLB can look for different size page table entries in parallel. In this work, we use a similar skewing technique but use compressed size, rather than page size, to select the appropriate way and hash-function combinations.

IV. SKEWED COMPRESSED CACHE

Previously proposed compressed caches either do not support variable-size compressed blocks [START_REF] Kim | Low-Energy Data Cache Using Sign Compression and Cache Line Bisection[END_REF][29] [START_REF] Lee | An on-chip cache compression technique to reduce decompression overhead and design complexity[END_REF] or need extra metadata to find a compressed block, increasing overhead and complexity [START_REF] Sardashti | Decoupled Compressed Cache: Exploiting Spatial Locality for Energy-Optimized Compressed Caching[END_REF][1] [START_REF] Hallnor | A Unified Compressed Memory Hierarchy[END_REF]. SCC stores neighboring compressed blocks in a power-of-two number of sub-blocks (e.g., 1, 2, 4, or 8 8-byte sub-blocks), using sparse super-block tags and a skewed associative mapping that preserves a one-to-one direct mapping between tags and data.

SCC builds on the observation that most workloads exhibit (1) spatial locality, i.e., neighboring blocks tend to simultaneously reside in the cache, and (2) compression locality, i.e., neighboring blocks often have similar compressibility [START_REF] Pekhimenko | Linearly Compressed Pages: A Low-Complexity, Low-Latency Main Memory Compression Framework[END_REF]. SCC exploits both types of locality to compact neighboring blocks with similar compressibility in one physical data entry (i.e., 64 bytes) if possible. Otherwise, it stores neighbors separately.

SCC differs from a conventional cache by storing a sparse super-block tag per data entry. Like a conventional super-block (aka sector) cache, SCC's tags provide additional metadata that can track the state of a group of neighboring blocks (e.g., up to eight aligned, adjacent blocks). However, SCC's tags are sparse because-based on the compressibility of the blocks-they may map only 1 (uncompressed), 2, or 4 compressed blocks. This allows SCC to maintain a conventional one-to-one relationship between a tag and its corresponding data entry (e.g., 64 bytes).

SCC only maps neighboring blocks with similar compressibility to the same data entry. For example, if two aligned, adjacent blocks are each compressible to half their original size, SCC will allocate them in one data entry. This allows a block's offset within a data entry to be directly determined using the appropriate address bits. This eliminates the need for additional metadata (e.g., backward pointers [START_REF] Sardashti | Decoupled Compressed Cache: Exploiting Spatial Locality for Energy-Optimized Compressed Caching[END_REF]) to locate a block.

SCC's cache lookup function is made more complicated because the amount of data mapped by a sparse super-block tag depends upon the blocks' compressibility. SCC handles this by using a block's compressibility and a few address bits to determine in which cache way(s) to place the block. For example, for a given super-block, uncompressed blocks might map to cache way #0, blocks compressed to half size might map to cache way #2, etc. Using address bits in the placement decision allows different super-blocks to map blocks with different compressibility to different cache ways. This is important, as it permits the entire cache to be utilized even if all blocks compress to the same size.

To prevent conflicts between blocks in the same superblock, SCC use different hash functions to access ways holding different size compressed blocks. On a cache lookup, the same address bits determine which hash function should be used for each cache way. Like all skewed associative caches, SCC tends to have fewer conflicts than a conventional set-associative cache with the same number of ways.

A. SCC Functionality

Figure 2 illustrates SCC functionality using some examples. This figure shows a 16-way cache with 8 cache sets. The 16 cache ways are divided into four way groups, each including four cache ways. For the sake of clarity, Figure 2 only illustrates super-blocks that are stored in the first way of each way group. This example assumes 64-byte cache blocks, 8-block super-blocks, and 8-byte sub-blocks, but other configurations are possible. A 64-byte cache block can compress to any power-of-two number of 8-byte subblocks (i.e., 1, 2, 4, or 8 sub-blocks). Eight aligned neighbors form an 8-block super-block. For example, blocks I-P belongs to SB2.

SCC associates one sparse super-block tag with each data entry in the data array. Each tag can effectively map (1) a single uncompressed cache block, (2) two adjacent compressed blocks, each compressed to 32 bytes, (3) four adjacent compressed blocks, each compressed to 16 bytes, or (4) eight adjacent compressed blocks, each compressed to 8 bytes. A tag keeps appropriate per-block metadata (e.g., valid and coherence) bits, so it may not be fully populated. If all eight neighbors exist and are compressible to one 8-byte subblock each, SCC will compact them in one data entry, tracking them with one tag. For example, all blocks of SB2 are compacted in one data entry in set #7 of way #1. SCC tracks them with the corresponding tag entry with the states of all blocks set as valid (V in Figure 2). If all cache blocks were similarly compressible, SCC would be able to fit eight times more blocks in the cache compared to a conventional uncompressed cache. On the other hand, in the worst-case

f A, B, C f(A)=f(B) =f(C) A, B, C Tag Data Tag Data f1 f2 f1(A) f1(B) f1(C) f2(A) f2(B) f2(C)
Tag Data Tag Data scenario when there is no spatial locality (i.e., only one out of eight neighbors exists in the cache) or blocks are not compressible, SCC can still utilize all cache space by allocating each block separately. For example, there are only blocks Y and Z from SB4 present in the cache, and neither are compressible. Thus, SCC stores them separately in two different sets in the same way group, tracking them separately with their corresponding tags.

SCC uses a block's compressibility or compression factor (CF) and a few address bits to determine in which way group to place the block. A block's compression factor is zero if the block is not compressible, one if compressible to 32 bytes, two if compressible to 16 bytes, and three if compressible to 8 bytes. For instance, in Figure 2, block A maps to a different set in each cache way depending on its compressibility, shown in hatched (red) entries. SCC allocates A in way group #0, #1, #2, or #3 if A is compressible to 32 bytes (4 sub-blocks), 64 bytes (8 sub-blocks), 8 bytes (1 sub-block), or 16 bytes (2 sub-blocks), respectively. These mappings would change for a different address, so that each cache way would have a mix of blocks with different compression ratios. For instance, SCC allocates block A and block I in cache way #1, if A is uncompressible and I is compressed to 8 bytes (1 sub-block). Using this mapping technique, for a given block, its location determines its compression ratio. This eliminates the need for extra metadata to record block compressibility.

Although SCC separately compresses blocks, it maps and packs neighbors with similar compressibility into one physical data entry. For example, SCC compacts blocks I to P (SB2) into a single physical data entry (set #7 of way #1) as each block is compressed to 8 bytes. However, when neighboring blocks have different compressibility, SCC packs them separately into different physical data entries.

For instance, blocks of SB3 (blocks Q to X) have three different compression ratios. SCC allocates blocks R, U, V, and X, which are compressible to one sub-block each, in one physical data entry (set #3 of way #0). It tracks them with the corresponding tag entry (also shown in Figure 2) with valid states for these blocks. It stores adjacent blocks S and T in a different physical entry since each one is compressed to four sub-blocks. It also stores block Q in way #2 as it is compressible to 32B. Finally, it allocates block W separately as it is not compressible, tracking it with a separate sparse super-block tag shown in Figure 2.

Within a physical data entry, a block offset directly corresponds to the block position in its encompassing superblock. In Figure 2, for example block X is the first block of SB3, similarly its position in the physical data entry in cache way #0 is fixed in the first sub-block. In this way, unlike previous work, SCC does not require any extra metadata (e.g., backward pointers [START_REF] Sardashti | Decoupled Compressed Cache: Exploiting Spatial Locality for Energy-Optimized Compressed Caching[END_REF] or forward pointers [START_REF] Hallnor | A Unified Compressed Memory Hierarchy[END_REF]) to locate a block in the data array. By eliminating the need for extra pointers, SCC simplifies data paths, provides fast lookups, lowers area overhead and design complexity, while still allowing variable compressed sizes.

While eliminating extra metadata simplifies SCC's design, it has the potential to hurt cache performance by increasing conflict misses and lowering effective cache associativity. A conventional 16-way set-associative cache can allocate a block in any cache way, but SCC restricts a block to a 4-way way group based on the block's compression factor. For example, when storing block A with compressed size of 16B, SCC can store it only in one of the four cache ways (including way #3) grouped together in Figure 2. To mitigate the effect of this restriction, SCC employs skewing inside way groups, indexing each cache way with a different hash function to spread out accesses.

B. SCC Structure

Structurally, SCC shares many common elements with previously proposed compressed caches [START_REF] Sardashti | Decoupled Compressed Cache: Exploiting Spatial Locality for Energy-Optimized Compressed Caching[END_REF][1] and the multi-page size skewed-associative TLB [START_REF] Seznec | Concurrent Support of Multiple Page Sizes on a Skewed Associative TLB[END_REF]. Figure 3 (a) shows one set of SCC tag array and its corresponding data set for a 4-way associative cache. Similar to a regular cache, SCC keeps the same number of tags as physical data entries in a cache set (e.g., 4 tags and 4 data entries per set in Figure 3). However, unlike a regular cache, which tracks exactly one single block per tag entry, SCC tag entries track a superblock containing 8 adjacent blocks. Figure 3 illustrates that each tag entry includes the super-block tag address and perblock coherency/valid states (e.g., eight states for 8-block super-blocks). Figure 2 also shows some examples of tag entries for block W in set #4 of way #3, blocks I-P in set #7 of way #1, and blocks R,U,V,X in set #3 of way #0. The data array is largely similar to a conventional cache data array, except it is organized at sub-blocks (e.g., 8 bytes).

W 1 W 0 = A 10 A 9 ^ CF 1 CF 0 (1)
Unlike a regular cache that can allocate a block in any cache way, SCC takes into account block compressibility. Equation [START_REF] Alameldeen | Adaptive Cache Compression for High-Performance Processors[END_REF] shows the way selection logic that SCC uses when allocating a cache block. It uses the block compression factor (CF 1 CF 0 ) and two address bits (A 10 A 9 ) to select the appropriate way group (W 1 W 0 ). The block compression factor (CF 1 CF 0 ) is zero if the block is not compressible, one if compressible to 32 bytes, two if compressible to 16 bytes, and three if compressible to 8 bytes. SCC maps neighboring blocks with similar compressibility to the same data entry. Thus, the way selection logic uses address bits A 10 A 9 , which are above the super-block offset. Note that since SCC uses address bits in way selection, even if all cache blocks are uncompressible (CF == 0), they will spread out among all cache ways. SCC uses different set index functions to prevent conflicts between blocks in the same super-block. Just using bit selection, e.g., the consecutive bits beginning with A 11 , would result in all blocks in the same super-block mapping to the same set in a way group, resulting in unnecessary conflicts. For example, if none of the blocks were compressible, then all eight uncompressed blocks would compete for the four entries in the selected way group (in Figure 2). To prevent this, SCC uses the index hash functions shown in [START_REF] Seznec | A case for two-way skewed-associative caches[END_REF], which draw address bits from the Block ID for the less compressible blocks. These functions map neighboring blocks to the same set only if they can share a data entry (based on their compression factor). SCC also uses different hash functions [START_REF] Seznec | Concurrent Support of Multiple Page Sizes on a Skewed Associative TLB[END_REF] for different ways in the same way group, to further reduce the of conflicts.

Within a 64-byte data entry, a compressed blocks location depends only on its compression factor and address, eliminating the need for extra metadata. Equation 3shows the function to compute the byte offset for a compressed block within a data entry.

C. SCC Cache Operations

Figure 4 illustrates how SCC operates for the main cache operations. On a cache lookup, since the accessing block's compressibility is not known, SCC must check the block's corresponding positions in all cache ways. To determine which index hash function to use for each way, SCC uses (4), the inverse of (1).

CF 1 CF 0 = A 10 A 9 ^ W 1 W 0 ( 4
)
For example, in Figure 2, when accessing block A, the tag entries in set #1 of way #3, set #5 of way #2, set #2 of way #1, and set #6 of way #0 (i.e., all hatched red tag entries) are checked for a possible match. A cache hit occurs if its encompassing super-block is present (i.e., a sparse super-block tag match), and the block state is valid. On a read hit, SCC uses the compression factor and appropriate address bits (using (3)) to determine which of the corresponding sub-blocks should be read from the data array.

On a write hit (e.g., a write-back to an inclusive last-level cache), the block's compressibility might change. If the block can still fit in the same place as before (i.e., its new size is less than or equal to the old one), SCC will update the block in place. Otherwise, SCC invalidates the current version of the block first by setting its corresponding state to invalid. Note that neighboring blocks that share the data entry are not affected. SCC then allocates a new entry as described below for a cache miss. Fortunately, this case does not arise very frequently; simulation results show that on average 97% of updated blocks fit in their previously allocated space.

SCC handles cache misses and write hits that do not fit in their previous space the same way. SCC first uses the block's (new) compression factor and address to search whether an existing sparse super-block of the right size has already been allocated for a neighboring block. For example, consider a write to block R in Figure 2 that changes the compression factor from 3 (8 bytes) to 1 (32 bytes). SCC would invalidate the old copy of R in set #7 of way #0 and write the new data in set #3 in way #2.

Detecting a sparse super-block hit is more complex than a normal tag match for two reasons. First, the size of the sparse super-block-and hence the number of tag bits that must be checked-depends upon the compression factor. For example, to detect that block R can be reallocated to the sparse super-block in set #3 of way #2, SCC must make sure that not only the super-block tag bits match, but that bits A 8 and A 7 also match, since the compression factor is 1 (32 bytes). Second, since SCC does not store bits A 8 A 7 A 6 in the tag entry, it must infer them from the coherence states. For example, SCC can infer that both A 8 and A 7 are one in set #3 of way #2 by testing if either State 7 or State 6 are valid (in this example State 7 is valid because block Q is valid).

If no matching sparse super-block tag with the right compression factor exists, SCC needs to select and evict a victim to make room. SCC selects the least-recently-used super-block tag within the way group (e.g., one of 4 ways in Figure 2). It then evicts all blocks that map to that tag's corresponding data entry. For example, if SCC needs to allocate a new block in set #0 of way #2, it would free that data entry by evicting blocks S and T (i.e., both cache lines in that data entry). Note that the rest of blocks from SB3 will stay in the cache in set #4 of way #3 (block W) and set #3 of way #0 (blocks R,U,V,X). For victim blocks, SCC can determine their compression factor based on the cache way and tag address using (4). After evicting the victim blocks, SCC updates the sparse super-block tag and inserts the new compressed block into the appropriate sub-blocks of the data entry.

SCC's replacement mechanism is much simpler than that needed by DCC. In DCC, allocating space for a block can trigger the eviction of several blocks, sometimes belonging to different super-blocks. In case of a super-block miss, all blocks associated with the victim super-block tag must be evicted, unlike SCC that evicts only blocks belonging to a particular data entry. In addition, in DCC, blocks belonging to other super-blocks may need to be evicted too. Thus, determining which block or super-block is best to replace in DCC is very complex.

SCC also never needs to evict a block on a super-block hit, while DCC may. SCC will allocate the missing block in its corresponding data entry, which is guaranteed to have enough space since the compression factor is used as part of the search criteria. In DCC, a super-block hit does not guarantee that there is any free space in the data array.

V. METHODOLOGY

Our target machine is an 8-core multicore system (Table 2) with OOO cores, per-core private L1 and L2 caches, and one shared last level cache (L3). We implement SCC and other compressed caches at the L3. We evaluate SCC using full-system cycle-accurate GEMS simulator [START_REF] Martin | Multifacet's General Execution-driven Multiprocessor Simulator (GEMS) Toolset[END_REF]. We use CACTI 6.5 [START_REF]CACTI[END_REF] to model area and power at 32nm. We report total energy of cores, caches, on-chip network, and main memory.

We simulate different applications from SPEC OMP [START_REF] Vishal Aslot | SPEComp: A New Benchmark Suite for Measuring Parallel Computer Performance[END_REF], PARSEC [START_REF] Bienia | PARSEC 2.0: A New Benchmark Suite for Chip-Multiprocessors[END_REF], commercial workloads [START_REF] Alameldeen | Simulating a $2M Commercial Server on a $2K PC[END_REF], and SPEC CPU 2006. Table 3 shows the list of our applications. We run mixes of multi-programmed workloads from memorybound and compute-bound SPEC CPU 2006 benchmarks. For example, for astar-bwaves, we run four copies of each benchmark. In Table 3 no yes classify these workloads into: low memory intensive (L), medium memory intensive (M), and high memory intensive (H) if their LLC MPKI is lower than one, between one and five, and over five respectively. We run each workload for approximately 500M instructions with warmed up caches. To address workload variability, we simulate each workload for a fixed number of work units (e.g., transactions) and report the average over multiple runs [START_REF] Alameldeen | Variability in Architectural Simulations of Multi-threaded Workloads[END_REF].

We study the following configurations at LLC:

• Baseline is a conventional 16-way 8MB LLC.

VI. DESIGN COMPLEXITIES

Compressed caches effectively increase cache capacity at the cost of more metadata. Table 4 shows the area breakdown of different compressed caches compared to Baseline. We assume a 48-bit physical address space. These compressed caches differ in the way they provide needed tags to track compressed blocks, and their tag-data mapping. In Table 4, we separate their area overhead caused by more tags (including tag addresses and LRU information), extra metadata for coherence information, and extra metadata for compression (including any compression flag, compressed block size, etc.).

The earlier FixedC and VSC designs double the number of tags, which increases the LLC area by about 6%. FixedC requires no additional metadata for tag-data mapping, since it retains a one-to-one tag-data relationship. It only stores a 1bit flag per block to represent if a block is compressed or not. VSC allows variable-size compressed blocks, requiring three bits of additional metadata per block to store its compressed size. VSC uses this modest additional metadata to determine the location of a compressed block.

DCC uses the same number of tags as Baseline, but each tag tracks a 4-or 8-block super-block. The tags use fewer bits for the matching address, thus compared to a regular cache tags are smaller. On the other hand, DCC needs additional coherence state for each block. DCC_4_16, with 4-block super-blocks, increases LLC area by 1.7% due to more coherence states. By doubling the super-block size, DCC_8_8 can track twice as many blocks but increases the SCC also tracks super-blocks, and thus has tag overhead lower than a conventional cache, but differs from DCC in two ways. First, SCC only needs (pseudo-)LRU state for the tags, while DCC maintains additional state for the decoupled sub-blocks. Second, SCC does not require extra metadata to track a block's location because of its direct tag-data mapping. SCC keeps only the tag address, LRU state and per-block coherence states. SCC_4_16 incurs 1.5% area overhead, more than a factor of 4 lower overhead than DCC_4_16. Similarly, SCC_8_8 incurs 3.5% area overhead, 78% less area overhead than DCC_8_8.

VII. EVALUATION

Cache Utilization

Figure 5 shows the effective capacity of the alternative cache designs normalized to Baseline for our workloads. We calculate the effective capacity of a cache by periodically counting the number of valid blocks. An ideal compressed cache would have a normalized effective capacity that is the same as the application's compression ratio. Practical compressed caches trade off effective capacity for lower overheads and lower complexity. In addition, some low memory intensive workloads, such as ammp, have small working sets, which fit in a small cache even though they have highly compressible data.

Figure 5 also shows that compressed caches can achieve much of the benefit of doubling the cache size, despite their low area overheads. 2X Baseline, which doubles the area used by the LLC, can hold on average 1.9 times more blocks (at most 2x and only 1.6x for the low memory intensive applications). FixedC and VSC provide, on average, 1.5x and 1.6x the normalized effective capacity, respectively. Like 2X Baseline, they can hold at most twice as many blocks since they have exactly twice as many (regular) tags. SCC and DCC can further increase effective capacity because tracking super-blocks allow a maximum effective capacity equal to the super-block size (e.g., 4x and 8x). SCC_4_16 and SCC_8_8 provide, on average, normalized effective capacities of 1.7 and 1.8. SCC achieves the highest effective capacity for memory intensive workloads (on average ~2.3), outperforming 2X Baseline.

DCC achieves a greater normalized effective capacity than SCC because its decoupled tag-data mapping reduces internal fragmentation and eliminates the need to ever store more than one tag for the same super-block. In DCC, nonneighboring blocks can share adjacent sub-blocks, while in SCC only neighboring blocks can share a data entry and only if they are similarly compressible. In addition, DCC does not store zero blocks in the data array, while SCC must allocate a block with compression factor of 3 (i.e., 8 bytes). DCC_4_16 and DCC_8_8 achieve, on average, effective capacities of 2.1 and 2.4, respectively. Of course, this comes at more than four times the area overhead and higher design complexity compared to SCC.

B. Cache Miss Rate

Figure 6 shows the LLC MPKI (Misses per Kilo executed Instructions) for different cache designs. Doubling cache size (2X Baseline) improves LLC MPKI by 15%, on average, but at significant area and power costs. Compressed caches, on the other hand, increase effective capacity and reduce cache miss rate with smaller overheads.

SCC improves LLC miss rate, achieving most of the benefits of 2x Baseline. On average, SCC provides about 13% lower LLC MPKI than Baseline. It achieves the greatest improvements for memory intensive workloads (on average %16). SCC's improvements come from two sources: reduced capacity misses and reduced conflict misses. By increasing effective capacity using compression, SCC obviously tends to reduce capacity misses. But SCC also reduces conflict misses as a result of its skewed-associative tag mapping. SCC primarily uses skewing to map different size compressed blocks to one of four way groups, while preserving a direct, one-to-one tag-data mapping. SCC further uses skewing to reduce conflicts between blocks within a 4-way way group.

To show the impacts of skewing on miss rate, Skewed Base in Figure 6 models a 4-way skewed cache. On average, Skewed Base performs in the same range as the 16-way Baseline (about 4% lower MPKI). For some workloads, such as Apache and Zeus, skewing reduces conflict misses significantly by spreading out the accesses. In SCC, this results to even lower miss rate of these workloads due to compression. On the other hand, for few workloads (mix2, mix5, and mix8), skewing cannot compensate the negative impacts of lowering the associativity in Skewed Base. For those workloads, SCC shows lower miss rate improvements, and even 7% LLC miss rate increase for mix5.

Compared to DCC, SCC provides similar improvements with a factor of 4 lower area overheads. By tracking superblocks, both DCC and SCC perform better than FixedC and VSC. Although DCC_8_8 achieves higher effective capacity than DCC_4_16 and SCC, it performs on average similar to DCC_4_16. For oltp, DCC_8_8 even increases LLC MPKI by about 13% as mapping 8 neighbors to the same set can increase conflict misses.

For completeness we also analyzed a design that combines skewed associativity with DCC. Due to the decoupled tag-data mapping of DCC, adding skewing to DCC results in a more complicated design and replacement policy that we do not consider practical to implement. DCC stores sub-blocks of a block anywhere in a cache set. When applying skewing, this means the sub-blocks of a block can be indexed to different sets. Thus, a BPE needs to store set index as well resulting to high area overheads (~15% area overhead for a configuration similar to DCC_4_16). In addition, skewing can significantly complicate replacement policy in DCC. A block allocation can trigger multiple block evictions as a block can be allocated across different sets. Our results (not shown here) show that adding skewing to DCC improves it marginally.

C. System Performance and Energy

Figure 7, Figure 8, and Figure 9 show system performance and energy of different cache designs. Our reported system energy includes both leakage and dynamic energy of cores, caches, on-chip network, and off-chip main memory.

By increasing cache efficiency and reducing accesses to the main memory, compressed caches can improve system performance and energy, achieving the benefits of larger caches. SCC improves system performance and energy by up to 22% and 20% respectively, and on average 8% and 6% respectively. SCC achieves comparable benefits as previous work DCC with a factor of four lower area overheads.

SCC benefits differ per application. It provides the highest improvements for memory intensive workloads (on average 11% and maximum of 23% faster runtime for apache). On the other hand, it has the smallest gains for low memory intensive workloads (on average 4%). For cache insensitive workloads, such as ammp, blackscholes and libquantum (mix3), SCC does not impact their performance and energy.

Figure 8 also shows the performance of Skewed Base, which basically separates skewing impacts on SCC performance. In Skewed Base, a block can be mapped to a group of 4 ways based on its address. Each of those ways is hashed differently. For some workloads, such as apache, Skewed Base improves their performance and energy by spreading out accesses. For these workloads, although SCC has smaller effective capacity than previous work DCC, SCC overall miss rate improvement is comparable to DCC and 2X Baseline. On the other hand, for few workloads (mix1, mix5, and mix8), skewing cannot compensate the effect of lower effective associativity in Skewed Base. For these workloads, SCC achieves lower performance and energy improvements. For mix5 (astar-bwave), SCC has about 5% increase in runtime and energy.

VIII. RELATED WORK

Compression. Data compression has been widely used to increase storage capacity at disks, main memory, and caches. IBM MXT [START_REF] Abali | Performance of Hardware Compressed Main Memory[END_REF] uses real-time main memory compression to effectively double the main memory capacity. Ekman et al. [START_REF] Ekman | A robust main-memory compression scheme[END_REF] propose a compressed memory design that extends page table entries to keep compressed block sizes. The decoupled zero-compressed memory [START_REF] Dusser | Decoupled Zero-Compressed Memory[END_REF] detects null blocks using a design based on decoupled sectored set-associative caches. Pekhimenko, et al. [START_REF] Pekhimenko | Linearly Compressed Pages: A Low-Complexity, Low-Latency Main Memory Compression Framework[END_REF] propose a new compressed memory design that exploits compression locality to simplify address mapping.

There are many proposals on cache compression. Arelakis et al. [START_REF] Arelakis | SC2: A statistical compression cache scheme[END_REF] utilize statistical compression to improve cache performance and power. Lee's proposed compressed cache [START_REF] Lee | An on-chip cache compression technique to reduce decompression overhead and design complexity[END_REF] uses a direct tag-data mapping, packing adjacent, aligned blocks into a single line if both blocks are compressed by at least a factor of two. Alameldeen and Wood [START_REF] Alameldeen | Adaptive Cache Compression for High-Performance Processors[END_REF] propose a variable-size compressed cache that uses extra metadata (block size) to locate a block. They also propose an adaptive technique to turn off compression whenever not beneficial, which could potentially be used with SCC. Similarly, IIC-C [START_REF] Hallnor | A Unified Compressed Memory Hierarchy[END_REF] supports variable compressed blocks, but uses forward pointers to associate a tag with its sub-blocks resulting in high cache area overhead (24%). Dusser et al. [START_REF] Dusser | Decoupled Zero-Compressed Memory[END_REF] augment the conventional cache with a specialized cache to store zero blocks (ZCA). A recent compressed cache design, DCC [START_REF] Sardashti | Decoupled Compressed Cache: Exploiting Spatial Locality for Energy-Optimized Compressed Caching[END_REF], tracks super-blocks to track more blocks with low area overhead. Unlike SCC, DCC decouples tag-data mapping using backward pointers to locate sub-blocks of a compressed block in a set.

Compression has also been used to reduce cache power consumption. Residue cache [START_REF] Kim | Residue Cache: A Low-Energy Low-Area L2 Cache Architecture via Compression and Partial Hits[END_REF] reduces L2 cache area and power by compressing and storing blocks in half size if compressible. DZC [START_REF] Villa | Dynamic zero compression for cache energy reduction[END_REF] also reduces power by only storing non-zero bytes of cache blocks. Similarly, FVC [START_REF] Yang | Frequent Value Locality and its Applications[END_REF] and significance compression [START_REF] Kim | Low-Energy Data Cache Using Sign Compression and Cache Line Bisection[END_REF] can reduce power by accessing half a block if it is compressible. Similarly SCC can also reduce LLC dynamic power due to accessing fewer bytes for compressed blocks.

S. Baek, et al. [START_REF] Baek | ECM: Effective Capacity Maximizer for High-Performance Compressed Caching[END_REF] improves the performance of compressed caches using a size-aware cache replacement mechanism. Their proposal is orthogonal to ours. Skewing. Skew-associative caches [START_REF] Seznec | A case for two-way skewed-associative caches[END_REF][3] index each way with a different hash function, resulting in lower conflict misses. ZCache uses skewing, but further increases associativity by increasing the number of replacement candidates for a given block. In the context of TLB management, Seznec [START_REF] Seznec | Concurrent Support of Multiple Page Sizes on a Skewed Associative TLB[END_REF] exploits skewed associativity to handle multiple page size granularity at the cost of reduced associativity for each page size.

Super-block caches. This work builds on earlier work on super-block caches. Super-blocks, originally called sectors, have long used to reduce tag overhead [START_REF] Rothman | The Pool of Subsectors Cache Design[END_REF][7] [START_REF] Zebchuk | A Framework for Coarse-Grain Optimizations in the On-Chip Memory Hierarchy[END_REF]. A conventional super-block cache uses one tag to track multiple adjacent, aligned blocks, reducing tag area overhead at the cost of lower cache utilization due to internal fragmentation. Seznec's [START_REF] Seznec | Decoupled sectored caches: Conciliating low tag implementation cost and low miss ratio[END_REF] Decoupled Sector Cache reduces internal fragmentation by decoupling the tags from the data blocks using backward pointers.

IX. CONCLUSIONS

In this paper, we propose Skewed Compressed Cache, a new low-overhead hardware compressed cache. SCC compacts compressed blocks in the last-level cache in such a way that it can find them quickly, and minimize the storage overhead and design complexity. To do so, SCC uses sparse super-block tags to track more compressed blocks, compact blocks into a variable number of sub-blocks to reduce internal fragmentation, but retain a direct tag-data mapping to find blocks quickly and eliminate the extra metadata. SCC proposes a direct tag-data mapping by exploiting compression locality. It compresses blocks to variable sizes, and at the same time eliminates the need for extra metadata (e.g., backward pointers). It dynamically packs neighboring blocks with similar compressibility in the same space tracking them with one sparse super-block tag. SCC further uses skewing to spread out blocks for lower conflicts. Like previous work DCC, SCC achieves performance comparable to that of a conventional cache with twice the capacity and associativity. But SCC does this with less area overhead (1.5% vs. 6.8%).

Figure 1 .

 1 Figure 1. (a) two-way set associative cache (b) skewed associative cache

Figure 2

 2 Figure 2. Skewed Compressed Cache

Figure 6 .Figure 5 .

 65 Figure 6. Normalized LLC MPKI

Figure 8 .Figure 7 .

 87 Figure 8. Normalized performance of different cache designs

Figure 9 .

 9 Figure 9. Normalized system energy

  , we show our applications in increasing LLC MPKI (Misses per Kilo executed Instructions) order for the Baseline configuration. We

	Processors	8, 3.2 GHz, 4-wide issue, out-of-order
	L1 Caches	32 KB 8-way split, 2 cycles
	L2 Caches	256 KB 8-way, 10 cycles
	L3 Cache	8 MB 16-way, 8 banks, 27 cycles
	Memory	4GB, 16 Banks, 800 MHz DDR3.

TABLE 2

 2

	: SIMULATION PARAMETERS

TABLE 3 : APPLICATIONS TABLE 4 :

 3APPLICATIONS4 COMPRESSED CACHES AREA OVERHEAD

		Application	LLC MPKI		Tags	Coherence Metadata	Compression Metadata	Total LLC Overhead
	Low Mem	ammp	0.01	FixedC	5.3%	0.6%	0.3%	6.2%
	Intensive	blackscholes canneal	0.13 0.51	VSC	5.3%	0.6%	1.1%	7.0%
		freqmine	0.65	DCC 4_16	-0.1%	1.7%	5.2%	6.8%
	Medium Mem	bzip2 (mix1) equake	1.7 2.2	DCC 8_8	-0.3%	3.8%	11.8%	15.3%
	Intensive	oltp	2.3	SCC 4_16	-0.2%	1.7%	0	1.5%
		jbb	2.7
		wupwise	4.3	SCC 8_8	-0.4%	3.9%	0	3.5%
	High Mem	gcc-omnetpp-mcf-bwaves-lbm-	8.4
	Intensive	milc-cactus-bzip (mix7)
		libquantum-bzip2 (mix2)	9.3
		astar-bwaves (mix5)	9.3
		zeus	9.3
		gcc-166 (mix4)	10.1
		apache	10.6
	omnetpp-4-lbm-4(mix8) cactus-mcf-milc-bwaves (mix6) applu additional area overhead to 3.8%. DCC decouples tag-data 11.2 13.4 25.9 mapping, requiring extra metadata to hold the backward
	libquantum(mix3) pointers that identify a block's location. DCC keeps one 43.9
	backward pointer entry (BPE) per sub-block in a set. In
	DCC_4_16, backward pointer entries incur 5.2% area
	overhead. Smaller sub-block sizes can reduce internal
	fragmentation, and so improve cache utilization, but at the
	cost of more BPEs. DCC_8_8 uses 8-block sub-blocks, has
	16*8 BPEs per set, resulting in 11.8% extra area overhead
	for the metadata.

X. ACKNOWLEDGEMENTS This work is supported in part by the European Research Council Advanced Grant DAL No 267175, the National Science Foundation (CNS-0916725, CCF-1017650, CNS-1117280, and CCF-1218323) and a University of Wisconsin Vilas award. The views expressed herein are not necessarily those of the NSF. Professor Wood has significant financial interests in AMD, Google, and Panasas. The authors would like to acknowledge Jason Power, Hamid Reza Ghasemi, members of the Multifacet research group, our shepherd Mike O'Connor and our anonymous reviewers for their comments.