（运筹学与控制论专业论文）基于petsc的交通流并行数值模拟.pdf

基于p e t s e 的交通流，并彳于数值模拟 基于p e t s c 的交通流并行数值模拟 摘要 交通流建模中，将交通流视为流体从而以流体力学方法进行研究是广为 采用的方法之一；从守恒方程生等+ 垒每= 咖( x ，r ) 出发，问题常可 归结为一个通常难以解析求解的二阶非线性偏微分方程，其一般形式为 鲁+ ( 办警= 1 ( p ) 筹+ 咖。并行计算是计算技术发展的一个重要方向， 本文针对交通流建模中提出的非线性二阶偏微分方程，讨论了并行计算环 境下利用p e t s c 实现并行数值求解的过程，并就不同的处边值条件给出 了数值算例及其结果。 关键词：交通流模型，二阶非线性偏微分方程，并行计算，p e t s c 。 ! _ 二汀大学硕士学位论文 摹 jp e t s c 的交通流并行数值模拟 p a r a l l e is i m u l a t i o no ft r a 仟i cf l o wb a s e do np e t s c1 _ o o l k i t a b s t r a c t t om o d e lv e h i c u l a rt r a f f i c ，ac o m m o nw a yi st ot r e a tt h et r a f f i c s t r e a ma sao n ed i m e n s i o n a lc o m p r e s s i b l ef l u i df l o w as e c o n d o r d e rn o n l i n e a rp d ef o rt h i sf l o wt h a th a st h e g e n e r a l f o r m 警+ 跏瓦c q p = 咖) 爰+ 币i s d e m e db a s e d 。nf h ec 。n s e r v 酬。n a w 掣+ 掣：咖 ) u s u a l l yt h i s p d ei su n s o i v a b l e d td 工 。 a n a l y t i c a l l y p a r a l l e lc o m p u t i n gi sam a i nt r e n di nt h ed e v e l o p m e n t o fc o m p u t e rs c i e n c ea n dt e c h n o l o g y i nn u m e r i c a l l ys o l v i n gt h e s e c o n d o r d e rn o n l i n e a rp d e p r o p o s e d f o rt r a f f i cf l o w p a r a l l e l i z a t i o nh a sb e e na c h i e v e db yu s i n gp e t s c ，aw e l ld e s i g n e d p a r a l l e lt o o l k i tf o ra c c e l e r a t i n gp a r a l l e lp r o g r a m m i n gw i t h o u tl o s i n g p e r f o r m a n c e n u m e r i c a le x p e r i m e n t s w i t hv a r i o u si n i t i a la n d b o u n d a r yc o n d i t i o n sh a v eb e e np e r f o r m e da n dt h ec o r r e s p o n d i n g r e s u l t sa r eg i v e n 曲扛玉兰皿兰监盐立一盅王上口= s 曲监墒j 直盘益盐值撞拉 第一章绪论 交通是国民经济和社会发展的命脉。当前，社会经济的快速发展和交 通建设的相对滞后已经构成非常突出的矛盾。因此，交通流研究作为一f 新兴的交叉性边缘学科，近年来受到越来越多的关注和重视。何谓交通? 交通是指人、物以及思想、信息在不同地点的移动( c o m m u n i c a t i o n ) 。一般 把人和物的移动称为经典意义上的交通( t r a n s p o r t a t i o n ) ，而把思想、信 息的传递称为通信( c o m m u n i c a t i o n ) “ 。交通研究大体可分为两个门类： 交通科学和交通工程；前者是后者的基础。交通流理论研究综合运用物理、 数学、力学、系统工程和计算机科学等工具以达到两个目的：建立能描述实 际交通一般特性的交通流模型和揭示控制交通流动的基本规律。1 9 3 3 年， k i n z e s 首次提出用p o i s s o y l 分布分析交叉口交通。 ，建立了第一个交通流 模型：1 9 5 5 年，l i g h t h i l l 和w h i t h a m 在其著名论文论运动学波中提出 了交通流的运动学理论“h 1 ，对交通流理论的发展作出了重要贡献；发展 到今天，建立交通模型，模拟交通流问题，大体上可分为三类不同的描述 方法：微观、宏观和中观法。其中宏观方法将交通流视作由大量车辆组成的 可压缩连续流体介质，用流体力学的基本方程作为控制方程来研究车辆集 体的综合平均行为特性；微观方法则研究单个车辆在相互作用f 的个体行 为特性，主要有车辆跟弛模型和元胞自动机模型；至于中观方法是基于概 率描述的气体动力学模型( b o l t z m a n n 方程) 。一个主要的问题是，无论 哪种方法建模，都会碰到难于解析求解的微分方程和缺乏考虑各种真实交 通环境的灵活性。从2 0 世纪8 0 年代起，随着计算机计算能力的大幅提高 使得计算机数值模拟成为研究交通流的一种重要的手段，计算机仿真和模 拟成为交通建模的一个重要的发展方向。当前，发展适合交通问题的分布、 并行的模拟技术和手段是交通流研究的热点问题之一，这有两个原因：一 是因为交通系统是由人、车、道路和环境所构成的具有复杂性、动态性和随 机性的系统，无论是理论模拟研究还是实际的交通工程控制管理都对计算 能力提出了极高的要求；比如，跟驰模型中，每辆车都有自己的运动方程 曲扛主生皿土堡位盐丑l 一 基王p e 工s 曲变通流芷盘盘擅撞拟 模拟计算的时间和内存要求和车辆数成正比；再如用宏观连续模型描述多 车道或一个路网的车流运动时，就要求解偏微分方程组或者高维的偏微分 方程，对c p u 和内存的要求则和车道数或路网规模成正比。原因之二则是 一些成功运用超级计算机并行模拟交通的例子吸引了不少交通理论和工程 研究人员的目光；1 9 9 2 年，n a g e l 和s c h r e c k e n b e r g 5 3 运用大容量高速并 行模拟，首次显示出车流从自由运动相至煸部阻塞相的相变；而 t r a n s i m s 项目则使用了包含6 2 0 0 个c p u 的“赢l u ”( b l u em o u n t a i n ) 超 级计算机 6 3 。 并行计算是计算机科学技术发展的一个重要方向和趋势。并行计算机 的体系结构 7 1 从早期( 2 0 世纪7 0 年代) 的专用的昂贵的向量超级计算机 p v p ( p a r a l1 e lv e c t o rp r o c e s s o r s ) 开始发展至今，呈现出多样化的特点 有对称多处理共享存储并行机s m p ( s y m m e t r i cm u l t i p r o c e s s i n g ) ，分布共 享存储并行机d s m ( d i s t r i b u t e ds h a r e dm e _ m q r y ) ，大规模并行机m p p ( l a s s i v e l y p a r a l e l p r o c e s s o r s ) ，工作站机群c o w ( c l u s t e ro f w o r k s t a t i o n ) 和微机机群( p cc l u s te r ) 。随着并行机体系结构的演变，并 行汁算机也逐渐从高端走向大众化。然而推广普及并行计算技术仍面临不 少困难，其中之一是并行应用程序的开发是一个较复杂、困难的任务嘲。关 于并行实现在高性能计算中的重要作月j ，在hj s i e g e l 等人的论文慨中 作了强调： “一个广泛流传的错误概念是在高性能计算领域中两个最重要 的部分是体系结构和算法，然而两者之问的接口也是一个关键问题。”与 串行相比，并行编程存在一些新的问题，这些问题涉及不确定性、通信、同 步、数据划分和分配、负载平衡、容错、异构、共享分布存储以及死锁竞争 条件等等。如何有效解决这些问题，是高效率实现并行计算能力面临的 个挑战。目前，开发并行应用程序从策略上大体有两种实现并行的机制： 隐式并行机制采用并行语言和并行编译器，用户不能指定而且不能控制计 算的调度和数据的分配，其性能取决于编译技术，就目自h 而言，其可应用 的场合较少；显式并行机制要求用户负责绝大部分并行实现的细节，比如 任务的分配、任务到进程的的映射以及通信的结构等等，显式并行的前提 2 是用户能够最有效的分析并判断如何最大限度的开发应用的并行性。实践 中，自动并行化方法因其局限性较少采用，而一切从头开始开发效率较低 介于两者之间的一种途径是使用并行库，这是目前并行实现技术的一个较 重要的方向；其基本思想是将一些经常使用的代码封装到一个用高效代码 实现的并行库中，要求并行库对体系结构和网络透明，可移植，提供较简 单的接口支持传统的高级语言，最终高性能地实现并行透明性。 拉尘二二唑籀土当纠芷逾立一釜王上e = s l 敞蠛瘟型j 至盐擅基越 第二章宏观交通流的流体力学模型n o 从宏观上将众多车辆在道路上瀚运动视作一维可压缩流体，用流体模篷 加以描述和研究，是交通流建模的重要方法之一。 记_ ；。侮移，v 良妒斧弱j ( x , o 分别为积黟她车流的密度、速发和流量黼数，砌从定 义有：j ( z 。f ) = p ( x ，f ) v ( 戈，f ) ， 根据车流满足守恒律可褥守恒方程“： 掣+ 掣= ，线 f 2 1 ) 这里咖( x ，t ) 为源汇项。欲求解还须再建一方程。一般而言，车流密度越离 委l 车速越低；反之翔车逡越高；鏊予诧，l i g h t h i l l w h i t h a m 截设了一个均 衡的速度一密艘关系： v = v 。( p ， 或 d = v 。( p ) 1 0 = j ( p ) ( 2 2 ) 代入( 2 1 ) 得： 警+ 掣警砘 汜。； 进步如假设流曩不仅是密度而且还是密度梯度的嫩数： 扣j ( p 卜n 袈， 这萋d 为垂鬻数。剩交为； 鲁+ 掣，筹蛆裳撬 泣t ； 与方程泛3 ) 鞠吃，眩妨多了旗性颈d 罴，这一方瑟光滑了解懿滋 4 出i l 丘生蜘土生拉i 垒立 基王p e 】：s 的空调流拄- 痖数擅檀拟 波结构，另一方面则可以增强数值解的稳定性，应该说是相当合理的。方 程的具体形式取决于纠的给出，这通常是经验的；比如给出线性的速度 一密度关系： v ( p ) = v 。( 1 一j ) _ ) ， 或 ( p ) = v 。p ( 1 一j l ) ， 卜j 即可得g r e e n s h i e l d s 模型3 ，其为一b u r g e r s 型方程： 警地嚣- d 囊地 这里唧一( 1 一笔) 。 一般的，描述车流的运动学模型方程可表示为： 瓦c g p 吲办舞刮办囊+ 咖 ( 2 5 ) 搬江堂强i ：擞垃垃立一一一立目墅i s 工曲立趟戚盛益盐工直撞烈 第三章模型方程的离散化 考虑方程( 2 5 ) 在初边值条件下的定解闻题的数值求解： 掣吲砖掣刊办掣删彬) ， p ( x ，r ) ，；o 一妒( z ) ， p ( x ，f ) 。：o = y o ( f ) ， p ( x ， ) ：j = y l ( f j ， ( s 。1 ) ( 3 2 ) 嗣差分法数德求艇熬物型或对滚一扩敖方程时，麓分格式瓣选择应绞 筹考虑精度、稳定性等数值性质、计算资源条件和并行化方法等“引n 副“。 般显式差分格式计箕篱便，对计算资源需求较低，具韵+ 良好的并行性适予 直接组织并行计算，但它怒条件稳定的；隐式差分格式具有良好的稳定性 ( 如古典隐格式和c r a n k - n i c h o l s o n 差分格式是绝对稳定的) “，但它在 每一时闯层需求解阶数为空间丽格数的线性方程组，从而对计算资源要求 较高，通常还难以直接组织并行计算，而要在求解线性方程组时并行化。 这里，对定簿翔麓( 3 。1 ) 一( 3 。2 ) 豹离散讫采麓c r a n k n i c h o l s o n 差分格式； 对区域( o ，1 ) ， o ，1 。作矩形网格划分，记 = 1 i n 和t = 1 i m 分别为空间和时 闻步长，可褥： 掣吲鲋堕o + i 鼍n + l 萨n n 训) _ 监翌鼍苎丝? f f = 1 , 2 。o n = 0 ，1 2 ) 整理( 3 。3 ) ，写成矩阵的型式： 一( 妒+ 1 = c ? ”= o ，1 2 这里记： 6 ( 3 3 ) ( 3 4 ) r = 孑t ，“昝等 ( p ? ) ，口牛兰h ( p ? ) ，( 川，2 ，_ 1 ) p ”= ( p ：，p n 】，p 嚣) 7 ，x m + 1 = ( p ：+ 1 ，p n + 一1 1 ) 7 爿： 1 + 2 口? “? 一e l o 0 0 _-t 一( 仪+ 卢 川) 1 + 2 芦“：一芦： 一 0 一( 。c ：! ，+ 卢：! 。) 1 + 2 f i ： d ? 1 + r e 1 2 口? 0 0 。c ：川+ e l 1 2 一d ! 川+ e l “譬! ，+ 口：! 。1 2 口：! 。一d c ? ! + 卢譬 计算按照时间层展开，在每一时间层求解一个线性方程组( 3 4 ) ，其唯数 等于空间网格数，并行化也在此展开，此即所谓时间步进( t i m e s t e p i n g ) 的解法。 7 濑援蠢鐾霆立苎堕擅扛已一一望童撼烈艘l 空通氲盐矗煎亟整益 第四章并行计算 4 。l 荠 亍计算枫体系结稳彝荠行编程环境 并行计算机按能同时处理的指令流和数据流从逻辑上可分为：s i s d ( s i n g l e i n s t r u c t i o ns t r e a m m u l t i p l e d a t as t r e a m ) 和m i m d ( m u l t i p l ei n s t r u c t i o ns t r e a mm u l t i p l ed a t as t r e a m ) 蹲种结葶哿，比 较逶瘸煞是m i m d 券牙系统。按爨c p u 对痰存豹壹接可访鹈浚可将m i m d 分 为共享内存( s h a r e dm e m o r y ，s m ) 帮分布内存( d i s t r i b u t i o nm e m o r y ， d m ) 两类；其中共事内存( s m ) 又可进一步分为对称多处理机s m p ( s y n 】i i l e t r i cm u l t i p r o c e s s o r ) 和分布菸享内存d s m ( d i s t r i b u t e ds h a r e d m e m o r y ) ，此外，物疆上分布内存的并幸亍系统也可在操作笨统层西应用虚 叛技术实现逻辑上豹共享蠹存，稼为s v m ( s h a r e dv i r t u a lm e m o r y ，囊 拟共享内存) ，以提供编程者一个统一的系统映像和单一的地址空间：所 以，从并行编程的角度，并行系统按系统组成的耦合程威和存储访问语义 可划分为u m a ( u n i f o r mm e m o r ya c c e s s ，均匀存储访问) 、n 【j m a ( n o n u n i f o r mm e m o r ya c c e s s ，； 均匀存镶访淀) 和n o r m a ( n or e m o t em e m o r y a c c e s s ，菲远程存储访闯) 三释模型。 在科学和工程计算实践中，a p o ( a u t op a r a l l e lo p t i o n ，自动并行编译 选项) 、s h m e m ( s h a r e dm e m o r ya c c e s sl i b r a r y ) 、o p e n m p 以及p v m ( p a r a l l e lv i r t u a lm a c h i n e ，荠行鹰擞机) 和m p i ( m e s s a g ep a s s i n g i n t e r f a c e ，溃惑传滋接圈) 是较誊两豹并李亍绽程丽凌；o p e n m p 楚基予共 枣内存的编程环境，而s h m e m 、m p i 和p v m 则是基于消息传递的并行编程 环境。其中，m p i 是一个由包括来自研究实验室、大学和产业界的联合体 ( m p if o r u m ，m p i 论坛) 制定的，得剿广泛支持的消息传递并行编程标 瀣，1 9 9 4 年发布tm p i - i ，1 9 9 7 年裁定了m p i 一2 ：它定义了一个函数库及 英函数豹接口焉予滋程润消息传递；它以疆立于平台，与滔言无关酶方式 说明库，并不给定嶷体实现：但m p i 丽向高级语言而设计，已实现与 逝虹盘坐垣士茎拉_ i 金立j e 一巳五e 泣曲立垣监韭五盘值撞拟 f o r t r a n 和c 的捆绑，其使用的消息( m e s s a g e ) 类型与相应的高级语言的 数据类型相一致：m p i 具有高可移植性和通用性，体系结构和网络透明 性以及高效率，是适用于各种并行计算平台的一个编程环境。 4 2 基于p e t s c 的并行程序实现叫3 由于m p i 仍是比较底层的通信库，直接在萁上编程开发效率较低，所 以我们同时采用了由美国a r g o n n e 国家重点实验室( a r g o n n en a t i o n a l l a b o r a t o r y ) 开发的p e t s e ( p o r t a b l e ，e x t e n s i b l e t o o l k i tf o r s c i e n t i f i cc o m p u t a t i o n ) ，一个面向高性能计算机的主要用于求解基于 偏微分方程的大规模应用问题的并行软件库：p e t s c 是美国能源部 o d e 2 0 0 0 支持的多个s c i d a c ( s c i e n t i f i cd i s c o v e r yt h r o u g ha d v a n c e d c o m p u t i n g ) 项目之一，是一个公开源代码项目，从1 9 9 5 到现在，一直由 美国a r g o n n e 国家重点实验室数学与计算机部的s a t i s hb a l a y ，w i l l i a m g r o p p ，l o i sc m c i n n e s ，b a r r ys m i t h 等人维护，目前最新的版本为 p e t s c2 2 1 ；p e t s c 建立在m p i 之上，与m p i 完全兼容，在p e t s c 程序中 可随意调用m p i 函数：具备高性能、可移植和可扩展的优点，已被安装到 目前国际上许多大计算中心的并行平台上，如c r a yt 3 d ，t 3 e ，o r i g i n 2 0 0 0 ，i b ms p ，h pu x ，a s c ir e d ，b l u em o u n t a i n ，n o w s ，l i n u x ，a l p h a 等，最新版还支持w i n d o w s 平台；p e t s c 使用标准c 语言实现了面向对象 的技术分格，使其功能构件的接口较简单，使用也较方便，它通过其设计 的高级的抽象的数据对象v e c ( 向量) 、i s ( i n d e xs e t s ) 、d a ( d i s t r u b u t e d a r r a y ，分布阵列) 、m a t ( 矩阵) 、k s p ( k r y l o v 子空间法) 、s n e s ( s c a l a b l e n o n l i n e a re q u a t i o ns o l v e r ) 等等提供了并行的代数数据结构、求解器等 在提供强大的数值计算能力的同时提供了对用户透明的并行计算能力，用 户如同写串行程序般调用p e t s c 函数，由其完成具体的并行细节，如数据 在内存的布局、通信等等。当然，它也允许用户按自己的需要定制并行实现 的细节。p e t s c 的基本结构如下图所示： 9 _ l 捱扛盅生丝土兰岜监监立一 基壬p e 曲立涵滥盐缸数值撞拉 图l p e t s c 的基本结构 p b t s c 的功能相当强大，利用它 些代码，而让p e t s c 做剩下的 p e t s c 的一般流程： 我们只需编写和应用问题本身相关的一 这大大提高了开发效率；下图是应用 图2 应用p e t s c 的般流程 另外p e t s c 中抽象的数据对象往往有几种不同的底层实现，所以它还提供 了相当强大的运行时选项功能，使得我们能在程序运行时定制诸如大型矩 阵在内存的存储方式、求解代数方程的数值算法和预处理方法等等，无须 更改程序即可实现不同的算法。p e t s c 的缺点是仍需要用户对m p i 有较好的 理解；另外，入门有定的难度。 1 0 4 3并行计算的性能分析和并行程序性能优化 发展并行计算的目的有二：一个是为了算得更快，另一个是为了算得 更大，即为了以更高的精度求解规模更大的问题。据此人们提出了加速比 ( s p e e d u p ) 、负载平衡( 1 0 a d b a l a n c e ) 和可扩展性( s c a l a b i l i t y ) 这三个衡 量一个并行算法或并行程序主要的性能指标。从不同的角度可给加速比下 不同的定义，一个常用的加速比的定义是a m d a h l 给出的：对同一计算任 务，串行计算时间和并行计算时间之比称为加速比：记s 为加速比，n 为 并行计算的处理器数，p 为并行化因子( 程序中并行部分所占比例) ，则 1 s 2 t 二i 靠， 如考虑并行化带来的额外开销，记其为c ，则 s = 1 一p 七p | n 七c 一般情况下，随着c p u 的增加，因并行化而导致的额 外开销也随着增长，使c p u 的有效利用率下降；可扩展性是指个并行算 法或并行程序有效利用不断增加的c p u 的能力：通常，用效率( e ) 来反 c 映可扩展性：e = 景。负载平衡是指将计算任务均衡的分派给各处理器； 因为我们追求的是某个计算任务所需的墙上时间最小化，易知，负载平衡 是必需的；换言之，只有负载平衡，才能使处理器都有效工作。 一个好的并行实现应该是综合考虑应用问题及算法、并行机体系结构和 并行编程环境的结果。首先，从应用问题的层次选择合适的并行化方案： 一方面当然应尽可能充分开发并行性，但另一方面则需分析并行任务在控 制、通信和同步等方面的相互关系一进程之间的拓扑结构，并使其和计算 机系统的拓扑结构相一致，即互相通信或共享数据的进程必须安排得尽可 能相邻，使得个并行任务之间交互的开销控制在合理的范围：其次，从编 程和代码设计的层次主要考虑数据划分及在内存的布局，尽可能满足进程 处理数据的局部性要求。对m p i 程序，每个进程有各自的数据空间，各进 程各自初始化所用的数据，局部性通常能得到满足，但仍可通过使用如改 逝江古堂蚀生位垃室 基壬p e 工5 e 曲交通洫莲征盐壤槿扭 变系统的内存分配方式、调整页面大小以及使用页面的动态迁移( 开销较 大) 等技术来优化性能。 一个进程在不同的阶段受限于不同的系统资源，或c p u 、或内存、或通信、 或i o 等等，为作性能分析采用全程跟踪的方法对于长时间运行的大程序 是不现实的，因为生成的文件巨大，难；玖分析，效率低；在s g i o r i g i n 2 0 0 0 上，我们先利用系统提供的基于静态程序分析和动态采样的 工具( s p e e d s h o p ) 大致确定性能瓶颈所在，然后对于瓶颈所在的局部利用 基于跟踪的工具( s p e e d s h o p ，m p e ) 作仔细的分析，整个过程可分为：1 ) 检查总的机器资源使用情况；2 ) 在试运行的基础上将整个程序的运行分 为若干阶段，确定每阶段性能瓶颈所在；3 ) 对重点关注的局部获得完整 的运行图象；4 ) 调整以优化性能；5 ) 重复以上过程。 1 2 捌疆强a 警址匕型互垃卫一一基土上聪强涵鲨筻遵城韭至蛰盈控篮 第五章算例 以下为针对不围初边僵条件和方程系数的算例。线性方穰组的求解采 躅k r y i o v 予空闽粒g m r e s 法，b 】o c kj a c o b i 秘1 l u ( 0 ) 相结合麓预处瑾技 拳弼，n = 5 0 0 ，m = 8 0 0 ，r t o l = 1 o * e 一1 5 ，a t o l = 1 游e 一5 0 ，计算在s g i o r i g i n 2 0 0 0 上完成。 算例l 对如下具体的方程系数和边界条件 ；( p ) - p ，b ( p ) 一3 0 ，垂 x ，f = o ： 妒x ；= y ，( 羔) = 吉4 吉s 叠( 6 丌x + 吾玎) y 。( x 户i 1 + 丢。o s ( 4 ，v x + r r ) ， 所得结果如下图 算例2 对如下具体的方程系数和边界条件 逝址盘整娅上望缸妊波丝上旺幽蜓出璇韭址抛蜷弛 ( pj 2 p ，q ( p j = 3 0 ， ，h 一05 ) 2 西( 圳= 。东丽e 。”s i n ( 2 r r f ) 啪( x ) = y ( x ) = 丢+ ；s j n ( 6 丌x + 吾丌 y 。( x ) = 昙+ 昙c 。s ( 4 r r x + r r ) i 所得结果如下图 算例3 对如下具体的方程系数和边界条件 ( p ) 2 p ，h ( p ) 2 3 ，0 咖( z ，f ) 2 0 ，? 111 7 咿i x ) = 百+ 百5 1 n 1 3 丌x 一了丌) ， y o 【x ) = y l ( z ) = 10 1 4 逝扛立当删u 掣盟赴虹一一一立日1 ) 上工 ；立姐立扭蓝韭盥监控拙 所得结果如下图 1 og o8 o 7 0 6 0 5 04 0 3 0 2 0 1 o t r a 闹cs t r e a md e n s i t v 逝扛盘堂砸土兰拉监立一一一 基壬e e 工s 曲交通流芷短数值撞拉 参考文献 1 唐孝威，张训生，陆坤权交通流和颗粒流浙江大学出版社：杭州，2 0 0 4 2 k i n z e rjp a p p i c a t i o no ft h et h e o r yo fp r o b a b i l i t yt op r o b l e m so f h i g h w a y t r a f f i c bcet h e s i s ，p o l y t e c h n i c i n s t i t u t eo f b r o o k l y n ( j u l y ，11 9 3 3 ) t r a f f i ce n g ，5 ，1 1 8 - 1 2 4 3 l i g h t h i l lmj w h i t h a mgb o nk i n e m a t i cw a v e s ：p ti f l o w m o v e m e n ti nl o n gr i v e r s ：i i a t h e o r yo ft r a f f i cf l o w o n l o n g c r o w d e dr o a d p r o or o ys o co fl o n d o na ，1 9 5 5 ，2 2 9 ：2 8 1 3 1 6 4 l i g h t h il lmj w h i t h a mgb o nk i n e m a t i cw a v e s ：p ti i at h e o r yo f t r a f f i cf 1 0 wo nl o n gc r o w d e dr o a d p r o e r o ys o co fl o n d o na 1 9 5 5 ，2 2 9 ：3 1 7 - 3 4 5 5 n a g e lk ，s c h r e c k e n b e r gm ac e l u l a ra u t o m a t o nm o d e lf o rf r e e w a y t r a f f i c jp h y si 1 9 9 2 ，2 ：2 2 2 i 6 t h o m p s o n t h e r e a l m y s t e r yo fn a t u r e ：w h a tc a u s e st r a f f ic a m s ? f r o m c o l dw a rt o c l o g g e dh i g h w a y i n t e r n a t i o n a lh e r a l dt r i b u n e 1 9 9 9 ，8 ：6 - 8 7 r a j k u m a rb u y y a h i g hp e r f o r m a n c ec l u s t e rc o m p u t i n gp r o g r m n m i n ga n d a p p l i c a t i o n s ，v o l u m e2 p r e n t i c e h a l l ，i n c 1 9 9 9 8 k a ih w a n g ，z h iw e ix u s c a l a b l ep a r a l l e l c o m p u t i n gt e c h n o l o g y a r c h e t e c t u r e ，p r o g r a m m i n g m c g r a w h i1l ，1 9 9 8 9 h j s i e g e l e t a 1 r e p o r to ft h ep u r d u ew o r k s h o po ng r a n dc h a l l e n g e s i nc o m p u t e ra r c h i t e c t u r ef o rt h e s u p p o r to fh i g hp e r f o r m a n c e c o m p u t i n g j p a r a l l e la n dd i s t r i b u t e dc o m p u t i n g ，v o 1 6 ，n o 3 1 9 9 2 1 0 t r a f f i cf l o wt h e o r y h p ：z m 卫生h r ：g q y z i s z f ! z f ：h 班 11 d e b a s h i s h c h o w d h u r y，l u d g e rs a n t e n ， a n d r e a s s c h a d s c h n e i d e r s t a t i s t i c a tp h y s i c so fv e h i c u l a rt r a f f i ca n ds o m er e l a t e ds y s t e m s p h y s i c sr e p o r t s3 2 9 ，1 9 9 ( 2 0 0 0 ) 1 2 李立康，於崇华，朱政华微分方程数值解法复旦大学出版社：上海， 1 9 9 9 1 3 刘儒勋，舒其望，计算流体力学的若干新方法科学出版社：北京，2 0 0 3 1 4 张宗琳，谷同祥，莫则尧数值并行计算原理与方法国防_ t 业出版社：北 京，1 9 9 9 1 5 蔡大用，白峰杉现代科学计算科学出版社：北京，2 0 0 0 1 6 h t t p ：w w w - u n i x m c s a n l g o v p e t s c p e t s c 一2 1 6 蚯江太堂熊土望芷业主 基壬p s 曲空通泣挂生i 敛值撞拉 致谢 本文在导师陈叔平教授指导下完成。首先，非常感谢陈老师支 持我自由选择做自己感兴趣的研究课题，这充分体现了他作为一个 学者所具有的宽大的胸襟和长远的目光；其次，陈老师勤奋踏实的 。? 工作作风，严谨的治学态度和活跃的学术思维，使我收益非浅。在 此谨向陈老师致以崇高的敬意和诚挚的谢意! 因为我是在职念书，各方压力稍大一些，我十分感谢我的家人 对我的理解和支持，尽其所能给我创造条件以便我安心_ t - 作和学习。 在此我还应向他们致歉，尤其是向我的女儿，本来她应该得到我更 多的关心和陪伴的。谨向所有关心我、支持我的亲a 4 l 致敬! 还应该感谢许多关心、帮助我的老师和朋友们，如复旦大学的 谭永基教授、本校的郑耀教授等，感谢他们多年来对我一如继往的 关心和帮助，谨向他们表达我诚挚的谢意! 最后，感谢美国a n l 实验室p e t s c 研究组给我的帮助。他们的 敬业精神和无私品格值得我学习。 2 0 0 5 年3 月于浙大玉泉 施扛盘堂蚀土堂垃谊立基王旺工s 的立趟近盘扛煎擅搓扭 附录源程序 s t a t i cc h a rh e l p = ”。 # i n c l u d e ”p ph ” # i n c l u d e ”g e t mc # i n c l u d e “g e t v , c # i n c l u d e ”m i nc # u n d e ff u n c t # d e f i n e f u n c t”m a i n ” i n tm a t t a i n i t ( v o i d ) ； i n tm a t t c i n i t ( v o i d ) ； i n tg e t v r ( v e c i n t v e c + ) ： i n tg e t v a ( v e c v e c 。) ： i n tg e t v b ( v e c v e c + ) ： i n tg e t m a t ( v e c ，v e c ，p e t s c s c a l a r p e t s c s c a l a r + ) i n ts p r i n t x ( v e c c h a r + ) ： n tm a i n ( i n ta r g c ，c h a r ”a r g v ) i n ti j ，i s t a r t ，l e n d r s t a r t ，r e n d ，i o c r o w _ d i m i n ti o c _ s i z e i t s ； p e t s c r e a in o r m ： p e t s c l n i t i a l i z e ( & a r g c & a r g v , ( c h a r + ) 0 ，h e l p ) i e r r = m p i _ c o m m r a n k ( p e t s c _ c o m m w o r l d ，& r a n k ) ；c h k e r r q ( i e r r ) ； j e r r = m p i c o m m _ s i z e ( p e t s c c o m m _ w o r l d ，& n p r o c ) ；c h k e r r q ( i e r r ) i e r r = p e t s c o p t i o n s g e t i n t ( p e t s c n u l l ，”- n “ i e r r = p e t s c o p t i o n s g e t i n t p e t s c n u l l ”- m h = ( x e n d - x s t a r t ) n ； t a u = ( t e n d t s t a r t ) t m ； r ：t a 山( ”h ) ： & n ，p e t s c n u l l ) ：c h k e r r q ( 1 e r r ) ： m p e t s c n u l l ) ；c h k e r r q ( i e r r ) i f ( r a n k = = n p r o c 一1 ) p r i n t f ( ”h ：f , t a u = fr = f 、n h ，t a u ，r ) ： i f ( r a n k = = n p r o c 一1 ) p r i n t f ( ”o n e = f ，z e r o = f 、r l , o n e z e r o ) ； i e r r = m a t c r e a t e m p i a i j ( p e t s c c o m m w o r l d p e t s c d e c i d e p e t s c d e c i d e n - 1 n - 1 3 ，p e t s cn u l l 0 p e t s ( ；n u l l a ) ：c h k e r r q ( i e r r ) ： i e r r = m a t s e t f r o m o p t i o n s ( a ) ；c h k e r r q ( i e r r ) ； m a t t a i n i t 0 ； i e r r = m a t s e t o p t i o n ( a ，m a t - n o n e v v _ n o n z e r o _ l o c a t i o n s ) ；c h k e r r q ( i e r r ) ； 逝扛主爨灏土拦拉监望j 电置e e 工s 的变捌洫燕缸数擅摸挝 i e r r = m a l g e l o w n e r s h i p r a n g e ( a & r s t a r t ，r e n d ) ：c h k e r r 0 ( i e r n l o c r o w d i m = r e n d r s t a r t ； i e r r = v e c c r e a t e ( p e t s cc o m m _ w o r l d & a i p ) ：c h k e r r q ( i e r r ) i e r r = v e c s e t s i z e s ( a l p ，i o c _ r o wd i m n 一1 ) ：c h k e r r q ( i e r r ) ： i e r r = v e c s e t f r o m o p t l o n s f 穗l p l c h l ( e r 歉q i e 啊： e r r = v e c d u p l i c a t e ( a l p & b e i ) ：c h k e r r q ( i e r r k i e r r = v e c d u p l i c a t e ( a l p ，& p h x e h k e r r q i e r 吩： i e r r = v e c d u p l i c a t e ( a l p ，& x ) ；c h k e r r q ( i e r r ) ； i e r r = v e c d u p l i c a t e ( x ，b ) i c h k e r r q ( i e r 一： i e r r = v e c g e t o w n e r s h i p r a n g e ( x ，& l s t a r t ，l e n 堪；：e 鞭k r r q i e 徉； i e r r = v e c g e t l o c a i s i z e ( x ，& l o cs i z e ) ；c h k e r r q ( i e r r ) ； i f ( r a n k = = o ) p e t s c s c a l a rt m p ； f o r ( i = 0 ；i n - 1 ：i + + ) t m p = p s i ( x s t a r t + ( i + l + ： i e r r = v e c s e t v a l u e s ( x ，1 ，i & t r a p ，i n s e r t v a l u e s ) ：c h k e r r q