基于圖形處理器的形態(tài)學(xué)重建系統(tǒng)

何希 吳炎桃 邸臻煒 陳佳

摘 要：形態(tài)學(xué)重建是醫(yī)學(xué)圖像處理中非?；A(chǔ)和重要的操作。它根據(jù)掩膜圖像的特征對標(biāo)記圖像反復(fù)進(jìn)行膨脹操作，直到標(biāo)記圖像中的像素值不再變化為止。對于傳統(tǒng)基于中央處理器（CPU）的形態(tài)學(xué)重建系統(tǒng)計(jì)算效率不高的問題，提出了使用圖形處理器（GPU）來加速形態(tài)學(xué)重建。首先，設(shè)計(jì)了適合GPU處理的數(shù)據(jù)結(jié)構(gòu)：并行堆集群;然后，基于并行堆集群，設(shè)計(jì)和實(shí)現(xiàn)了一套基于GPU的形態(tài)學(xué)重建系統(tǒng)。實(shí)驗(yàn)結(jié)果表明，相比傳統(tǒng)基于CPU的形態(tài)學(xué)重建系統(tǒng)，基于GPU的形態(tài)學(xué)重建系統(tǒng)可以獲取超過20倍的加速比。基于GPU的形態(tài)學(xué)重建系統(tǒng)展示了如何把基于復(fù)雜數(shù)據(jù)結(jié)構(gòu)的軟件系統(tǒng)高效地移植到GPU上。

關(guān)鍵詞：圖形處理器;形態(tài)學(xué)重建;并行計(jì)算;并行堆;并行數(shù)據(jù)結(jié)構(gòu)

Abstract： Morphological reconstruction is a fundamental and critical operation in medical image processing， in which dilation operations are repeatedly carried out on the marker image based on the characteristics of mask image， until no change occurs on the pixels of the marker image. Concerning the problem that traditional CPU-based morphological reconstruction system has low computational efficiency， using Graphics Processing Unit （GPU） to quicken the morphological reconstruction was proposed. Firstly， a GPU-friendly data structure： parallel heap cluster was proposed. Then， based on the parallel heap cluster， a GPU-based morphological reconstruction system was designed and implemented. The experimental results show that compared with traditional CPU-based morphological reconstruction system， the proposed GPU-based morphological reconstruction system can achieve speedup ratio over 20 times. The proposed system demonstrates how to efficiently port complex data structure-based software system onto GPU.

Key words： Graphics Processing Unit （GPU）; morphological reconstruction; parallel computing; parallel heap; parallel data structure

0 引言

形態(tài)學(xué)重建（morphological reconstruction）是醫(yī)學(xué)圖像處理中非?；A(chǔ)和重要的操作。它根據(jù)掩膜圖像的特征對標(biāo)記圖像反復(fù)進(jìn)行膨脹操作，直到標(biāo)記圖像中的像素值不再變化為止。其中的標(biāo)記圖像（Marker Image）和掩膜圖像（Mask Image）是兩張尺寸相同的高像素醫(yī)學(xué)圖像。在標(biāo)記圖像的膨脹操作中，符合擴(kuò)散條件的像素點(diǎn)會(huì)不斷地向鄰接的像素點(diǎn)傳播其像素值。假設(shè)I（e）、I（f）是標(biāo)記圖像中相鄰的兩個(gè)像素點(diǎn)，J（e）是掩膜圖像中與I（e）位置相對應(yīng)的像素點(diǎn)，那么I（f）對I（e）發(fā)生擴(kuò)散的條件如下：

