基于MPI的并行最大最小蚂蚁系统
基于MPI 的并行最大最小蚂蚁系统
刘彩云a ，陈 忠a ，熊 杰b
(长江大学 a. 信息与数学学院；b. 电子信息学院，湖北 荆州 434023)
摘 要：现有蚁群系统在求解大规模组合优化问题时所需的计算时间较长。针对该不足，提出基于消息传递接口的粗粒度异步协作并行最大最小蚂蚁系统，能在保证解质量的前提下，降低并行计算中的通信开销。在曙光4000L 并行机上进行的数值实验结果表明，该系统具有较优的并行加速比和加速效率，且适合于大规模TSP 问题的求解。
关键词：并行最大最小蚂蚁系统；消息传递接口；部分异步并行实现；粗粒度；多蚁群协作
Parallel Max-Min Ant System Based on MPI
LIU Cai-yun a , CHEN Zhong a , XIONG Jie b
(a. School of Information and Mathematics; b. School of Electronics and Information, Yangtze University, Jingzhou 434023, China)
【Abstract 】Existing Colony system for the large scale optimization combination problem needs long computation time. Aiming at this shortage, this paper presents coarse grained asynchronous parallel implementation Parallel Max-Min Ant System(PMMAS) based on Message Passing Interface(MPI) which can reduce the cost of communication of parallel computation and guarantee the quality of solution. Numerical experiment result which is obtained on the dawn 4000L parallel computer indicates that the system has well speedup and speedup efficiency, and it is suitable for large-scale under the prerequisite of solving Traveling Salesman Problem(TSP).
【Key words 】Parallel Max-Min Ant System(PMMAS); Message Passing Interface(MPI); Partially Asynchronous Parallel Implementation(PAPI); coarse grained; multi-ant colony collaboration
计 算 机 工 程 Computer Engineering 第36卷 第19期
Vol.36 No.19 2010年10月
October 2010
·人工智能及识别技术·
文章编号：1000—3428(2010)19—0200—03
文献标识码：A
中图分类号：TP301
1 概述
蚁群优化算法是一种基于真实蚁群行为的新型仿生类算法[1]。最早由Dorigo M 等人提出，并且成功用于求解旅行商问题(Traveling Salesman Problem, TSP)问题、二次分配问题、网格划分问题、蛋白质折叠问题、Web 页面分类问题、路径优化问题[2]以及其他组合优化问题。蚁群算法能在迭代若干代后，收敛到几乎最优的解，但是当求解大规模的组合优化问题时，和其他优化算法一样存在求解时间过长的问题。并行化是提高求解速度的有效手段之一。消息传递接口(Message Passing Interface, MPI)是目前最为广泛使用的并行计算开发环境，本文将设计基于MPI 的并行蚁群优化系统。蚁群优化算法是一个算法家族，包括基本蚁群算法——蚂蚁系统(Ant System, AS)[3]及其众多改进算法。到目前为止，性能最好的是蚁群系统(Ant Colony System, ACS)[3]和最大最小蚂蚁系统(Max-Min Ant System, MMAS)[4]。本文选取MMAS 作为并行最大最小蚂蚁系统(Parallel Max-Min Ant System, PMMAS)的基础。
2 并行最大最小蚂蚁系统
2.1 并行蚁群划分策略
本文给出蚁群划分策略。在并行粒度选择方面，根据文献[5-8]的研究，粗粒度的并行策略更有效，因为这种策略能减少通信时间，从而获得较优的加速比和加速效率。本文采用粗粒度的并行策略，即为每个处理器分配多只蚂蚁，进行并行计算。在蚂蚁协作策略方面，将同一个处理器上的多只蚂蚁，看作一个独立的蚁群，它们拥有完整信息，包括信息素矩阵、距离矩阵、迭代最优解、t max 、t min 等。同一个处理器上的子蚁群，在本地信息的指导下独立构造解。不同子蚁群间(即不同处理器间)，通过信息交换的方法进行协作。将这种蚁群划分策略称为粗粒度多蚁群策略。
2.2 信息交换频率
根据信息交换频率的不同，并行算法主要有同步和部分异步2种实现模型。文献[5,9]的研究结果表明，部分异步并行实现模型更有效。因此，本文采用部分异步并行实现(Part Asynchronous Parallel Implementation, PAPI)的方式，让各个蚁群每隔固定的迭代次数进行一次信息交换。各个计算节点在新的信息素矩阵的基础上，继续开始下一轮计算。采用PAPI 方式，能减少网络中传递的信息次数，从而降低通信时间开销。
2.3 信息交换算法
按PAPI 蚁群每隔固定迭代次数需进行一次信息交换。常见的信息交换算法是主节点收集各从节点的本地解和本地信息素矩阵，从中选出得到目前最优解的节点，再将该节点的本地解和本地信息素矩阵广播给各从节点。对于大规模优化问题，信息素矩阵巨大(空间复杂度2()O n )，常规信息交换方法每次需广播2次信息素矩阵，因此通信时间开销很大。
为提高信息交换效率，本文设计一种新的信息交换算法。
基金项目：国家自然科学基金资助项目“基准面旋回理论解析与定量层序地层模型”(40572078)；国家“118”专项基金资助子项目“天然气水合物资源综合评价软件研制与开发”(GZH200200202-3) 作者简介：刘彩云(1975－)，女，副教授、硕士，主研方向：并行计算；陈 忠，教授、博士；熊 杰，讲师、硕士
收稿日期：2010-04-21 E-mail ：Liucaiyun01@https://www.sodocs.net/doc/a810877670.html,
首先主节点收集各从节点的本地解；然后主节点选出得到目前最优解的从节点，并将该从节点号广播给各从节点；最后由得到目前最优解的从节点将本地解和本地信息素矩阵广播给其他从节点。本信息交换算法每次只需广播一次信息素矩阵，能很好地降低通信时间开销。
2.4 系统实现
下文给出主节点(算法1)和从节点(算法2)的并行最大最小蚁群系统。
算法1(主节点算法)
步骤1 读取用户参数seed
βγρ
、、、，初始化信息素矩阵和距离矩阵；
步骤2广播seed
βγρ
、、、，信息素矩阵、距离矩阵和城市数N到各节点；
步骤3如果不满足算法结束条件，则反复执行步骤4~步骤9，否则退出算法；
步骤4按照2.1节所述粗粒度多蚁群策略，划分蚁群，并随机平均分配蚂蚁到各个城市；
步骤5 按照MMAS，本地迭代N次求解；
步骤6 收集各个节点的求解结果；
步骤7 根据2.3节信息交换算法，与各从节点交换信息；
步骤8 收集各个节点的结束标志，计算全局结束标志，并广播给各个节点；
步骤9 转步骤3，开始下一次循环。
算法2(从节点算法)
步骤1 接收主节点广播的seed
βγρ
、、、，信息素矩阵、距离矩阵和城市数N；
步骤2 如果不满足算法结束条件，则反复执行步骤3~步骤7，否则退出算法；
步骤3 随机平均分配蚂蚁到各个城市；
步骤4 按照MMAS，本地迭代N代求解；
步骤5 根据2.3节信息交换算法，与主节点交换信息；
步骤6 发送本地结束标志给主节点，并接收全局结束标志；
步骤7 转步骤2，开始下一次循环。
3 数值实验结果与分析
硬件平台是曙光天潮4000L并行机，软件环境是Linux+ MPI+C。利用MPI函数库，编写C语言程序，实现本文提出的并行最大最小蚂蚁系统。通过实验研究实例规模、计算节点数对本文设计的并行最大最小蚂蚁系统性能的影响。
3.1 评价指标与评价方案
本文主要从2个方面考察并行最大最小蚂蚁系统：
(1)是否适用于所有规模的TSP问题的求解；
(2)在不同数量的计算节点并行计算时，是否同样高效。
本文设计如下2个评价方案：
(1)固定采用2个节点并行计算，分别以不同规模的经典TSP实例，运行串行MMAS(Serial MMAS, SMMAS)和PMMAS，测试PMMAS的并行性能；
(2)以同一个经典TSP为例，分别采用2个、4个、8个、16个节点进行并行计算，测试PMMAS的在不同计算节点并行计算时的性能。
3.2 参数设置
本文将PMMAS用于求解各种经典TSP实例[10]，主要参数设置为α=1、β=2、ρ=0.2、m=25、t0=1/ρC nn，其中，α、β分别为信息素影响因子和启发信息影响因子；ρ为信息素的蒸发率；m、n分别为蚂蚁数和城市数；t0为信息素初始值；
nn
C表示由最近邻启发式方法构造的路径长度。
信息素大小被限制在
max
1/bs
t C
ρ
=
到
min max
(1/
t t=
((avg?之间，其中，avg是每只蚂蚁在构建解的每一步中面临的不同选择的平均个数。
3.3 实验结果
(1)实例规模对并行性能的影响
利用2个节点对不同规模的TSP实例进行求解，为了在同等计算条件下对比SMMAS与PMMAS的性能，实验中将2种算法的最大执行时间设为相同。现将PMMAS、SMMAS 算法对不同实例重复运行20次，实验结果见表1所示。其中，max
t表示最大运行执行时间；
avg
t为求得的最优解平均计算时
间；
avg
i为平均迭代次数。
表1 SMMAS、PMMAS求解TSP的结果比较实例算法平均值t max/s t avg/s i avg平均误差/(%)
PMMAS15 781.120 6.34 370.70 0.000 07 D198
SMMAS15 780.020 5.53 574.00 0.000 00
PMMAS294 546.0100 42.53 762.80 0.063 90 Gr666
SMMAS294 422.1100 56.95 1 647.350.021 80
PMMAS56 906.0200 87.26 895.80 0.024 60
Pcb1173
SMMAS56 909.4200 126.89 1 895.250.030 60
PMMAS22 320.4400 140.89 1 107.200.320 90 fl1577
SMMAS22 323.1400 234.14 3 288.550.333 00
PMMAS378 821.3 1 000 421.65 1 661.850.208 80 pr2392
SMMAS378 823.0 1 000 750.57 4 359.100.209 20
PMMAS569 388.6 2 000 957.83 705.50 0.682 30 rl5915
SMMAS569 668.6 2 000 1 733.94 2 082.900.731 80
(2)计算节点数对并行性能的影响
以fl1577实例为例，分别采用2个、4个、8个、16个节点进行计算，重复运行20次，实验结果见表2。
表2 采用不同计算节点数求解TSP的结果比较实例节点数t avg/s 平均误差/(%) 加速比加速效率
1 234.14 0.333 1.000 0 1.000 0
2 140.89 0.33
3 1.661 9 0.830 9
4 102.4 0.32
5 2.28
6 5 0.571 6
8 86.63 0.318 2.702 8 0.337 8
fl1577
16 79.38 0.346 2.949 6 0.184 4 3.4 结果分析
本文利用表2，计算出加速比、加速效率，得到加速比与实例规模的关系(见图1)
、加速效率与实例规模的关系(见图2)。由图1、图2可以看出，对于固定2个节点参与计算，加速比、加速效率均随实例规模的增长逐渐提高。对于大型实例规模的求解(如rl5915)，加速比接近于上限2，加速效率接近于上限1。结果表明本文所设计的算法更适合于大规模的TSP问题的求解。
2.0
1.6
1.2
0.0
0.8
0.4
D198Gr666Pcb1173pr2932rl5915
fl1577
加
速
比
实例规模
图1 加速比与实例规模的关系
图2 加速效率与实例规模的关系
根据表3，得到加速比与计算节点数的关系(见图3)，加
速效率与计算节点数的关系(见图4)。
图3 加速比与计算节点数的关系
图4 加速效率与计算节点数的关系
由图3、图4可以看到，随着计算节点数的增加，加速
比单调上升，但增长速度逐渐减慢；加速效率单调下降，但
下降速度逐渐减慢。可见，更多节点参与计算，虽然能提高
求解速度，获得较好的加速比，但加速效率却不理想。通过
分析可知，这是因为更多节点参与计算，虽然能带来更强的
计算能力，但也会导致通信开销逐步增大。因此，不断的增
加计算节点，并不一定总能获得理想的加速效果，需要综合
考虑加速比和加速效率2个因素，以获得满意的加速效果。
4 结束语
本文采用并行蚁群划分策略、信息交换频率和信息交换
算法，提出一种新的并行最大最小蚂蚁系统。通过数值实验
研究了实例规模、计算节点数对并行性能的影响。实验结果
表明，该系统在适当的并行规模(计算节点数)下求解TSP问
题，能显著加快求解速度。
参考文献
[1] Colomi A, Dorigo M, Maniezzo V. Distributed Optimization by Ant
Colonies[C]//Proc. of European Conference on Artificial Life. Paris,
France: [s. n.], 1991.
[2] 王罡, 冯艳君. 基于蚁群优化算法的旋转货架拣选路径规
划[J]. 计算机工程, 2010, 36(3): 221-223.
[3] Dorigo M, Grambardella L M. Ant Colony System: A Cooperative
Learning Approach to the Traveling Salesman Problem[J]. IEEE
Transactions on Evolutionary Computation, 1997, 1(1): 53-56.
[4] Stutzle T, Hoos H. MAX-MIN Ant System and Local Search for the
Traveling Salesman Problem[C]//Proc. of International Conference
on Evolutionary Computation. Indianapolis, USA: IEEE Press,
1997.
[5] Bullnheimer B, Kotsis G, Strauss C. Parallelization Strategies for the
Ant System[C]//Proc. of Conference on High Performance Software
for Nonlinear Optimization: Status and Perspectives. Ischia, Italy:
[s. n.], 1997.
[6] Stutzle T. Parallelization Strategies for Ant Colony Optimization[C]//
Proc. of the 5th International Conference on Parallel Problem
Solving From Nature. London, UK: Springer-Verlag, 1998.
[7] Manfrin M. Parallel Ant Colony Optimization for the Traveling
Salesman Problem[C]//Proc. of ANTS’06. Brussels, Belgium: [s. n.],
2006.
[8] Benkner S. Communication Strategies for Parallel Cooperative Ant
Colony Optimization on Cluster and Grids[C]//Proc. of PARA’04
Workshop on State-of-the-art in Scientific Computing. Lyngby,
Denmark: [s. n.], 2004.
[9] Middendorf M, Reischel F, Schmeck H. Multi Colony Ant
Algorithm[J]. Journal of Heuristics, 2002, 8(3): 305-320.
[10] Ruprecht-Karls-Universitat-Heidelberg. TSPLIB[EB/OL]. [2009-
11-22]. http://www.iwr.uni-heidelberg.de/groups/comopt/software/
TSPLIB95.
编辑陆燕菲
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ （上接第199页）
参考文献
[1] Loy G, Barnes N. Fast Shape-based Road Sign Detection for a
Driver Assistance System[C]//Proc. of IEEE International
Conference on Intelligent Robots and Systems. Nice, France: IEEE
Press, 2004: 70-75.
[2] Cyganek B L. Road-signs Recognition System for Intelligent
Vehicles[C]//Proc. of the 2nd International Workshop on Robot
Vision. Auckland, New Zealand: [s. n.], 2008: 219-233.
[3] Jun-Taek O. Segmentation and Recognition of Traffic Signs Using
Shape Information[C]//Proc. of ISVC’05. Lake Tahoe, Nevada,
USA: [s. n.], 2005: 519-526.
[4] 黎海兵, 易卫东. 一种高效检测图像中是否有三角形的算法[J].
中国图象图形学报, 2008, 13(6): 456-460.
[5] Loy G, Zelinsky A. Fast Radial Symmetry for Detecting Points of
Interest[J]. IEEE Trans. on Pattern Analysis and Machine
Intelligence, 2003, 25(8): 959-973.
[6] Duda R, Hart P. Use of the Hough Transform to Detect Lines and
Curves in Pictures[J]. Communications of the ACM, 1972, 15(1):
11-15.
[7] Bascon S M. Road-sign Detection and Recognition Based on
Support Vector Machines[J]. IEEE Trans. on Intelligent Transport-
ation Systems, 2007, 8(2): 264-278.
编辑金胡考
并行计算1
并行计算 实 验 报 告 学院名称计算机科学与技术学院专业计算机科学与技术 学生姓名 学号 年班级 2016年5 月20 日
一、实验内容 本次试验的主要内容为采用多线程的方法计算pi的值，熟悉linux下pthread 形式的多线程编程，对实验结果进行统计并分析以及加速比曲线分析，从而对并行计算有初步了解。 二、实验原理 本次实验利用中值积分定理计算pi的值 图1 中值定理计算pi 其中公式可以变换如下： 图2 积分计算pi公式的变形 当N足够大时，可以足够逼近pi，多线程的计算方法主要通过将for循环的计算过程分到几个线程中去，每次计算都要更新sum的值，为避免一个线程更新sum 值后，另一个线程仍读到旧的值，所以每个线程计算自己的部分，最后相加。三、程序流程图 程序主体部分流程图如下：
多线程执行函数流程图如下： 四、实验结果及分析
令线程数分别为1、2、5、10、20、30、40、50和100，并且对于每次实验重复十次求平均值。结果如下： 图5 时间随线程的变化 实验加速比曲线的计算公式类似于 结果如下： 图5 加速比曲线 实验结果与预期类似，当线程总数较少时，线程数的增多会对程序计算速度带来明显的提升，当线程总数增大到足够大时，由于物理节点的核心数是有限的，因此会给cpu带来较多的调度，线程的切换和最后结果的汇总带来的时间开销较大，所以线程数较大时，增加线程数不会带来明显的速度提升，甚至可能下降。 五、实验总结
本次试验的主要内容是多线程计算pi的实现，通过这次实验，我对并行计算有了进一步的理解。上学期的操作系统课程中，已经做过相似的题目，因此程序主体部分相似。不同的地方在于，首先本程序按照老师要求应在命令行提供参数，而非将数值写定在程序里，其次是程序不是在自己的电脑上运行，而是通过ssh和批处理脚本等登录到远程服务器提交任务执行。 在运行方面，因为对批处理任务不够熟悉，出现了提交任务无结果的情况，原因在于windows系统要采用换行的方式来表明结束。在实验过程中也遇到了其他问题，大多还是来自于经验的缺乏。 在分析实验结果方面，因为自己是第一次分析多线程程序的加速比，因此比较生疏，参考网上资料和ppt后分析得出结果。 从自己遇到的问题来看，自己对批处理的理解和认识还比较有限，经过本次实验，我对并行计算的理解有了进一步的提高，也意识到了自己存在的一些问题。 六、程序代码及部署 程序源代码见cpp文件 部署说明： 使用gcc编译即可，编译时加上-pthread参数，运行时任务提交到服务器上。 编译命令如下： gcc -pthread PI_3013216011.cpp -o pi pbs脚本(runPI.pbs)如下： #!/bin/bash #PBS -N pi #PBS -l nodes=1:ppn=8 #PBS -q AM016_queue #PBS -j oe cd $PBS_O_WORKDIR for ((i=1;i<=10;i++)) do ./pi num_threads N >> runPI.log
并行计算实验报告一
江苏科技大学 计算机科学与工程学院 实验报告 实验名称：Java多线程编程 学号：姓名：班级： 完成日期：2014年04月22日
1.1 实验目的 (1) 掌握多线程编程的特点； (2) 了解线程的调度和执行过程； (3)掌握资源共享访问的实现方法。 1.2 知识要点 1.2.1线程的概念 (1)线程是程序中的一个执行流,多线程则指多个执行流; (2)线程是比进程更小的执行单位,一个进程包括多个线程; (3)Java语言中线程包括3部分:虚拟CPU、该CPU执行的代码及代码所操作的数据。 (4)Java代码可以为不同线程共享，数据也可以为不同线程共享； 1.2.2 线程的创建 (1) 方式1：实现Runnable接口 Thread类使用一个实现Runnable接口的实例对象作为其构造方法的参数，该对象提供了run方法，启动Thread将执行该run方法； (2)方式2：继承Thread类 重写Thread类的run方法； 1.2.3 线程的调度 (1) 线程的优先级 ●取值范围1～10，在Thread类提供了3个常量，MIN_PRIORITY=1、MAX_ PRIORITY=10、NORM_PRIORITY=5； ●用setPriority()设置线程优先级，用getPriority()获取线程优先级； ●子线程继承父线程的优先级，主线程具有正常优先级。 (2) 线程的调度：采用抢占式调度策略，高优先级的线程优先执行，在Java中，系统按照优先级的级别设置不同的等待队列。 1.2.4 线程的状态与生命周期
说明：新创建的线程处于“新建状态”，必须通过执行start()方法，让其进入到“就绪状态”，处于就绪状态的线程才有机会得到调度执行。线程在运行时也可能因资源等待或主动睡眠而放弃运行,进入“阻塞状态”,线程执行完毕，或主动执行stop方法将进入“终止状态”。 1.2.5 线程的同步--解决资源访问冲突问题 (1) 对象的加锁 所有被共享访问的数据及访问代码必须作为临界区，用synchronized加锁。对象的同步代码的执行过程如图14-2所示。 synchronized关键字的使用方法有两种： ●用在对象前面限制一段代码的执行，表示执行该段代码必须取得对象锁。 ●在方法前面，表示该方法为同步方法,执行该方法必须取得对象锁。 (2) wait()和notify()方法 用于解决多线程中对资源的访问控制问题。 ●wait()方法：释放对象锁，将线程进入等待唤醒队列； ●notify()方法：唤醒等待资源锁的线程，让其进入对象锁的获取等待队列。 (3)避免死锁 指多个线程相互等待对方释放持有的锁，并且在得到对方锁之前不会释放自己的锁。 1.3 上机测试下列程序 样例1：利用多线程编程编写一个龟兔赛跑程序。 乌龟：速度慢，休息时间短；
计算方法上机实验报告
《计算方法》上机实验报告 班级：XXXXXX 小组成员：XXXXXXX XXXXXXX XXXXXXX XXXXXXX 任课教师：XXX 二〇一八年五月二十五日
前言 通过进行多次的上机实验，我们结合课本上的内容以及老师对我们的指导，能够较为熟练地掌握Newton 迭代法、Jacobi 迭代法、Gauss-Seidel 迭代法、Newton 插值法、Lagrange 插值法和Gauss 求积公式等六种算法的原理和使用方法，并参考课本例题进行了MATLAB 程序的编写。 以下为本次上机实验报告，按照实验内容共分为六部分。 实验一： 一、实验名称及题目： Newton 迭代法 例2.7(P38):应用Newton 迭代法求 在 附近的数值解 ，并使其满足 . 二、解题思路： 设'x 是0)(=x f 的根,选取0x 作为'x 初始近似值,过点())(,00x f x 做曲线)(x f y =的切线L ,L 的方程为))((')(000x x x f x f y -+=,求出L 与x 轴交点的横坐标) (') (0001x f x f x x - =,称1x 为'x 的一次近似值,过点))(,(11x f x 做曲线)(x f y =的切线,求该切线与x 轴的横坐标) (') (1112x f x f x x - =称2x 为'x
的二次近似值,重复以上过程,得'x 的近似值序列{}n x ,把 ) (') (1n n n n x f x f x x - =+称为'x 的1+n 次近似值，这种求解方法就是牛顿迭代法。 三、Matlab 程序代码： function newton_iteration(x0,tol) syms z %定义自变量 format long %定义精度 f=z*z*z-z-1; f1=diff(f);%求导 y=subs(f,z,x0); y1=subs(f1,z,x0);%向函数中代值 x1=x0-y/y1; k=1; while abs(x1-x0)>=tol x0=x1; y=subs(f,z,x0); y1=subs(f1,z,x0); x1=x0-y/y1;k=k+1; end x=double(x1) K 四、运行结果： 实验二：
进程管理实验报告
进程的控制 1 ．实验目的 通过进程的创建、撤消和运行加深对进程概念和进程并发执行的理解，明确进程与程序之间的区别。 【答：进程概念和程序概念最大的不同之处在于： (1)进程是动态的，而程序是静态的。 (2)进程有一定的生命期，而程序是指令的集合，本身无“运动”的含义。没有建立进程的程序不能作为1个独立单位得到操作系统的认可。 (3)1个程序可以对应多个进程，但1个进程只能对应1个程序。进程和程序的关系犹如演出和剧本的关系。 (4)进程和程序的组成不同。从静态角度看，进程由程序、数据和进程控制块（PCB）三部分组成。而程序是一组有序的指令集合。】2 ．实验内容 (1) 了解系统调用fork()、execvp()和wait()的功能和实现过程。 (2) 编写一段程序，使用系统调用fork()来创建两个子进程，并由父进程重复显示字符串“parent:”和自己的标识数，而子进程则重复显示字符串“child:”和自己的标识数。 (3) 编写一段程序，使用系统调用fork()来创建一个子进程。子进程通过系统调用execvp()更换自己的执行代码，新的代码显示“new
program.”。而父进程则调用wait()等待子进程结束，并在子进程结束后显示子进程的标识符，然后正常结束。 3 ．实验步骤 （1）gedit创建进程1.c （2）使用gcc 1.c -o 1编译并./1运行程序1.c #include
蚁群算法
蚁群算法报告及代码 一、狼群算法 狼群算法是基于狼群群体智能,模拟狼群捕食行为及其猎物分配方式,抽象出游走、召唤、围攻3种智能行为以及“胜者为王”的头狼产生规则和“强者生存”的狼群更新机制,提出一种新的群体智能算法。 算法采用基于人工狼主体的自下而上的设计方法和基 于职责分工的协作式搜索路径结构。如图1所示,通过狼群个体对猎物气味、环境信息的探知、人工狼相互间信息的共享和交互以及人工狼基于自身职责的个体行为决策最终实现了狼群捕猎的全过程。 二、布谷鸟算法 布谷鸟算法 布谷鸟搜索算法,也叫杜鹃搜索,是一种新兴启发算法CS 算法，通过模拟某些种属布谷鸟的寄生育雏来有效地求解最优化问题的算法.同时，CS 也采用相关的Levy 飞行搜索机制 蚁群算法介绍及其源代码。 具有的优点：全局搜索能力强、选用参数少、搜索路径优、多目标问题求解能力强，以及很好的通用性、鲁棒性。 应用领域：项目调度、工程优化问题、求解置换流水车间调度和计算智能 三、差分算法 差分算法主要用于求解连续变量的全局优化问题，其主要工作步骤与其他进化算法基本一致，主要包括变异、交叉、选择三种操作。 算法的基本思想是从某一随机产生的初始群体开始，利用从种群中随机选取的两个个体
的差向量作为第三个个体的随机变化源，将差向量加权后按照一定的规则与第三个个体求和而产生变异个体，该操作称为变异。然后，变异个体与某个预先决定的目标个体进行参数混合，生成试验个体，这一过程称之为交叉。如果试验个体的适应度值优于目标个体的适应度值，则在下一代中试验个体取代目标个体，否则目标个体仍保存下来，该操作称为选择。在每一代的进化过程中，每一个体矢量作为目标个体一次，算法通过不断地迭代计算，保留优良个体，淘汰劣质个体，引导搜索过程向全局最优解逼近。 四、免疫算法 免疫算法是一种具有生成+检测的迭代过程的搜索算法。从理论上分析，迭代过程中，在保留上一代最佳个体的前提下，遗传算法是全局收敛的。 五、人工蜂群算法 人工蜂群算法是模仿蜜蜂行为提出的一种优化方法，是集群智能思想的一个具体应用，它的主要特点是不需要了解问题的特殊信息，只需要对问题进行优劣的比较，通过各人工蜂个体的局部寻优行为，最终在群体中使全局最优值突现出来，有着较快的收敛速度。为了解决多变量函数优化问题，科学家提出了人工蜂群算法ABC模型。 六、万有引力算法 万有引力算法是一种基于万有引力定律和牛顿第二定律的种群优化算法。该算法通过种群的粒子位置移动来寻找最优解，即随着算法的循环，粒子靠它们之间的万有引力在搜索空间内不断运动，当粒子移动到最优位置时，最优解便找到了。 GSA即引力搜索算法，是一种优化算法的基础上的重力和质量相互作用的算法。GSA 的机制是基于宇宙万有引力定律中两个质量的相互作用。 七、萤火虫算法 萤火虫算法源于模拟自然界萤火虫在晚上的群聚活动的自然现象而提出的，在萤火虫的群聚活动中，每只萤火虫通过散发荧光素与同伴进行寻觅食物以及求偶等信息交流。一般来说，荧光素越亮的萤火虫其号召力也就越强，最终会出现很多萤火虫聚集在一些荧光素较亮的萤火虫周围。人工萤火虫算法就是根据这种现象而提出的一种新型的仿生群智能优化算法。在人工萤火虫群优化算法中，每只萤火虫被视为解空间的一个解，萤火虫种群作为初始解随机的分布在搜索空间中，然后根据自然界萤火虫的移动方式进行解空间中每只萤火虫的移动。通过每一代的移动，最终使的萤火虫聚集到较好的萤火虫周围，也即是找到多个极值
多核编程与并行计算实验报告 (1)
(此文档为word格式，下载后您可任意编辑修改！) 多核编程与并行计算实验报告 姓名： 日期：2014年 4月20日
实验一 // exa1.cpp : Defines the entry point for the console application. // #include"stdafx.h" #include 实验二 // exa2.cpp : Defines the entry point for the console application. // #include"stdafx.h" #include 单片机并行口实验报告 实验二并行口实验报告 班级： 学号： 姓名： 教师： 一、实验目的 通过实验了解8051并行口输入方式和输出方式的工作原理及编程方法。 二、实验内容 1、输出实验 如图4-1所示。以8031的P2口为输出口。通过程序控制发光二极管的亮灭。 2、输入实验 如图4-1所示。以8031的P1口为输入口。用开关向P1.0~P1.3输入不同的状态，控制P2口P2.4~P2.7发光二极管的亮灭。 3、查询输入输出实验 如图1-1所示。以8051的P1.6或P1.0为输入位，以P2口为输出，二进制计数记录按键的次数。 图1-1 三、编程提示 1、输出实验程序 （1）设计一组显示花样，编程使得P2口按照设计的花样重复显示。 （2）为了便于观察，每一状态加入延时程序。 2、输入实验程序 开关打开，则输入为1；开关闭合，则输入为0。读取P1.0~ P1.3的状态，并将它们输出到P2.4~ P2.7，驱动发光二极管。所以发光二极管L1~L4的亮灭应与开关P1.0~ P1.3的设置相吻合。 3、查询输入输出程序 （1）编程计数P1.0按键次数，按键不去抖动。 （2）编程计数P1.6按键次数，按键不去抖动。 （3）编程计数P1.0按键次数，按键软件延时去抖动。 观察（1）、（2）、（3）、的结果。 四、实验器材 计算机，目标系统实验板 五、实验步骤 1、在KEILC中按要求编好程序，编译，软件调试，生成.HEX文件。 2、断开电源，按图1-1所示，连好开关及发光二极管电路。 3、下载程序。 4、调试运行程序，观察发光二极管状态。 六、C源程序清单 1、#include 并行计算上机实验报告题目：多线程计算Pi值 学生姓名 学院名称计算机学院 专业计算机科学与技术时间 一. 实验目的 1、掌握集群任务提交方式； 2、掌握多线程编程。 二.实验内容 1、通过下图中的近似公式，使用多线程编程实现pi的计算； 2、通过控制变量N的数值以及线程的数量，观察程序的执行效率。 三.实现方法 1. 下载配置SSH客户端 2. 用多线程编写pi代码 3. 通过文件传输界面，将文件上传到集群上 4.将命令行目录切换至data，对.c文件进行编译 5.编写PBS脚本，提交作业 6.实验代码如下： #include #include 第２２卷第２期中原工学院学报 Ｖｏｌ．２２ Ｎ ｏ．２ｐ 收稿日期： ２０１１－０３－１３ 基金项目： 河南省重点科技攻关项目（０７２１０２２１０００７） 作者简介： 金保华（１９６６－），男，河南郑州人，副教授． 文章编号： １６７１－６９０６（２０１１）０２－００１４－０４基于最大最小蚂蚁系统的一种应急物流路径规划方法 金保华，张 亮，和振远 （郑州轻工业学院，郑州４５０００２ ）摘 要： 根据应急物流中存在的一些问题，利用最大最小蚂蚁系统收敛速度快和避免局部最优的优势，提出了一种基于最大最小蚂蚁系统的应急物流路径规划方法．该方法通过最大最小蚂蚁系统将信息素限制在一个适当的范围之内，克服了传统算法收敛速度慢和易陷于局部最优的缺点．对应用最大最小蚂蚁系统的应急物流系统进行仿真实验，结果表明： 该方法能快速实现应急物流配送，满足了实际需要，减少了物流成本．关 键 词： 蚁群优化； 最大最小蚂蚁系统；旅行商问题；应急物流中图分类号： ＴＰ１８ 文献标志码： Ａ ＤＯＩ：１０．３９６９／ｊ ．ｉｓｓｎ．１６７１－６９０６．２０１１．０２．００４ 应急物流是指为突发事件提供紧急物资、 资金、职员的一种特别活动． 本文就应急物流选择最佳配送路线问题提出解决方法，即将最大最小蚂蚁系统（ＭＭＡＳ）应用到物流配送系统中，从而快速找到最优路径，完成配送． 蚁群算法是最近几年才提出的一种新型的模拟进 化算法．蚂蚁系统（ＡＳ ）是第一个蚁群算法，它最早是由意大利学者Ｄｏｒｉｇｏ Ｍａｎｉｅｚｚｏ等人在２０世纪９０年代初提出来，并用该方法求解旅行商问题（Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓ－ｍａｎ Ｐｒｏｂｌｅｍ，ＴＳＰ）［１］、二次分配问题（Ｑｕａｄｒａｔｉｃ Ａｓｓｉｇ ｎ－ｍｅｎｔ Ｐｒｏｂｌｅｍ，ＱＡＰ）、ｊｏｂ－ｓｈｏｐ调度问题等，取得了一系列较好的实验结果．但蚂蚁系统容易出现搜索停滞现 象．针对ＡＳ算法的不足， 许多学者对其进行深入研究，最后在ＡＳ基础上提出了最大最小蚂蚁系统［２］ ． 最大最小蚂蚁系统通过只允许在最好的解方法中增加信息素来实现最优路径搜索．它使用简单的机制限制了信息素的增强，有效避免了搜索的过早收敛．ＭＭＡＳ算法是当前解决ＴＳＰ和ＱＡＰ问题性能最好的方法之一．本文主要是将最大最小蚂蚁系统应用到应急物流路径选择中，并得到了较好的结果． １ 最大最小蚂蚁系统的原理 提升蚁群优化算法性能的关键是避免过早陷入搜 索停滞现象．为了解决这个问题，ＭＭＡＳ在蚂蚁系统 的基础上作了以下４个方面的改进： （１）在算法运行期间，只允许单只蚂蚁增加信息素．这只蚂蚁可能在当前迭代中找到最优解，或者在线索开始时就找到最优解． （２）为了避免出现搜索停滞现象，信息素范围限制在［τｍｉｎ，τｍａｘ］ 之间．（３）将弧段信息素初始化为τｍａｘ．（４ ）当系统达到停滞状态，或者在一定次数的迭代过程中不再有更优的路径出现时，则所有的信息素值都会被重新初始化． １．１ 信息素更新 在ＭＭＡＳ中，每次循环结束后只有一只蚂蚁更新信息素．信息素更新规则如下： τｉｊ（ｔ＋１）＝ρ·τｉｊ（ｔ）＋△Ｔｉｊ ｂｅｓｔ （１ ）式中：△Ｔｉｊ ｂｅｓｔ＝１／ｆ（ｓｂｅｓｔ），ｆ（ｓｂｅｓｔ ）代表了循环最优解或者全局最优解的值．ＭＭＡＳ主要使用迭代最优解．只用循环最优解或者全局最优解中的一个解进行信息素更新是ＭＭＡＳ中搜索过程最重要的方法．当仅用全局最优解时，搜索可能很快集中到这个解周围，而限制了搜索其他可能更好的解．如果只用循环最优解， 可能导致大量的解元素得到偶然加强．当然，也可以用 华中科技大学 课程名称并行处理 实验名称矩阵乘法的实现及加速比分析考生姓名李佩佩 考生学号 M201372734 系、年级计算机软件与理论2013级类别硕士研究生 考试日期 2014年1月3日 一. 实验目的 1) 学会如何使用集群 2) 掌握怎么用并行或分布式的方式编程 3) 掌握如何以并行的角度分析一个特定的问题 二. 实验环境 1) 硬件环境：4核CPU、2GB内存计算机； 2) 软件环境：Windows XP、MPICH2、VS2010、Xmanager Enterprise3； 3) 集群登录方式：通过远程桌面连接211.69.198.2，用户名：pppusr，密码：AE2Q3P0。 三. 实验内容 1. 实验代码 编写四个.c文件，分别为DenseMulMatrixMPI.c、DenseMulMatrixSerial.c、SparseMulMatrixMPI.c和SparseMulMatrixSerial.c，用于比较并行和串行矩阵乘法的加速比，以及稀疏矩阵和稠密矩阵的加速比。这里需要说明一下，一开始的时候我是把串、并行放在一个程序中，那么就只有两个.c文件DenseMulMatrix.c 和SparseMulMatrix.c，把串行计算矩阵乘的部分放到了主进程中，即procsID=0的进程，但是结果发现执行完串行后，再执行并行就特别的慢。另外，对于稀疏矩阵的处理方面可能不太好，在生成稀疏矩阵的过程中非0元素位置的生成做到了随机化，但是在进行稀疏矩阵乘法时没有对矩阵压缩，所以跟稠密矩阵乘法在计算时间上没多大区别。 方阵A和B的初始值是利用rand()和srand()函数随机生成的。根据稀疏矩阵和稠密矩阵的定义，对于稀疏矩阵和稠密矩阵的初始化方法InitMatrix(int *M,int *N,int len)会有所不同。这里需要说明一下，一开始对于矩阵A和B的初始化是两次调用InitMatrix(int *M ,int len)，生成A和B矩阵，但是随后我发现，由于两次调用方法InitMatrix的时间间隔非常短，又由于srand()函数的特点，导致生成的矩阵A和B完全一样；然后，我就在两次调用之间加入了语句“Sleep(1000)；”，加入头文件“#include 北京科技大学计算机与通信工程学院 实验报告 实验名称： 学生姓名： 专业： 班级： 学号： 指导教师： 实验成绩：________________________________ 实验地点： 实验时间：2015年05月 一、实验目的与实验要求 1、实验目的 1对比矩阵乘法的串行和并行算法，查看运行时间，得出相应的结论；2观察并行算法不同进程数运行结果，分析得出结论； 2、实验要求 1编写矩阵乘法的串行程序，多次运行得到结果汇总； 2编写基于MPI，分别实现矩阵乘法的并行化。对实现的并行程序进行正确性测试和性能测试，并对测试结果进行分析。 二、实验设备（环境）及要求 《VS2013》C++语言 MPICH2 三、实验内容与步骤 实验1，矩阵乘法的串行实验 （1）实验内容 编写串行程序，运行汇总结果。 （2）主要步骤 按照正常的矩阵乘法计算方法，在《VS2013》上编写矩阵乘法的串行程序，编译后多次运行，得到结果汇总。 实验2矩阵乘法的并行化实验 3个总进程 5个总进程 7个总进程 9个进程 16个进程 四：实验结果与分析（一）矩阵乘法并行化 矩阵并行化算法分析： 并行策略：1间隔行带划分法 算法描述：将C=A*B中的A矩阵按行划分，从进程分得其中的几行后同时进行计算，最后通信将从进程的结果合并的主进程的C矩阵中 对于矩阵A*B 如图：进程1：矩阵A第一行 进程2：矩阵A第二行 进程3：矩阵A第三行 进程1：矩阵A第四行 时间复杂度分析： f(n) =6+2+8+k*n+k*n+k*n+3+10+n+k*n+k*n+n+2 (k为从进程分到的行数) 因此O(n)=(n)； 空间复杂度分析： 从进程的存储空间不共用，f(n)=n; 因此O(n)=(n); 2间隔行带划分法 算法描述：将C=A*B中的A矩阵按行划分，从进程分得其中的几行后同时进行计算，最后通信将从进程的结果合并的主进程的C矩阵中 对于矩阵A*B 如图：进程1：矩阵A第一行 进程2：矩阵A第二行 进程3：矩阵A第三行 进程3：矩阵A第四行 时间复杂度分析： f(n) =6+2+8+k*n+k*n+k*n+3+10+n+k*n+k*n+n+2 (k为从进程分到的行数) 因此O(n)=(n)； 空间复杂度分析： 从进程的存储空间不共用，f(n)=n; 因此T(n)=O(n); 蚂蚁算法求解TSP问题 指导教师：李正学 系 别：应用数学系 班 级：2003级06班 姓 名：王源 学 号：200312082 蚂蚁算法求解TSP问题 摘 要蚂蚁算法是通过蚂蚁觅食而发展出的一种新的启发算法，该算法已经成功的解决了诸如TSP问题。本文简要学习探讨了蚂蚁算法和TSP问题的基本内容，尝试解决一个实例问题并给出C语言算法。 关键词蚂蚁算法；TSP问题。 1 蚂蚁算法与TSP问题 1.1 蚂蚁算法 蚂蚁算法(Ant Colony Algorithm) 是由意大利学者M.Dorigo ,V. Manierio ,A. Collorni等人于二十世纪九十年代提出的一种新型的模拟进化算法。受到人们对自然界中真实蚁群集体行为研究成果的启发,考虑到蚁群搜索食物的过程与旅行商问题的相似性,利用蚁群算法求解旅行商问题(Traveling Salesman Problem, TSP ) 、指派问题(AssignmentProblem)和调度问题( Scheduling Problem) ,取得了一些比较满意的实验结果。蚁群算法是一种适应性好、鲁棒性强,具有正反馈结构的并行算法。这些初步研究已显示出蚁群算法在求解复杂优化问题(特别是离散优化问题)方面的一些优越性,证明它是一种很有发展前景的方法。蚂蚁算法在各个领域的应用,说明该算法有着广泛的适应性,但由于该算法出现的较晚,对其 研究还处于起步阶段,远不如遗传算法、人工神经网络和模拟退火算法那样成熟。算法的很多特性,如算法的收敛性,参数的设定都来自于大量实验统计结果,目前 对该算法理论研究有待进一步加强。 经过研究发现，蚂蚁在觅食的过程中通过一种称之为信息素（Pheromone）的物质相互传递信息。更具体地，蚂蚁在运动过程中能够在其所经过的路径上留下信息素，而且在运动过程中能够感受到这种信息素的存在及其强度，并以此指导自己的运动方向。蚂蚁倾向于朝着信息素浓度高的方向前进，因此，由大量蚂蚁组成的蚁群的行为便表现出一种信息的正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚁群就是通过个体之间这种信息交换机制来彼此协作达到搜索食物的目的。 设有甲、乙两只蚂蚁从蚁穴A出发，分别沿AC 和ABC 路径同时在C 处 多核编程与并行计算实验报告 姓名： 日期：2014年 4月20日 实验一 // exa1.cpp : Defines the entry point for the console application. // #include"stdafx.h" #include 实验二 // exa2.cpp : Defines the entry point for the console application. // #include"stdafx.h" #include 8255并行口实验实验报告 作者： 一、实验目的 掌握8255A的编程原理。 二、实验设备 CPU挂箱、8086CPU模块。 三、实验内容 8255A的A口作为输入口，与逻辑电平开关相连。8255A的B口作为输出口，与发光二极管相连。编写程序，使得逻辑电平开关的变化在发光二极管上显示出来。 四、实验原理介绍 本实验用到两部分电路：开关量输入输出电路和8255可编程并口电路。 五、实验步骤 1、实验接线 CS0?CS8255； PA0～PA7?平推开关的输出K1～K8； PB0～PB7?发光二极管的输入LED1～LED8。 2、编程并全速或单步运行。 3、全速运行时拨动开关，观察发光二极管的变化。当开关某位置于L 时，对应的发光二极管点亮，置于H时熄灭。 六、实验提示 实验也是如此。实验中，8255A工作于基本8255A是比较常用的一种并行接口芯片，其特点在许多教科书中均有介绍。8255A有三个8位的输入输出端口，通常将A端口作为输入用，B端口作为输出用，C端口作为辅助控制用，本输入输出方式（方式0）。 七、实验结果 程序全速运行后，逻辑电平开关的状态改变应能在LED上显示出来。例如：K2置于L位置，则对应的LED2应该点亮。 八、程序框图（实验程序名：t8255.asm） 开始 设置8255工作方式 读A口 输出至B口 结束 九、程序源代码清单： assume cs:code code segment public org 100h start: mov dx,04a6h ;控制寄存器地址 mov ax,90h ;设 置为A口输入，B口输出 out dx,ax mov al,0feh start1:mov dx,04a2h 芯片的 入口地址 out dx,al mov bl,al mov dx ,04a0h in al,dx test ax,01h jz strat2 mov al ,bl rol al,1 流水灯循环左移 mov bl,al mov cx,3000h 设置cx为灯闪烁时间对应的循环次数 add: loop add jmp start1 无条件跳转至start1 strat2:mov al,bl mov dx,04a2h out dx,al ror al,1 流水灯循环左移 mov bl, al mov cx,3000h add1: loop add jmp start 无条件跳转至start code ends end start 十、实验总结 通过该实验，掌握了8255A的编程原理，学会了用汇编语言来编写程序控制8255A进行流水灯的操作实验。 深圳大学 实验报告 课程名称：并行计算 实验名称：矩阵乘法的OpenMP实现及性能分析姓名： 学号： 班级： 实验日期：2011年10月21日、11月4日 一. 实验目的 1) 用OpenMP 实现最基本的数值算法“矩阵乘法” 2) 掌握for 编译制导语句 3) 对并行程序进行简单的性能 二. 实验环境 1) 硬件环境：32核CPU 、32G 存计算机； 2) 软件环境：Linux 、Win2003、GCC 、MPICH 、VS2008； 4) Windows 登录方式：通过远程桌面连接192.168.150.197，用户名和初始密码都是自己的学号。 三. 实验容 1. 用OpenMP 编写两个n 阶的方阵a 和b 的相乘程序，结果存放在方阵c 中，其中乘法用for 编译制导语句实现并行化操作，并调节for 编译制导中schedule 的参数，使得执行时间最短，写出代码。 方阵a 和b 的初始值如下： ????????? ? ??????????-++++=12,...,2,1,..2,...,5,4,31,...,4,3,2,...,3,2,1n n n n n n n a ???????? ? ???????????= 1,...,1,1,1..1,...,1,1,11,...,1,1,11,..., 1,1,1b 输入： 方阵的阶n 、并行域的线程数 输出： c 中所有元素之和、程序的执行时间 提示： a,b,c 的元素定义为int 型，c 中所有元素之各定义为long long 型。 Windows 计时: 用 实验报告 课程名称虚拟化与云计算学院计算机学院 专业班级11级网络工程3班学号3211006414 姓名李彩燕 指导教师孙为军 2014 年12 月03日 EXSI 5.1.0安装 安装准备 安装VSPHERE HYPERVISOR SEVER（EXSI 5.1.0）需要准备： 无操作系统的机器（如有系统，安装过程中会格式化掉），需切换到光盘启动模式。BOIS中开启虚拟化设置（virtualization设置成enable） VMware vSphere Hypervisor 自启动盘 安装过程 1.安装VMware vSphere Hypervisor确保机器中无操作系统，并且设置BIOS到光盘启 动模式 2.插入光盘，引导进入安装界面。 3.选择需要安装在硬盘 4.选择keyboard 类型，默认US DEFAULT 5.设置ROOT的密码 6.安装完毕后，请注意弹出光盘。然后重启。 7.F2进入系统配置界面。 8.选择到Configure management network去配置网络。 9.配置完毕后，注意重启网络以使设置生效，点击restart management network，测 试网络设置是否正确，点test management network。至此，sever端安装完毕。配置 1.添加机器名：在DNS服务器上添加相关正反解析设置。 2.License设置：Vsphere client登陆后，清单→配置→已获许可的功能→编辑 输入license 3.时间与NTP服务设置：Vsphere client登陆后，清单→配置→时间配置→属性 钩选上NTP客户端 选项中，NTP设置设添加NTP服务器，然后在常规中开启NTP服务 科技大学计算机与通信工程学院 实验报告 实验名称： 学生： 专业： 班级： 学号： 指导教师： 实验成绩：________________________________ 实验地点： 实验时间：2015年05月 一、实验目的与实验要求 1、实验目的 1对比矩阵乘法的串行和并行算法，查看运行时间，得出相应的结论；2观察并行算法不同进程数运行结果，分析得出结论； 2、实验要求 1编写矩阵乘法的串行程序，多次运行得到结果汇总； 2编写基于MPI，分别实现矩阵乘法的并行化。对实现的并行程序进行正确性测试和性能测试，并对测试结果进行分析。 二、实验设备（环境）及要求 《VS2013》C++语言 MPICH2 三、实验容与步骤 实验1，矩阵乘法的串行实验 （1）实验容 编写串行程序，运行汇总结果。 （2）主要步骤 按照正常的矩阵乘法计算方法，在《VS2013》上编写矩阵乘法的串行程序，编译后多次运行，得到结果汇总。 实验2矩阵乘法的并行化实验 3个总进程 5个总进程 7个总进程 9个进程 16个进程 四：实验结果与分析（一）矩阵乘法并行化 矩阵并行化算法分析： 并行策略：1间隔行带划分法 算法描述：将C=A*B中的A矩阵按行划分，从进程分得其中的几行后同时进行计算，最后通信将从进程的结果合并的主进程的C矩阵中 对于矩阵A*B 如图：进程1：矩阵A第一行 进程2：矩阵A第二行 进程3：矩阵A第三行 进程1：矩阵A第四行 时间复杂度分析： f(n) =6+2+8+k*n+k*n+k*n+3+10+n+k*n+k*n+n+2 (k为从进程分到的行数) 因此O(n)=(n)； 空间复杂度分析： 从进程的存储空间不共用，f(n)=n; 因此O(n)=(n); 2间隔行带划分法 算法描述：将C=A*B中的A矩阵按行划分，从进程分得其中的几行后同时进行计算，最后通信将从进程的结果合并的主进程的C矩阵中 对于矩阵A*B 如图：进程1：矩阵A第一行 进程2：矩阵A第二行 进程3：矩阵A第三行 进程3：矩阵A第四行 时间复杂度分析： f(n) =6+2+8+k*n+k*n+k*n+3+10+n+k*n+k*n+n+2 (k为从进程分到的行数) 因此O(n)=(n)； 空间复杂度分析： 从进程的存储空间不共用，f(n)=n; 因此T(n)=O(n); 小蚂蚁大智慧 蚂蚁算法蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 为什么小小的蚂蚁能够找到食物？他们具有智能么？设想，如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要多么复杂呢？首先，你要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小，而且更重要的是，你要小心翼翼的编程，因为程序的错误也许会让你前功尽弃。这是多么不可思议的程序！太复杂了，恐怕没人能够完成这样繁琐冗余的程序。 然而，事实并没有你想得那么复杂，上面这个程序每个蚂蚁的核心程序编码不过100多行！为什么这么简单的程序会让蚂蚁干这样复杂的事情？答案是：简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！那么，这些简单规则是什么呢？下面： 1、范围蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。 2、环境蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。 3、觅食规则在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。 4、移动规则每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。 5、避障规则如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。 7、播撒信息素规则每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。 综述根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。单片机并行口实验报告
并行计算第一次实验报告
基于最大最小蚂蚁系统的一种应急物流路径规划方法
并行处理实验报告：用MPI实现的矩阵乘法的加速比分析
矩阵乘法的并行化 实验报告
蚂蚁算法
多核编程与并行计算实验报告 (1)
并行口实验实验报告
并行计算-实验二-矩阵乘法的OpenMP实现及性能分析
虚拟化与云计算实验报告.
矩阵乘法的并行化实验报告
蚂蚁算法(小蚂蚁大智慧)