是否有用于微控制器 EEPROM 磨损均衡的通用算法? [英] Is there a general algorithm for microcontroller EEPROM wear leveling?

问题描述

我正在开发一个 Arduino 库，它将最大限度地延长 AVR 的 EEPROM 的使用寿命.它需要您要存储的变量数量并完成其余的工作.这是我的尝试，并不适用于所有情况.

背景信息

Atmel 表示，每个存储单元的额定写入/擦除周期为 100,000 次.他们还提供了应用说明，其中描述了如何进行磨损均衡.以下是应用笔记的摘要.

通过在两个内存地址之间交替写入，我们可以将擦除/写入增加到 200,000 个周期.三个内存地址为您提供 300,000 次擦除/写入周期等等.为了自动执行此过程，使用状态缓冲区来跟踪下一次写入的位置.状态缓冲区也必须与参数缓冲区的长度相同，因为也必须对其执行磨损均衡.由于我们无法存储下一次写入的索引，因此我们在状态缓冲区中增加相应的索引.

这是一个例子.

 <------------------- EEPROM -------------------->0 牛顿-------------------------------------------------参数缓冲区 |状态缓冲区 |-------------------------------------------------初始状态.[ 0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 |0 ]首先写的是一个7.对应的位置状态缓冲区中的值更改为以前的值 + 1.两个缓冲区都是循环的.[ 7 |0 |0 |0 |0 |0 |1 |0 |0 |0 |0 |0 ]第二个值 4 被写入参数缓冲区状态缓冲区中的第二个元素变为前一个元素，在本例中为 1，加 1.[ 7 |4 |0 |0 |0 |0 |1 |2 |0 |0 |0 |0 ]等等[ 7 |4 |9 |0 |0 |0 |1 |2 |3 |0 |0 |0 ]

为了确定下一次写入应该发生在何处，我们查看元素之间的差异.如果前一个元素 + 1 不等于下一个元素，那么这就是应该发生下一次写入的地方.例如:

 从第一个开始计算差异状态缓冲区中的元素并环绕.一般算法:前一个元素 + 1 = 当前元素第一个元素:0 + 1 = 1 = 第一个元素(继续)第二个元素:1 + 1 = 2 = 第二个元素(继续)第三个元素:2 + 1 = 3 = 第三个元素(继续)第 4 个元素:3 + 1 = 4 != 第 4 个元素(下一次写入发生在这里)[ 7 |4 |9 |0 |0 |0 |1 |2 |3 |0 |0 |0 ]^ ^||另一个要考虑的边缘情况是当递增值环绕在 256 处，因为我们正在写入字节.随着下面的缓冲区我们知道下一个写入是在第三个元素因为 255 + 1 = 0 != 250 假设我们使用字节算术.[ x |× |× |× |× |× |第254话255 |250 |第251话第252话253]^|在我们写入元素 3 后，状态缓冲区增加使用字节算术到下一个值，看起来像这样.255 + 1 = 0(环绕)0 + 1 != 251(下一次写入在这里)[ x |× |× |× |× |× |第254话255 |0 |第251话第252话253]^|

以上这些示例展示了如何为一个变量延长 EEPROM 的使用寿命.对于多个变量，想象一下将 EEPROM 分成多个具有相同数据结构但缓冲区更小的段.

问题

我有我上面描述的工作代码.我的问题是当缓冲区长度 >= 256 时算法不起作用.这是发生了什么

 缓冲区长度为 256.最后一个零来自缓冲区的初始状态.在每个索引前一个元素 + 1 == 下一个元素.没办法知道下一个写入应该在哪里.<--------------状态缓冲区------------>[ 1 |2 |... |第253话第254话255 |0 ]当缓冲区长度为大于 256.查找读取会认为下一个元素在它应该在的第一个 0 处255.<-------------------- 状态缓冲区------------------->[ 1 |2 |... |第253话第254话255 |0 |0 |0 ]

问题

如何解决上述问题?有没有更好的方法来跟踪下一个元素应该写在哪里?

解决方案

关于一般 EEPROM 寿命延长的一些想法:

1. EEPROM 单元的写入(由硬件)通常分两步操作:首先，单元被擦除，即设置为全 1(0b11111111 = 0xff)，然后将要写入的位(有效只有那些 0) 被实际写入.位只能通过实际写操作设置为 0.将位从 0 更改为 1 需要擦除整个单元格，然后重新写入新值.

2. 如果 EEPROM 单元已经包含要写入的相同值 - 可能会(重新)写入或多或少的数据的情况 - 则无需写入单元，从而将该写入操作的磨损减少到 0.人们可能想要检查单元内容以确定是否需要写入，而不是总是向其写入新值.

3. 以上的组合导致了一种方法，即只在写入之前擦除单元格，如果新值中有任何 1 位，其中存储的值具有 0 位(即，如果 StoredValue & NewValue != NewValue).如果新值不需要 0 -> 1 位转换(StoredValue & NewValue == NewValue)，则无需擦除单元格.

4. AVR 提供用于分别擦除和写入 EEPROM 单元的单独指令，以支持上述机制.