如圖1（a）所示，標(biāo)記圖像中像素點(diǎn)O的像素值（32）比其鄰接像素點(diǎn)C的像素值（17）大，而且C在掩膜圖像中位置相對應(yīng)的像素點(diǎn)C1的像素值（45）也比C的數(shù)值大，于是O的像素值在膨脹操作中擴(kuò)散到了它的鄰接像素點(diǎn)C（如圖1（c））。接著，C的像素值又會(huì)通過其鄰接像素點(diǎn)進(jìn)一步地?cái)U(kuò)散。這種像素值的擴(kuò)散會(huì)不斷迭代地進(jìn)行下去，直到標(biāo)記圖像中的像素值不再變化為止。形象地理解形態(tài)學(xué)重建，標(biāo)記圖像中較大的像素值會(huì)像“水”一樣四處擴(kuò)散。如果沒有掩膜圖像，那么當(dāng)形態(tài)學(xué)重建結(jié)束時(shí)標(biāo)記圖像里所有的像素值都會(huì)變成標(biāo)記圖像中某個(gè)最大的像素值，而掩膜圖像就像“高山”一樣阻擋了標(biāo)記圖像中像素值任意的傳播，使得像素值擴(kuò)散只在若干個(gè)隔絕的區(qū)域中發(fā)生。由于標(biāo)記圖像，掩膜圖像的超高分辨率（有些圖像分辨率可以達(dá)到51200×51200，102400×102400），并且隨著傳感器技術(shù)和掃描設(shè)備的提高，圖像的分辨率會(huì)越來越高，形態(tài)學(xué)重建是一個(gè)計(jì)算量很大的問題?？紤]到形態(tài)學(xué)重建里像素值擴(kuò)散的迭代特性，傳統(tǒng)的算法使用了隊(duì)列來跟蹤像素點(diǎn)的擴(kuò)散過程，然而隊(duì)列是按照像素值的擴(kuò)散順序而不是像素值的大小來決定下一次迭代中像素值擴(kuò)散的先后順序，使用隊(duì)列會(huì)導(dǎo)致頻繁出現(xiàn)對于同一個(gè)像素點(diǎn)的多次像素值擴(kuò)散。形態(tài)學(xué)重建的計(jì)算量會(huì)因此大幅度提高。這個(gè)問題促使了在形態(tài)學(xué)重建中使用以像素值大小為優(yōu)先級(jí)的優(yōu)先隊(duì)列，由優(yōu)先隊(duì)列先選出具有較大像素值的像素點(diǎn)讓其像素值先擴(kuò)散以避免較小像素值的擴(kuò)散，從而可以大幅度減少形態(tài)學(xué)重建的計(jì)算量。

現(xiàn)代的NVIDIA圖形處理器（Graphics Processing Unit， GPU）是一個(gè)可編程的基于眾核架構(gòu)的處理器。每一個(gè)圖形處理器包含若干個(gè)流處理器（Streaming Multiprocessors）。每個(gè)流處理器上有32個(gè)或者更多的計(jì)算單元以及存取速度很快但數(shù)量有限的寄存器和共享內(nèi)存（Shared Memory）。同時(shí)，每個(gè)圖形處理器上還配有所有流處理器都可以訪問的全局內(nèi)存（Global Memory）。運(yùn)行在圖形處理器上的CUDA（Compute Unified Device Architecture）程序可以啟動(dòng)成百上千線程同時(shí)執(zhí)行任務(wù)。這些線程是以線程組的形式組織起來的，每個(gè)線程組會(huì)由圖形處理器的硬件調(diào)度系統(tǒng)分配到最空閑的流處理器上執(zhí)行。圖形處理器強(qiáng)大的計(jì)算能力使得很多傳統(tǒng)問題的計(jì)算時(shí)間縮短了十幾倍甚至是幾十倍至原來的十幾分之一甚至幾十分之一此處表述不當(dāng)，應(yīng)該為縮短至原來的十幾分之一甚至幾十分之一。形態(tài)學(xué)重建問題涉及的是高像素圖像以及由此產(chǎn)生的很多的細(xì)粒度任務(wù)，它非常適合使用圖形處理器來加速其計(jì)算過程，而如何設(shè)計(jì)基于圖形處理器并且適合形態(tài)學(xué)重建的并行優(yōu)先隊(duì)列決定了能否高效地把形態(tài)學(xué)重建以及別的類似應(yīng)用移植到圖形處理器上進(jìn)行加速處理。

1 相關(guān)工作

1.1 形態(tài)學(xué)重建

文獻(xiàn)[1]詳細(xì)描述了傳統(tǒng)上形態(tài)學(xué)重建的幾種算法，本文簡單地介紹三種。

