Marwa Said

Laurent Cassayre

Jean-Louis Dirion

Ange Nzihou

Xavier Joulia

Behavior of heavy metals during gasification of phytoextraction plants: thermochemical modelling

Keywords: Biomass, Heavy metals, Thermodynamic equilibrium, Simulation, Gasification

Waste such as contaminated biomass, which contain potentially high level of heavy metals, are widely available resources. One of the drawbacks of using this biomass in gasification processes is that some heavy metals might be transferred in the produced syngas, and requires then specific further cleaning steps. Thermodynamic equilibrium calculations are a relevant tool to estimate the behavior of those heavy metals to manage the syngas treatment. The calculations were made with the commercial software FactSage. Due to the several thousands of produced compounds, a specific methodology was set up to choose the stable compounds of the database for the simulations. As an illustrative example, the results of the thermodynamic equilibrium calculations of lead are presented in this paper.

Introduction

Biomass is considered to be the only natural and renewable carbon resource that can effectively be a substitute to fossil fuels. This is why current researches focus on the development of the use of this alternative renewable fuel in many processes in order to produce energy. Gasification has recently been receiving increasing attention thanks to the success of the first plants for the production of electricity from biomass. In fact, gasification is the partial oxidation of biomass, which transforms the organic matter into energy carrier gas. The synthesis gas (CO and H 2 ) allows a wide range of application: power production or biofuel. Most of research works in literature are focused on process using clean biomass as opposed to contaminated biomass which is available in significant quantities. However it is used to a much smaller extent as a source of energy due to their potentially high level of heavy metals. An example of such biomass is phytoextraction plants which are used to extract contaminants from polluted soils. Heavy metals are then accumulated inside the roots, stems and leaves of these plants [START_REF] Gupta | Phytoextraction Capacity of the Plants Growing on Tannery Sludge Dumping Sites[END_REF]. Following the thermochemical process of biomass gasification, these metals are found in the ash, gas and tar products which make them difficult to use and may increase risks to human health and the environment [START_REF] Nzihou | The Fate of Heavy Metals during Combustion and Gasification of Contaminated Biomass-a Brief Review[END_REF]. Recent works have shown that heavy metals can have a significant influence on reaction kinetics and on thermodynamics equilibrium. The aim of this work is to contribute in understanding the behavior of heavy metals during the gasification process of contaminated biomass by modeling the thermodynamic equilibrium. This study aims at predicting the partitioning of heavy metals in the gasification products (gas, tar or ash fractions) (Al [START_REF] Chami | Evaluation of Flash and Slow Pyrolysis Applied on Heavy Metal Contaminated Sorghum Bicolor Shoots Resulting from Phytoremediation[END_REF]. This is an important scientific challenge for optimizing the thermochemical conversion processes applied to the contaminated biomass.

Materials and method

Biomass characterization

The biomass considered in this study is willow, which is the most used plant in phytoextraction thanks to its high absorption capacity of heavy metals. Willow is composed of 55% cellulose, 28% hemicellulose and 17% lignin (Phyllis [START_REF] Database | ECN Phyllis Classification[END_REF]. The elementary composition of willow is indicated in Table1 (Phyllis [START_REF] Database | ECN Phyllis Classification[END_REF].

Calculations methodology

The aim of the thermodynamic modeling is to determine the nature, the state (gas, liquid or solid), speciation the amount of gasification products in given operating conditions considering that all chemical reactions reach their equilibrium. Thermodynamic models can be developed using two approaches (Basu, 2010):

-Stoichiometric Equilibrium Models, based on equilibrium constants of each reaction.

-Non-Stoichiometric Equilibrium Models, where the only inputs needed are the elemental compositions of the feeds. The non-stoichiometric method which is often referred to as "Gibbs free energy minimization approach" is the usual approach since no chemical reaction needs to be assumed [START_REF] Basu Prabir | Biomass Gasification and Pyrolysis: Practical Design and Theory[END_REF]. It may be calculated using modern software provided the thermodynamic data for all compounds (reactants and products) under consideration exist. In a reacting system, a stable equilibrium condition is reached when the Gibbs free energy of the system is at the minimum. Since the thermodynamic properties of the willow components are unconventional in most software, willow has to be split into its constituent elements/molecules as input data to the software. The operating conditions chosen as initial data for the calculations are:

-initial quantity of biomass: 7 mol (biomass chemical formulae: C 6 H 9 O 4 ), -reactor pressure: 1 or 10 bar, -reactor temperature: from 500 to 1000 °C (step value: 25 °C), -gasification agent: 41 mol of H 2 O [START_REF] Froment | Thermodynamic Equilibrium Calculations of the Volatilization and Condensation of Inorganics during Wood Gasification[END_REF].

Calculations were performed with FactSage 6.3 commercial software [START_REF] Bale | FactSage Thermochemical Software and Databases -Recent Developments[END_REF]), which has already found applications in the field of biomass gasification modelling [START_REF] Fraissler | Thermodynamic Equilibrium Calculations Concerning the Removal of Heavy Metals from Sewage Sludge Ash by Chlorination[END_REF]) [START_REF] Froment | Thermodynamic Equilibrium Calculations of the Volatilization and Condensation of Inorganics during Wood Gasification[END_REF]) and includes a large database on heavy metals. FactSage uses the Gibbs free energy minimization method. For each compound, the structure of the database is as follow: available thermochemical data capacity polynomial dependence on temperature Cp(T)) are provided for a given state (solid, liquid and gas) and a given temperature range.

As thousands of compounds and phases exist in the multicomponent system consisting of contaminated willow, a preliminary selection of the compounds which might form in gasification conditions was required: software limitations and computing time impose to take into account a maximum of 1500 compounds, while the commercial SGPS database includes more than 256 liquids, 813 solids and 894 gases. The selection procedure, based on the systematic calculation of predominance diagrams for gaseous compounds, leads to the definition of a new specific database containing a few hundreds compounds. The following methodology was applied:

1. Selection of the major elementary compounds of the main organic components of wood: C, H, N, O and S. 2. Removal of gas, liquid and solid C n H m compounds with n > 3. 3. Selection of all gaseous compounds existing in the contaminated willow system. 4. Removal of unstable gaseous compounds, based on predominance diagram calculations (this step is developed below). 5. Removal of gaseous compounds whose Cp(T) range validity is outside the range [500 °C-1000 °C]. Predominance diagrams were computed in order to identify the most stable compounds over specific partial pressure ranges of gaseous master species: O 2 , S 2 , F 2 , C 2 and H 2 . By combination with a metal element, these master species allow to account for the formation of oxides, sulfides, fluorides, carbides, hydrides and their combinations (e.g. hydroxydes, oxyfluorides, etc.). The predominance diagrams are plotted for a given fixed temperature and a total pressure. In this work, two extreme conditions of gasification process were taken into account: 500 °C/1 bar and 1000 °C/10 bar. For compounds involving O, S, H and C, all compounds shown stable on the predominance diagram were selected. Fig. 1 shows as illustrative example, the Cr-H-O predominance diagram at 500 °C and 1 bar. All those compounds were selected. Furthermore, due to the high number of existing fluoride compounds, it has been decided to eliminate the compounds that are unlikely to form in gasification conditions due to the low partial pressure of F 2 (g). Preliminary calculations using a simplified biomass mixture showed that at 500 °C and 1 bar the fluoride partial pressure P(F 2 ) is below 10 -39 bar and below 10 -21 bar at 1000 °C and 10 bar. So all stable compounds which appeared in the predominance diagrams at a P(F 2 ) above those two values were eliminated from the database. For instance, CrF 5 (g) and CrF 4 (g) which are present in the Cr-F-O diagram (Fig. 2) were not selected in the database.

Results

After the calculation and examination of 163 predominance diagrams for 20 elements (Al, B, P, Na, K, Mg, Ca, Ti, V, Mn, Cr, Fe, Ni, Cu, Zn, Cd, Pb, Si, Sr et Sn), 271 gaseous compounds were selected amongst 894 and grouped in a specific user database. Hence, the thermodynamic equilibrium calculations were performed, with the elemental composition of willow (Table 1), with the user database for the gases and the SGPS database for the liquid and solid compounds.

Partial Pressure of gaseous master species and total volume of gas

The equilibrium calculations allow determining the total gas volume and the partial pressure of all the gaseous compounds. Fig. 3 shows the variation of partial pressure of gaseous master species (O 2 , S 2 , F 2 , H 2 ) at two total pressures 1 and 10 bar. These pressures are related to the predominance diagrams so we can exactly determine the stable compounds and their fate at the real partial pressure of this system. The calculations confirm that the fluoride partial pressure at 500 °C/1 bar is less than 10 -39 bar and 10 -21 bar at 1000 °C/10 bar. Hence, the hypothesis regarding the selection of fluoride compounds is validated. Hence, the hypothesis regarding the selection of fluoride compounds is validated. And as expected from thermodynamic point of view, the total volume of gas increases with the temperature and the total pressure (Fig. 4).

Speciation of Pb species

As an example of heavy metals, the behavior of lead is discussed in this work, because of its high volatility. The thermodynamic calculations are used to identify the speciation of all biomass elements. Fig. 5 presents the speciation of the lead at a total pressure of 1 bar. Above 700 °C, liquid Pb vaporizes to form mainly Pb(g) and PbS(g), as well as small quantities of PbO(g). The calculations also show that, even if the PbO(g) amount notably increases at high temperature, this compound remains a minor component of the gas phase in the whole temperature range.

Pressure effect

The total pressure effect from 1 to 10 bar is reported in Fig. 6. As expected from thermodynamic stand point, increasing the total pressure delays volatilization of most Pb species. At 1 bar the whole amount of lead volatizes at 700 °C, while for a total pressure of 10 bar it volatizes at 800 °C. A comparison of the speciation of lead at 1bar and 10 bar (Fig. 5 and Fig. 6), evidences the presence of PbS in the condensed phase at high pressure and low temperature. Figure 6. Speciation of Pb calculated at 10 bar.

