Jinwook Jung
email: jinwookjung@kaist.ac.kr

Dongsoo Lee

Youngsoo Shin

Design and Optimization of Multiple-Mesh Clock Network

Keywords: Clock distribution, Clock mesh, Multiple-mesh clock network

A clock mesh, in which clock signals are shorted at mesh grid, is less susceptible to on-chip process variation, and so it has widely been studied recently for a clock network of smaller skew. A practical design may require more than one mesh primarily because of hierarchical clock gating architecture; a single mesh, however, can also support the same architecture after some hierarchies are removed but at the cost of gating efficiency. We experimentally compare multiple-and single-mesh using a few test circuits, and show that the former consumes smaller clock power (16.3%) but exhibits larger clock skew (10.2ps) and longer clock wirelength (21.7%). We continue to study how multiple meshes should be floorplanned on the layout, specifically whether or not we allow the overlaps among meshes. The choice is translated into different physical design strategy, and causes different amount of clock skew, critical path delay, clock wirelength, and clock power consumption, which we experimentally evaluate. We give at last the comparison of clock skew variation for each mesh implementation and clock tree, and show that floorplanning of multiple meshes helps to reduce the variation of clock skew.

Introduction

Big industrial designs such as SoCs and processors are often embedded with multiple levels of clock gating to efficiently reduce the power consumption of clock distribution network [START_REF] Shin | 28nm high-k metal-gate heterogeneous quad-core CPUs for high-performance and energy-efficient mobile application processor[END_REF][START_REF] Singh | Jaguar: a next-generation low-power x86-64 core[END_REF][START_REF] Xu | Low-power H.264/AVC baseline decoder for portable applications[END_REF]. Some clock gating is inserted by automatic CAD tools, e.g. by compiling load-enable registers into normal registers driven by clock gating cells (CGCs); designers may also insert clock gating in manual fashion, especially at module-or system-level, based on the knowledge of the usage scenario of a design [START_REF] Guthaus | Revisiting automated physical synthesis of high-performance clock networks[END_REF].

If the clock network of such a design is to be constructed using clock meshes to achieve lower clock skew, multiple meshes may be inserted as shown in Fig. 1. This is a natural choice in terms of power consumption because each mesh can be gated whenever the block it spans is not actively switching. Furthermore, it is

Multiple meshes

Mesh 1 Mesh 2 well known that mesh consumes more power than standard clock tree network [START_REF] Chinnery | High performance and low power design techniques for ASIC and custom in nanometer technologies[END_REF] due to more wire capacitance and excessive short-circuit current; a study indicates that 33.4% more power is consumed in comparison with the standard clock tree [START_REF]Cyclos: Clock design for SoCs with lower power and better specs[END_REF], so it helps to gate mesh whenever it is possible. A single big mesh, however, may be inserted instead after some clock gating hierarchies are removed, which is also illustrated in Fig. 1. This choice is not efficient in terms of power consumption, but it has the benefits of shorter design time because of its simpler structure, as well as shorter clock wires and more importantly smaller clock skew.

Non-overlapping meshes

In this paper, we quantitatively explore the two styles of mesh implementation, using some test circuits in 28-nm technology, which is the first contribution. When multiple meshes are employed, it is important to decide how to floorplan them. If overlaps between meshes are allowed, physical design can be done in flat. No overlap, on the other hand, implies hierarchical physical design. The two styles will have different impact on clock power, clock wirelength, clock skew, and timing closure, which we want to quantitatively assess; this constitutes the second contribution of the paper. The remainder of this paper is organized as follows. The basic mesh network structure and the steps to synthesize it are reviewed in Section 2; clock gating in multiple levels of hierarchy is also described. In Section 3, we address the procedures to design single-and multiple-mesh clock networks in the context of multi-level clock gating, and use some test circuits to experimentally assess the two implementation styles. Section 5 discusses the floorplan of multiple meshes and provides experimental evaluation. Section 6 gives the comparison of the three mesh implementations with the standard clock tree, and evaluates clock skew variation. Several related works are reviewed in Section 7, and we finally conclude the paper in Section 8.

Preliminaries

Clock Mesh Structure and Its Synthesis

Fig. 2 illustrates a structure of mesh clock network that we are concerned with in this paper. It consists of three main components: a premesh tree, a mesh grid, and a postmesh tree. Clock sinks are connected to the mesh through postmesh buffers and stub wires. A premesh tree can be a balanced H-tree or standard clock tree, and connects the mesh to the clock source. Leaf-stage buffers in the premesh tree will be called mesh drivers.

Fig. 3 illustrates the overall synthesis flow of a mesh clock network; we synthesize a mesh clock network in a bottom-up manner. Clock sinks are first grouped together based on their locations; maximum fanout of postmesh buffers, which are inserted and sized properly once the groups are formed, determines the group size. A mesh grid is constructed and connected to the postmesh buffers through stub wires; a grid structure is designated by the numbers of vertical and horizontal wires. It is determined in a way that minimum length of wires are used for mesh grid and stub wires. The pitch of grid wires that gives the mesh of the minimum wire length is calculated as [START_REF] Shim | Analysis and minimization of short-circuit current in mesh clock network[END_REF]:

p = 12 ρ , ( 1
)
where ρ denotes the density of the postmesh buffers in the placement area. Then we can determine the number of vertical wires m and horizontal wires n:

m = W p , n = H p , ( 2
)
where W and H are the width and height of the placement area, respectively. After the mesh grid construction, mesh drivers are placed at each grid location; they then serve as the sinks of premesh tree synthesis. Fig. 4: Clock gating in multiple levels.

Multi-level Clock Gating

Clock gating is a standard technique to reduce clock power. It is often applied in multiple levels, particularly in big industrial designs [START_REF] Shin | 28nm high-k metal-gate heterogeneous quad-core CPUs for high-performance and energy-efficient mobile application processor[END_REF][START_REF] Singh | Jaguar: a next-generation low-power x86-64 core[END_REF][START_REF] Xu | Low-power H.264/AVC baseline decoder for portable applications[END_REF][START_REF] Guthaus | Revisiting automated physical synthesis of high-performance clock networks[END_REF]. This is illustrated in Fig. 4. Register-level clock gating is mostly realized through automatic CAD tools, e.g. by replacing load-enable registers with clock gating cells (CGCs) and normal registers, and by employing XOR self-gating [START_REF] Ezroni | Advanced dynamic power reduction techniques: XOR self-gating[END_REF].

In addition, designers may explicitly instantiate CGCs at module level or system level (right after the clock source) according to the usage scenario of a chip. This type of clock gating gives the capability to turn off the clock signal of specific modules or entire systems, and shuts down a large portion of clock distribution network.

Mesh Clock Networks for Multi-level Clock Gating

A design of multiple level clock gating encounters the choice of mesh implementation styles as shown in Fig. 4. Specifically, a single big mesh may be inserted at system level (or at each clock domain) or more than one small meshes may be inserted with each mesh assigned to a module or to a group of registers. The two styles incur different clock power consumption, as well as different clock skew, wirelength, and design time, which we want to explore in this section.

Single-mesh Implementation

In this implementation, a single big mesh is inserted right after the system level clock gating of Fig. 4. The resulting clock network is shown in Fig. 5. To retain the advantage of smaller clock skew of mesh network, it is desirable to have short clock paths from mesh to each clock sink. But, multiple levels of clock gating after mesh (see Fig. 4) lend themselves to local clock trees with a few CGCs and buffers. The key therefore is to remove the hierarchy of clock gating so that Clock mesh CGC Fig. 5: Single mesh implementation of multi-level clock gating. the paths from mesh to clock sinks become shorter. The module-level CGCs are removed for this purpose; a new CGC is inserted to each group of registers that have directly been gated by a module-level CGC; a CGC that has been driven by module-level CGC is now gated by its original gating logic and the logic that has gated module-level CGC.

