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

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

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

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