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

摘要

本文主要研究光并行计算在数字图像信号处理和计算分子生物学中的应用。我们介绍了光并行计算的一种常用的LARPBS模型，以及在LARPBS上的一些基本操作，基础的矩阵乘法和排序算法；给出了在LARPBS上图像处理方面的Hough变换和欧几里得距离变换的快速并行算法；在计算分子生物学方面，我们探讨了LARPBS上用于解决最长公共子序列问题和序列对比问题的算法。　　本文提供的基于LARPBS的算法可以证明光并行计算强大的并行处理能力和高计算效率，特别是光并行计算应用于处理计算分子生物学中的问题必将会成为一个前景非常广阔的研究领域。

目录

文摘

英文文摘

攻读学位期间发表的深信论文和参加的研究工作

致谢

第一章引言

1.1背景介绍

1.2主要结果

1.3论文组织

第二章可重构的流水光总线模型及其基本操作

2.1背景介绍

2.2可重构的线性阵列模型—LARPBS

2.3脉冲吻合寻址技术

2.4基本数据操作

2.5矩阵乘法

2.5.1N2个处理器的矩阵乘法

2.5.2N3个处理器的矩阵乘法

2.5.3N2.8704个处理器的矩阵乘法

2.6排序问题

2.6.1使用N2个处理机O(1)时间完成的排序算法

2.6.2使用N个处理机的排序算法

2.6.3使用p个处理机的排序算法

2.6.4使用N个处理机的并行排序改进版本

2.7本章总结

第三章Hough变换

3.1背景介绍

3.2基本性质

3.3 Hough变换算法

3.4可扩放性分析

3.5本章总结

第四章欧几里得距离变换

4.1背景介绍

4.2 EDT的基本性质

43O(lognloglogn/logloglogm)的EDT算法

4.3.1算法描述

4.3.2复杂度分析

4.4 O(logn·loglogn)的EDT算法

4.4.1算法描述

4.4.2复杂度分析

4.5参数化的EDT

4.5.1算法描述

4.5.2复杂度和可扩放性分析

4.6本章总结

第五章最长公共子序列问题

5.1背景介绍

5.2研究回顾

5.3基础知识

5.4理论基础

5.5计算代价最优的快速并行算法

5.5.1快速算法

5.5.2复杂度分析

5.5.3代价最优的可扩放的并行算法

5.6更快速的并行算法

5.6.1子序列块的性质

5.6.2快速并行算法

5.6.3算法分析

5.6.4可扩放性分析

5.7本章总结

第六章序列对比问题

6.1背景介绍

6.2研究回顾

6.3理论基础

6.4序列对比的快速算法

6.4.1 LARPBS上的数据散射操作

6.4.2计算序列相似度的快速并行算法

6.4.3快速并行算法的复杂度分析

6.4.4时空最优的快速序列对比算法

6.4.5时空最优的快速序列对比算法的复杂度分析

6.4.6时空优化的快速序列对比算法的运行实例

6.4.7可扩放的空间节省的并行算法

6.4.8扩放的空间节省的并行算法复杂度分析

6.5本章总结

第七章结论

7.1我们的贡献

7.2将来的工作

参考文献