容错处理器阵列的并行重构及VHDL实现

网格连接的处理器阵列是一种应用广泛的高性能体系结构,而容错处理器阵列的重构技术是近年来的研究热点之一.现有的研究多数集中在串行重构算法上,忽视了该结构重构时内在的可并行性.本文根据阵列结构的特点设计了一种基于VHDL语言的重构算法,该算法从第一行的各个无故障处理器单元同时向下选路,具有潜在的并行性,.实验结果表明,与现有的串行算法相比,本文提出的并行算法同样能够生成最大规模的目标阵列并且当物理阵列大小为48×48,本文提出的并行算法加速重构将近20倍.     

环网处理器阵列的容错重构技术

高效的容错技术对于提高多处理器系统的可靠性至关重要。环网(Torus)是连接多处理器阵列的重要网络结构,而环网处理器阵列上的容错重构技术目前尚属空白。针对环网阵列的特殊连接方式,将环网阵列重构问题转化为矛盾图上求解最大独立集问题。矛盾图上的结点表示故障处理器的替换方案,而边代表了不同替换方案之间的不可共存特性。主要是根据三种不同的冗余处理器分布方案,设计生成矛盾图算法,求解最大独立集算法,以及由独立集生成逻辑处理器阵列算法,取得了令人满意的结果。实验结果表明,当阵列规模较小或故障率较低时,一行一列和十字型的冗余单元分布的重构能力较好;而随着阵列规模或故障率的增大,三种冗余单元分布策略的重构成功率都随之下降,但可通过增加冗余单元以及调整冗余分布来改善容错效果。此外,从实验结果中还可以看出,环网处理器阵列的容错能力显然优于网格(Mesh)处理器阵列。     

灵活列选路模式下构造紧致逻辑阵列的高效算法

当前成百上千的处理器可以集成到同一个芯片上,而高密度处理器阵列在高速并行处理的时候经常发生故障.一种有效的解决方法是构造一个不包含故障单元的逻辑阵列,使得原始任务能够继续执行.我们研究在灵活列选路模式下构造逻辑阵列的高效算法,使得所构造的逻辑阵列不仅规模最大而且互连网络长度尽可能短.我们提出的算法TCA首先使用现存算法构造一个最大逻辑阵列,之后优化各个逻辑列来减少阵列的互连网络长度,我们把优化每个逻辑列的问题转化为带权图上的最短路径问题求解.实验结果表明我们的方法显著减少了逻辑阵列互连网络长度.     

可重构阵列的同步性能优化算法

可重构多处理器阵列上的容错技术可用来重构含有故障单元的处理器阵列,以便获得最大可用的目标阵列。现有的研究成果主要侧重于重构算法的构造,还没有涉及对重构后目标阵列的同步通讯性能的研究。提出了一种改善目标阵列同步通讯性能的电路优化算法,用来降低目标阵列行与行之间通讯的延时,使得相邻两行处理器的通讯尽可能达到同步。实验结果表明,提出的算法对不同大小、不同故障率的阵列都有相应的同步通讯性能的改善。     

多核处理器上的并行联机分析处理算法研究

近年来,计算机硬件技术获得了很大发展,尤其是大内存和多核,但算法效率并没有随着硬件技术的发展而提高,根本原因是没有充分利用CPU缓存以及单线程程序设计的局限性。在联机分析处理领域,数据方体计算是一个重要而又耗时的操作,因此如何提高数据方体的计算效率是该领域的一个研究难点。探讨了基于多核CPU特征的并行立方体算法,提出了MT-Multi-Way(multi-threading multi-way)和MT-BUC(multi-threading bottom-up computation)算法。该算法通过有效的数据划分和多线程协作,避免了Cache竞争,并确保了负载均衡,获得了近似线性加速比。以上述算法为基础,提出了处理立方体算法的多核框架,包括数据划分策略及递归算法的多核处理,指导立方体算法的并行化。     

基于可重构处理器的并行优化算法

为挖掘可重构处理器的内在并行性,需要编译器通过分析程序的并行性来决定可重构处理器硬件最好的执行模式。为此,提出一种基于可重构处理器的并行优化算法。将有向无环图的并行计算部分映射到可重构处理器上,对任务实现3个不同层次的并行性(指令级并行、循环级并行、线程级并行)。测试结果表明,该算法使得可重构处理器在处理任务时比未用并行优化算法的性能提升1.2倍左右。     

三维可重构阵列互连资源在线分布式容错方法

