本文關(guān)鍵詞：細胞自動機，由筆耕文化傳播整理發(fā)布。

 

一、概述

（一）         細胞自動機的應(yīng)用實例

長久以來，人們一直希望使用計算機模擬現(xiàn)實世界的各種問題，細胞自動機理論的出現(xiàn)為這一理想提供了有力的實現(xiàn)工具。

劍橋的數(shù)學(xué)家John Horton Conway設(shè)計了一種著名的細胞自動機--“生命游戲”，提出用二維的胞元數(shù)組模擬問題空間，每一個數(shù)組元素中可能存在一個生命體，與它相臨的數(shù)組元素表示它的鄰居，生命體根據(jù)一定的規(guī)則和相鄰元素改變自己的生存狀態(tài)。眾多的細胞自動機問題都可以根據(jù)類似的方式進行設(shè)計和實現(xiàn)。其中，Shark & Fish模型就是一個模擬海洋生態(tài)系統(tǒng)的簡單應(yīng)用，本文的目的就是使用并行算法將其實現(xiàn)。

在Shark & Fish模型中，海洋里只存在鯊魚和小魚，分別在各自的壽命內(nèi)于海域里移動，達到生育年齡后產(chǎn)下后代。鯊魚是以小魚為食物的捕食者，在連續(xù)一段時間沒有進餐后，鯊魚由于饑餓而死。通過并行算法對這個有限的海域的模擬，可以更好地理解細胞自動機和并行計算理論的應(yīng)用。

（二）         應(yīng)用實例解決方案

 應(yīng)用串行和并行的方式分別實現(xiàn)細胞自動機，它們之間有區(qū)別又有眾多的聯(lián)系。本文在分析了細胞自動機的特性以及需解決的基本內(nèi)容之后，首先分析串行的解決策略，主要集中在隨機選擇序列的產(chǎn)生算法，挑選出隨機位置的細胞后進行各類型自身擁有的捕食、移動等動作。隨后，將串行的算法改寫成并行方法，要解決例如任務(wù)分配、沖突解決等問題。本文對比了消息處理和簡單統(tǒng)一這兩種完全不同的沖突處理方式，分析它們各自的優(yōu)勢和劣勢。并行化處理的根本目的是提高運算速度，因此在講述如何實現(xiàn)幾種并行策略后，結(jié)合試驗和算法對比了各方法的執(zhí)行效率，分析其中的原因和改進的方法。

（三）結(jié)論

    細胞自動機問題本身具有明顯的并行性，使用編制合理的并行算法不但能夠提高程序的執(zhí)行效率，還能跟好地體現(xiàn)出問題內(nèi)在并行的本質(zhì)特點。本文使用的算法中，任務(wù)分配算法雖然簡單易于實現(xiàn)，但是沒有能動態(tài)地平衡各個處理機之間的負載；所使用的處理沖突的算法致力于盡量真實地模擬自動機的隨機特性，在運行效率上并不能令人滿意，所以隨后又使用簡單統(tǒng)一公共數(shù)據(jù)的方法，更多的側(cè)重于運算效能的提高，在可容忍的限度內(nèi)犧牲了一些邊界地區(qū)計算的準確性。對于以上方案，有很多地方可以做出效能和處理結(jié)果上面的改進，使得整體效果得到提升。

二、理論基礎(chǔ)與應(yīng)用

（一）并行計算理論與應(yīng)用

在并行計算理論出現(xiàn)之前，傳統(tǒng)的程序運算在單處理機的環(huán)境下執(zhí)行，由于物理條件的限制，某些運算量巨大、要求快速計算的應(yīng)用問題不能得到滿足。然而單處理機的性能提升難度和成本都相對較高，因此將多個處理機聯(lián)合，并行的解決方案能夠滿足這些高性能的需求。除了提高了運算速度，也使很多要求高精度計算的問題能夠在合理的時間內(nèi)得以解決。此外，有很多問題由于自身的特點，特別適用于并行方法進行求解。模擬實驗常常屬于這種類別，更多地集中在應(yīng)用領(lǐng)域并行算法的研究上，包括計算生物學(xué)、計算化學(xué)、計算流體動力學(xué)、飛行動力學(xué)、計算機輔助設(shè)計、數(shù)據(jù)庫管理、油藏建模、中長期天氣預(yù)報、海洋環(huán)流和求解N-body 問題等。例如本文實現(xiàn)的細胞自動機的問題本身就具有并行性。