It is well known that mesh consumes more power than clock tree due to more wire capacitance and short-circuit current [START_REF] Chinnery | High performance and low power design techniques for ASIC and custom in nanometer technologies[END_REF][START_REF] Shim | Analysis and minimization of short-circuit current in mesh clock network[END_REF]. It is thus important to gate mesh as often as possible. A single big mesh, however, is gated less frequently, thus has disadvantage in power consumption. Balancing postmesh trees should be easier, which yields smaller skew. Test circuits will be used to assess these factors, as well as wirelength and design time.

The maximum fanout of newly inserted CGCs, which serve as postmesh buffers, may be increased to reduce the additional capacitance of mesh wires; from Equations 1 and 2, reducing the number of postmesh buffers results in fewer mesh grid segments. Therefore we can consider using a small number of postmesh buffers to cut down the power consumption of clock meshes. However, it leads us to choose postmesh trees containing multiple levels of buffers which incur additional clock skew, since the maximum transition constraint of clock signal may be violated without a buffered tree structure. We will see how the maximum fanout of newly inserted CGCs affects clock skew and power consumption of the single-mesh implementation later in this section.

Multiple-mesh Implementation

Another implementation of mesh is shown in Fig. 6. This time, a mesh is assigned to each module as well as to registers that have not belonged to any modules, which we call top-level registers. The initial clock network shown in Fig. 4 may be very unbalanced; in particular, the path from the clock source to top-level registers tends to be shorter. This is alleviated by inserting isolation taps, which have comparable delays to CGCs. If there are some modules without modulelevel clock gating, their clock sinks are also isolated by the isolation taps. Mesh Fig. 6: Multiple mesh implementation of multi-level clock gating.

drivers are inserted at each grid of meshes; they are then considered as sinks of premesh tree synthesis.

Since each mesh is gated at module-level, it can be gated more frequently, and leads to smaller power consumption. Clock skew can arise between different meshes as well as between different clock sinks under the same mesh; so skew is very likely to be larger than that in a single mesh implementation. Design complexity and wires will also increase.

Assessment

The design flow of mesh network synthesis for single-and multiple-mesh implementation has been implemented in Tcl, which runs on commercial placement and route tool; it is illustrated in Fig. 7. To determine the number of mesh wires in each implementation, we used Equation 2A few test circuits have been chosen from OpenCores [START_REF]OpenCores[END_REF]; the RTL description of each circuit has been modified to insert module-and system-level clock gating. A library of 28 nm industrial technology has been used to compile each circuit and to obtain a netlist. The last column of Table 1 corresponds to the number of meshes when clock is implemented as multiple meshes; the numbers of gates and flip-flops are also shown. Clock skew and power consumption have been measured using SPICE after parasitics are extracted from layout.

Comparison of Single-and Multiple-mesh Implementations

Single-and multiple-mesh implementations are compared in Table 2. Multiple meshes consume on average of 16.3% smaller power than single mesh. This has been expected because small multiple meshes are gated more often than a single big mesh; meshes are gated 78% of time in multiple meshes (on average of meshes, and on average of circuits), while a single mesh is gated 49% of time. Relatively small difference in power, considering the big difference in mesh gating probability, is due to more clock wires in multiple-mesh implementation as indicated in columns 5-7. Fig. 8 depicts how respective mesh grids of single-and multiplemesh networks are constructed in circuit ac97. Multiple meshes are placed as overlapped each other due to irregular module boundaries, causing the sum of mesh wires to be increased by 21.7% compared to single mesh on average of the circuits.

Clock skew is compared in the last three columns. It clearly shows the advantage of the single-mesh implementation of which clock skew is 10.2ps smaller than that of the multiple meshes on average, which also has been expected. Postmesh buffers are close to a mesh grid in the single-mesh while the stub wires of the multiple-mesh implementations becomes longer (see Fig. 8 (b)), which introduce additional clock skew due to the stub wire delay. Also, different meshes themselves contribute to clock skew in the multiple-mesh implementation due to the different latenciy from the clock source to each mesh (see Fig. 6). Fig. 9 compares the time elapsed for clock network synthesis. Multiple-mesh implementation takes 35.4% more time than single-mesh, on average. This is mainly due to the fact that designing mesh grid and postmesh trees has to be iterated in the multiple-mesh implementation. A circuit spi is an exception. It contains only two meshes in its multiple-mesh implementation; more times are spent in the postmesh tree synthesis of single-mesh implementation due to the large number of clock sinks (in consideration of circuit size).

Impact of Using Fewer Postmesh Buffers

We took the circuit ac97 and implemented two more single-mesh clock networks with two and four times bigger maximum fanouts of newly inserted CGCs, respectively, to see how reducing postmesh buffers affects clock skew and power consumption of the single-mesh implementation. The respective postmesh trees are now synthesized as 2-level and 3-level clock trees. The measured clock power, wirelength, and clock skew are summarized in Table 3 along with the results of single-and multiple-mesh implementations of the previous section.

Fig. 10 shows the clock mesh layouts. The number of grid segments are reduced due to the increased fanout of mesh grid; the clock wirelengths of the single-mesh network with 2-and 3-level postmesh trees are decreased by 3.3% and 8.7% compared to the original single-mesh implementation. It results in lower power consumption; the power consumption of the single-mesh implementation with 3-level postmesh is now close to the multiple-mesh implementation (see column 2 of Table 3). As the depth of postmesh trees becomes deeper, however, clock skew is increased; it is now even larger than the multiple-mesh implementation, and the benefit of using single-mesh implementation in terms of clock skew diminishes. Therefore, it is better to choose the multiple-mesh implementation over the single-mesh network with deeper-levels of postmesh trees for lower power consumption.

Choosing Mesh Implementation Style

Assessments in Section 3.3 indicate that a single big mesh has advantages over a multiple-mesh network in terms of clock skew. On the other hand, the multiplemesh implementation shows reduced power consumption due to the capability of shutting down a large portion of clock network; a low-power design may take multiple-mesh as the design strategy of choice.

Although our evaluation results show that all the test circuits taken for the assessments consume lower power in the multiple-mesh implementation, they also result in longer clock wirelengths. This fact implies the excessive metal resources may cause power overhead when gating probabilities of CGCs in a design are small. Here, let us briefly address the impact of gating probabilities in power consumptions. We took the circuit ac97 and generated SPICE netlist of singleand multiple mesh clock networks with parasitics extracted. To see how gating probabilities affect the power consumption, we controlled the enable signals arbitrarily and estimated power consumptions of different gating scenarios. Fig. 11 plots the difference of power consumption between two design options with respect to different gating probabilities; the difference is calculated by subtracting the power of single-mesh from that of multiple-mesh. If a circuit does not gate at all, a single big mesh consumes lower power due to shorter wirelength. As the gating probabilities become larger, multiple mesh implementation begins to have smaller power consumption. The difference of power consumption has the maximum at average gating probability of 0.8. As the gating probabilities are still more increased, the power advantage of multiple-mesh implementation begins to shrink; this is because system-level clock gating also has large gating probability in that case. Fig. 11: Difference in power consumption between two mesh implementations for ac97 with respect to gating probabilities.

XII

Switching capacitance estimation

The mesh implementation of choice depends on the gating probabilities in a design. It may raise the question of how we know which mesh network has a benefit of power consumption. If there is a method of estimating switching capacitance of two strategies, we can select the mesh network of lower power before mesh construction; power is proportional to switching capacitance as is well known.

Let ∆C be the difference of the total capacitances in single-and multiplemesh implementations. The following equation then allows us to select the suitable design strategy of mesh network before actual mesh construction:

∆C = k α s C m - ∀mi α i C i m , ( 3
)
where k is an empirical constant, α s and α i are the switching activities of systemand module-level clock gatings, C m is the capacitance of a single big mesh, m i is the ith mesh in multiple-mesh, and C i m denotes the capacitance of the ith mesh of multiple-mesh implementation.

The structure of a mesh and the area it spans can be known just after the placement stage. So we can calculate the capacitance involved in a mesh from Equation 2 and capacitance per unit length. Equation 3 expresses the difference in switching capacitance of mesh clock network between the single-and multiple-mesh implementations. To consider premesh tree capacitance, we multiply an empirical constant k (e.g., 1.75 for H-tree); the wirelength of premesh tree is almost proportional to the size of mesh grid, as shown in are relatively small, ∆C can be negative; the high gating probabilities will yield the positive value of ∆C. Therefore, we can evaluate the equation Equation 3and predict which implementation will have smaller power consumption without actually constructing the two mesh clock networks. We will not take up this matter further in this paper since our assessments in Section 3.3 show that gating probability is relatively high, and multiple-mesh is always better in terms of power consumption for the test circuits. Nevertheless, if the functional simulation at earlier design phase indicates that the design has smaller value of gating probability, designers may consider the adoption of singlemesh for lower power.

Floorplanning of Multiple Meshes

It has been shown in Section 3 that multiple mesh implementation has advantage in clock power even though it incurs longer clock wirelength and larger clock skew. In this section, we want to explore how multiple meshes can be floorplanned. Specifically, we may or may not allow the overlaps between meshes 1 as shown in Fig. 13. Note that the overlap does not cause the use of additional metal wires as illustrated in Fig. 14.

The choice of mesh floorplanning has significant implication in physical design process. Fig. 13(a) allows flat placement and routing, thus more flexibility in achieving timing closure even though more wires will be used for mesh grid; Fig. 13(b) on the other hand assumes hierarchical physical design which is associated with more design steps and less design flexibility, but with less usage of wires for mesh grid. We want to experimentally assess the two choices in terms of clock power, clock wirelength, clock skew, and critical path delay. 1 We wanted to compare single-and multiple-mesh implementation using the same placement, so overlap was allowed in Section 3.

Assessment

When overlap is allowed, placement is performed in flat. The region is identified from the location of flip-flops that belong to the same mesh, and mesh grid is constructed accordingly. The remaining steps of mesh network synthesis follow those of Section 3.2. For meshes without overlap, floorplanning is performed manually by referring to the relative locations of meshes with overlap (i.e. obtain Fig. 13(b) from Fig. 13(a)). We then assign a bounding box to all flip-flops and combinational gates that belong to the same mesh. Automatic placement is then performed with a set of bounding boxes as placement constraints, which is followed by mesh network synthesis. The two mesh floorplanning methods are compared in Table 4. Floorplanning without overlap yields smaller clock power (5.2% on average), which is mainly due to shorter clock wirelength (15.9% on average). A circuit usbf is an exception, i.e. clock power is not very different even with large difference in clock wirelength. Its meshes are not gated very often (28% of time); it consists of one big mesh and two small meshes, so large number of buffers are inserted to balance clock arrival time to three meshes, much more when overlap is not allowed. Clock skew becomes smaller when overlap is not allowed; it is reduced by 4.8ps on average. Meshes are smaller in this case (see Fig. 13), so mesh grid pitch also becomes smaller; the longest stub wire, which affects the skew, becomes shorter as a result.

We have also measured the critical path delay, which are reported in Table 5. It is clearly shorter when overlap is allowed (0.10ns), because placement is performed in flat with greater flexibility in meeting circuit timing. Fig. 15 illustrates how critical paths are identified in two mesh floorplans of the circuit usbf.

Comparison with Clock Tree

In this section, we compare the three mesh implementation styles, that we have covered, with the standard clock tree. We implemented a clock tree in each test circuit for this purpose using the commercial placement and route tool. Clock power, wirelength, and clock skew of the clock trees are reported in Table 6. Fig. 16 (a) shows the clock skew of each clock network (normalized to the clock of the clock tree). Compared to clock tree, a 39.7ps reduction of clock skew is achieved by adopting the single-mesh implementation. Two multiple meshes also significantly improve clock skew; 29.5ps and 34.3ps reductions are observed in multiple meshes with and without overlap, respectively. Note that the benefit of reducing clock skew by clock mesh grows as the number of clock sinks becomes larger; the divergence of clock paths increases, so the clock skew of a clock tree tends to increase. On the other hand, a large number of clock sinks share the clock path in a mesh clock network. Delay balancing between different meshes should be done for different meshes in the multiple-mesh implementation, but it is easier than in the clock tree since there are a few clock path to be balanced.

Power consumptions are also compared in Fig. 16 (b) (normalized to the single-mesh implementation). As is well known, clock trees shows less power consumption than mesh networks; it needs 29% less power than a single mesh on average. Multiple meshes can reduce this large power overhead of clock mesh; floorplanned multiple meshes consume only 8% larger power than clock tree.

Clock Skew Variation

We generated the SPICE netlists of the three mesh implementations and a clock tree from the circuit ac97 with parasitics extracted, and conducted Monte Carlo simulation of 1,000 samples to evaluate clock skew variation. We obtained the arrival times of all clock sinks, and calculated the global clock skew by subtracting the minimum arrival time from the maximum arrival time. Fig. 17 shows the histogram of the clock skew for each clock network. Singlemesh network and clock tree show the smallest and the largest clock skew variations, respectively. Multiple-mesh implementation with mesh overlap is affected on-chip variation more than multiple meshes without overlap. It is due to its longer latency; a mesh network of overlapped multiple meshes has longer wirelength and thereby more wire capacitance, so it shows larger clock latency than floorplaned meshes. Floorplanning the multiple meshes reduces the clock wirelength, so it can reduce the clock skew variation.

Related Work

There have been various studies concerning mesh clock network, particularly on the reduction of its excessive power consumption. A representative method is to reduce the wire usage of a mesh clock network thereby the wire capacitance. Such approach can be divided into two big categories; one is the reduction of unnecessary mesh grid segments [START_REF] Rajaram | MeshWorks: A comprehensive framework for optimized clock mesh network synthesis[END_REF], and another approach is the shortening the stub wires by moving clock sinks or grid wires [START_REF] Lu | Integrated clock mesh synthesis with incremental register placement[END_REF][START_REF] Guthaus | Non-uniform clock mesh optimization with linear programming buffer insertion[END_REF]. Short circuit current is also an important source of power consumption in mesh clock network, so several researches have proposed dedicated mesh driver to cut off the short circuit current [START_REF] Shim | Analysis and minimization of short-circuit current in mesh clock network[END_REF]. However, there are few studies on mesh network design considering the clock gating although it is a pervasive technique to reduce clocking power. Lu et al. proposed a mesh clock network with several gated local trees [START_REF] Lu | Clock mesh synthesis with gated local trees and activity driven register clustering[END_REF]. They grouped FFs in the same grid after the mesh grid construction, and extracted gating function from the FF group. However, there is the limit to extract gating functions from only the adjacent FFs in the same grid box. Also, their methodology is impractical since in most cases the clock gating structure is defined before the placement stage. Wilke and Reis [START_REF] Wilke | Design and analysis of "tree+local meshes" clock architecture[END_REF] compared clock skew and power consumption of a multiple-mesh network with a single-mesh network. They concluded that although the former has greater power consumption and larger clock skew, clock gating can be adopted to reduce power consumption, in that the multiple meshes becomes more power efficient solution. But they did not use the actual clock gated circuits for their assessments, and the multi-level clock gating structure covered in our study was not also considered.

