Spark环境下基于数据倾斜模型的Shuffle分区优化方案

针对Spark分布式平台在shuffle阶段中导致数据量分配不均衡的问题，首先分析了Spark平台中数据倾斜的原因，建立了一个可以统一量化shuffle后key-value数据倾斜程度的倾斜模型；基于倾斜模型提出了一个可以解决Spark平台中多种数据倾斜问题的shuffle分区方案.该分区方案首先对Map阶段的输出数据进行采样，预测出全局中间数据的大小，再根据基于哈希的最佳适应算法对采样数据进行预分区，得到一张预分区表，最后根据预分区表对全部的中间数据完成分区.在key和value这2种不同倾斜情况下的实验结果表明，该shuffle分区方案具有普适性和高效性，可以有效处理key和value倾斜的情况.     

基于Spark的自适应差分进化极限学习机研究

为了解决传统自适应差分进化极限学习机（SaDE-ELM）在单机环境下运行效率低下的问题,本文提出了基于Spark平台的并行化自适应差分进化极限学习机算法（PSaDE-ELM）。该算法的主要思想是:将差分进化算法中的原始种群均匀地分割为几个子种群,每个子种群均占有RDD的一个分区,在每个分区中使用SaDE-ELM算法独立进化,并且周期性地将各个子种群中的最优个体按照一定的拓扑结构替换掉其他子种群的最差个体,以此来达到各个子种群共同进化的目的。实验结果表明:PSaDE-ELM算法的预测准确率与SaDE-ELM算法相比基本没有丢失,且随着数据集样本数或子种群数量的增加,算法的运行效率至少提升了1.5倍,在一定程度上证明了本文提出的并行化算法的有效性。     

基于多槽哈夫曼Trie树的规则引擎快速匹配算法

为了提高机场类企业数据在海量规则集合中的匹配能力,提出了基于多槽哈夫曼Trie树（MSTHTrie）的规则引擎快速匹配算法。该算法充分利用了规则点属性名数与规则条数之间的不对称特性,将对规则的线性比对转换为对多槽的并行比对,从而在稳定的空间复杂度下提高了规则引擎的匹配效率。首先对通用规则进行了严格的形式化描述,并在合理假设条件下证明了槽内规则分布命题和动作数定理;然后基于动作数定理提出了简化操作符的MSHtree算法;随之扩展操作类型提出了MSHTrie算法,使规则引擎有了普适性;最后在国内枢纽机场的业务数据上完成对比实验,表明新算法在空间复杂度上较传统线性匹配算法节约了52.6%,匹配性能上与Policytree算法相比提高了21.3%。     

基于云计算平台的并行DBSCAN算法

DBSCAN算法是一种典型的基于密度的聚类算法,具有速度快、可以发现噪声的优点,但在处理大规模数据时出现聚类效率低、内存和I/O消耗大、聚类精度降低的问题,集群式计算机技术特别是云计算技术的发展提供了解决DBSCAN算法缺陷的方案.文中提出了数据预分区的并行PMDBSCAN算法,该算法在聚类之前对数据分区预处理,利用并行编程模型MapReduce实现DBSCAN算法并行化,结合重叠分区思想,减少I/O消耗.实验结果表明,在大规模数据集上,PMDBSCAN算法聚类有效提高了聚类的速度、减少了I/O消耗、改善了聚类的质量.     

异构数据库信息集成冲突检测和消解策略

为了进一步解决异构数据库信息集成中冲突的检测和消解问题,在深入分析冲突产生原因的基础上,提出了数据冲突层次分类模型及相应的冲突解决策略.并对模式结构冲突给出了基于属性空间的模式结构冲突解决算法,把模式结构冲突的解决转换为可度量的矢量空间求解,提高了信息集成的效率和自动化程度.     

一种高效的H.264 CABAC解码器的VLSI结构

提出一种H．264／AVC中基于上下文的自适应二进制算术编码（CABAC）解码器的硬件设计方法．在采用并行结构的基础上．给出了一种高效的VLS1实现方案．采用两级有限状态机结构控制宏块解码过程，共通过对残差系数存储器的定时清零解决了数据存储耗时的问题，大大降低了解码控制的复杂度．从而提高解码速度．达到每1至2个时钟解出1比特．仿真结果表明，该方案能满足H.264／AVC main profile CIF 30fps实时解码的要求．     

