论文部分内容阅读
光并行计算具有时延的精确性、极高的传输速度、高带宽、高可靠性,能够同时处理大量的数据等特点。本文主要研究光并行计算在数字图像信号处理和计算分子生物学中的应用。我们介绍了光并行计算的一种常用的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的算法可以证明光并行计算强大的并行处理能力和高计算效率,特别是光并行计算应用于处理计算分子生物学中的问题必将会成为一个前景非常广阔的研究领域。