第一種算法稱為順序重建法（Sequential Reconstruction），這種算法依賴不斷地正向掃描和反向掃描標(biāo)記圖像，直到在一輪掃描以后再也找不到符合擴(kuò)散條件的像素點(diǎn)為止。正向掃描指的是從圖像中最左上的像素點(diǎn)開始，到最右下的像素點(diǎn)為止，以從上到下、從左到右的順序掃描圖像中的每一個(gè)像素點(diǎn)，而反向掃描恰恰和正向掃描相反，它是從圖像中最右下的像素點(diǎn)開始，到最左上的像素點(diǎn)為止，以從下到上、從右到左的順序掃描圖像中的每一個(gè)像素點(diǎn)。在掃描過程中，一旦發(fā)現(xiàn)某個(gè)像素點(diǎn)符合擴(kuò)散的條件，就會(huì)立即執(zhí)行像素值擴(kuò)散操作，將其像素值賦給鄰接像素點(diǎn)。

第二種算法稱為快速混合重建法（Fast Hybrid Reconstruction）。這種算法首先會(huì)運(yùn)行一次正向掃描和一次反向掃描，對標(biāo)記圖像執(zhí)行初步的膨脹操作，并把有擴(kuò)散可能的像素點(diǎn)收集起來放進(jìn)一個(gè)先進(jìn)先出隊(duì)列中，然后，對于隊(duì)列里的像素點(diǎn)，快速混合重建法會(huì)逐個(gè)取出來，嘗試把像素點(diǎn)上的像素值向其鄰接像素點(diǎn)擴(kuò)散，并且把被擴(kuò)散的鄰接像素點(diǎn)添加到隊(duì)列里。上述操作會(huì)持續(xù)進(jìn)行下去，直到隊(duì)列為空為止。對比順序重建法，快速混合重建法更加有效率，因?yàn)樗恍枰幚碛袛U(kuò)散可能的像素點(diǎn)，而不需要像順序重建法一樣反復(fù)進(jìn)行全局的掃描，但是快速混合重建法也有可以提高的地方，例如其中很多像素值的擴(kuò)散操作是對同一個(gè)像素點(diǎn)執(zhí)行的，因而是重復(fù)的計(jì)算。

第三種算法稱為下坡過濾器（Downhill Filter）[2]，與第二種算法不一樣的是，它使用了一個(gè)隊(duì)列，把有擴(kuò)散可能的像素點(diǎn)按像素值大小進(jìn)行排序，先處理像素值較大的像素點(diǎn)，避免了像素值較小的像素點(diǎn)的擴(kuò)散，從而減少了整個(gè)形態(tài)學(xué)重建的計(jì)算量。

1.2 基于圖形處理器的并行數(shù)據(jù)結(jié)構(gòu)

基于中央處理器的數(shù)據(jù)結(jié)構(gòu)已經(jīng)被研究了很多年，但是基于圖形處理器的并行數(shù)據(jù)結(jié)構(gòu)研究還是非常有限?？紤]到本文涉及了圖形處理器上并行數(shù)據(jù)結(jié)構(gòu)，首先對這個(gè)領(lǐng)域作一個(gè)簡述。

當(dāng)圖形處理器開始應(yīng)用于解決一般問題時(shí)，研究人員嘗試把各種傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)變成適合眾核架構(gòu)的并行數(shù)據(jù)結(jié)構(gòu)。文獻(xiàn)[3]按照廣度優(yōu)先的順序構(gòu)造KD（請補(bǔ)充KD的英文全稱?；貜?fù)：這個(gè)從原來的英文名字翻譯過來的。原來的名字叫kd-trees或者k-d tree. 國內(nèi)的文獻(xiàn)一般叫KD樹或者kd-樹（在中國知網(wǎng)上搜索"KD樹"可以看到相關(guān)文章）. 我覺得就叫KD樹吧。）-樹，并且對大節(jié)點(diǎn)采用了新穎的構(gòu)造算法以充分利用圖形處理器的計(jì)算能力。文獻(xiàn)[4]針對前者在構(gòu)造KD-樹過程中消耗了過多圖形處理器內(nèi)存的問題提出了按照部分廣度優(yōu)先的順序構(gòu)造KD-樹，犧牲一部分并發(fā)性以換取內(nèi)存的大量節(jié)省。文獻(xiàn)[5]中提出了一種在圖形處理器上表面積啟發(fā)式構(gòu)建KD樹的并行方法。其他基于樹的數(shù)據(jù)結(jié)構(gòu)，例如八叉樹（Octree）[6-12]、決策樹[13-14]、層次包圍盒（Bounding Volume Hierarchy）[15]也已經(jīng)在文獻(xiàn)中被討論了如何移植到圖形處理器上。文獻(xiàn)[16]通過把包含指針的操作轉(zhuǎn)化為數(shù)組操作，設(shè)計(jì)出了一種高效率、適合圖形處理器的跳表結(jié)構(gòu)（Skiplist）。在文獻(xiàn)[17]里，研究者們在完美哈希表（Perfect Hash）[18]和布谷鳥哈希表（Cuckoo Hash）[19]的基礎(chǔ)上設(shè)計(jì)出了一個(gè)適合圖形處理器的并行哈希表。文獻(xiàn)[20]中提出了在圖形處理器中實(shí)現(xiàn)布隆過濾器（Bloom Filter）的方案。對于集合，文獻(xiàn)[21]中提出了圖形處理器中新穎的集合數(shù)據(jù)組織方式以及實(shí)現(xiàn)集合相交的算法。在圖方面，文獻(xiàn)[22]使用了多層隊(duì)列的方式在圖形處理器中加速了廣度優(yōu)先圖的遍歷。文獻(xiàn)[23]解決了如何并行計(jì)算最小生成樹的問題。

