点对多边形位置检测的稳定串行最优与并行的算法

点相对于多边形位置检测是计算机图形学中的一个底层而基本的问题,目前的算法较多,但这些算法要么复杂,要么不稳定,都或多或少存在一些问题。为改进算法,首先从分析直线的正负性入手,进一步全面描述了点与有向线段的各种相互位置关系及相应的处理步骤。借助于正负性,不仅简化了点与有向线段的位置判断,降低了算法复杂性,更彻底消除了各种不稳定的因素。算法处理如此的精细也保证了算法的可并行性,实现了串、并行算法。实验证明,串行算法是一个稳定的最优算法。

一种优化BITONIC算法:“并行-优化-串行”合并和分类向量算法

串行算法并行化是发挥各种巨型机的效率的关键技术之一 .“并行 -优化 -串行”归并向量算法 ( POSVM) ,是一种串行算法并行化的优化方法 .它用 O( N / p )时间把总长为 N的两个有序序列归并或把总长为 N的一个Bitonic序列排序 .“并行 -优化 -串行”排序向量算法 ( POSVS)用 O( ( N log N) / p)时间在实际 SIMD机上把 N个数排序 .这些是第 1个满足以下两个条件的向量 Optimal算法 (加速比 =O( p ) ) .1它能在实际 SIMD计算机上实现 .处理机的台数 p的范围很宽 1≤ p≤ N 1-ε,这里 ,ε是任意的小的正数 .2它统一了 3种不同类的合并算法 :Batcher的 Bitonic算法 (最快但效率随参数变大而趋向于 0 )、优化 ( Optimal)算法 (效率为常数的算法 )和最佳的串行算法 .而且也综合了 3个算法的优点 .“并行 -优化 -串行”( POS)方法是一个通用方法 。

多核处理器环境下遥感数据处理的并行与串行算法的性能比较

卫星遥感能够提供（准）实时地面信息，在地震研究中的应用越来越广泛。MODIS是搭载在Terra和Aqua两颗卫星上的重要的“图谱合一”光学遥感观测仪器。由于MODIS数据具有多频段、高分辨率、高时效性、应用广泛等特点，使得MODIS数据对地球科学的综合研究和对陆表、生物圈、固态地球、大气和海洋的长期观测有着重要意义，在自然灾害的监测和分析研究领域也有着广泛的应用。

翼型绕流数值模拟中串行和并行算法的比较分析

用串行算法和并行算法进行复杂旋转机械中翼型绕流的数值计算,这一过程包括网格生成,压力场、密度场和速度场的求解,以及后处理过程,并同实验数据相比较。结果表明:并行算法是可行的,并且具有收敛快,计算稳定的优点。

串行程序的并行划分算法研究

提出了将串行程序并行化的方法 .首先对串行程序进行分段 ,提出并行划分模型 ,基于这个模型提出一种并行划分算法PDMA ;然后给出了相关程度的定义 ,并根据程序段之间相关程度 ,提出了一种对PDMA进行改进的并行划分方法RPDMA ;最后对这两种算法进行了比较和时间复杂度分析 .

基于FPGA的CRC算法的串行和并行实现

在数字数据通信系统中,由于信道传输特性不理想以及噪声等干扰,常常会出现一些异常情况。因此,通常在数据通信中添加循环冗余校验(cyclic redundancy check,CRC)码,可以大幅度提高通信的可靠性。文章在论述串行CRC实现的基础上,对电路结构提出了改进的方案,实现了基于现场可编程逻辑门阵列(field programmable gate array,FPGA)的CRC的串行2、4、8位和并行算法,并用超高速集成电路硬件描述语言(very-high-speed integrated circuit hardware description language,VHDL)实现CRC校验,将实验结果下载到DE2,验证了方案的可行性。

基于串行FastLSA的并行算法

提出了一种基于串行FastLSA算法的两个序列比对的并行算法。主要是对海量级的序列比对,目的是减少串行FastLSA算法的时间和空间的复杂度。实验结果表明该算法完全可以并行化,而且空间复杂度降到线性空间。

求复函数方程的根的串行和并行算法

主要研究了求复函数方程的根的串行和并行算法，探讨了并行算法中的任务分配方案、负载平衡等问题，并对串行算法和并行算法的实现结果进行了比较和分析。

基于VHDL的并行到串行转换器算法模型

以并行到串行转换器为例介绍一种建立器件算法模型的方法。该方法利用进程模型图给出器件行为级的结构体的图形表示,从而可实现自然语言描述到VHDL算法模型的映射。从本文可以得出,进程模型图可以清晰表示行为域中算法级模型的结构,利用这种方法可产生易于理解的、全面的算法模型。