在并行環(huán)境下解決應(yīng)用問題，就需要編制并行算法。并行算法就是用多臺處理機聯(lián)合求解問題的方法和步驟，其執(zhí)行過程是將給定的問題首先分解成若干個盡量相互獨立的子問題，然后使用多臺計算機同時求解它，從而最終求得原問題的解[1]。使用某種程序語言實現(xiàn)這種算法就稱為并行程序設(shè)計。

    目前，有多種并行程序設(shè)計方法在不同領(lǐng)域得以應(yīng)用，其中消息傳遞接口MPI漸漸成為主流的編程方案。這種方法對原有的高級程序設(shè)計語言進行擴展，使它能夠進行消息庫的調(diào)用，完成進程之間的直接消息傳遞。使用MPI進行編程時，必須顯式地說明要執(zhí)行那些進程，何時在那些并行進程間傳遞何種消息。

     本文在Microsoft Visual C++.NET 2005編程平臺調(diào)用消息傳遞接口MPI模擬細胞自動機的并行算法。

（二）細胞自動機理論與應(yīng)用

自動機(Automaton)在1984年的《英漢計算機詞典》[2]中被譯為：指不需要人們逐步進行操作指導(dǎo)的設(shè)備。它的起源要追溯到1936年，Turing提出的圖靈機，它是由一個有限控制器、一條無限長存儲帶和一個讀寫頭構(gòu)成的抽象的機器，根據(jù)不同的狀態(tài)信息和當前輸入按照預(yù)定的規(guī)則進行狀態(tài)的轉(zhuǎn)換。對于自動機的進一步發(fā)展和應(yīng)用就不能不提到應(yīng)用廣泛的細胞自動機。

細胞自動機（Cellular Automata）最初由數(shù)學(xué)家 Stanislaw M.Ulam（1909-1984）與 John von Neumann（1903-1957）于 1950年代所提出，在型態(tài)表現(xiàn)上，細胞自動機是一個離散型的動力系統(tǒng)（Discrete Dynamical Systems）。美國數(shù)學(xué)家L.P.Hurd和K·Culik等人在90年代初，對細胞自動機分別從集合論和拓撲學(xué)等角度進行了嚴格地描述和定義。1970 年，John Conway 依據(jù)Von Neumann的想法進一步發(fā)展成電腦上的生命游戲（Game of Life），從此CA 的概念逐漸普及到相關(guān)領(lǐng)域。

細胞自動機最基本的組成細胞、細胞空間、鄰居及規(guī)則四部分。簡單講，細胞自動機可以視為由一個細胞空間和定義于該空間的變換函數(shù)所組成。細胞自動機作為一種動態(tài)模型，更多的是作為一種通用性建模的方法，其應(yīng)用幾乎涉及社會和自然科學(xué)的各個領(lǐng)域。自它產(chǎn)生以來，被廣泛地應(yīng)用到社會、經(jīng)濟、軍事和科學(xué)研究的各個領(lǐng)域。應(yīng)用領(lǐng)域涉及社會學(xué)、生物學(xué)、生態(tài)學(xué)、信息科學(xué)、計算機科學(xué)、數(shù)學(xué)、物理學(xué)、化學(xué)、地理、軍事學(xué)等。在社會學(xué)中，細胞自動機用于研究經(jīng)濟危機的形成與爆發(fā)過程、個人行為的社會性，流行現(xiàn)象，如服裝流行色的形成等。在生物學(xué)中，細胞自動機的設(shè)計思想本身就來源于生物學(xué)自繁殖的思想，因而它在生物學(xué)上的應(yīng)用更為自然而廣泛。例如細胞自動機朋于腫瘤細胞的增長機理和過程模擬、人類大腦的機理探索(Victor.Jonathan.D.，1990)、艾滋病病毒HIV的感染過程(Sieburg，H.B.. 1990)、自組織、自繁殖等生命現(xiàn)象的研究以及最新流行的克隆 (Clone)技術(shù)的研究等 (Ermentrout.G.B，1993)。在信息學(xué)中。細胞自動機冉于研究信息的保存、傳遞、擴散的過程。另外。Deutsch(1972)、Sternberg(1980)和Rosenfeld(1979)等人還將二維細胞自動機應(yīng)用到圖像處理和模式識別中(WoIfram.S.，1983) 。在生態(tài)學(xué)中。細胞自動機用于兔子-草，鯊魚-小魚等生態(tài)動態(tài)變化過程的模擬，展示出令人滿意的動態(tài)效果;細胞自動機還成功地應(yīng)用于螞蟻、大雁、魚類洄游等動物的群體行為的模擬;另外，基于細胞自動機模型的生物群落的擴散模擬也是當前的一個應(yīng)用熱點。在計算機科學(xué)中，細胞自動機可以被看作是并行計算機而用于并行計算的研究(Wolfram.S.1983)。

本文的內(nèi)容正是利用計算機并行技術(shù)實現(xiàn)對鯊魚-小魚的生態(tài)模型的模擬，下面將詳細介紹細胞自動機問題并行處理的理論基礎(chǔ)。

（三）并行實現(xiàn)細胞自動機的理論基礎(chǔ)

細胞自動機在模擬生物動態(tài)變化的應(yīng)用問題時必須相互等待實現(xiàn)同步，才能繼續(xù)獨立的計算，被稱為全同步應(yīng)用。各個細胞在每次迭代開始時同步啟動，直到所有細胞都結(jié)束前一次迭代后才開始下一次迭代，稱為同步迭代。