In [START_REF] Jung | Design and optimization of multiple-mesh clock network[END_REF], which is the preliminary version of this paper, Jung et al. in the first time consider practical multi-level clock gating structure in the design of the single-mesh and multiple-mesh network. They presented the comparison of the two mesh networks, and showed that the multiple-mesh network consumes lower power while the single-mesh has the advantages in clock skew and design complexity. It is also presented that the floorplanning of multiple meshes can be used to reduce the power consumption of multiple meshes at the cost of critical path delay.

Conclusion

The clock network of a design with hierarchical clock gating can be implemented by a set of meshes. If some hierarchies are removed, however, it also can be implemented by a single big mesh. We have shown that multiple-mesh implementation has advantage in clock power (16.2% smaller power on average of test circuits); but single mesh consumes shorter clock wires, yields smaller clock skew, and takes less time to design.

Multiple meshes can be floorplanned with some overlaps if placement is performed in flat, or they can be floorplanned without overlap if hierarchical physical design is assumed. The experiments have shown that the mesh floorplan with overlap yields smaller clock power owing to shorter clock wires, smaller clock skew, and more variation tolerance, but timing closure is easier if overlap are not allowed.

Fig. 1 :

 1 Fig. 1: Design of mesh clock network for multi-level clock gating.

Fig. 2 :

 2 Fig. 2: Mesh clock network.

Fig. 3 :

 3 Fig. 3: Mesh clock network synthesis: (a) postmesh buffer insertion, (b) mesh grid construction, (c) mesh driver insertion, and (d) premesh tree synthesis.

Fig. 7 :

 7 Fig. 7: Design flow of mesh network synthesis.

Fig. 8 :

 8 Fig. 8: Layouts of (a) single-and (b) multiple-mesh implementations for circuit ac97.

Fig. 9 :

 9 Fig. 9: Comparison of design time.

Fig. 10 :

 10 Fig. 10: Layouts of single-mesh networks of different postmesh structures.

Fig. 12 .Fig. 12 :

 1212 Fig. 12: Estimation of k value for H-tree premesh.

Fig. 13 :Fig. 14 :

 1314 Fig. 13: Floorplanning of multiple meshes: (a) with overlap and (b) without overlap.

Fig. 15 :

 15 Fig. 15: Critical paths in usbf: (a) meshes with overlap and (b) meshes without overlap.

Fig. 16 :

 16 Fig. 16: (a) Normalized clock skew and (b) clock power.

Table 1 :

 1 Test circuits

	Circuits	# Gates	# FFs	# Meshes
	ac97	3225	1067	4
	mc	6211	1069	3
	usbf	7647	1736	3
	pci	11142	3206	4
	sdc	11815	3760	5
	spi	13964	4656	2
	des3	63217	8811	4
	fft64	71263	15996	4
	Single mesh	Placement	Multiple mesh
	RemoveNmodule-levelN clockNgating		InsertNisolationNtaps
	GroupNungated registersN	GroupNungated registersN
	InsertNpostmesh buffers		InsertNpostmesh buffers
	andNbalanceNpostmesh		andNbalanceNpostmesh
	ConstructNmeshNgrid		ConstructNmeshNgrid
	InsertNmeshNdrivers		InsertNmeshNdrivers
	SynthesizeNpremesh tree	SynthesizeNpremesh tree
			MoreNmeshes?	Yes
			No
		Routing

Table 2 :

 2 Comparison of single-and multiple-mesh implementation

		Clock power (mW)	Clock wirelength (mm)	Clock skew (ps)
	Circuits	Single	Multiple	Diff. (%)	Single	Multiple	Diff. (%)	Single	Multiple	Diff. (ps)
	ac97	0.52	0.43	17.1	5.5	6.6	-20.0	13.5	26.6	-13.1
	mc	0.18	0.15	18.2	4.8	6.3	-31.7	13.4	20.9	-7.5
	usbf	0.89	0.85	10.0	7.6	10.0	-31.8	11.8	27.0	-15.2
	pci	0.50	0.45	11.8	13.9	17.8	-28.7	13.4	26.1	-12.7
	sdc	0.45	0.32	28.2	14.3	17.6	-23.6	14.0	23.3	-9.3
	spi	0.84	0.62	26.1	18.3	20.2	-10.8	12.5	19.6	-7.0
	des3	2.95	2.55	13.6	38.2	45.5	-19.4	14.0	24.5	-10.5
	fft64	1.74	1.55	10.9	62.6	67.7	-8.0	19.8	26.0	-6.2
	Average			16.3			-21.7			-10.2

Table 3 :

 3 Experimental results for various postmesh trees of ac97

	Scheme	Clock power (mW) Clock wirelength (mm) Clock skew (ps)
	Single	0.52	5.5	13.5
	w/ 2-level postmesh	0.47	5.3	33.1
	w/ 3-level postmesh	0.43	5.0	51.3
	Multiple	0.43	6.6	30.6

Table 4 :

 4 Comparison of overlapping and non-overlapping meshes

		Clock power (mW)		Clock wirelength (mm)	Clock skew (ps)
	Circuits Overlap No overlap Diff (%) Overlap No overlap Diff. (%) Overlap No overlap Diff. (ps)
	ac97	0.43	0.43	1.1	6.6	5.8	11.1	26.6	18.3	8.3
	mc	0.15	0.13	12.0	6.3	4.8	24.0	20.9	20.1	0.7
	usbf	0.85	0.83	2.4	10.0	7.6	23.4	27.0	25.5	1.5
	pci	0.45	0.39	12.8	17.8	14.0	21.4	26.1	20.0	6.1
	sdc	0.32	0.31	3.5	17.6	14.9	15.8	23.3	20.6	2.7
	spi	0.62	0.60	4.1	20.2	18.1	10.5	19.6	13.4	6.2
	des3	2.55	2.50	1.8	45.5	38.1	16.2	24.5	16.3	8.2
	fft64	1.55	1.48	4.2	67.7	64.1	5.3	26.0	21.6	4.4
	Average			5.2			15.9			4.8

Table 5 :

 5 Critical path delays of multiple mesh designs

	Circuits	Overlap (ns) No overlap (ns) Diff. (ns)
	ac97	1.70	1.72	-0.01
	mc	3.18	3.21	-0.03
	usbf	2.12	2.30	-0.18
	pci	2.59	2.70	-0.11
	sdc	2.67	2.77	-0.10
	spi	2.70	2.82	-0.11
	des3	2.43	2.46	-0.03
	fft64	3.84	4.07	-0.23
	Average			-0.10

Table 6 :

 6 Experimental results of clock trees

	Circuits Clock power (mW) Clock wirelength (mm) Clock skew (ps)
	ac97	0.37	4.5	32.2
	mc	0.13	4.2	39.9
	usbf	0.74	7.1	52.6
	pci	0.34	12.4	53.6
	sdc	0.31	12.2	58.3
	spi	0.57	15.6	54.4
	des	2.33	31.9	69.6
	fft64	1.22	54.8	69.2


Dongwoo Lee
email: dongwoolee@dal.snu.ac.kr

Kiyoung Choi
email: kchoi@snu.ac.kr

Energy-Efficient Partitioning of Hybrid Caches in Multi-Core Architecture

Keywords: Spin-Transfer Torque RAM (STT-RAM), hybrid caches, cache partitioning

This chapter presents a technique for reducing energy consumed by hybrid caches that have both SRAM and STT-RAM (Spin-Transfer Torque RAM) in multi-core architecture. It is based on dynamic way partitioning of the SRAM cache as well as the STT-RAM cache. Each core is allocated with a specific number of ways consisting of SRAM ways and STT-RAM ways. Then a cache miss fills the corresponding block in the SRAM or STT-RAM region based on an existing technique called read-write aware region-based hybrid cache architecture. Thus, when a store operation from a core causes an L2 cache miss (store miss), the block is assigned to the SRAM cache. When a load operation from a core causes an L2 cache miss (load miss) and thus causes a block fill, the block is assigned to the STT-RAM cache. However, if all the allocated ways are already placed in the SRAM, then the block fill is done into the SRAM regardless of store or load miss. The partitioning decision is updated periodically. We further improve our technique by adopting the so called allocation switching technique to avoid too much unbalanced use of SRAM or STT-RAM. Simulation results show that the proposed technique improves the performance of the multi-core architecture and significantly reduces energy consumption in the hybrid caches compared to the state-of-the-art migration-based hybrid cache management.

