Lifetime improvement through adaptive reconfiguration for nonvolatile FPGAs

Lifetime improvement through adaptive reconfiguration for nonvolatile FPGAs

SRAM的FPGA有漏电和容量的限制，使用NVM替换SRAM是一个有效的方式，但是NVM有寿命问题。BRAM的磨损均衡问题依赖静态分析，但是静态分析对于具有多个运行时工作模式的应用程序不够准确。

提出了一个对工作模式进行感知并自适应模式进行重构的磨损均衡机制

以4%的性能开销实现120%的寿命改善

---

静态分析是什么？工作模式是什么？

静态分析：写使能信号的稳定性使其可通过监视的写入信号使能频率来估计BRAMs在运行时的写入频率（maybe)

应用程序可能具有不同工作负载的各种工作模式。此外，对于某些应用程序，工作模式强烈依赖于执行环境。

20组随机输入激励信号（三种工作模式）

e1-e8的写使能信号频率的变化（写次数的波动）

---

Pattern-aware wear leveling mechanism

key：工作模式与配置文件特征的匹配
work：

1. 修改布局算法使其根据不同的特性生成配置文件
2. 开发一个决定器感知工作模式，选择配置文件

Lifetime-aware placement

为了匹配运行模式，我们希望生成“不同”的配置文件进行自适应选择。从生存时间的角度，“不同“说明配置所映射的物理BRAM不同。

配置文件对BRAM寿命的影响：

以此引出配置文件生成的两个策略

1. 逻辑BRAM映射到被映射次数尽可能少的物理BRAM上

   

2. 避免逻辑BRAM被映射到之前已经被映射过的物理BRAM（为了避免更细粒度的写损坏吗？）

   

放置算法的流程图如下。传统的CAD放置算法时基于模拟退火的。

// 加载BRAM过去的使用次数记录
foreach 𝑃ℎ𝑦𝑖 ∈ 𝑃ℎ𝑦𝑠 do
    𝑃ℎ𝑦𝑠_𝐷𝑖𝑐𝑡[𝑃ℎ𝑦𝑖] = BRAMs usage record;
𝑃ℎ𝑦𝑠_𝐿𝑖𝑠𝑡 = sort(𝑃ℎ𝑦𝑠_𝐷𝑖𝑐𝑡.𝑢𝑠𝑒𝑑_𝑛𝑢𝑚);	// 从小到大排序使用次数
𝑆𝑒𝑙_𝑛𝑢𝑚 = min(⌊(1+𝛼)∗#𝐿𝑜𝑔𝑠/#𝑃ℎ𝑦𝑠∗100%⌋, #𝑃ℎ𝑦𝑠);// 选择前(1+𝛼)*100%次数最小的BRAM
𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒_𝑃ℎ𝑦𝑠 = 𝑃ℎ𝑦𝑠_𝐿𝑖𝑠𝑡[0∶𝑆𝑒𝑙_𝑛𝑢𝑚];// 作为将被逻辑BRAM映射的物理BRAM候选队列
𝑀𝑎𝑥_𝑢𝑠𝑎𝑔𝑒 = 𝑃ℎ𝑦𝑠_𝐿𝑖𝑠𝑡[𝑆𝑒𝑙_𝑛𝑢𝑚].𝑢𝑠𝑒𝑑_𝑛𝑢𝑚; // 获取之前BRAM写次数最大值
// 给每个逻辑BRAM随机生成一个初始解的物理BRAM
foreach 𝐿𝑜𝑔𝑖 ∈ 𝐿𝑜𝑔𝑠 do
    Randomly Select 𝑃ℎ𝑦𝑠𝑒𝑙 from 𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒_𝑃 ℎ𝑦𝑠;
	𝐿𝑜𝑔_𝑖.𝑃ℎ𝑦 map to the 𝑃ℎ𝑦𝑠𝑒𝑙;
Calculate 𝑇 ; // 计算退火温度
while Not Exit(T) do
    Randomly Select one 𝐿𝑜𝑔𝑠𝑒𝑙 from 𝐿𝑜𝑔𝑠;	// 随机选择一个逻辑BRAM:Logsel
	while Not Exit inner(inner_iter) do
        Randomly Select 𝑃ℎ𝑦𝑠𝑒𝑙 from 𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒_𝑃ℎ𝑦𝑠; // 随机选择一个物理BRAM:Physel
		// 旧解决方案的花费，不仅计算性能花销，也计算了寿命花销
		𝑂𝑙𝑑 𝑆𝑜𝑙𝑢𝑡𝑖𝑜𝑛 = (𝐿𝑜𝑔𝑠𝑒𝑙-𝐿𝑜𝑔𝑠𝑒𝑙.𝑃ℎ𝑦; 𝑃ℎ𝑦𝑠𝑒𝑙.𝐿𝑜𝑔-𝑃ℎ𝑦𝑠𝑒𝑙)
        𝐶𝑜𝑠𝑡𝑆1 = Calculate(𝑂𝑙𝑑 𝑆𝑜𝑙𝑢𝑡𝑖𝑜𝑛);
		// 交换映射后新的解决方案的花费
		𝑁𝑒𝑤 𝑆𝑜𝑙𝑢𝑡𝑖𝑜𝑛 = (𝐿𝑜𝑔𝑠𝑒𝑙-𝑃ℎ𝑦𝑠𝑒𝑙; 𝑃ℎ𝑦𝑠𝑒𝑙.𝐿𝑜𝑔-𝐿𝑜𝑔𝑠𝑒𝑙.𝑃ℎ𝑦);
		𝐶𝑜𝑠𝑡𝑆2 = Calculate(𝑁𝑒𝑤 𝑆𝑜𝑙𝑢𝑡𝑖𝑜𝑛);
		𝛥𝐶𝑜𝑠𝑡 = 𝐶𝑜𝑠𝑡𝑆2 − 𝐶𝑜𝑠𝑡𝑆1;	// 新旧方案花销的差值
		if 𝛥𝐶𝑜𝑠𝑡 < 0 then	// 新方案花销更小
            Accept_Swap();	// 接受新方案
			break;
		else
            if Rand(0,1) < 𝑒^{−(𝛥𝐶𝑜𝑠𝑡)/𝑇} then	// 以特定概率接受
            	Accept_Swap();
				break;
			Reject_Swap();
		𝑖𝑛𝑛𝑒𝑟_𝑖𝑡𝑒𝑟 ++;
	Update 𝑇;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

• 逻辑与物理的映射一一对应，多的𝛼用于解空间的探索，𝛼的值决定了综合时间和配置文件的表现和寿命。这里设置为20%
• 解决方案的花费，不仅计算性能花销，也计算了寿命花销

Adaptive reconfiguration at runtime stage

在运行时，decision-maker用于将配置文件与工作模式进行匹配。

n个BRAM，m个配置文件

矩阵𝐶𝑢𝑟表示物理BRAM的历史写负载（write load) = 历史写次数/BRAM的总生命周期