Concentration effect

As willow is a plant which has a high potential to accumulate heavy metals, the concentration of Pb can vary for a plant to other depending in the soil contamination.

The initial lead concentration in the willow used in this work is 135 mg.kg -1 . [START_REF] Nzihou | The Fate of Heavy Metals during Combustion and Gasification of Contaminated Biomass-a Brief Review[END_REF] summarized the different limits concentration of heavy metals in phytoextraction plants: the concentration of Pb can vary between 55 and 300 mg.kg -1 . Fig. 7 shows that doubling the initial concentration of Pb increases the temperature at which the whole amount of Pb volatilizes by 30 °C. Conversely, a speciation of inorganics during wood gasification realized by Froment et al. ( 2013) using a lower lead concentration (1 ppm) shows that the whole amount of Pb volatilizes at 500 °C. This is linked with the increase of the total volume of gas with temperature (Fig. 4): a higher volume of gas is required to evaporate a higher amount of Pb. No other concentration effect was evidenced.

Conclusions

Equilibrium calculations using a compound thermodynamic database were carried out to simulate contaminated biomass gasification. Due to the high number of compounds related to biomass composition, a selective methodology was applied in order to focus on the most relevant gaseous compounds. An example dealing with the behavior of lead during gasification is provided. It shows that, at concentration of about 135 mg/kg in a contaminated willow biomass, lead is mostly found in the gaseous phase under its metal form, and in smaller quantity as sulfur and oxide.

Ongoing work is considering the behavior of other metal species (Transitions metals, Alkali and alkaline earth metals).

Figure 1 .

 1 Figure 1. Cr-H-O predominance diagram (500 °C -1 bar).

Figure 2 .

 2 Figure 2. Cr-F-O predominance diagram (500 °C -1 bar).

Figure 3 .

 3 Figure 3. Partial pressure of gaseous master species at 1 and 10 bar.

Figure

  Figure 4. Total volume gas variation at 1 and 10 bar.

Figure 5 .

 5 Figure 5. Speciation of Pb calculated at 1 bar.

)Figure 7 .

 7 Figure 7. Effect of lead concentration (135 and 270 mg.kg -1 )

Table 1

 1 Elementary composition of dry contaminated willow.

	Element	mol/kg	Element	mol/kg	Element	mol/kg
	C	41.25	S	0.012	Pb	6.51 10 -4
	H	58.40	F	5.30 10 -3	Ti	1.87 10 -4
	O	27.56	Na	5.20 10 -3	Sr	1.59 10 -4
	N	0.300	Al	3.70 10 -3	Mn	1.46 10 -4
	Ca	0.090	Fe	1.97 10 -3	Cu	1.10 10 -4
	Si	0.060	Ni	1.32 10 -3	Ba	2.91 10 -5
	K	0.050	Zn	9.48 10 -4	Cd	1.51 10 -5
	P	0.020	Cr	8.65 10 -4	V	3.92 10 -6
	Mg	0.014	B	8.18 10 -4	Sn	2.52 10 -6


Exploring value prediction with the EVES predictor *

André Seznec INRIA/IRISA

Outline

In this study we explore the performance limits of value prediction for small value predictors (8KB and 32KB) in the context of a processor assuming a large instruction window (256-entry ROB), a perfect branch predictor, fetching 16 instructions per cycle, an unlimited number of functional units, but a large value misprediction penalty with a complete pipeline flush at commit on a value misprediction This evaluation framework emphasizes two major difficulties that an effective hardware implementation value prediction will face. First the prediction of a value should be used only when the potential performance benefit on a correct prediction outweighs the potential performance loss on a misprediction. Second, value prediction has to be used in the context of an out-of-order execution processor with a large instruction window. In many cases the result of an instruction has to be predicted while one or several occurrences of the same instruction are still progressing speculatively in the pipeline. Many value predictors (FCM predictors [START_REF] Sazeides | The predictability of data values[END_REF], stride predictors [START_REF] Mendelson | Speculative execution based on value prediction[END_REF] ) are using the result(s) of one or more previous occurrence(s) of the instruction to predict the result of the current occurrence. In this case, a prediction cannot be used in the pipeline unless no instruction occurrence is still speculative or all the occurrences present in the pipeline have been predicted with high confidence.

Our proposition EVES, for Enhanced VTAGE Enhanced Stride, combines two predictor components which do not use on the result of the last occurrence of the instruction to compute the prediction. We use an enhanced version of the VTAGE predictor [START_REF] Perais | Practical data value speculation for future high-end processors[END_REF], E-VTAGE. On VTAGE, the predicted value is the value directly read at prediction time on the predictor tables. Second, we propose a enhanced version of the stride predictor, E-Stride. E-Stride computes the prediction from the last committed occurrence of the instruction and the number of speculative inflight occurrences of the instruction in the pipeline.

The prediction flowing out from E-Stride or E-VTAGE is used only when its confidence is high. The major contribution of this study is the algorithm to assign confidence to predictions depending on the expected benefit/loss of a * This work was partially supported by an Intel research grant prediction. For the predictor components, the predictor entry allocation and victim selection is also guided by this expected benefit/loss. The confidence/priority assignment algorithms use probabilistic counters defined by Riley et al. [START_REF] Riley | Probabilistic counter updates for predictor hysteresis and stratification[END_REF].

On the distributed traces, the EVES predictors with respectively 8KB, 32KB and unlimited storage budgets achieve respectively 4.026 IPC, 4.202 IPC and 4.408 IPC (geometric mean), i.e., respectively 25.3 %, 30.8 % and 37.3 % improvement over the 3.211 IPC achieved without value prediction. Most of this benefit is brought by the 48entry E-Stride predictor with 16.1 % speedup.

The Enhanced Stride Predictor

The stride predictor [START_REF] Mendelson | Speculative execution based on value prediction[END_REF] computes the predicted value as the result of the addition of the last result of the instruction and a stride. The stride is dynamically computed and updated at validation time. The stride is read on the predictor table while the last value is read either on the predictor table or more often when there is at least an inflight occurrence of the instruction in the pipeline from the speculative instruction window. The prediction is only used in the pipeline when both the stride and the last value are high confidence. That is if any of the inflight occurrences present in the pipeline was not high confidence then one can not use the prediction: when the stride becomes high confident for instruction I, one cannot begin using the hardware value predictions when before all the occurrences of instruction I have disappeared from the instruction window. On short loops, this might never happens unless the pipeline is flushed. Notice that even on a realistic framework implementing branch prediction or memory order violation disambiguation, complete flushes of the pipeline might not be that frequent since these incidents are handled after execution stage, not commit stage.

Dealing with speculative occurrences In order to avoid the above mentioned issue, we introduce a modified version of the stride prediction algorithm. number of speculative occurrences of instruction I. As soon as the stride associated with instruction I reaches high confidence, the prediction can be used even if other (not predicted) occurrences of the same instruction are still present in the pipeline. This is illustrated in Figure 1. The same algorithm was suggested to use value prediction for predicting branches [START_REF] Heil | Improving branch predictors by correlating on data values[END_REF].

A limited storage budget E-stride predictor In the presence of VTAGE, there is no interest in using the stride predictor to predict sequences of constant values; therefore entries with null strides are systematic targets for replacement in E-Stride. A 3-way skewed-associative 48-entry E-Stride predictor was found to reach performance very close to the one of an unlimited size E-stride predictor on the distributed traces. Moreover the width of the stride can be reduced to 20 bits.

Confidence management and entry allocation Not all predictions are equal. Predicting the result of a load missing the LLC cache is more likely to lead to a performance benefit than predicting the result of a single cycle ALU operation.

To manage confidence 5-bit probabilistic counters [START_REF] Riley | Probabilistic counter updates for predictor hysteresis and stratification[END_REF] are used. A prediction is forwarded to the pipeline only if the confidence counter reaches 7.

We carefully define the probabilities of incrementing the confidence counter depending on the instruction type, the instruction behavior and the stride value. In our submission, the probability of incrementing the counter on a load is 1 on a miss on the LLC, 3 4 on a hit on the LLC, 5 16 on a hit on the L2 cache, 9 64 on a hit on the L1 cache. For a slow ALU or a floating point operation, probability 1 32 is used. For single cycle ALU instructions, probability 1 128 is used. Finally we remarked that small strides (e.g. 1) does not bring the same benefit as large ones; therefore for small strides, the confidence counter is incremented with a lower probability.

The probability of inserting an entry on a miss on the predictor is also adjusted to the potential performance benefit/loss expected from predicting the instruction. This probability varies from 1 for a load missing on the LLC to 1 16 for a load hitting in the store queue and to 1 64 for a single cycle ALU instruction.

Abruptly resetting the confidence counter on a misprediction often leads to successions of warming periods with no benefits from stride predictions followed by a period of useful predictions. Therefore we opted for a decrease of the confidence counter by 4. With a 5-bit counter and a high confidence threshold of 7, in most cases the use of the prediction can restart immediately after a misprediction.

On an entry allocation, the selection of the target is also guided by the potential benefit/target from predicting this target entry. Each entry is protected by a 2-bit useful counter. This probabilistic counter is incremented on a correct prediction as the confidence counter, reset on a misprediction, and smoothly aged on tries to steal the entry.

Avoiding some slowdowns Several traces were encountering slowdowns with the E-Stride predictor. In order to avoid/decrease this phenomenon, we implemented a simple safety net. The ratio of misprediction associated with E-stride on the ratio of instructions is monitored and maintained under 1 1024 through a 16-bit counter (SafeStride in the code).

Enhanced VTAGE

VTAGE was introduced in [START_REF] Perais | Practical data value speculation for future high-end processors[END_REF] and is directly derived from the indirect branch predictor ITTAGE [START_REF] Seznec | A case for (partially) tagged geometric history length branch prediction[END_REF].