设计了一种新型三维可重构阵列结构, 并且对其互连资源在线分布式容错方法进行了研究。系统由相同的功能细胞和开关块以三维结构组成, 通过在线输入测试向量对互连线进行故障定位, 并且实现故障连线分层自修复。以四位加法/减法器电路为设计实例, 对可重构阵列功能和容错能力进行验证。实验结果表明该方法可有效完成容错, 且时间开销小、容错能力强、资源利用率高。     

基于阵列处理器的SVDC算法并行设计与实现

视点合成失真算法(Synthesized View Distortion Change,SVDC)作为三维高效视频编码(3D High Efficiency Video Coding,3D-HEVC)中改善深度图编码效率的有效途径,已成为当下三维视频领域的研究前沿之一.基于阵列处理器,利用分布式共享存储结构设计并实现一种SVDC算法的并行映射方式,并根据访存特性提出失真值计算优化方案,以像素级误差平方和(Sum of Squared Differences,SSD)计算替代单元级SSD计算.实验表明,相比于HTM平台,算法的平均性能可以提升19.03%,所设计的失真值计算并行方案串/并加速比为 2.36,使用像素级SSD计算后相比于优化前平均性能可以提升39.3%.     

视频阵列处理器HEVC去块滤波算法动态重构实现

去块滤波算法是高效视频编码标准(high-efficiency video coding, HEVC)的重要组成部分,专用硬件实现的去块滤波电路结构难以满足不断革新的算法需求,可重构计算兼具计算高效性和编程灵活性成为研究热点。基于指令流与数据流混合驱动可重构视频阵列处理器(reconfigurable video array processor, RVAP),提出一种可重构的HEVC编码去块滤波电路的并行化实现方法,依据数据流图分析实现去块滤波算法的最大化并行,提高计算效率;通过强/弱滤波方式的灵活切换,提高计算资源利用率。实验结果表明,所提方法在满足算法灵活切换和计算速度要求的同时,硬件资源减少了47.6%,时钟频率达167 MHz。     

基于阵列处理器的最小均方误差检测算法并行设计与实现

针对大规模多输入多输出（MIMO）系统中,最小均方误差（MMSE）检测算法在可重构阵列结构上适应性差、计算复杂度高和运算效率低的问题,基于项目组开发的可重构阵列处理器,提出了一种基于MMSE算法的并行映射方法。首先,利用Gram矩阵计算时较为简单的数据依赖关系,设计时间上和空间上可以高度并行的流水线加速方案;其次,根据MMSE算法中Gram矩阵计算和匹配滤波计算模块相对独立的特点,设计模块化并行映射方案;最后,基于Xilinx Virtex-6开发板对映射方案进行实现并统计其性能。实验结果表明,该方法在MIMO规模为、和的正交相移键控（QPSK）上行链路中,加速比分别2.80、4.04和5.57;在的大规模MIMO系统中,可重构阵列处理器比专用硬件减少了42.6%的资源消耗。     

可重构并行嵌入式系统

摘要：针对目前应用于军事、航天特殊环境的嵌入式系统存在功能单一、灵活性差、可靠性有限等问题,构建高性能高可靠嵌入式系统RPES,采用SMP并行机制、多种容错策略、硬件支持的软件重注入机制和算法部件动态重构机制,支持系统容错策略以及性能和灵活性的提升。‘测试结果表明,该系统能适应大范围的特殊应用。     

Minimizing interconnect length on reconfigurable meshes

Shorter total interconnect and fewer switches in a processor array definitely lead to less capacitance, power dissipation and dynamic communication cost between the processing elements. This paper presents an algorithm to find a maximum logical array (MLA) that has shorter interconnect and fewer switches in a reconfigurable VLSI array with hard/soft faults. The proposed algorithm initially generates the middle (⌊k/2⌋ ^th ) logical column and then makes it nearly straight for the MLA with k logical columns. A dynamic programming approach is presented to compact other logical columns toward the middle logical column, resulting in a tightly-coupled MLA. In addition, the lower bound of the interconnect length of the MLA is proposed. Experimental results show that the resultant logical array is nearly optimal for the host array with large fault size, according to the proposed lower bound.     

Genetic algorithm with dynamic variable number of individuals and accuracy

