Clay Codes — 从生成矩阵的角度来看

Clay Codes ( Clay Codes: Moulding MDS Codes to Yield an MSR Code ) 是FAST18 上提出的一种编码方法,文章地址,Clay 码能够将一般的MDS 码(最优容错)转化为具有最优修复的编码方法,具有以下性质:

  • Minimum Storage (最小存储开销,同经典RS码和最小存储再生码,MSR)
  • Maximum Failure Tolerance(最大容错,即 (n,k)-Clay 码可以容任意n-k 失效)
  • Optimal Repair Bandwidth (最优修复开销,能够达到理论最优值)
  • All-Node Optimal Repair (最小开销修复所有节点的数据,包括原始数据和校验数据)
  • Disk Read Optimal (最优磁盘读)
  • Low Sub-packetization (低分包数,即码字长度短)

首先介绍下Clay 码的设计思想,第二部分从生成矩阵的角度来看看Clay 码如何实现。

一 Clay 码的设计思想

1.1 术语

首先文章介绍了一些基础概念:

纠删码:纠删码将一段原始数据等分为k 份,进而编码为m 份,共计n=k+m 份,通过将这n 份数据分别存储在n 个不同的存储节点上,达到抵御数据丢失的风险。

标量码/向量码(Scalar code/Vector code):标量码每个码字在每个节点上包含一个字节,向量码在每个节点上包含若干个字节,共同组合为一个超字节(superbyte),不同节点上超字节共同组成一个码字。

   上图表示标量码,下图表示向量码。在磁盘阵列中,每个条带(stripe)也是横跨n 个节点,对应的一个码字,而码字中一个字节(标量码)或者超字节(向量码)则对应着条带中的一个数据块。一个(n,k) 标量码和向量码在生成矩阵中对应的是一个n×k 和nw×kw 矩阵,其中一个超字节包含w 个字节。

MDS 码:最大距离可分(Maximum Distance )码是一种最优容错编码方法,即编码后的n 份数据最大可容忍任意m 份数据失效,原始数据也不会丢失。常见的RS、CRS、Evenodd、RDP 码都是MDS 码。

修复开销:修复开销指的是重建一个节点数据或单个数据块所需要的数据量(从磁盘读取、从网络传输的数据量)。在存储系统中,单点失效是常态,因此研究更注意单点失效的修复开销。

MSR 码:最小存储再生码(Minimum Storage Regenerating codes,MSR 码)是一类具有最小存储开销下的再生码。再生码是一类能够减少修复开销的纠删码。

原始数据量为M,再生码在每个节点存储的数据量为α。如果每个节点存储量最小,即α=M/k,那么这个再生码是MSR 码,和其他经典(n,k)-MDS 码存储开销相同。当一个节点失效,需要从剩余d<(n-1) 个节点中每个取β<α 数据完成修复,修复开销为dβ。当n-1 时,修复开销最小,为(n-1)α/m。

磁盘开销:再生码是网络编码研究者提出的,在数据修复时在网络上传输的数据量能够达到理论最小,但需要在磁盘上读取大量数据,进而计算得到少量修复数据进行数据修复,因此需要额外的磁盘访问和计算。Clay 码能够减少磁盘开销,即在网络上传输的数据就是从磁盘哦读取的数据。

系统码:系统码编码后保留了原始数据,非系统码编码后只有校验数据。实际存储系统中常见的是系统码,这样数据读取不用解码。

1.2 编码方法

下面以(n=4,k=2) 来介绍Clay 码,一种将一般MDS 码转化为MSR 码的方法。

Clay 是Coupled Layer 的结合,包含了Clay 码的两个特点:1 将MDS 码分层处理;2 分层之间耦合数据。

一个(4,2)-MDS 码编码后的数据有4 份,可以摆放成一个正方形。

四个(4,2)-MDS 码编码后的数据可以形成一个四层的棱柱,四棱柱的四个边对应着四个存储节点,边上的四个点所代表的数据存储于同一个节点。(下图a_0/b_0/c_o/d_0 都存在同一个节点)

耦合是将分层中不同数据进行线性组合,以实现最小修复开销。

图中被耦合的数据块用黄色表示,没有参与耦合的数据块用红色表示,两两耦合对应的数据块如上右图所示。如何选择耦合的数据块对文章中有也介绍,但为什么这样选择文章未提及。

下面谈谈什么是耦合,耦合即通过线性组合两个数据块,不管这两个数据块是原始数据块还是校验数据块。然后再将两个线性组合后的数据块(Coupled)取代两个原来未耦合的数据块(Uncoupled)。下图中(a_0, b_0),[a_0,b_0] 表示的就是数据块a_0 和b_0 的线性组合。注意:实际中Clay 码在节点上存储的是耦合后的数据,这样才能保证Clay 码的最优修复。

两个数据块的线性组合可以表示为数据块的乘法,解耦同理,如果用C(p) C*(p)表示两个耦合的数据块,解耦即乘以解耦矩阵,

γ 为不等于0的值,使得矩阵(在对应的有限域)满秩即可,比如2。

1.3 最优修复单点失效

下面以一个节点的修复来展示Clay 的最小修复开销,(4,2) 编码最小修复开销为(n-1)α/m = 3α/2 = 6,这也是其他MSR 的最小理论修复开销。下图给出了原a_2 数据块所在节点的修复过程。

Clay 修复该节点失效只需要第二层和第三层的剩余数据块(如上图(中)所示),修复步骤如下:

  1. 两个耦合的数据块(b_3,d_1) 和[b_3, d_1] 解耦得到b3 和d1,如上图(右)
  2. 第二层通过b1,b3 的MDS 解码得到b_0, b_2,第四层MDS 解码得到d_0,d_2
  3. 利用第二层中[a_2, b_0] 和步骤2 得到的b_0 得到a_2,同理得到c_2;

简单推导可以发现其他三个节点也可以以最小开销完成数据修复。

1.4 系统码

需要注意的是Clay 码这时虽然满足了所有节点的最优修复,但耦合的过程中某些数据已经不再是系统码,因为某些原始数据已经线性组合为校验数据。作者因此提出了一种“耦合-编码-再解耦”的方式来保证Clay 码的系统性(systematic),如下图所示。