VTAGE uses the PC and the branch history to predict the instruction result. VTAGE uses several tables for storing predictions. Each table is indexed by a different number of bits of the global branch history, hashed with the PC of the instruction. The different lengths form a geometric series [START_REF] Seznec | A case for (partially) tagged geometric history length branch prediction[END_REF]. The tables are backed up by a base predictor -a tagless Last Value Predictor [START_REF] Lipasti | Exceeding the dataflow limit via value prediction[END_REF]? which is accessed using the instruction address only. In VTAGE, an entry of a tagged component consists of a partial tag, a usefulness counter u used by the replacement policy, a full 64-bit value val, and a confidence counter c. At prediction time, all components are searched in parallel to check for a tag match. The matching component accessed with the longest history provides the prediction to the pipeline.

We describe below the VTAGE features that we modify in E-VTAGE.

Enhancements over VTAGE

Tags and associativity on the PC indexed component A difference between value prediction on VTAGE and indirect branch prediction on ITTAGE is usage. An indirect branch predictor must deliver a prediction otherwise the processor stops. The value predictor has to deliver a prediction on every access. In practice, even when it delivers a value, the predicted value is used in the pipeline only if it has high confidence.

The first modification we make over the initial VTAGE proposition is related to this property. On E-VTAGE, we implement tags on all the components; moreover we add associativity to this component (2-way skewed associative).

Reducing the data volume Since only high confidence predictions are used, many values stored in the predictor are never used as predictions in the pipeline. As a consequence, storing 64 bits of data value in each VTAGE entry is a waste of storage space. The second modification we make over the initial VTAGE is to initially store only a hash of the value in the E-VTAGE entry. When the confidence of this entry reaches a level close to high confidence, we replace this hash by a pointer to a table where we store effective 64-bit values, i.e. E-VTAGE predicts a pointer in the value table (Figure 2).

For instance, on the 32KB predictor, each entry features a 11 bit hash-or-pointer field instead of a 64-bit value field and we use a 3-way skewed associative 1536-entry 55-bit value array. In case of a high confidence prediction, the 64-bit value is reconstructed with the index (9-bits) and the 55-bit value. This allows us to implement a more than 6Kentry E-VTAGE in a 32KB budget instead of a 3K-entry VTAGE if each entry had featured a complete 64-bit value.

Sharing the E-VTAGE storage space We assume a banked interleaved E-VTAGE. The overall storage is shared among all the logical tables of E-VTAGE. The weird numbers of banks in the submitted predictors are due to the fixed storage budget constraints imposed by the championship rules.

Careful management of confidence As already mentioned for E-Stride, one should only use the predicted value when a performance benefit can be expected in average. Such a benefit depends on the potential performance benefit on a correct prediction, on the potential performance loss on a misprediction and the probability of misprediction. Clearly the tradeoff is dependent on the specific instruction.

Figure 2. The E-VTAGE predictor

For the submitted E-VTAGE, we use the probabilistic 3bit confidence counters as in the initial VTAGE proposition [START_REF] Perais | Practical data value speculation for future high-end processors[END_REF].

We carefully defined the updating policy of confidence counters on correct predictions and mispredictions depending on the instruction type, on the provider component, but also on the actual value. In practice, the average benefit of predicting a null value (or a small value) is lower than the average benefit of predicting a large value.

If the provider component is the index based component then the potential benefit is higher than if it is the provider is a tagged component. Therefore the probability of incrementing the confidence counter varies in a large range from 1 for a large value prediction hitting on the index based table and missing the LLC, to 1 256 for a simple ALU operation with null result and a hit on an history indexed component. This set of probabilities was also slightly adapted to the predictor sizes (see the predictor codes).

The algorithm for updating the confidence counter on a misprediction must also be carefully optimized. If the prediction is high confidence then the counter is not directly reset, but just decremented by 2 otherwise it is reset. This provides some hysteresis, thus allowing the use of the prediction quite rapidly after an "accidental" misprediction.

Allocations on misses and mispredictions TAGE and ITTAGE [START_REF] Seznec | A case for (partially) tagged geometric history length branch prediction[END_REF] rely on (quasi)-systematic allocation of new entries after a misprediction. On a limited storage budget E-VTAGE predictor, such a strategy would lead to a huge majority of allocations of entries that do not reach high confidence before being evicted.

Therefore on misses, we only allocate a new entry on E-VTAGE with a probability depending on the instruction type, its latency and its actual result. For instance, on the 32 KB predictor, this probability varies from 1 2 for a large 3 range value load missing on the LLC to 1 2048 for a single cycle ALU on a null value.

The choice of a victim for replacement is based on a 2bit useful field u as on TAGE. u is reset on mispredictions, but also through a resetting algorithm inspired from the one implemented for TAGE. The u incrementing algorithm is also designed to favor the entries that are likely to result in high benefit predictions (probabilities 1 32 to 1, see code). Dealing with bursts of mispredictions To avoid burst of mispredictions, E-VTAGE predictions are not used if an E-VTAGE misprediction has occurred in the last 128 instructions. This does not really increase performance, but reduces the number of mispredictions.

3 Predictors budgets and characteristics of the submitted predictors

The 8KB EVES predictor

The E-VTAGE predictor necessitates 60274 bits:

• a 3-way skewed associative data value table with a total of 384 entries. Each entry is composed of a 57-bit value and a 2-bit useful counter: 22656 bits

• a 47 -bank interleaved VTAGE array with 32 entries on each bank. Each entry consists of a 9 bit hash-orpointer, a 11-bit tag, a 2-bit useful counter and a 3-bit confidence counter, i.e., 25 bits per entry : 37600 bits

• A 10-bit counter TICK to manage the resetting of the useful counters and a 8-bit counter to date the last misprediction.

A 30-bit global path history is used for E-VTAGE, i.e. the addresses of 30 taken branches are taken into account. The E-stride predictor is 3-way skewed associative. It features a total of 48 entries. Each entry is composed of a 64-bit last value, a 2-bit useful counter, a stride limited to 20 bits, a 14-bit tag, a 5-bit confidence counter, and a 1 bit NotFirstOcc indicating that the stride has been set for the entry since its allocation or the last misprediction. Each entry features a total of 106 bits, i.e. a total of 5088 bits for the 48 entries and 16 bits for the SafeStride counter, i.e., a total of 5104 bits.

The 8KB EVES predictor necessitates a total storage budget of 65378 bits.

The 32 KB EVES predictor

The E-VTAGE predictor necessitates 256914 bits:

• A 3-way associative data value table with a total of 1536 entries. Each entry is composed of a 55-bit value and a 2-bit useful counter: 87552 bits.

• A 49-bank interleaved VTAGE array with 128 entries on each bank. Each entry consists of a 11-bit hash-orpointer, a 11-bit tag, a 2-bit useful counter and a 3-bit confidence counter, i.e., 27 bits per entry : 169344 bits.

• A 10-bit counter TICK to manage the resetting of the useful counters and a 8-bit counter to date the last misprediction.

A 127-bit global path history is used for E-VTAGE. The E-stride predictor is the same as the one for the 8KB configuration, i.e., 5104 bits.

The 64KB EVES predictor necessitates a total storage budget of 262108 bits.

The unlimited size EVES predictor

We use quasi-illimited size predictor components with millions of entries and a 511-bit global path history for E-VTAGE.

Performance analysis of the EVES predictor

On the distributed traces, the EVES predictors with 8KB, 32KB and unlimited storage budgets achieve respectively 4.026 IPC, 4.202 IPC and 4.408 IPC (geometric mean), i.e., respectively 25.3%, 30.8% and 37.3 % improvement over the 3.211 IPC achieved without value prediction.

E-Stride versus E-VTAGE

We also simulated independently E-VTAGE and E-Stride.

The 48-entry E-Stride predictor achieves 16.1 % performance improvement by itself. This is particularly impressive for such a small structure (less than a 1 Kbytes !!).

The E-VTAGE components from the 8KB and 32KB EVES achieve 7.0% and 11.2 % performance improvement respectively.

In practice, E-VTAGE and E-Stride do not predict the same instructions. Interestingly, E-VTAGE is able to predict some instructions with stride behavior and short sequences that E-Stride does not capture. An early (and more complex version) of E-Stride was capturing these instructions, but was necessitating regular behavior (i.e., loops with constant number of iterations). In practice, the benefits of E-VTAGE and E-Stride are slightly more than multiplicative (1.112*1.161= 1.291, slightly less than 1.308).

E-Stride and E-VTAGE do not perform well on the same set of traces. For instance, on the 32 KB predictor, among the 135 traces, E-Stride achieves more than 10 % IPC improvement on 41 traces, E-VTAGE achieves the same on 40 traces, but only 19 traces belong to both sets. EVES achieves more than 10 % improvement on 71 traces, more than 20 % on 54 traces and more than 100 % on 15 traces with a peak at 1090 % on compute int 45.

In practice, the E-Stride component is sometimes able to predict the results of loads that miss the L2 cache and sometimes the LLC cache. The coverage of the 48-entry E-Stride component is extremely dependent on the traces varying from 0 to up to 56.4 % with an arithmetic mean of only 3.4 %.

The coverage of the E-VTAGE component is much higher (18.7 % in average for the 32 KB predictor, 45.3 % for the unlimited size predictor) with several traces experiencing coverage higher than 60 % (up to 77 %). However this higher coverage does not translate in the same performance benefit per used prediction as on the E-Stride predictor, since the E-VTAGE predicts much less high reward values (i.e, LLC misses or L2 misses ) than the E-Stride predictor.

Using the number of inflight occurrences on the E-Stride predictor Relying on the number of inflight occurrences to compute the prediction rather than on the last (potentially) predicted value allows to increase the number of predictions used in the pipeline on the stride predictor. Our simulation showed that this improves the performance by about 2 %.

