.516 智能系统学报 第11卷 2)当i<n/8时执行如下步骤：否则转3)。 如整数的加、减、比较、比特运算及移位等仅需一个 ①X=E:,H=X≥4，L=E:A0xF 时钟周期(eycle)。但数据加载的执行时间则有很 ②C4[H]=C[H]+1, 多因素，无法以准确的值计量。这里仅做粗略估计， C4[L]=C4[L]+1, 因此加速数据加载也仅需要一个时钟周期。这样一 Cs[X]=C[x]+1, 来原算法对一个样本进行检测的粗略估计时间为 ③i=i+1。 64M个时钟周期，算法1对一个样本进行检测的粗 3)计算两个统计值V,和V。 略估计时间为6M个时钟周期，以此法粗略估计，算 .-4芝ca-子 法1的检测速度为原算法的10.7倍左右。当然，此 =0 处为不精确的粗略估计而已，具体的速度提升情况 2048/ n c,9)-号 以实验为准。 :=0 4)如果V,<入且Vg<入g,则认为待检序列通 5模拟实验测试 过检测。否则未通过。 为更准确地说明本文提出的算法的效率，本节 算法1的主要优化方式是直接对输入的待检序 测试优化前后算法的执行效率。 列按字节而不是比特进行处理，减少了大量不必要的 测试数据是利用我国的分组密码算法SM4算 数据拆分为单比特等操作；并且将两种参数下的频数 法生成的10°bit的伪随机数据，按样本大小10比 统计合并在一起，避免了大量的数据加载等操作。 特划分为1000个样本。 4优化前后计算量分析与对比 测试平台为Intel Core i3@3400MHz处理器、4 GB DDR316 00MHz内存、Windows XP SP3操作系 本节对优化前的算法和优化后的算法的计算量 统、Visual Studio2008编译器。处理器的缓存情况 进行定量评估与对比。 为：一级缓存为每个核心32KB,二级缓存为每个核 原算法的2)~4)的计算量都很小，因此本节在 心64KB,三级缓存为多核共享3MB。 进行计算量评估对比时，只比较最关键最耗时的步 模拟实验使用的代码情况如下。优化前的测试 骤统计频数所需要的运算量。为简化表示，将n比 代码来源是先从NIST的官方网站取得检测代码，然 特二元序列的字节长度记为M,M=n/8。而且通常 后按原算法以及NST代码思想对以比特表示的二 情况下输入的二元序列都是以字节表示，因此这里 元序列，按比特操作实现扑克检测，NIST代码完成 默认待检二元序列的比特长度n能被8整除。 字节序列转比特表示的二元序列的相关功能。优化 根据第2节的分析结果知，对一个n=10bit 后的代码（参见附录）是对以字节表示的序列按算 (M=125×103字节)的样本而言，原算法1)的计 法1的步骤以字节处理为主实现扑克检测。所有的 算量为16M次SHFT、16M次L0AD和32M次 算法都采用标准C实现。 ADD。扑克检测优化算法1的1)进行简单分析可 实验采用欧洲estream算法竞赛的速度测试模 知，对一个n=10bit的样本而言，算法1的2)的计 型的简化版本，该测试模型不仅在estream算法竞赛 算量为M次SHIFT、M次LOAD、M次AND和3M次 中采用，后续许多算法的性能评估也常采用该测试 ADD。原算法和优化算法（算法I)的运算量详情以 模型。具体来讲速度测试流程如下。1)在被测试 及对比情况见表2。 代码段的前后各设置一个时间计数器T,和T。;2) 表2两个算法的运算量对比 Table 2 The performance comparison of two algorithms 将两个计时器之差T=T。-T,作为这段代码的耗 时：3)重复1)和2)多次，为统计方便设定重复次数 运算 原算法 算法1 为奇数，记重复次数为C,得到一系列的耗时值 LOAD 16M M T[i],1≤i≤C:4)将统计得到的耗时值序列按从 SHIFT 16M M 大到小的顺序排列得到T[1]≥T[2]≥…≥ AND 0 M T[C],当然也可按从小到大的顺序排列：5)取新 ADD 32M 3M 序列的中值T'[(C+1)/2]作为本段代码的统计耗 由表2可知，优化后的扑克检测的计算量显著 时值。W为了保证测试结果的准确性，本测试模型 降低。 中1)的时间计数器使用CPU频率计时器，直接调 在现在的CPU中，常见的整数运算都比较快， 用汇编指令RDTSC,在Windows环境下也可调用_２）当 ｉ ＜ ｎ ／ ８ 时执行如下步骤；否则转 ３）。 ① Ｘ ＝ Ｅｉ ， Ｈ ＝ Ｘ ≫ ４， Ｌ ＝ Ｅｉ ∧ ０ｘＦ ② Ｃ４ ［Ｈ］ ＝ Ｃ４ ［Ｈ］ ＋ １， Ｃ４ ［Ｌ］ ＝ Ｃ４ ［Ｌ］ ＋ １， Ｃ８ ［Ｘ］ ＝ Ｃ８ ［Ｘ］ ＋ １， ③ ｉ ＝ ｉ ＋ １。 ３）计算两个统计值 Ｖ４ 和 Ｖ８ 。 Ｖ４ ＝ ６４ ｎ ∑ １５ ｉ ＝ ０ Ｃ４ ［ｉ］ ２ ( ) － ｎ ４ Ｖ８ ＝ ２ ０４８ ｎ ∑ ２５５ ｉ ＝ ０ Ｃ８ ［ｉ］ ２ ( ) － ｎ ８ ４）如果 Ｖ４ ＜ λ４ 且 Ｖ８ ＜ λ８ ，则认为待检序列通 过检测。 否则未通过。 算法 １ 的主要优化方式是直接对输入的待检序 列按字节而不是比特进行处理，减少了大量不必要的 数据拆分为单比特等操作；并且将两种参数下的频数 统计合并在一起，避免了大量的数据加载等操作。 ４ 优化前后计算量分析与对比 本节对优化前的算法和优化后的算法的计算量 进行定量评估与对比。 原算法的 ２） ～４）的计算量都很小，因此本节在 进行计算量评估对比时，只比较最关键最耗时的步 骤统计频数所需要的运算量。 为简化表示，将 ｎ 比 特二元序列的字节长度记为 Ｍ， Ｍ ＝ ｎ ／ ８。 而且通常 情况下输入的二元序列都是以字节表示，因此这里 默认待检二元序列的比特长度 ｎ 能被 ８ 整除。 根据第 ２ 节的分析结果知，对一个 ｎ ＝ １０ ６ ｂｉｔ （ Ｍ ＝ １２５ × １０ ３ 字节）的样本而言，原算法 １）的计 算量 为 １６Ｍ 次 ＳＨＩＦＴ、 １６Ｍ 次 ＬＯＡＤ 和 ３２Ｍ 次 ＡＤＤ。 扑克检测优化算法 １ 的 １） 进行简单分析可 知，对一个 ｎ ＝ １０ ６ ｂｉｔ 的样本而言，算法 １ 的 ２）的计 算量为 Ｍ 次 ＳＨＩＦＴ、Ｍ 次 ＬＯＡＤ、Ｍ 次 ＡＮＤ 和 ３Ｍ 次 ＡＤＤ。 原算法和优化算法（算法 １）的运算量详情以 及对比情况见表 ２。 表 ２ 两个算法的运算量对比 Ｔａｂｌｅ ２ Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｗｏ ａｌｇｏｒｉｔｈｍｓ 运算 原算法 算法 １ ＬＯＡＤ １６Ｍ Ｍ ＳＨＩＦＴ １６Ｍ Ｍ ＡＮＤ ０ Ｍ ＡＤＤ ３２Ｍ ３Ｍ 由表 ２ 可知，优化后的扑克检测的计算量显著 降低。 在现在的 ＣＰＵ 中，常见的整数运算都比较快， 如整数的加、减、比较、比特运算及移位等仅需一个 时钟周期（ ｃｙｃｌｅ）。 但数据加载的执行时间则有很 多因素，无法以准确的值计量。 这里仅做粗略估计， 因此加速数据加载也仅需要一个时钟周期。 这样一 来原算法对一个样本进行检测的粗略估计时间为 ６４Ｍ 个时钟周期，算法 １ 对一个样本进行检测的粗 略估计时间为 ６Ｍ 个时钟周期，以此法粗略估计，算 法 １ 的检测速度为原算法的 １０．７ 倍左右。 当然，此 处为不精确的粗略估计而已，具体的速度提升情况 以实验为准。 ５ 模拟实验测试 为更准确地说明本文提出的算法的效率，本节 测试优化前后算法的执行效率。 测试数据是利用我国的分组密码算法 ＳＭ４ 算 法生成的 １０ ９ ｂｉｔ 的伪随机数据，按样本大小 １０ ６ 比 特划分为 １ ０００ 个样本。 测试平台为 Ｉｎｔｅｌ Ｃｏｒｅ ｉ３ ＠ ３４００ＭＨｚ 处理器、４ ＧＢ ＤＤＲ３ １６００ＭＨｚ 内存、Ｗｉｎｄｏｗｓ ＸＰ ＳＰ３ 操作系 统、Ｖｉｓｕａｌ Ｓｔｕｄｉｏ ２００８ 编译器。 处理器的缓存情况 为：一级缓存为每个核心 ３２ ＫＢ，二级缓存为每个核 心 ６４ ＫＢ，三级缓存为多核共享 ３ ＭＢ。 模拟实验使用的代码情况如下。 优化前的测试 代码来源是先从 ＮＩＳＴ 的官方网站取得检测代码，然 后按原算法以及 ＮＩＳＴ 代码思想对以比特表示的二 元序列，按比特操作实现扑克检测，ＮＩＳＴ 代码完成 字节序列转比特表示的二元序列的相关功能。 优化 后的代码（参见附录）是对以字节表示的序列按算 法 １ 的步骤以字节处理为主实现扑克检测。 所有的 算法都采用标准 Ｃ 实现。 实验采用欧洲 ｅｓｔｒｅａｍ 算法竞赛的速度测试模 型的简化版本，该测试模型不仅在 ｅｓｔｒｅａｍ 算法竞赛 中采用，后续许多算法的性能评估也常采用该测试 模型。 具体来讲速度测试流程如下。 １） 在被测试 代码段的前后各设置一个时间计数器 ＴＳ 和 ＴＦ ；２） 将两个计时器之差 Ｔ ＝ ＴＦ － Ｔｓ 作为这段代码的耗 时；３）重复 １）和 ２）多次，为统计方便设定重复次数 为奇数，记重复次数为 Ｃ， 得到一系列的耗时值 Ｔ［ｉ］ ， １ ≤ ｉ ≤ Ｃ ；４）将统计得到的耗时值序列按从 大到小的顺序排列得到 Ｔ′［１］ ≥ Ｔ′［２］ ≥ … ≥ Ｔ′［Ｃ］ ，当然也可按从小到大的顺序排列；５） 取新 序列的中值 Ｔ′［（Ｃ ＋ １） ／ ２］ 作为本段代码的统计耗 时值。 ｗ 为了保证测试结果的准确性，本测试模型 中 １）的时间计数器使用 ＣＰＵ 频率计时器，直接调 用汇编指令 ＲＤＴＳＣ，在 Ｗｉｎｄｏｗｓ 环境下也可调用＿＿ ·５１６· 智 能 系 统 学 报 第 １１ 卷