• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 17
    • 下载费用:30 金币  

    重庆时时彩北京赛车时时乐ez114: 基于内存访问堆栈距离的数据CACHE性能探索方法.pdf

    摘要
    申请专利号:

    重庆时时彩单双窍门 www.4mum.com.cn CN201410014367.9

    申请日:

    2014.01.13

    公开号:

    CN103793339A

    公开日:

    2014.05.14

    当前法律状态:

    终止

    有效性:

    无权

    法律详情: 未缴年费专利权终止IPC(主分类):G06F 13/16申请日:20140113授权公告日:20160824终止日期:20180113|||授权|||实质审查的生效IPC(主分类):G06F 13/16申请日:20140113|||公开
    IPC分类号: G06F13/16 主分类号: G06F13/16
    申请人: 杭州电子科技大学
    发明人: 姚英彪; 韩琪
    地址: 310018 浙江省杭州市下沙高教园区2号大街
    优先权:
    专利代理机构: 杭州求是专利事务所有限公司 33200 代理人: 杜军
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201410014367.9

    授权公告号:

    |||||||||

    法律状态公告日:

    2018.12.28|||2016.08.24|||2014.06.11|||2014.05.14

    法律状态类型:

    专利权的终止|||授权|||实质审查的生效|||公开

    摘要

    本发明公开了一种基于内存访问堆栈距离的数据Cache性能探索方法。本发明包括如下步骤:步骤1.计算内存访问堆栈距离及其概率分布;步骤2.确定探索的Cache容量及其三个参数组数S(Set?size)、关联度A(Associativity)和块大小B(Block?size)的范围;步骤3.计算估计参数es(S)、ea(A)和eb(B),利用es(S)、ea(A)和eb(B)估计Cache三个参数组数S(Set?size)、A(Associativity)和B(Block?size)对命中率的影响,并计算命中率est1;步骤4.利用内存访问堆栈距离的概率分布计算命中率est2;步骤5.比较命中率est1和est2,最终估计出Cache命中率。本发明在嵌入式系统内存结构早期设计中是非常有用,它能够帮助设计者快速从巨大的内存设计空间中筛选出少量满足具体应用要求的片上内存结构,从而节约产品开发时间和成本。

    权利要求书

    权利要求书
    1.  基于内存访问堆栈距离的数据Cache性能探索方法,其特征在于包括如下步骤: 
    步骤1.计算内存访问堆栈距离及其概率分布; 
    步骤2.确定探索的Cache容量及其三个参数组数S(Set size)、关联度A(Associativity)和块大小B(Block size)的范围; 
    步骤3.计算估计参数es(S)、ea(A)和eb(B),利用es(S)、ea(A)和eb(B)估计Cache三个参数组数S(Set size)、A(Associativity)和B(Block size)对命中率的影响,并计算命中率est1; 
    步骤4.利用内存访问堆栈距离的概率分布计算命中率est2; 
    步骤5.比较命中率est1和est2,最终估计出Cache命中率; 
    步骤1所述的计算内存访问堆栈距离及其概率分布的具体如下: 
    1-1.读入一条内存访问踪迹,得到当前内存访问地址; 
    1-2.如果该地址在SP中第i个位置命中,则对应位置的堆栈距离直方图H_SP(i)加1,同时将SP的0~(i-1)个元素往下挪移1个位置,用空出来的第0个位置保存该地址,SP中其它位置的元素不动; 
    1-3.如果该地址在SP中没有命中,则该地址是第一次访问,将H_SP(∞)加1,SP增加一个新元素,SP所有元素往下挪移1个位置,最后将此地址保存在SP第0个位置; 
    1-4.重复步骤1-1至1-3,直到n条内存访问踪迹处理完成,将内存访问堆栈距离直方图通过公式(1)转换为内存访问堆栈的概率分布P_SP; 
    P_SP=H_SP/n(1) 
    读入是应用程序执行时的内存访问踪迹,输出是内存访问堆栈距离的概率分布和应用程序数据量大??;计算内存访问堆栈距离时的地址粒度为处理器的字宽度,SP是内存访问的地址堆栈,H_SP是内存 访问堆栈距离的直方图,P_SP是内存访问堆栈距离的概率分布,n为应用程序内存访问踪迹条数,Num为应用程序的数据量。 

    2.  如权利要求1所述的基于内存访问堆栈距离的数据Cache性能探索方法,其特征在于步骤2中所述的Cache容量C、组数S(Set size)、关联度A(Associativity)和块大小B(Block size)的范围计算具体包括如下步骤: 
    2-1.根据应用程序数据量的大小Num,按下面公式(2)确定Cache探索的容量C;该公式确定的Cache容量C的单位是比特,对应以字为单位的Cache容量size=2C字; 

    2-2.Cache的组数S(Set size)、关联度A(Associativity)和块大小B(Block size)三个参数按以下方式确定; 
    Smin=Cmin-2 
    Smax=Cmax
    A=0~2(分别对应直接映射、2或4路组关联Cache) 
    B=0~4(块大小从1个字到16个字)。 

    3.  如权利要求1所述的基于内存访问堆栈距离的数据Cache性能探索方法,其特征在于步骤3中所述的参数es(S)、ea(A)、eb(B)和命中率est1的计算步骤具体如下: 
    3-1.计算估计参数es(S),es(S)用来估计组数S(Set size)对命中率的影响,计算过程如下: 
    3-1-1.确定es(Smin)和组数S(Set size)的初始值, 
    ,S=Smin+1; 
    3-1-2.利用块大小为1个字的全相联Cache估计其相对性能speedup1: 

    3-1-3.利用此相对性能speedup1估计es(S)的值: 

    3-1-4.令组数S的值加1; 
    3-1-5.重复步骤3-1-2至3-1-4,直到组数S>Smax; 
    3-2.计算估计参数ea(A),ea(A)用来估计关联度A对命中率的影响,计算过程如下: 
    3-2-1.确定ea(A)的初始值,ea(0)=0.75; 
    3-2-2.用WayHit来保存Cache在不同关联度下的命中次数,执行一次Cache仿真(参数为S=Smin,A=2,B=0),并将Cache在不同关联度下的命中次数保存在WayHit中; 
    WayHit的具体计算如下: 
    当Cache命中,则判断Cache在哪一路数命中:若Cache在最新路数命中,则WayHit(0)加1;若Cache在次最新路数命中,则WayHit(1)加1;若Cache在其他路数命中,则WayHit(2)加1; 
    3-2-3.将不同关联度的命中次数转换为Cache的相对性能speedup2: 

    3-2-4.利用此相对性能speedup2估计ea(A)在A=1,2的值: 
    ea(A)=2×ea(A-1)×speedup22    (6) 
    3-3.计算估计参数eb(B),eb(B)用来估计块大小B对命中率的影响,计算过程下: 
    3-3-1.确定eb(B)的初始值,eb(0)=0.75; 
    3-3-2.用BlockHit来保存Cache在不同块大小的近似命中次数,执行一次Cache仿真(参数为S=Smin,A=0,B=4),并将Cache在不同块大小的近似命中次数保存在BlockHit中; 
    BlockHit的具体计算如下: 
    当Cache命中时,计算上一次在此块命中的地址的块号(块大小为1个字)与当前在此块命中的地址的块号差值的绝对值,如果此绝对值 小于1,则BlockHit(0)加1;若此绝对值大于等于1且小于2,则BlockHit(1)加1;若此绝对值大于等于2且小于4,则BlockHit(2)加1;若此绝对值大于等于4且小于8,则BlockHit(3)加1;若此绝对值大于等于8且小于16,则BlockHit(4)加1; 
    3-3-3.将不同块大小的命中次数转换为Cache的相对性能speedup3: 

    3-3-4.利用此相对性能speedup3估计eb(B)在B=1~4的值: 
    eb(B)=2×eb(B-1)×speedup32    (8) 
    3-4.按公式(9)估计Cache在不同组数S(Set size)、关联度A(Associativity)和块大小B(Block size)下的命中率est1: 

    上式(9)中,sd为内存访问堆栈距离,P_SP是内存访问堆栈距离的概率分布;u_sd为可能在Cache命中的堆栈距离的上界,u_sd用公式(10)计算如下: 

    上式(10)中,size表示Cache的容量,size=2S+A+B,其中,S、A和B用比特数表示。 

    4.  如权利要求1所述的基于内存访问堆栈距离的数据Cache性能探索方法,其特征在于步骤4中所述的计算命中率est2具体方法如下: 
    在步骤1得到内存访问堆栈距离的概率分布P_SP后,应用公式(11)估计块大小为1个字、组数为size的全关联LRU Cache的命中率,并将此命中率的1.25倍作为est2,其实质是用它作为Cache在参数为S、A和B时的命中率的上限; 


    5.  如权利要求1所述的基于内存访问堆栈距离的数据Cache性能探索方法,其特征在于步骤5中所述的在参数为S、A和B时估计并输出最终Cache的命中率est,此命中率为est1和est2较小的,即: 
    est=min(est1,est2)    (12)。 

    说明书

    说明书基于内存访问堆栈距离的数据Cache性能探索方法
    技术领域
    本发明涉及嵌入式系统的存储系统设计领域,特别是涉及一种基于内存访问堆栈距离的数据Cache性能探索方法。
    背景技术
    片上内存结构是嵌入式系统关键部件之一,它对系统的整体性能、制造成本、系统功耗等多个参数具有很大的影响。为得到给定应用的最优片上内存结构,嵌入式系统设计者必须对片上内存结构设计空间的每一种方案进行性能评价,以得到满足系统性能、功耗和成本等约束的最佳方案。然而,由于设计空间巨大,如片上内存类型是SPM(Scratch Pad Memory)还是高速缓存Cache、容量怎么划分、Cache或SPM的具体设计参数等,如果仅仅靠仿真的方法去评价每一种片上内存配置,无疑是一件耗时耗力的事情,特别是在产品有上市时间限制的条件下,这种全仿真的方法更不可实现。
    为在巨大的片上内存设计空间找出满足性能、功耗和成本要求的配置,设计者需要用快速准确的方法去评价不同片上内存配置的相对性能,这点对成本敏感的嵌入式系统设计尤为重要。例如,如果分析表明一个小的片上内存结构就能获得满意的性能,那么设计时就可以采用小的片上内存结构,从而减少芯片面积和降低芯片的生产成本,使产品更有竞争力。在片上内存结构性能估计中,由于SPM是软件管理的片上内存,其上的数据对设计者是已知的,因此性能很好估计;难点在于硬件管理的Cache的性能估计,其上的数据对设计者未知,因此它的性能估计是片上内存结构性能估计的难点问题。由于Cache的性能公式为:
    T=hit×Thit+(1-hit)×Tmiss
    上述公式中,Thit和Tmiss分别为Cache命中时和失配时的访问延迟,它们很 容易通过Cache的硬件结构和工艺库得到;hit为Cache针对不同应用的命中率,它是Cache性能估计的难点??杉?,探索Cache在不同配置下的性能,关键是要估计Cache在不同配置下的命中率。针对这个问题,本发明专利提出一种基于内存访问堆栈距离的数据Cache命中率估计方法,以此实现对Cache性能的探索。
    内存访问堆栈距离是指同一个内存地址两次连续访问之间的独一无二的其它内存地址的访问个数;如果该地址为第一次访问,堆栈距离记为∞,如图1所示。在图1中,前2次内存访问都是新地址,因此内存访问堆栈距离为∞;第3次访问在地址堆栈的第0个位置命中,因此内存访问的堆栈距离为0;依次类推。
    内存访问堆栈距离之所以能用来进行Cache命中率估计,在于它具有这样的性质:对于一个采用最近最少使用(LRU)替换策略的全相联Cache,其大小为s组;如果内存访问堆栈距离计算时的地址大小与Cache的块大小一致,则当内存访问的堆栈距离d≤s时,它在Cache里面命中;d>s时,它在Cache里面失配。由于内存访问堆栈也是按最近最少使用排序的,即将最近访问的排在最前面,离现在访问最远的排在最后面,因此本发明专利提出的基于内存访问堆栈距离的Cache性能探索方法仅适合于采用LRU替换算法的Cache。
    发明内容
    本发明的目的在于针对现有技术不足,实现Cache性能快速且准确估计,提供一种基于内存访问堆栈距离的数据Cache性能探索方法。
    本发明解决其技术问题所采用的技术方案具体包括如下步骤:
    步骤1.计算内存访问堆栈距离及其概率分布;
    步骤2.确定探索的Cache容量及其三个参数组数S(Set size)、关联度A(Associativity)和块大小B(Block size)的范围;
    步骤3.计算估计参数es(S)、ea(A)和eb(B),利用es(S)、ea(A)和eb(B)估计Cache三个参数组数S(Set size)、A(Associativity)和B(Block size)对命中率 的影响,并计算命中率est1;
    步骤4.利用内存访问堆栈距离的概率分布计算命中率est2;
    步骤5.比较命中率est1和est2,最终估计出Cache命中率。
    步骤1所述的计算内存访问堆栈距离及其概率分布的具体如下:
    1-1.读入一条内存访问踪迹,得到当前内存访问地址;
    1-2.如果该地址在SP中第i个位置命中,则对应位置的堆栈距离直方图H_SP(i)加1,同时将SP的0~(i-1)个元素往下挪移1个位置,用空出来的第0个位置保存该地址,SP中其它位置的元素不动。
    1-3.如果该地址在SP中没有命中,则该地址是第一次访问,将H_SP(∞)加1,SP增加一个新元素,SP所有元素往下挪移1个位置,最后将此地址保存在SP第0个位置。
    1-4.重复步骤1-1至1-3,直到n条内存访问踪迹处理完成,将内存访问堆栈距离直方图通过公式(1)转换为内存访问堆栈的概率分布P_SP。
    P_SP=H_SP/n      (1)
    读入是应用程序执行时的内存访问踪迹,输出是内存访问堆栈距离的概率分布和应用程序数据量大??;计算内存访问堆栈距离时的地址粒度为处理器的字宽度,SP是内存访问的地址堆栈,H_SP是内存访问堆栈距离的直方图,P_SP是内存访问堆栈距离的概率分布,n为应用程序内存访问踪迹条数,Num为应用程序的数据量。
    步骤2中所述的Cache容量C、组数S(Set size)、关联度A(Associativity)和块大小B(Block size)的范围计算具体包括如下步骤:
    2-1.根据应用程序数据量的大小Num,按下面公式(2)确定Cache探索的容量C;该公式确定的Cache容量C的单位是比特,对应以字为单位的Cache容量size=2C字。

    2-2.Cache的组数S(Set size)、关联度A(Associativity)和块大小 B(Block size)三个参数按以下方式确定。
    Smin=Cmin-2
    Smax=Cmax
    A=0~2(分别对应直接映射、2或4路组关联Cache)
    B=0~4(块大小从1个字到16个字)
    步骤3中所述的参数es(S)、ea(A)、eb(B)和命中率est1的计算步骤具体如下:
    3-1.计算估计参数es(S),es(S)用来估计组数S(Set size)对命中率的影响,计算过程如下:
    3-1-1.确定es(Smin)和组数S(Set size)的初始值,
    es(Smin)=2Smin,]]>S=Smin+1。
    3-1-2.利用块大小为1个字的全相联Cache估计其相对性能speedup1:
    speedup1=Σi=02×es(S-1)P_SP(i)/Σi=0es(S-1)P_SP(i)---(3)]]>
    3-1-3.利用此相对性能speedup1估计es(S)的值:

    3-1-4.令组数S的值加1。
    3-1-5.重复步骤3-1-2至3-1-4,直到组数S>Smax。
    3-2.计算估计参数ea(A),ea(A)用来估计关联度A对命中率的影响,计算过程如下:
    3-2-1.确定ea(A)的初始值,ea(0)=0.75。
    3-2-2.用WayHit来保存Cache在不同关联度下的命中次数,执行一次Cache仿真(参数为S=Smin,A=2,B=0),并将Cache在不同关联度下的命中次数保存在WayHit中。
    WayHit的具体计算如下:
    当Cache命中,则判断Cache在哪一路数命中:若Cache在最新路数命中,则WayHit(0)加1;若Cache在次最新路数命中,则WayHit(1) 加1;若Cache在其他路数命中,则WayHit(2)加1。
    3-2-3.将不同关联度的命中次数转换为Cache的相对性能speedup2:
    speedup2=Σi=0kWayHit(i)/Σi=0k-1WayHit(i)---(5)]]>
    3-2-4.利用此相对性能speedup2估计ea(A)在A=1,2的值:
    ea(A)=2×ea(A-1)×speedup22      (6)
    3-3.计算估计参数eb(B),eb(B)用来估计块大小B对命中率的影响,计算过程下:
    3-3-1.确定eb(B)的初始值,eb(0)=0.75。
    3-3-2.用BlockHit来保存Cache在不同块大小的近似命中次数,执行一次Cache仿真(参数为S=Smin,A=0,B=4),并将Cache在不同块大小的近似命中次数保存在BlockHit中。
    BlockHit的具体计算方法是:
    当Cache命中时,计算上一次在此块命中的地址的块号(块大小为1个字)与当前在此块命中的地址的块号差值的绝对值,如果此绝对值小于1,则BlockHit(0)加1;若此绝对值大于等于1且小于2,则BlockHit(1)加1;若此绝对值大于等于2且小于4,则BlockHit(2)加1;若此绝对值大于等于4且小于8,则BlockHit(3)加1;若此绝对值大于等于8且小于16,则BlockHit(4)加1。
    3-3-3.将不同块大小的命中次数转换为Cache的相对性能speedup3:
    speedup3=Σi=0kBlockHit(i)/Σi=0k-1BlockHit(i)---(7)]]>
    3-3-4.利用此相对性能speedup3估计eb(B)在B=1~4的值:
    eb(B)=2×eb(B-1)×speedup32      (8)
    3-4.按公式(9)估计Cache在不同组数S(Set size)、关联度A(Associativity)和块大小B(Block size)下的命中率est1:
    est1(S,A,B)=Σsd=0u_sd2-sdes(S)×ea(A)×eb(B)×P_SP(sd)---(9)]]>
    上式(9)中,sd为内存访问堆栈距离,P_SP是内存访问堆栈距离的概率分布;u_sd为可能在Cache命中的堆栈距离的上界,u_sd用公式(10)计算如下:

    上式(10)中,size表示Cache的容量,size=2S+A+B(其中,S、A和B用比特数表示)。
    步骤4中所述的计算命中率est2具体方法如下:
    在步骤1得到内存访问堆栈距离的概率分布P_SP后,应用公式(11)估计块大小为1个字、组数为size的全关联LRU Cache的命中率,并将此命中率的1.25倍作为est2,其实质是用它作为Cache在参数为S、A和B时的命中率的上限。
    est2(S,A,B)=1.25×Σi=0size-1P_SP(i)---(11)]]>
    步骤5中所述的在参数为S、A和B时估计并输出最终Cache的命中率est,此命中率为est1和est2较小的,即:
    est=min(est1,est2)      (12)
    本发明有益效果如下:
    本发明专利只需要计算一次应用程序的内存访问堆栈距离和执行2次Cache仿真提取估计参数,就可以估算采用LRU替换策略的数据Cache在不同块大小、关联度、组数情况下的命中率,从而快速实现对Cache性能空间的探索。本专利利用一些实际程序进行测试,测试结果表明,本专利方法估计出的数据Cache命中率的平均绝对误差为3%左右,最大误差10%左右,不同配置的两两比较正确率在90%左右。本发明专利在嵌入式系统的早期设计中是非常有用的,它能够帮助设计者快速从巨大的内存设计空间中筛选出适应具体应用的少量片上内存结构,从而节约产 品开发时间和成本。
    附图说明
    图1是内存访问的堆栈距离示意图;
    图2是基于堆栈距离的Cache性能估计方法的流程图;
    图3是平均误差和最大误差分布图;
    图4是正确率分布图。
    具体实施方式
    本发明是一种基于内存访问堆栈距离的数据Cache性能估计方法,下面结合图2说明其具体实施过程。
    步骤1.计算内存访问堆栈距离及其概率分布;
    步骤2.确定探索的Cache容量及其三个参数组数S(Set size)、关联度A(Associativity)和块大小B(Block size)的范围;
    步骤3.计算估计参数es(S)、ea(A)和eb(B),利用es(S)、ea(A)和eb(B)估计Cache三个参数组数S(Set size)、A(Associativity)和B(Block size)对命中率的影响,并计算命中率est1;
    步骤4.利用内存访问堆栈距离的概率分布计算命中率est2;
    步骤5.比较命中率est1和est2,最终估计出Cache命中率。
    步骤1所述的计算内存访问堆栈距离及其概率分布的具体如下:
    1-1.读入一条内存访问踪迹,得到当前内存访问地址;
    1-2.如果该地址在SP中第i个位置命中,则对应位置的堆栈距离直方图H_SP(i)加1,同时将SP的0~(i-1)个元素往下挪移1个位置,用空出来的第0个位置保存该地址,SP中其它位置的元素不动。
    1-3.如果该地址在SP中没有命中,则该地址是第一次访问,将H_SP(∞)加1,SP增加一个新元素,SP所有元素往下挪移1个位置,最后将此地址保存在SP第0个位置。
    1-4.重复步骤1-1至1-3,直到n条内存访问踪迹处理完成,将内存访问堆栈距离直方图通过公式(1)转换为内存访问堆栈的概率分布 P_SP。
    P_SP=H_SP/n      (1)
    读入是应用程序执行时的内存访问踪迹,输出是内存访问堆栈距离的概率分布和应用程序数据量大??;计算内存访问堆栈距离时的地址粒度为处理器的字宽度,SP是内存访问的地址堆栈,H_SP是内存访问堆栈距离的直方图,P_SP是内存访问堆栈距离的概率分布,n为应用程序内存访问踪迹条数,Num为应用程序的数据量。
    步骤2中所述的Cache容量C、组数S(Set size)、关联度A(Associativity)和块大小B(Block size)的范围计算具体包括如下步骤:
    2-1.根据应用程序数据量的大小Num,按下面公式(2)确定Cache探索的容量C;该公式确定的Cache容量C的单位是比特,对应以字为单位的Cache容量size=2C字。

    2-2.Cache的组数S(Set size)、关联度A(Associativity)和块大小B(Block size)三个参数按以下方式确定。
    Smin=Cmin-2
    Smax=Cmax
    A=0~2(分别对应直接映射、2或4路组关联Cache)
    B=0~4(块大小从1个字到16个字)
    步骤3中所述的参数es(S)、ea(A)、eb(B)和命中率est1的计算步骤具体如下:
    3-1.计算估计参数es(S),es(S)用来估计组数S(Set size)对命中率的影响,计算过程如下:
    3-1-1.确定es(Smin)和组数S(Set size)的初始值,
    es(Smin)=2Smin,]]>S=Smin+1。
    3-1-2.利用块大小为1个字的全相联Cache估计其相对性能speedup1:
    speedup1=Σi=02×es(S-1)P_SP(i)/Σi=0es(S-1)P_SP(i)---(3)]]>
    3-1-3.利用此相对性能speedup1估计es(S)的值:

    3-1-4.令组数S的值加1。
    3-1-5.重复步骤3-1-2至3-1-4,直到组数S>Smax。
    具体实现如下:

    行1用来确定es(Smin),行3利用块大小为1个字的全相联Cache估计不同S下的相对性能,行4确定其S下的es(S)的值。
    3-2.计算估计参数ea(A),ea(A)用来估计关联度A对命中率的影响,计算过程如下:
    3-2-1.确定ea(A)的初始值,ea(0)=0.75。
    3-2-2.用WayHit来保存Cache在不同关联度下的命中次数,执行一次Cache仿真(参数为S=Smin,A=2,B=0),并将Cache在不同关联度下的命中次数保存在WayHit中。
    WayHit的具体计算如下:
    当Cache命中,则判断Cache在哪一路数命中:若Cache在最新路数命中,则WayHit(0)加1;若Cache在次最新路数命中,则WayHit(1)加1;若Cache在其他路数命中,则WayHit(2)加1。
    3-2-3.将不同关联度的命中次数转换为Cache的相对性能speedup2:
    speedup2=Σi=0kWayHit(i)/Σi=0k-1WayHit(i)---(5)]]>
    3-2-4.利用此相对性能speedup2估计ea(A)在A=1,2的值:
    ea(A)=2×ea(A-1)×speedup22      (6)
    具体实现如下:

    WayHit用来保存Cache在不同关联度下的命中次数,行2-9执行一次Cache仿真(参数为S=Smin,A=2,B=0),并将Cache在不同关联度下的命中次数保存在WayHit中;行11-12利用WayHit估计ea(A)。
    3-3.计算估计参数eb(B),eb(B)用来估计块大小B对命中率的影响,计算过程下:
    3-3-1.确定eb(B)的初始值,eb(0)=0.75。
    3-3-2.用BlockHit来保存Cache在不同块大小的近似命中次数,执行一次Cache仿真(参数为S=Smin,A=0,B=4),并将Cache在不同块大小的近似命中次数保存在BlockHit中。
    BlockHit的具体计算方法是:
    当Cache命中时,计算上一次在此块命中的地址的块号(块大小为1个字)与当前在此块命中的地址的块号差值的绝对值,如果此绝对值小于1,则BlockHit(0)加1;若此绝对值大于等于1且小于2,则BlockHit (1)加1;若此绝对值大于等于2且小于4,则BlockHit(2)加1;若此绝对值大于等于4且小于8,则BlockHit(3)加1;若此绝对值大于等于8且小于16,则BlockHit(4)加1。
    3-3-3.将不同块大小的命中次数转换为Cache的相对性能speedup3:
    speedup3=Σi=0kBlockHit(i)/Σi=0k-1BlockHit(i)---(7)]]>
    3-3-4.利用此相对性能speedup3估计eb(B)在B=1~4的值:
    eb(B)=2×eb(B-1)×speedup32      (8)
    具体实现如下:

    BlockHit用来保存Cache在不同块大小的近似命中次数,行2-14执行一次Cache仿真(参数为S=Smin,A=0,B=4),并将Cache在不同块大小的近似命中次数保存在BlockHit中;行16-17利用BlockHit估计eb(B)。
    3-4.按公式(9)估计Cache在不同组数S(Set size)、关联度A(Associativity)和块大小B(Block size)下的命中率est1:
    est1(S,A,B)=Σsd=0u_sd2-sdes(S)×ea(A)×eb(B)×P_SP(sd)---(9)]]>
    上式(9)中,sd为内存访问堆栈距离,P_SP是内存访问堆栈距离的概率分布;u_sd为可能在Cache命中的堆栈距离的上界,u_sd用公式(10)计算如下:

    上式(10)中,size表示Cache的容量,size=2S+A+B(其中,S、A和B用比特数表示)。
    步骤4中所述的计算命中率est2具体方法如下:
    在步骤1得到内存访问堆栈距离的概率分布P_SP后,应用公式(11)估计块大小为1个字、组数为size的全关联LRU Cache的命中率,并将此命中率的1.25倍作为est2,其实质是用它作为Cache在参数为S、A和B时的命中率的上限。
    est2(S,A,B)=1.25×Σi=0size-1P_SP(i)---(11)]]>
    步骤5中所述的在参数为S、A和B时估计并输出最终Cache的命中率est,此命中率为est1和est2较小的,即:
    est=min(est1,est2)      (12)
    实施例1
    为验证本发明专利有效性,对本发明专利的方法进行了实验。所使用的7个测试程序的基本情况如表1所示。使用时间加速比、平均绝对误差、最大绝对误差、正确率作为性能评价指标。时间加速比反映本发明专利估计Cache性能的快速性;平均绝对误差、最大绝对误差、正确率反映本发明专利估计Cache性能的准确性。
    表1测试程序基本情况
    Trace来源数据量(字)Cache大小(字)Cache配置数FFTMiBench4950128-204856CRC32MiBench112864-51239JPEG CoderMiBench5416128-204856GCCSPEC200018938256-819271SWIMSPEC20006482256-409656AC3 Decoder实际应用6123256-409656MP3 Decoder实际应用6444256-409656
    对时间加速比性能只是利用MP3测试程序估计了本发明专利与指令集仿真、RTL级仿真方法的时间加速比,它表示为
    speedup=T‾sim×NTstack+Tpara+T‾est×N]]>
    上式中,Tstack、Tpara和分别为每个配置平均仿真时间、堆栈距离计算时间,参数估计时间和每个配置平均估计时间,N为配置数。在同一个实验平台上,对于MP3测试程序,相对于指令集仿真器,这几个参数为Tstack=5313ms、Tpara=3402ms和在N=56条件下,本发明专利的时间加速比接近11;相对于RTL级仿真器,在N=56条件下,本发明专利的时间加速比接近3.8*104。从上式也可以看出,内存设计探索空间越大,本发明专利的时间加速比越好,其极限是
    平均绝对误差反映了估计命中率与仿真命中率整体上的接近程度,最大误差反映了估计命中率与仿真命中率的最大差异值。平均绝对误差、最大绝对误差用下式定义:
    Avg_err=1NΣi=1N|hitsim(i)-hitest(i)|]]>
    Max_err=max(|hitsim(i)-hitest(i)|),i=1,2,...,N
    上式中,hitsim是仿真得到的Cache命中率,hitest是本发明专利估计出的Cache命中率。实验结果如图3所示,本发明专利的基于堆栈距离 的Cache性能估计平均绝对误差为2.65%,最大绝对误差为10.9%。
    在进行内存设计探索时,更重要的是比较Cache不同配置下的相对性能的正确率。如果两个配置其仿真得到的Cache命中率和估计出的Cache命中率满足下式,则认为这次比较是正确的:
    (hitsim(i)-hitsim(j))×((hitest(i)-hitest(j))>=0
    正确率则定义为比较正确的次数比上总次数。表1所示测试程序在不同Cache配置下的性能比较正确率指标如图4所示,其平均正确率为89.44%。

    关 键 词:
    基于 内存 访问 堆栈 距离 数据 CACHE 性能 探索 方法
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:基于内存访问堆栈距离的数据CACHE性能探索方法.pdf
    链接地址://www.4mum.com.cn/p-6157155.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03