首先对原始数据进行耦合,经过MDS 编码后再解耦,这样原始数据还是原始数据,但校验数据不再是MDS 编码后的校验数据了。

但如果是这样理解的话,会存在一个问题:MDS 编码前,耦合的校验数据为空,导致一个原始数据和空数据耦合,那么解耦后的数据能延续刚才的最优修复么?

换个角度,如果耦合的两个数据块中有一个是原始数据,是不是可以选课合适的耦合方程来保证原始数据不发生变化,即数据块a,b 耦合后可以是a,xa+yb(a 是原始数据)或xa+yb,b(b是原始数据)的形式么?但如果需耦合数据都是校验数据块呢?

这几个问题可以通过生成矩阵的方法来解释。

二 Clay 码的生成矩阵

本节用生成矩阵这个工具来展示如何实现Clay 码,即生成(4,2)-Clay 码的生成矩阵并验证其最优修复性质。

首先利用Clay 码“耦合 – MDS编码 – 解耦” 的变换过程构建其生成矩阵。因为三个变换都是线性变换,所以可以用三个矩阵来代替。

注意:前面我们提到解耦矩阵和耦合矩阵是互逆的,这是针对两个需要耦合/解耦数据块而言的,本节所讲的耦合、解耦矩阵是针对所有数据块,且需要在中建添加MDS 编码过程,所以本节耦合、结构矩阵大小不同,更不互逆。

|G| 是Clay 码的生成矩阵,那么

|G| = |U|×|GM|×|C|

|U|是解耦矩阵,|GM| 是MDS编码的生成矩阵,|C| 是耦合矩阵。

首先从最简单的MDS 编码矩阵 |GM| 开始,一层MDS 编码生成矩阵是一个2×2 单位矩阵和2×2 校验矩阵组合得到的4×2 的生成矩阵(如下左图所示)。四层的MDS 编码矩阵如下右图(在生成矩阵右边标出了该行向量对应的数据块)。

为了使得一个码字中原始数据部分放在一起,可以进行一个对齐操作,即将单位矩阵放在上面,新的生成矩阵为|GM|。

根据所对应数据块位置和耦合规则,可以得到解耦矩阵 |U|,如下图所示。

因为MDS 编码后,有16个数据块,所以解耦矩阵|U| 大小为16×16。

耦合矩阵是一个8×8 大小的矩阵(因为四层MDS码有8 个原始数据块,|GM| 大小是16×8)。那么利用|G| 矩阵上半部分是单位矩阵可解出耦合矩阵|C|

|G| = [I P] = |U|×|GM|×|C|  →    |C| = |I+L×GP|^{-1}

耦合矩阵|C| 是 |I+L×GP| 的逆矩阵,L 是解耦矩阵|U| 右上分块矩阵,GP是MDS 编码生成矩阵|GM| 下半部分的校验部分。

下面介绍程序验证过程。首先是测试当λ=2 时,两个数据块的耦合和解耦矩阵。

当λ=2 时,计算得到的耦合矩阵|C| = |I+L×GP|^{-1} 为

MDS 码采用RS码,|GM| 为

耦合矩阵乘积为 |GM|×|C| 为

最终(4,2)-Clay 码生成矩阵|G|为

最后,用程序验证了这个矩阵的最优修复性质,具体而言,首先将该矩阵等分为4×8 的4个子矩阵,依次失效每个子矩阵,从失效子矩阵以外的矩阵中选取行向量重建该失效子矩阵,所需要选取的子矩阵的行向量个数即需要重建数据块的数量,验证发现所有子矩阵修复都只需要6 个行向量,达到了最小修复开销。

基于FPGA SoC 的内存系统中的纠错码

原文地址:https://www.altera.com/en_US/pdfs/literature/wp/wp-01179-ecc-embedded.pdf

原文名称:Error Correction Code in SoC FPGA-Based Memory Systems

下载地址wp-01179-ecc-embedded

备注:本文是Altera 和Micron 科技的共同编写的技术白皮书。

 

 

本文分析了1. 软错误的潜在原因和影响;2. Altera 和Micron 提出的一种错误检测和纠错方法,能够使得嵌入式系统能够容忍这类软差错。

 

引言

不断进步的半导体工艺技术使得嵌入式系统集成度、功能和性能都在增加。然而,性能的增长也带了巨大的开销,高性能系统的一个负面影响就是必须花费更多精力去处理软差错。随着集成电路供应电压的下降,使得它更容易受到电磁和颗粒辐射的影响。随着嵌入式系统内存大小增大到百兆量级,自然界alpha 粒子导致的软差错可能会超出可接受的限度。另外,现代接口速度超过Gb 每秒,大量的噪声和抖动会造成数据在传输线上写入/读出外部内存时发生错误。

 

内存比特错误来源

1. 比特单元软错误

通常,被写入数据的比特单位都以电荷值表示其编程值。当向某比特单位写入新值时,将重新编程和强制电荷值变为新值。一般来说,只要基本要求满足,如供电正常,对于动态内存刷新方法有效,内存比特单元内的编程值总是确定的。

但是,存储的电荷值会受到射入内存系统外部电荷的负面影响。宇宙粒子和大气中的原子碰撞产生能量射线可能会影响到存储的电荷值。要使得内存比特单元值跳变,必须向其注入足够多的电荷才能使得其表示为一个错误的逻辑值。

宇宙射线中百分之十以上由高能alpha 粒子组成,它们能够穿透几米厚的混凝土。芯片封装材料在衰减过程中会释放出低能alpha 粒子,因为能量小,其传播的距离和影响也小。类似地,gamma 射线也是表现为宇宙射线的一种高能粒子,由自然界衰减造成。地球的大气环境对于宇宙射线和粒子是一个天然、有重要意义的屏障,但绝不是天衣无缝的。结果就是,在高海拔,如山顶上、航空系统,大气环境能够提供的保护更少,发生软错误的几率更高。

这类因为外来能量注入无意地修改内存比特单位中数值叫做单粒子翻转(single event upset, SEU)。这类错误是软错误,这类错误的原因不是因为设备的缺陷造成的,而是由于设备所在环境的外部干扰造成。一旦正确的数据因此发生重写,几乎不可能再次经历SEU而翻转回来。这类事件的可能性极小,并且随着内存容量增加而增大。