細胞自動機的問題空間首先被劃分為眾多的方格，被稱為胞元。每個胞元處于預(yù)先設(shè)定的有限狀態(tài)中的一個。根據(jù)某種規(guī)則，胞元受到鄰居狀態(tài)的影響，屬于同一代的所有胞元同時受到影響，相應(yīng)地改變自己的狀態(tài)。這些規(guī)則被重復(fù)地應(yīng)用于每一代的胞元。

    在并行程序設(shè)計中，問題空間根據(jù)某種方式（靜態(tài)或動態(tài)）被劃分區(qū)域，分配給各個進程進行迭代計算，用來模擬細胞在每一代中的狀態(tài)改變，進程間同步實現(xiàn)各代的更迭。

三、問題分析和解決方案

（一）問題分析

    在程序?qū)崿F(xiàn)Shark & Fish模型前，應(yīng)該對其中涉及到的各方面問題作詳細的分析，才能對整體架構(gòu)和具體細節(jié)都有一個清晰的理解和認識，有助于理清頭緒，使得后面的算法設(shè)計條理清楚，目的明確。

（1）數(shù)據(jù)結(jié)構(gòu)

    Shark & Fish模型有鯊魚、小魚和空白區(qū)域三種不同類型的胞元。鯊魚類型具有類型標識、年齡和饑餓時間三個屬性；小魚類型具有類型標識和年齡兩個屬性；空白區(qū)域類型具有類型標識一個屬性。根據(jù)三種胞元類型的特點，可以將其統(tǒng)一為胞元類或胞元結(jié)構(gòu)體。由于整體海域由以上三種胞元組成，可以定義為胞元類型的二維數(shù)組，通過對其中胞元屬性的賦值和更新實現(xiàn)對這個小海洋生態(tài)的模擬。對于胞元的鄰居定義為上下左右四個方向的數(shù)組元素或者包括對角線方向的八個方向的數(shù)組元素。

（2）細胞行為

    Shark & Fish模型每個細胞都有各自的相應(yīng)的行動規(guī)則，根據(jù)相鄰細胞的狀態(tài)并遵循這些規(guī)則改變自己的狀態(tài)。

    （a）捕食：捕食是鯊魚特有的行為，當鯊魚的相鄰胞元是一條小魚時，鯊魚將它吃掉，如果相鄰的小魚多于一條時，鯊魚隨機從其中選擇一條捕食。

    （b）饑餓：饑餓是鯊魚特有的行為，當鯊魚相鄰的區(qū)域都是空白區(qū)域時，鯊魚沒有食物可以選擇，鯊魚將會饑餓一次，鯊魚胞元的饑餓時間屬性增加一個時間單位。

    （c）移動：移動是鯊魚和小魚共有的行為，但它們之間也有一些區(qū)別，各自在不同的情況下進行移動。當小魚周圍有空白的相鄰區(qū)域時，小魚從中隨機選擇一個方向移動；當鯊魚周圍沒有可以捕食的小魚，鯊魚饑餓的同時，如果鯊魚周圍有空白的相鄰區(qū)域，則從空白區(qū)域中隨機選擇一個方向進行移動。

    （d）餓死：餓死是鯊魚特有的行為，鯊魚有一個固有的饑餓忍耐時間，當鯊魚連續(xù)沒有吃到小魚的時間超過它的饑餓極限時，鯊魚就被餓死，將所在空間設(shè)置為空白。

    （e）擁擠致死：擁擠致死是鯊魚和小魚共有的行為，如果鯊魚和小魚被同類所包圍，沒有可以捕食的食物或移動的空間，鯊魚和小魚由于同類密度太大擁擠致死，將所在空間設(shè)置為空白區(qū)域。

    （f）繁殖：繁殖是鯊魚和小魚共有的行為，它們各自有一個固有的繁殖年齡周期，當鯊魚和小魚在可移動的情況下，達到了繁殖周期，則會在原地產(chǎn)下一條同類幼體，同時自己隨機移動到相鄰的空白區(qū)域。

    （g）年齡增長：年齡增長是鯊魚和小魚的共有行為，當它們沒有因為饑餓、擁擠或衰老致死的情況下便將細胞的年齡增加一個時間單位。

    （h）衰老致死：衰老致死是鯊魚和小魚共有的行為，它們各自都有一個固有的生命極限，當鯊魚和小魚的年齡達到這個時間后便衰老致死，將所在空間設(shè)置為空白。

（3）區(qū)域內(nèi)細胞隨機序列行動

    在海洋區(qū)域內(nèi)進行同一代的細胞行為計算時，對細胞的操作有一定的先后順序，不同的順序可能生成不同的計算結(jié)果，以為較早改變的細胞應(yīng)用了舊的鄰居信息生成自己新的細胞狀態(tài)，它的改變會影響暫時還未改變狀態(tài)的鄰居細胞執(zhí)行后面的操作。

