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

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

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

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