三维电磁场有限元数据到有限差格式的转换算法

为实现电磁场作用下三维凝固传输过程高效率有限元/有限差(FEM/FDM)耦合数值计算,针对任意三维ANSYS有限元剖分网格与有限差网格间不规则空间几何对应关系,并基于有限元数值插值原理,提出了一种将三维有限元网格节点上的场量计算结果转换为有限差格式数据的算法.采用基于Visual Fortran6.6A平台的QuickWin模块及Fortran95语言编写了三维数据转换和后处理图形显示程序.经冷坩埚电磁定向凝固等工艺三维电磁场有限元计算结果的FEM→FDM数据转换及三维矢量/标量场结果显示,表明该算法及计算与显示程序是成功和有效的,可为后续基于有限差法的电磁凝固传输耦合计算提供可靠的电磁场数据和有效的图示分析手段.     

基于工业基础类的建筑物3D Tiles数据可视化

针对目前建筑信息模型（BIM）与地理信息系统（GIS）集成方案网络传输与浏览器渲染能力的不足,选择GIS领域更适合Web端加载的三维瓦片数据作为研究目标,提出BIM模型从工业基础类（IFC）向3D Tiles数据格式的转化方法和在Web端快速加载BIM模型的思路,并对GIS和BIM在Web端的大体量数据集成方案进行研究. 针对IFC标准模型数据,根据建筑构件划分标准对数据进行拆分,得到几何信息文件和语义属性文件. 几何信息文件经中间格式转换,最终与语义属性文件封装为保留有BIM语义属性的三维瓦片数据. 在转换过程中完成了坐标转换、数据映射、空间索引以及多细节层级（LOD）划分,实现了BIM数据和地理要素数据在三维WebGIS框架下快速、高效的渲染交互.     

面向光传输网的Polar-LDGM码方案

针对光传输网（OTN）对纠错码低实现复杂度、逼近香农限性能和无错误平层的要求,提出了一种基于Polar码和低密度生成矩阵（LDGM）码的低复杂度高速级联码方案。首先针对级联模型阐述了Polar-LDGM码的编码设计方案,并分析了编码复杂度。然后基于两种码的结构特点,给出了基于置信传播（BP）算法的级联解码算法。通过合理利用高斯逼近（GA）法推导解码算法中传递消息的均值,能够准确地预测出Polar-LDGM码的理论错误概率。仿真结果表明,Polar-LDGM码满足在OTN中应用的要求。     

基于直线方向搜索的光线空间数据压缩方法

为了提高光线空间数据的压缩效率，提出了一种基于直线方向搜索的数据压缩方法.基于光线空间描述，讨论了其数据相关性和数据分布特性.在光线空间的数据压缩中，计算了数据的相关系数，采用二维离散余弦变换（DCT）进行了变换域分析.在片间预测中，通过对光线空间片的纹理统计，确立初始的搜索方向，实现分层的直线方向搜索方法.以复杂度失真最优化作为层间判别准则，通过引入自适应阈值实现块匹配.实验结果表明，与全搜索方法相比，该方法计算复杂度明显降低，同时保持了近似的解码图像质量和编码码率，进一步提高光线空间数据的编码效率.     

动态3D虚拟场景并行化光线跟踪加速结构设计

为提高光线与虚拟场景几何面片求交的计算效率,提出一种基于混合模式的空间加速结构。该方法改进传统的层次包围盒,把细分层次包围盒与空间均匀网格划分相结合,实现了可并行的混合空间加速设计。此外,把帧间可重用的数据抽取至数据缓存,建立多几何群组的加速结构共享,实现了光线跟踪算法的并行优化。实验证明,该混合加速结构能有效加快光线跟踪的光线场景求交判断速度,快速实现光线跟踪并行化计算。     

一种高吞吐率的系统Raptor码并行译码方法

在系统Raptor码译码中，针对高复杂度的高斯消元运算导致译码延时大、吞吐率低的问题，提出一种低延时高吞吐率的降维并行译码方案。该方案采用仅对少量丢包译码的低复杂度降维运算，替换对全部源数据包译码的高斯消元运算，降低译码延时；并针对降维译码采用全并行的硬件结构实现，提高译码吞吐率。依此方案，在Xilinx FPGA XC7K410T平台上实现系统Raptor译码器。测试结果表明，当网络丢包率在10-2以下时，译码数据吞吐率达到3.5 Gbps，是相同硬件下采用高斯消元译码实现的80倍以上。     

