RS柯西码编码算法改进研究

针对RS(Reed-Solomon)算法编码过程涉及有限域运算,复杂度高,效率低,运算代价难以被大规模分布式存储系统所接受等问题,提出了一种RS柯西码编码改进算法。该算法用贪心算法选取局部最优柯西矩阵,减少柯西码的计算量。同时,引入二进制矩阵替换柯西矩阵中的有限域元素进行阵列化,将有限域运算转换为异或运算,并对阵列进行运算优化,进一步减少计算量,增加柯西码的编码效率。根据仿真实验表明,改进后RS柯西码与通过遍历得到的最优柯西矩阵的柯西码相比,计算量更小,与编码效率著称的阵列码中的EVENODD码和STAR码相比,编码效率更高。并且具有类似阵列码性质,能够选择更简单高效的译码方法,在一定程度上提高解码效率。     

基于之字形解码算法优化的高效低存储ZD码

ZD码(ZigZag-decodable codes)是基于之字形解码算法设计生成的一类纠删码, 它仅需要少量的计算即可修复存储系统中的故障数据, 但需要存储相对其他纠删码更多的冗余数据以保证系统的高可靠性. 为了降低ZD码产生的存储开销, 本文通过分析当前在存储系统中使用的之字形解码的思想, 提出了一种优化的之字形解码算法. 新的解码算法能够更充分利用校验数据中的信息来完成数据修复. 基于新的解码算法, 本文相应的提出了一种新的ZD码编码方案, 由于新算法更高的信息利用率, 新的编码方案能够用更少的存储开销来满足存储系统的高可靠性. 实验结果表明, 本文提出的ZD码编码方案具有最优的存储开销, 且编解码性能远高于目前广泛使用的RS码.     

基于简单再生码的分段编码方案

简单再生码将可容多错的RS纠删码与简单的异或运算相结合,在达到容忍任意n－k个节点故障可靠性的基础上,可以实现对单个失效节点的高效快速修复。对简单再生码的失效节点修复过程进行改进,提出一种新的基于简单再生码的分段编码方案,将f个具有相同下标的编码块分成两段,将每段中的编码块进行异或操作,生成一个新的校验块。对该方案的存储开销、磁盘读取的开销以及修复带宽开销进行性能分析和仿真实验,结果表明提出的基于简单再生码的分段编码方案在增加少量存储开销的同时,其修复带宽和磁盘读取的开销性能有了很大程度的优化,进一步验证了改进方案的正确性和有效性。     

云存储多异构文件联合延迟尾概率凸优化分析

随着擦除码技术的流行,分布式存储中高数据可靠性和高空间效率存储性能逐渐实现,但是降低尾部延迟仍然是一个有待解决的问题。为此,提出一种量化和优化擦除编码存储系统尾延迟的算法框架。对于任意服务时间分布和异构文件,推导给出尾部延迟上界。提出了一个优化模型,使得所有文件在服务器上放置的加权延迟尾概率和访问请求文件的服务器选择共同最小化,并证明了其非凸问题特性,以便采用一种高效的交替优化算法求解。此外,通过描述延迟分布尾部的渐近行为,以闭合形式对任意擦除编码存储的服务延迟的尾部指数进行数学量化,证明了基于概率调度的算法是（渐近）最优的。实验结果表明,在实际工作负载下擦除编码存储系统的尾部延迟显著降低。     

一种新的三容错最大距离可分阵列码

随着海量存储系统的发展,双容错数据布局已不能满足系统对可靠性要求.在双容错行对角线奇偶码的基础上,只增加1冗余校验列,提出一种新的3容错最大距离可分阵列码.采用二元矩阵给出了新的阵列码代数编码定义,并通过基二元矩阵变换,给出结构简单易于软硬件实现的译码算法.并理论上证明新阵列码具有最大距离可分编码特性,空间利用率达到了3容错编码最优.与现有其它3容错编码进行比较,分析结果表明新码的编译码效率,小写性能,以及平衡性的综合性能达到最优.     

项目优化调度的病毒协同进化遗传算法

