面向申威众核处理器的LZMA并行算法设计与优化
发布时间：2021-10-08 17:28
随着高性能计算和科学计算应用的发展,高性能计算集群系统传输、存储和处理的数据规模呈现爆炸式增长。对大规模数据进行高效的压缩,减少数据存储所需空间和传输所需的通信带宽,是提升高性能计算集群系统性能的关键之一。无损压缩算法中,LZMA算法具有较高的压缩率,但串行版本的LZMA算法压缩速率很慢。采用多核架构的处理器对无损压缩算法进行并行化,是提升压缩速率的一个研究方向。设计并实现了面向申威26010异构众核处理器并行化LZMA算法。结合申威异构众核处理器的特点,对LZMA算法存储空间需求、访存特性、热点函数等进行分析,基于Athread接口实现LZMA算法从核多线程并行,并对LDM地址空间进行细粒度的布局与优化以获得更好的缓存性能,实现DMA双缓冲的循环滑动窗口算法。测试结果表明,相较主核串行版本算法,并行LZMA算法在Silesia语料库基准测试集和大规模数据集中分别获得了4.1倍和5.3倍的最大加速比,获得了较好的加速效果。
【文章来源】：计算机科学与探索. 2020,14(09)北大核心CSCD
【文章页数】：9 页
【部分图文】：
从核CPE存储层次结构图
LZMA算法支持4 KB到上百MB的字典空间，在提升压缩率的同时也导致其搜索缓存空间变得很大。为了减小匹配最长的字符串所需时间，快速搜索匹配字符，LZMA算法实现中，将多个可能的最长匹配存储于Hash散列表中，使用Hash链表或二叉查找树的数据结构来查找匹配数据。如图4所示，Hash函数中，将搜索缓存头两个字节的散列值作为一个散列数组的索引，散列数组存放着对应匹配字符组的起始位置。该散列数组大小为字典大小一半的2的整次幂。LZMA编码器针对2、3、4个相邻字节设置了不同级别的散列函数，用以实现对应不同字典大小的高效定位。图4 基于Hash查表的LZMA滑动窗口算法示意图
神威太湖之光异构众核计算系统[11]中，基本单元为一个申威异构众核处理器和32 GB内存与其他控制器组成的计算节点，其处理器体系结构如图1所示。256个计算节点构成一个超节点，总计160个超节点提供93PFLOPS的实测性能。其中，从核采用轻量级的核心设计，其指令集功能非常精简，不支持中断等操作，仅在用户态下运行。每个从核包含16 KB指令L1级cache和64 KB LDM(local directive memory，片上局部数据空间），支持256位向量操作。从核可与主核共享内存，采用DMA(direct memory access）方式进行内存与LDM的数据交换。从核阵列中，处于同一行或列的从核可通过寄存器通信方式进行数据交换，每次传输数据量最大为256 bit，延迟较低。图2为从核CPE(computing processing element）存储层次结构图。从核可通过寄存器直接访存和寄存器LDM访存两种方式读取数据。由于主核与从核之间没有共享缓存，寄存器直接访存的延迟达到近百个时钟周期。解决问题的方式之一就是通过DMA方式将数据拷贝至LDM进行访存来提高访存速度。这增加了并行程序设计的难度，需要程序合理地设置DMA调度策略，尽可能实现计算通信重叠，提高并行效率。从核间数据交换，可采用寄存器通信方式进行。根据主从并行编程模型的特点，神威太湖之光提供了Athread加速线程库，分为主核加速线程库和从核加速线程库两部分。
【参考文献】：
期刊论文
[1]The Sunway Taihu Light supercomputer:system and applications[J]. Haohuan FU,Junfeng LIAO,Jinzhe YANG,Lanning WANG,Zhenya SONG,Xiaomeng HUANG,Chao YANG,Wei XUE,Fangfang LIU,Fangli QIAO,Wei ZHAO,Xunqiang YIN,Chaofeng HOU,Chenglong ZHANG,Wei GE,Jian ZHANG,Yangang WANG,Chunbo ZHOU,Guangwen YANG. Science China（Information Sciences）. 2016(07)
本文编号：3424624
【文章来源】：计算机科学与探索. 2020,14(09)北大核心CSCD
【文章页数】：9 页
【部分图文】：
从核CPE存储层次结构图
LZMA算法支持4 KB到上百MB的字典空间，在提升压缩率的同时也导致其搜索缓存空间变得很大。为了减小匹配最长的字符串所需时间，快速搜索匹配字符，LZMA算法实现中，将多个可能的最长匹配存储于Hash散列表中，使用Hash链表或二叉查找树的数据结构来查找匹配数据。如图4所示，Hash函数中，将搜索缓存头两个字节的散列值作为一个散列数组的索引，散列数组存放着对应匹配字符组的起始位置。该散列数组大小为字典大小一半的2的整次幂。LZMA编码器针对2、3、4个相邻字节设置了不同级别的散列函数，用以实现对应不同字典大小的高效定位。图4 基于Hash查表的LZMA滑动窗口算法示意图
神威太湖之光异构众核计算系统[11]中，基本单元为一个申威异构众核处理器和32 GB内存与其他控制器组成的计算节点，其处理器体系结构如图1所示。256个计算节点构成一个超节点，总计160个超节点提供93PFLOPS的实测性能。其中，从核采用轻量级的核心设计，其指令集功能非常精简，不支持中断等操作，仅在用户态下运行。每个从核包含16 KB指令L1级cache和64 KB LDM(local directive memory，片上局部数据空间），支持256位向量操作。从核可与主核共享内存，采用DMA(direct memory access）方式进行内存与LDM的数据交换。从核阵列中，处于同一行或列的从核可通过寄存器通信方式进行数据交换，每次传输数据量最大为256 bit，延迟较低。图2为从核CPE(computing processing element）存储层次结构图。从核可通过寄存器直接访存和寄存器LDM访存两种方式读取数据。由于主核与从核之间没有共享缓存，寄存器直接访存的延迟达到近百个时钟周期。解决问题的方式之一就是通过DMA方式将数据拷贝至LDM进行访存来提高访存速度。这增加了并行程序设计的难度，需要程序合理地设置DMA调度策略，尽可能实现计算通信重叠，提高并行效率。从核间数据交换，可采用寄存器通信方式进行。根据主从并行编程模型的特点，神威太湖之光提供了Athread加速线程库，分为主核加速线程库和从核加速线程库两部分。
【参考文献】：
期刊论文
[1]The Sunway Taihu Light supercomputer:system and applications[J]. Haohuan FU,Junfeng LIAO,Jinzhe YANG,Lanning WANG,Zhenya SONG,Xiaomeng HUANG,Chao YANG,Wei XUE,Fangfang LIU,Fangli QIAO,Wei ZHAO,Xunqiang YIN,Chaofeng HOU,Chenglong ZHANG,Wei GE,Jian ZHANG,Yangang WANG,Chunbo ZHOU,Guangwen YANG. Science China（Information Sciences）. 2016(07)
本文编号：3424624
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/3424624.html
