PRAM和LARPBS模型上的近似串匹配并行算法

作     者：钟诚 陈国良 

作者机构：中国科学技术大学计算机科学与技术系安徽合肥230027 国家高性能计算中心安徽合肥230027 

基　　金：国家重点基础研究发展规划(973)No.G1998030403 国家高技术研究发展计划(863)No.2001AA111041 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2004年第15卷第2期

页      码：159-169页

摘      要：近似串匹配技术在网络信息搜索、数字图书馆、模式识别、文本挖掘、IP路由查找、网络入侵检测、生物信息学、音乐研究计算等领域具有广泛的应用.基于CREW-PRAM(parallel random access machine with concurrent read and exclusive write)模型,采用波前式并行推进的方法直接计算编辑距离矩阵D,设计了一个允许k-差别的近似串匹配动态规划并行算法,该算法使用(m+1)个处理器,时间复杂度为O(n),算法理论上达到线性加速;采取水平和斜向双并行计算编辑距离矩阵D的方法,设计了一个使用a(m+1)个处理器和O(n/a+m)时间的、可伸缩的、允许k-差别的近似串匹配动态规划并行算法,+<11mna.基于分治策略,通过灵活拆分总线和合并子总线动态重构光总线系统,并充分利用光总线的消息播送技术和并行计算前缀和的方法,实现了汉明距离的并行计算,设计了两个基于LARPBS(linear arrays with reconfigurable pipelined bus system)模型的通信高效、可扩放的允许k-误配的近似串匹配并行算法,其中一个算法使用n个处理器,时间为O(m);另一个为常数时间算法,使用mn个处理器.

主 题 词：近似串匹配 并行算法 CREW-PRAM(parallel random access machine with concurrent read and exclusive write) 可重构光总线系统 编辑距离 汉明距离 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.13328/j.cnki.jos.2004.02.001

馆 藏 号：203382958...