光并行计算及其在图像处理和计算分子生物学中的应用

来源 :扬州大学 | 被引量 : 0次 | 上传用户:xiaoping123123
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
光并行计算具有时延的精确性、极高的传输速度、高带宽、高可靠性,能够同时处理大量的数据等特点。本文主要研究光并行计算在数字图像信号处理和计算分子生物学中的应用。我们介绍了光并行计算的一种常用的LARPBS模型。,以及在LARPBS上的一些基本操作,基础的矩阵乘法和排序算法;给出了在LARPBS上图像处理方面的Hough变换和欧几里得距离变换的快速并行算法;在计算分子生物学方面,我们探讨了LARPBS上用于解决最长公共子序列问题和序列对比问题的算法。 在本文中我们给出了使用m·n2个处理机,常数时间的Hough变换并行算法,该算法提升了Hough变换并行算法的计算速度和效率,使它们皆达到最优。 在欧几里得距离变换(EDT)方面,我们的设计的三个算法得到如下的结果:第一个算法使用了n2个处理机,可以在O(logn·loglogn/logloglogn)时间内完成;第二个算法使用了O(n2/loglogn)个处理机,时间复杂度为O(logn·loglogn);第三个是参数化的算法,使用n·d(n)·c(n)个处理机可以在O(nlogn/(c(n)·logd(n)))时间完成,这里c(n)和d(n)满足1≤c(n)≤n和1<d(n)≤n,特别地,若取c(n)=n,d(n)=nε,这昊ε为满足O<ε≤1的常数,则算法的处理机数为n2+ε,时间复杂度为O(1),这是目前常数时间EDT算法中效率最好的算法。 对于最长公共子序列问题,我们设计了使用p(1≤p≤max{m,n})台处理机,在(二)(mn/p)的时间内完成,每台处理机使用D((m+n)/p)空间的时空代价最优的并行算法;我们还给出了一个时间复杂度为O(logm)快速算法,据我们所知这是当前最快的最长公共子序列问题的并行算法。 最后在序列对比问题上,我们通过深入的理论推导得出序列对比的行递推定理,使得序列对比的递推公式可以逐行并行计算。基于行递推定理,我们给出了使用p(1≤p≤n)个处理机,每个处理机仅需要O((m+n)/p)的空间,可以在O(mn/p)的时间内完成的可扩放性快速算法,据我们所知这是第一个可扩放性的时空代价都达到最优的序列对比的并行算法。 本文提供的基于LARPBS的算法可以证明光并行计算强大的并行处理能力和高计算效率,特别是光并行计算应用于处理计算分子生物学中的问题必将会成为一个前景非常广阔的研究领域。
其他文献
随着互联网的不断发展,网络资源变的越来越丰富。传统的技术模式已难以满足人们的要求,一些更灵活、更先进的计算模型应运而生。移动代理技术就是在这种背景下产生的。 移动
近年来,基于模糊建模的不确定非线性系统的鲁棒自适应控制一直是智能控制研究的热点之一。本文就此领域的相关问题展开系列研究。 首先,针对一类具有未知函数控制增益的不
首先,本文以原有PRDX数据发布系统为基础,针对原有XML数据发布系统中查询模块的查询性能优化问题进行研究,从提高原数据系统查询效率的角度,对原有系统查询部分进行改进,大大地
基于XML标准的Web服务是目前动态电子商务和企业应用继承优秀的解决方案,它可以实现客户和企业及企业和企业之间快速而灵活的信息共享与资源互用.Web服务技术可以通过Interne
  本文主要的研究方向是网络视频会议系统中的底层数据传输,目标是实现支持基于互联网的大规模交互式应用的可靠多播协议。本文提出了基于树形结构的可靠多播协议(Tree-base
本文提出把容错机制引入网格中,并提出了以检查点算法为基础、以进程迁移为任务的载体实现容错机制,为网格系统容错机制的进一步实现和发展奠定基础。本文提出了检查点和回
PDM是Product Data Management(产品数据管理)的缩写。PDM是以软件技术为基础,以产品为核心,实现对产品相关的数据、过程、资源统一集成管理的技术。 利用PDM进行信息管理是
本课题研究对象是如何在与地面网有着很大差别的卫星网络中实施有效的流量工程技术及其性能优化问题,以满足日趋重要的宽带卫星网络稳定传输大业务量的需求。卫星网络的动
随着我国证券市场逐步走向规范与成熟,作为证券市场重要组成部分的证券公司及其下属的交易营业部也从暴利时代进入了微利时代。如何通过提高咨询业务的服务水平来摆脱市 场低
本文主要从查询处理自适应性方面进行研究,在已经存在的适应性查询处理技术基础之上,将自适应性与遗传算法相结合,提出自适应性遗传算法,并给出实验结果。本文的主要研究成果如下