一種Delaunay三角網並行構建方法

2023-06-14 04:29:46 1

專利名稱：一種Delaunay三角網並行構建方法
技術領域：
本發明屬於計算 機網絡技術領域，涉及一種Delaunay三角網並行構建方法。該方 法可以充分利用計算節點資源，將Delaunay三角網構建過程最大並行化，取得了比較好的 效果。
背景技術：
在過去十幾年的時間內，國內外的眾多學者和專家在Delaunay三角網構建方法 上已提出許多有效的算法。一般可以將各種三角網算法分為逐點插入算法、三角網生長法 和分治算法。逐點插入算法最壞情況下的時間複雜度是0 (N2)。但是，若點是隨機插入的話， 其性能將能達到O(NlogN)。但由於算法過程需要排序，其時間複雜度不能進一步改進。分 治算法的效率很高，最壞情況下的時間複雜度都能達到0 (NlogN)，最好情況下其性能甚至 能達到O(NloglogN)。生長算法的效率最差，性能最高也只能達到O (Nv2)。隨著國內外研究的不斷深入和需求的不斷提升，特別是在大規模場景渲染和地形 可視化等領域中，為了進一步提高Delaunay三角網的構網速度，很多人採取混合Delaunay 三角網構建方法。目前研究較多的合成算法是把逐點插入法植入到分治方法中。但是由於 三角網生長方法在點集較小時也具有比較好的性能，所以當前在子三角網構建時採用三角 網生長方法的研究也開始出現。儘管經過多年的研究，Delaunay三角網的構建速度已經有了很大的提高。但是對 於大數量的建模，單機構網速率仍然非常有限，部分研究開始考慮在分治方法的基礎上對 構網過程進行並行處理，將大量的計算分給多個處理器來處理，從而達到提高算法運算速 度的目的。傳統的Delaunay三角網並行構建系統結構有兩種對等式結構和主從式結構，如

圖1所示。對等式結構(如圖1(a)所示)存在一定的缺陷，主要體現在系統中的每一個 計算節點都要同時具有動態管理和計算的功能，並且各個節點都會與其他節點持續保持數 據交換，通信開銷較大，管理相對分散，軟體開發實現難度大。主從結構模式(圖1(b))雖 然解決了對等式結構的缺陷，但是又引入了新的問題，主要體現在以下幾點(1)主機主要 工作任務是資源的管理、並行計算任務的發起和節點計算結果的匯總，並沒有充分利用其 資源；(2)所有任務劃分、分配、匯總都由主機來完成，沒有將這些過程充分並行化；(3)葉 子節點除了與主機進行通信外，還需要與其他葉子節點進行通信，通信開銷沒有降到最小。