Introduction

Non-volatile memories such as Spin-Transfer Torque RAM (STT-RAM) have been researched as alternatives to SRAMs due to their low static power consumption and high density. Among such memories, STT-RAM has a relatively high endurance compared to other memories and thus it is regarded as the best candidate for substituting SRAM used in last-level shared caches in modern chip multi-processors. [START_REF] Apalkov | Spin-transfer torque magnetic random access memory (stt-mram)[END_REF] However, STT-RAM has asymmetric characteristics of read and write. Writing into STT-RAM consumes significantly larger energy and takes more time than reading. Such characteristics can significantly increase energy consumption and degrade performance of the system if the program running on the processor cores need frequent writes into the shared cache. To mitigate the adverse effect of the characteristics of STT-RAM, many methods are proposed [START_REF] Ahn | Write intensity prediction for energy-efficient nonvolatile caches[END_REF][START_REF] Chen | Static and dynamic co-optimizations for blocks mapping in hybrid caches[END_REF][START_REF] Li | Stt-ram based energy-efficiency hybrid cache for cmps[END_REF][START_REF] Li | A software approach for combating asymmetries of non-volatile memories[END_REF][START_REF] Wu | Hybrid cache architecture with disparate memory technologies[END_REF][START_REF] Wu | Power and performance of readwrite aware hybrid caches with non-volatile memories[END_REF] on hybrid caches, where a small SRAM cache is combined with a large STT-RAM cache. In the hybrid caches, a block that is expected to be written frequently is placed in the SRAM cache, which has much lower write overhead compared to STT-RAM. So, in the hybrid cache approaches, where to place a block between SRAM and STT-RAM is one of the most important issues in reducing energy consumption and enhancing performance.

Fig. 1. shows that block fill on a read miss is one major source of write operations into a cache. So reducing the number of block fills is another method of lowering dynamic energy consumption of hybrid caches. A cache partitioning technique is developed to increase the performance of chip multi-processors by dynamically partitioning ways of the cache such that the number of misses is minimized and consequently the number of block fills is reduced. So the application of cache partitioning has great potential of reducing the dynamic energy consumption of the hybrid caches. However, conventional cache way partitioning techniques cannot be applied to hybrid caches directly, because ways in the hybrid caches are separated into SRAM and STT-SRAM and thus ways assigned to a core as a result of partitioning also should be divided into SRAM and STT-RAM. Properly dividing the ways of a partition into the two caches and placing a block into a more efficient cache are new challenging issues when applying a partitioning technique to hybrid caches. This chapter proposes a technique that adopts the cache partitioning scheme in a hybrid cache for reducing the energy consumption. We assume that the hybrid cache is a last-level shared cache in multi-core architecture. A conventional partitioning technique called utility-based partitioning is used to determine the sizes of the partitions, one for each core, such that the number of misses is minimized. To incorporate the technique into hybrid caches, the replacement policy should be redesigned. When a store operation of a core causes a miss in the shared cache, the corresponding new block is placed in SRAM. If all the allocated ways in the SRAM are already in use, a victim is selected among them. In the case of a load miss, the block is placed in STT-RAM if there is an unused way among those allocated to the core. If all the allocated ways in the STT-RAM are full, a victim block is selected. However, if all the ways allocated to the core have already been assigned to SRAM, a victim is selected among these blocks in SRAM. So, within a partition, the ratio between SRAM ways and STT-RAM ways can be adjusted and the ratio can be adjusted differently for different sets. Simulation results show that our techniques improve the performance of a quad-core system by 4.9%, reduce the energy consumption of hybrid caches by 10.0%, and decrease the DRAM energy by 5.9% compared to the state-of-the-art migration based hybrid cache management technique.

In the above scheme, it is possible that cache accesses are concentrated to either SRAM or STT-RAM so that the partitioning decision does not fully apply to hybrid caches. We resolve this situation by switching an allocation policy of load and store miss with small constant probability. Thus, within the small constant probability, the block allocation on a load miss is done as if it were a store miss and vice versa. This switching technique, which we call allocation switching technique, further improves the performance of a multi-core system by 1.8% (6.7% in total), and reduces the energy consumption by 6.6% (16.6% in total), and DRAM energy by 1.6% (7.5% in total). This chapter is organized as follows. Section 2 explains the background of STT-RAM technology, hybrid caches, and partitioning techniques. Section 3 describes the details of our proposed technique that exploits partitioning scheme for hybrid caches. Section 4 shows the evaluation methodology and Section 5 discusses the results of evaluation. Section 6 summarizes the survey of the related work and Section 7 concludes this chapter.

Background

STT-RAM Technology

Spin-Transfer Torque RAM (STT-RAM) is an emerging memory technology, which uses a Magnetic Tunnel Junction (MTJ) as an information carrier. The MTJ consists of two ferromagnetic layers and one tunnel barrier between them as shown in Fig. 2. The reference layer has a fixed direction of magnetic flow and the free layer can change its magnetic direction when a spin-polarized current flows through the MTJ with intensity above a threshold. If the directions of the two layers are in parallel, the MTJ has resistance lower than that of anti-parallel case. Thus, by measuring the voltage difference across the MTJ with a small current flow, the state of MTJ can be detected. Because of its non-volatility, STT-RAM has a very low leakage current. For read operations, it requires energy and latency comparable to SRAM, but in case of write operations, it consumes much higher energy and takes much longer than SRAM. Other noticeable properties of STT-RAM are its high endurance compared to other non-volatile memories such as Phase Change RAM (PRAM) or Resistive RAM (ReRAM) and its high density compared to SRAM.

Hybrid Approach for Last-Level Caches

Unlike other emerging non-volatile memories targeting off-chip storage, STT-RAM is expected to replace SRAM used for current last-level caches (LLCs) in chip multi-processors mainly due to its fast read latency close to that of SRAM and high endurance. But its high overhead of write operation obstructs the use of pure STT-RAM LLCs. To mitigate the shortcoming, there have been researches on hybrid caches that combine a small sized SRAM cache with a large sized STT-RAM cache, which lowers the write overhead of STT-RAM significantly. These two different caches are usually combined by a region-based manner. The two memories are placed at a same level of cache hierarchy and share tags of the caches. Ways are divided into the SRAM and the STT-RAM region and consequently, block placement becomes an important issue. it will be more efficient to place blocks that will be frequently written in SRAM and place others in STT-RAM. One of the state-of-the-art techniques is the read-write aware hybrid cache architecture [START_REF] Wu | Power and performance of readwrite aware hybrid caches with non-volatile memories[END_REF], in which a block fill caused by a store miss is made to a writeefficient SRAM region and a block fill caused by a load miss is made to a readefficient STT-RAM region based on the assumption that a block filled by a store miss is prone to frequent write and a block filled by a load miss is prone to frequent read. If there are consecutive hits on a block in a way opposite to the initial assumption, the block is migrated to the other region.

Cache Partitioning Technique

The utility-based cache partitioning technique is proposed to improve the performance of chip multiprocessors by minimizing the number of misses on a shared cache [START_REF] Qureshi | Utility-based cache partitioning: A low-overhead, highperformance, runtime mechanism to partition shared caches[END_REF]. It has the same number of Utility-MONitors (UMONs) and CPU cores. A UMON consists of an Auxiliary Tag Directory (ATD) and counters for measuring the number of hits for each position of LRU stack by observing the access of sampled sets in a cache. The algorithm periodically calculates the partition size of each core to maximize the number of hits in the cache. Bits are added to cache tags to identify the core that owns the block. The replacement policy gradually adjusts the size (number of ways) of each partition to the calculated size. The partitioning technique is especially efficient when cache insensitive (e.g., low hit rate) applications and cache sensitive ones are running at the same time on a multi-core processor. It tends to restrict the cache usage of the low hit-rate applications, while increasing the performance of other cache sensitive ones.

