共查询到11条相似文献,搜索用时 66 毫秒
1.
基于可分负载理论的最优原则,在假定正文串分配顺序固定的前提下,考虑处理机节点具有不同计算速度、不同通信能力的情况,提出一种异构机群计算环境下的最优正文串分配策略,给出最优正文串分配的闭合解。对于节点具有不同计算速度、通信能力、存储容量的异构机群系统,建立正文串最优分配的线性规划模型。针对几种特殊情况讨论正文串的最优分配顺序。实验结果表明,与平均分配正文串策略以及按照从处理机能力分配正文串策略相比,利用该策略进行近似串匹配并行处理所需时间分别缩短了10%~40%和5%~20%。 相似文献
2.
分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n2)处理器,时间复杂度为O(log2n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n3)处理器,计算时间复杂度为O(logn). 相似文献
3.
4.
存储受限异构机群系统的多目标串近似匹配并行算法 总被引:1,自引:0,他引:1
针对处理机节点具有不同的计算能力、通信延迟和存储容量的情形,考虑计算和通信启动开销,给定处理机分配顺序,基于可分负载理论,分别建立单层和两层树结构模型的存储受限异构机群系统的目标串最优分配线性规划模型,给出相应的目标串最优分配方法,并讨论了处理机最优分配顺序.实验结果表明,本文提出的基于最优分配方法的多目标串近似匹配并行算法优于平均分配算法,获得了较好的加速并具有良好的可扩展性. 相似文献
5.
异构机群系统上基于多轮分配方式的近似串匹配并行算法 总被引:1,自引:0,他引:1
在给定正文串分配轮数的前提下,考虑处理机节点具有不同计算速度、不同通信能力的情形,根据从处理机是否允许重叠执行计算和通信操作,提出异构机群计算环境下的最优正文串多轮分配策略;同时提出一种周期性的正文串多轮分配策略并给出了相应的正文串多轮分配的闭合解,此策略可以求出最优的分配轮数.实验结果表明,正文串多轮分配策略比正文串单轮分配策略大大缩短了近似串匹配并行处理的时间,并且在正文串多轮分配策略中,当近似串匹配应用的规模较小时,分配轮数比参与近似串匹配并行处理的从处理机数更能影响近似串匹配并行处理的完成时间,反之,从处理机数对近似串匹配并行处理的完成时间影响更大. 相似文献
6.
CUDA (Compute Unified Device Architecture)是一种重要的并行处理架构,但其具有相对复杂的线程管理机制和多重存储模块,从而使得基于CUDA的算法时间复杂度很难量化.针对这一问题,提出了一种分层存储理论模型—HMM (Hierarchical Memory Machine)模型,该模型所具有的分层存储结构可以有效地描述图形处理单元设备不同存储模块的物理特性,因此非常适用于对CUDA算法时间复杂度的量化评估.作为HMM模型的应用实例,文章提出了一种基于HMM模型的并行近似字符串匹配算法,并给出了相应算法时间复杂度的计算过程.与串行算法相比,该算法可以获得60倍以上的加速比. 相似文献
7.
8.
基于匹配区域特征的相似字符串匹配过滤算法孙德才 总被引:1,自引:0,他引:1
相似字符串匹配过滤算法因其适合大库查找而被广泛应用,为通过提高过滤算法的过滤效率加快匹配速度,提出一种基于匹配区域特征的过滤算法.该算法将模式串和文本串分割成固定长度为kq+1的逻辑块,并从各块中提取了2个新的匹配区域特征:q-gram命中的均匀性和q-gram有效命中的区域性.新算法利用这些新特征优化了传统过滤标准,提高了算法的过滤效率;并改进了QUASAR中基于分块策略的过滤区确定方案.实验结果表明,新算法与改进前相比有效地加快了匹配速度,尤其在误差率较小时改进效果更佳. 相似文献
9.
10.
In this paper, we present deterministic and probabilistic methods for simulating PRAM computations on linear arrays with reconfigurable pipelined bus systems (LARPBS). The following results are established in this paper. (1) Each step of a p-processor PRAM with m=O(p) shared memory cells can be simulated by a p-processors LARPBS in O(log p) time, where the constant in the big-O notation is small. (2) Each step of a p-processor PRAM with m=(p) shared memory cells can be simulated by a p-processors LARPBS in O(log m) time. (3) Each step of a p-processor PRAM can be simulated by a p-processor LARPBS in O(log p) time with probability larger than 1–1/pc for all c>0. (4) As an interesting byproduct, we show that a p-processor LARPBS can sort p items in O(log p) time, with a small constant hidden in the big-O notation. Our results indicate that an LARPBS can simulate a PRAM very efficiently. 相似文献
11.
基于Hausdorff距离的图像匹配算法鲁棒性较好,但计算代价较大,软件实现方案很难满足实时性要求。为了解决这个问题,本文在基于局部Hausdorff距离的图像匹配算法基础上提出了一种鲁棒而实时的FPGA实现方案。为了充分有效利用FPGA的硬件资源,首先对传统串行算法进行并行性分析,提出了一个并行算法;然后以此为基础设计了一种三段式粗粒度流水体系结构,并将其映射到FPGA上进行实现。实验结果表明,该系统在性能上优于其它相关工作,与PC(Pentium42.8GHz)上的软件实现方案相比可以达到接近50倍的加速比。 相似文献