5. 当执行读-比较-擦除-写操作而不仅仅是擦除-写操作时，数据传输到 EEPROM 的最坏情况速度当然会下降.然而，这有可能完全跳过某些/大多数单元的擦除-写入操作，这可能会降低相对速度损失.

对于你目前的问题，考虑以上几点:为什么不使用单个位来存储你的下一个写入位置?

示例:

状态缓冲区初始化为全1:

位号:0123 4567 89AB CDEF值:1111 1111 1111 1111

在访问 EEPROM 中的值之前，找到状态缓冲区中的前 1 位.该位的数字表示(循环)参数缓冲区的当前头"的地址.

每次推进参数缓冲区时，将状态缓冲区中的下一位设置为 0:

位号:0123 4567 89AB CDEF值:0111 1111 1111 1111

然后

值:0011 1111 1111 1111

然后

值:0001 1111 1111 1111

等等.

这可以在不擦除整个单元格的情况下完成，因此每次更新时只会磨损"状态缓冲区的一位 - 如果写入的数据也只有一个 0 位.
例如，要将存储的 0111 值转换为新值 0011，要写入的数据应为 1011 (data =( newValue XOR oldValue ) XOR 0xff)，除了我们真正想要更改的单个位之外，所有位都保持不变.

一旦状态缓冲区耗尽(全为 0)，它就会被完全擦除，然后一切重新开始.

这里的一个明确优点是，每个参数缓冲区单位只需要维护一位状态，与 Atmel 应用笔记相比，它仅消耗 1/8 的内存.此外，查找下一个写入位置也会快得多，因为只需要对状态缓冲区进行 1/8 的读取操作.(不正确，因为 EEPROM 读取的成本性能几乎为零-明智的，而所需的位移可能需要几十个周期.)

另一个注意事项:您认为使用 256 多个参数缓冲单元实际上有用吗?例如，在处理设备上 1024 字节的总可用 EEPROM 时，这些单元会变得非常小.- 100000 周期乘以 256 是相当多的写操作，如果似乎需要这么大的数字，则算法可能有问题，或者根本不应该使用 EEPROM.作为替代方案，在某些情况下，外部 NVRAM 将是一个不错的选择.>

访问时间也可能是这里的一个方面:当尝试在参数缓冲区中查找和读取 3 字节大小的元素时，带有 256 字节状态缓冲区，256 (+3) 在最坏的情况下将需要读取操作 - 巨大的开销！

有一个关于 EEPROM 单元的工作原理的非常说明性的文件，包括退化的方式和原因:

意法半导体:设计师如何充分利用 STMicroelectronics SerialEEPROM"，应用笔记 AN2014

I'm working on an Arduino library that will maximize the life of the AVR's EEPROM. It takes the number of variables you want to store and does the rest. This is my attempt, which does not work in all cases.

Background information

Atmel says each memory cell is rated for 100,000 write/erase cycles. They also provide an application note, which describes how to perform wear levelling. Here is a summary of the application note.

By alternating writes across two memory addresses, we can increase the erase/write to 200,000 cycles. Three memory addresses gives you 300,000 erase/write cycles and so on. To automate this process, a status buffer is used to keep track of where the next write should be. The status buffer must also be the same length as the parameter buffer because wear leveling must be performed on it as well. Since we can't store the index of the next write we increment the corresponding index in the status buffer.

Here is an example.

   <------------------- EEPROM -------------------->  
   0                                               N
   -------------------------------------------------
       Parameter Buffer    |     Status Buffer     |
   -------------------------------------------------

   Initial state.
   [ 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 ]

   First write is a 7. The corresponding position
   in the status buffer is changed to previous value + 1.
   Both buffers are circular.
   [ 7 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 ]

   A second value, 4, is written to the parameter buffer 
   and the second element in the status buffer becomes
   the previous element, 1 in this case, plus 1.
   [ 7 | 4 | 0 | 0 | 0 | 0 | 1 | 2 | 0 | 0 | 0 | 0 ]

   And so on
   [ 7 | 4 | 9 | 0 | 0 | 0 | 1 | 2 | 3 | 0 | 0 | 0 ]

To determine where the next write should occur, we look at the difference between elements. If the previous element + 1 does NOT equal the next element then that is where the next write should occur. For example:

   Compute the differences by starting at the first
   element in the status buffer and wrapping around. 
   General algo: previous element + 1 = current element
   1st element:  0 + 1 = 1 = 1st element (move on)
   2nd element:  1 + 1 = 2 = 2nd element (move on)
   3rd element:  2 + 1 = 3 = 3rd element (move on)
   4th element:  3 + 1 = 4 != 4th element (next write occurs here)

   [ 7 | 4 | 9 | 0 | 0 | 0 | 1 | 2 | 3 | 0 | 0 | 0 ]
                 ^                       ^
                 |                       |

   Another edge case to consider is when the incrementing values
   wrap around at 256 because we are writing bytes. With the
   following buffer we know the next write is at the 3rd element 
   because 255 + 1 = 0 != 250 assuming we are using byte arithmetic.

   [ x | x | x | x | x | x | 254 | 255 | 250 | 251 | 252 | 253 ]
                                          ^
                                          | 

   After we write at element 3 the status buffer is incremented 
   to the next value using byte arithmetic and looks like this.
   255 + 1 = 0 (wrap around)
   0 + 1 != 251 (next write is here)

   [ x | x | x | x | x | x | 254 | 255 |  0  | 251 | 252 | 253 ]
                                                ^
                                                | 