圖示 1

    如圖示1 所示情況，左側(cè)的鯊魚首先吃掉了位于中間的小魚，它的行動將影響下面的鯊魚未來的選擇，它需要根據(jù)改變后的情況選擇其他小魚進行捕食或移動到空白區(qū)域。因此需要對海域內(nèi)的生物進行隨機順序的選擇操作，避免固定操作順序會造成連續(xù)的影響，從而盡量模擬現(xiàn)實情況中事件發(fā)生的隨機性。

（4）無限區(qū)域的有限表示

     在有限區(qū)域內(nèi)對生物海域進行模擬就要考慮當鯊魚或小魚游弋到區(qū)域的最外層邊界時的處理，不但這些胞元的狀態(tài)取決于鄰居胞元的信息，它們下一個所處的位置也可能超出了預(yù)先設(shè)定的范圍，需做特殊處理。

    （a）邊界反射法：這種處理方法使得生物運動出邊界后，像鏡子對光線的反射一樣，細胞將向初始運動的反方向活動。

    （b）邊界循環(huán)法：循環(huán)法將整個區(qū)域看成是上下、左右邊界相連的球狀區(qū)域，當細胞從一邊出界后，將出現(xiàn)在相對應(yīng)的另一側(cè)邊界處。如圖示2所示，圓圈內(nèi)的鯊魚向左移動出邊界，它將出現(xiàn)在同行的右側(cè)列邊界中。本文所使用的就是這種方法來實現(xiàn)環(huán)形海域的模擬。

圖示 2

   

通過以上幾種方法，就可以用有限區(qū)域模擬生物在無限環(huán)境下的活動狀態(tài)。

 

 

（5）并行化處理

     將串行算法改寫為并行算法需要了解并行環(huán)境進程的操作特點，分析可能出現(xiàn)的新問題，提出有效的解決辦法。下面就針對并行解決方案中進程間相互協(xié)同操作的幾個突出的問題作簡要地分析。

    （a）任務(wù)分配：要將現(xiàn)有問題并行化處理就要將整體的操作區(qū)域按照一定的策略進行劃分，分別交由相應(yīng)的子進程處理。任務(wù)的分配一般分為靜態(tài)分配和動態(tài)分配。靜態(tài)分配就是在運行解決方案之前確定每個處理機獲得的任務(wù)量；與此相對應(yīng)的是動態(tài)分配，這種方法可以實時地根據(jù)處理機實際處理能力和具體條件動態(tài)地調(diào)整任務(wù)量。顯然動態(tài)分配對于細胞自動機這樣的同步計算問題顯得尤為重要，根據(jù)木桶原理，每一次迭代的執(zhí)行時間是由執(zhí)行最慢的進程所決定的。因此將任務(wù)合理地分配給各個進程，盡量使所有工作進程在同一時間結(jié)束處理，減少等待時間的處理機效能浪費，能夠有效地提高并行程序的執(zhí)行效率。

（b）同步計算：子進程的處理必須保持同步性，即在所有子進程完成這一代的計算之前，任何進程不能進行下一代的處理。工作進程完成自己的處理任務(wù)之后，如果沒有和兄弟進程進行信息交換，它就由于沒有獲得完整的數(shù)據(jù)而不能提前開始下一代的計算。

圖示 3

（c）邊界沖突：在任務(wù)分配給各個公共進程之后，進程要完成自己區(qū)域內(nèi)的計算，必須獲得相鄰進程的部分數(shù)據(jù)，提供給所獲區(qū)域最外側(cè)胞元的鄰居節(jié)點信息。然而工作進程之間的計算是獨立的，進程內(nèi)部的處理又是隨機的，因此它們對這些公共數(shù)據(jù)的處理結(jié)果可能是各不相同的，這就產(chǎn)生了邊界沖突。例如圖示3，灰色區(qū)域表示的是上下兩個進程數(shù)據(jù)的邊界，可以看到兩條鯊魚都會選擇捕食圓圈中的這條魚，由于邊界兩邊的數(shù)據(jù)被分別處理，所以會在相互統(tǒng)一信息時產(chǎn)生沖突。這些數(shù)據(jù)關(guān)系到各代數(shù)據(jù)的一致性，如何預(yù)防數(shù)據(jù)沖突的或者在沖突發(fā)生之后有效的解決沖突影響著計算的正確性；同時由于進程間通訊耗費的時間遠遠多于計算相同數(shù)據(jù)，因此處理沖突的策略也可能極大地影響并行算法的時間復(fù)雜度。因此，設(shè)計一種能夠確實反映自動機的隨機特性又不明顯降低通訊效率的策略就成為并行實現(xiàn)細胞自動機的關(guān)鍵所在。

 

（二）串行解決方案

（1）程序整體框架

