基于元胞自动机的沙堆模型并行计算.pdf

第 39卷 第 4期四 川 大 学 学 报 工 程 科 学 版 V o l 39 No 4 2007年 7月JOURNAL OF SI CHUAN UNI VERSI TY ENGI NEER I NG SCI ENCE ED I TI ON July 2007 文章编号 1009 3087 2007 04 0040 04 基于元胞自动机的沙堆模型并行计算 苏凤环 1 姚令侃1 李洪波2 1 西南交通大学 土木工程学院道路与铁道工程系 四川 成都 610031 2 中国石油大学 华东 储运与建筑工程学院 山东 东营 257061 摘 要 为了研究大规模沙堆模型的自组织临界性 必须进行大量计算 为了克服原有串行计算技术浪费大量时间 的缺点 引入并行计算技术 利用 M PI消息传递和 C语言 采用主从模式编程实现沙堆模型的并行算法 仿真实 验结果表明 当模型格点总数不大时 并行计算的优势并不能很好地体现出来 但当模型规模增大到 L 200后 并 行计算时间大大缩短 取得较好的加速比 将并行计算技术应用到二维沙堆模型 将会减少大规模模型的计算时 间 提高计算效率 为下一步研究自组织临界性是否具有尺度效应提供可借鉴的经验 关键词 元胞自动机 沙堆模型 自组织临界性 并行计算 消息传递 中图分类号 TP311 11文献标识码 A Parallel Co mputation of Sand PileM odel Based on Cellular Automata SU Feng huan 1 YAO Ling kan1 LIH ong bo2 1 Dept ofRoad and Railway Eng Southwest Jiaotong Univ Chengdu 610031 China 2 College ofA rchitecture and Storage Eng China Univ of Petroleum Dongying 257061 China Abstract It needed do a lot of computation in order to study the self organized critical of large scale sandpile Par allel programm ing was introduced to overcome the shortcom ing that serial program wastes a great deal of ti me The parallel algorith m of sandpile model was realized by using m aster slave mode through m essage passing interface MPI and C The si mulation result showed that the advantage of parallel computation couldn t exhibitwhenmod el scale was smal l The parallel computation ti me would shorten and got good acceleration ratio when model scale was larger than 200 The application of parallel technique to t wo di mension sandpilemodel usually shortens compu tation ti me and increases efficiency Itwould provide experience to study whether self organized critical had scale effect further Key words cellular automata sand pilemode l self organized critica l parallel computation MPI 作为控制大量广延耗散动力系统 Spatially ex tended dynam ical systems 的普遍组织原则 Bak Tang 与W iesenfeld提出了自组织临界性 Self Organized 收稿日期 2006 04 14 基金项目 国家自然科学基金资助项目 50478085 国家自然 科学基金西部重大研究计划资助项目 90202007 作者简介 苏凤环 1977 女 博士生 研究方向 道路与铁道工 程 E mai l sfhlzz yahoo com cn Criticality 简称 SOC 的概念 1 2 在这个概念里 广延耗散动力系统自发地向一种临界状态演化 沙 堆是自组织临界性的典型范例 对 SOC 的理解大 部分来自于在元胞自动机上的数值模拟 3 元胞 自动机 Cellular Automaton 以下简称为 CA 是一种 时间 空间 状态都离散 空间上的相互作用及时间 上的因果关系皆局部的网格动力学模型 4 元胞 自动机模型能十分方便地赋值出复杂的现象和动态 演化过程中的吸引子和混沌现象 5 非常适合于模 拟单元间有强烈耦合与协调作用的非线性系统的自 组织过程 通过对沙堆物理实验的研究 发现小规模的均 匀沙堆呈现 SOC现象 而大规模的均匀沙堆不呈现 SOC 6 而文献 7 和 8 所进行的水槽沙堆实验 和文献 9 和 10 所进行的单面坡沙堆实验都采用 较大尺度的沙堆 实验中发现大规模的非均匀沙也 呈现 SOC现象 为了利用计算机仿真沙堆模型研 究 SOC是否具有尺度效应 必须增大模拟规模 增 加元胞格点总数 即需要上百万颗沙粒元胞 随着 问题规模的不断扩大 利用原有串行计算机解决大 规模沙堆模型搜索过程将花费大量的计算时间 传 统的串行程序在效率上显得 力不从心 为了缩 短计算时间 节省计算空间 需要使用超级计算机或 者高性能计算系统 作者将并行计算技术引入到二维沙堆模型 SPM 中 介绍并行化程序的分析 设计和实现 同时 在高性能计算系统 曙光 2000上进行测试运算 1 串行二维沙堆模型 沙堆模型主要用来描述一类包含大量相互作用 组元的广延耗散动力系统 在临界状态下 微小的扰 动能对系统中任何数目的组元产生影响 建立在元 胞自动机基础上的沙堆模型 通过建立微观演化规 则 能够描述系统受到微扰的动态连锁反应 沙堆模型采用二维M N 网格矩阵和四周开放 的边界 其中 M N 表示网格矩阵的行列宽 初始格 子的状态值在 0 3之间变化 具体元胞自动机规则 如下 1 加沙过程 在网格中随机选择一格子进行加 沙 使其值加 1 并且统计落沙值 z x y z x y 1 1 2 扫描及崩塌过程 考察整个网格的各个格子 状态值是否有超过阈值 zcr的 若有则该格子状态值 减 4 同时向其邻近的 4个邻居格子输送一粒沙 邻 近的 4个邻居格子的状态值分别加 1 当 z x y zcr时 z x y z x y 4 z x 1 y z x 1 y 1 z x y 1 z x y 1 1 2 这样扫描沙堆网格若干遍 直到再没有格子高 度超过阈值为止 然后重复上述操作 开始下一轮 迭代 边界之外的状态值始终为 0 边缘格子上的 沙粒掉到底台之外 当满足仿真实验的迭代次数之 后 结束实验 根据得到的实验参数检验沙堆落沙 量是否服从幂律分布而判断沙堆系统是否呈现 SOC 现象 串行程序流程图如图 1所示 图 1 串行程序流程图 Fig 1 Serial program flow graph 2 并行沙堆模型 SPM 算法的设计 2 1 系统结构 并行算法是指一个过程可分配到不同的子进程 在不同的处理器上同时处理的计算方法 并行 SPM 将并行计算机的高速并行性和其天然并行性相结合 极大的促进了 CA的研究与应用 并行 SPM 的实现 大致可以分为 3类 全局型 启动计算和回收结果 而每个 Slave负责完成子 任务计算 包括局部初始化 并行计算和模块间的数 据通信 并把结果返回到 M aster 现在可以初步预 见 对于较大的沙堆网格 如果通信 计算时间是较小 的 那么使用并行计算将大大提高计算时间 主体算法描述如图 2所示 根据 SPM 模型的 特点 可采用以下并行算法 先在主任务中把二维网 格划分成数块 然后分配到各个处理器或进程中去 每个处理器或进程再在自己的内存空间中执行分配 给它的子任务 每一子任务代表完成对某一个分条 41 第 4期苏凤环 等 基于元胞自动机的沙堆模型并行计算 块作一次子组态的更新 并且只测量此条格点的数 据 如落沙数量等 最后由 MPI函数 MPI AllRe duce将所有的处理器或进程中的数据归纳 得到整 个网格的总体数据 图 2 并行算法流程图 Fig 2 Parallel program flow graph 由于并行程序的特殊性 其算法设计远不同于 串行程序 主要难点在于任务划分 进程间通信 由于并行程序的特殊性 其算法设计远不同于 串行程序 主要难点在于任务划分 进程间通信 2 2 任务分配 并行程序的核心是如何协同各结点 将任务均 匀地分配到各计算结点是影响并行程序性能的一个 主要因素 任务分配的策略有很多种 如块分配 卷帘分配 等 对于本模型 由于网格的大小在整个搜索过程 中是恒定的 因此可采用块分配的方法 所谓块分 配 是指将网格数目连续地分成若干个任务块 每个 处理器负责一个块的计算 用此方法 可以将一个 L L的沙堆网格划分成 几块 假设有 P个处理器 分别标为 0 1 2 P 1 就可把格子分成 L P块 其中每块大小为 L P P 分配给处理器 p的处理单元为从第 L P P行 到 L P P 1 行 2 式描述的沙堆崩塌过程中 一个格点与其 周围邻居格点之间进行沙粒的重新分配 所以在划 分格子之后 每块子格子的头尾两行就要从其他进 程中的相应行取得数据 此处就要用进程间通信来 实现 此处采用进程间缓存 Interprocessor Cac hing 的技术来解决 在每块的头尾两行上再加两 行缓存行 Caching row 用来接收和发送数据给近 邻的进程 为了确切自身的进程号及其上下相邻的 进程号 每个进程需要设置以下变量 int sid 自身的进程号 int up id sid 1 P 处理上一块 子格子的进程号 int l w id sid P 1 P 处理下 一块子格子的进程号 因此 设置每个子块的数组大小为 S L P 2 L 多出来的两行用来放置 Cache Row 2 3 进程间通讯 在采用进程间缓存技术时 每个进程 p的第 0行 和 L P 1 行必须跟 p 1进程的第 L P 行和 p 1进程的第 1行数据进行通讯 若是同步更新 缓冲区 的使用就会发生冲突 继而可能发生死锁 解决的方 法就是将进程分成奇进程和偶进程 第 1步是偶进程 发送数据到发送缓冲区 从接收缓冲区中接收数据 奇进程则相反 第 2步与上一步刚好相反 这样就避 免了缓冲区利用时的冲突 从避免死锁 3 结果分析 并行沙堆模型的数值模拟是在国家高性能计算 中心的曙光 2000并行系统实现的 并行程序代码 采用 C语言和消息传递库 当沙堆规模较小时 落沙量 Sd服从幂律分布 而沙堆规模很大时 沙堆落沙量服从指数分布 因此 系统不呈现 SOC 表 1 沙堆模型的实验结果 Tab 3 Experi m ental results 沙堆规模 平均落沙量 Sd g 最大落沙量 Sd g 统计分布类型 显著性水平 0 01 60783lny 7 88 0 92lnm 1009114lny 7 03 1 02lnm 20012127指数分布 50014194指数分布 图 3是利用并行计算结果绘制的大小为 100 100的沙堆坍塌图形 42四川大学学报 工程科学版 第 39卷 图 3 沙堆坍塌图形 Fig 3 Sandpile collapse 图 4显示二维沙堆模型计算机时和网格大小 所用并行结点数目的关系 由图可以看出 在格点 总数 V L L不大的情况下 并行计算的优势并不 能很好地体现出来 这是因为 L 不大的时候 每个 CPU的计算量较少 通信时间占了总的计算时间的 较大比例 所以加速比不好 当体积增大到一定程 度 如 L 200时 并行计算的优势就能较好地体 现 当 cpu数目 5时 结点间的通信时间比每个 CPU的计算时间小得多时 取得最好的加速比 但 是随着结点数目继续增加 结点间的通讯消耗时间 逐渐增大 并行效率反而降低 图 4 沙堆模型计算时间与 CPU数目的关系 Fig 4 The relationship bet ween computer tmi e and c pu nu mber 4 结 论 为了研究 SOC是否具有尺度效应 必须进行大 量的计算 而以往的模型停留在几千个格点上 不 能满足研究问题的需要 而当进行大规模的运算 时 计算技术必须提高 否则将会浪费大量的时间 因此对模型的并行计算做了探索性研究 将并行计 算技术应用到二维沙堆模型上 将会减少大规模模 型的计算时间 大大提高计算效率 使进一步研究包 括几百万颗粒子的大规模沙堆模型的系统特征成为 可能 能够为下一步将大规模技术引进 SOC提供 可借鉴的经验 致谢 感谢国家高性能计算中心 成都 及王建波 老师对并行程序进行指导帮助 参考文献 1 Bak P Tang C W iesenfeld K Self organized criticality J PhysicalRevie w A 1988 38 1 364 374 2 Yao L ingkan Huang Yuanyang Lu Yang Self organized criticality and its application in the slope disasters under gravity J Science in China Series E 2003 46 Supp 20 30 3 Yao L ingkan L i Shixiong Jiang Liangwe iSelf organized criticality and its application in granularmixture J Journal of Sichuan University Engineering Science Edition 2003 35 1 8 14 姚令侃 李仕雄 蒋良潍 自组织临界性 及其在散粒体研究中的应用 J 四川大学学报 工程科 学版 2003 35 1 8 14 4 周成虎 孙战利 地理元胞自动机研究 M 北京 科 学出版社 2000 5 W olfra m S Cellular automata and co mplexity M Balti more Addison W esley Publishing Company 1994 6 Held G A SolinaII D H Keane D T et a l Experi mental study of criticality mass fluctuation in an evolving sandpile J PhysicalReview Letters 1990 65 9 1120 1123 7 Yao Lingkan Fang Dwo On the self organized criticality of non unifor m sands J International Journal of Sedi ment Research 1998 13 3 19 24 8 L iYuqnfu Y ao Lingkan Deng Yuca i An experi ment study on the self organized criticality of sand pile modelw ith one grade slope J Jo