發明內容
本發明的目的在於提供一種Delaunay三角網並行構建方法。本發明經過對 Delaunay三角網構建算法、並行計算理論以及網絡通信方式等知識的研究，借鑑各種結構 和思想的優點，提出了本發明的方法；該方法將任務的劃分、分配和合併過程在每個非葉子 計算節點上進行，既減輕了主機的瓶頸效應，又能夠將分割和合併操作並行化，大大地提高 了 Delaunay三角網並行構建速度。並且每層計算節點之間無需通信，在一定程度上減少了通信開銷。
本發明方法涉及的主要內容包括
1.多叉樹式並行計算結構
多叉樹式並行結構是以主從結構為基礎，動態添加計算節點的網絡計算結構。其 三層計算結構如圖2所示，該結構與傳統的主從結構模式的不同點在於
1)傳統的主從模式結構下，主機主要工作任務是資源的管理、並行計算任務的發 起和節點計算結果的匯總。但多叉樹式並行計算結構中的主機還將負責部分子任務的計算 工作，充分地利用了主機的資源。
2)傳統的主從模式結構下，除了主機之外，所有的計算節點都是葉子節點，不存在 非葉子節點。但多叉樹式並行計算結構中有非葉子節點，每個非葉子節點的工作內容是任 務劃分和分配，逐點插入法構建三角網、子節點的三角網和自身節點三角網的合併以及將 合併結果返回給父親節點。
3)傳統的主從模式結構下，葉子節點除了與主機進行通信外，還需要與其他葉子 節點進行通信。但多叉樹式並行計算結構中，葉子節點之間不需要進行通信，只需要與其父 節點進行通信即可。同時非葉子節點也不需要與其同層次的非葉子節點之間通信，它也只 需要與其子節點和父親節點進行通信。
4)傳統的主從模式結構是靜態的，而多叉樹式並行計算結構是動態構成的，節點 之間的父子關係是可變的。
2.主機及計算節點工作流程
主機節點的功能主要有4個方面
1)維護計算節點狀態信息；狀態信息的數據結構如圖6所示；
2)構建一部分數據的三角網；
3)發送點集數據(用於構建三角網的採樣點數據信息，即輸入數據)給空閒的計 算節點，並收集合併計算節點的構建結果。
4)根據合併的構建結果繪製三角網；
其工作流程如圖3所示。具體步驟闡述如下
步驟1 主機在接受輸入的點集數據以後，首先判斷該點集的數據點數目是否超 過閾值，如果不超過給定閾值，則直接進行三角網構建並進行步驟6 ；
步驟2 如果輸入的點集中數據點的數目超過了給定的閾值，則需要獲取當前網 絡中可用的節點數目n，並判斷輸入的點集中數據點的數目是否超過了 η*給定閾值，如果 不超過η*給定閾值，直接進行步驟3 ；如果超過η*給定閾值，即輸入點集規模超過了當前 網絡的處理能力，則需要將輸入點集進行分割，保留η*給定閾值數量的數據點，進行步驟 3 ；
步驟3 將輸入點集分割成兩份，當前節點保留一份，將另一份分配給其子節點； 重複該步驟直到網絡中每個節點所處理的點集中數據點數量都小於給定閾值；
步驟4 每個節點中進行三角網構建；該過程並行執行；
步驟5 每個父節點接受其子節點所構建的三角網並對其進行正確合併；
步驟6 繪製所構建的三角網，程序結束。
非葉子節點的功能主要有5個方面5
1)接收父節點分配的點集數據；
2)將點集數據分割後，將其中一部分分配給空閒的計算節點；
3)構建一部分數據的三角網；
4)收集合併各子計算節點的構建結果；
5)將合併後的結果數據發送給父節點。
葉子計算節點的功能主要有3個方面
1)接收父節點分配的點集數據；
2)逐點插入串行構建三角網；
3)將三角網構建結果數據發送給父節點。
儘管運行在非葉子節點和葉子節點上的程序功能有所差異，但是其程序是一樣 的，只因為點集數量與閾值之間的不同大小關係形成了不同分支而已。並且本文的節點網 絡結構是動態的，所有的計算節點有可能成為葉子節點，也有可能成為非葉子節點。其工作 流程如圖4所示。具體步驟如下
步驟1 接受父節點所分配的點集數據；
步驟2 當前節點判斷所處理的點集中的數據點是否超過給定閾值，若超過給定 閾值，則對點集進行分割，當前節點保留一份，將另一份分配給其子節點；該步驟重複進行， 直到當前節點所處理的點集中數據點的數量不超過給定閾值；若不超過給定閾值，則直接 進行步驟3 ；
步驟3:構建三角網；
步驟4 判斷當前節點是否為葉子節點，若為葉子節點，直接進行步驟5 ；否則，接 受並合併當前節點的所有子節點所構建的三角網；
步驟5 將所構建的三角網返回給當前節點的父節點，程序結束。
3.任務劃分策略
並行計算方法應當保證點集分割後的每個區域的點數量大致相當，否則很難做到 負載均衡。傳統的分治算法進行分割時，是採取按照X坐標值或者y坐標值等分區域的做 法，當點分布不均勻時，這種方法很難保證分割後每個子區域點數量大致相當。本文採取的 方法則是按照點的數量嚴格進行分割。具體的分割方法首先是根據並行系統中計算節點的 數量來確定一次並行算法能夠處理的點數據總量。也就是說若系統中有N個節點，且分割 閾值是P的話(分割閾值P是指系統中每個節點能夠處理的最大數據量)，那麼一次並行構 網所能處理的最多點數據量為N*P個。由於點數據集在進行分割之前已經進行了排序預處 理，且排序之後的點存儲在向量數組vector中，而vector是可以通過下標進行訪問的。所 以每次分割的時候，就可以通過當前點數據集範圍的最小下標和最大下標的中間值來確定 分割點，將會非常精確。另外每次分割的初始值都是N*P，所以經過精確分割後，最終每個計 算節點所得到的計算量都會在P左右，這就很好的控制了負載均衡。
4.閾值選擇策略
分治算法的時間複雜度模型如下
T (η) = 2Τ (η/2) +η
逐點插入算法的時間複雜度為0(η2)，設分割閾值為Φ，那麼可以計算出分割次數 λ = 10 (n/Φ)，即分治算法的時間複雜度模型最多只能迭代λ次，最後可得分治逐點插入算法的時間複雜度如下。T(η, Φ) = ηλ +2λΤ(Φ)(1)進一步求解得Τ(η, Φ) = η1οδ2(η/Φ) + (η/Φ)0(Φ2) (2)對⑵式進行一定的變換，可以得式子Τ(η，Φ) = η1ο&η+η(0(Φ)-1ο&Φ)(3)設0( Φ) = kcK對(3)式在Φ方向求偏導後得式子
權利要求
1.一種Delaimay三角網並行構建方法，其步驟為1)主機節點接收到輸入的點集數據後，判斷該點集數據是否超過設定閾值P，如果超 過閾值P，則進行步驟2)，否則直接進行三角網構建並繪製所構建的三角網；2)主機節點獲取當前網絡中可用的節點數目n，並判斷該點集數據是否超過nXP，如 果未超過則進行步驟3)；否則保留該點集數據中nXP個數據點，進行步驟3)；3)主機將該點集數據分成兩份，主機節點保留一份，將另一份分配給其子節點；4)主機節點及其子節點分別判斷分配給自己的數據是否超過設定閾值P，如果未超過 則進行步驟5)；如果超過則將分配給自己的數據分為兩份，自己保留一份，將另一份分配 給其子節點，直到網絡中每個節點所處理的數據點數量都未超過閾值P ；5)每個節點分別對其最終所留數據進行三角網構建；6)葉子節點將所構建的三角網發送給其父節點，父節點對其子節點的三角網進行合併 後的三角網發送給其父節點，直到主機節點；7)主機節點對自己所建三角網以及收到的三角網進行合併。
2.如權利要求1所述的方法，其特徵在於每一父節點分別維護一個棧來管理其子節 點，該棧內信息包括節點標識號。
3.如權利要求2所述的方法，其特徵在於父節點進行三角網合併的方法為1)父節點接收其子節點所生成的三角網數據，如果父節點正在進行合併操作，則將該 子節點的合併任務放入父節點的等待列表中；否則進行步驟2)；2)父節點判斷該子節點的標識號是否與棧頂元素相同，若不同，則將該子節點的合併 任務放入等待列表中；否則，進行步驟3)；3)將子節點返回的三角網與父節點所生成的三角網進行合併，同時彈出棧頂元素；4)父節點檢查棧是否為空，若為空則合併結束；否則進行步驟5)；5)父節點檢查合併任務等待列表是否為空，若為空則合併結束；否則進行步驟6)；6)父節點取出等待隊列中的合併子任務，按照步驟2) 5)進行合併直到任務等待列 表為空。
4.如權利要求2或3所述的方法，其特徵在於所述標識號為節點的IP位址。
5.如權利要求1所述的方法，其特徵在於父節點分配點集數據時，對分給其子節點的 數據保留一數據副本，並記錄該子節點的標識號；然後將其子節點的標識號與分給該子節 點的數據區域號進行綁定。
6.如權利要求5所述的方法，其特徵在於每個計算節點分別在設定時間間隔t內向主 機及其父節點發送心跳信息；當父節點在設定時間T內沒有收到某子節點的心跳消息，則 父節點將其確定為故障節點，父節點查詢本地保存的區域分配信息，根據故障節點標識號 找出需要重新構建的數據點集；然後向主機申請空閒計算節點，若申請到空閒節點，則父節 點分割此塊數據，並將其中一部分發送給新申請到的節點，否則另啟一線程在本地對需要 重新構建的數據點集三角網構建。
7.如權利要求6所述的方法，其特徵在於當故障節點為非葉子節點時，主機停掉故障 節點及其所有子節點的工作，並將它們都設置成「閒」和「未分配」狀態。
8.如權利要求1或2或3或5或6或7所述的方法，其特徵在於所述點集數據存儲於 已向量數組中，父節點根據點集數據的最小下標和最大下標的中間值對所述點集數據進行劃分。
9.如權利要求1或2或3或5或6或7所述的方法，其特徵在於計算所述閾值P的方 法為Ρ = ;，其中，k為環境因素參量。 km2
10.如權利要求1或2或3或5或6或7所述的方法，其特徵在於所述三角網的構建方 法為逐點插入三角網構建方法。
全文摘要
本發明公開了一種Delaunay三角網並行構建方法，屬於計算機網絡技術領域。本方法為主機節點判斷輸入點集數據是否超過設定閾值P，如果超過則獲取可用的節點數目n；如果該點集數據超過n×P，則保留該點集數據中n×P個數據點；將該點集數據分成兩份，自己保留一份，另一份分給其子節點；主機節點及其子節點分別判斷分給自己的數據是否超過設定閾值P，如超過則繼續進行分配，直到每個節點的數據點都未超過閾值P，如未超過則每個節點對其最終所留數據進行三角網構建；葉子節點將所構建的三角網發送給其父節點進行合，直到主機節點；主機節點對自己所建三角網以及收到的三角網進行合併。本發明充分利用計算節點資源，將三角網構建過程最大並行化。
文檔編號H04L29/08GK102045196SQ201010578848
公開日2011年5月4日 申請日期2010年12月8日 優先權日2010年12月8日
發明者余杰, 呂品, 張潔, 鄭昌文 申請人:中國科學院軟體研究所