These examples above show how to extend the life of the EEPROM for one variable. For multiple variables imagine segmenting the EEPROM into multiple segments with the same data structure, but smaller buffers.

Problem

I have working code for what I described above. My problem is the algorithm does not work when the buffer length >= 256. Here is what happens

   Buffer length of 256. The last zero is from
   the initial state of the buffer. At every index
   previous element + 1 == next element. No way to
   know where the next write should be.

   <-------------- Status Buffer ------------>
   [  1  |  2  | ... | 253 | 254 | 255 |  0  ]


   A similar problem occurs when the buffer length
   is greater than 256. A lookup for a read will think
   the next element is at the first 0 when it should be at 
   255.
   <-------------------- Status Buffer ------------------>
   [  1  |  2  | ... | 253 | 254 | 255 |  0  |  0  |  0  ]

Question

How can I solve the above problem? Is there a better way to track where the next element should be written?

解决方案

Some thoughts about general EEPROM lifetime extension:

1. EEPROM cells are usually written (by the hardware) in a two step operation: first, the cell is erased, that is, set to all ones (0b11111111 = 0xff), then the bits to be written (effectively only those that are 0) are actually written. Bits can only be set to 0 by an actual write operation. Changing a bit from 0 to 1 requires the whole cell to be erased and then re-writing the new value.

2. If an EEPROM cell already contains the same value that is to be written to it - which may be the case for more or less of the data to be (re-)written - there is no need to write to the cell at all, reducing wear for that write operation to 0. One might want to check the cells content to decide if it needs to be written at all instead of always writing a new value to it.

3. The combination of the above leads to an approach where a cell is only erased before a write, if there are any 1 bits in the new value where the stored value has a 0 bit (that is, if StoredValue & NewValue != NewValue). There is no need to erase the cell if there are no 0 -> 1 bit transitions required for the new value (StoredValue & NewValue == NewValue).

4. The AVR provides separate instructions for erasing and writing to, respectively, an EEPROM cell to support the mechanisms mentioned above.

5. The worst-case speed of a data transfer to EEPROM will of course drop when performing a read-compare-erase-write instead of just an erase-write operation. However, this has the potential to completely skip erase-write operations for some/most cells which may reduce the relative speed penalty.

For your present problem, think about the above points: Why not use single bits to store your next write position?

Example:

Status buffer is initialized to all ones:

Bit number: 0123 4567 89AB CDEF
Value:      1111 1111 1111 1111

Before accessing a value in EEPROM, find the first 1 bit in your status buffer. The number of that bit represents the address of the current "head" of your (circular) parameter buffer.

Each time you advance the parameter buffer, set the next bit in your status buffer to 0:

Bit number: 0123 4567 89AB CDEF
Value:      0111 1111 1111 1111

then

Value:      0011 1111 1111 1111

then

Value:      0001 1111 1111 1111

and so on.

This can be done without erasing the whole cell and will thus only "wear" a single bit of your status buffer for every update - if the data written has only a single 0 bit, too.
To turn, for instance, a stored value of 0111 to the new value 0011 the data to write should be 1011 (data = ( newValue XOR oldValue ) XOR 0xff), leaving all bits untouched except for the single one we actually want to change.

Once the status buffer is exhausted (all 0) it is erased in full, and it all starts over again.

A definite plus here is that only a single bit of status needs to be maintained per unit of the parameter buffer, which consumes only 1/8 of the memory compared to the Atmel application note. Besides, finding the next write location will also be much faster since only 1/8 of the read operations on the status buffer will be needed. (Edit: Not true because EEPROM reads come at almost zero cost performance-wise, while the required bit-shifting may take some dozens of cycles.)

Another note, though: Do you think it is actually useful to use 256+ parameter buffer units? The units would become quite small when dealing with, for example, 1024 bytes of total available EEPROM on the device. - And 100000 cycles multiplied by 256 is quite a huge number of write operations and if that large a number seems to be required, there probably is something wrong in the algorithm or EEPROM should not be used for the purpose at all. As an alternative, external NVRAM would be a good choice in some scenarios.

Access time may be an aspect here, too: When trying to look up and read an element of, say, 3 bytes size in the parameter buffer with a 256 byte status buffer, 256 (+3) read operations will be needed in the worst case - a tremendous overhead!

There is a very illustrative document about the workings of EEPROM cells, inlcuding the how-and-why of deterioration:

STMicroelectronics: "How a designer can make the most of STMicroelectronics Serial EEPROMs", application note AN2014

这篇关于是否有用于微控制器 EEPROM 磨损均衡的通用算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！