Impact of confidence updating policy and entry allocation policy

To illustrate the benefit of using differentiated probabilities, we run the exact same configuration as EVES, but with fixed confidence update probability and fixed entry allocation probability ( 1 32 ). This resulted in a performance of 3.710 IPC instead of 4.202 IPC on the 32 KB predictor.

Should we predict only loads? We run simulations with predicting only loads. This reduces the performance improvement by 2.7 % for the unlimited configuration, by 1.3% for the 32 KB configuration and 1.5 % for the 8KB configuration. This confirms that most of benefit from value prediction can be obtained from predicting only load results as pointed out in [START_REF] Sheikh | Load value prediction via path-based address prediction: avoiding mispredictions due to conflicting stores[END_REF].

A few remarks on the ChampionShip framework

The reader should not assume that since the simulation framework is an idealistic framework, the potential benefits of value prediction are systematically overestimated in this study.

We would like to point out two features that lead to underestimate the potential benefits of value prediction by the Championship framework.

First the framework assumes that after an instruction triggering a value misprediction, no instruction is fetched and speculatively executed. The instructions that follow the mispredicted instruction are delayed till the commit of the mispredicted instruction. On an effective hardware implementation, some of these instructions would have already been executed at the commit of the mispredicted instruction; particularly load instructions missing the memory hierarchy could have already triggered the fetch of the data from the main memory or the LLC. Thus the simulation framework overestimates the penalty on some mispredictions.

Second, the framework is not providing the precise Op-Code of the instructions. With the EOLE architecture [START_REF] Perais | EOLE: Paving the Way for an Effective Implementation of Value Prediction[END_REF], it has been shown that a large portion of instruction results could be computed in the front-end from computed or predicted registers; thus increasing considerably the number of registers that can be already computed/predicted before entering the execution core. For instance, assuming the 32 KB EVES predictor, 40 % of the register results could have been computed/predicted against 22 % predicted with the EVES predictor.

Summary

EVES combines two predictors E-VTAGE and E-Stride addressing two different instruction behaviors. The E-Stride predictor has no need for the speculative result of the last occurrence of the instruction, but can rely on the last committed value and the number of inflight instances of the instruction in the speculative window. E-VTAGE is a storage effective VTAGE predictor which stores full 64-bit values only when they become very likely to be used in the pipeline.

For these two predictor components, we have developed an efficient approach for managing the prediction uses in the pipeline and and for allocation/eviction of predictor entries. We differentiate the probabilities of updating confidence counters and useful counters and the probabilities of predictor insertions depending on instruction type, instruction latency and instruction result value. On an effective hardware implementation, these probabilities will have to be carefully designed, depending on the management of mispredictions (at execution or at commit), the effective characteristics of the pipeline (execution width, . . . ), the branch predictor behavior, the criticality of the instruction, the memory level parallelism, . . . . Despites the limited information (instruction type, actual latency, actual value) that was available from the simulation framework, the submitted EVES predictors demonstrate a large potential performance impact of value prediction with relatively simple prediction algorithms and limited storage budget.

This study has been focused on limited size predictors. Therefore we have only explored the limits of value prediction with very large storage budgets with EVES. Other prediction schemes could be considered to supplement E-Stride and E-VTAGE such as predicting load addresses [START_REF] Sheikh | Load value prediction via path-based address prediction: avoiding mispredictions due to conflicting stores[END_REF] or Finite Context Methods [START_REF] Sazeides | The predictability of data values[END_REF].

Figure 1. Predicting with E-Stride predictor

  The predicted value for instruction I is computed as the Last Committed Value added with (Inf light + 1)*Stride where Inf light is the

			Update at commit
	table	Val/Stride	Val Stride	Confidence
	PC		Val + (Inflight+1) *Stride
	window	Speculative	Inflight


Biswabandan Panda

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

Synergistic Cache Layout For Reuse and Compression

Recent advances in research on compressed caches make them an attractive design point for effective hardware implementation for last-level caches. For instance, the yet another compressed cache (YACC) layout leverages both spatial and compression factor localities to pack compressed contiguous memory blocks from a 4-block super-block in a single cache block location. YACC requires less than 2% extra storage over a conventional uncompressed cache.

Performance of LLC is also highly dependent on its cache block replacement management. This includes allocation and bypass decision on a miss as well as replacement target selection which is guided by priority insertion policy on allocation and priority promotion policy on a hit. YACC uses the same cache layout as a conventional set-associative uncompressed cache Therefore the LLC cache management policies that were introduced during the past decade can be transposed to YACC. However, YACC features super-block tags instead of block tags. For uncompressed block, these super-block tags can be used to monitor the reuse behavior of blocks from the same super-block. We introduce the First In Then First Use Bypass (FITFUB) allocation policy for YACC. With FITFUB, a missing uncompressed block that belongs to a super-block that is already partially valid in the cache is not stored in the cache on its first use, but only on its first reuse if any. FITFUB can be associated with any priority insertion/promotion policy.

YACC+FITFUB with compression turned off, achieves an average 6.5%/8% additional performance over a conventional LLC, for single-core/multi-core workloads, respectively. When compression is enabled, the performance benefits associated with compression and FITFUB are almost additive reaching 12.7%/17%. This leads us to call this design the Synergistic cache layout for Reuse and Compression (SRC). SRC reaches the performance benefit that would be obtained with a 4X larger cache, but with less than 2% extra storage.

INTRODUCTION

Compressed caches have become an attractive design point for effective hardware implementation for last-level caches (LLCs). Recently proposed compressed cache layouts, such as decoupled compressed cache (DCC) [START_REF] Sardashti | Decoupled Compressed Cache: Exploiting Spatial Locality for Energy-optimized Compressed Caching[END_REF], skewed compressed cache (SCC) [START_REF] Sardashti | Skewed Compressed Caches[END_REF], and yet another compressed cache (YACC) [START_REF] Sardashti | Yet Another Compressed Cache: A Low-Cost Yet Effective Compressed Cache[END_REF] leverage super-block tags 1 to implement compressed caches with a limited storage overhead (less than 2% for SCC and YACC). On YACC and SCC, the data array is organized in fixed size data entries (typically 64B the size of an uncompressed block), each data entry being associated with a unique and fixed tag. However, this tag is a super-block tag and the data entry can contain either multiple compressed memory blocks or a single uncompressed memory block. The read access time of YACC or SCC is similar as the ones of uncompressed caches apart for the decompression. YACC and SCC are agnostic to the cache compression algorithm. However, YACC and SCC ensures that the allocation unit in the LLC is a complete 64B data entry. The DIctionary SHaring (DISH) compression scheme [START_REF] Panda | Dictionary Sharing: An Efficient Cache Compression Scheme for Compressed Caches[END_REF] leverages this particularity. With DISH, a dictionary is shared among the memory blocks represented in the data entry. This allows more efficient compression than traditional compression schemes [START_REF] Alameldeen | Frequent Pattern Compression: A Significance-Based Compression Scheme for L2 Caches[END_REF][START_REF] Chen | C-PACK: A High-performance Microprocessor Cache Compression Algorithm[END_REF][START_REF] Pekhimenko | Base-delta-immediate Compression: Practical Data Compression for On-chip Caches[END_REF] that compress every memory block independently. As a result, YACC or SCC coupled with DISH performs generally better than a 2X uncompressed cache [START_REF] Panda | Dictionary Sharing: An Efficient Cache Compression Scheme for Compressed Caches[END_REF].

LLC replacement policies for compressed caches has received little attention so far, apart from [START_REF] Baek | ECM: Effective Capacity Maximizer for high-performance compressed caching[END_REF][START_REF] Gaur | Base-victim Compression: An Opportunistic Cache Compression Architecture[END_REF][START_REF] Pekhimenko | Exploiting compressed block size as an indicator of future reuse[END_REF]. Before of the introduction of YACC, the adaptation of the state-ofart replacement policies for compressed caches was very challenging. For instance, on DCC [START_REF] Sardashti | Decoupled Compressed Cache: Exploiting Spatial Locality for Energy-optimized Compressed Caching[END_REF], the replacement policy had to manage the super-block replacements (when the super-block tag is missing) and the block replacements (when the super-block tag is present, but the block is missing). As the allocated data size is known only after compression, a single cache miss could lead to several super-blocks evictions and several cache block evictions. In contrast, YACC has a very similar layout as a conventional cache, apart that a super-block tag is associated with each data array entry instead of a block tag (Figure 1), thus allowing to map either an uncompressed data block or up to four co-compressed blocks of the super-block in the data entry. On a cache allocation, a single data entry is replaced. Most LLC management policies that were proposed for conventional caches [START_REF] Jaleel | High Performance Cache Replacement Using Re-reference Interval Prediction (RRIP)[END_REF], [START_REF] Moinuddin | Adaptive Insertion Policies for High Performance Caching[END_REF], [START_REF] Jaleel | Adaptive Insertion Policies for Managing Shared Caches[END_REF], [START_REF] Wu | SHiP: Signature-based Hit Predictor for High Performance Caching[END_REF], [START_REF] Seshadri | The Evicted-address Filter: A Unified Mechanism to Address Both Cache Pollution and Thrashing[END_REF], [START_REF] Manabi Khan | Sampling Dead Block Prediction for Last-Level Caches[END_REF], [START_REF] Manikantan | NUcache: An Efficient Multicore Cache Organization Based on Next-Use Distance[END_REF], [START_REF] Jain | Back to the Future: Leveraging Belady's Algorithm for Improved Cache Replacement[END_REF] can be directly transposed to the YACC cache.