基于SVM的汉语句子片段划分

针对长句子引起句法分析性能下降的问题,本文提出了一种基于SVM的句子片段划分方法:先根据语法结构将句子划分为多个片段,识别出每个片段的类别;然后根据片段的类别将句子分割为几个部分,每个部分作为句法分析的基本单元;最后将句法分析之后的各个部分进行合并,形成完整的分析结果.该方法减小了句法分析的复杂度,提高了分析的准确率.     

基于确定信息的直接语法分析

分析了句子中确定信息的特征,将其归结为不同层次的模式.分别对模式进行了形式化,对相同层次的模式赋予不同的优先级.利用这些确定信息,提出一个不经过词性消歧的直接语法分析算法:首先分析确定的信息,减少搜索空间,获得更多确定信息,并不断利用已有的信息进行深入的分析,最终导出正确的分析结果.实验显示:该算法精确率和召回率分别达到92.90%和91.47%.     

用于LDPC码快速译码的改进加权比特翻转算法

为了提高低密度奇偶校验码（LDPC）译码器的译码速度,提出了一种基于部分并行比特选择机制的快速多比特翻转算法.根据接收向量中错误具有随机分布的特点,将所有比特划分成若干子块,从每个子块挑选出1个候选翻转比特,再从这些候选比特中挑选出合理数目的比特进行翻转,完成译码迭代.此外,通过引入树形搜索和数据池技术降低该算法核心模块的计算复杂度,以进一步增加算法硬件实现时的译码速度.分析结果表明,相较于多比特翻转算法,利用所提出的算法和相关硬件实现技术,译码器的吞吐量能得到明显的提高.仿真结果验证了快速多比特翻转算法的有效性.     

LDPC码的并行译码算法

基于低密度校验(LDPC)码置信传播译码算法,综合译码性能、复杂度和延时,提出了低复杂度并行译码算法. 该算法通过对校验节点传递给比特节点的信息进行有效简化,使计算复杂度接近“最小和”算法. 仿真结果表明,其性能与置信传播算法非常接近.     

媒体处理器视频哈夫曼解码快速算法

为了提高视频处理中哈夫曼解码的性能,从减少比特操作、提高处理器内存利用率的角度出发,设计了2种不同的数据结构进行哈夫曼码表的组织,提出了一种新的并行分步查表算法,对Ishii的并行查表法进行了改进.实验结果表明,采用新算法及其内存优化策略,以哈夫曼解码性能较少下降的代价,内存开销得到大幅降低.新算法比常用的分步查表算法的解码效率有较大提升,对MPEG系列、H.26X系列等视频压缩标准具有普适性.     

毫米波Massive-MIMO系统中基于GMD的混合预编码

提出一种毫米波大规模多输入多输出（MIMO）系统中基于几何均值分解（GMD）的混合预编码方案.通过GMD处理将信道分解为等增益的子信道,以简化编解码复杂度.在此基础上,推导出基于GMD的系统频效优化目标函数解析式;然后根据基追踪原理和最小二乘法分别设计模拟预编码和数字预编码;最后通过相应的优化算法得到系统频效的优化解.数值仿真结果表明,提出的基于GMD的混合预编码方法与正交匹配追踪的方案相比,能明显降低系统编解码复杂度,并提高系统频效.     

非均匀Hilbert曲线的生成算法

基于分形理论,针对Hilbert曲线处理非均匀分布的不足,提出了一种非均匀Hilbert曲线的生成算法.该算法根据数据分布密度,对子区域进行空间层次分解,构造区域连接曲线,最终以递归的方式来生成非均匀Hilbert曲线.结果表明:该算法能够对非均匀空间进行有效的处理,极大的减少曲线的路径长度和遍历曲线时的复杂度,从而打破了传统Hilbert曲线的应用局限性.     

基于LDPC码的MIMO-OFDM系统联合迭代检测译码

针对宽带无线通信系统对高可靠性和高速率数据传输的要求,本文介绍了一种基于LDPC码的MIMO-OFDM宽带无线通信系统模型.结合MIMO-OFDM的软判决检测和LDPC码的软对数似然比译码,本文给出了系统的一种低复杂度高性能的联合迭代检测译码算法.仿真结果表明,采用该译码方案对系统的性能有明显改善.