1.3 并行優(yōu)先隊(duì)列

單線程優(yōu)先隊(duì)列有不同的實(shí)現(xiàn)方式，包括二元堆（Binary Heap）[24]、二項(xiàng)堆（Binomial Heap）[25]、斐波那契堆（Fibonacci Heap）[26]等。一般來說有三種方式來并行化優(yōu)先隊(duì)列。

第一種方式是使用多個(gè)計(jì)算單元來并行化單個(gè)元素的入隊(duì)列或者出隊(duì)列操作[27]，縮短了單個(gè)操作的時(shí)間。

第二種方式是允許優(yōu)先隊(duì)列里同時(shí)有多個(gè)單線程入隊(duì)列和出隊(duì)列操作[28]，減少了單個(gè)操作的平均時(shí)間。

第三種方式則是既允許入隊(duì)列操作和出隊(duì)列操作同時(shí)進(jìn)行，又使用多個(gè)計(jì)算單元來并行化入隊(duì)列和出隊(duì)列操作[29]。

本文的主要工作有兩點(diǎn)：

1）在圖形處理器上設(shè)計(jì)和實(shí)現(xiàn)了并行堆集群。并行堆是并行優(yōu)先隊(duì)列在圖形處理器上的實(shí)現(xiàn)，而并行堆集群則是并行堆的集合，出于性能考慮而設(shè)計(jì)，可以理解為并線優(yōu)先隊(duì)列在圖形處理器上的近似實(shí)現(xiàn)。

2）基于并行堆集群，在圖形處理器上設(shè)計(jì)和實(shí)現(xiàn)了形態(tài)學(xué)重建系統(tǒng)。

2 基于圖形處理器的形態(tài)學(xué)重建系統(tǒng)

2.1 系統(tǒng)概述

為了充分利用圖形處理器的并行計(jì)算能力以縮短形態(tài)學(xué)重建的計(jì)算時(shí)間，本文設(shè)計(jì)開發(fā)了一套基于圖形處理器的形態(tài)學(xué)重建系統(tǒng)，取名為MR_GPU（Morphological Reconstruction_GPU）。MR_GPU設(shè)計(jì)的一個(gè)重要原則是把計(jì)算量大、適合使用并行計(jì)算的操作放在圖形處理器端處理，而中央處理器端則負(fù)責(zé)系統(tǒng)的初始化、輸入輸出以及與圖形處理器的協(xié)調(diào)工作。圖2展示的是MR_GPU的流程。r是并行堆節(jié)點(diǎn)可容納的最大像素點(diǎn)個(gè)數(shù)。系統(tǒng)的輸入是一張標(biāo)記圖像和一張掩膜圖像，輸出是一張膨脹后的標(biāo)記圖像。系統(tǒng)內(nèi)的處理主要分為三個(gè)階段：準(zhǔn)備階段、建堆階段和迭代膨脹階段。在準(zhǔn)備階段，系統(tǒng)會(huì)完成初始化和數(shù)據(jù)準(zhǔn)備的工作。初始化工作主要包括配置系統(tǒng)參數(shù)，初始化系統(tǒng)中引用的各種外部類庫和在中央處理器和圖形處理器兩端計(jì)算并分配存儲(chǔ)空間。數(shù)據(jù)準(zhǔn)備工作則包括：1）從標(biāo)記圖像和掩膜圖像文件里把圖像信息數(shù)據(jù)讀取出來，并存放在二維數(shù)組里;2）對圖像信息進(jìn)行必要的類型轉(zhuǎn)換和數(shù)據(jù)清洗;3）把圖像信息傳輸?shù)綀D像處理器端的全局內(nèi)存;4）掃描圖像信息，找出符合擴(kuò)散條件的種子像素點(diǎn)，并且把這些種子像素點(diǎn)均勻地分組。在建堆階段，上一階段留下的每一個(gè)像素點(diǎn)組，會(huì)被按照像素值進(jìn)行排序以構(gòu)造一個(gè)最大并行堆。在迭代膨脹階段，每一個(gè)最大并行堆都會(huì)獨(dú)立地、迭代地執(zhí)行膨脹操作，其步驟如算法1所示。細(xì)節(jié)會(huì)在介紹并行堆時(shí)一起討論。