This paper proposes a novel processor for genetic algorithm (GA) that can dynamically change number of individuals and accuracy. In conventional GA, number of population and accuracy are fixed. However, the accuracy of solution is low at first-half stage. Therefore, the number of population is doubled at expense of the accuracy of solution, and the searching ability is improved at first-stage in the proposed GA processor. Then, the number of population is reduced by half, and the accuracy is improved at second-half stage. As a result, the searching ability is improved. The proposed GA processor was designed and verified. The effectiveness of proposed method was confirmed by applying to the knapsack problem. Recommended by Guest Editor Phill Kyu Rhee. This work was supported by the grant from Research Institute for Science and Technology, Tokyo Denki University (Q06J-03). Akihiko Tsukahara received the B.E. degree in Electronic Engineering from Tokyo Denki University in 2005. He is currently a M.E. student in Tokyo Denki University. His research interests include VLSI design for genetic algorithm and rough sets. Akinori Kanasugi received the B.E., M.E. and Ph.D. degrees from Saitama University, Japan, in 1983, 1985 and 1994, respectively. After a research associate in Saitama University, he moved to Tokyo Denki University in 2002, where he is currently a Professor in the Faculty of Engineering. His current research interests are in the development of VLSI systems such as reconfigurable processor, GA processor, and rough sets processor.     

可重构造的网孔机器上的k-选择

对于一个 ｍ ×ｎ（ｍ ≤ｋ）的列有序矩阵,文中在 ｎ × ｎ 可重构造的网孔机器上提出了一个并行 ｋ选择算法,其时间复杂度为 Ｏ（ｌｏｇ２ｍ ＋ ｌｏｇｍ ｌｏｇ２ ｎ＋ ｌｏｇ３ ｎ）,而对于一般的ｌ元集,文中在相同的模型下提出了一个时间复杂度为 Ｏ ｌｏｇ２ ｌｎ ＋ ｌｏｇ ｌｎ ｌｏｇ２ ｎ＋ ｌｏｇ３ｎ＋ ｌｎ ｌｏｇ ｌｎ 的并行 ｋ选择算法．当时 ｌ≥ Ｏ（ｎｌｏｇ３ｎ／ｌｏｇ ｌｏｇｎ,该时间复杂度为 Ｏ ｌｎ ｌｏｇ ｌｎ ．特别地,当ｌ＝ Ｏ（ｎ１＋ ε）（ε＞ ０ 为常数）,则时间复杂度为 Ｏ ｌｎ ｌｏｇｎ ．此时达到的加速比为 ｎ／ｌｏｇｎ．     

New Processor Array Architectures for the Longest Common Subsequence Problem

A longest common subsequence (LCS) of two strings is a common subsequence of two strings of maximal length. The LCS problem is to find an LCS of two given strings and the length of the LCS (LLCS). In this paper, we present a new linear processor array for solving the LCS problem. The array is based on parallelization of a recent LCS algorithm which consists of two phases, i.e. preprocessing and computation. The computation phase is based on bit-level dynamic programming approach. Implementations of the preprocessing and computation phases are discussed on the same processor array architecture for the LCS problem. Further, we propose a block processor array architecture which reduces the overall communication and time requirements. Finally, we develop a performance model for estimating the performance of the processor array architecture on Pentium processors.     

基于QoS的网络存活性动态重配置管理模型

传统的安全技术已经不足以保护无边界网络环境中高分布信息系统的存活性问题.针对网络存活性系统中由于外来攻击或自身故障等原因导致失效时,提供关键服务自恢复能力的不足,从容错QoS角度出发,提出了一个有效的网络存活性自适应重配置模型,讨论了存活性重配置策略,并给出存活性重配置的具体实现环节和相应的动态重配置算法.该模型可以实时监测系统当前状态,并能在系统遭受攻击或自身故障时,迅速确定动态调整算法,为系统有效实施存活性动态重配置策略提供了一种可行思路.     

Synchronization and control of parallel algorithms

We propose a modest collection of primitives for synchronization and control in parallel numerical algorithms. These are phrased in a syntax that is compatible with FORTRAN, creating a publication language for parallel software. A preprocessor may be used to map code written in this extended FORTRAN into standard FORTRAN with calls to the run-time libraries of the various parallel systems now in use. We solicit the reader's comments on the clarity, as well as the adequacy, of the primitives we have proposed.     

基于网络处理器的多模式串匹配研究

深度数据包检查是网络入侵检测系统的性能瓶颈。该文分析入侵规则集中模式串的分布特点,对多模式匹配算法FNP进行改进,研究在多核多线程体系结构的网络处理器上高效实现模式串匹配的方法。在Intel IXP2800网络处理器上的仿真实验结果表明,改进算法在规模为10 K的模式串集合上能达到6 Gb/s的吞吐量,具有几乎线性的加速比。