2. 硬件错误

硬件错误被被归类为功能性错误。这类错误往往是可重复的、持续性的。一个包含了内存设备的系统被制造出后,应该是没有故障的,但随着系统寿命的增加,这种状况可能发生改变。各种因素,如频繁的温度变化、电压、高湿度和物理压力,都可能会引起系统中部件的失效。这类错误可能会表现为一个内存单元或一个印制线缺陷导致的比特卡顿(bit stuck,某位比特单位读出、传输结果总是1或0)。

3. 传输错误

传输错误发生在内存比特单位和功能性单元之间的读写数据路径上。这类错误一般是因为系统中短暂地超过系统设计余量的抖动和噪声造成,因此它们与设计余量、使用系统部件质量和系统对所在环境的电能敏感度有关。

物理连接到外部内存的电感、电容数量和导线长度比片上系统(System-on-Chip,SoC)或者内存系统中的内部布线要高出几个数量级。不过,部件内部还是可能发生传输错误。Alpha 粒子和gamma 射线能够影响感应放大器和内存比特线,导致获取到错误的数据值。

图一:传输错误

4. 数据错误的影响

内存数据的损坏对于嵌入式系统的运行通常是致命的。在基于处理器的系统中,内存错误会导致指令或数据流中的值不正确。现代处理器会检测到非法指令,通常会迫使系统重新启动。数据流中的错误可能会导致程序流出轨,往往会导致非法访问受保护的内存。这些事件在桌面系统中表现为“死亡蓝屏”或“core dump”。

尽管在嵌入式系统中崩溃是令人讨厌的,但是想要有个替代方法也不是那么简单。没有立即检测出的错误可能会长时间滞留在系统中。由于错误的数据用于计算新数据,未检测到的内存错误可能会倍增。而一旦检测到错误的数据,错误的起点以及造成的后续影响将很难确定。

嵌入式系统通常运行时间较长,并不像在台式计算机那样频繁地重新启动。这给嵌入式系统带来了额外的缺点:错误将随着时间推移而累积。数据错误和系统崩溃的负面影响很多:异常行为的系统会令用户烦恼,让顾客感到不快;维护成本可能会增加,因为客户的投诉会触发对不可重现错误来源进行昂贵的调查;突然的系统故障可能会造成重型机器周围的不安全环境,而且安全系统中的错误可能会导致意外的系统访问后门。

5. 嵌入式系统中错误的可能性

硬错误率和传输错误率是许多变量的函数。在较大系统中对于这类错误的研究比较成熟,但研究结果并不能直接将应用于其他系统。另一方面,已有很多研究发布了软错误率(Soft Error Rate,SER)结果。举一个实际例子,一个有1GB 内存的嵌入式系统的平均故障间隔时间的范围在一年几次和几年一次。

MTBF 还应该考虑到该领域系统数量。系统供应商则应该考虑一个给定时间段内可能发生失效设备的总数。假设10000 台设备的MTBF 是十年,那么意味着平均每年都将有1000 台设备遭受一次单比特错误。

这种错误率的可接受性取决于应用领域。在高海拔使用的应用开发人员将关注由于宇宙射线造成的较高的SER。军事,汽车,高性能计算,通信和工业客户将更关注错误率导致的安全性和可靠性的下降。在消费领域,一年的MTBF 则有时可以被接受。然而在许多情况下,错误率造成增加维护成本和不满意的客户数量是推动解决方案的关键因素。

 

提高容错能力

1. 传输错误

Altera®SoC FPGA 支持高达533 MHz(1066 Gbps)的DDR3。 DDR3 接口规范以及SoC FPGA 与外部存储器器件中实现的方式保证了错误率可以忽略不计,因为于DDR 规范所限定的范围内具有可靠的电路板设计和抖动和噪声控制。

谷歌与多伦多大学合作进行的大规模研究以及斯坦福大学的另一项研究表明,被分析的所有系统中大部分错误仅是由系统的一个设备子集造成。这些错误很可能是由过度的抖动或噪声引起的,或可能与系统及其组件的质量不合格有关。

传输错误发生的概率会随着接口速度的增加而增大,比如DDR4 或更高。随着功耗降低和接口速度提高,电源层面的电压和信号电平也随之缩小,抖动和噪声越来越难以控制。

随着更高的接口速度而增加,例如为DDR4及更高版本所定义。随着功耗降低和接口速度提高,电源层面的电压和信号电平也随之缩小,抖动和噪声越来越难以控制。 JEDEC 指出,对于DDR4 和GDDR5 的下一代存储器规范,抖动和噪声的影响已经促使该规范允许在一定的误码率和简化设计,特性和鉴定之间权衡。任何需要容忍的误码率都将用一种有效的方法来纠正发生的错误。

2. 软错误

因为软错误是不可避免的,所以已研发出了一些方法能够使得系统对这些错误具有抵抗力。也就是说,当一个错误发生时,它能够被检测、校正并传输校正后的值,因此系统可不中断地运行。这个壮举是通过向内存数据段中添加字节实现的,那么加宽的数据段携带了足够的信息来检测和校正错误。数据字段中增加的比特越多,能够被校正的错误也就越多。这使得纠错成为成本和期望可靠性的函数。能够修正一个错误和检验出两个错误的纠错方法即具有成本效益,又被证明在嵌入式系统中提供了出色的错误恢复能力。这种在工业界被广泛应用的技术叫做纠错码(Error Correction Code,ECC)。

3. ECC 的基本实现

通过增加内存容量,并在进出额外的外部内存的通道上增加有限的组合逻辑可以实现ECC。逻辑部分用于ECC 编码,采用非常成熟的多项式汉明(Hamming)算法。一个ECC 比特产生器可以为正在存储的数据生成ECC 数据,并将ECC 数据和普通数据一起存储。ECC 检测和校正逻辑函数被插入在内存的输出端,当从内存读取数据,这个函数将检验ECC 数据和普通数据的组合。如果没有检测到错误,则直接传输普通数据而不做任何改变。如果检测到一个错误,它将纠正普通数据内的错误比特位,并返回纠正后的数据,可选择性地抛出一个异常标志。当检测到两个错误时,则抛出一个异常标识,让系统因地制宜地去响应这个事件。