针对次序约束和资源约束的多模式项目调度问题提出了一种病毒协同进化遗传算法,并提出了解的编码、选择、交叉、变异和病毒感染操作等.算法用于求解项目活动的一个最优调度顺序和资源模式以使项目的成本最低,其操作特点是既可以通过遗传操作在父子代群体之间纵向传播进化基因进行全局搜索,又可以通过病毒感染操作在同一代群体内横向传播进化基因进行局部搜索.利用模板理论对算法的性能进行了分析.理论分析和实验结果表明,算法的搜索性能优于一般的遗传算法.算法对于不同优化目标的多模式项目调度问题可以同时求得一个满足次序约束的项目活动的最优调度顺序和满足资源约束的最优资源模式.     

RS类纠删码的译码方法

RS(Reed-Solomon)码可以根据应用环境构造出任意容错能力的码字,有很好的灵活性,且使用RS纠删码作为容错方法的存储系统能达到理论最优的存储效率.但是,与异或(exclusive-OR,XOR)类纠删码相比,RS类纠删码译码计算的时间开销过大,这又很大程度上阻碍了它在分布式存储系统中的使用.针对这一问题,提出了一类RS纠删码的译码方法,该方法完全抛弃了当前大多RS类纠删码译码方法中普遍使用的矩阵求逆运算,仅使用计算复杂度更小的加法和乘法,通过构造译码变换矩阵并在此矩阵上执行相应的简单的矩阵变换,能够直接得出失效码元由有效码元组成的线性组合关系,从而降低译码计算复杂度.最后,通过理论证明了该方法的正确性,并且针对每种不同大小的文件,进行3种不同大小文件块的划分,将划分得到的数据块进行实验,实验结果表明:在不同的文件分块大小情况下,该新译码方法较其他方法的译码时间开销更低.     

基于简单再生码的带宽感知的分布式存储节点修复优化

分布式存储系统为保证可靠性会采用一定存储冗余策略如多副本策略、纠删码策略.纠删码相对于副本具有存储开销小的优点,但节点修复网络开销大.针对修复网络开销优化,业界提出再生码与以简单再生码为代表的局部可修复码,显著降低了修复网络开销.然而,现有基于编码的分布式容错存储方案大都假设节点处于星型逻辑网络结构中,忽略了实际的物理网络拓扑结构和带宽信息.为实现拓扑感知的容错存储优化,相关研究在纠删码和再生码修复过程结合网络链路带宽能力,建立树型修复路径,进一步提高了修复效率.但由于编码和修复过程的差异性,上述工作并不适合于简单再生码修复.针对该问题,本文结合实际物理网络拓扑结构,将链路带宽能力引入到简单再生码的修复过程中,对带宽感知的简单再生码修复优化技术开展研究.论文建立了带宽感知节点修复时延模型,提出了基于最优瓶颈路径和最优修复树的并行修复树构建算法.并通过实验对所提算法性能进行了评估.实验结果表明,与星型修复方式相比,论文所提算法有效地降低了节点修复时延,提高了修复效率.     

求解job shop调度问题的量子粒子群优化算法*

针对粒子群优化算法搜索空间有限、容易出现早熟现象的缺陷,提出将量子粒子群优化算法用于求解作业车间调度问题。求解时,将每个调度按照一定的规则编码为一个矩阵,并以此矩阵作为算法中的粒子;然后根据调度目标确定目标函数,并按照量子粒子群优化算法的进化规则在调度空间内搜索最优解。仿真实例结果证明,该算法具有良好的全局收敛性能和快捷的收敛速度,调度效果优于遗传算法和粒子群优化算法。     

求解job-shop调度问题的量子粒子群优化算法

针对粒子群优化算法搜索空间有限、容易出现早熟现象的缺陷,提出将量子粒子群优化算法用于求解作业车间调度问题.求解时,将每个调度按照一定的规则编码为一个矩阵,并以此矩阵作为算法中的粒子;然后根据调度目标确定目标函数,并按照量子粒子群优化算法的进化规则在调度空间内搜索最优解.仿真实例结果证明,该算法具有良好的全局收敛性能和快捷的收敛速度,调度效果优于遗传算法和粒子群优化算法.     

云计算环境任务调度方法研究综述

随着应用程序计算需求的快速增长,异构计算资源不断地增多,任务调度成为云计算领域中重要的研究问题。任务调度负责将用户任务匹配给合适的虚拟计算资源,算法的优劣将直接影响响应时间、最大完工时间、能耗、成本、资源利用率等一系列与用户和云服务供应商经济利益密切相关的性能指标大小。针对独立任务和科学工作流这两类云环境主流任务,结合不同云环境特征对任务调度算法研究进展进行综述和讨论。回顾梳理已有的任务调度类型、调度机制及其优缺点;归纳单云环境和混合云、多云及联盟云等跨云环境下任务调度特征,并对部分相关典型文献的使用方法、优化目标、优缺点等方面进行阐述,在此基础上讨论各个环境下任务调度研究现状;进一步对各类环境下文献使用的调度优化方法进行梳理,明确其使用范围;总结并指出需要对计算数据密集型应用在跨云环境下的任务调度研究进行重点关注。     

