可擴展并行計算及其應(yīng)用研究.pdf

1、自90年代以來，為了適應(yīng)計算在科學(xué)研究和實際應(yīng)用中求解大規(guī)模問題和復(fù)雜系統(tǒng)的要求，高性能并行計算得以空前飛速發(fā)展。但隨著超級計算機規(guī)模的不斷擴大，并行算法的可擴展性研究日益得到重視。針對這種應(yīng)用需求，本文對平面Delaunay三角剖分(DT)的傳統(tǒng)高性能計算，以及SAT和精確覆蓋兩個經(jīng)典NP完全問題的非傳統(tǒng)高性能計算中的可擴展并行計算問題展開了研究。 首先，對于Delaunay三角剖分問題，目前已出現(xiàn)了不少成熟的算法，但這些算法

2、各有優(yōu)劣。本文結(jié)合逐點插入法和分治法，并引入著名的投影法和凸殼技術(shù)，提出了兩個DT并行算法。其中一個算法基于PRAM-EREW計算模型，在不增加總操作數(shù)復(fù)雜度的前提下，將時間復(fù)雜度減小到O(n)。算法雖然獲得了較好的時間性能，卻沒有考慮可擴展性。因此，本文同時提出一個基于PRAM-CREW計算模型的具有較好可擴展性的并行DT算法，新算法在保持總操作數(shù)O(nlogn)不變的情況下，時間性能可隨處理器個數(shù)的增加而提高。 對于NP完全

3、問題，傳統(tǒng)高性能計算依然不能解決計算時間或處理機個數(shù)呈指數(shù)增加的問題。DNA計算以其海量存儲和并行運算能力，被認為是解決NP完全問題和其它難解問題的潛在方案之一。但是，目前DNA計算中依然存在類似傳統(tǒng)高性能計算問題中的“指數(shù)爆炸”問題。針對這一現(xiàn)象，本文提出一種具有良好可擴展性的DNA計算機新模型，并將其成功應(yīng)用于求解精確覆蓋問題的DNA計算機算法，新算法在保持原有多項式時間復(fù)雜度的前提下，將所需的DNA鏈數(shù)從O(2n)降低到O(2n/