图2:ECC 内存容量更大且增加额外的逻辑部件

4. ECC 优势

能够纠单错和检测出双错具有很多好处。虽然ECC 是由大内存的SER 问题推动的,但它也增加了抵御其他类型错误的能力。一个硬件单错,比如内存中的比特卡顿或印刷电路板上的不稳定连接,都能够被ECC 完全掩盖,同样单比特传输错误也同样能被解决。核心是ECC 可以校正一个数据段中的错误比特。也就是说,ECC 可以正确地处理系统中的多个错误,只要任意一个数据段中发生不超过一个比特的错误。

另一个好处ECC 逻辑能够指出系统的健康状态。当ECC 逻辑纠正了一个数据段中的单错,它还可以向处理器发送一个故障状态信号,以利于处理器采去与系统所需的可靠性相关的措施。这一手段将系统降级转化为可调度的维护任务,而不是响应意外的、致命的系统错误状况。基于启发式概率,附表分析了有ECC 和没有ECC 的系统的估计软错误模型,表明ECC 有效地增加了MBTF,使其从短于系统寿命增加到比宇宙寿命更长。

表1:ECC 使得容单错能力大大提高

 

图3:外部DDR 内存没有错误校正的软错误MTBF

Altera 和Micron ECC 解决方案

1. 外部DRAM 的ECC

为Altera SoC FPGA 的外部内存添加ECC 功能只需要增加内存数据带宽。生成ECC 比特、错误检测和校正的功能都已经内置到SoC FPGA 的内存控制器中,这样的话,虽然带宽变大,但内存具备了ECC 功能。此外,在SoC FPGA 和外部内存之间的数据通道上已经布置了ECC,因此在数据通道上也可以恢复某些传输错误。

具有16-bit 或32-bit 宽的数据通道的外部内存系统在SoC FPGA 和外存之间分别需要存储额外的6 或7 个ECC 存储位。 对于这两种情况,Altera 架构简化为定义一个额外的1 字节的ECC 内存存储位。

2. ECC DRAM 的典型架构

一个由SoC FPGA 和外部存储器组成的现代嵌入式系统可能需要包含1 GB 的DRAM。 为了实现这种系统的高性价比的32 位宽内存接口,一个典型的DRAM 可以包括并行配置的一个8位宽器件和两个16位宽器件的组合。

图4:典型的外部DDR 内存架构

3. ECC NAND 闪存

外部的NAND 闪存可以连接到SoC FPGA 器件,既可以作为一个存储引导配置的内存,也可以作为存储应用程序的文件系统。NAND 闪存对软错误非常敏感,并且经常需要ECC 保护。不同于外部DDR 内存将数据段带宽变宽,NAND 闪存提供额外的存储缓冲区来保存ECC 数据。ECC 所编码的数据块也更大,如512 或1024 字节,那么SoC FPGA 设备则能够校正高达24 比特的错误。尽管实现方式被调整为更适应NAND 闪存的一般错误模式,但恢复方法还是类似于常规的SRAM 和DRAM。

4. Altera SoC FPGA 的错误恢复

ECC功能内置于SoC FPGA器件中,用于大量片上内存实例。L2 缓存,临时RAM,FPGA 结构内部的内存和外围上作为数据缓存的内存都带宽加宽并装备上了ECC 产生器和逻辑校正器件。由于这些是内置的,使用ECC 功能不需要额外的成本。 同样地,外部内存和NAND 闪存的ECC 也内置在SoC FPGA 中。数据和指令缓存在物理大小上相对较小,因此不容易发生软错误。因为它们需要高速运行,也为了读取L1 缓存时避免额外的延迟,系统使用更简单的奇偶校验方法。

FPGA 架构内的配置数据不是以增宽的数据段来组织的,因此也没有用ECC 校验。FPGA 架构内部有一个内置的硬件引擎,允许循环地检查配置数据的正确性,当检测到一个错误时会抛出一个异常标志。这种错误校正方法称作“擦洗(scrubbing)”,也是这类设备的一种工业标准方法。Altera SoC FPGA 具有支持系统级的错误恢复所需要的逻辑器件,并集成到设备中。通过仅扩展外部DDR 内存,可以获得对软错误和传输错误具有恢复能力的通用综合系统级方法。

图5:SoC FPGA 系统级的容错能力

 

总结

嵌入式系统中的内存可能受到宇宙射线的注入而导致比特位翻转,而过度的噪声和抖动也会导致传输错误,从而使得传输的数据不正确。虽然这种错误可能性很小,但随着内存容量、接口频率和带宽的增大,这类事件的可能性越来越成为挑战。系统级错误恢复能力日益成为高性能嵌入系统设计的考虑因素。Altera SoC FPGA 设备通过擦除(scrubbing)、奇偶校验和ECC 技术实现高容错能力。它能够很方便地为外部内存增加ECC 功能,特别是兼容了高性能系统中32-bit 位宽的外部DRAM 内存。增加ECC 实际上消除了内存对这些错误的敏感性,为系统级别的容错做出了重要贡献。

 

扩展阅读

“A Second Look at Jitter: Calculating Bit Error Rates,” Justin Redd, Maxim Integrated Products:
www.eetimes.com/electronics-news/4164171/A-second-look-at-jitter-Calculating-bit-error-rates
■ “Understanding the New Bit Error Rate DRAM Timing Specifications,” Perry Kelly, Agilent Technologies:
www.jedec.org/sites/default/files/Understanding%20BER%20based%20timing%20specifications%20Agilent%202011_1101.pdf
■ “DRAM Errors in the Wild: A Large-Scale Field Study,” Bianca Schroeder, University of Toronto, Eduardo Pinheiro and Wolf-Dietrich Weber, Google Inc.:
www.cs.toronto.edu/~bianca/papers/sigmetrics09.pdf
■ “Hard Data on Soft Errors: A Large-Scale Assessment of Real-World Error Rates in GPGPU,” Imran S. Haque, Vijay S. Pande, Stanford University:
http://cs.stanford.edu/people/ihaque/papers/gpuser.pdf
■ White Paper: Enhancing Robust SEU Mitigation with 28-nm FPGAs , Altera Corporation:
www.altera.com/literature/wp/wp-01135-stxv-seu-mitigation.pdf
■ On the Need to Use Error-correcting Memory,” Berke Durak:
http://lambda-diode.com/opinion/ecc-memory