基于模因优化和循环调度的多目标负载均衡技术

针对现有多目标调度方法所需时间较长以及处理突发情况时性能降低的问题,提出一种基于模因优化和循环调度的多目标负载均衡技术。使用突发检测器检测发送到云服务器的用户请求,确定负载状态。基于测器结果,应用不同的负载平衡算法来高效地调度用户任务。利用选定的负载平衡算法将用户请求任务调度到资源最佳的虚拟机上,保证在最低的时间消耗内达到负载均衡的状态。实验结果表明,与其他算法相比,该方法在多个性能指标上具有明显优势,可以提高调度效率的同时,最大限度地降低云中的能源使用。     

基于纠删码的细粒度云存储调度方案

针对云存储系统中数据获取时延长以及数据下载不稳定的问题,提出了一种基于存储节点负载信息和纠删码技术的调度方案。首先,利用纠删码对文件进行编码存储以降低每份数据拷贝的大小,同时利用多个线程并发下载以提高数据获取的速度;其次,通过分析大量存储节点的负载信息确定影响时延的性能指标并对现有的云存储系统架构进行优化,设计了一种基于负载信息的云存储调度算法LOAD-ALGORITHM;最后,利用开源项目OpenStack搭建了一个云计算平台,根据真实的用户请求数据在云平台上进行部署和测试。实验结果表明,相比于现有的工作,调度算法在数据获取时延方面最高能减少15%的平均时延,在数据下载稳定性方面最高能降低40%的时延波动。该调度方案在真实的云平台环境下能有效地提高数据获取速度和稳定性,降低数据获取时延,达到更好的用户体验。     

基于RBEC的副本动态存储方法

随着云存储技术的飞速发展,现有的云存储架构和存储模式都以一种静态的方式呈现在用户和攻击者面前,使得数据面临着更多的安全威胁。针对这种数据静态存储模式的不足,文中提出了一种基于二元随机扩展码(RBEC)的副本动态存储方法。该方法利用一种网络编码将数据块存储在云节点上,通过基于二元随机扩展码进行节点数据变换,可随机时变地改变节点的数据信息,通过变换攻击面来增加攻击者实施攻击的复杂度和成本,降低系统的脆弱性曝光和被攻击的概率,提高系统的弹性。理论分析和仿真实验结果表明,该方法对变换时的编码计算时间开销在整个动态变换中的占比不高,主要的时间开销是在节点间数据编码块的传输上。此外,文中还将该方法与一般再生码拟态变换方案做了性能对比分析。REBC的特性,即重新生成的编码矩阵满足MDS性质的概率几乎为1,所以文中所提方法的编码过程的性能开销优于一般再生码可能多次变换的性能开销。     

一种用于时空体元编解码存储的低计算量优化方法

针对时空网格体对象的编解码占用存储空间大的问题,提出了一种用于时空体元编解码存储的低计算量优化方法。首先以十六叉树索引结构为基础,构建了时空网格体元编解码的数学模型,实现体元对象标识和时空位置索引,并借助3DGIS的自动编解码方法,实现了时空网格体元对象编解码存储表示的换算;其次,采用伽罗华有限域理论,构建了网格体元的二进制编码矩阵和存储的低计算量优化算法,实现了体元对象编解码存储过程中的优化计算;最后,以某矿山的矿床空间块体数据为例,对网格体元编解码模型、存储表示换算以及低计算量优化算法进了实际应用,并与八叉树索引结构的Morton码进行比较和分析,结果表明：该方法可有效降低30%的编解码存储计算量,提高了存储网格体元对象的时空效率。     

云计算环境中面向DAG任务的多目标调度算法

