基于FPGA的非编码RNA基因检测算法加速器研究

ncRNA(非编码RNA)是一类重要的遗传物质,它通过多种机制调控着基因的表达。由于缺少编码RNA基因所具有的典型特征,ncRNA基因的检测成为生物信息学RNA研究领域的热点问题。QRNA是目前该领域最典型使用最广泛的程序之一,但受限于O(L3)计算复杂度,传统的软件预测方法并不能满足日常研究的需要。本文基于FPGA平台实现了一种细粒度的并行ncRNA检测算法,利用CPU加FPGA的方案对QRNA程序实现细粒度并行,采用按矩阵列循环划分的任务分配策略实现处理单元间的负载平衡;采用数据预取、滑动窗口和数据传递流水线实现处理单元间的数据重用,减少片外访存开销。在单片FPGA上集成了由8个处理单元构成的计算阵列。实验结果表明,与运行在AMD四核9650处理器上的QRNA-2.0.3c程序相比,可获得超过18倍的加速效果,并且FPGA加速器功耗仅为通用微处理器平均功耗的20%。     

基于FPGA的存储优化的细粒度并行Zuker算法加速器研究

RNA二级结构预测是生物信息学领域重要的研究方向,基于最小自由能模型的Zuker算法是目前该领域最典型使用最广泛的算法之一.基于FPGA平台实现了一种细粒度的并行Zuker算法,采用按矩阵列循环划分的任务分配策略实现了处理单元间的负载平衡;采用数据预取、滑动窗口和数据传递流水线实现了处理单元间的数据重用;采用曲线拟合、离散点赋值和地址空间压缩编码等策略减少了约85%的自由能参数存储需求.在单片FPGA上集成了由20个PE构成的主从多PE线性阵列,实验结果表明与运行在AMD四核9650处理器上的ViennaRNA-1.6.5程序相比,可获得超过18倍的加速效果,并且FPGA加速器功耗仅为通用微处理器平均功耗的1/5.     

基于FPGA的细粒度并行K-means算法加速器的设计与实现

本文在深入分析K-means算法计算特征的基础上,基于FPGA平台提出并实现了一种细粒度的并行浮点K-means算法。设计采用了阵列多PE并行处理的任务划分策略,实现了处理单元间的负载平衡,采用数据驱动的流水线隐藏片外存储访问,设计了一种基于脉动阵列结构的主从多PE并行计算阵列,并在单片FPGA(XC5VLX330)上成功集成了4个PE。实验结果表明,我们提出的K-means算法加速器结构具备良好的可扩展性。通过实验测试,我们的实现方案相对于Pentium 4 2.66 GHz单处理器程序达到了15倍的加速比。     

基于OpenCL大规模种群并行遗传算法

为了提高RNA二级结构预测的准确率和加速遗传算法,提出基于OpenCL大规模种群并行遗传算法。通过研究遗传算法中潜在的并行性,以Acer TMP246M-MG-5086为实验平台,先在CPU中实现遗传算法,再使用OpenCL技术在GPU中实现大规模种群并行遗传算法。测试结果表明,并行遗传算法对于RNA二级结构预测的准确率平均提高了约49.88%,使用GPU平均加速比为9.76x。     

基于多级片上总线的并行图像处理系统设计*

采用基于平台级FPGA的SOC设计方法, 设计了一种基于多级PLB总线的可扩展并行图像处理系统。系统采用总线桥并行扩展处理单元来增加系统处理性能和扩展存储访问带宽;通过数据分发模块实现图像数据输入与处理流水线操作。时序功能仿真与硬件实现表明,该设计能灵活高效地实现系统结构的并行扩展,显著提高了系统并行处理性能。     

OpenVX与三维渲染在多态GPU上的并行实现

针对图像处理与机器视觉以及三维图形渲染等所具有的大规模并行处理特征,通过充分利用面向图形图像处理的多态阵列架构(PAAG)处理器的可编程性以及灵活的并行处理方式,采用操作级并行与数据级并行相结合的并行化设计方法,实现了OpenVX中Kernel函数以及3D图形渲染.实验结果表明,在OpenVX标准图像处理Kernel函数以及图形渲染的并行实现中,采用PAAG处理器中的多指令多数据(MIMD)并行处理方式可以获得斜率为1的线性加速比,比传统图形处理器(GPU)中单指令多数据(SIMD)并行处理方式所得到的斜率值小于1的非线性加速比效率更高.     