Vim 常见问题(StackOverflow 高票问题)

如何退出Vim 编辑器?

:点击 Esc 键,然后 :q 退出编辑器(或 :q! 不保存退出编辑器,或:q! 退出编辑器不保存,或 :x 等同于:wq 退出编辑器并保存))。

 

如何快速缩进多行?

:利用 > 命令, >5> 或者  5>>  缩进五行, >% 缩进一个block(需要将光标放在括号上)。

 

如何在Vim 中符号替换为换行符,:%s/,/\n/g 将会插入^@ 字符?

:用/r 代替 /n 。在Vim 中,/r 和 /n 分别插入0X00 和0X0A 字符。

 

Vim 如何高亮搜索?

set nohlsearch 关闭高亮, set hlsearch! 打开高亮。

 

如何设置搜索大小写不敏感?

: /letter\c搜索letter 且大小写不敏感,/letter\C 大小写敏感(默认);或:set ignorecase 设置大小写不敏感。

 

如何复制一行?

yy 复制一行,dd 剪切一行,p  粘贴内容在本行下一行,P 粘贴内容在本行上一行。

 

w !sudo tee % 如何实现sudo (root 权限)保存的功能?

% 表示当前文件,tee 将即输出到% 还输出到屏幕。

 

如何设置Tab 为4 个空格,并自动缩进?

:在vimrc 中添加

filetype plugin indent on
" show existing tab with 4 spaces width
set tabstop=4
" when indenting with '>', use 4 spaces width
set shiftwidth=4
" On pressing tab, insert 4 spaces
set expandtab

 

如何移动到一行的最后?

A 移动到本行最后并进入插入模式或 $ 移动到最后(普通模式,normal mode)

 

如何编辑多个文件?

:使用tabs(Vim7 中引入),:tabe <filepath> 在新tab 中打开文件,:tabn 和 :tabp 在文件之间切换。还可以通过:sp <filepath> 进行分屏,ctrl+w 在屏幕之前切换。

 

remap/map/noremap 命令

remap 是使得映射命令能够递归地映射。系统默认是开启的(建议)。map/noremapd 都是映射命令。:map 和 :noremap 是递归映射(recursive)和非递归映射(no-recursive)。

:map j gg
:map Q j
:noremap W j

j 映射为 ggQ 递归地映射为 gg。 W 将不会映射到 gg 而只会映射到 j ,因为它使用非递归映射。考虑到还有普通模式(normal)可视模式(visual),还有对应的映射命令(:nmap 和 :nnoremap)与 (:vmap 和 :vnoremap)。

 

如何关闭粘贴时的自动缩进?

:set paste 进入插入粘贴模式(显示-- INSERT (paste) --),粘贴后取消 -:set nopast。可以将<F3> 键进行映射,从而快速切换模式::set pastetoggle=<F3>

 

如何使用寄存器(registers)?

:Vim 中寄存器可以用于暂时存储文本、宏命令等,以备后面使用。

:reg a b c 打印出  a b c 寄存器中内容;"a 表示寄存器a,"ayy 复制一行到寄存器a,"ap复制到当前位置;"Ayy 将内容增添在寄存器a;"+ 是一个特殊寄存器指向系统剪切板(clipboard),"+p 将系统剪切板中的内容粘贴到当前位置; "0 – "9 是九个数字寄存器,"0 寄存器保存复制(yank)的内容,"1 – "9 按时间分别保存删除(dd)的内容。

 

如何快速注释多行?