在單進程環(huán)境下，處理過程相對并行比較簡單清晰，主要有定義并初始化海域內(nèi)生物最初狀態(tài)、生成隨機選擇策略、對所選細胞單元進行處理、完成迭代等幾個部分組成。程序整體框架如圖示4所描述。

（2）主要方法實現(xiàn)與分析

    （a）細胞隨機選擇序列：由于海域由二維胞元數(shù)組表示，每一代的細胞保存其中。隨即序列生成函數(shù)建立鯊魚和小魚兩條隊列的頭指針，函數(shù)按行掃描胞元數(shù)組，生成一個在隊列長度的范圍內(nèi)的隨機數(shù)，表示隨機插入隊列的位置，將掃描到的細胞指針插入所屬類型的隊列中。當處理海域內(nèi)的細胞時，每次從隊列中提取隊列頭部的細胞進行處理，所處理的細胞將就是按照隨機位置出現(xiàn)的。由于鯊魚處于食物鏈中的強勢地位，因此首先處理鯊魚隊列。如圖示5所示，建立鯊魚隨機細胞的隊列，掃描海域，分別將其中的鯊魚插入到隊列4、1、2、6、3、5位置。

圖示4

圖示 5

（b）細胞行為：無論細胞是鯊魚還是小魚，無論是進行捕食還是移動或生育下一代都需要一個函數(shù)選擇操作方向，定位下一個位置。程序首先確定鄰居節(jié)點中的可選擇的方向，例如移動操作要尋找周圍空白的區(qū)域，而捕食的操作要尋找周圍小魚的區(qū)域。隨后將找到的可選方向按照順序存入數(shù)組中，并生成一個隨機數(shù)選擇其中的一個作為下一個動作的目標方位。鯊魚捕食、生物移動以及生育行為都是以隨機方向選擇為基礎(chǔ)的，并根據(jù)行動特點對主體和客體細胞進行操作。如圖示6所示，鯊魚有四個方向可選擇，按順序存入數(shù)組后，產(chǎn)生一個在四之內(nèi)的隨機數(shù)2選定方向LEFT，所以鯊魚隨后移動到左側(cè)方格中。

圖示 6

    鯊魚捕食的過程大體相似，將圖示6中的空白區(qū)域換成可選擇的小魚方格，然后隨機選擇一條，鯊魚移動到小魚的區(qū)域內(nèi)，清空原來占據(jù)的方格。在捕食的同時，需要將鯊魚原來的饑餓時間還原為零。如果方向選擇函數(shù)返回的信息說明周圍沒有小魚可以捕食，需要將鯊魚的饑餓時間增加一個時間單位，如果此時到達了鯊魚的饑餓極限，則將胞元置空，表示鯊魚被餓死。

    在移動的處理上，如果沒有可選的方向，是因為被同類包圍，需要將方格置空，表示細胞由于同類密度太大而死。同時需要在移動的時候判斷是否達到了各自的生育年齡，如果為真，細胞在移動到新位置后，在原來的位置生成一個同類幼體，年齡設(shè)置為零，進入下一次迭代過程。

（三）并行解決方案

（1）程序整體框架

    在了解了細胞自動機的串行實現(xiàn)方法后，可以更容易地理解并行程序在各個進程中的執(zhí)行步驟。本節(jié)主要側(cè)重在分析和實現(xiàn)多進程之間的協(xié)同工作，詳述預(yù)防和處理沖突的實現(xiàn)方法。下面將首先介紹并行程序的整體框架。

    整體框架由主進程和工作進程組成。主進程負責(zé)生成原始數(shù)據(jù)、為各工作進程分配任務(wù)、協(xié)調(diào)各工作進程之間的工作和沖突并收集整理其他進程的工作結(jié)果，控制進程同步，扮演著管理者的角色；工作進程負責(zé)接受來自主進程的數(shù)據(jù)任務(wù)，進行處理，處理的過程與串行程序基本一致。此外還負責(zé)與鄰居進程交互解決協(xié)同和數(shù)據(jù)沖突等問題，扮演著勞動者的角色。

圖示 7