2.2 并行堆

并行堆是專門為圖形處理器設(shè)計(jì)的優(yōu)先隊(duì)列，可以看成是二元堆的升級(jí)版本。與二元堆類似，并行堆實(shí)際上是一棵完全二叉樹，并且同樣維護(hù)堆的屬性，即每個(gè)節(jié)點(diǎn)里元素的值都比孩子節(jié)點(diǎn)元素的值要大（最大堆）或者小（最小堆）。在本文中，所討論的并行堆都為最大堆。與二元堆不同的是，并行堆里的節(jié)點(diǎn)可以包含多個(gè)元素。實(shí)際上，在本文的形態(tài)學(xué)重建系統(tǒng)里，并行堆節(jié)點(diǎn)的元素?cái)?shù)是幾十甚至上百，這樣可以方便分配多個(gè)線程同時(shí)對并行堆進(jìn)行操作，也符合圖形處理器中通過多線程調(diào)度來解決內(nèi)存存取延遲問題的硬件特性。

與二元堆類似，并行堆也有入堆和出堆操作。出堆操作從緩沖區(qū)內(nèi)取回r個(gè)元素并放到根節(jié)點(diǎn)上，然后執(zhí)行出堆調(diào)整操作，使并行堆保持堆的屬性。具體的調(diào)整方案是把根節(jié)點(diǎn)上的r個(gè)元素和它的兩個(gè)孩子節(jié)點(diǎn)n1、n2內(nèi)的2r元素合并。假設(shè)n1里的最小元素比n2里的最小元素要小，那么合并后最大的r個(gè)元素存放在根節(jié)點(diǎn)，最小的r個(gè)元素放在n2節(jié)點(diǎn)，其余的r個(gè)元素放在n1節(jié)點(diǎn)。可以證明只有n2節(jié)點(diǎn)及它的子節(jié)點(diǎn)需要繼續(xù)調(diào)整[28]。出堆調(diào)整操作會(huì)繼續(xù)迭代地調(diào)整n2節(jié)點(diǎn)及其子節(jié)點(diǎn)，直到到達(dá)了葉子節(jié)點(diǎn)。

入堆操作是要把新的r元素添加到并行堆現(xiàn)有元素之后，并且調(diào)整并行堆使其保持堆的屬性。具體的調(diào)整方案如下：計(jì)算一條從根節(jié)點(diǎn)到待插入節(jié)點(diǎn)之間由上往下的入堆路線。從根節(jié)點(diǎn)開始，新的r個(gè)元素與根節(jié)點(diǎn)的r個(gè)元素合并。較大的r個(gè)元素留在根節(jié)點(diǎn)，較小的r個(gè)元素繼續(xù)流向入堆路線上的下一個(gè)節(jié)點(diǎn)里，然后在下一個(gè)節(jié)點(diǎn)上繼續(xù)合并，保留較大的r個(gè)元素，讓較小的r個(gè)元素繼續(xù)流向再下一個(gè)節(jié)點(diǎn)。上述步驟持續(xù)進(jìn)行，直到較小的元素到達(dá)待插入節(jié)點(diǎn)。