Partitioning technique for hybrid caches

This section explains the details of our technique proposed in [START_REF] Lee | Energy-efficient partitioning of hybrid caches in multi-core architecture[END_REF], which exploits the partitioning technique to reduce the energy consumption of hybrid caches in a multi-core processor. It also describes the extended work on the allocation switching technique to mitigate too much concentration on SRAM or STT-RAM.

Motivation

Read access of the last-level shared cache comes from a load or store miss of the upper level cache. In the case of store miss, a block written into the upper level cache becomes dirty, and so it eventually causes a write-back to the shared cache. Write access of the last-level cache can be classified into a write-back from the upper-level cache and a block-fill on a read miss. A read-write aware hybrid cache [START_REF] Wu | Power and performance of readwrite aware hybrid caches with non-volatile memories[END_REF] utilizes the property of read access. If a read miss on the shared cache is caused by a store miss of the upper level cache (store miss), the new block is placed in SRAM so that a write-back to that block occurs in the write-efficient region. In case of a read miss caused by a load miss of the upper level cache (load miss), the block is placed in STT-RAM where read operations are efficient. If the decision is wrong, migration from one cache to the other occurs to remedy the situation. However, this technique does not consider the block-fill caused by a read miss in the shared cache and a write-back to a block (in the shared cache) that was originally loaded by a load miss of the upper level cache.

We propose a technique for hybrid caches that handles these cases by exploiting the advantage of a dynamic cache partitioning technique. The dynamic partitioning scheme adjusts the sizes of partitions such that the total number of misses in the shared cache is minimized. Thus it helps reduce the number of block-fills caused by read misses. In case that the number of SRAM ways used by a core is already greater than1 or equal to that allocated to the core, a new block loaded into the LLC due to a miss is placed in the SRAM even if the miss is a load miss. The rationale is that utilizing the already allocated SRAM ways helps reducing energy and latency since subsequent write-backs to the block can be done in SRAM.

Architecture

Fig. 3 shows a structure to implement our technique. Basically, it combines a cache partitioning architecture with hybrid caches. For a dynamic cache partitioning technique, it has a set of UMONs that sample cache accesses to designated sets of the cache and count the number of hits on each position of an LRU stack. It periodically calculates the partition size of the cache for each of the multiple cores such that the total number of misses in the cache is minimized. It is done by using the values of hit counters collected by the UMONs during the previous period. In the cache tags, bits are added per block to identify the core that owns the block.

The last-level shared cache consists of SRAM and STT-RAM. Thus the data array is a hybrid of the two memories, but the tags are made of SRAM only. Ways of a set are divided unevenly; SRAM contains a smaller number of ways and STT-RAM covers the rest. When a new block needs to be placed in hybrid caches, the result of the partitioning technique is used to decide the type of caches for allocation and select a victim block in the resulting type of cache as explained in the following section.

For simplicity, we assume that an independent application runs on each core in a multi-core architecture, so a UMON is attached to each core. However, the technique can also be applied in a per-application manner. In that case, the UMONs are required as many times as the number of applications running on the architecture.

Replacement Policy

To maximize the effect of applying a partitioning technique to hybrid caches, where to insert a new block should be carefully decided. If a core performs a store operation and eventually causes a miss in the shared cache, SRAM in the shared cache is selected as a location to place a new block because the block allocated in the upper level cache will become dirty, and thus there will be a write-back into the LLC. The victim selection policy within the SRAM is changed from the traditional LRU policy to a more complicated one that involves partitioning decision.

Let us define several notations as follows. -N S (i, j): the number of SRAM blocks currently in use by core i in set j.

Cache

-N M (i, j): the number of STT-RAM blocks currently in use by core i in set j.

-N U T (i): the total number of ways allocated to core i by the partitioning.

-N U M (i, j) = N U T (i) -N S (i, j): the maximum number of ways that can be allocated to core i in set j of STT-RAM.

If N S (i, j) ≥ N U T (i), then the LRU among these blocks is chosen as a victim. If N S (i, j) < N U T (i), the LRU among all blocks in SRAM is selected as a victim. This modification is to better utilize SRAM ways which is relatively smaller than STT-RAM ways.

If a miss in the shared cache is caused by a load miss in the upper level cache, the new block can be placed either in SRAM or in STT-RAM. If N S (i, j) ≥ N U T (i), the LRU among them is chosen as a victim. This decision procedure is exactly the same as that of the store miss case. It allows using already allocated SRAM ways and avoids unnecessary overhead of allocating a new way in STT-RAM. And by placing the block into the SRAM, the block-fill due to the read miss is done in the write-efficient region, reducing the dynamic energy of caches without performance degradation of multi-core processors.

If N S (i, j) < N U T (i), the new block is placed in STT-RAM. The total number of blocks in a set of both caches is maintained not to exceed N U T (i), and thus N M (i, j) is maintained not to exceed N U M (i, j). Therefore, N M (i, j) is adjusted dynamically according to the change of N S (i, j) and/or N T (i). For example, if N M (i, j) becomes larger than N U M (i, j) due to a new partitioning, the LRU among the STT-RAM blocks owned by core i is selected to be replaced by a new block of another core. If N M (i, j) < N U M (i, j), the LRU of blocks owned by other cores is chosen as a victim. Contrary to the utility-based partitioning, our approach allows a zero value for N U M (i, j), and thus we allow to select the LRU of blocks allocated by other cores in the STT-RAM is chosen as a victim when there is no existing block in the STT-RAM owned by the core that requests the new block.

In this replacement policy, new blocks introduced by store misses can be placed only in SRAM, but new blocks introduced by load misses can be placed either in SRAM or in STT-RAM so that the utilization of the SRAM region can be maintained relatively high. The ratio between N S (i, j) and N M (i, j) can be adjusted freely under the constraint given by N S (i, j) + N M (i, j) ≤ N U T (i), which results in a decrease of the total misses in hybrid caches.

Allocation switching technique

In the above replacement policy, it is possible that too many block-fills are guided into either SRAM or STT-RAM, in which case, the partitioning decision cannot be properly applied to hybrid caches. For example, if there is an application that has a large number of load misses and no store miss, then a cache block of this application cannot be allocated to the SRAM. Similarly, if there is an application that has plenty of store misses and rare load misses, then a cache block of this application cannot be allocated to STT-RAM. If such applications are cache-size sensitive, then the partitioning decision of the applications cannot be applied to hybrid caches properly.

To resolve this situation, we devise an allocation switching technique where a block allocation on a load miss is done as if there were a store miss and vice versa within a small constant probability. By applying this switching technique, the concentration on either SRAM or STT-RAM can be relaxed.

The allocation switching technique works as follows. Consider the case where most of the misses occurring during the execution of an application are load misses. Then the application will put most of its blocks in the STT-RAM region even if some extra ways allocated to the application (or core) are in SRAM, making the STT-RAM crowded. It may not be able to move the extra ways in the SRAM to the STT-RAM side since other cores are already taking the STT-RAM space. In that case, it will be beneficial to place new blocks into the extra SRAM ways. Thus, sometimes on a load miss, placing the corresponding block into the SRAM region instead of the STT-RAM region helps alleviating the congestion in the STT-RAM region.

We set the probability of such allocation switching to a small constant value obtained empirically. But there is still room for further research on adjusting the probability value dynamically to achieve even higher performance because the characteristics of applications are very different. This section describes the experimental setup and methodology used to evaluate our hybrid cache partitioning technique.

