發(fā)布時(shí)間：2016-07-04 09:01

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

 

一、概述

（一）         細(xì)胞自動機(jī)的應(yīng)用實(shí)例

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

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

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

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

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

（三）結(jié)論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三、問題分析和解決方案

（一）問題分析

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

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

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

（2）細(xì)胞行為

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

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

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

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

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

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

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

    （g）年齡增長：年齡增長是鯊魚和小魚的共有行為，當(dāng)它們沒有因?yàn)轲囸I、擁擠或衰老致死的情況下便將細(xì)胞的年齡增加一個(gè)時(shí)間單位。

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

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

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

圖示 1

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

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

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

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

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

圖示 2

   

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

 

 

（5）并行化處理

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

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

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

圖示 3

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

 

（二）串行解決方案

（1）程序整體框架

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

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

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

圖示4

圖示 5

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

圖示 6

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

    在移動的處理上，如果沒有可選的方向，是因?yàn)楸煌惏鼑�，需要將方格置空，表示�?xì)胞由于同類密度太大而死。同時(shí)需要在移動的時(shí)候判斷是否達(dá)到了各自的生育年齡，如果為真，細(xì)胞在移動到新位置后，在原來的位置生成一個(gè)同類幼體，年齡設(shè)置為零，進(jìn)入下一次迭代過程。

（三）并行解決方案

（1）程序整體框架

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

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

圖示 7

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

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

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

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

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

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

圖示8

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

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

switch(MSG)

{

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

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

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

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

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

}

圖示9

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

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

圖示10

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

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

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

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

（一）穿行程序試驗(yàn)測評分析：

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

試驗(yàn)編號

問題規(guī)模

迭代次數(shù)

執(zhí)行時(shí)間

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秒

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

（二）并行程序試驗(yàn)測評分析：

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

試驗(yàn)編號

問題規(guī)模

進(jìn)程數(shù)

迭代次數(shù)

執(zhí)行時(shí)間

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

由于問題規(guī)模較小，根據(jù)上面的分析，將串行程序并行化沒有能夠有效地提高效率，反而會因?yàn)榇罅康耐ㄐ艜黾訄?zhí)行時(shí)間，當(dāng)問題規(guī)模超過通訊方面的消耗后，性能方面會有明顯的改進(jìn)。

五、結(jié)論

（一）解決方案的特點(diǎn)

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

圖示11

（二）方案的算法改進(jìn)與性能提升

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

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

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

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

圖示12

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

圖示13

（2）邊界沖突改進(jìn)

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

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

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

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

 

六、參考文獻(xiàn)

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

[2] 夏培肅，英漢計(jì)算機(jī)辭典,北京:人民郵電出版社,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)鍵詞：細(xì)胞自動機(jī)，由筆耕文化傳播整理發(fā)布。

本文編號：65706