萤火虫2：一种多态并行机的硬件体系结构

提出了一种新型的多态高效并行阵列机结构--萤火虫2号阵列机。该结构的处理单元可以在SIMD和MIMD两种模式下运行,兼有异步执行机制,还可以实现分布式指令级并行处理。采用了硬件的多线程管理器和高效通信机制,这些机制使得此种阵列机能够实现效率很高的线程级并行运算、数据级并行运算和分布式指令级并行运算。尤其值得指出的是,此种阵列机的流处理性能堪与专用集成电路匹敌。该结构还能有效实现静态与动态数据流计算,可以高效实现图形、图像和数字信号处理任务。     

一类大规模稀疏矩阵特征问题求解的并行算法

本文提出一种求解大规模稀疏矩阵特征问题的并行共轭梯度算法.为了提高算法的并行效率,设计了负载平衡的行划分方式,实现了计算和通信重叠的稀疏矩阵重排序方法,通过预处理减少计算过程中各进程间消息传递的通信量.另外,基于多核处理器高性能并行计算,实现了MPI和细粒度(线程级)OpenMP混合并行算法.在深腾7800并行计算机上对并行算法进行了测试,结果表明在进程数增多时并行算法可保持通信时间稳定性,在并行计算机上有很好的扩展性,适合大规模稀疏特征问题的求解.     

矿山三维空间数据距离直方图算法优化及加速

分析了三维空间数据距离直方图算法的性质及数据结构,提出了基于图形处理器的通用计算方法和基于FPGA的高性能计算方法,基于图形处理器的计算方法可用于实现三维空间数据距离直方图算法的单指令多数据并行优化;基于FPGA的计算方法可实现算法的硬件分块优化,使算法的硬件结构达到最优匹配。实验结果表明,利用基于图形处理器的计算方法可使算法达到平均18倍的性能加速,基于FPGA的计算方法可使算法达到平均30倍的性能加速,大大提升了算法的数据处理能力。     

基于CUDA的并行粒子群优化算法的设计与实现

针对处理大量数据和求解大规模复杂问题时粒子群优化(PSO)算法计算时间过长的问题, 进行了在显卡(GPU)上实现细粒度并行粒子群算法的研究。通过对传统PSO算法的分析, 结合目前被广泛使用的基于GPU的并行计算技术, 设计实现了一种并行PSO方法。本方法的执行基于统一计算架构（CUDA）, 使用大量的GPU线程并行处理各个粒子的搜索过程来加速整个粒子群的收敛速度。程序充分使用CUDA自带的各种数学计算库, 从而保证了程序的稳定性和易写性。通过对多个基准优化测试函数的求解证明, 相对于基于CPU的串行计算方法, 在求解收敛性一致的前提下, 基于CUDA架构的并行PSO求解方法可以取得高达90倍的计算加速比。     

Large scale multiple sequence alignment with simultaneous phylogeny inference

Multiple sequence alignment (MSA) and phylogenetic tree reconstruction are one of the most important problems in the computational biology. While both these problems are of great practical significance, in most cases they are very computationally demanding. In this paper we propose a new approach to the MSA problem which simultaneously infers an underlying phylogenetic tree. To process large data sets we provide parallel implementation of our method, which is based on the distributed caching of intermediate results. Finally, we show a parallel server designed for grid environments, and we report results of experiments performed with actual biological data, e.g. 1000 ribosomal RNA sequences.     

不可压N-S方程的高效并行直接求解

对不可压N-S方程的数值计算,当计算规模增大时,不论是采用湍流模型计算还是直接数值模拟（Direct Numerical Simulation,DNS）,大规模的并行计算都难以实现.该问题的关键是求解全场联立的压力泊松方程的并行计算技术.利用并行近似解求解方案,创建高效大规模并行计算的不可压N S方程的直接求解方法.三维窄方腔热对流的DNS计算结果表明,该直接求解并行计算方法具有很好的并行效率,并且计算的三维湍流热对流的特性是合理的.     

Parallel exact sampling and evaluation of Gaussian Markov random fields