<Ctrl>+v 进入可视块(visual block)模式,选择多行,<Shift>+i 进入插入(insert)模式,在行首加入注释符(//,#),<Esc> 键将在选择的多行前都添加注释符。

 

如何用字符显示空格?

:set listchars=eol:¬,tab:>·,trail:~,extends:>,precedes:<,space:␣

:set list (根据我的经验,不要显示空格,或者空格用点符号更美观  space:·

 

什么是记录(Vim recording)?

q<letter> 开始记录,再次按q 结束记录,并通过@<letter> 回放。它可以记录所有你输入的,比如查找,移动,替换等操作。非常有用。

 

如何删除空白行?

:g/^$/d

 

如何实现全文缩进对齐?

gg=G。 gg 跳到文件开头, = 缩进对其,G 到文件末尾。

 

如何粘贴内容到系统剪切板(clipboard),或者从系统剪切板到Vim 中?

:寄存器 "* 和 "+ 是系统剪切板寄存器,"*yy 或者 "+yy 将复制行到系统剪切板,"*p 和 "+P 粘贴到本行下一行或者上一行。(我更习惯用<shift>+<insert> 粘贴)

 

如何将(Win)dos 中文件行结束转化为Linux 行结束?

dos2unix 是专门处理这个的工具。或者使用替换命令 :%s/^M//g ,或 :set ff=unix 。

 

如何 “重做”(redo) “回退”(undo)?

u 回退,<Ctrl>+r 重做。

 

如何移动屏幕,而不需要移动光标?

zz 移动当前行到屏幕中间,zt 移动当前行到屏幕顶部,zb 移动当前行到屏幕底部。

 

如何删除行而不存在寄存器中?

"_d 删除到“黑洞”寄存器

 

查找下一个

n 查找文件的上一个,N 查找文件中上一个

 

如何设置非贪婪正则表达?

:用.\{-} 代替.* 。

 

如何设置内容超过80 列后提醒?

:在 ~/.vimrc 内添加

highlight OverLength ctermbg=red ctermfg=white guibg=#592929
match OverLength /\%81v.\+/

 

如何复制文件中所有行?

gg"*yG 复制内容到"* 寄存器。

 

如何关闭单个打开的文件缓存(e.g. vim a.txt b.txt 打开后如何关闭一个文件缓存)?

:bd 关闭当前缓冲区,:ls 列出当前所有缓冲区,:bd2 关闭第二个缓冲区。

 

^M 是什么?

:Unix 用 0xA 表示新行,Windows 则用 0xD 0xA^M 显示为 0xD 。

 

如何关闭所有选项页(tabs)?

:qa 退出所有选项,:wqa保存所有选项页并退出。

 

自动补全?

:YouCompleteMe

 

用遗传算法解决简单的数学等式问题

[翻译]原文:Genetic Algorithm for Solving Simple Mathematical Equality Problem

[翻译]地址:https://arxiv.org/ftp/arxiv/papers/1308/1308.4675.pdf

[翻译]目的:文章旨在为新手解释什么是遗传算法。并使用遗传算法这个工具一步步解决一个具体的数学问题——求解数学等式的解。

基本理念

在通过遗传算法寻找问题解的过程中,用染色体来表示一个解,一堆染色体叫做种群。染色体由基因构成,基因可以是数值的、符号的也可以是其他类型数据结构(视所解决的问题来定)。染色体通过环境适应度来衡量这个解对于问题的优劣程度。种群中的染色体通过交叉(交配)遗传到下一代,子代染色体是父代基因的组合。基因还会发生突变,遗传算法中使用交叉率和突变率来控制。

算法步骤

  1. 决定染色体数目、循环代数(决定遗传多少代)、突变率和交叉率;
  2. 产生染色体种群,并使用随机值初始化染色体中的基因
  3. 重复步骤4-8(重复次数等于循环代数)
  4. 考量每个染色体的适应值
  5. 染色体选取
  6. 交叉
  7. 变异
  8. 产生新的后代染色体
  9. 得到最终解

算术问题

以求解多元一次不等式 a+2b+3c+4d=30 为例,使用遗传算法找到a b c d 值满足该等式。很显然可以使用这样一个函数衡量适应度

f (x) = |(a + 2b + 3c + 4d) - 30|

a b c d 初始化为0到30之间的一个自然数。

步骤一 初始化                            (下面步骤不完全和算法步骤对应)

随机生成六个染色体Chromosome[1-6]。

Chromosome[1] = [a;b;c;d] = [12; 5; 23; 8]

Chromosome[2] = [a;b;c;d] = [ 2; 21; 18; 3]

Chromosome[3] = [a;b;c;d] = [10; 4; 13; 14]

Chromosome[4] = [a;b;c;d] = [20; 1; 10; 6]

Chromosome[5] = [a;b;c;d] = [ 1; 4; 13; 19]

Chromosome[6] = [a;b;c;d] = [20; 5; 17; 1]

步骤二 评估

计算每个染色体的适应度。

F_obj[1] = Abs(( 12 + 2*05 + 3*23 + 4*08 ) - 30) = 93

F_obj[2] = Abs((02 + 2*21 + 3*18 + 4*03) - 30) = 80

F_obj[3] = Abs((10 + 2*04 + 3*13 + 4*14) - 30) = 83

F_obj[4] = Abs((20 + 2*01 + 3*10 + 4*06) - 30) = 46

F_obj[5] = Abs((01 + 2*04 + 3*13 + 4*19) - 30) = 94

F_obj[6] = Abs((20 + 2*05 + 3*17 + 4*01) - 30) = 55

步骤三 选择

适应度是越小越好,我们将适应度取倒数(加1避免出现除以0的错误),并归一化得到一个概率P

Fitness[1] = 1 / (1+F_obj[1]) = 1 / 94 = 0.0106

Fitness[2] = 1 / (1+F_obj[2]) = 1 / 81 = 0.0123

Fitness[3] = 1 / (1+F_obj[3]) = 1 / 84 = 0.0119

Fitness[4] = 1 / (1+F_obj[4]) = 1 / 47 = 0.0213

Fitness[5] = 1 / (1+F_obj[5]) = 1 / 95 = 0.0105

Fitness[6] = 1 / (1+F_obj[6]) = 1 / 56 = 0.0179

总计 Total = 0.0106 + 0.0123 + 0.0119 + 0.0213 + 0.0105 + 0.0179 = 0.0845

P[1] = 0.0106 / 0.0845 = 0.1254

P[2] = 0.0123 / 0.0845 = 0.1456

P[3] = 0.0119 / 0.0845 = 0.1408

P[4] = 0.0213 / 0.0845 = 0.2521

P[5] = 0.0105 / 0.0845 = 0.1243

P[6] = 0.0179 / 0.0845 = 0.2118

从结果可以看出基因4具有最高的适应度。接下来计算累计概率分布CPD:

C[1] = 0.1254

C[2] = 0.1254 + 0.1456 = 0.2710

C[3] = 0.1254 + 0.1456 + 0.1408 = 0.4118

C[4] = 0.1254 + 0.1456 + 0.1408 + 0.2521 = 0.6639

C[5] = 0.1254 + 0.1456 + 0.1408 + 0.2521 + 0.1243 = 0.7882

C[6] = 0.1254 + 0.1456 + 0.1408 + 0.2521 + 0.1243 + 0.2118 = 1.0

%e4%bf%a1%e6%81%af

然后生成六个随机数R[i=1,2,3,4,5,6],通过这六个随机数在上图中的位置区间选择新的染色体,比如,当随机数在0.4118到0.6639之间则选择染色体4。不难看出,这种方法反应了适应度好的染色体具有更大概率被选择。

随机生成的六个随机数如果是:

R[1] = 0.201

R[2] = 0.284

R[3] = 0.099

R[4] = 0.822

R[5] = 0.398

R[6] = 0.501

那么相应的六个新的染色体是:

NewChromosome[1] = Chromosome[2] = [ 2; 21; 18; 3]

NewChromosome[2] = Chromosome[3] = [10; 4; 13; 14]

NewChromosome[3] = Chromosome[1] = [12; 5; 23; 8]

NewChromosome[4] = Chromosome[6] = [20; 5; 17; 1]

NewChromosome[5] = Chromosome[3] = [10; 4; 13; 14]

NewChromosome[6] = Chromosome[4] = [20; 1; 10; 6]

 

步骤四 交叉

假设交叉率为25%(0.25),那么生成6个随机数,如果随机数小于交叉数,则对应的染色体被选择用于交叉。比如随机数为:R[1] = 0.191, R[2] = 0.259, R[3] = 0.760, R[4] = 0.006, R[5] = 0.159,R[6] = 0.340。那么得到用于交叉的三对染色体是NewChromosome[1], NewChromosome[4] 和NewChromosome[5]。交叉方式为:

NewChromosome[1] >< NewChromosome[4]

NewChromosome[4] >< NewChromosome[5]

NewChromosome[5] >< NewChromosome[1]

下面决定从那个位置进行交叉。因为染色体长度为4,则随机生成1-(4-1) 大小的随机数,随机数用于表示基因从哪里开始交叉。

C[1] = 1 C[2] = 1 C[3] = 2

CrossChromosome[1] = [ 2; 21; 18; 3] >< [20; 5; 17; 1] = [ 2; 5; 17; 1]     // C[1] = 1

CrossChromosome[2] = [20; 5; 17; 1] >< [10; 4; 13; 14] = [20; 4; 13; 14]     // C[2] = 1

CrossChromosome[3] = [10; 4; 13; 14] >< [ 2; 21; 18; 3] = [10; 4; 18; 3]    // C[3] = 2

那么剩余的种群中则有染色体:

NewChromosome[2] = [10; 4; 13; 14]

NewChromosome[3] = [12; 5; 23; 8]

NewChromosome[6] = [20; 1; 10; 6]

CrossChromosome[1] = [ 2; 5; 17; 1]

CrossChromosome[2] = [20; 4; 13; 14]

CrossChromosome[3] = [10; 4; 18; 3] 

步骤五 突变

假设突变概率为10%(0.1)。考虑到6个染色体中每个有6个基因,那么将有4×6×0.1= 2.4 ≈ 2个基因发生突变,通过产生两个1-24范围的数值得到突变染色体位置(假设为12和18)。接着还产生两个1-30之间的随机数作为突变后的结果(假设为2 和 5)。那么得到新的种群如下(红色为突变基因):

Chromosome[1] = [10; 4; 13; 14]

Chromosome[2] = [12; 5; 23; 8]

Chromosome[3] = [20; 1; 10; 2]

Chromosome[4] = [ 2; 5; 17; 1]

Chromosome[5] = [20; 5; 13; 14]

Chromosome[6] = [10; 4; 18; 3] 

步骤六 回到步骤二进行迭代

步骤七 至循环代数次结束

步骤六和步骤七类似,不再赘述。

整个过程如下图所示:

如何为程序绑定不同的网络连接出口

问题:个人笔记本连接着手机上网(生成本地连接3),同时连接wifi(生成无线连接2),需要通过wifi远程连接服务器。如何能够正常上网(浏览器,QQ等),也可以通过wifi 远程连接服务器。

%e7%bb%98%e5%9b%be1

解决方法:将本地连接3设置为家庭网络(所有程序优先走该连接),无线连接2设置为工作或者公开网络,并通过ForceBindIP 将xshell 应用绑定到无线连接2对应的IP 地址。

注意:USB连接上手机生成的本地连接3每次在重新插上时IP 都会发生变化,所以不是很好绑定应用于该连接。无线连接2必须设置为固定IP。

STM32F10x 单片机移植Modbus

最近在做STM32F10x 单片机移植Modbus的工作。Modbus是串口通信中广泛使用的协议,为了将其移植到stm32f10x单片机中,我们通过其开源实现freeModbus 进行了协议分析。stm32f10x 是一款被广泛使用的单片机,具有能耗小、价格低、速度快和中断响应迅速等优点。

首先,本文主要对Modbus 协议分析,有少量涉及到stm32单片机的内容;其次,文章主要以从机作为分析对象。(主从机是通信的一种模式,主机用于发送指令或者查询数据,从机用于应答)。另外Modbus 只有从机开源。

文章中参考了一些网友的资料,如有需要,可以参考下面文章:

  1. STM32单片机嵌入式实战教程 (stm32单片机视频讲解)
  2. Freemodbus RTU在stm32上的移植分析    (包含Modbus 发送接收状态机)
  3. freeModbus 主机的改写 (包含主机部分代码)
  4. http://www.freemodbus.org/ (freeModbus 官网)

下面按照几个方面进行协议分析:

一、单片机上串口通信的数据帧

单片机上串口通信通过数据帧完成,但必须规定一帧的开始和结束才能够进行正常的数据读取。简单的方法就是在帧的两端定义特殊的开始字节和结束字节。但这样的话,要求数据部分不能出现与开始字节和结束字节相同的内容,且帧的开始结束都是由应用程序判断。Modbus使用更“硬件”的方法,它通过两个帧之间的时间间隔来判断一个帧,即如果两个字节相隔一段时间(如传输3.5个字符时间),则认为新的的数据是新的一帧。

二、Modbus 启动流程

我们以freeModbus 为例进行分析(从参考[4] 可以下载到freeModbus 的源代码)。源码中mb.c是Modbus 的主要接口函数,include 目录是头文件,tcp/ascii/rtu 是Modbus 支持的三种传输模式,rtu 是最常用的,本文只涉及rtu模式。

主函数main() 中包含三个部分:

eStatus = eMBInit( MB_RTU, 0x0A, 0, 38400, MB_PAR_EVEN );
eMBInit() 是初始化函数,使用“模式,端口,地址,波特率,校验”几个参数初始化系统硬件相关信息。

eStatus = eMBEnable(  );
使能函数,使得Modbus 整个协议栈工作起来。具体会做开启一些中断等工作。

for( ;; ){
( void )eMBPoll( );
}

这是从机的主要工作部分,系统经过简单的配置和使能后,就进入eMBpoll()这样的服务模式,类似于Linux 中I/O多路复用的epoll(),当有事件发生时则做出相应响应。

整个Modbus工作流程如下图,也可以看出初始化、使能和eMBPoll()服务三个部分。

untitled-flowchart

初始化:eMBInit()在mb.c中根据定义的是rtu 还是asccii等模式会给接口函数(函数指针)进行初始化,这样的好处是对应于不同的模式使用统一的接口函数。当模式为rtu时:

pvMBFrameStartCur = eMBRTUStart;     \\开始接收数据帧
pvMBFrameStopCur = eMBRTUStop;       \\停止接收数据帧
peMBFrameSendCur = eMBRTUSend;       \\数据帧已经发送
peMBFrameReceiveCur = eMBRTUReceive; \\数据帧接收完毕
pvMBFrameCloseCur = MB_PORT_HAS_CLOSE ? vMBPortClose : NULL;
pxMBFrameCBByteReceived = xMBRTUReceiveFSM;       \\接收到数据帧内一个Byte
pxMBFrameCBTransmitterEmpty = xMBRTUTransmitFSM;   \\接收到空
pxMBPortCBTimerExpired = xMBRTUTimerT35Expired;    \\发生T35 中断

其中,然后就进入了rtu模式下的初始化eMBRTUInit(),其中主要是对串口中断和时钟中断进行的初始化(xMBPortSerialInit()和xMBPortTimersInit())。串口中断会开启相应的RCC时钟,配置GPIO口,配置串口模式(速率等),这和一般的单片机串口通信初始化类似;时钟中断初始化也是要开启相应的RCC时钟,设置时钟模式。需要指出:

Modbus用3.5个字符传输时间间隔作为隔断数据的判断依据,即从时钟中断使能开始,3.5个字符传输时间发起一次中断,记作T35

但当速率超过19200时,则使用固定的时间作为中断依据,这些都在eMBRTUInit()源码中有注释。

使能:eMBEnable()是Modbus 的使能函数,主要是通过函数pvMBFrameStartCur()(rtu模式下指向eMBRTUStart())进行串口中断和时钟中断使能。使能就是使得相应功能能够正常开始工作了。

基于事件的服务模式:eMBPoll()用于循环询问是否有新来事件,有则处理。

三、基于事件驱动的服务模式

从eMBPoll() 源码可以看出:

eMBpoll() 使得整个系统处于一个事件驱动的工作模式,当有新事件到达则处理它,否则就一直循环询问。

进入mb.c 中的eMBpoll() 函数可以看到,首先使用

xMBPortEventGet( &eEvent )

获取可能的事件信息,可能的事件有:

  • EV_READY:准备事件,可以开始接收数据了;
  • EV_FRAME_RECEIVED:数据帧到达事件,如果是发给自己的数据帧,则发起一个EV_EXECUTE 的事件;
  • EV_EXECUTE:执行事件,根据已定义的功能码和功能函数对数据帧进行相应处理 (eException = xFuncHandlers[i].pxHandler( ucMBFrame, &usLength ););
  • EV_FRAME_SENT:数据帧已经发送状态

那么什么时候系统会产生事件呢:中断和状态改变。当发生中断时,中断处理函数可能修改系统所处状态,并发起事件。系统中可以使用xMBPortEventPost() 发起事件。

四、各种状态

系统设置了几类状态,如eMBErrorCode 类型的eStatus 表示整个系统的总体状态,有下面几种:

  • MB_ENOERR,            /*!< no error. */
  • MB_ENOREG,            /*!< illegal register address. */
  • MB_EINVAL,               /*!< illegal argument. */
  • MB_EPORTERR,        /*!< porting layer error. */
  • MB_ENORES,             /*!< insufficient resources. */
  • MB_EIO,                      /*!< I/O error. */
  • MB_EILLSTATE,          /*!< protocol stack in illegal state. */
  • MB_ETIMEDOUT        /*!< timeout error occurred. */

eMBState 表示Modbus 协议在系统中的状态,有以下几种:

  • STATE_ENABLED
  • STATE_DISABLED
  • STATE_NOT_INITIALIZED

另外还有数据接收流程和数据发送流程中的不同状态,数据接收状态eRcvState有:

  • STATE_RX_INIT,         /*!< Receiver is in initial state. */
  • STATE_RX_IDLE,        /*!< Receiver is in idle state. */
  • STATE_RX_RCV,         /*!< Frame is beeing received. */
  • STATE_RX_ERROR     /*!< If the frame is invalid. */

数据发送状态eMBSndState有:

  • STATE_TX_IDLE,      /*!< Transmitter is in idle state. */
  • STATE_TX_XMIT       /*!< Transmitter is in transfer state. */

接收状态eRcvState和发送状态eMBSndState都在mbrtu.h/c 中定义,并在mbrtu.c中实现了接收/发送过程的状态机(xMBRTUReceiveFSM和xMBRTUTransmitFSM)。

五、两类状态机

xMBRTUReceiveFSM()和xMBRTUTransmitFSM()两个函数在mbrtu.c中实现了接收和发送过程中的状态机,两种状态机的状态变化在参考[2]中有详细描述,这里引用文中的图。

中断时改变发送接收状态的唯一手段,所以我们必须知道有哪些中断会改变发送和接收状态,从两个状态机来看,无非两种:数据到达或者发送的串口中断和T35对应的时钟中断。

六、两类中断

Modbus 在启动时进行了串口中断初始化和时钟中断初始化,两类中断在有字节到达串口和过了T35时间时会发生中断。串口USART1的中断处理函数为USART1_IRQHandler(),时钟TIM2的中断函数为TIM2_IRQHandler()。前者在portserial.c 中,后者在porttimer.c 中。

下图是串口USART1的中断处理流程,流程中可能不完全包括对发送和接收状态的修改,具体需要在源码中查看。

uart-interrupt-and-fsm

当捕捉到USART1串口中断时,首先判断是接收中断还是发送中断。在接收第一个字节后,会将发送空闲状态(STATE_RX_IDLE)变化为接收状态(STATE_RX_RCV),此后只要不溢出接收缓冲区就一直接收,没接收一个字符,无论哪个状态都要调用vMBPortTimerEnable()重置时钟中断。接收数据首先要求发送处于发送空闲状态(STATE_RX_IDLE),然后逐个发送数据。

timer-interrupt

当时钟TIM2中断使能后,每过T35时间系统就会发起TIM2的中断,并由porttimer里的TIM2_IRQHandler() 函数处理,中断处理函数根据数据接收状态(eRcvState)发起不同的事件,如当系统处于初始化状态(STATE_RX_INIT)过了T35时间,表示系统可以进入准备状态(发起准备系统准备EV_READY)接收数据了;如果系统处于数据接收状态,则表示数据数据已经接收完毕(还记得串口中断中如果一直有连续数据进来,则接收一个字节就重新使能时钟中断);vMBPortTimersDisable()最后失效所有时钟中断(没关系当接收状态发生改变时,系统中断会被开启)。

 

以上赘言是个人总结和网络资料的汇编。