（2）主要方法實現(xiàn)與分析

    （a）任務(wù)分配：本文的任務(wù)分配使用靜態(tài)分配算法。這種算法思路簡單易于實現(xiàn)，因此計算量相對較小。然而靜態(tài)分配存在明顯的缺陷，它沒有根據(jù)處理機的實際情況進行處理，任務(wù)量一經(jīng)分配就不會更改，算法的效率由最慢的進程決定，嚴重浪費了優(yōu)勢進程的計算能力，本文將在結(jié)論部分中性能提高小節(jié)中再次詳細論述動態(tài)分配的方法及分析。

     本文對靜態(tài)分配的實現(xiàn)方法是按行分塊，根據(jù)工作進程的數(shù)量整除，最后一個進程獲得余下的部分，同時每個進程分別多獲得臨近兩個進程的兩條邊界數(shù)據(jù)方便后面的計算。如圖8所示，相鄰的兩側(cè)邊界都同時分發(fā)給了兩個進程，使得各自在處理數(shù)據(jù)時能夠方便地使用已有數(shù)據(jù)，但這也埋下了數(shù)據(jù)沖突的問題，這正是接下來我要具體分析和解決的問題。

    （b）沖突處理：由上面對任務(wù)分配的闡述可知，各進程獲得的數(shù)據(jù)不是相互獨立的，他們在邊界區(qū)域有著重疊的數(shù)據(jù)單元，這就在進程獨立的處理過程中難免會產(chǎn)生處理結(jié)果不一致的現(xiàn)象如何預(yù)防和解決這些沖突就成為并行算法是否能夠成功的關(guān)鍵所在。本文在這個問題上設(shè)計了并實現(xiàn)了幾套方案來處理邊界數(shù)據(jù)的沖突問題，他們各有優(yōu)劣，下面將這幾種方法作較為詳實的介紹。

    方案一：基于消息機制的預(yù)防沖突模式

    這種方法的提出是受到Window編程中消息循環(huán)機制的啟發(fā)，將不同的進程看作是不同

圖示8

的用戶，將主進程看作服務(wù)器端，這些用戶要處理一些服務(wù)器端的公共數(shù)據(jù)。要保持這些數(shù)據(jù)讀寫的正確性和一致性，在服務(wù)器端建立消息響應(yīng)機制，有用戶發(fā)出讀寫數(shù)據(jù)的申請，消息響應(yīng)機制根據(jù)現(xiàn)在數(shù)據(jù)的狀態(tài)，對申請者的要求進行處理和回應(yīng)。這種方法可以在沖突發(fā)生之前就做出相應(yīng)處理，防止沖突的發(fā)生，而且有效地模擬了細胞自動機的隨機發(fā)生的特性，沒有因為邊界的處理破壞這一重要性質(zhì)。

    在主進程中建立一個消息循環(huán)，以所有進程發(fā)送完成自身工作的消息為退出條件，同時在主進程保留公有數(shù)據(jù)。在循環(huán)內(nèi)部設(shè)置了開關(guān)語句，對由子進程發(fā)來的消息進行分析和處理。消息被定義為一個結(jié)構(gòu)體，包含了消息的類型和消息來源，使得收到消息的主進程根據(jù)消息的類型對發(fā)來消息的進程做出相應(yīng)的響應(yīng)操作。當子進程處理的數(shù)據(jù)位于公共邊界時，它要首先向主進程發(fā)出查詢消息，查詢自己是否已經(jīng)被處理過。如果是則要從主進程更新自己擁有的數(shù)據(jù)，并放棄本次操作，然后確認可以修改目標胞元后方可對數(shù)據(jù)進行處理，在處理之后要將處理結(jié)果回傳給主進程更新公共資源，若不能修改則要重新選擇目標操作對象或進行其他處理。這個查詢過程只能有一個工作進程與主進程進行交互對話，保持對公共數(shù)據(jù)操作的互斥性。在圖示9中用偽碼形式描述了主進程中消息循環(huán)的構(gòu)成和主要功能，對可能出現(xiàn)的消息做出合理的響應(yīng)。在所有進程完成自己任務(wù)的處理后，主進程保留的公共數(shù)據(jù)是相鄰進程間統(tǒng)一認可的操作結(jié)果，將邊界和非邊界的數(shù)據(jù)統(tǒng)一起來就是本次迭代的最終效果，可以進行輸出顯示和下一次迭代的任務(wù)分配。

switch(MSG)

{

    case MSG_START: 工作進程開始查詢操作，建立進程互斥機制,暫時只接受來自消息源的消息 break;

    case MSG_END: 工作進程結(jié)束查詢操作，撤銷進程互斥機制，接收來自于所有工作進程的消息 break;

    case MSG_FINISH: 工作進程結(jié)束自己的工作，計數(shù)器加一，當達到工作進程數(shù)后消息循環(huán)退出 break;

    case MSG_APPLICATION: 工作進程發(fā)出查詢指定數(shù)據(jù)一致性的申請消息，如果數(shù)據(jù)和自己擁有的一致則繼續(xù)進行處理，，如果不一致，則需要根據(jù)具體情況做出進一步處理。 break;

    case MSG_UPDATE: 工作進程完成對數(shù)據(jù)的更改，發(fā)送數(shù)據(jù)更新消息，將處理后的數(shù)據(jù)傳給主進程。  break;

}

圖示9

    方案二：簡易沖突解決模式

    基于消息機制的預(yù)防沖突模式雖然能夠在沖突發(fā)生之前進行判斷，提供給工作進程處理的自由度，但是其中的消息響應(yīng)處理過程過于復(fù)雜，要在不同的情況下做出合理的操作，邏輯關(guān)系需要十分嚴密，實現(xiàn)起來有一定的困難。更為重要的是消息模式需要在進程間傳遞大量的消息，這對于單機系統(tǒng)沒有性能上的太大影響，然而對于并行系統(tǒng)之間的通信遠遠慢于計算數(shù)據(jù)的速度，因而這種方式必然會大大降低整體的效率，后面的方案性能部分將詳細地對比串并行算法以及不同并行算法之間的運行效率。因此，在不會嚴重影響自動機的效果的前提下，可以使用簡易的解決沖突的方式，減少不必要的通訊次數(shù)，提高處理效率。