Markov chain Monte Carlo algorithms are computationally expensive for large models. Especially, the so-called one-block Metropolis-Hastings (M-H) algorithm demands large computational resources, and parallel computing seems appealing. A parallel one-block M-H algorithm for latent Gaussian Markov random field (GMRF) models is introduced. Important parts of this algorithm are parallel exact sampling and evaluation of GMRFs. Parallelisation is achieved with parallel algorithms from linear algebra for sparse symmetric positive definite matrices. The parallel GMRF sampler is tested for GMRFs on lattices and irregular graphs, and gives both good speed-up and good scalability. The parallel one-block M-H algorithm is used to make inference for a geostatistical GMRF model with a latent spatial field of 31,500 variables.     

用并行遗传算法解决带约束并行多机调度问题

遗传算法是一种全局优化的数值计算方法,它存在自然并行性,本文提出了一种解带约束并行多机调度问题的主从式控制网络并行遗传算法,并在PVM环境下实现。计算结果表明,并行遗传算法是有效的,且能适用于大规模并行多机调度问题。     

基于申威众核架构的分组卷积计算加速与优化

针对应用普通卷积结构的卷积计算复杂度较高、计算量与参数量较大的问题,提出以国产SW26010P众核处理器为平台的并行分组卷积算法。核心思想是利用独特的数据布局,通过多核映射处理进行并行计算。实验测试结果表明,与单核串行算法相比,使用该并行分组卷积算法可以获得79.5的最高加速比及186.7MFLOPS的最大有效算力。通过SIMD指令对并行分组卷积算法进行数据并行优化后,与使用优化前的并行分组卷积算法相比,可以获得10.2的最高加速比。     

多重网格格子Boltzmann方法的并行算法

针对复杂流动数值模拟中的格子Boltzmann方法存在计算网格量大、收敛速度慢的缺点,提出了基于三维几何边界的多重笛卡儿网格并行生成算法,并基于该网格生成方法提出了多重网格并行格子Boltzmann方法（LBM）。该方法结合不同尺度网格间的耦合计算,有效减少了计算网格量,提高了收敛速度;而且测试结果也表明该并行算法具有良好的可扩展性。     

用并行遗传算法解决带约束并行多机调度问题

遗传算法是一种全局优化的数值计算方法。它存在自然并行性。本文提出一种解带约束并行多机调度问题的主从式控制网络并行遗传算法,并在PVM环境下实现。计算结果表明,并行遗传算法是有效的,且能适用于大规模并行多机调度问题。     

Parallel distributed genetic fuzzy rule selection

Genetic fuzzy rule selection has been successfully used to design accurate and compact fuzzy rule-based classifiers. It is, however, very difficult to handle large data sets due to the increase in computational costs. This paper proposes a simple but effective idea to improve the scalability of genetic fuzzy rule selection to large data sets. Our idea is based on its parallel distributed implementation. Both a training data set and a population are divided into subgroups (i.e., into training data subsets and sub-populations, respectively) for the use of multiple processors. We compare seven variants of the parallel distributed implementation with the original non-parallel algorithm through computational experiments on some benchmark data sets.     

基于MapReduce的并行贝叶斯分类算法的设计与实现

针对现代大规模文本文档分类在单机计算机上训练和测试过程计算时间长,本文设计和实现了一种基于MapReduce架构的并行贝叶斯文本分类算法。在用普通PC搭建的Hadoop集群上研究实验,结果表明,基于MapReduce架构的贝叶斯文本自动分类算法处理大规模的文档自动分类时,在保证分类效果的情况下,并能获得接近线性的加速比。     

On the promise of general-purpose parallel computing

It has become generally accepted that continued improvements in high-performance scientific computation will be achieved only through the ‘exploitation of parallelism’. Despite the nebulous nature of this expression, enthusiasm for the potential of parallel computing has led to calls for improvements in computational performance of more than a thousand-fold in the next few years, or for what is sometimes referred to as a Teraflop (one trillion floating-point operations per second) Computer. Such a system is envisioned as a general-purpose tool for accelerating progress in such widely varied applications as astronomy, biochemistry, circuit analysis, computational fluid dynamics, global economic modeling, high energy physics, materials science, structural analysis, and weather prediction.

Although parallel architectures appear to offer the greatest promise for significant improvements in overall computational performance, it is not yet clear whether a general-purpose parallel architecture can realize the large increases solicited by the scientific community. This note will take a practical look at the prospect for general-purpose parallel computation and will consider some of the potential limitations by using a simple parametric model of computational performance.