计算机工程与科学-投稿模板

_______________________________________基金项目：国家自然科学基金（No.60970036，No.60873016）；国家863高技术研究发展计划（2009AA01Z124）一种低开销的异构可变相联度二级Cache结构ALow-overheadHeterogeneousVariableWayL2Cache***，***，***Y***,Y***,Z***（国防科学技术大学计算机学院，湖南长沙410073）(SchoolofComputerScience,NationalUniversityofDefenseTechnology,Changsha,Hunan410073,China)摘要：V-WayCache结构利用存储访问在组之间分布不均匀性，根据需求动态调整组相联度，具有比传统Cache结构更有效的资源利用率。然而，V-WayCache结构组相联度调整以增大Tag阵列容量为代价，增加了面积、功耗等开销，且Tag阵列利用率不高。本文对V-WayCache结构进行优化，提出一种低开销的异构可变相联度Cache结构HV-WayCache。HV-WayCache采用异构Tag阵列组织，通过允许多个组共享Tag项资源以缩减Tag路容量；Tag项替换信息以组为单位组织，挑选最久没有被使用的项作为被替换项。使用Cacti和Simics模拟器进行模拟实验，结果表明HV-WayCache结构能以很少的性能损失实现面积、功耗开销的极大降低。Abstract:Exploitingnon-uniformdistributionofcacheaccessesamongsets,V-Waycacheallowsvaryingwaysinsetswiththerun-timedemandsandoutperformsconventionalset-associativecacheinresourceutilization.However,thetagarrayinV-Waycacheisexpandedwhichinducelargeareaandpoweroverhead.Consideringthetagarrayisunder-utilizedinV-Waycache,weproposealow-overheadheterogeneousvariablewaycache,namedHV-Waycache.HV-Waycacheadoptsheterogeneoustagarrayandcutdowncapacityoftagwaysbysetssharinginthesameway.Maintainingtagreplacementinformationinper-setgranularity,HV-Waycacheselectstheleastrecentlyusedtagentriesforeviction.ExperimentresultsofCactiandSimicssimulatorsshowthatHV-Waycachebringsdownthelatency,areaandpoweroverheadgreatlyattheexpenseofsmallperformanceloss.关键词：Cache；低开销；异构结构；替换策略Keywords:Cache;Low-overhead;HeterogeneousOrganization;ReplacementStrategy中图分类号：TP3021引言目前广泛使用的多路组相联Cache结构将Cache空间分成若干组，每组包含相同数目Cache块，使用LRU替换策略管理资源。由于存储访问在Cache组之间的分布呈现不均匀性，传统结构等同对待所有组的方式造成了资源浪费。近年来，不少学者研究异构相联度Cache结构[1]-[4]，允许各个组实际包含的数据块数目变化，以提高资源利用率。根据管理策略的不同，现有异构相联度Cache结构大致可以分成两类：一类基于LRU替换策略管理，如HWS[1]（HeterogeneousWay-SizeCache）、SBC[2]（SetBalancingCache）等。LRU替换策略的基本出发点是局部性原理。二级Cache上存储访问的局部性特征经过一级Cache层次过滤后，LRU替换策略并不能有效管理Cache资源，还存在进一步提升性能的空间。另一类基于全局替换策略管理，如IIC[3]（IndirectIndexCache）、V-WayCache[4]（Variable-WayCache）等。与LRU替换策略相比，全局替换策略可以减轻局部性特征被过滤的影响，但是实现开销很大。IIC和V-WayCache都以增加Tag阵列容量为代价实现一定程度上全局替换。二级Cache结构设计应该在失效率、访问延迟、面积、功耗等因素之间权衡。针对V-WayCache中Tag阵列利用率低、开销大的问题，本文对其进行优化，提出一种低开销的异构可变相联度Cache结构（HeterogeneousVariableWayCache，简称为HV-WayCache）。它采用异构Tag阵列组织方式，允许各个Tag路中包含的组的数目不同；使用Reuse替换策略管理数据阵列，允许各个Tag组中对应的数据项数目不同。分别使用Cacti[5]和Simics[6]模拟器进行开销、性能分析，实验结果表明，HV-WayCache能以很少的性能损失获得面积、功耗开销的大大降低。2异构可变相联度Cache结构2.1整体框架W0Wn-1LRUDataRCT…maskTagArrayDataArrayHit？MultiplexerDecoderDataTagComparatoroffindextag图1HV-WayCache整体结构框图HV-WayCache结构对V-WayCache结构的Tag阵列进行优化，采用异构Tag阵列组织形式，实现Tag和数据阵列更加灵活的配置，整体框图如图1所示。HV-WayCache中Tag和数据阵列分离，Tag项和数据项之间使用双向指针关联。Tag阵列采用异构多路组相联形式，基于LRU替换策略管理，每路包含的组的数目iWS不同，且满足公式1。数据阵列使用地址索引方式访问，基于Reuse替换策略管理，优先淘汰数据阵列中重用次数为0的项。jiifSSjiWW,(1)与传统多路组相联结构相比，HV-WayCache结构中的Tag项中增加数据项地址信息，使用LRU表集中维护Tag项的LRU信息；数据项中增加Tag项地址信息，使用RCT表记录每个数据项的重用次数、有效位信息。HV-WayCache结构中必须满足Tag资源数多于数据资源数，即TDR（Tag-to-DataRatio）大于1，以引起较充裕Tag资源对有限数据资源的竞争，实现资源有效利用。2.2异构Tag阵列LRU替换策略总是将最近访问的Cache块放置在组的MRU位置，并选择组中LRU块作为被替换块，导致各个路的利用率存在差异，通常MRU路的利用率最高，LRU路的利用率最低。异构Tag阵列的基本思想是允许Tag路中多个组共享资源以缩减Tag路容量，降低整体开销的同时尽量减少对性能的影响。除了第0路Tag外，其它Tag路进行访问时首先经过地址掩膜，从组索引地址的最高位开始屏蔽若干位。使用组数目计算Tag路容量，假设第i路的容量为iWS，则第i+1路的容量为kWiS2，其中0k；组索引地址位数为02logWS，第i路屏蔽的地址位数为02logWWSSi；所有Tag项中tag长度统一，等于容量最少的路1nWS中tag所需长度。Tag项的LRU信息以组为单位使用单独的LRU表维护；LRU表中每一项以队列形式组织，按照LRU顺序记录对应Tag组中各个路的序号；LRU表的长度等于第0路Tag中组数目0WS。LRU信息更新是异构Tag阵列实现的关键。如果Cache访问组索引地址为index，路i的容量kWWSSi20，LRU表的更新操作如下：当Cache访问命中路i时，找出LRU表中低位地址与index的低iWS2log位相同的项，将路i插入各项的MRU位置（队列头）。当Cache访问失效时，查找LRU表中地址为index的项，将位于其LRU位置（队列尾）的路i作为被替换块地址，淘汰Tag路i中组地址与index的低iWS2log位相同的块以放置新加载块，然后按照Cache访问命中路i时的操作更新LRU表。W0W1LRU[2:0][2:0][1:0]index01234567012345670123MRU~LRUW0W1LRU[2:0][2:0][1:0]01234567012345670123MRU~LRUW0W1LRU[2:0][2:0][1:0]01234567012345670123MRU~LRU(a)命中路0(b)命中路1(c)失效01indexindex1101101100110101010图2两路组相联异构Tag阵列LRU表更新示例图2描述一个简单的两路组相联异构Tag阵列中LRU表更新示例，其中路0包含8项，路1包含4项，LRU表包含8项，当前Cache访问的组索引地址为110，路1的访问地址需要屏蔽index的最高1位。根据tag比较结果的不同，LRU表的更新操作可以分成如下三种情况：情况一：Cache访问命中路0时，更新LRU表中项6（110），将路0放置在MRU位置，路1放置在LRU位置，如图2(a)所示。情况二：Cache访问命中路1时，更新LRU表中项2（010）与项6（110），将路1放置在MRU位置，路0放置在LRU位置，如图2(b)所示。情况三：Cache访问失效时，查找LRU表中的项6（110），此时路1位于LRU位置，则将路1中块2（010）作为被替换块，放置新加载块；然后将LRU表中项2（010）与项6（110）中路1移动到MRU位置，如图2(c)所示。2.3存储访问操作发生二级Cache访问操作时，HV-WayCache首先根据存储地址访问Tag阵列，进行Tag比较。如果命中，则根据命中Tag项中记录的数据项地址访问数据阵列，读出数据。如果失效，则分别在Tag阵列和数据阵列中找到被替换Tag和数据项，用于放置新加载数据信息。被替换Tag项选取原则是Tag组中的LRU项，被替换数据项的选取依赖于被替换Tag项。如果被替换Tag项为有效项，则被替换Tag项对应的数据项作为被替换数据项；否则由Reuse替换策略选取。HV-WayCache中数据阵列的实现与V-WayCache相同，使用RCT表记录每个数据项的重用次数。当需要Reuse替换策略选取被替换数据项时，顺序搜索RCT表，找到重用次数为0的项。3实验及结果3.1实验设置模拟实现两种HV-WayCache配置方案，并与V-WayCache结构进行比较。三种Cache结构的配置如下：V-WayCache：基准结构，128KB，Tag阵列四路组相联，TDR=2，总tag项数目为4096项，总数据项数目为2048项。HV-Way-1：在V-WayCache基础上将Tag阵列分成tag1和tag2两部分，tag1包含路0和路1，tag2包含路2和路3，且将tag2中组的数目缩减一半。总的来说，Tag阵列容量缩减1/4，数据阵列不变。HV-Way-2：在HV-Way-1基础上维持TDR=2，即将数据阵列也缩减1/4。使用Cacti6.5估算访问延迟L、面积A、每次访问的动态读能量DE、漏流功耗LP。存储地址设置为64b，块大小为64B，温度为350K，所有Cache方案都采用顺序tag-data访问模式，一个读/写端口，加权功耗优化。Cache开销由Tag阵列开销和数据阵列开销两部分组成，HV-WayCache结构下的Tag阵列开销通过分别计算tag1、tag2的开销得到。L、A、DE、LP的计算公式如下：datatagtagdatatagLLLLLL21,ma