脉动阵列处理器的设计研究

本文首先介绍了脉动阵列处理的基本概念和主要应用领域，以及脉动脉列处理器设计所淑及的主要理论基础。在研究了脉动阵列处理器结构特点和优化标准的基础上，重点对最短计算时间和最小流水周期的设计进行了研究，最后对割集的收缩过程进行了讨论。     

映射循环算法到脉动阵列的一种有效方法

本文提出了把任意ｎ维嵌套循环算法映射和划分到２维固定大小的Ｓｙｓｔｏｌｉｃ阵列的一种自动设计方法，由于考虑了数据相关性，运用该方法产生的ＶＬＳＩ算法的执行时间少，而且不会引起时空冲突。因为平面ＶＬＳＩ阵列容易构造，所以该方法有良好的可行性的实用性。     

线性脉动阵列变换的空时映射搜索算法

研究了一类多重循环算法的线性脉动阵列实现.为了提高线性脉动阵列变换中空时映射的搜索效率,在Moldovan空时映射的基础上,采用启发式搜索方法,并引入基削减与分支定界相结合的算法,大大降低了算法复杂度,提高了效率.通过合理安排验证顺序,结合实际硬件结构进行搜索,进一步降低了计算复杂性,并使得到的线性阵列更加易于实际实现,硬件功能及结构之间达到了最大程度的均衡性.     

蒙哥马利算法到脉动阵列的规范映射方法

蒙哥马利算法是在RSA密码系统中广泛应用的模乘法算法。该文介绍蒙哥马利算法到脉动阵列的映射过程,阐述了从算法到脉动阵列的规范映射方法。阵列的时钟周期长度大致是两个单位全加器延迟,n位模乘法的计算延迟是2n+2个时钟周期。模块化、规则化、通信局部化等特征,使得脉动阵列特别适合采用深亚微米VLSI技术实现,并获得很高的工作频率,从而提高处理速度。     

Smith-Waterman算法在脉动阵列上的实现及分析

Smith Waterman算法是一种经典的序列比对算法 ,在双序列比对的情况下具有比较好的性能 ,但是在大规模的序列比对时 ,其性能并不能令人满意 .脉动式阵列和Smith Waterman算法有比较好的吻合性 .该文通过在龙芯 1号处理器上附加一个脉动式阵列的协处理器 ,构建了硬件模型 .通过模拟器的验证 ,附加了协处理器的龙芯 1号的性能与没有附加协处理器时的性能之比接近于线性 .该文最后根据硬件模型和模拟器的性能数据 ,具体分析了系统各个方面对性能提高的影响     

一类脉动阵列算法的正确性与最优性

本文以脉动处理定理为基础,给出了一阶递归问题的脉动阵列算法的正确性证明,并证明了最优方案与问题尺寸及目标函数的独立性,从而降低了优化搜索的复杂度。文中提出了两个新的脉动阵列算法,用以阐述理论结果对复杂问题的应用。     

脉动阵列算法自动综合的优化策略

对于脉动阵列算法的自动综合方法，本文揭示了参数确定法和相关性变换法的本质联系，给出了相关性变换法适用问题类的一个新的高效寻优策略。     

脉动变换的一个新的快速搜索算法

介绍了搜索脉动变换的一个快速方法，使用数据相关性法将循环算法映射成脉动阵列，主要任务是搜索脉动变换T-[∏，S]，为此需要对选定的∏和所有可能的矩阵K解方程SD=PK，本文指出如下事实并依据该事实提出一个搜索变换S的新方法：如果变换S满足[0…0 0…0]≤SD≤[L L]其中L=[[∏δ1/2]]……[[∏δm/2]]。则存在矩阵K满足方程SD=PK。因此通过验证不等式即可得出变换S，避免了矩阵K的枚举和反复解方程组SD=PK，使搜索效率显著提高。     

脉动阵列变换的搜索策略及自动化算法*

对于多重循环中,当内层迭代的上下界为外层迭代的仿射函数时,介绍了搜索脉动变换的一个优化策略和相应的自动化算法.     

HEVC帧内预测算法加速设计与实现

新一代视频编码标准获得了较高的编码效率,但同时也增加了计算量。HEVC(High Efficiency Video Coding)并行算法能够提高编码速度,开发适用于多核处理器的并行编码算法对于满足高清视频实时传输和大规模实时共享具有十分重要的意义。分析帧内预测算法在处理像素过程中数据之间的依赖关系,进行基于预测模式的细粒度并行性的设计。块与块之间采用流水线处理,减少帧内预测算法的执行时间。利用动态可编程可重构视频阵列处理器,对帧内预测算法进行验证。实验结果表明,相比于HM16.0官方测试标准,信噪比提高了10%,算法的执行时间减少了大约70%。     

PROCESSOR-TIME-OPTIMAL SYSTOLIC ARRAYS

Abstract

Minimizing the amount of time and number of processors needed to perform an application reduces the application's fabrication cost and operation costs. A directed acyclic graph (dag) model of algorithms is used to define a time-minimal schedule and a processor-time-minimal schedule, We present a technique for finding a lower bound on the number of processors needed to achieve a given schedule of an algorithm. The application of this technique is illustrated with a tensor product computation. We then apply the technique to the free schedule of algorithms for matrix product, Gaussian elimination, and transitive closure. For each, we provide a time-minimal processor schedule that meets these processor lower bounds, including the one for tensor product.     

求解正交数组问题的拟物拟人算法

此工作是方开泰工作的继续，正交数组在制造业和高技术产业的试验中有着广泛的应用，目前正交数组构造的研究相当活跃，现有的许多构造方法很复杂且所能构造的类型有限。提出了一个构造正交数组简单而效的方法－拟物拟人算法，应用该算法已经独立地得到了一些历史上尚未发现的L27（3^13)的不同构数组，希望该算法经过进一步发展后将能设计出许多新的正交数组。     

有真实感图形的纹理映射算法

本文讨论了计算机生成真实感图形的纹理映射技术，根据模拟现实物体的表面细节特征提出了三种纹理映射方法。     

映射对象到关系数据库

面向对象技术是当今最流行的软件开发方法,关系模型是最常用的一种数据模型。如何用关系数据库实现持久对象的存储成为信息系统成功的关键。本文对映射对象模型到存储数据的关系模型的方法进行了探讨。     

PROPERTIES OF SIMULATED ANNEALING AND GENETIC ALGORITHMS FOR MAPPING DATA TO MULTICOMPUTERS

We experimentally analyze some properties of simulated annealing algorithms (SA) and genetic algorithms (GA) for mapping data to multicomputers. These properties include sensitiviiy to user parameters, fault tolerance capability, and applicability to different multicomputer topologies. Some user parameters are included in the objective function and are architecture- or problem-dependent parameters. The others are used in the GA and SA algorithms. The fault tolerance capability is demonstrated by mapping data to a multicomputer with some faulty processors. We assume a hypercube multicomputer architecture in most experiments. However, mapping to mesh, array, ring, tree, and star graph topologies is also demonstrated. The experimental results show that the GA and SA are insensitive to user parameters in wide ranges, completely fault tolerant, and unbiased towards particular multicomputer topologies. These properties of flexibility and general applicability, which are lacking in other heuristic algorithms, make the GA and SA attractive for automatic parallelization systems.     

流场类问题并行化中数组共享变量的自动搜索

本文的目的是解决流场类问题的自动并行化．首先将流场数据均匀划分，并以SPMD模式对流场计算串行程序进行并行化；引入数组共享变量，着重讨论一种新方法──用递归函数实现数组共享变量的自动搜索．用本文方法的并行化工具已初步实现．