圖示10

    此方案首先允許各工作獨立地處理自己擁有的公共數(shù)據(jù)，然后將處理的結(jié)果交換，根據(jù)一定的策略進行統(tǒng)一，消除其中互相沖突的部分。在圖示10中，在統(tǒng)一公共數(shù)據(jù)時，考慮到進程甲對邊界A的操作具有相對的主動權(quán)，同理進程乙對邊界B具有操作的主動權(quán)，因此使用接收進程甲的邊界A和進程乙的邊界B組成最終的處理結(jié)果。處理沖突的策略不盡相同，可以有很多選擇，例如根據(jù)進程編號的大小或奇偶性確定統(tǒng)一數(shù)據(jù)的優(yōu)先權(quán)等等，這里不再進行贅述。

    相對消息處理方式，第二種方式效率明顯提高，沒有頻繁的數(shù)據(jù)傳遞，節(jié)省了大量的計算時間，并且易于實現(xiàn)；然而它的缺點也很突出，由于對于沖突數(shù)據(jù)的統(tǒng)一過于簡單，沒有確切的理論根據(jù)，因此會對數(shù)據(jù)的正確性構(gòu)成不利的影響，如果整個區(qū)域足夠大，可以忽略邊界數(shù)據(jù)對整體造成的誤算。

    通過以上兩種沖突解決方法可以看出，要想在效率和計算合理兩方面上都達到完美的效果十分困難，似乎是魚和熊掌不可兼得，只能盡量在其間尋求較好的平衡。

四、實現(xiàn)方案的性能評價

（一）穿行程序試驗測評分析：

    在相同情況下，運行串行的細胞自動機程序若干次，獲得如下結(jié)果數(shù)據(jù)。

試驗編號

問題規(guī)模

迭代次數(shù)

執(zhí)行時間

1

20*20

50

4秒

2

20*20

100

9秒

3

20*20

200

16秒

4

100*20

50

10秒

5

100*20

100

23秒

6

200*20

50

17秒

7

200*20

100

43秒

有上面的運行數(shù)據(jù)表說明，在串行解決方案下，程序的執(zhí)行時間基本是隨問題的規(guī)模和迭代計算次數(shù)成線性增長。在數(shù)據(jù)表的前三行中，迭代次數(shù)分別遞增為兩倍和四倍，可以看到程序執(zhí)行的時間也近似增加為兩別和四倍，體現(xiàn)了良好的線性特征，線性函數(shù)大約為y=8x/100（在20*20規(guī)模下,x為迭代次數(shù)），其他規(guī)模下有同樣特征。在相同迭代次數(shù)情況下，試驗2、5、7大致遵循了y=2x/10+3（迭代次數(shù)為100時，x為海域規(guī)模中的行數(shù)）線性方程。

（二）并行程序試驗測評分析：

    由于運行環(huán)境與上述串行程序不同，所以運行時間有很大差異，并行試驗結(jié)果如下.

試驗編號

問題規(guī)模

進程數(shù)

迭代次數(shù)

執(zhí)行時間

1

20*20

3

100

0.377434秒

2

50*20

3

100

0.624617秒

3

20*20

4

100

0.482409秒

4

50*20

4

100

0.833043秒

5

20*20

5

100

0.854842秒

6

50*20

5

100

1.12731秒

在Windows環(huán)境下進行算法時間的統(tǒng)計誤差很大，每次試驗的結(jié)果都有較大變化，但我們可以從以上的數(shù)據(jù)看出在比較小的計算任務(wù)下，運行時間主要消耗在進程間的通信中，隨著運行進程數(shù)量的增加，運行時間不降反升。這種現(xiàn)象是由于每個進程用來完成任務(wù)的時間遠遠小于傳遞數(shù)據(jù)的時間。從試驗2、4和6看出，在任務(wù)規(guī)模增加、邊界規(guī)模不變的情況下，運行時間增加有限。顯然程序的執(zhí)行時間將會隨迭代次數(shù)線性增長。

由于問題規(guī)模較小，根據(jù)上面的分析，將串行程序并行化沒有能夠有效地提高效率，反而會因為大量的通信會增加執(zhí)行時間，當問題規(guī)模超過通訊方面的消耗后，性能方面會有明顯的改進。

五、結(jié)論

