请选择 进入手机版 | 继续访问电脑版

一种用于提高固态硬盘命中率的PSO缓存管理方案

2017-7-8 02:17 134 0
0
摘要: 抽象随着闪存的普及和基于闪存的固态硬盘(SSD)具有耐冲击性,非易失性,低能耗和高I/O速度等优点,固态硬盘被广泛应用于企业计算环境。同时,固态硬盘还具有异地更新和读,写,擦除操作之间的非对称I/O延迟的特性, ...

抽象

随着闪存的普及和基于闪存的固态硬盘(SSD)具有耐冲击性,非易失性,低能耗和高I/O速度等优点,固态硬盘被广泛应用于企业计算环境。同时,固态硬盘还具有异地更新和读,写,擦除操作之间的非对称I/O延迟的特性,固态硬盘的写入和擦除操作要比读操作慢很多。因此,缓冲器替换算法需要很好地反映这种不对称性。该文中提出了一种以粒子群优化算法(PSO)为基础的缓冲管理算法来准确预测在缓冲区中的每个逻辑页中存的是热数据还是冷数据。该预测是页面级FTL方案的一个关键标准。被预测为热数据的页面将被保持在缓冲器,从而提高固态硬盘缓冲区的命中率。仿真结果表明,这篇论文提出的方案在读写命中次数和命中率方面要优于现有方案。


算法概述

该方案是在固态硬盘内部的FTL上实现的,它维护了三个列表:目录列表,保护列表,驱逐列表。


目录列表是用来做索引的,它和缓冲区中记录的编号是一致的,它能来保持所有请求的逻辑页不会因为引用而改变他们的顺序。当缓冲区满的时候,必须要释放空间来响应新的请求。被替换的页就是从驱逐列表里面选出来的,然后将它从缓冲区清除掉,最后它对应的逻辑页也会在目录列表中删除。


保护列表是被用来记录缓冲区中拥有较高 PH 值的逻辑页的,它的大小是缓冲区的一半。对保护列表的操纵是基于 LRU 原理的,然而,当保护列表满的时候,剔除的页并不是从保护列表里面选的。


驱逐列表用来维护目录列表中 PH 值较小的逻辑页。它的大小是缓冲区大小的一半。这个驱逐列表是一个传统的 LRU 列表,其中最近且最少被使用的页作为被替换的页被驱逐出缓冲区。当驱逐列表中页的总的访问频率比保护列表中的要大时,驱逐列表中的页将比保护列表中的页更“热”。PSO算法最终会来计算目录列表中每个页的的 PH 适应值。拥有较大 PH 适应值的页将会被维持在保护列表中,其他的将会放在驱逐列表中。


用来实现缓冲区写,读和被替换的页的选择的算法


用来实现缓冲区写的算法



用来实现缓冲区读的算法


用来实现替换页选择的算法



热度值(PHF)的预测

在缓存管理模块的目录列表中应用 PSO 算法,从而根据 PH 适应值把逻辑页分为以下两种类型,被预测为“热”数据和被预测为“冷”数据。


PH适应值的计算方法如下:


PHfitness(i)=impact(i,M)+impact(i)PHfitness(i)=impact(i,M)+impact(i)


假设缓冲区总共有 L 个逻辑页,i,M 都是属于 L 的。 某个逻辑页 page_i 的 PHF 值是由缓冲区里访问频率最大的页 page_M 的频率和该逻辑页自身的频率 page_i 决定的。


如下图所示,目录列表里一共有 L 个逻辑页。因为列表里的逻辑页是按顺序存放的,所以它们很有可能属于同一个请求。然而,把所有的这些逻辑页作为一个写操作的基本单位是不切实际的。因此,在本文中,我们假设连续页的任何子序列都属于同一个写操作。


一个页面的PHF值很大程度上会收到缓冲区里访问频率最快的页面的影响。如上图所示,page_M 是缓冲区中被访问频率最高的。既然列表里的逻辑页都是按顺序存放的,那么他们很有可能是和 page_M 一起被访问。他们被一起访问的概率是由他们到 page_M 的距离来决定的。例如,上图中,page_(M-1) 比 page_2 离 page_M 更近,因此在后面的操作中 page_(M-1) 跟page_M一起访问的可能性就比 page_2 高。


impact(M−1,M)>impact(2,M)


其次,目录列表中每个页面访问频率的增长率同样是受自身当前的访问频率影响的。换句换说,如果一个页面在当前有很高的访问频率,那么在未来他的频率很有可能会增长。例如,如果上图中的 page_2 比 page_(M-1) 的访问频率高,那么在后面 page_2 比 page_(M-1) 有更高的可能被访问到。


impact(M−1)<impact(2)


最后,基于上面两个公式就可以计算出页面的 PHF 了。页面的 PHF 越高就越有可能留在缓冲区中。


算法实现

swarms 是 L*1 的矩阵,表示目录列表中每个页面的访问次数。


Rate 是 L*1 的矩阵,表示每个粒子预测的增长率。


Plargest 是 L*1 的矩阵,表示种群中每个粒子所预测的最大的访问频率,是由当前访问频率决定的。


GHightest 表示目录列表中访问次数最大的粒子。

在第 i+1 次迭代中,页面 p 的预测的热度可以用下面的公式计算:


Rate(p,i+1)=w∗Rate(p,i)+C1∗rand1∗(Plargest(p,i)−PHF(p,i))+c2∗rand2/【GHightest(p,i)−PHF(p,i)】


PHF(p,i+1)=PHF(p,i)+Rate(p,i+1)


在上面的公式中 Plargest(p,i)-PHF(p,i) 表示一个页面的 PHF 值受自身的值影响,GHightest(p,i) - PHF(p,i) 表示一个页面的 PHF 值也受当前缓冲区中 PHF 的最大值影响。参数 w 代表着惯性因素,影响着最优解的收敛。 c1 和 c2 分别代表着粒子的自身学习因子和社会学习因子,rand1 和 rand2 分别是他们的权重,取值为0到1之间。


总结

缓冲区替换算法需要适当地反映不对称性,而基于粒子群优化(PSO)的缓冲器管理算法,将缓冲区中的每个逻辑页面精确地预测为热或冷。为热的页面保持在缓冲器中以最大化SSD缓冲器的命中率。显著的提升了在读写命中次数和命中率方面的能力


原文转载于:http://ieeexplore.ieee.org/document/7292929/

扩展阅读:http://www.swarmintelligence.org/


每天一个段子:你们每个月还蚂蚁花呗的时候是怎样一种心态?我是特别怨恨命运的不公。上个月买了喜欢的东西,爽的明明是上个月的我,凭什么要这个月的我还钱。


注:本文由SSD PK社区提供,如有错误和不足之处欢迎在留言中批评指正,如果您喜欢本文,也可以分享给你的朋友。转载本文请务必保留原文出处,更多热门请关注SSD PK 社区网,www.pkssd.com是有关SSD最专业的社区网,提供全球有关SSD的最新热门资讯、各大厂商产品热门评测,最新前沿技术动态、有关企业级SSD选型以及最佳实践。


鲜花

握手

雷人

路过

鸡蛋
分享到

最新评论

    TylerDong

    管理员
    这个人很懒什么都没写!
    • 40

    • 文章
    • 0

    • 收听
    • 0

    • 听众

    热门文章

    SSD社区微信公众号

    SSD社区微信公众号

    扫我关注
    返回顶部