傳統(tǒng)的二元堆入堆調(diào)整由下往上進(jìn)行，而出堆調(diào)整是由上往下進(jìn)行的。由于在多線程環(huán)境下會(huì)存在多個(gè)出堆調(diào)整和入堆調(diào)整線程，這種出堆、入堆調(diào)整方向不一致的情況會(huì)導(dǎo)致死鎖問題的出現(xiàn)。實(shí)際上，并行堆根據(jù)圖形處理器同步的特點(diǎn)，采用了流水線（Pipeline）的并行策略，堆中每一個(gè)層次同時(shí)都有一組入堆調(diào)整線程和一組出堆調(diào)整線程在運(yùn)行，因此，在并行堆中，把出堆、入堆調(diào)整的方向都設(shè)計(jì)為由上到下以避免死鎖的出現(xiàn)。

在形態(tài)學(xué)重建系統(tǒng)里需要一個(gè)緩沖區(qū)，緩沖區(qū)內(nèi)存放的是最近產(chǎn)生的待擴(kuò)散的像素點(diǎn)。每次迭代中，并行堆根節(jié)點(diǎn)的像素點(diǎn)會(huì)被取出來，與緩沖區(qū)內(nèi)的像素點(diǎn)合并成有序序列，然后最大的r個(gè)像素點(diǎn)會(huì)被取出進(jìn)行擴(kuò)散處理，次大的r個(gè)像素點(diǎn)會(huì)被放在并行堆的根節(jié)點(diǎn)，然后進(jìn)行由上到下的出堆調(diào)整操作。另外的r像素點(diǎn)則會(huì)沿著計(jì)算好的路徑由上而下，最終把經(jīng)過調(diào)整后較小的像素點(diǎn)添加到并行堆的待插入節(jié)點(diǎn)中。

圖3（a）顯示的是一個(gè)簡化版本的并行堆例子。它共有11個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有一個(gè)編號(hào)，最多可以包含2個(gè)像素點(diǎn)，緩沖區(qū)內(nèi)有上次迭代收集的4個(gè)像素點(diǎn)（62，45，38，35）。在當(dāng)前迭代中，出堆操作會(huì)從并行堆取出根節(jié)點(diǎn)內(nèi)的像素點(diǎn)（57，59）放到緩沖區(qū)內(nèi)，然后對緩沖區(qū)內(nèi)的像素點(diǎn)的值進(jìn)行排序，然后，如圖3（b）所示，對于像素值最大的2個(gè)像素點(diǎn)（62，59），系統(tǒng)會(huì)對它們進(jìn)行擴(kuò)散處理，并把擴(kuò)散所涉及的鄰接像素點(diǎn)收集到緩沖區(qū)為下一輪迭代做準(zhǔn)備。對于緩沖區(qū)像素值排第3第4的像素點(diǎn)（57，45），系統(tǒng)會(huì)把它們放回到并行堆的根節(jié)點(diǎn)，然后從根節(jié)點(diǎn)開始對并行堆進(jìn)行出堆調(diào)整。至于剩下的像素點(diǎn)（38，35），則會(huì)執(zhí)行入堆操作。調(diào)整后具有較小像素值的兩個(gè)像素點(diǎn)（35，38）將會(huì)被放到節(jié)點(diǎn)12上去。因?yàn)榇迦牍?jié)點(diǎn)已知，系統(tǒng)由此可以計(jì)算入堆路線，并由上往下進(jìn)行入調(diào)整。圖3（c）顯示是入堆、出堆調(diào)整后的并行堆。

2.3 并行策略

行之有效的并行策略是MR_GPU中重要的一環(huán)。在準(zhǔn)備階段，分配了數(shù)量眾多的線程來并行掃描標(biāo)記圖像和掩膜圖像。由于圖形處理器獨(dú)特的硬件線程調(diào)度實(shí)現(xiàn)，數(shù)量眾多的線程不但不會(huì)因?yàn)榫€程調(diào)度而影響性能，反而可以隱藏讀寫內(nèi)存帶來的延遲從而提高整體的性能。在建堆階段和迭代膨脹階段，適用的并行策略可以分為三個(gè)層次。