Simulator

We evaluate our cache partitioning technique using a cycle accurate simulator MARSSx86 [START_REF] Patel | Marss: A full system simulator for multicore x86 cpus[END_REF]. For off-chip memory model, we use DRAMSim2 simulator [START_REF] Rosenfeld | Dramsim2: A cycle accurate memory system simulator[END_REF], which is integrated into MARSSx86. The details of our system configuration are listed in Table 1. The system has a 3.0 GHz, quad-core out-of-order processor based on x86 ISA. The cache hierarchy is configured with 32KB, 4-way set-associative L1 instruction/data caches and 4MB, 16-way set-associative L2 shared caches. We implement the shared L2 hybrid cache with a bank contention model. The L2 cache is a 16-way set associative cache consisting of 4 ways of SRAM and 12 ways of STT-RAM with asymmetric read/write latency. The offchip DRAM is configured as a DDR3-1333 in which CL, tRCD, tRP timings are 10, 10, and 10, respectively.

The parameters of the hybrid cache model are calculated using NVSim [4] and CACTI 6.0 [START_REF] Muralimanohar | Cacti 6.0: A tool to model large caches[END_REF] under 45 nm technology. A tag of 16-way 4MB SRAM is borrowed for hybrid caches. 4-way 1MB SRAM and 4-way 1MB STT-RAM is configured for the data array. By combining one SRAM bank and three banks of STT-RAM, 16-way 4-bank data array is designed for the hybrid cache. Table 2 lists the energy consumption of the L2 cache.

Workloads

We use SPEC 2006 [START_REF] Henning | Spec cpu2006 benchmark descriptions[END_REF] with reference input as workloads for the evaluation. For more precise analysis, the simulation method is changed from the work in [START_REF] Lee | Energy-efficient partitioning of hybrid caches in multi-core architecture[END_REF] where 10 billion instructions were fast-forwarded per core to skip the initialization phase of code and multi-core workloads were mixed with high and low-MPKI applications. In the simulation of this chapter, we annotate a synchronization point in the program source code after some initialization code part. As a result, a multi-core simulation always starts at the same points of benchmarks in the MARSSx86 simulator. Because of this modification, the simulation region of a benchmark can be different from that in [START_REF] Lee | Energy-efficient partitioning of hybrid caches in multi-core architecture[END_REF].

Workloads have also been selected differently; in this chapter, cache sensitivity of benchmarks is considered. We analyze the cache sensitivity of benchmarks by simulating benchmarks on a 16-way 4MB L2 cache and on a 2-way 512kB L2 cache. If the number of L2 misses per kilo instructions (MPKI) of a benchmark on the 16-way 4MB L2 cache is greater by more than 10% compared to that on the 2-way 512kB L2 cache, then we classify this benchmark as cache-sensitive. Otherwise, we classify it as cache-insensitive. The benchmarks are listed in Table 3.

Now we randomly assemble 20 quad-core workloads considering cache sensitivity. Workloads are categorized into five groups, four workloads in each group. For each quad-core workload, we mix four benchmarks. There is no cacheinsensitive benchmark in the workloads in group1, one in each workload in group2, two in group3, three in group4, and group5 has only cache-insensitive benchmarks. Workloads are listed in Table 4.

After 5 million cycles cache warm up, 2 billion instructions are simulated for multi-programmed workloads on quad-core processors. For the partitioning technique, we use a 5 million cycle period for monitoring and partitioning decisions as was done in [START_REF] Qureshi | Utility-based cache partitioning: A low-overhead, highperformance, runtime mechanism to partition shared caches[END_REF]. We use a 2% probability value for an allocation switching technique which is obtained empirically (the performance is not sensitive to the value around 2%).

Results

This section discusses the results of simulation. We compared our techniques with and without the allocation switching technique to the state-of-the-art migrationbased hybrid cache management technique, called read-write aware hybrid cache architecture (RWHCA) [START_REF] Wu | Power and performance of readwrite aware hybrid caches with non-volatile memories[END_REF].

Performance

A weighted speedup is used as a performance metric, which is the sum of perapplication speedups in IPC compared to the baseline (RWHCA running a single application is used as the baseline). Fig. 4 shows the weighted speedups normalized to those of RWHCA (the weighted speedups of RWHCA are also obtained by using the same baseline). The left bar in each workload set represents the speedup of the proposed approach without the switching technique and the right bar represents that with the switching technique.

In the hybrid caches partitioning technique without switching, the performance improvement is 4.9% in geometric mean over the total of 20 workloads. For the workloads in group3, where two cache-sensitive and two cache-insensitive benchmarks are mixed, the performance improvement is 8.7% on average; the useless preemption of cache ways by cache-insensitive benchmarks can degrade the performance of the cache-sensitive applications, and thus the partitioning technique can be very effective in this group. In the case of group5 where four cache-insensitive benchmarks are mixed, the partitioning scheme can improve cache utilization by assigning an optimal number of ways to each application, but the improvement is not as significant as group3.

The hybrid caches partitioning technique with allocation switching improves the performance by 6.7% in geometric mean over the total of 20 workloads. Some workloads show drastic performance improvement such as set1 and set10. These improvements come from some benchmarks that have little store access. So the SRAM is underutilized in these workloads. If both SRAM and STT-RAM caches are fully utilized, then an allocation switching scheme can harm the performance improvement of cache partitioning as shown in set5, but its degradation is not significant.

Miss Rates

Fig. 5 reports the difference in L2 miss rates between the RWHCA and our techniques with and without allocation switching. Left bars are the results of the proposed technique without allocation switching, and right bars are the results with switching. The former case reduces the miss rate by 4.8% on average for the 20 workloads. The miss rate increases for set3, but the difference is ignorable. Among the five groups, group3 shows the highest reduction of miss rates (9.2% on average), which is similar to the trend of performance.

In the technique with switching, the miss rate reduction is 6.7% on average compared to the reference technique, which is 1.8% more reduction compared to technique without switching. The miss rate is reduced by 13.3% for group2 compared to the reference technique.

Cache Energy Consumption

Fig. 6 compares the L2 energy consumption of our techniques with and without a switching scheme against the reference. In the technique without switching, the reduction of energy consumption is 10.0% on average for a total 20 of workloads and 11.7%, 10.4%, 11.0%, 12.0%, and 4.4%, respectively, for group1 to group 5. Workloads in group5 show little energy reduction compared to those of RWHCA because the partitioning technique is not efficient in these workloads.

The technique with switching reduces energy consumption by 16.6% on average over the total of 20 workloads, which corresponds to 6.6% more reduction compared to the technique without switching. All groups except group5 show more reduction of energy consumption. Compared to the reference technique, energy reductions by groups are 12.1%, 22.3%, 22.9%, 20.7%, and 3.2%.

DRAM Energy Consumption

Fig. 7 shows the DRAM energy consumption during the simulation. The results of our techniques with and without the switching scheme are normalized to that of RWHCA. In the technique without switching, the decrease of energy consumption is 5.9% on average for the 20 workloads. Group3 shows the highest energy saving of 9.6% on average and group5 shows the lowest of 3.4%. The technique with allocation switching decreases DRAM energy consumption by 7.5% on average over the 20 workloads, which corresponds to 1.6% more reduction compared to the technique without the switching scheme.

Area Overhead

An area overhead of our technique comes from a partitioning scheme. For cache usage monitoring, every 32nd cache set is sampled, so one UMON has 16 of 4B counters and an ATD of 128 sets for a 4MB 16-way set-associative cache. One ATD consists of 16 entries, each has one valid bit, 24-bit tag and 4-bit LRU information. So the total overhead of one UMON is 7.3KB and the total overhead of cache usage monitoring for a quad-core processor is 29.25KB. In a tag of the cache, 2-bit is added to identify the core that owns each block, the sum of the overheads for the cache is 16KB. So the total overhead of the partitioning scheme for 4MB 16-way set-associative cache is 45.25KB, which is negligible compared to the size of the last-level cache. 6 Related work