实时数值仿真几类并行与串行算法的特性分析

针对动力学系统实时数值仿真,分析了实时数值仿真的特点,概述了实时数值仿真算法的一般的构造思想。重点讨论和分析了几类实时数值仿真的并行算法的具体构造思想、方法,收敛阶、数值稳定性、加速比、并行效率、应用的特性。类似地分析了几类实时数值仿真的串行算法的构造特点、快速性、数值稳定性和计算复杂性等。并指出了进一步的研究方向。

USB数据传输中CRC校验码的并行算法实现

文章介绍了用于USB总线数据传输的CRC校验的原理和算法,并且采用并行电路实现USB2.0中的CRC产生和CRC校验,与传统的串行电路实现相比,并行电路实现方法虽然在芯片面积上大于串行电路实现,但由于降低了时钟频率,电路更容易综合实现,并且大大降低了功耗,有利于低功耗电路设计。

流域变换的串行与并行策略研究

流域变换是数字形态学中用于图像分割的一种经典方法,其并行化问题成为近年来研究的重点。首先给出了流域变换的数学模型,并归纳列举了几种离散情况下的形式化定义;其次分类总结了近年来流域变换串行算法研究的新进展,从而在此基础上重点讨论了相应的并行化策略。详细分析了设计并行流域算法需要考虑的几个问题;并比较评价了现有并行算法的性能特点,得出了一些结论;最后提出了有待进一步研究的问题。

解线性最小二乘问题的一个新并行算法

讨论了求解无约束线性最小二乘问题的一种并行单纯形法以及对它的改进算法并行共轭梯度—单纯形法 .算法本身具有很强的并行机制 ,能够充分地发挥并行机快速省时的特点 .本文也对算法做了理论分析 ,对算法的收敛性给予了证明 (在二维情形下 ) .最后做了数值实验 (由于软硬件条件的限制 ,并行算法未能在并行计算机上实现 ,鉴于这种情况 ,我们所做的数值实验均是在串行机上完成的 )

对称正定矩阵的并行LDL^T分解算法实现

基于网络机群这一新的并行环境和消息传递界面MPI给出了两种不带平方根的Cholesky并行分解算法, 算法采用行卷帘存储方案和提前发送策略,从而减少了负载的不平衡,增加了计算通信的重叠,减少了通信时 间。理论分析和数值试验均表明,算法具有较高的并行加速比和效率。

生物多序列比对的并行算法

多序列比对是生物信息学中的基本问题。由于生物序列数据库的快速增长,即使优秀的串行算法已不能满足实际的需要。研究了Gusfield提出的星型比对模型的串行算法,进行了空间和时间上的改进,基于cluster结构的某并行机提出了一种并行算法,并对大量基因数据进行了测试,结果表明对于大规模的多序列比对,算法能达到较高的加速比。

并行数据库中JOIN运算的并行算法

JOIN运算的并行算法一直是并行数据库领域中研究的热点问题,先后出现了一系列并行JOIN算法或改进算法,但它们都存在着通信效率较低、负载调度频繁等问题。本文针对这些问题,在分析比较前人工作的基础上对SABJ+算法与ABJ+算法加以改进,得到了效率更高的并行JOIN算法ABJ++。

串行程序在大粒度级的并行分解及可并行执行包的形成

本文提出了针对由划分阶段所形成的任务图［７］进行优化、合并的技术及相应的算法，用于在并行与通信开销间进行折衷，以使分解出的并行成份有尽可能高的执行效率。本文还给出了根据综合后的任务图形成可并行执行包，并在其中自动插入通信原语的方法。

表调度算法的并行化研究

当目标处理器个数大于2时,调度任意结构并行任务图并获取最优解的问题是NP完全难题。表调度算法作为一类代表性的启发式任务调度算法具有调度性能较好而时间复杂度较低的优点。但当任务图的规模较大时表调度算法的耗时也很可观,无疑并行表调度算法是一种好的解决方法。本文在串行算法LBP的基础上提出了一个新的表调度并行算法PLBP,该算法在保证与串行算法同样调度性能的前提下,时间复杂度有较大的改善。同时,与已有的表调度并行算法相比较,PLBP算法有更小的时间复杂度。

基于LogP简化模型的矩阵求逆并行算法研究

LogP is becoming a practical parallel computation model that meets the demanding of parallel computersand parallel algorithms. So it is important to re-design parallel algorithms on the LogP model. This paper studies theparallel algorithm of computing converse matrix on the simplified LogP model, and gets the simulating results.

实部半正定矩阵的判定及并行算法

给出了实部半正定矩阵的一种判定方法 ,并给出了该判定方法的算法 .使用此方法可以对任意阶的矩阵进行判定 .