However YACC uses super-block tags. As conventional tags, super-block tags can be used to monitor activities/status of the blocks present in the cache. They can also be used to monitor the activities/status of blocks belonging to the super-block, but absent from the cache. Many fetched blocks are not reused before eviction (e.g. [START_REF] Albericio | The Reuse Cache: Downsizing the Shared Last-level Cache[END_REF]). The super-block tag can be used to (partially) exploit this property on superblocks that are uncompressed or not co-compressible. The First In Then First Use Bypass (FITFUB) allocation policy leverages the super-block tag in YACC as follows.On an LLC miss, on a block Bi within a missing super-block B, a data entry and its super-block associated tag are allocated. On a subsequent miss on Bj in the same super-block B, if the block cannot be co-compressed with Bi, then the validity status associated with Bj is updated in the super-block tag as First-Use, but the data entry is not allocated. An additional data entry and its associated super-block tag location are allocated for Bj only if it gets reused before super-block B is evicted from the cache. On YACC, FITFUB can be implemented on top of a conventional priority insertion/promotion policy.

Interestingly, FITFUB is an efficient LLC allocation policy even when compression is turned off and makes the YACC layout attractive even for uncompressed caches. In our experiments, with compression turned off, YACC with FITFUB achieves an average 6.5% and 8% higher performance than a conventional LLC that uses SHiP++ [START_REF] Wu | SHiP: Signature-based Hit Predictor for High Performance Caching[END_REF] (an extended version of SHiP as per cache replacement championship held in ISCA '17) for single-core and multi-core workloads, respectively. When the DISH compression is turned on, YACC+FITFUB achieves 12.7% and 17% higher performance than a conventional uncompressed LLC for singlecore and multi-core workloads, respectively while YACC only achieves 8.3% and 10%, respectively. As the benefits of cache compression through the YACC layout and the benefits of the FITFUB policy are nearly additive, and as FITFUB essentially identifies the reused cache blocks when uncompressed, we call it Synergistic cache layout for Reuse and Compression (SRC).

The remainder of the paper is organized as follows. Section 2 presents the background on compressed caches. Section 3 introduces our experimental framework. The motivation and opportunity behind SRC is in Section 4. Section 5 introduces the FITFUB allocation policy for YACC. We evaluate the overall SRC proposal in Section 6 while Section 8 concludes this study.

BACKGROUND

This section provides the background on the state-of-the-art compressed cache layouts and cache compression schemes. Compressed Cache Layouts: Compressed caches use a compression technique that compresses cache blocks and a compaction technique that compacts the compressed blocks in the data array. Till the proposition of DCC [START_REF] Sardashti | Decoupled Compressed Cache: Exploiting Spatial Locality for Energy-optimized Compressed Caching[END_REF], the proposed designs were considering the use of more tags than data entries.

In DCC [START_REF] Sardashti | Decoupled Compressed Cache: Exploiting Spatial Locality for Energy-optimized Compressed Caching[END_REF], super-block tags limit the tag volume, the main observation being that often adjacent contiguous cache blocks co-reside at the LLC. DCC compacts up to 16 four 64B block super-block in 1024B. The SCC [START_REF] Sardashti | Skewed Compressed Caches[END_REF] and the YACC cache [START_REF] Sardashti | Yet Another Compressed Cache: A Low-Cost Yet Effective Compressed Cache[END_REF] further simplify the cache layout design through associating a single super-block tag with a fixed 64 bytes data entry.

SCC [START_REF] Sardashti | Skewed Compressed Caches[END_REF] is a compressed cache layout that compacts multiple (in power of two, such as 1, 2, and 4) compressed blocks from the same super-block and stores them in one data entry. It uses super-block tags and skewed associative mapping [START_REF] Seznec | A Case for Two-way Skewed-associative Caches[END_REF]. It maintains an one-to-one mapping between a tag entry and a data entry, and it compacts cache blocks based on their compression factors (CFs). For a data entry of 64 bytes, the CF of a cache block is: four/two/one if it is compressed to <16B/between 16B to 32B/>32B.

YACC [START_REF] Sardashti | Yet Another Compressed Cache: A Low-Cost Yet Effective Compressed Cache[END_REF] simplifies the design aspects of SCC, and maintains the one-to-one mapping between a tag entry and a data entry. It uses a cache layout, which is similar to a regular setassociative uncompressed cache. It removes skewing from SCC, and achieves the same performance level. However, similar to SCC, it compacts cache blocks by taking their CFs into account. YACC tracks from one to four cache blocks with the help of a super-block tag. An important property of YACC is that all the blocks belonging to a 4-block superblocks are stored in the same cache set. That is: YACC has a set associative structure, apart that it uses super-block tags instead of block tags, and that a data entry-aka a cache line locationcan store either an uncompressed cache block, or several compressed cache blocks from the same super-block. This mapping provides an average performance reduction of less than 1.5% as it reduces the effective associativity of a set. In this paper, we consider a version of YACC, which considers only two possible compression factors, CF=1 (1 uncompressed block) and CF=4 (1 to 4 compressed blocks). In that context, Figure 1 represents the super-block tag. Compared to the tag of a conventional cache and assuming a 3-bit coherence/validity state per block, the extra tag storage is only 8 bits per tag ((three 3-bits + one bit compressed/uncompressed ) -(two address bits that YACC saves from the address splitting)), i.e. 1.5% storage overhead on the LLC. Cache Compression Techniques: State-of-the-art compressed cache layouts are independent of the underlying compression techniques such as CPACK [START_REF] Chen | C-PACK: A High-performance Microprocessor Cache Compression Algorithm[END_REF], FPC [START_REF] Alameldeen | Frequent Pattern Compression: A Significance-Based Compression Scheme for L2 Caches[END_REF], BDI [START_REF] Pekhimenko | Base-delta-immediate Compression: Practical Data Compression for On-chip Caches[END_REF], SC2 [START_REF] Arelakis | SC2: A Statistical Compression Cache Scheme[END_REF] and DISH [START_REF] Panda | Dictionary Sharing: An Efficient Cache Compression Scheme for Compressed Caches[END_REF], out of which BDI and DISH provide compression ratios of 1.7X and 2.3X when associated with a YACC layout, respectively [START_REF] Panda | Dictionary Sharing: An Efficient Cache Compression Scheme for Compressed Caches[END_REF]. On a compressed cache, decompression is on the critical path. BDI and DISH decompress a cache block in a single cycle.

BDI [START_REF] Pekhimenko | Base-delta-immediate Compression: Practical Data Compression for On-chip Caches[END_REF] compresses a cache block by exploiting the data correlation property. It uses one base value for a cache block, and replaces the other data values of the block in terms of their respective deltas (differences) from the base value. BDI tries different granularities of base (2 bytes to 8 bytes) and deltas (1 byte to 4 bytes).

DISH [START_REF] Panda | Dictionary Sharing: An Efficient Cache Compression Scheme for Compressed Caches[END_REF] is a compression technique that was specifically designed for the compaction schemes such as SCC and YACC that always allocate a full data block in the LLC and that associate it to a super-block tag. DISH uses a dictionary that is shared by up to four cache blocks. In this way, DISH manages both compression and compaction together. Both BDI and DISH can be used with a YACC layout. DISH is more efficient than BDI when associated with YACC [START_REF] Panda | Dictionary Sharing: An Efficient Cache Compression Scheme for Compressed Caches[END_REF]. It even simplifies the YACC layout design, retaining only two cases CF=4 and CF=1. Therefore, apart when explicitly mentioned, in the remainder of the paper, DISH is used as the compression scheme.

EXPERIMENTAL METHODOLOGY

This section describes the experimental methodology that we use throughout the paper. We use the x86-based gem5 [START_REF] Binkert | The Gem5 Simulator[END_REF] simulator to evaluate the effectiveness of SRC cache at the LLC. Table 1 illustrates the baseline configuration for the simulated systems. We simulate both single-core and multi-core (16-and 32-core) systems, and we estimate the cache latencies with CACTI 6.5 [START_REF] Muralimanohar | CACTI 6.0: A Tool to Understand Large Caches[END_REF]. To calculate the power consumption of DRAM, we use the Micron Power Calculator. We measure the energy consumption of LLC and DRAM, off-chip transfers between LLC and DRAM, as well as the energy consumed by the compressor and de-compressor of DISH. For single-core evaluations, we collect the statistics [START_REF] Bienia | The PARSEC Benchmark Suite: Characterization and Architectural Implications[END_REF], CRONO [START_REF] Ahmad | CRONO: A Benchmark Suite for Multithreaded Graph Algorithms Executing on Futuristic Multicores[END_REF], and from the world of graph analytics and machine learning, into 2 classes (SP, and IN), based on their sensitivity to cache capacity. A benchmark is sensitive-positive (SP) if there is an improvement in performance with the increase in the LLC size and insensitive (IN) if the increase in the cache size does not affect performance or affect it negligibly. IN also includes the benchmarks that are sensitive-negative, for which performance decreases when the LLC size doubles (this occurs when LLC misses do not drop since we model a longer access latency for a larger LLC). We created multi-programmed workload mixes from singlethreaded SPEC CPU 2006, PARSEC, CRONO, and other benchmarks. We created these workload mixes based on their LLC sensitivity and fraction of non-reused cache blocks. At the LLC, if a workload gets a performance increase over 8% when the LLC size doubles, then we classify it as high (H ) in terms of LLC sensitivity otherwise, the workload is termed as low (L). Similarly, in terms of non-reused blocks, if a workload exhibits more than 50% of LLC blocks that are non-reused, we termed it high (h); otherwise, it is termed as low (l). We select 200 16-core and 32-core workloads into four categories such as Hh, Hl, Lh, and Ll where each category consists of 50 workloads. For multi-core evaluations, we evaluate both multi-programmed and multi-threaded workloads. For multi-threaded workloads (such as PARSEC and CRONO), we use the region of interest for 2B instructions. For multiprogrammed workloads, we simulate the multi-programmed mixes by running each benchmark for 2B instructions from the region of interest. A workload terminates when the slowest benchmark completes 2B instructions. For all the evaluations, we warm-up the cache for 1B instructions before running the region of interest.

Metrics: We use data block misses per kilo instruction (MPKI) to measure the behavior of the cache itself. For singlecore simulations and for multi-threaded workloads, we use speedup as the metric, i.e., Ex ect ime bas el ine Ex ect ime t echnique . For multi programmed mixes, we use normalized weighted speedup (WS) [START_REF] Snavely | Symbiotic Job scheduling for a Simultaneous Multithreaded Processor[END_REF] and the normalized fair speedup (FS) [START_REF] Kun Luo | Balancing thoughput and fairness in SMT processors[END_REF] where

W S = N -1 i=0 I PC t oдe t he r i I PC al one i , FS = N N -1 i =0 I P C al one i I P C t oдe t her i , IPC
t oдet her i is the IPC of core i when it runs along with other N -1 applications and IPC alone i is the IPC of core i when it runs alone on a N -core multi-core system. WS tends to be a good measure for system throughput improvement while FS balances system throughput improvement with maintenance of system fairness.

MOTIVATION AND OPPORTUNITY

Albericcio et al. showed that a significant fraction of the blocks missing in the LLC do not get any reuse before eviction from LLC [START_REF] Albericio | The Reuse Cache: Downsizing the Shared Last-level Cache[END_REF]. Our experiments show that this property still holds for compressed caches. Fig. 2 illustrates the fraction of LLC blocks that are not reused on YACC in our experiments for single core. On average, more than 55% of blocks (both compressed and uncompressed) do not get a reuse at the LLC, with the maximum of 82%. In particular, streaming applications such as libquantum have a significant number of LLC blocks getting no reuse. The Reuse cache [START_REF] Albericio | The Reuse Cache: Downsizing the Shared Last-level Cache[END_REF] was proposed to exploit this property on an uncompressed cache. The Reuse cache layout is radically different from the one of a conventional cache. It implements 4X more tags than the number of data cache blocks; the tag array and data array are decoupled (pointers and back pointers are needed). On a miss on a memory block, only the tag is allocated and the data is bypassed to the core. On the first (tag) reuse, i.e., hit on the tag array but miss on the data array, the data block is allocated on data array. Our experiments confirm that, in most cases, the Reuse cache achieves performance in the same range or higher as a 2X larger conventional cache. Unfortunately the Reuse cache also incurs very significant hardware overhead; ignoring the extra logic, the Reuse cache necessitates about 20% of extra storage than a conventional cache. With the Reuse cache, data blocks have three possible presence status, tag-only, tag+data, and invalid. The tag-only status allows to track the first use blocks that are not present in the data array.

In our experiments, with YACC, on average, 42% of the blocks sitting in the LLC are uncompressed, with the maximum being 90% (Fig. 3). This means that 42% of the superblock tags (that can map up to four contiguous blocks) represent one tag+data block state and 3 invalid block states. For a super-block with super-block tag (say SA) that contains one uncompressed block A2, the introduction of the presence status tag-only in YACC will allow to track the reuse property of its companion cache blocks (A0, A1 and A3).

In the next section, we present the FITFUB allocation policy for YACC. FITFUB exploits this extra presence status to (partially) filter the allocation of single use uncompressed blocks in the YACC cache.

FIRST IN THEN FIRST USE BYPASS ALLOCATION POLICY

We describe FITFUB policy as follows: On an LLC miss for a block Bi within a missing super-block B, a data entry and its associated super-block tag are allocated. On a subsequent miss on Bj in the same super-block B, and if the block cannot be co-compressed with Bi, the validity status associated with Bj is updated in the super-block tag as First-Use, but the data entry is not allocated. An additional data entry and its associated super-block tag location are allocated for this second block Bj, only if it gets reused before super-block B is evicted from the cache.

We detailed below the various access scenarios induced by the FITFUB policy on the YACC cache. For the sake of simplicity, we first describe the scenarios when all blocks are uncompressed (or not co-compressible), and then we generalize to the mix of uncompressed and compressed cache blocks.

Scenarios with uncompressed blocks

We consider in this section that all blocks in the super-block are uncompressible (or that they are not co-compressible). On YACC, four contiguous cache blocks A0, A1, A2 and A3 belonging to a 4-block super-block (say SA) are mapped to the same cache set. A super-block tag is associated with each data entry. Below are the different access cases (refer Figure 4):

Global miss on SA ( 1 ): On the access, if the super-block englobing the block, e.g. block A2 in super-block SA is missing then a super-block tag is allocated in the tag array. The data block is placed in the associated data entry. In the tag, the CS field (as mentioned in Figure 1) associated with the loaded block is marked as valid. The CS fields associated with the other blocks in the super-block are marked as invalid.

Hit on super-block tag, but requested block is invalid ( 2 ): When block A0 is accessed and if tag SA with block A2 valid is present, a hit is encountered on the tag array, but a miss on the data array (CS0 is invalid). Block A0 is marked as first-use in CS0 (meaning this is the first access to block A0), the block is forwarded to L2 cache and then to the processor. But it is not allocated in the data array.

Hit(s) on super-block tag, but request block is marked as first use block ( 3 ): On a subsequent access to block A0, a new super-block tag and its associated data block is allocated in the cache for A0. Its CS0 field is marked as valid. In the first tag associated with SA (that was allocated on the access of A2), the CS field is marked as invalid.

Multiple super-block tag hits, but request block is invalid ( 4 ): On an access to A3, the same process is repeated apart that on the first access, the CS3 field in both tags associated with A2 and A0 are set to first use.

Writeback at the LLC ( 5 ): On a writeback at the LLC, if the block is valid in the LLC, it is updated. Otherwise, on a full miss or a first use hit, the block is directly forwarded to the DRAM without modifying the LLC. The rationale of this policy is that multiple uses by the processor are, in practice read uses. In practice, we leverage the use of super-block tags to record the recent first use of blocks belonging to superblocks that have been recently touched: a single tag is able to record this information for four blocks of the super-block.

An extra coherence/validity state: FITFUB needs an additional state for cache blocks: the first-use state. For a noninclusive cache hierarchy, depending on whether the number of possible states allowed by the coherence protocol is power of two or not, this additional state can lead to an additional bit per block in the super-block.

Scenarios with compressible blocks

So far we have only considered un-compressible blocks. In this section, we describe few extensions for accommodating compressed blocks. The first type of modification corresponds to the cases 1 and 3 of Section 5.1: On a cache block allocation, if the block is compressible then it is stored as compressed block and the compressed bit is set in the super-block tag (refer 1 of Figure 5). The second type of modification corresponds to cases 2 and 4 of Section 5.1 where one needs to take into account that a data entry that contains one or more compressed blocks can still be completed with a missing block.

Hit on super-block tag, compressed bit is set, however block is present in invalid state: This scenario corresponds to the access to A0 with super-block tag SA when a valid block A2 is present in compressed form. In this case, if A0 is co-compressible3 with A2 then A0 is packed in the same data entry as A2 and marked as valid (refer 2 of Figure 5). However if the missing block is in-compressible (or not co-compressible) then it would be marked as first use, as illustrated for block A1 (refer 3 of Figure 5).

Hit on super-block tag, compressed bit is set, however block is in first use state: This corresponds to the case 4 in Figure 5. A1 was in first-use state and is reused so a dedicated data entry is allocated for it (general case). In the case where A1 has been modified since its first use (e.g a Write-Back) and has become co-compressible with A2, one can pack it in the already allocated entry.

Multiple super-block tag hits, at least one super-block tag has compressed bit set, however block is in invalid state. In this scenario, the block could potentially be cocompressible with several cache entries, one has to ensure that at most one copy of the block (in compressed format) is stored in the cache and the corresponding super-block tag correctly updated (refer 5a of Figure 5). If it can not be compacted then it is marked as first use in all super-block hitting tags (refer 5b of Figure 5).

The third type of modification corresponds to the writebacks. For most writebacks, the scenario is directly derived from the scenario on uncompressed blocks, i.e., we update the block in the cache if the data block is present and is cocompressible with the other co-located blocks in the LLC. If the block is marked as first use or is invalid then we directly write back the block into the DRAM.

However particular attention must be given to the case where the compressibility status of the block changes and becomes incompatible with the previous state. This arises when the block was compressible and co-located with one or more other blocks, and becomes in-compressible or not co-compressible with its companion blocks. In this case, the block is directly written back to the DRAM and invalidated in the LLC (refer 6 of Figure 5). The rationale is that, we find, in these cases more than 80% of the time the written back cache block do not get a reuse before its replacement. Techniques such as dead-write predictor [START_REF] Ahn | DASCA: Dead Write Prediction Assisted STT-RAM Cache Architecture[END_REF] can be used to improve the decision process for this event.

FITFUB, YACC and inclusive Cache Hierarchies

For inclusive cache hierarchies, the FITFUB allocation policy violates the inclusiveness by not allocating data entries at the LLC. To resolve this issue, we rely on the solution proposed for the Reuse cache, the tag-only (TO) status. So at the LLC, a coherence state can have two different variations: one in which data is present in the data array and one where only the tag is valid (corresponding to a first use). A coherence transaction on a block in TO state should be propagated to the caches closer to the processor. With the addition of a new state, there are two new coherence transitions that are possible: tag-only to tag+data and tag+data to tag-only. This incurs an additional overhead of 1 bit per cache block.

PERFORMANCE EVALUATION

We first evaluate the FITFUB allocation policy on YACC layout with compression turned off. For convenience, we refer this configuration as U-SRC. Then we evaluate the FITFUB allocation policy with YACC and DISH compression turned on. We refer to this configuration as the SRC cache. Our evaluation addresses the FITFUB allocation policy. Therefore, for all simulated caches on an insertion or a block hit, the block priority is updated as in SHiP++ [START_REF] Wu | SHiP: Signature-based Hit Predictor for High Performance Caching[END_REF].

Evaluation: Compression turned off

In this section, we evaluate the effectiveness of U-SRC and compare it with a baseline cache as well as the Reuse Cache [START_REF] Albericio | The Reuse Cache: Downsizing the Shared Last-level Cache[END_REF]. The Reuse cache is simulated as a reference point since it was essentially designed to capture the potential of bypassing first use prefetch blocks. Due to space limitation, we illustrate the results for single core only. Figure 6 and Figure 7 illustrate the improvement on LLC misses and execution time, respectively. U-SRC simulation results for multicores are illustrated in Figure 10 of Section 6.

The miss rates of the Reuse cache and U-SRC are very similar and this for all applications in our benchmark set. The miss rates are in many cases significantly lower than on the conventional cache confirming than bypassing first use blocks allows to keep useful multi-used blocks in the cache. Both the Reuse cache and U-SRC keeps information on multiple uses on a 4X larger size than the effective data array. The SHiP++ policy applied on the baseline does not have such information.

Note that, the improvement in miss rates does not translate in the same performance improvement on U-SRC as on the Reuse cache. Compared to the baseline uncompressed LLC, the Reuse cache improves the performance by 8.6% and U-SRC only captures 3 4 th of this potential, i.e, 6.5% performance improvement.

In practice, the misses encountered by U-SRC and the Reuse cache are not similar. U-SRC allocates a data entry on the first miss on 4-block super-block while the Reuse cache treats all blocks as equal. This translates in missed opportunities of bypassing for U-SRC, but also in extra misses for reused blocks on the Reuse cache. In our experiments, in most cases these two phenomena compensate approximately each other in terms of miss numbers. While the miss rates on the caches are similar, the access patterns on the main memory and the cost of the misses are different. The average cost of a miss on U-SRC is higher than on the Reuse cache. For instance, for a fully used super-block encountering multiple uses, the Reuse cache suffers two bursts of four misses, each burst generating 4 contiguous DRAM accesses, thus potentially benefiting from row locality. On the same sequence, U-SRC saves a low cost miss, but unfortunately statistically this low cost miss is replaced by a higher cost miss.

However, given the higher design complexity of the Reuse cache compared to a conventional cache design and U-SRC, in terms of storage overhead (about 20% storage overhead), and design complexity (tag array and data array are decoupled, and pointers and back pointers are needed), U-SRC (i.e YACC layout and FITFUB policy) appears as a cost-effective design point even for uncompressed LLCs.

Compression turned on

In this section, we evaluate the effectiveness of the SRC cache i.e YACC layout + FITFUB allocation policy with cache compression turned on. We compare it with the baseline compressed cache YACC. In both cases, we assume that the DISH compression scheme is used. We also compare SRC cache with an uncompressed Reuse cache, with U-SRC, with the conventional cache and a 4X sized conventional cache. DISH takes 24 and 1 cycles for compression and decompression, respectively. The access time to the cache is modelled through CACTI 6.5, therefore the access time of a 4X larger cache is longer than the one on the baseline cache.

Single-core Results: Fig. 8 illustrates the absolute MPKI numbers for an uncompressed baseline, U-SRC, YACC+DISH, 4X uncompressed LLC, and SRC. The SRC cache always encounters fewer misses than YACC and U-SRC. It even encounters fewer LLC misses than the 4X uncompressed baseline cache, except for mcf and bzip2. For many memoryintensive (high MPKI) applications such as mcf and lbm, the reduction is very significant with number of LLC misses reduced by more than 3X.

In several cases, the benefit comes essentially from compression e.g. sssp, apsp, and bzip2. In other cases, the benefit comes from FITFUB allocation policy e.g. libquantum, leslie3d, and bwaves. In many cases, the reduction in LLC misses comes from both the block allocation policy and the cache compression e.g lbm, soplex, and knn. Compared to YACC+DISH, SRC reduces the average miss rate (in terms of MPKI) from 3.2 to 1.1. This reduction induces a performance improvement as illustrated in Figure 9. On average, compared to an uncompressed baseline, SRC cache provides 12.7% of speedup (a maximum of 50% for xalancbmk) whereas a 4X uncompressed baseline, YACC+DISH, and U-SRC provide speedups of 10%, 8.3% and 6.5% respectively. SRC always outperforms both YACC+DISH and U-SRC, and on many benchmarks, the performance benefits of compression and allocation policy are nearly additive. Moreover, SRC cache outperforms 4X uncompressed baselines on most of the applications. A few points can be underlined. i) In a few cases, the 4X larger cache performs worse than other configurations despite similar (libquantum with U-SRC) or lower miss ratios (zeusmp with U-SRC). This was expected since our simulations assume a longer cache access latency for 4X larger cache.