（一）解決方案的特點

    無論從串行程序還是并行解決方案，都力圖盡量突出細胞自動機的隨機性，希望能夠最大限度的模擬生態(tài)海域的自然變化特性。產(chǎn)生隨機行動的選擇序列能夠在操作區(qū)域內(nèi)較好地避免細胞狀態(tài)的改變造成的連貫不利影響，從而體現(xiàn)這樣的設(shè)計初衷。在并行方案中對任務(wù)的靜態(tài)分配過于簡單，沒有能夠根據(jù)程序運行后實際的情況調(diào)整分配策略，這一點是解決方案中最具提高潛質(zhì)的部分。由于在并行化處理數(shù)據(jù)邊界的沖突問題上過于強調(diào)計算的準確性，方案一太偏重達到較高的數(shù)據(jù)一致性操作，忽視了并行處理的主要目的是提高運行效率，這在方案二中得到了體現(xiàn)。串行程序的輸出結(jié)果較為自然，如圖11所示為細胞自動機的一次迭代結(jié)果，圖中由黑色正方形表示鯊魚，使用圓型表示小魚，原地連續(xù)輸出即表現(xiàn)為動畫效果。然而由于MPICH不支持c++的清屏操作，所以每步的結(jié)果都將魚貫輸出，遺憾地沒有實現(xiàn)動畫的效果。整體來看，解決方案的主要優(yōu)勢是對隨機性的忠實，缺陷集中在執(zhí)行效率上，仍有較大的提高空間。

圖示11

（二）方案的算法改進與性能提升

    在設(shè)計和實現(xiàn)解決方案的過程中，體會到影響算法效率的問題主要是任務(wù)的分配、沖突處理和結(jié)果回收等幾個方面。由于結(jié)果回收的通訊量是固定的，所以提升改進算法的工作集中在如何有效地達到工作進程的負載平衡和沖突的低消耗解決。下面就這兩個方面的改進算法作詳細論述。

（1）動態(tài)分配任務(wù)

    由本文前面的論述，我們已經(jīng)知道靜態(tài)分配任務(wù)的缺點，經(jīng)過查閱多種資料，改進這個問題可以通過如下幾種方式來進行動態(tài)負載平衡以提高計算效率。

    （a）集中式動態(tài)負載平衡[3]：這種方法中，所有的任務(wù)依然由主進程掌握，它將任務(wù)分為數(shù)個任務(wù)單元，構(gòu)成工作池，由于所有任務(wù)和進程同等重要，所以使用隊列進行組織，其他工作進程將向主進程申請工作任務(wù)，如果完成則提交自己的結(jié)果并領(lǐng)取下一份工作。這種方式正好符合本方案的整體架構(gòu)。值得注意的是，應(yīng)用這個方法時，需要處理好各進程間公共邊界的處理，工作進程需要知道自己的鄰居進程是誰。

圖示12

    （b）樹形分解[4]：在二維海域內(nèi)將區(qū)域進行四塊的分化，建立四叉樹，達到每個葉子節(jié)點分的區(qū)域任務(wù)具有相同的細胞，這樣就保證每個任務(wù)塊分得的區(qū)域雖然大小不一樣，但他們的計算任務(wù)卻是基本一樣的，避免了隨機生成的細胞位置不平均，造成任務(wù)不平均。如圖12所示，將海域不斷四分，直到所有葉子節(jié)點得到基本同樣的工作量。

圖示13

（2）邊界沖突改進

    在解決邊界沖突的問題上還有幾種很好的算法，這些不同的思路值得分析和借鑒，它們都有自己的特色和優(yōu)勢，在改進已有方案的性能也有一定的幫助。

    （a）操作回滾[5]：這種技術(shù)是在發(fā)生數(shù)據(jù)沖突的時候，將自己的操作回滾一步，根據(jù)新的周邊環(huán)境進行重新操作。這就要求進程一直保存操作序列，而且在找到合理可用的操作之前，可能會回滾多步操作，而且越到結(jié)尾時，周邊的胞元可能都已經(jīng)操作，想找到一個不沖突的選擇是相當費時的，保存和利用操作序列的算法也較為復(fù)雜。

    （b）序列操作[6]：這種方法將不同區(qū)域的操作分開，如圖13所示，首先各個進程操作自己的非公共區(qū)域，然后對于所有的工作進程，按照一定的順序操作公共數(shù)據(jù)，避免了同時隨機操作帶來的眾多麻煩。

    通過以上幾種方式可以對本文的方案在性能方面給予有效的提高，并且多元化的思考問題的方式也會對其他方面的改進起到啟發(fā)的作用。

 

六、參考文獻

[1] 陳國良《并行算法研究進展》計算機學(xué)會通訊

[2] 夏培肅，英漢計算機辭典,北京:人民郵電出版社,1984。

[3] Barry Wilkinson Michael Allen, Parallel Programming

[4] David E. Culler, Sources of Parallelism and Locality

[5] Sathish Vadhiyar ，University of Tennessee，MPI Process Topologies

[6] Henri Casanova ，Parallel & Distributed Computing Seminar (ICS691)

  本文關(guān)鍵詞：細胞自動機，由筆耕文化傳播整理發(fā)布。

本文編號：65706