兰顿蚂蚁_ac自动机_云上的日子
本文关键词：细胞自动机，由笔耕文化传播整理发布。
一、概述
（一） 细胞自动机的应用实例
长久以来，人们一直希望使用计算机模拟现实世界的各种问题，细胞自动机理论的出现为这一理想提供了有力的实现工具。
剑桥的数学家John Horton Conway设计了一种著名的细胞自动机--“生命游戏”，提出用二维的胞元数组模拟问题空间，每一个数组元素中可能存在一个生命体，与它相临的数组元素表示它的邻居，生命体根据一定的规则和相邻元素改变自己的生存状态。众多的细胞自动机问题都可以根据类似的方式进行设计和实现。其中，Shark & Fish模型就是一个模拟海洋生态系统的简单应用，本文的目的就是使用并行算法将其实现。
在Shark & Fish模型中，海洋里只存在鲨鱼和小鱼，分别在各自的寿命内于海域里移动，达到生育年龄后产下后代。鲨鱼是以小鱼为食物的捕食者，在连续一段时间没有进餐后，鲨鱼由于饥饿而死。通过并行算法对这个有限的海域的模拟，可以更好地理解细胞自动机和并行计算理论的应用。
（二） 应用实例解决方案
应用串行和并行的方式分别实现细胞自动机，它们之间有区别又有众多的联系。本文在分析了细胞自动机的特性以及需解决的基本内容之后，首先分析串行的解决策略，主要集中在随机选择序列的产生算法，挑选出随机位置的细胞后进行各类型自身拥有的捕食、移动等动作。随后，将串行的算法改写成并行方法，要解决例如任务分配、冲突解决等问题。本文对比了消息处理和简单统一这两种完全不同的冲突处理方式，分析它们各自的优势和劣势。并行化处理的根本目的是提高运算速度，因此在讲述如何实现几种并行策略后，结合试验和算法对比了各方法的执行效率，分析其中的原因和改进的方法。
（三）结论
细胞自动机问题本身具有明显的并行性，使用编制合理的并行算法不但能够提高程序的执行效率，还能跟好地体现出问题内在并行的本质特点。本文使用的算法中，任务分配算法虽然简单易于实现，但是没有能动态地平衡各个处理机之间的负载；所使用的处理冲突的算法致力于尽量真实地模拟自动机的随机特性，在运行效率上并不能令人满意，所以随后又使用简单统一公共数据的方法，更多的侧重于运算效能的提高，在可容忍的限度内牺牲了一些边界地区计算的准确性。对于以上方案，有很多地方可以做出效能和处理结果上面的改进，使得整体效果得到提升。
二、理论基础与应用
（一）并行计算理论与应用
在并行计算理论出现之前，传统的程序运算在单处理机的环境下执行，由于物理条件的限制，某些运算量巨大、要求快速计算的应用问题不能得到满足。然而单处理机的性能提升难度和成本都相对较高，因此将多个处理机联合，并行的解决方案能够满足这些高性能的需求。除了提高了运算速度，也使很多要求高精度计算的问题能够在合理的时间内得以解决。此外，有很多问题由于自身的特点，特别适用于并行方法进行求解。模拟实验常常属于这种类别，更多地集中在应用领域并行算法的研究上，包括计算生物学、计算化学、计算流体动力学、飞行动力学、计算机辅助设计、数据库管理、油藏建模、中长期天气预报、海洋环流和求解N-body 问题等。例如本文实现的细胞自动机的问题本身就具有并行性。
在并行环境下解决应用问题，就需要编制并行算法。并行算法就是用多台处理机联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解[1]。使用某种程序语言实现这种算法就称为并行程序设计。
目前，有多种并行程序设计方法在不同领域得以应用，其中消息传递接口MPI渐渐成为主流的编程方案。这种方法对原有的高级程序设计语言进行扩展，使它能够进行消息库的调用，完成进程之间的直接消息传递。使用MPI进行编程时，必须显式地说明要执行那些进程，何时在那些并行进程间传递何种消息。
本文在Microsoft Visual C++.NET 2005编程平台调用消息传递接口MPI模拟细胞自动机的并行算法。
（二）细胞自动机理论与应用
自动机(Automaton)在1984年的《英汉计算机词典》[2]中被译为：指不需要人们逐步进行操作指导的设备。它的起源要追溯到1936年，Turing提出的图灵机，它是由一个有限控制器、一条无限长存储带和一个读写头构成的抽象的机器，根据不同的状态信息和当前输入按照预定的规则进行状态的转换。对于自动机的进一步发展和应用就不能不提到应用广泛的细胞自动机。
细胞自动机（Cellular Automata）最初由数学家 Stanislaw M.Ulam（1909-1984）与 John von Neumann（1903-1957）于 1950年代所提出，在型态表现上，细胞自动机是一个离散型的动力系统（Discrete Dynamical Systems）。美国数学家L.P.Hurd和K·Culik等人在90年代初，对细胞自动机分别从集合论和拓扑学等角度进行了严格地描述和定义。1970 年，John Conway 依据Von Neumann的想法进一步发展成电脑上的生命游戏（Game of Life），从此CA 的概念逐渐普及到相关领域。
细胞自动机最基本的组成细胞、细胞空间、邻居及规则四部分。简单讲，细胞自动机可以视为由一个细胞空间和定义于该空间的变换函数所组成。细胞自动机作为一种动态模型，更多的是作为一种通用性建模的方法，其应用几乎涉及社会和自然科学的各个领域。自它产生以来，被广泛地应用到社会、经济、军事和科学研究的各个领域。应用领域涉及社会学、生物学、生态学、信息科学、计算机科学、数学、物理学、化学、地理、军事学等。在社会学中，细胞自动机用于研究经济危机的形成与爆发过程、个人行为的社会性，流行现象，如服装流行色的形成等。在生物学中，细胞自动机的设计思想本身就来源于生物学自繁殖的思想，因而它在生物学上的应用更为自然而广泛。例如细胞自动机朋于肿瘤细胞的增长机理和过程模拟、人类大脑的机理探索(Victor.Jonathan.D.，1990)、艾滋病病毒HIV的感染过程(Sieburg，H.B.. 1990)、自组织、自繁殖等生命现象的研究以及最新流行的克隆 (Clone)技术的研究等 (Ermentrout.G.B，1993)。在信息学中。细胞自动机冉于研究信息的保存、传递、扩散的过程。另外。Deutsch(1972)、Sternberg(1980)和Rosenfeld(1979)等人还将二维细胞自动机应用到图像处理和模式识别中(WoIfram.S.，1983) 。在生态学中。细胞自动机用于兔子-草，鲨鱼-小鱼等生态动态变化过程的模拟，展示出令人满意的动态效果;细胞自动机还成功地应用于蚂蚁、大雁、鱼类洄游等动物的群体行为的模拟;另外，基于细胞自动机模型的生物群落的扩散模拟也是当前的一个应用热点。在计算机科学中，细胞自动机可以被看作是并行计算机而用于并行计算的研究(Wolfram.S.1983)。
本文的内容正是利用计算机并行技术实现对鲨鱼-小鱼的生态模型的模拟，下面将详细介绍细胞自动机问题并行处理的理论基础。
（三）并行实现细胞自动机的理论基础
细胞自动机在模拟生物动态变化的应用问题时必须相互等待实现同步，才能继续独立的计算，被称为全同步应用。各个细胞在每次迭代开始时同步启动，直到所有细胞都结束前一次迭代后才开始下一次迭代，称为同步迭代。
细胞自动机的问题空间首先被划分为众多的方格，被称为胞元。每个胞元处于预先设定的有限状态中的一个。根据某种规则，胞元受到邻居状态的影响，属于同一代的所有胞元同时受到影响，相应地改变自己的状态。这些规则被重复地应用于每一代的胞元。
在并行程序设计中，问题空间根据某种方式（静态或动态）被划分区域，分配给各个进程进行迭代计算，用来模拟细胞在每一代中的状态改变，进程间同步实现各代的更迭。
三、问题分析和解决方案
（一）问题分析
在程序实现Shark & Fish模型前，应该对其中涉及到的各方面问题作详细的分析，才能对整体架构和具体细节都有一个清晰的理解和认识，有助于理清头绪，使得后面的算法设计条理清楚，目的明确。
（1）数据结构
Shark & Fish模型有鲨鱼、小鱼和空白区域三种不同类型的胞元。鲨鱼类型具有类型标识、年龄和饥饿时间三个属性；小鱼类型具有类型标识和年龄两个属性；空白区域类型具有类型标识一个属性。根据三种胞元类型的特点，可以将其统一为胞元类或胞元结构体。由于整体海域由以上三种胞元组成，可以定义为胞元类型的二维数组，通过对其中胞元属性的赋值和更新实现对这个小海洋生态的模拟。对于胞元的邻居定义为上下左右四个方向的数组元素或者包括对角线方向的八个方向的数组元素。
（2）细胞行为
Shark & Fish模型每个细胞都有各自的相应的行动规则，根据相邻细胞的状态并遵循这些规则改变自己的状态。
（a）捕食：捕食是鲨鱼特有的行为，当鲨鱼的相邻胞元是一条小鱼时，鲨鱼将它吃掉，如果相邻的小鱼多于一条时，鲨鱼随机从其中选择一条捕食。
（b）饥饿：饥饿是鲨鱼特有的行为，当鲨鱼相邻的区域都是空白区域时，鲨鱼没有食物可以选择，鲨鱼将会饥饿一次，鲨鱼胞元的饥饿时间属性增加一个时间单位。
（c）移动：移动是鲨鱼和小鱼共有的行为，但它们之间也有一些区别，各自在不同的情况下进行移动。当小鱼周围有空白的相邻区域时，小鱼从中随机选择一个方向移动；当鲨鱼周围没有可以捕食的小鱼，鲨鱼饥饿的同时，如果鲨鱼周围有空白的相邻区域，则从空白区域中随机选择一个方向进行移动。
（d）饿死：饿死是鲨鱼特有的行为，鲨鱼有一个固有的饥饿忍耐时间，当鲨鱼连续没有吃到小鱼的时间超过它的饥饿极限时，鲨鱼就被饿死，将所在空间设置为空白。
（e）拥挤致死：拥挤致死是鲨鱼和小鱼共有的行为，如果鲨鱼和小鱼被同类所包围，没有可以捕食的食物或移动的空间，鲨鱼和小鱼由于同类密度太大拥挤致死，将所在空间设置为空白区域。
（f）繁殖：繁殖是鲨鱼和小鱼共有的行为，它们各自有一个固有的繁殖年龄周期，当鲨鱼和小鱼在可移动的情况下，达到了繁殖周期，则会在原地产下一条同类幼体，同时自己随机移动到相邻的空白区域。
（g）年龄增长：年龄增长是鲨鱼和小鱼的共有行为，当它们没有因为饥饿、拥挤或衰老致死的情况下便将细胞的年龄增加一个时间单位。
（h）衰老致死：衰老致死是鲨鱼和小鱼共有的行为，它们各自都有一个固有的生命极限，当鲨鱼和小鱼的年龄达到这个时间后便衰老致死，将所在空间设置为空白。
（3）区域内细胞随机序列行动
在海洋区域内进行同一代的细胞行为计算时，对细胞的操作有一定的先后顺序，不同的顺序可能生成不同的计算结果，以为较早改变的细胞应用了旧的邻居信息生成自己新的细胞状态，它的改变会影响暂时还未改变状态的邻居细胞执行后面的操作。
图示 1
如图示1 所示情况，左侧的鲨鱼首先吃掉了位于中间的小鱼，它的行动将影响下面的鲨鱼未来的选择，它需要根据改变后的情况选择其他小鱼进行捕食或移动到空白区域。因此需要对海域内的生物进行随机顺序的选择操作，避免固定操作顺序会造成连续的影响，从而尽量模拟现实情况中事件发生的随机性。（4）无限区域的有限表示
在有限区域内对生物海域进行模拟就要考虑当鲨鱼或小鱼游弋到区域的最外层边界时的处理，不但这些胞元的状态取决于邻居胞元的信息，它们下一个所处的位置也可能超出了预先设定的范围，需做特殊处理。
（a）边界反射法：这种处理方法使得生物运动出边界后，像镜子对光线的反射一样，细胞将向初始运动的反方向活动。
（b）边界循环法：循环法将整个区域看成是上下、左右边界相连的球状区域，当细胞从一边出界后，将出现在相对应的另一侧边界处。如图示2所示，圆圈内的鲨鱼向左移动出边界，它将出现在同行的右侧列边界中。本文所使用的就是这种方法来实现环形海域的模拟。
图示 2
通过以上几种方法，就可以用有限区域模拟生物在无限环境下的活动状态。
（5）并行化处理
将串行算法改写为并行算法需要了解并行环境进程的操作特点，分析可能出现的新问题，提出有效的解决办法。下面就针对并行解决方案中进程间相互协同操作的几个突出的问题作简要地分析。
（a）任务分配：要将现有问题并行化处理就要将整体的操作区域按照一定的策略进行划分，分别交由相应的子进程处理。任务的分配一般分为静态分配和动态分配。静态分配就是在运行解决方案之前确定每个处理机获得的任务量；与此相对应的是动态分配，这种方法可以实时地根据处理机实际处理能力和具体条件动态地调整任务量。显然动态分配对于细胞自动机这样的同步计算问题显得尤为重要，根据木桶原理，每一次迭代的执行时间是由执行最慢的进程所决定的。因此将任务合理地分配给各个进程，尽量使所有工作进程在同一时间结束处理，减少等待时间的处理机效能浪费，能够有效地提高并行程序的执行效率。
（b）同步计算：子进程的处理必须保持同步性，即在所有子进程完成这一代的计算之前，任何进程不能进行下一代的处理。工作进程完成自己的处理任务之后，如果没有和兄弟进程进行信息交换，它就由于没有获得完整的数据而不能提前开始下一代的计算。
图示 3
（c）边界冲突：在任务分配给各个公共进程之后，进程要完成自己区域内的计算，必须获得相邻进程的部分数据，提供给所获区域最外侧胞元的邻居节点信息。然而工作进程之间的计算是独立的，进程内部的处理又是随机的，因此它们对这些公共数据的处理结果可能是各不相同的，这就产生了边界冲突。例如图示3，灰色区域表示的是上下两个进程数据的边界，可以看到两条鲨鱼都会选择捕食圆圈中的这条鱼，由于边界两边的数据被分别处理，所以会在相互统一信息时产生冲突。这些数据关系到各代数据的一致性，如何预防数据冲突的或者在冲突发生之后有效的解决冲突影响着计算的正确性；同时由于进程间通讯耗费的时间远远多于计算相同数据，因此处理冲突的策略也可能极大地影响并行算法的时间复杂度。因此，设计一种能够确实反映自动机的随机特性又不明显降低通讯效率的策略就成为并行实现细胞自动机的关键所在。
（二）串行解决方案
（1）程序整体框架
在单进程环境下，处理过程相对并行比较简单清晰，主要有定义并初始化海域内生物最初状态、生成随机选择策略、对所选细胞单元进行处理、完成迭代等几个部分组成。程序整体框架如图示4所描述。
（2）主要方法实现与分析
（a）细胞随机选择序列：由于海域由二维胞元数组表示，每一代的细胞保存其中。随即序列生成函数建立鲨鱼和小鱼两条队列的头指针，函数按行扫描胞元数组，生成一个在队列长度的范围内的随机数，表示随机插入队列的位置，将扫描到的细胞指针插入所属类型的队列中。当处理海域内的细胞时，每次从队列中提取队列头部的细胞进行处理，所处理的细胞将就是按照随机位置出现的。由于鲨鱼处于食物链中的强势地位，因此首先处理鲨鱼队列。如图示5所示，建立鲨鱼随机细胞的队列，扫描海域，分别将其中的鲨鱼插入到队列4、1、2、6、3、5位置。
图示4
图示 5
（b）细胞行为：无论细胞是鲨鱼还是小鱼，无论是进行捕食还是移动或生育下一代都需要一个函数选择操作方向，定位下一个位置。程序首先确定邻居节点中的可选择的方向，例如移动操作要寻找周围空白的区域，而捕食的操作要寻找周围小鱼的区域。随后将找到的可选方向按照顺序存入数组中，并生成一个随机数选择其中的一个作为下一个动作的目标方位。鲨鱼捕食、生物移动以及生育行为都是以随机方向选择为基础的，并根据行动特点对主体和客体细胞进行操作。如图示6所示，鲨鱼有四个方向可选择，按顺序存入数组后，产生一个在四之内的随机数2选定方向LEFT，所以鲨鱼随后移动到左侧方格中。
图示 6
鲨鱼捕食的过程大体相似，将图示6中的空白区域换成可选择的小鱼方格，然后随机选择一条，鲨鱼移动到小鱼的区域内，清空原来占据的方格。在捕食的同时，需要将鲨鱼原来的饥饿时间还原为零。如果方向选择函数返回的信息说明周围没有小鱼可以捕食，需要将鲨鱼的饥饿时间增加一个时间单位，如果此时到达了鲨鱼的饥饿极限，则将胞元置空，表示鲨鱼被饿死。在移动的处理上，如果没有可选的方向，是因为被同类包围，需要将方格置空，表示细胞由于同类密度太大而死。同时需要在移动的时候判断是否达到了各自的生育年龄，如果为真，细胞在移动到新位置后，在原来的位置生成一个同类幼体，年龄设置为零，进入下一次迭代过程。
（三）并行解决方案
（1）程序整体框架
在了解了细胞自动机的串行实现方法后，可以更容易地理解并行程序在各个进程中的执行步骤。本节主要侧重在分析和实现多进程之间的协同工作，详述预防和处理冲突的实现方法。下面将首先介绍并行程序的整体框架。
整体框架由主进程和工作进程组成。主进程负责生成原始数据、为各工作进程分配任务、协调各工作进程之间的工作和冲突并收集整理其他进程的工作结果，控制进程同步，扮演着管理者的角色；工作进程负责接受来自主进程的数据任务，进行处理，处理的过程与串行程序基本一致。此外还负责与邻居进程交互解决协同和数据冲突等问题，扮演着劳动者的角色。
图示 7
（2）主要方法实现与分析
（a）任务分配：本文的任务分配使用静态分配算法。这种算法思路简单易于实现，因此计算量相对较小。然而静态分配存在明显的缺陷，它没有根据处理机的实际情况进行处理，任务量一经分配就不会更改，算法的效率由最慢的进程决定，严重浪费了优势进程的计算能力，本文将在结论部分中性能提高小节中再次详细论述动态分配的方法及分析。
本文对静态分配的实现方法是按行分块，根据工作进程的数量整除，最后一个进程获得余下的部分，同时每个进程分别多获得临近两个进程的两条边界数据方便后面的计算。如图8所示，相邻的两侧边界都同时分发给了两个进程，使得各自在处理数据时能够方便地使用已有数据，但这也埋下了数据冲突的问题，这正是接下来我要具体分析和解决的问题。
（b）冲突处理：由上面对任务分配的阐述可知，各进程获得的数据不是相互独立的，他们在边界区域有着重叠的数据单元，这就在进程独立的处理过程中难免会产生处理结果不一致的现象如何预防和解决这些冲突就成为并行算法是否能够成功的关键所在。本文在这个问题上设计了并实现了几套方案来处理边界数据的冲突问题，他们各有优劣，下面将这几种方法作较为详实的介绍。
方案一：基于消息机制的预防冲突模式
这种方法的提出是受到Window编程中消息循环机制的启发，将不同的进程看作是不同
图示8
的用户，将主进程看作服务器端，这些用户要处理一些服务器端的公共数据。要保持这些数据读写的正确性和一致性，在服务器端建立消息响应机制，有用户发出读写数据的申请，消息响应机制根据现在数据的状态，对申请者的要求进行处理和回应。这种方法可以在冲突发生之前就做出相应处理，防止冲突的发生，而且有效地模拟了细胞自动机的随机发生的特性，没有因为边界的处理破坏这一重要性质。在主进程中建立一个消息循环，以所有进程发送完成自身工作的消息为退出条件，同时在主进程保留公有数据。在循环内部设置了开关语句，对由子进程发来的消息进行分析和处理。消息被定义为一个结构体，包含了消息的类型和消息来源，使得收到消息的主进程根据消息的类型对发来消息的进程做出相应的响应操作。当子进程处理的数据位于公共边界时，它要首先向主进程发出查询消息，查询自己是否已经被处理过。如果是则要从主进程更新自己拥有的数据，并放弃本次操作，然后确认可以修改目标胞元后方可对数据进行处理，在处理之后要将处理结果回传给主进程更新公共资源，若不能修改则要重新选择目标操作对象或进行其他处理。这个查询过程只能有一个工作进程与主进程进行交互对话，保持对公共数据操作的互斥性。在图示9中用伪码形式描述了主进程中消息循环的构成和主要功能，对可能出现的消息做出合理的响应。在所有进程完成自己任务的处理后，主进程保留的公共数据是相邻进程间统一认可的操作结果，将边界和非边界的数据统一起来就是本次迭代的最终效果，可以进行输出显示和下一次迭代的任务分配。
switch(MSG)
{
case MSG_START: 工作进程开始查询操作，建立进程互斥机制,暂时只接受来自消息源的消息 break;
case MSG_END: 工作进程结束查询操作，撤销进程互斥机制，接收来自于所有工作进程的消息 break;
case MSG_FINISH: 工作进程结束自己的工作，计数器加一，当达到工作进程数后消息循环退出 break;
case MSG_APPLICATION: 工作进程发出查询指定数据一致性的申请消息，如果数据和自己拥有的一致则继续进行处理，，如果不一致，则需要根据具体情况做出进一步处理。 break;
case MSG_UPDATE: 工作进程完成对数据的更改，发送数据更新消息，将处理后的数据传给主进程。 break;
}
图示9
方案二：简易冲突解决模式基于消息机制的预防冲突模式虽然能够在冲突发生之前进行判断，提供给工作进程处理的自由度，但是其中的消息响应处理过程过于复杂，要在不同的情况下做出合理的操作，逻辑关系需要十分严密，实现起来有一定的困难。更为重要的是消息模式需要在进程间传递大量的消息，这对于单机系统没有性能上的太大影响，然而对于并行系统之间的通信远远慢于计算数据的速度，因而这种方式必然会大大降低整体的效率，后面的方案性能部分将详细地对比串并行算法以及不同并行算法之间的运行效率。因此，在不会严重影响自动机的效果的前提下，可以使用简易的解决冲突的方式，减少不必要的通讯次数，提高处理效率。
图示10
此方案首先允许各工作独立地处理自己拥有的公共数据，然后将处理的结果交换，根据一定的策略进行统一，消除其中互相冲突的部分。在图示10中，在统一公共数据时，考虑到进程甲对边界A的操作具有相对的主动权，同理进程乙对边界B具有操作的主动权，因此使用接收进程甲的边界A和进程乙的边界B组成最终的处理结果。处理冲突的策略不尽相同，可以有很多选择，例如根据进程编号的大小或奇偶性确定统一数据的优先权等等，这里不再进行赘述。相对消息处理方式，第二种方式效率明显提高，没有频繁的数据传递，节省了大量的计算时间，并且易于实现；然而它的缺点也很突出，由于对于冲突数据的统一过于简单，没有确切的理论根据，因此会对数据的正确性构成不利的影响，如果整个区域足够大，可以忽略边界数据对整体造成的误算。
通过以上两种冲突解决方法可以看出，要想在效率和计算合理两方面上都达到完美的效果十分困难，似乎是鱼和熊掌不可兼得，只能尽量在其间寻求较好的平衡。
四、实现方案的性能评价
（一）穿行程序试验测评分析：
在相同情况下，运行串行的细胞自动机程序若干次，获得如下结果数据。
试验编号
问题规模
迭代次数
执行时间
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=8x/100（在20*20规模下,x为迭代次数），其他规模下有同样特征。在相同迭代次数情况下，试验2、5、7大致遵循了y=2x/10+3（迭代次数为100时，x为海域规模中的行数）线性方程。
（二）并行程序试验测评分析：
由于运行环境与上述串行程序不同，所以运行时间有很大差异，并行试验结果如下.
试验编号
问题规模
进程数
迭代次数
执行时间
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环境下进行算法时间的统计误差很大，每次试验的结果都有较大变化，但我们可以从以上的数据看出在比较小的计算任务下，运行时间主要消耗在进程间的通信中，随着运行进程数量的增加，运行时间不降反升。这种现象是由于每个进程用来完成任务的时间远远小于传递数据的时间。从试验2、4和6看出，在任务规模增加、边界规模不变的情况下，运行时间增加有限。显然程序的执行时间将会随迭代次数线性增长。
由于问题规模较小，根据上面的分析，将串行程序并行化没有能够有效地提高效率，反而会因为大量的通信会增加执行时间，当问题规模超过通讯方面的消耗后，性能方面会有明显的改进。
五、结论
（一）解决方案的特点
无论从串行程序还是并行解决方案，都力图尽量突出细胞自动机的随机性，希望能够最大限度的模拟生态海域的自然变化特性。产生随机行动的选择序列能够在操作区域内较好地避免细胞状态的改变造成的连贯不利影响，从而体现这样的设计初衷。在并行方案中对任务的静态分配过于简单，没有能够根据程序运行后实际的情况调整分配策略，这一点是解决方案中最具提高潜质的部分。由于在并行化处理数据边界的冲突问题上过于强调计算的准确性，方案一太偏重达到较高的数据一致性操作，忽视了并行处理的主要目的是提高运行效率，这在方案二中得到了体现。串行程序的输出结果较为自然，如图11所示为细胞自动机的一次迭代结果，图中由黑色正方形表示鲨鱼，使用圆型表示小鱼，原地连续输出即表现为动画效果。然而由于MPICH不支持c++的清屏操作，所以每步的结果都将鱼贯输出，遗憾地没有实现动画的效果。整体来看，解决方案的主要优势是对随机性的忠实，缺陷集中在执行效率上，仍有较大的提高空间。
图示11
（二）方案的算法改进与性能提升
在设计和实现解决方案的过程中，体会到影响算法效率的问题主要是任务的分配、冲突处理和结果回收等几个方面。由于结果回收的通讯量是固定的，所以提升改进算法的工作集中在如何有效地达到工作进程的负载平衡和冲突的低消耗解决。下面就这两个方面的改进算法作详细论述。
（1）动态分配任务
由本文前面的论述，我们已经知道静态分配任务的缺点，经过查阅多种资料，改进这个问题可以通过如下几种方式来进行动态负载平衡以提高计算效率。
（a）集中式动态负载平衡[3]：这种方法中，所有的任务依然由主进程掌握，它将任务分为数个任务单元，构成工作池，由于所有任务和进程同等重要，所以使用队列进行组织，其他工作进程将向主进程申请工作任务，如果完成则提交自己的结果并领取下一份工作。这种方式正好符合本方案的整体架构。值得注意的是，应用这个方法时，需要处理好各进程间公共边界的处理，工作进程需要知道自己的邻居进程是谁。
图示12
（b）树形分解[4]：在二维海域内将区域进行四块的分化，建立四叉树，达到每个叶子节点分的区域任务具有相同的细胞，这样就保证每个任务块分得的区域虽然大小不一样，但他们的计算任务却是基本一样的，避免了随机生成的细胞位置不平均，造成任务不平均。如图12所示，将海域不断四分，直到所有叶子节点得到基本同样的工作量。
图示13
在解决边界冲突的问题上还有几种很好的算法，这些不同的思路值得分析和借鉴，它们都有自己的特色和优势，在改进已有方案的性能也有一定的帮助。
（a）操作回滚[5]：这种技术是在发生数据冲突的时候，将自己的操作回滚一步，根据新的周边环境进行重新操作。这就要求进程一直保存操作序列，而且在找到合理可用的操作之前，可能会回滚多步操作，而且越到结尾时，周边的胞元可能都已经操作，想找到一个不冲突的选择是相当费时的，保存和利用操作序列的算法也较为复杂。
（b）序列操作[6]：这种方法将不同区域的操作分开，如图13所示，首先各个进程操作自己的非公共区域，然后对于所有的工作进程，按照一定的顺序操作公共数据，避免了同时随机操作带来的众多麻烦。
通过以上几种方式可以对本文的方案在性能方面给予有效的提高，并且多元化的思考问题的方式也会对其他方面的改进起到启发的作用。
六、参考文献
[1] 陈国良《并行算法研究进展》计算机学会通讯
[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)
本文关键词：细胞自动机，由笔耕文化传播整理发布。
本文编号：65706
本文链接：https://www.wllwen.com/jianzhugongchenglunwen/65706.html