矩阵𝐶𝑜𝑛表示物理BRAM在改变到特定配置后的归一化(normalized)写负载。可根据过去一段时间的历史写行为预测写负载，预测会定期更新。

预测会更新，那么权重要重新计算吗？

矩阵𝑤是每个配置文件执行时间的权重。

“𝐶𝑜𝑛⋅𝑤”代表执行配置文件一段时间(权重为𝑤)后的未来写负载。

历史写的负载+未来配置写的负载*每个配置执行的时间分布 ===》希望BRAM的写负载可以达到100%

在哪？功能由BRAM的计数器实现，达到一定写次数后触发重配置吗？

如果由计数器触发重配置，那么执行时间w的重配置的优先级是啥？

• 计数器计算负载达到某个值触发重配置
• 没有计数器触发，根据分配的执行时间权重w,自动重配置

Answer：Observer就是每个BRAM的计数器
时间权重并不是指运行时间，而是指BRAM的写负载（写次数/总可写次数）

磨损均衡的目标是使每个BRAM的写负载接近1，这可以被抽象为最小化矩阵的L2范数表示矩阵距离的最小化，也就是公式4.

距离是指和原点的距离吗

公式4可以转换为公式5，是一个关于w的二次函数，就可以求最小值

Evaluation

写负载由ACE 2.0[29]产生。为了模拟动态工作模式，设置参数𝛾来间歇性地调整写负载调整写负载的范围

**𝛾表示静态分析的工作负载与实际运行时工作负载之间的偏差率。**实验中，𝛾设置为40%来评估所提议的策略。

采用了来自各种应用程序的一系列基准测试。表2总结了评估电路的特点。

Lifetime enhancement

使用累计运行周期数来衡量FPGA设备的寿命。模拟器记录每个NVM单元的写次数和FPGA的运行周期。当单元耗尽时，模拟将停止，其中运行周期的累积数将被记录为FPGA的寿命。

Our-的策略，它使用提出的策略生成重构文件，同时采用与PAWL相同的重配置策略。

PAWL+和Our采用本文提出的decision-maker,有效地减少累积偏差的影响

使用多个𝛾参数评估不同工作模式下寿命的实验结果。如图8所示，随着𝛾的增加，我们的机制呈现出更大的优势。因为决策者能够感知工作模式的变化，实现寿命提升。

Storage and performance overhead

随着配置文件数量的增加，存储开销会非常大。

设置了一组实验探索Our在不同数量配置文件下的寿命增强

如图9所示，随着配置文件数量的增加，所提策略获得了更长的生命周期改进

配置文件的增长率低于生命周期的增长率

如图10所示，所提出的机制比PAWL有更多的性能开销，并且性能开销会随着配置文件数量的增加而增加。与PAWL相比，我们增加了物理bram的利用率，这可能会导致一些路由不友好的放置结果，导致性能较差。