Reducing Write Overhead of STT-RAM

A write intensity predictor [START_REF] Ahn | Write intensity prediction for energy-efficient nonvolatile caches[END_REF] is proposed to find a write intensive block and allocate the block to SRAM. This approach achieves high energy reduction of hybrid caches, but does not consider cache partitioning, and thus it may increase miss rates of the cache in some workloads, worsening the DRAM energy efficiency. Obstruction-aware cache management technique (OAP) [START_REF] Wang | Oap: An obstruction-aware cache management policy for stt-ram last-level caches[END_REF] increases the efficiency of a last-level STT-RAM cache by bypassing some application that has no merits of using the last-level cache. The technique collects information on latency, number of accesses, and miss rates of the applications in a period and exploits the data for the detection of bypassing applications. But the target of this technique is a pure STT-RAM cache, so it can not be applied directly to hybrid caches. A lot of researches [START_REF] Chen | Static and dynamic co-optimizations for blocks mapping in hybrid caches[END_REF][START_REF] Li | A software approach for combating asymmetries of non-volatile memories[END_REF][START_REF] Li | Mac: Migration-aware compilation for stt-ram based hybrid cache in embedded systems[END_REF][START_REF] Sun | A novel architecture of the 3d stacked mram l2 cache for cmps[END_REF][START_REF] Wu | Hybrid cache architecture with disparate memory technologies[END_REF][START_REF] Wu | Power and performance of readwrite aware hybrid caches with non-volatile memories[END_REF] utilize a migration technique for adapting block placements, but in our proposed partitioning technique, a conventional migration scheme [START_REF] Wu | Power and performance of readwrite aware hybrid caches with non-volatile memories[END_REF] can reduce the energy efficiency of hybrid caches by breaking the partitioning decision.

Cache Partitioning for Energy Saving

Cooperative partitioning technique [START_REF] Sundararajan | Cooperative partitioning: Energy-efficient cache partitioning for high-performance cmps[END_REF] is proposed to save energy consumption of a shared cache. In this technique, a partition is aligned physically and unused ways are disabled to reduce static power consumption. But this technique does not consider hybrid caches, and thus the block placement problem should be solved to apply this technique to hybrid caches. Writeback-aware partitioning [START_REF] Zhou | Writeback-aware partitioning and replacement for last-level caches in phase change main memory systems[END_REF] assumes an off-chip memory of phase change RAM (PRAM) and reduces the number of write operations in PRAM by dynamic partitioning of a shared cache to decrease the energy consumption of the write-inefficient memory.

Conclusion

We address the potential of the dynamic cache partitioning technique for reducing energy consumption of hybrid caches. We propose an energy-efficient partitioning technique for hybrid caches in which the number of blocks installed by a core is adaptively balanced between SRAM and STT-RAM while satisfying a partitioning decision. If a miss is caused by a store miss in the upper-level cache, the corresponding block is placed in SRAM. If the miss is originated from a load miss in the upper-level cache, a new block can be placed in either SRAM or STT-RAM according to the number of blocks installed by the core in SRAM. In addition, we apply the allocation switching technique to avoid too much unbalanced use of SRAM or STT-RAM. The simulation results show that our partitioning technique improves the performance of the multi-core system by 6.7% on average, saves the energy consumption of the hybrid cache by 16.6%, and reduces the DRAM energy by 7.5% compared to the state-of-the-art migration-based hybrid cache management technique.

Fig. 1 .

 1 Fig. 1. Breakdown of write-inducing events in the L2 cache.

Fig. 2 .

 2 Fig. 2. Magnetic tunnel junction of STT-RAM.

Fig. 3 .

 3 Fig. 3. Structure of hybrid cache partitioning.

Fig. 4 .

 4 Fig. 4. Normalized weighted speedup.

Fig. 5 .

 5 Fig. 5. Difference in miss rates.

Fig. 6 .

 6 Fig. 6. Energy consumption of RWHCA (left), our architecture without allocation switching (middle), and our architecture with allocation switching (right).

Fig. 7 .

 7 Fig. 7. Normalized energy consumption of DRAM.

Table 1 .

 1 System configuration

	Parameters	Configuration
	Processor	3.0 GHz, 4-core CMP, 4-wide, out-of-order, 128-entry ROB, 48-entry
		LSQ.
	L1 Caches	I-cache: 32kB, 64B lines, 4-way, 2-cycle latency
		D-cache: 32kB, 64B lines, 4-way, 2-cycle latency
	L2 Cache	Unified, 4MB, 64B lines, 16-way (4-way SRAM and 12-way STT-RAM),
		10 cycle latency for SRAM, 10 cycle (read) and 38 cycle (write) latency
		for STT-RAM
	DRAM	DDR3-1333 (10-10-10), 1 channel, 8 banks, 32-entry queue, open-page
		policy, FR-FCFS policy

Table 2 .

 2 Energy Consumption of the L2 Cache

		Read Energy	Write Energy	Static Power
	SRAM Region	0.217 nJ	0.217 nJ	14.682 mW
	STT-RAM Region 0.097 nJ	0.670 nJ	3.438 mW

Table 3 .

 3 Benchmark analysis of SPEC CPU2006

		L2 MPKI	-Diff (%)	Type
	Benchmark 512kB	4MB
	quantum	24.7	24.7	0.0
	milc	24.3	24.3	0.1
	sjeng	56.2	56.1	0.1	Insensitive
	gobmk	11.9	11.6	3.0
	lbm	35.2	33.5	4.8
	namd	0.8	0.8	7.0
	soplex	31.9	27.2	14.9
	mcf	78.8	66.3	15.9
	h264	0.3	0.1	65.6
	gromacs	2.1	0.5	73.3
	hmm	2.5	0.5	78.7
	deal2	0.3	0.1	80.3	Sensitive
	perl	0.5	0.1	80.8
	astar	15.8	2.3	85.5
	povray	1.2	0.2	85.8
	gcc	1.6	0.2	87.5
	bzip	4.7	0.1	97.4
	omnetpp	102.3	2.6	97.5

Table 4 .

 4 Workloads from SPEC CPU2006

		Set		Workloads
		1	soplex	perl	gcc	omnetpp
	group1	2	soplex	povray	bzip	hmm
		3	gcc	h264	hmm	soplex
		4	perl	povray	h264	hmm
		5	bzip	omnetpp	hmm	quantum
	group2	6	omnetpp gromacs	soplex	gobmk
		7	soplex	mcf	gromacs quantum
		8	milc	monetpp	h264	deal2
		9	omnetpp quantum	soplex	sjeng
	group3	10	omnetpp	h264	namd	quantum
		11	sjeng	milc	deal2	bzip
		12	quantum	sjeng	gromacs	bzip
		13	milc	omnetpp	sjeng	quantum
	group4	14	omnetpp quantum	sjeng	gobmk
		15	quantum	milc	lbm	omnetpp
		16	soplex	quantum	milc	gobmk
		17	milc	namd	gobmk	lbm
	group5	18	lbm	milc	sjeng	gobmk
		19	quantum	sjeng	gobmk	milc
		20	sjeng	quantum	gobmk	lbm

Since we perform dynamic partitioning, the number of cache ways allocated to a core can be reduced after repartitioning. Thus NS(i, j) can temporarily exceed NUT (i) set by the new partitioning. The excess ways can be claimed later by other cores and thus NS(i, j) will be reduced to the new value of NUT (i).

Acknowledgment. This work was supported by the National Research Foundation of Korea (NRF) grants funded by the Korean government (MEST) (No. 2012R1A2A2A06047297).