pram和larpbs模型上的近似串匹配并行算法

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