为了实现任务执行效率与执行代价的同步优化,提出了一种云计算环境中的DAG任务多目标调度优化算法。算法将多目标最优化问题以满足Pareto最优的均衡最优解集合的形式进行建模,以启发式方式对模型进行求解;同时,为了衡量多目标均衡解的质量,设计了基于hypervolume方法的评估机制,从而可以得到相互冲突目标间的均衡调度解。通过配置云环境与三种人工合成工作流和两种现实科学工作流的仿真实验测试,结果表明,比较同类单目标算法和多目标启发式算法,算法不仅求解质量更高,而且解的均衡度更好,更加符合现实云的资源使用特征与工作流调度模式。     

Static scheduling for barrier MIMD architectures

In a SIMD or VLIW machine, conceptual synchronizations are accomplished by using a static code schedule that does not require run-time synchronization. The lack of run-time synchronization overhead makes these machines very effective for fine-grain parallelism, but they cannot execute parallel code structures as general as those executed by MIMD architectures, and this limits their utility.In this paper we present a timing analysis that allows a compiler for a MIMD machine to eliminate a large fraction of the run-time synchronization by making efficient use of static code scheduling. Although these techniques can be adapted to be applied to most MIMD machines, this paper centers on the analysis and scheduling for barrier MIMD machines. Barrier MIMDs are asynchronous multiple instruction stream/multiple data stream architectures capable of parallel execution of variable execution-time instructions and arbitrary control flow (e.g., while loops and calls). However, they also incorporate a special hardware barrier synchronization mechanism that facilitates static scheduling by providing a mechanism which the compiler can use to enforce precise timing constraints. In other words, the compiler tracks relative timing between processors and uses static code scheduling until the timing imprecision becomes too large, at which point the compiler simply inserts a barrier to reduce that timing imprecision to zero (or a small constant).This paper describes new scheduling and barrier placement algorithms for barrier MIMDs that are based loosely on the list scheduling approach employed for VLIWs [Ellis 1985]. In addition, the experimental results from scheduling thousands of synthetic benchmark programs for a parameterized barrier MIMD machine are presented.     

支持SIMD 与簇间双字传输体系下的VLIW DSP 分簇算法

VLIW DSP通过软件流水获得时间并行性,通过指令分簇获得空间并行性.指令的分簇本质上是资源分配问题.传统的指令分簇假设一条指令分到某一簇执行,而某些体系结构提供SIMD指令,传统的分簇算法对这类体系结构并不完全适用.提出的基于评估模型的分簇算法能对SIMD指令和普通指令进行合理的分簇.分簇之后,通过调度簇间传输指令,合成适当的簇间双字传输指令.由于SIMD和簇间双字传输的引入,以及较好的分簇决策,程序整体的调度延迟变短.对许多数字信号处理程序相对于没分簇的情况下的性能有2～3倍的性能提升,相对寄存器压力分簇算法有约7～10%性能的提升.     

基于稀疏随机矩阵的再生码构造方法

针对已有的再生码编码方案的运算是基于有限域GF（q）、运算复杂度高、效率低的问题,提出了一种将GF（2）上的稀疏随机矩阵和乘积矩阵框架相结合的再生码构造方法。首先,将文件数据矩阵式排布后根据编码矩阵进行行异或运算;其次,节点失效后,参与帮助节点根据失效节点的编码向量编码本地数据并发送至修复节点;最后,修复节点根据接收到的数据译码出失效节点原有的数据。实验结果表明修复带宽至多只有传统纠删码修复方案的1/10,相比基于传统范德蒙编码矩阵的再生码,编码速率提升了70%,译码恢复速率提升了50%,方便了再生码在大规模存储系统中的应用。     

面向期限感知分布式矩阵相乘的高效存储方案

分布式矩阵相乘是众多分布式机器学习、科学计算等应用中的关键操作,但其性能会受到系统中常见的落后节点的严重影响。最近研究者提出了基于喷泉码的编码矩阵相乘方法,能够充分利用落后节点的部分计算结果,从而大幅度减轻落后节点问题,但忽略了工作节点的存储开销。在考虑存储开销与计算完成时间之间的权衡关系的基础上,首先提出了面向异构工作节点的计算期限感知的存储优化问题;然后进一步通过理论分析,提出了基于期望近似的解决思路,并通过松弛将问题转化为凸优化问题以方便高效求解。仿真实验表明,在保证较大的任务成功率的情况下,所提方案的存储开销会随着任务期限的放宽迅速下降,并且该方案能够更大幅度降低编码带来的存储开销。也就是说,所提方案能够在保障整体计算在期限内大概率完成的前提下,大幅度降低总体的额外存储负载。