并行策略的第一層次是在圖形處理器集群上。圖形處理器集群上部署了多個(gè)圖形處理器，可以切割大圖像文件并分配到每個(gè)圖形處理器上，由這些圖形處理器獨(dú)立地、并行地進(jìn)行形態(tài)學(xué)重建。同時(shí)，圖形處理器間有同步策略，可以在不同圖像文件分割塊間進(jìn)行同步。

并行策略第二層次是在每個(gè)圖形處理器上運(yùn)行的并行堆集群上，可以配置多個(gè)并行堆同時(shí)執(zhí)行形態(tài)學(xué)重建中的膨脹操作。在最開始的設(shè)計(jì)中只維護(hù)了一個(gè)并行堆。一個(gè)并行堆可以保證具有較大像素值的像素點(diǎn)首先可以得到擴(kuò)散的機(jī)會(huì)，從而避免很多較小像素值不必要的擴(kuò)散，但是問題在于如果一個(gè)圖形處理器中只維護(hù)一個(gè)并行堆的話，圖形處理器的計(jì)算能力遠(yuǎn)遠(yuǎn)得不到充分的利用，整個(gè)形態(tài)學(xué)重建的效率并沒有得到最大化。現(xiàn)在MR_GPU中設(shè)計(jì)的并行堆集群中各個(gè)并行堆是相互獨(dú)立的，保證了效率不會(huì)因?yàn)椴⑿卸阎g的相互依賴關(guān)系而下降。每個(gè)并行堆內(nèi)部也是保證具有較大像素值的像素點(diǎn)首先可以得到擴(kuò)散的機(jī)會(huì)從而減少了不必要的計(jì)算，而并行堆之間由于是相互獨(dú)立，沒有同步的機(jī)制，會(huì)導(dǎo)致一些重復(fù)的像素值擴(kuò)散操作。然而，相對于采用并行堆集群而獲取的圖形處理器計(jì)算能力的充分利用，這些重復(fù)計(jì)算的代價(jià)是可以承受的。

并行策略的第三層次是在并行堆內(nèi)部。在建堆階段，需要對初始化階段找出的首先擴(kuò)散的像素點(diǎn)進(jìn)行并行排序從而構(gòu)造并行堆。在圖形處理器上并行排序是一個(gè)已經(jīng)有很多研究者在研究的課題[30-33]?？梢灾苯硬捎靡呀?jīng)優(yōu)化的并行排序方案。在迭代膨脹階段，采用了流水線（pipeline）的并行機(jī)制，出堆和入堆調(diào)整線程從根節(jié)點(diǎn)開始，一層一層往下對并行堆進(jìn)行調(diào)整。當(dāng)一組出堆調(diào)整和一組入堆調(diào)整線程完成了對根節(jié)點(diǎn)的調(diào)整，開始對并行堆的第二層進(jìn)行調(diào)整時(shí)，系統(tǒng)會(huì)啟動(dòng)另外一組出堆調(diào)整和一組入堆調(diào)整線程執(zhí)行下一輪出堆入堆操作。一般來說，對于一個(gè)有n層的并行堆，會(huì)有n組出堆調(diào)整線程和n組入堆調(diào)整線程。每一個(gè)出堆或入堆調(diào)整線程組內(nèi)會(huì)有r個(gè)線程，r是并行堆節(jié)點(diǎn)里最大的元素?cái)?shù)，而為節(jié)點(diǎn)里每一個(gè)元素分配一個(gè)線程無論從實(shí)現(xiàn)角度還是效率角度來看都是不錯(cuò)的選擇。出堆和入堆調(diào)整線程還涉及了并行合并操作和并行收集像素點(diǎn)操作，對于前者，別的研究已經(jīng)提供了解決方案[30，34]。對于并行收集像素點(diǎn)到緩沖區(qū)問題，本文的策略是為每個(gè)產(chǎn)生待擴(kuò)散的像素點(diǎn)的線程分配臨時(shí)空間存放待擴(kuò)散像素點(diǎn)，然后統(tǒng)計(jì)像素點(diǎn)的個(gè)數(shù)。線程同步以后使用并行掃描的方式統(tǒng)計(jì)像素點(diǎn)總的個(gè)數(shù)以確定每個(gè)線程產(chǎn)生的像素點(diǎn)在緩沖區(qū)內(nèi)的位置，然后讓每個(gè)線程分別把各自的像素點(diǎn)從臨時(shí)空間拷貝到緩沖區(qū)內(nèi)。