ii) On average U-SRC provides less performance benefit than YACC+DISH despite a larger miss rate reduction. This can attributed to the difference of miss patterns that are induced by the FITFUB allocation policy, leading to less DRAM row access locality.

iii) For several benchmarks on which U-SRC is lagging in performance against the Reuse cache despite a similar or smaller miss rate, e.g freqmine, bfs, and ferret (see Figure 6 and 7), the same phenomenon occurs with SRC against the 4X cache, but with a smaller amplitude. Once again, this can attributed to the patterns of misses which result in less locality on DRAM row accesses in memory. However, the phenomenon is less pronounced than on the uncompressed cache since compressed blocks do no generate extra misses on the second use. iv) Among our benchmarks, bzip2 is a very particular case with the 4X cache reaching 77% of performance improvement. With the 4X cache, the working set of bzip2 almost fits in at the LLC. Moreover, the stream of misses exhibits poor locality, DRAM row hit rate is very low (less than 50 %), therefore the cost of each individual miss is very high.

Multi-core results: For 16-and 32-core systems, we use an LLC of 32MB and 64MB, respectively. All other shared resources are scaled as mentioned in Table 1. We divide the multi-core results into two types -multi-programmed and multi-threaded. For multi-programmed workloads, we provide the performance improvement for each of the classes (Hh, Hl, Lh, Ll) defined according to their sensitivity to cache size and their ratio of reused blocks (see Section 3). Fig. 10 illustrates the performance improvement for 200 multi-programmed workloads that span across four categories, and multi-threaded workloads. On average (geomean of weighted speedup) across 200 workloads, compared to an uncompressed baseline, SRC cache provides 17% improvement whereas uncompressed Reuse cache, U-SRC cache and 4X uncompressed baseline provide improvements of 9%, 8%, and 13%, respectively. Fair speedups are in the same range (refer Figure 11). We observe similar trends for multi-threaded applications.

