论文阅读：SSD中基于PSO的缓冲区管理算法（ICITCS 2015）

目录 [+]

1. 1. Abstract
2. 2. 算法概述
3. 3. 热度值(PHF)的预测
4. 4. 算法实现

原文：Wang Y L, Lee B J, Lee J J, et al. A PSO-based Buffer Management Scheme for Improving Hit Ratio of Solid State Drive[C]. IT Convergence and Security (ICITCS), 2015 5th International Conference on. IEEE, 2015: 1-5. [下载]

1. Abstract

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

2. 算法概述

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

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

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

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

Algorithm 1. PSO_bufferWriteMangement(). p: logic page p

if(p resides in SSD buffer )
    find the requested logic page p in the directory list;
if(p resides in protection list){
    M_SelectPage();
    p.write frequency++;
    maintain the p in the header of protection list;
}
else if(p resides in eviction list){    
    M_SelectPage();
    p.write frequency++;
    maintain the p in the header of eviction list;
}
else if(p not resides in SSD buffer )
    if(p resides in SSD flash){
        VictimPage=M_SelectVictimPage();
        flush VictimPage to SSD Flash;
        load p from SSD flash and maintain the
        p in header of eviction list;
    }
    else if(p not resides in SSD flash)
        if (directory list is not full){
            if (protection list is not full){
                maintain the p in the header of protection List;
            }
            else if(Eviction List is not full){
                maintain the p in the header of eviction List;
            }
        }
    else if(directory list is full){
        VictimPage=M_SelectVictimPage();
        lush VictimPage to SSD Flash;
        maintain the p in the header of eviction list
    }

Algorithm 2. PSO_bufferReadMangement() . p: logic page p

if(p resides in SSD buffer )
    find the requested logic page p in the directory list;
if(p resides in protection list){ 
    M_SelectPage();
    p.read frequency++;
    maintain the p in the header of protection list;
}
else if(p resides in eviction list){ 
    M_SelectPage();
    p.read frequency++;
    maintain the p in the header of eviction list;
}
else
    p.readmiss++;

Algorithm 3. M_SelectVictimPage() .logic page p;buffer size L

PH: Predict Hot fitness value;
Sum_P: sum of frequency count of pages in protection list
Sum_E: sum of frequency count of pages in eviction list

if (Sum_P > Sum_E)
    return to the tail of eviction list;
    M_SelectVictimPage()
else
    Performed the PSO algorithm in the directory list;
Maintain 2/L logical pages with the top largest PH values of in the protection list;
The remaining 2/L logical pages maintain in the eviction list;
Return to the tail of eviction list;
M_SelectVictimPage()

3. 热度值(PHF)的预测

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

$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 越高就越有可能留在缓冲区中。

4. 算法实现

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

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

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

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

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

$Rate(p,i+1) = w * Rate(p,i) + C_1 * rand_1 * (Plargest(p,i)-PHF(p,i)) + c_2 * \frac{rand_2}{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之间。