In general SRC cache provides additional LLC space by not allocating data entries to non-reused blocks through helping the cache-sensitive applications of a workload mix. As expected, workload mixes of category Hh that contain cache sensitive applications and high proportions of single use blocks are the greatest benefactors of SRC cache. As also expected mixes such as Ll get more marginal benefits with SRC cache as the individual applications are less sensitive to an increase of the cache size.

SRC on inclusive Cache Hierarchies: So far, the evaluation has considered non-inclusive cache hierarchy. We also simulated a relaxed inclusive cache hierarchy using the tag-only state described in Section 5.3. On a relaxed inclusive cache, the effectiveness of SRC remains similar as observed for non-inclusive caches.

Energy consumption

Through reducing execution time, SRC reduces the energy consumption both in the cores and in the memory system. We focus our evaluation on the shared memory system including LLC, DRAM and compressor and de-compressor. Figure 12 illustrates the reduction in the energy consumption in the memory components (LLC and DRAM) allowed by the SRC cache for the multicore workloads. On average, SRC reduces the energy consumption by 17 % on both the DRAM and the LLC. However these similar average percentages cover different scenarios. For instance, on the PARSEC workloads, the benefit at the LLC is lower than on DRAM while on Ll workloads the energy benefit at the DRAM is much lower than the energy benefit at the cache. At the LLC, the additional static power required by SRC over the baseline configuration is marginal (roughly 2%), corresponding to the storage overhead. Therefore, on our benchmarks, the static energy consumption of SRC is about 13 % lower than the one of the conventional cache (1 -1.02 1.17 ≡ 13%). The savings on dynamic energy are slightly higher. They come from the substantial reduction of the number of misses, and also from the reduction of writes on the cache for data blocks that are bypassed to the L2 cache.

For DRAM energy, the savings are also slightly higher on dynamic consumption than on static consumption. The static energy reduction is proportional to the reduction of the execution time (1 -1 1.17 ≡ 15%). For the dynamic energy, the reduction comes essentially from the reduction of the number of accesses, and also on the change in the access patterns on the DRAM which improves the row buffer hit rate. Compression/Decompression: While energy is saved at the memory components (LLC and DRAM), additional energy is spent on compression/decompression. From our evaluation, energy for compressing a block with the DISH compression scheme is about 15% of the energy of a read access on the cache. Energy for decompressing a block is 3% of the energy for a read access. This leads to an overall compression/decompression energy in the 4% range of the overall LLC energy since i) all blocks in the LLC are not compressed and therefore not decompressed, ii) the blocks bypassed with the FITFUB policy do not flow through the compression hardware. Overall, the extra energy spent on compression/decompression is much smaller than energy saved at the memory system.

Sensitivity Studies

LLC size: To understand the effect of LLC size on SRC cache, we simulate multi-core systems with 1MB, 2MB and 4MB per core. Fig. 13 illustrates the average performance for different cache sizes for multicores. As expected, the performance benefit is higher for a small cache (1MB per core), but is still significant for the larger configuration (4MB per core).

Cache Replacement Policies: In our evaluation, SRC cache uses SHiP++ [START_REF] Wu | SHiP: Signature-based Hit Predictor for High Performance Caching[END_REF] as its underlying cache replacement policy. We study the effectiveness of SRC cache with different cache insertion/promotion priority policies such as not recently reused (NRR) [START_REF] Albericio | Exploiting Reuse Locality on Inclusive Shared Last-level Caches[END_REF], hawkeye [START_REF] Jain | Back to the Future: Leveraging Belady's Algorithm for Improved Cache Replacement[END_REF], and sampling dead-block predictor (SDBP) [START_REF] Manabi Khan | Sampling Dead Block Prediction for Last-Level Caches[END_REF]. Figure 14 illustrates the performance difference when we change the cache replacement policy. That is the column (SRC, NRR) illustrates the performance improvement of SRC with NRR over SRC with SHiP++. Similarly the column (baseline, hawkeye) illustrates the performance ratio of baseline with hawkeye over baseline with SHiP++. Overall, on our experimental set, the average performance difference between these replacement policies remains very small (< 2%) for all the cache structures. That is for all the tested policies, SRC outperforms the baseline configuration by 17% to 18%. This makes a strong case for using FITFUB as a block allocation policy. However LLC management policies answer two different different questions i) on a miss, whether the block will be allocated in the LLC? ii) which is the target for replacement ? The FITFUB allocation policy only answers to the first question and can be associated directly with most of the previously proposed LLC management policies to manage the YACC cache. There are many possible optimizations around FITFUB and optimizing the replacement target policy that could be explored. For instance, one could explore the priority level at which compressed blocks and uncompressed blocks should be inserted, one could explore the priority level at which compressed blocks and uncompressed blocks should be promoted on a hit, one can predict when not to bypass. All these optimizations might bring some additional performance gains on SRC, but are left for future work.

Compression Technique: So far, we have evaluated SRC cache with DISH technique. However, as SRC cache is independent of the underlying compression schemes, we evaluate SRC cache with BDI, CPACK+Z, and FPC compression techniques that use YACC layout. Compared to the baseline uncompressed cache, SRC cache that uses BDI, CPACK+Z and FPC provide performance improvements of 13.8%, 11.2% and 10.3%, respectively, on multi-core systems. Therefore, SRC cache is effective across different compression techniques providing high performance gain and energy savings. Unsurprisingly, DISH that was designed especially for the YACC cache layout, achieves the best performance improvement (17%).

RELATED WORK

To the best of our knowledge, this is the first study on replacement/insertion policy for compressed caches that associate a single super-block tag to a fixed data entry, i.e., YACC or SCC. LLC replacement policies for uncompressed caches and their possible adaptation to the SRC context have been previously discussed. On the other hand, there has been a limited number of studies on optimizing insertion/replacement policies for compressed caches. A few studies [START_REF] Baek | ECM: Effective Capacity Maximizer for high-performance compressed caching[END_REF][START_REF] Gaur | Base-victim Compression: An Opportunistic Cache Compression Architecture[END_REF][START_REF] Pekhimenko | Exploiting compressed block size as an indicator of future reuse[END_REF] address cache designs where a tag is not associated with a fixed data entry, or several tags are associated with a data entry.

ECM [START_REF] Baek | ECM: Effective Capacity Maximizer for high-performance compressed caching[END_REF] proposes size aware cache replacement policies by taking the compressed size of the cache blocks into account for evicting LLC blocks. CAMP [START_REF] Pekhimenko | Exploiting compressed block size as an indicator of future reuse[END_REF] outperforms size aware cache replacement policies by dynamically prioritizing cache blocks using their compressed block sizes. In the same direction, on SRC, one could prioritize promotion/insertion of data entries based on their compression status and/or on the number of valid compressed blocks in the data entry.

Gaur et al. [START_REF] Gaur | Base-victim Compression: An Opportunistic Cache Compression Architecture[END_REF] acknowledge that replacement decision is a nightmare on compressed caches with multiple tags associated with the same data entry. For a compressed cache allowing a maximum of two compressed blocks per data entry, they propose the base-victim compression cache. On the base-victim compression cache, a data entry stores a main block and possibly a victim block. The replacement policy only considers the main block. On a miss on block B as main block (either a real miss or a hit on a victim block), one allocates a data entry for block B, and one tries to keep the evicted main block (if compressible) as companion victim block with some main block. This elegant policy guarantees that the sequence of misses as main blocks is the same as the sequence of misses on an uncompressed cache with the same replacement policy.

CONCLUSION

To accommodate cache compression, the YACC [START_REF] Sardashti | Yet Another Compressed Cache: A Low-Cost Yet Effective Compressed Cache[END_REF] layout appears as a very promising solution, particularly when associated with an adapted compression scheme such as DISH [START_REF] Panda | Dictionary Sharing: An Efficient Cache Compression Scheme for Compressed Caches[END_REF]. It achieves significant performance improvement compared with a conventional cache design at a very limited storage overhead (1.5 %).

The structure of the YACC layout is very similar to the one of a conventional set-associative cache apart that that it associates a super-block tag with each data entry (aka line in the data array) instead of a block tag in order to map the co-compressible of a super-block in a single data entry. The performance of a cache also depends on its management and particularly on the decision of allocating in the LLC or bypassing blocks fetched from the memory. On YACC, the super-block tag offers us the opportunity to implement the FITFUB allocation and bypass policy. After a first uncompressed block from a super-block has been allocated in the cache, its super-block tag can be used to monitor the reuse usage of its companion blocks in the super-block. This allows to bypass these companion blocks on their first use, and store them (and allocate a data entry for them) only on the second use of the block. FITFUB can be implemented on top of any priority insertion/promotion policy for the cache.

Our experiments show that, the benefit from cache compression plus FITFUB is in the order of 12.7% and 17% for single core and multi-core workloads, respectively. These benefits also translate in energy savings on the memory system (LLC and DRAM).

As a global proposition, SRC appears as very cost effective design leveraging cache compression and an effective allocation and bypass policy at very limited hardware overhead: the compression/decompression logic and 1.5% storage overhead.

Figure 1 :

 1 Figure 1: YACC tag entries with different compression factors (CFs). CS:coherence states/V/I bits. SB: Superblock.

Figure 3 :

 3 Figure 3: Fraction of uncompressed LLC blocks.

Figure 4 :

 4 Figure 4: Different access scenarios with the U-SRC cache. FU is the first-use bit. A0 to A3 are the blocks of a super-block SA. For each access, we show the updated tag entries (after the access is serviced).

Figure 5 :

 5 Figure 5: FITFUB: Access scenarios for compressible blocks..

Figure 7 :

 7 Figure 7: Speedup normalized to an uncompressed baseline LLC.

Figure 9 :

 9 Figure 9: Speedup normalized to an uncompressed baseline LLC.

Figure 10 :

 10 Figure 10: Normalized system performance (weighted speedup) over an uncompressed baseline.

Figure 11 :

 11 Figure 11: Normalized system performance (fair speedup) over an uncompressed baseline.

Figure 12 :

 12 Figure 12: Improvement in memory sub-system energy normalized to uncompressed baseline.

Figure 13 :

 13 Figure 13: Effect of LLC size: Performance normalized to an uncompressed baseline for multi-core systems.

Figure 14 :

 14 Figure 14: Effect of cache management policies on SRC Cache: Normalized performance to the same cache structure that uses SHiP++. Results are for multi-core systems.

Table 1 :

 1 Parameters of the simulated system

	Processor		1/16/32-cores, 3.7 GHz, out of order
	L1 D/I, L2		32 KB (4 way), 256KB (8 way)
	Banked Shared L3		2/32/64 MB for 1/16/32 cores with 16
			ways, non-inclusive
	MSHRs		16/16/16 per core MSHRs at L1/L2/L3
	Line size		64B in L1, L2 and L3
	Cache Replacement policy	SHiP++ [31]
	Compressed Cache Layout	YACC [24]
	Compression Technique DISH [19]
	L2 prefetcher		Stream based [30], 32 streams with de-
			gree = 4 and distance = 32
	On-chip interconnect	Crossbar
	DRAM controller		1/4/8 controllers for 1/16/32-cores, Open
			Row, 64 read/write queues, FR-FCFS
	DRAM bus		split-transaction, 800 MHz, BL=8
	DRAM		DDR3 1600 MHz (11-11-11), Max band-
			width/channel -12.8 GB/sec
		Benchmarks		Types
	SPEC CPU 2006 [29] xalancbmk, bzip2, hmmer, soplex, mcf,	Sensitive-
		omnetpp, h264ref, cactusADM, lbm, gro-	positive
		macs, zeusmp		(SP)
		libquantum, milc, bwaves, namd,	Insensitive
		leslie3d, sjeng		(IN)
	PARSEC [8]	canneal, dedup, ferret, fluidanimate, fre-	Sensitive-
		qmine, vips		positive
					(SP)
		blackscholes, bodytrack, swaptions,	Insensitive
		facesim, streamcluster, x264	(IN)
	CRONO [1]	sssp, apsp			Sensitive-
					positive
					(SP)
		pagerank, community detection (com-	Insensitive
		munity), bfs, betweenness centrality (bc)	(IN)
	Machine Learning	sparse matrix vector multiplication	Sensitive-
		(spmv),	symmetric	Gauss-seidel	positive
		smoother (symgs)		(SP)
		locality sensitive hashing (lsh). stochas-	Insensitive
		tic gradient descent (sgd), K nearest	(IN)
		neighbor (knn)

Table 2 :

 2 Classification of benchmarks.

	from the region of interest for 2B instructions.
	Workload selection: Table 2 classifies 40 benchmarks from
	SPEC CPU 2006 [29] 2 , PARSEC

A super-block is an aligned and contiguous group of blocks (compressed and uncompressed) that use a single tag called super-block tag for all the blocks. For example, a 4-block super-block that contains four cache blocks share a single super-block tag.

In our gem5 set-up, only 17 SPEC applications run correctly. Seven applications do not run correctly with gem5 and the rest of the applications provide incorrect outputs.

The DISH compression scheme proposes two encoding schemes, and two blocks of a super-block can be stored in the same data entry only if they can be compressed with same encoding scheme[START_REF] Panda | Dictionary Sharing: An Efficient Cache Compression Scheme for Compressed Caches[END_REF]