典型并行算法的实现性能分析
第４卷第５期２００３年１０月
空军工程大学学报（自然科学版）
ＪＯＵＲＮＡＬＯＦＡＩＲＦｏＲＣＥＥＮＣＩＮＥＥＲＩＮＧＵⅣＩｖＥＲＳｒｒＹｆＮＡＴＵＲＡＬＳＣＩＥＮＣＥＥＤｍ０Ｎ
ｖｏ】４Ｎｏ５
０ｃｔ．２００３典型并行算法的实现性能分析
雷英杰１，霍红卫２
（１空军工程大学导弹学院，陕西三原７１３８００；２．西安电子科技大学计算机学院，陕西西安７１００７１）
摘要：讨论和分析了几种典型的并行算法及其各种处理方法在基于ｗｊｎｄｏｗｓｘＰ环境、消息传递接口ＭＰＩ并行编程环境支持和ｃ＋＋语言描述的编程实现问题，给出了相应并行程序详尽的计算结果，对比分析了它们的计算性能，以及它们对计算精度产生的影响。分析结论以相应并行算法的
实际编程实现和试验计算数据为基础，可信度高。设计实例表明。分析方法是有效的。
关键词：并行计算；消息传递接ｏ；并行算法；高性能计算
中图分类号：ＴＰ３９３文献标识码：Ａ文章编号：１００９—３５１６（２００３）０５一００６７—０４
并行算法计算性能问题是高端、高性能、大规模并行计算领域非常重要的研究内容…。本文以计算。值并行算法为例，通过对若于典型并行算法基于消息传递接口ＭＰＩ（ＭｅｓｓａｇｅＰ∞ｓｉｎｇ１１１ｔｅｒｆａｃｅ）编犁２１和ｃ语言描述的ＨｏｓⅡｅｓｓ程序实现及其运行结果的分析，给出一些新的对比分析结论。
ｌＭＰＩ并行编程环境
在基于ＭＰＩ的编程模型中，计算是由一个或多个彼此通过调用函数库函数进行消息收、发通信的进程所组成。在绝大部分ＭＰＩ实现中，一组固定的进程在程序初始化时生成。这些进程可以执行相同或不同的程序。进程间的通信可以是点到点的，也可以是群体的（ｃｏｌｌｅｃｔｉｖｅ）。ＭＰＩ最重要的特性是使用了称之为通信体的机构，允许程序员定义一种封装内部通信结构的模块。所谓通信体就是一个进程组加上进程活动环境，其中进程组就是一组有限或有序的进程集合。所谓有限意即组内包含有限数目的ｎ个进程依次按ｏ，１，…，ｎ—ｌ整数定序（Ｒａｎｋｅｄ）。ＭＰＩ中的进程活动环境是指系统指定的超级标记（ｓｕｐｅｒｔａｇ），它能安全地将彼此相互冲突的通信区分开来。每个通信体都有一个不同的、系统指定的进程活动环境，在这一个进程活动环境中发送的消息不能在另一个进程活动环境中被接收。
ＭＰＩ不是一个独立的、白包含的软件系统，ＭＰＩ进程是重量级、单线程的进程”］。ＭＰＩ标准并不指明如何启动并行计算，它可通过命令行参数指定应被生成的进程数，然后按ｓＰＭＤ或ＭＰＭＤ方式执行程序”Ｊ。
ＭＰＩ并行程序中经常需要一些进程组闻的群体通信，包括：①路障（Ｂａ而ｅＴ）——同步所有进程；②广播（Ｂｍａｄｃａｓｔ）——从一个进程发送一条数据给所有进程；③收集（Ｇａｔ｝ｌｅｒ）——从所有进程收集数据到一个进程；④散射（ｓｃａｔｃｅｒ）——从一个进程散发多条数据给所有进程；⑤归约（Ｒｅｄｕｃｔｉｏｎ）——包括求和、求积等。ＭＰＩ包含的函数多达２００个，它们的功能及参数描述参见文献［４］、［５］等。
２问题与算法描述
设计求ｗ值并行算法的关键是构造一个合适的函数，（＊），使得它计算起来既简便，误差又小。即使
收稿日期：２００３—０５一１２
基金项目：国家教育部骨干教师资助计划项目（ＧＧ一８１０—９００３９—１００３）资助
作者简介：重摹杰（１９５６一），争，阵西渭南人，教授，博士生导师；主要从事智能信息处理与模式识别研究
霍红卫（１９６３一），女，陕西西安人，主要从事算法设计与分析，并行与分布计算研究
空军工程大学学报（自然科学版）２００３年
ｗ＝【，（ｘ）出一∑＾。以扎）
这里取ｎ＝Ｏ，６＝１，Ⅳ为子区间分割数，于是＾＝１／Ⅳ。
我们选取二种函数，一种是，（ｘ）＝４√ｌ—ｘ２，其物理意义是单位圆面积ｓ＝”?ｒ２，我们称之为算法１。另一种函数是，（ｚ）＝４／（１＋ｚ２），可以直接进行积分，我们称之为算法２。
算式中的％在计算各个子区间的小矩形面积时，按左边界计算取ｑ＝＾＋ｉ，按右边界计算为％＝＾ｔ（ｉ＋１），按中间值计算为ｔ＝＾－（ｉ＋ｏ．５），按梯形计算时则要同时用到左、右两个边界。
并行算法实现时，分配每一个进程或ｃＰｕ计算其中的若干个子区间，然后通过归约，得到最终结果㈣。计算过程中。精度越高，要求Ⅳ越大。对于足够大的Ⅳ，要求在ｐ个进程或处理机上尽量均衡分配计算任务，通过归约完成总的计算。
３编程实现
３．１编程与运行环境
所实现的并行计算Ⅱ值的程序环境如下：ＭＰｌ支持为ＭＰＩｃＨＩ．２．４；编程语言为Ｍｉｃｍｓｏｆｔｖｉｓｕａｌｃ＋＋６．０；开发环境为ＭｉｃｒｏｓｏｆｔｗｈｌｄｏｗｓｘＰ＆ＶｉｓｕＢｌｓｔｕｄｉｏ６．０；硬件环境为ＰⅡＩ９００ｃＰｕ，１２８ＭＲＡＭ，２５６ｋｃａｃｈ８；运行环境为ｗｉｎｄｏｗ８ｘＰ。
３．２基于ＭＰＩ的编程
算法实现中用到的ＭＰｌ函数主要有：ＭＰＩｊＮｒｒ～启动ＭＰＩ计算；ＭＰｌ—ｃｏｍｎＬ－ｓｉｚｅ——确定进程数；ＭＰＩ—ｃｏ∞一ｍｋ——确定自己的进程标识数；ＭＰＩ—Ｇｅｔ—ｐｒｏｃｅｓｓｏｒ—ｎａｌｎｅ——获取处理机名字；ＭＰＩ—ｗｔｉｍｅ——获取系统时钟时间，以便记录算法始末运行的时刻和计算算法总的运行时间；ＭＰＩ—Ｂｃａｓｔ——广播进程信息给该组的所有其它进程；ＭＰＩ—Ｒｅｄｕｃｅ——归约，使各个进程所计算的值归约为一个值；ＭＰＩ—Ｆｉｎａｌｉｚｅ——结束ＭＰＩ进程。此外，比较重要的函数还有ＭＰＩ—ｓｅｎｄ——发送一条消息；ＭＰＩ—Ｒｅｃｖ——接受一条消息等。
对于足够大的子区间划分数Ⅳ和进程数ｐ，每个进程均衡完成的计算量为总计算量的＾坳。每一个计算进程通过ＭＰＩ—Ｂｃａｓｃ函数将自己计算的结果传递给其他进程，最后由某一进程（标识数ＭｙＩｄ为ｏ）利用ＭＰＩ—Ｒｅｄｕｃｅ函数进行归约，从而得到总的计算结果。
３．３实现的算法功能
对于算法ｌ，程序实现了如下功能：①利用小矩形左边界分解计算函数子区间面积的数值积分法，记为ＲＬＡｌ；②利用小矩形中问界分解计算函数子区间面积的数值积分法，记为ＲＭＡｌ；③利用小矩形右边界分解计算函数子区间面积的数值积分法，记为ＲＲＡｌ；④利用小梯形分解计算函数子区间面积的数值积分法，记为ＲＴＡｌ。
对于算法２，程序实现了如下功能：①利用小梯形分解计算函数子区间面积的数值积分法，记为ＡＴＡ２；
②利用小矩形中间界分解计算函数子区间面积的数值积分法，记为ＡＭＡ２
为分析方便起见，表ｌ列出了程序实现的功能号、算法及处理方法之间的对应关系。
使用时通过交互式菜单指定选择相应的算法及其实现功能，然后指定相应的子区间分割数目，程序将给出相应的计算结果。此外，也可以通过编辑一个文本文件，来设定需要选择的功能号和需要指定的子区间划分数目，然后在启动运行该程序时通过系统所提供的重定向功能，把该程序的输入重新定向到编辑好的文本文件。“功能号”取值可参见表１．“子区间分割数”取值应为任何足够大的正整数，如１０２—１０８。
表１程序功能、算法、处理方法对应关系
第５期雷英杰等：典型并行算法的实现性能分析
４结果及分析
针对各种算法功能，分别指定不同的子区间分割数，它们各自的计算结果如表２一表７所示。在设定计算参数时，子区间分割数从１０２～１０８共分７个数量级。表中分别列出子区间分割数Ⅳ、新计算出来的ｗ值与２５位”值比较后的误差值，以及本次计算所用的时间（单位为ｓ）。
精确Ⅱ值的前２５位为３．１４ｌ５９２６５３５８９７９３２３８４６２６４３。
表２ＲＬＡｌ计算结果表４ＲＲＡｌ计算结果表６ＡＴＡｌ计算结果表３ＲＭＡｌ计算结果表５ＲＴＡｌ计算结果表７ＡＭＡｌ计算结果
通过对计算结果的仔细观察、分析和比较，可以得出如下几点结论：
１）子区同分割数与计算时间的关系。无论对于哪一种计算功能，子区间的划分数目每增加一个数量级，计算叮ｒ值所需要花费的时间基本上也随之增加一个数量级。
２）算法性能。在分割子区间数目相同的情况下，无论是从计算时间，还是从计算精度方面来看，算法２都要优于算法ｌ。算法２在计算精度方面的优势十分明显。
究其原因，主要是因为算法２使用了反正切函数的导数函数作为母函数，计算简单，只包含一次乘法和一次除法。而算法１所使用的母函数除包含２次乘法之外，还需要多进行一次求平方根开方运算，而正是这个开方运算，既花费较多的时间，又使计算累计误差随机传播，从而降低了计算的速度和精度。
单从计算时间来看，无论是算法ｌ还是算法２，各种矩形法的计算时间基本都在同一个量级上，而梯形
７０空军工程大学学报（自然科学版）２００３年
法的计算时间则要长得多。
３）梯形法与矩形法。两者相比，由于梯形法要计算左、右边界两次，所以计算时间的相应增加远不止一倍。通过比较表２、表３、表４与表５，以及比较表６与表７，这一点十分明显。以子区间划分１０８为例，对于算法ｌ，矩形法的计算时间大致为ｌｏ—１２ｓ，而梯形法的计算时间则高达３６ｓ；对于算法２，矩形法的计算时间大致为１０～１１８，而梯形法的计算时间则高达２６．８ｓ。
在计算精度方面，当子区间分割数相对较小时，譬如１０２、１０３等，梯形法的计算精度明显高于矩形法，特别是对于算法ｌ。当子区间分割数相对较大时，譬如１０７、１０８等，梯形法与矩形法的计算精度已经没有明显差别。从理论上讲，梯形法的精度要高于矩形法，但从实践方面看，结果并不尽然，有时候梯形法的精度甚至要低于矩形法。这一情况产生的主要原因是理论上总是假定计算机每一步计算都是较为精确的，也很少假定所用算法在计算过程中产生的误差的分布和传播。实际上，对计算精度的影响还远不止于此。例如，求平方根的开方运算，可能导致计算结果有效数位显著减少，从而影响最终的计算结果。这一点可以从以上使用两种算法的计算结果表看出。
４）子区问分割数与计算误差。宏观上看，随着子区间分割数的增加，计算误差总体上呈现出下降的趋势，但这种下降不一定是单调的。对于算法１而言，基本是单调下降的；而对于算法２来说，则呈现波动下降的态势。
子区间分割数每增加一个数量级，算法ｌ总能使计算误差下降１至２个数量级。当子区问分割数大到一定程度后，如１０８数量级，算法２并不能总使计算误差再继续单调下降或保持稳定，而是出现了波动。这一点如表６和表７所示。其主要原因可能与计算误差的随机传播有关”“１”１。
５结论
本文集中讨论和分析了几种典型的计算叮ｒ值的并行算法及其各种处理方法在基于ＷｉｒｌｄｏｗｓｘＰ环境、ＭＰＩ并行编程环境支持和ＶＣ＋＋６．Ｏ下ｃ语言描述的编程实现问题，给出了计算程序详尽的计算结果，对比分析了各种算法及其处理方法的性能，以及它们对计算精度产生的影响。本文得出的若干分析结论是以相应算法的实际编程实现和试验计算数据为基础的，因而可信度高。
参考文献
［１］陈国良．并行计算——结构?算法?编程［Ｍ］．北京：高等教育出版社，１９９９．
［２］黄凯，徐志伟．可扩展并行计算——技术、结构与编程［Ｍ］．北京：机械工业出版社，２０００．
［３］ｍｅｄａ
Ｋ，Ａ王ＩｓｏｐｐＮＫ，ＨａＩｄ试ｃｋＪｃ，ｅｔＢＩ．ＡｎＡｓｓ瞄ｓｍｅｎｔ０ｆＭＰＩ
ＥⅡｖｉｒｏ册肌协ｆｏｒ刑ⅡｄｏｗｓＮ“Ｊ］ｎｅ如ｕｍｄ０ｆｓ“ｐｅ’ｃ…ｐｕ６“ｇ，２００１，（１９）：３１５—３２３．
［４］ｌ（ＩＩ曲ｄＡｌ—Ｔａｗｉｌ，ｃｓａｂａＡｎｄｍＭ甜ｔｚ．Ｐｅ而皿叩ｃｅＭ０ｄ出“ｇ虮ｄＥｖａｌｕａｄ叩ｏｆＭＨ［Ｊ］．Ｊｏｕｍａｌ０ｆＰａ讪ｅｌａＩｌｄＤｉｓｔｎｂｍｅｄｃｏｍＰｕｔｉｎｇ，２００ｌ，６１（２）：２０２—２２３．
［５］Ｄａｌｅｓｈｊｒｅｓ，Ｒ跚Ｍｏｈａｎ．ＡｎＥｖａｌｕ觚ｏｎｏｆＨＰＦ肌ｄＭＰＩＡｐｐ’ｎａｃｈ黯ⅡｎｄＰｅ面珊蛐ｃｅｉｎｕｎｓｔｍｃｔｕｒｅｄＦｉ础ｅＥｌｅｍｅｎｔｓｉｍｕｌａ－ⅡｏｎＢ［Ｊ］Ｊｏ啪ａ１０ｆＭ且ｔｈｃ啪ｄｃ且ｌＭ０ｄｅｍ“ｇａｎｄＡｌｇ“ｔＩ埘８，２００１，ｌ（３）：１５３—１６７．
［６］ｓｌ。ｇ陆ｅｄＢｅｎｋｎｅｒ，ＶｊｅｍｓｉＰｋｏｖａ．Ｅｘｐ“ｔｉｎｇＤｉｓｔ曲ｕｔｅｄ—Ｍｅｆｎｏｒｙａｎｄ
ｓｈａｒｅｄ—Ｍｅｍ。ｒｙＰ删“ｓｍｏｎｃｌｕ５ｔｅｒｓ０ｆｓＭＰｓｗｉｔｈＤａｔａＰａｍｕｅｌＰｒｏｇ栅８［Ｊ］．Ｉ呲ｅｍａ畦ｏｎ丑１Ｊ０ｕｍａｌｏｆＰ盯ａｌｌｅｌＰｍｇｍｍｒｒＩｉ“ｇ，２００１，３１（１）：３—１９．
［７］ＤａｖｉｓｏｎＧｅ珊ａｉｎ，ＡｌａｎＭ。ｒｒｉｓ，ｓｔｅｖｅｎＰａｒｋｅｒ，ｅｔ丑１．Ｐｅ南皿衄ｃｅＡｎａｌｙｓｉｓＩｍ唧ｄ叩ｉｎ吐№ｕｉｎｔａｌｌｓ曲ｗａｒｅＤ愀ｌｏｐｍｅｎｔｃｙ－ｄｅ［Ｊ］．Ｉｍ锄肚ｉｏｎａｌＪｏ眦ａｌｏｆＰａｍｕｅｌＰｒ０肿ｍｍｉｎｇ，２００３，３１（１）：３５—５３．
［８］ｗｅｎｈ８ｎｇ“ｕ，ｃｈｏ一“ｗ舳ｇ，Ｐ瑚明ｎａｖｉｋｔｏｒＫ．Ｐ０ｒｔａｂｌｅａｎｄｓｃａｌａｂｌｅＡｌｇｏ甜哪ｆｏｒＩ唧ｌａｒＡ１１一ｔｏ—Ａｌｌｃ砌ｍｕ血ｃ“ｏｎ［Ｊ］Ｊｏｕｒ【ｌｄ０ｆＰ啪ｕｅｌａｒｄＤｉ８ｔ抽ｕｔｅｄｃｏｍｐｕｔ岖，２００２，６２（１０）：１４９３—１５２６．
［９］Ｈｏ“ｇｚｈａ“ｇｓｈ帅，Ｊ船“ｎｄｅｒＳｉｎｇｈ，Ｌ肿ｎｉｄ０ｌｉｋｅｒ，ｅｔａ１．Ｍｅｓｓ８９ｅｐ鹊８ｉ“ｇ蚰ｄｓｈａｒｅｄａｄｄｒｅｓｓｓｐａｃｅｐ眦ｕｅ吐ｓｍｏｎ且ｒＩｓＭＰｄｕｓ—ｔｅｒ［Ｊ］．Ｐａｒ且ｕｅｌｃｏｍｐｕｔｉＩｌｇ，２００３，２９（２）：１６７—１８６
［１０］雷英杰，郑全弟．图像工程的基本概念和理论基础［Ｊ］空军工程大学学报（自然科学版），２００３，４（４）：６０一“．
（编辑：田新华）
（下转第７４页）
７４空军工程大学学报（自然科学版）２００３年
４．３数组边界检查
数组边界检查是对数组的读写操作进行严格的检查，确保对数组的操作是在正确的范围内”。ｏ。目前有以下几种检查方法：ｃｏｒｎｐａｑｃ编译器（由康柏公司开发），存储器存取检查（ｐｕ面ｒ工具）和选用类型一安全语言。
４．４程序指针完整性检查
程序指针完整性检查和边界检查略有不同。程序指针完整性检查，就是在指针被引用之前检测它是否发生过改变，即使一个攻击者成功地改变了程序的指针，由于系统事先检测到了指针的改变，因此这个指针将不会被使用。程序指针完整性检查通常有三种方法：一是堆栈检测，它能通过检测ｃｐｕ堆栈来确定缓冲区溢出；二是堆栈保护，这是～种提供程序指针完整性检查的编译器技术，通过检查函数活动纪录中的返回地址来实现。三是指针保护，通过在所有的代码指针之后放置附加字节来检验指针在被调用之前的合法性，如果检验失败，会发出报警信号，并退出执行程序。
５结束语
综上所述，缓冲区溢出是目前许多操作系统和软件产品开发中的常见问题，针对缓冲区溢出的攻击，已经给人类社会带来了一次次的灾难，给计算机网络系统带来了极大的隐患，严重威胁着网络安全。如何安全地使用计算机，预防和打击计算机犯罪，在普及计算机知识和应用的今天，已成为十分紧迫的任务。
参考文献
［１］凌雨欣，常红．网络安全技术与反黑客［Ｍ］．北京：冶金工业出版社，２０吡
［２］谭敏安，网络攻击防护编码设计［Ｍ］，北京：希望电子出版社，２００２．
［３］Ｅ工ｉｃｃｏｌｅ．Ｈ鹏ｋｅｒｂｅ啪ｒｅ［Ｍ］．ＩＮ：．Ｎｅｗ斑ｄｅ玛ＰＩｌｂＨｓｈｊ“ｇ，２００２．
［４］汪立东，方滨兴．ｕＮＩＡ缓冲区溢出攻击：技术原理、防范与检测［Ｊ］．计算机工程与应用，２０００，（２）：１２一ｌ４．
［５］雷荚杰，赵晔，邓宁．面向大型网络的肪火墙系统设计［Ｊ］．空军工程大学学报（自然科学版）．２００１，２（６）：３４—３６．
（编辑：田新华）Ｍｅｃｌｌａｌｌｉｓｍ锄ｄＡｔｔ孔ｌ【ｉｎｇＡｎａｌｙｓｉｓｏｆＢｕ肌ｒｏｖｅｍｏｗ
珊Ｙｏ“ｇ—ｙ蚰，Ｙ矾Ⅺａｏ—ｃｈｕａｎ，ＤＥＮＧＪｕｎ
（ｎｅｃｏｍｍｕｎｉｃ“０ｎＥｎ西ｎｅｅ血ｇＩｎｓｄｔｕｔｅ，ＡｉｒＦ０ｒｃｅＥｎ舀ｎｅｅｄｎｇＵｎｉｖｅｒｓ畸，Ｘｉ’ａｎ，Ｓｈａａｌｌ）【ｉ７１００７７，ｃｈｉｎａ）Ａｂｓ打ａｃｔ：Ｂ舳ｅｄ０ｎｔｌｌｅｆＬｌｎｄ蜘ｅｎｔａＩｍｅｃｈ虮ｉｓｍ０ｆｂｕ饪ｅｒｏｖｅｒｎｄｗ８ｔｔａｃｋｉ“ｇ，ｔ｝ｌｅｐｒｏｃｅｓｓａＩＩｄｃ１８ｓｓ墒ｃ“叽０ｆｂｕ船ｒｏｖｅｒｎｏｗａｔｔａｃｋｉｎｇａｒｅ∞ａｌｙｚｅｄｉｎ山ｉｓｐ印ｅｒ，ｓｉ叫ｌｔａｎｅｏｕｓｌｙｔｈｅｅｘｐ鲥ｍｅｎｔａｌ锄Ｂｌｙｓｉｓｉ８ｎｌａｄｅ卸ｄｓｅｖｅｒ８ｌｍｅａ３一ｏｖｅｍｏｗａｒｅｌｉｓｔｅｄｉｎｔｌｌｅｅｎｄ．
ｕｒｅｓｕ８ｅｄｔｏｎｍｔｅｃｔｂｕ丑ｂｒ
Ｋｅｙｗｏｒｄｓ：ｂｕ髓ｒｏｖｅｍｏｗ；ａｔｔａｃｋ
一十．＋中＋－＋－■——＋－—Ｐ—｝－ｐ忡■—?＋斗‘卜。■一＋－＿■’”＋。＋‘■‘。。＋一—Ｐ呻．＋叶一‘卜＋忡¨。＋巾＋一＋＿＋十＋＿＋?斗?（上接第７０页）
Ａ聃ｌｙｓｉｓｏｆＩｍｐＩ蜘呻ＩＩｔｉｎｇＰｅｒｆｏｍ粕ｃｅｆｏｒＴｙｐｉｃａｌＰａｒａｕｅｌＡｌｇｏｒｉｍｍｓ
ＬＥＩＹｉ“ｇ—ｊｉｅｌ，ＨｕＯＨ０ｎｇ—ｗｅｉ２
（１．ＴｈｅＭｊｓ８ｉｌｅＩｎｓｔｉｔｕｔｅ，ＡｉｒＦ０ｒｃｅＥ１１９ｉｎｅｅｒｉＩｌｇｕｎｉｖｅ商ｔｙ，Ｓａｎｙｕａｎ，ｓｈ姗ｘｉ７１３８００，Ｃｈｉｎａ；２．ｓｃｈｏｏｌｏｆ
Ｓｃｉｅｎｃｅ肌ｄＥｎｇｉｎｅｅｒｉｎｇ，Ⅺｄｉ趴ｕｎｉｖｅｒｓｉ哆，ｘｉ’ａ１１，ｓｈａａｎｘｊ７ｌ００７１，ｃｈｉｎａ）
ｃｏｍｐｕｔｅｒ
Ａｂｓｔ憎ｃｔ：７ｒｈｉｓｐａｐｅｒｄｉ８ｃｕｓｓｅｓ蚰ｄ蚰由ｚｅｓ血ｅｐｒ０Ｆａｍｍｉｎｇｐｒｏｂｌｅｍｓｗｉ血ｃ＋＋ｄｅｓｃｄｐｄｏｎｕｎｄｅｒｗｉｎｄｏｗｓＸＰ—ｂａｓｅｄｅｎｖｉｍｎｍｅｎｔｓｓｕｐｐｏｎｅｄｂｙｍｅｓｓａ９８ｐａｓｓｉｎｇｉｎｔｅｒｆｈｃｅ（ＭＰＩ），ｗｈｉｃｈｉｓａｐ删ｌｅｌｐｒｏ咿ｍｍｉ“ｇｔ００１，ａ１１ｄｉｍｐｌｅｍｅｎｔｉｎｇｐｅｄｂ皿肌ｃｅｏｆｓｅＶｅｒａｌ呻ｉｃａｌＰａｒａｌＩｅｌａｌｇｏｄｔ｝ｌｍＢ趿ｄｔｈｅｉｒｖ８ｒｉａｔｉｏｎｓｆ打ｐｒｏｃｅ３ｓｉｎｇ．Ｓｔｉｌｌ“ｐｒｅｓｅｎｔｓｉｎｄｅｔａｉｌ小ｅｃｏｍｐｕｔｅｄｒｅｓｕｈｓｉｎ出ｅｐｍⅡｄｐｒｏｇ咖ｍｓ锄ｄａｎＢｌｙｚｅｓａｃｏｍｐ耐ｓｏｎｏｆ血ｅｉｒｃｏｍｐｕｄｎｇｐｅ南珊明ｃｅｓａｎｄｔｈｅｅＨｂｃｔｏｆｔ｝Ｉｅｍｏ“ｐｒｅｃｉｓｉｏｎｉｎｃａｌｃｕｈｄｏｎ．
Ｋｅｙｗｏｒｄｓ：Ｐ叮且ｕｅｌｃｏｍｐｕｔａｔｉｏｎ；ＭＰＩ；ｐｄｌｅｌ讪妒ｒｉｔ｝ｌＩｎｓ．ｈｉｇｌｌｐｅ面ｎ犟衄ｃｅｃ咖ｐｕｔａｄｏｎ
并行与串行数据结构与算法课程设计报告
课程实验报告课程名称：并行与串行数据结构与算法 专业班级：ACM1301 学号：U201315057 姓名：李海锋 指导教师：陆枫 报告日期：2015.9.23 计算机科学与技术学院
目录 1、课程设计概述 (2) 1.1 课设目的 (2) 1.2 课设要求 (2) 1.3 实验环境 (3) 2、系统总体设计 (4) 2.1 系统主模块结构体 (4) 2.2 找附近的最近的三个某地 (5) 2.3 找两点之间最短路径 (6) 2.4 数据录入模块 (7) 3、数据结构和算法详细设计 (7) 3.1 地图的存储 (7) 3.1.1 地图背景图片的存储 (7) 3.1.2 地图点 (7) 3.2 找附近的最近的特定地点（findNearby） (8) 3.3 找最短路径 (8) 4、程序实现简要说明 (9) 4.1开发环境 (9) 4.2 支持包 (9) 4.3 函数原型 (10) MainActivity.java:实现了地图主要功能 (10) Setting.java：地图数据的录入 (12) 4.4 函数功能调用关系 (14) MainActivity.java：地图主要功能程序 (15) Setting.java：数据录入程序 (15) 5、程序测试及结果分析 (16) 5.1 功能测试 (16)
5.2 测试结果分析 (22) 6、复杂度分析 (22) 6.1 输入地点名查找，鼠标点击显示 (22) 6.2 找两点之间的最短路径(dijkstra) (22) 6.3 找附近最近的三个某地 (22) 7、软件的用户使用说明 (23) 8、特色与不足 (23) 8.1 特色 (23) 8.2 不足 (23) 九、主要参考文献 (24)
并行算法设计与分析考题与答案
《并行算法设计与分析》考题与答案 一、1.3，处理器PI的编号是： 解：对于n ×n 网孔结构,令位于第j行，第k 列（0≤j，k≤n-1）的处理器为P i（0≤i≤n2-1）。以16处理器网孔为例,n=4（假设j、k由0开始）： 由p0=p(j,k)=p(0,0) P8=p(j,k)=p(2,0) P1=p(j,k)=p(0,1) P9=p(j,k)=p(2,1) P2=p(j,k)=p(0,2) P10=p(j,k)=p(2,2) P3=p(j,k)=p(0,3) P11=p(j,k)=p(2,3) P4=p(j,k)=p(1,0) P12=p(j,k)=p(3,0) P5=p(j,k)=p(1,1) P13=p(j,k)=p(3,1) P6=p(j,k)=p(1,2) P14=p(j,k)=p(3,2) P7=p(j,k)=p(1,3) P15=p(j,k)=p(3,3) 同时观察i和j、k之间的关系，可以得出i的表达式为：i= j * n+k
一、1.6矩阵相乘（心动算法） a)相乘过程 设 A 矩阵= 121221122121 4321 B 矩阵=1 23443212121121 2 【注】矩阵元素中A(i,l)表示自左向右移动的矩阵，B(l,j)表示自上向下移动的矩阵，黑色倾斜加粗标记表示已经计算出的矩阵元素,如12, C(i,j)= C(i,j)+ A(i,l)* B(l,j) 1 2、
4、
6、
8、
10 计算完毕 b)可以在10步后完成，移动矩阵长L=7，4*4矩阵N=4,所以需要L+N-1=10
典型并行算法的实现性能分析
第４卷第５期２００３年１０月 空军工程大学学报（自然科学版） ＪＯＵＲＮＡＬＯＦＡＩＲＦｏＲＣＥＥＮＣＩＮＥＥＲＩＮＧＵⅣＩｖＥＲＳｒｒＹｆＮＡＴＵＲＡＬＳＣＩＥＮＣＥＥＤｍ０Ｎ ｖｏ】４Ｎｏ５ ０ｃｔ．２００３典型并行算法的实现性能分析 雷英杰１，霍红卫２ （１空军工程大学导弹学院，陕西三原７１３８００；２．西安电子科技大学计算机学院，陕西西安７１００７１） 摘要：讨论和分析了几种典型的并行算法及其各种处理方法在基于ｗｊｎｄｏｗｓｘＰ环境、消息传递接口ＭＰＩ并行编程环境支持和ｃ＋＋语言描述的编程实现问题，给出了相应并行程序详尽的计算结果，对比分析了它们的计算性能，以及它们对计算精度产生的影响。分析结论以相应并行算法的 实际编程实现和试验计算数据为基础，可信度高。设计实例表明。分析方法是有效的。 关键词：并行计算；消息传递接ｏ；并行算法；高性能计算 中图分类号：ＴＰ３９３文献标识码：Ａ文章编号：１００９—３５１６（２００３）０５一００６７—０４ 并行算法计算性能问题是高端、高性能、大规模并行计算领域非常重要的研究内容…。本文以计算。值并行算法为例，通过对若于典型并行算法基于消息传递接口ＭＰＩ（ＭｅｓｓａｇｅＰ∞ｓｉｎｇ１１１ｔｅｒｆａｃｅ）编犁２１和ｃ语言描述的ＨｏｓⅡｅｓｓ程序实现及其运行结果的分析，给出一些新的对比分析结论。 ｌＭＰＩ并行编程环境 在基于ＭＰＩ的编程模型中，计算是由一个或多个彼此通过调用函数库函数进行消息收、发通信的进程所组成。在绝大部分ＭＰＩ实现中，一组固定的进程在程序初始化时生成。这些进程可以执行相同或不同的程序。进程间的通信可以是点到点的，也可以是群体的（ｃｏｌｌｅｃｔｉｖｅ）。ＭＰＩ最重要的特性是使用了称之为通信体的机构，允许程序员定义一种封装内部通信结构的模块。所谓通信体就是一个进程组加上进程活动环境，其中进程组就是一组有限或有序的进程集合。所谓有限意即组内包含有限数目的ｎ个进程依次按ｏ，１，…，ｎ—ｌ整数定序（Ｒａｎｋｅｄ）。ＭＰＩ中的进程活动环境是指系统指定的超级标记（ｓｕｐｅｒｔａｇ），它能安全地将彼此相互冲突的通信区分开来。每个通信体都有一个不同的、系统指定的进程活动环境，在这一个进程活动环境中发送的消息不能在另一个进程活动环境中被接收。 ＭＰＩ不是一个独立的、白包含的软件系统，ＭＰＩ进程是重量级、单线程的进程”］。ＭＰＩ标准并不指明如何启动并行计算，它可通过命令行参数指定应被生成的进程数，然后按ｓＰＭＤ或ＭＰＭＤ方式执行程序”Ｊ。 ＭＰＩ并行程序中经常需要一些进程组闻的群体通信，包括：①路障（Ｂａ而ｅＴ）——同步所有进程；②广播（Ｂｍａｄｃａｓｔ）——从一个进程发送一条数据给所有进程；③收集（Ｇａｔ｝ｌｅｒ）——从所有进程收集数据到一个进程；④散射（ｓｃａｔｃｅｒ）——从一个进程散发多条数据给所有进程；⑤归约（Ｒｅｄｕｃｔｉｏｎ）——包括求和、求积等。ＭＰＩ包含的函数多达２００个，它们的功能及参数描述参见文献［４］、［５］等。 ２问题与算法描述 设计求ｗ值并行算法的关键是构造一个合适的函数，（＊），使得它计算起来既简便，误差又小。即使 收稿日期：２００３—０５一１２ 基金项目：国家教育部骨干教师资助计划项目（ＧＧ一８１０—９００３９—１００３）资助 作者简介：重摹杰（１９５６一），争，阵西渭南人，教授，博士生导师；主要从事智能信息处理与模式识别研究 霍红卫（１９６３一），女，陕西西安人，主要从事算法设计与分析，并行与分布计算研究
并行算法的设计基础
第四章 并行算法的设计基础 习题例题： 1. 试证明Brent 定理：令W (n)是某并行算法A 在运行时间T(n)内所执行的运算数量，则 A 使用p 台处理器可在t(n)＝O(W(n)／p+T(n))时间内执行完毕。 2. 假定P i （1≤i ≤n ）开始时存有数据d i , 所谓累加求和指用 1 i j j d =∑来代替P i 中的原始值 d i 。 算法 PRAM-EREW 上累加求和算法 输入： P i 中保存有d i , l ≤ i ≤ n 输出： P i 中的内容为 i j j l d =∑ begin for j = 0 to logn – 1 do for i = 2j + 1 to n par-do (i) P i = d i-(2^i) (ii) d i = d i + d i-(2^j) endfor endfor end (1)试用n=8为例，按照上述算法逐步计算出累加和。 (2)分析算法时间复杂度。 3. 在APRAM 模型上设计算法时，应尽量使各处理器内的局部计算时间和读写时间大致 与同步时间B 相当。当在APRAM 上计算M 个数的和时，可以借用B 叉树求和的办法。 假定有j 个处理器计算n 个数的和，此时每个处理器上分配n/p 个数，各处理器先求出自身的局和；然后从共享存储器中读取它的B 个孩子的局和，累加后置入指定的共享存储单元SM 中；最后根处理器所计算的和即为全和。算法如下： 算法 APRAM 上求和算法 输入： n 个待求和的数 输出： 总和在共享存储单元SM 中 Begin (1) 各处理器求n/p 个数的局和,并将其写入SM 中 (2) Barrier (3) for k = [ log B ( p(B – 1) + 1) ] – 2 downto 0 do 3.1 for all P i , 0 ≤ i ≤ p – 1,do if P i 在第k 级 then P i 计算其B 各孩子的局和并与其自身局和相加,然后将结果写入SM 中 endif
对并行算法的介绍和展望——学期大作业
《计算机系统结构》大作业 对并行算法的介绍和展望 专业计算机科学与技术 班级 111 学号 111425020133 姓名完颜杨威 日期 2014年4月17日 河南科技大学国际教育学院
对并行算法的介绍和展望 我们知道，算法是求解问题的方法和步骤。而并行算法就是用多台处理机联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。并行算法的研究涉及到理论、设计、实现、应用等多个方面，要保持并行算法研究的持续性和完整性，需要建立一套完整的“理论－设计－实现－应用”的学科体系，也就是所谓的并行算法研究的生态环境。其中，并行算法理论是并行算法研究的理论基础，包含并行计算模型和并行计算复杂性等；并行算法的设计与分析是并行算法研究的核心内容；并行算法的实现是并行算法研究的应用基础，包含并行算法实现的硬件平台和软件支撑技术等；并行应用是并行算法研究的发展动力，除了包含传统的科学工程计算应用外，还有新兴的与社会相关的社会服务型计算应用等。 并行算法主要分为数值计算问题的并行算法和非数值计算问题的并行算法。而并行算法的研究主要分为并行计算理论、并行算法的设计与分析、和并行算法的实现三个层次。现在，并行算法之所以受到极大的重视，是为了提高计算速度、提高计算精度，以及满足实时计算需要等。然而，相对于串行计算，并行计算又可以划分成时间并行和空间并行。时间并行即流水线技术，空间并行使用多个处理器执行并发计算，当前研究的主要是空间的并行问题。并行算法是一门还没有发展成熟的学科，虽然人们已经总结出了相当多的经验，但是远远不及串行算法那样丰富。并行算法设计中最常用的的方法是PCAM方法，即划分，通信，组合，映射。首先划分，就是将一个问题平均划分成若干份，并让各个处理器去同时执行；通信阶段，就是要分析执行过程中所要交换的数据和任务的协调情况，而组合则是要求将较小的问题组合到一起以提高性能和减少任务开销，映射则是要将任务分配到每一个处理器上。任何一个并行算法必须在一个科学的计算模型中进行设计。我们知道，任何算法必须有计算模型。任何并行计算模型必须要有为数不多、有明确定义的、可以定量计算的或者可以实际测量的参数，这些参数可以构成相应函数。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。它屏蔽了并行机之间的差异，从并行机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。 经过多年的发展，我国在并行算法的研究上也取得了显著进展，并行计算的应用已遍布天气预报、石油勘探、航空航天、核能利用、生物工程等领域，理论研究与应用普及均取得了很大发展。随着高性价比可扩展集群并行系统的逐步成熟和应用，大规模电力系统潮流并行计算和分布式仿真成为可能。目前，并行算法在地震数据处理中应用已较为成熟，近年来向更实用的基于PC机群的并行技术发展.然而，在非地震方法中，并行算法应用较少见文献报道，研究尚处于初级研究阶段。在大地电磁的二维和三维正、反演问题上，并行计算技术逐渐得到越来越多关注和重视.随着资源和能源需求的增长，地球物理勘探向深度和广度快速发展，大幅增长的数据量使得高性能并行计算机和高效的并行算法在勘探地球物理学中的发展和应用将占据愈来愈重要的地位。计算机技术在生物医学领域已经广泛应用，实践证明，并行算法在生物医学工程的各个领域中具有广泛的应用价值，能有效提高作业效率。随着电子科学技术的发展，电磁问题变得越来越复杂，为了在有限的计算机资源条件下求解大规模复杂电磁问题，许电磁学家已
习题作业-第五章 并行算法的一般设计方法
第5章 并行算法的一般设计策略 习题例题： 1、 令n是待排序的元素数，p＝2d是d维超立方中处理器的数目。假定开始随机选定主元x，并将其播送给所有其他处理器，每个处理器按索接收到的x，对其n/p个元素按照≤x 和＞x进行划分，然后按维进行交换。这样在超立方上实现的快排序算法如下： 算法5.6 超立方上快排序算法 输入：n个元素，B = n/p, d = log p 输出： 按超立方编号进行全局排序 Begin (1)id = processor’s label (2)for i=1 to d do (2.1) x = pivot / * 选主元 * / (2.2) 划分B为B1和B2满足B1 ≤B＜B2 (2.3) if第i位是零 then (i) 沿第i维发送B2给其邻者 (ii) C = 沿第i维接收的子序列 (iii) B= B1∪C else (i) 沿第i维发送B1给其邻者 (ii) C = 沿第i维接收的子序列 (iii) B= B2∪C endif endfor (3)使用串行快排序算法局部排序B = n/p个数 End ① 试解释上述算法的原理。 ② 试举一例说明上述算法的逐步执行过程。 2、 ① 令T = babaababaa。P =abab，试用算法5.4计算两者的匹配情况。 ② 试分析KMP算法为何不能简单并行化。 3、 给定序列（33，21，13，54，82，33，40，72）和8个处理器，试按照算法5.2构造一棵为在PRAM-CRCW模型上执行快排序所用的二叉树。 4、 计算duel(p, q)函数的算法如下： 算法5.7 计算串匹配的duel(p, q) 的算法 输入： WIT〔1: n-m+1〕，1≤p＜q≤n-m+1，(p - q) ＜ m/2 输出： 返回竞争幸存者的位置或者null（表示p和q之一不存在） Begin if p=null then duel= q else
《并行算法》课程总结与复习
《并行算法》课程总结与复习 Ch1 并行算法基础 1.1 并行计算机体系结构 并行计算机的分类 ?SISD,SIMD,MISD,MIMD； ?SIMD,PVP,SMP,MPP,COW,DSM 并行计算机的互连方式 ?静态：LA(LC),MC,TC,MT,HC,BC,SE ?动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) 1.2 并行计算模型 PRAM模型：SIMD-SM， 又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW SIMD-IN模型：SIMD-DM 异步APRAM模型：MIMD-SM BSP模型：MIMD-DM，块内异步并行，块间显式同步 LogP模型：MIMD-DM，点到点通讯 1.3 并行算法的一般概念 并行算法的定义 并行算法的表示 并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 并行算法的WT表示：Brent定理、WT最优 加速比性能定律 并行算法的同步和通讯 Ch2 并行算法的基本设计技术 基本设计技术 平衡树方法：求最大值、计算前缀和 倍增技术：表序问题、求森林的根 分治策略：FFT分治算法 划分原理： 均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择) 流水线技术：五点的DFT计算 Ch3 比较器网络上的排序和选择算法 3.1 Batcher归并和排序 0-1原理的证明 奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数)
双调归并网络：计算流程和复杂性(比较器个数和延迟级数) Batcher排序网络：原理、种类和复杂性 3.2 (m, n)-选择网络 分组选择网络 平衡分组选择网络及其改进 Ch4 排序和选择的同步算法 4.1 一维线性阵列上的并行排序算法 4.2 二维Mesh上的并行排序算法 ShearSort排序算法 Thompson&Kung双调排序算法及其计算示例 4.3 Stone双调排序算法 4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 Ch5 排序和选择的异步和分布式算法 5.1 MIMD-CREW模型上的异步枚举排序算法 5.2 MIMD-TC模型上的异步快排序算法 5.3分布式k-选择算法 Ch6 并行搜索 6.1 单处理器上的搜索 6.2 SIMD共享存储模型上有序表的搜索：算法 6.3 SIMD共享存储模型上随机序列的搜索：算法 6.4 树连接的SIMD模型上随机序列的搜索：算法 6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 Ch8 数据传输与选路 8.1 引言 信包传输性能参数 维序选路(X-Y选路、E-立方选路) 选路模式及其传输时间公式 8.2 单一信包一到一传输 SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) 8.3 一到多播送 SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法8.4 多到多播送 SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法8.5 贪心算法(书8.2) 二维阵列上的贪心算法 蝶形网上的贪心算法 8.6 随机和确定的选路算法(书8.3) Ch12矩阵运算
基于OpenMP并行求和算法分析
基于OpenMP的并行求和算法的研究与分析【摘要】目前几乎所有主流cpu厂商都致力于大力发展多核处理器，增加芯片支持的并行能力，从而提升计算机运算速度。本文主要探讨近来流行的多核计算技术，介绍一种重要的工业标准openmp，以及通过一个基于openmp的并行求和的简单例子来分析和说明并行计算效率与传统串行计算效率比较的优势。 【关键词】多核处理；并行求和算法；多线程；openmp 0.引言 多核技术始终是近年来全球计算机技术发展的重要内容。自从英特尔在2006年底发布了全球第一基于openmp的并行遗传算法探讨397款主流服务器四核处理器后，英特尔一直致力于推动多核应用生态系统的成熟与发展。实际上，从2002年推出超线程技术开始，英特尔就开始了向多核技术转型的步伐。最终，英特尔公司将四个计算“大脑”装入一枚处理器中，随着至强5300的诞生，计算机行业宣告正式进入了多核时代。 多核计算将成为一种广泛普及的计算模式，影响企业和消费者用户的使用模式。如目前的服务器应用，要求高的吞吐率和在多处理器上的多线程应用；internet的应用、p2p和普适计算的应用都促使了计算机性能的不断提升。大型企业的erp、crm等复杂应用，科学计算、政府的大型数据库管理系统、数字医疗领域、电信、金融等都需要高性能计算，多核技术可以满足这些应用的需求。 本文主要探讨近来流行的多核计算技术，介绍一种重要的工业
标准openmp，以及通过一个基于openmp的并行求和的简单例子来分析和说明并行计算效率与传统串行计算效率比较的优势。 1.openmp openmp是一种适用于多种硬件平台的共享存储编程的工业应用标准，提供了一个可用的编程模型，具有简单、可移植性和可扩展性，灵活支持多线程和负载平衡的潜在能力，目前支持fortran语言，c和c++。openmp规范中定义的制导指令、运行库和环境变量，能够在保证程序可移植性的前提下，按照标准将已有的串行程序逐步并行化。 openmp程序开始于一个单独的主线程。主线程会一直串行地执行，直到遇见第一个并行域才开始并行执行。并行域表示该部分程序计算量大，需要多个处理器共同来处理以提高效率和运行速度；并行区间以外的部分表示该部分的程序不适宜或者不能并行执行，只能由一个处理器来执行。主线程创建一队并行线程，然后，并行域中的代码在不同的线程队中并行执行，当主线程在并行域中执行完后，它们或被同步或被中断，最后只有主线程在执行。实际上，所有的openmp的并行化，都是通过使用嵌入到c/c++或foaran源代码中的编译制导语句来达到的。在具体实现时，在并行域开始处添加openmp制导指令#pragma，另外，openmp是独立于平台的，如果编译器不支持openmp，将会自动忽略预处理指令#pragma，程序依然可以按照串行程序代码顺利编译执行。 2.传统求和算法
并行计算-习题及答案-第12章 并行程序设计基础
第十二章 并行程序设计基础 习题例题： 1、假定有n 个进程P(0)，P(1)，…，P(n -1)，数组元素][i a 开始时被分配给进程P(i )。试写出求归约和]1[]1[]0[-+++n a a a 的代码段，并以8=n 示例之。 2、假定某公司在银行中有三个账户X 、Y 和Z ，它们可以由公司的任何雇员随意访问。雇员们对银行的存、取和转帐等事务处理的代码段可描述如下： /*从账户X 支取￥100元*/ atomic { if (balance[X] > 100) balance[X] = balance[X]-100； } /*从账户Y 存入￥100元*/ atomic {balance[Y] = balance[Y]-100；} /*从账户X 中转￥100元到帐号Z*/ atomic { if (balance[X] > 100){ balance[X] = balance[X]-100； balance[Z] = balance[Z]+100； } } 其中，atomic {}为子原子操作。试解释为什么雇员们在任何时候（同时）支、取、转帐时，这些事务操作总是安全有效的。 3、考虑如下使用lock 和unlock 的并行代码： parfor (i = 0；i < n ；i++){ noncritical section lock(S)； critical section unlock(S)； }
假定非临界区操作取T ncs时间，临界区操作取T cs时间，加锁取t lock时间，而去锁时间可忽略。则相应的串行程序需n( T ncs + T cs )时间。试问： ①总的并行执行时间是多少？ ②使用n个处理器时加速多大？ ③你能忽略开销吗？ 4、计算两整数数组之内积的串行代码如下： Sum = 0； for(i = 0；i < N；i++) Sum = Sum + A[i]*B[i]； 试用①相并行；②分治并行；③流水线并行；④主-从行并行；⑤工作池并行等五种并行编程风范，写出如上计算内积的并行代码段。 5、图12.15示出了点到点和各种集合通信操作。试根据该图解式点倒点、播送、散步、收集、全交换、移位、归约与前缀和等通信操作的含义。 图12.15点到点和集合通信操作
并行算法的一般设计策略
第五章并行算法的一般设计策略 习题例题: １、令n是待排序的元素数,p＝2ｄ是d维超立方中处理器的数目。假定开始随机选定主元x，并将其播送给所有其他处理器，每个处理器按索接收到的x,对其n／p个元素按照≤ x和>x 进行划分，然后按维进行交换。这样在超立方上实现的快排序算法如下： 算法５.6 超立方上快排序算法 输入：n个元素，Ｂ= n/p, d ＝lｏg ｐ 输出:按超立方编号进行全局排序 Ｂｅｇin (1)iｄ=proｃesｓｏr’s labeｌ (2)fｏrｉ=１to d do (2.１) x = piｖoｔ/ * 选主元 * / （2.２) 划分B为B1和Ｂ2满足B1 ≤B<Ｂ2 （2.3）if第i位是零thｅn (i) 沿第i维发送B２给其邻者 （iｉ）C ＝沿第i维接收的子序列 (ｉii) Ｂ＝B1∪Ｃ eｌse (i）沿第ｉ维发送B1给其邻者 （ii) C=沿第i维接收的子序列 （iii) B= B2∪Ｃ eｎdif enｄｆｏｒ (3)使用串行快排序算法局部排序Ｂ= n/p个数 Eｎd ①试解释上述算法的原理。 ②试举一例说明上述算法的逐步执行过程。 2、①令T＝bａbaaｂabaa。P ＝abａｂ，试用算法5.4计算两者的匹配情况。 ②试分析KMP算法为何不能简单并行化。 3、给定序列（3３,2１,13，５4,8２，33,４0，７2）和8个处理器,试按照算法5.2构造一棵为在ＰRAM-CRCW模型上执行快排序所用的二叉树。 4、计算dｕel（ｐ, q)函数的算法如下: 算法5.7 计算串匹配的ｄuel（p，q）的算法 输入：WIＴ〔１:n－ｍ+1〕，１≤p 深圳大学 实验报告 课程名称：并行计算 实验名称：矩阵乘法的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 计时: 用 并行计算-实验二-矩阵乘法的OpenMP实现及性能分析 深圳大学 实验报告 课程名称：并行计算 实验名称：矩阵乘法的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计时: 用 第五章并行算法的一般设计策略 习题例题： 1、令n是待排序的元素数，p＝2d是d维超立方中处理器的数目。假定开始随机选定主元x，并将其播送给所有其他处理器，每个处理器按索接收到的x，对其n/p个元素按照≤ x和＞x进行划分，然后按维进行交换。这样在超立方上实现的快排序算法如下： 算法5.6 超立方上快排序算法 输入：n个元素，B = n/p, d = log p 输出：按超立方编号进行全局排序 Begin (1)id = processor’s label (2)for i=1 to d do (2.1) x = pivot / * 选主元 * / (2.2) 划分B为B1和B2满足B1 ≤B＜B2 (2.3) if第i位是零then (i) 沿第i维发送B2给其邻者 (ii) C = 沿第i维接收的子序列 (iii) B= B1∪C else (i) 沿第i维发送B1给其邻者 (ii) C = 沿第i维接收的子序列 (iii) B= B2∪C endif endfor (3)使用串行快排序算法局部排序B = n/p个数 End ①试解释上述算法的原理。 ②试举一例说明上述算法的逐步执行过程。 2、①令T = babaababaa。P =abab，试用算法5.4计算两者的匹配情况。 ②试分析KMP算法为何不能简单并行化。 3、给定序列（33，21，13，54，82，33，40，72）和8个处理器，试按照算法5.2构造一棵为在PRAM-CRCW模型上执行快排序所用的二叉树。 4、计算duel(p, q)函数的算法如下： 算法5.7 计算串匹配的duel(p, q) 的算法 输入：WIT〔1: n-m+1〕，1≤p＜q≤n-m+1，(p - q) ＜m/2 输出：返回竞争幸存者的位置或者null（表示p和q之一不存在） Begin if p=null then duel= q else if q =null then duel= p else (1) j= q - p +1 并行编程模型 1.概述 并行编程模型是并行计算，尤其是并行软件的基础，也是并行硬件系统的导向。并行编程模型可以按照以下几种方式进行表述： （1）数据并行和任务并行：根据并行程序是强调相同任务在不同数据单元上并行，还是不同任务在相同或不同数据上实现并行执行，可以将并行性分为两类：数据并行和任务并行。由于数据并行能获得的并行粒度比任务并行高，因此可以扩展并行机上的大多数程序采取数据并行方式。但是任务并行在软件工程上有很重要的作用，它可以使不同的组件运行在不同的处理单元集合上，从而获得模块化设计。人们越来越趋向予将并行程序组织成为由数据并行组件组成的任务并行组合物。 （2）显式并行和隐式并行：并行编程系统可以根据支持显式或隐式并行编程模型来对其进行分类。显式并行系统要求编程人员直接制定组成并行计算的多个并发控制线程的行为；隐式并行系统允许编程人员提供一种高层的、指定程序行为但不显示表示并行的规范，它依赖于编译器或底层函数库来有效和正确地实现并行。越来越普遍的一种做法就是将算法设计的复杂性集成到函数库上，这样可以通过一系列对函数库的调用来开发应用程序。通过这种方式，可以在一种显式并行框架中获得隐式并行的某些好处。 （3）共享存储和分布存储：在共享存储模型中，程序员的任务就是指定一组通过读写共享存储进行通信的进程的行为。在分布存储模型中，进程只有局部存储，它必须使用诸如消息传递或远程过程调用等机制来交换信息。 很多多核处理器体系结构都同时支持这两种模型。 共享存储体系结构下的并行编程模型主要是共享变量编程模型，它具有单地址空间、编程容易、可移植性差等特点，其实现有OpenMP和Pthreads等。分布式存储体系结构下的并行编程模型主要有消息传递编程模型和分布式共享编程模型两种:消息传递编程模型的特点是多地址空间、编程困难、可移植性好，其实现有MPI, PVM等; 分布式共享编程模型是指有硬件或软件的支持，在分布式体系结构下实现的具有共享变量编程模型特点的编程模型。 后者可以分别按照硬件或软件的实现分为DSM和SVM,其实现有TreadMark和JiaJia等，目前研究热点的分割全局地址空间(PGAS)模型的研究有UPC等代表，具有很强的发展潜力。 2.并行编程模型的性的评价指标 (1)时间：程序串行运行时间是指在串行计算机上，程序从开始到运行结束所用的时间。并行运行程序是从并 行计算开始时刻到最后的处理器完成运算所经过的时间。 (2)总并行开销：并行系统的开销函数或总开销为由所有处理器话费的总时间，除去在单个处理器上求解相同 问题时最快的串行算法所需要的时间。所有处理器所用总时间减去完成有用工作所花费的时间，剩余部分即是开销。 (3)加速比：在单个处理器上求解问题所花的时间与用p个相同处理器并行计算机求解同一问题所花时间之比。 (4)效率：处理器被有效利用部分时间的度量，它定义为加速比与处理器数目的比率。在理想的并行系统中， 加速比等于p，效率等于1。实际上，加速比小于p而效率在0和1之间，它依赖于处理器被利用的效率。 (5)成本：并行运行时间与所用处理器数目的乘积。成本反映每个处理器求解问题所花费时间的总和。 另外，移植性、伸缩性和对各类语言的支持度也是评价指标。 3．影响并行编程模型性能的关键因素 多核处理器系统采用单芯片多处理器核的设计，这些处理器核相互独立，每个拥有一套完整的硬件执行环境，可以同时执行多道指令。在高速缓存设计方面，每个核拥有独立的片上缓存和共享的最后一级缓存。基于多核处理器的系统特征，影响并行程序性能的因素主要包括存储带宽、片上缓存一致性和负载均衡。 （1）存储带宽。在多核系统中，最后一级缓存是被各个核所共享的，如果位于同核上的多个线程同时对不同的数据集进行操作，将会导致最后一级缓存与主存之间频繁地传送数据。由于在主存和缓存之间传送数据的速度远小于CPU的计算速度，因此有限的存储带宽成为了影响多核环境下并行程序性能的瓶颈。 （2）片上缓存一致性。所谓片上缓存一致性，是指多核系统中各个核的片上缓存位于相同存储空间上的数据必须保持一致。虽然多核系统共享的cache体系结构在最后一级cache上减少了cache一致性问题，但由于每个核 中科院数学与系统科学研究院 “并行计算” 课程讲义（草稿）” 张林波 计算数学与科学工程计算研究所 科学与工程计算国家重点实验室 2003 年1月29 目录 第一部分MPI消息传递编程 第一章预备知识 §1.1 高性能并行计算机系统简介 §1.1.1 微处理器的存储结构 §1.1.2 Cache 结构对程序性能的影响 §1.1.3 共享内存SMP 型并行计算机 §1.1.4 分布式内存MP P 型并行计算机 §1.1.5 DSM 型并行计算机 §1.1.6 SMP/D SM 机群 §1.1.7 微机／1.4.作站机群 §1.1.8 TOP500 §1.2 并行编程模式 §1.2.1 自动并行与手1.4.并行 §1.2.2 0penMP §1.2.3 DSM 编程模式 §1.2.4 高性能Fortran: HPF §1.2.5 消息传递并行编程模式 §l.3 Unix 程序开发简介 §l.3.1 Unix中常用的编译系统 §1.3.2 实用1.4.具make §1.4 消息传递编程平台MPI §1.4.1 MPI 程序的编译与运行 §1.4.2 利用MPICH 建立MPI 程序开发与调试环境第二章MPI 基础知识 §2.1 下载MPI标准的PS 文档 §2.2 一些名词与概念 §2.3 编程模式 §2.4 MPI 函数的一般形式 §2.5 MPI 的原始数据类型 §2.5.1 Fortran 77 原始数据类型 §2.5.2 C 原始数据类型 §2.6 MPI 的几个基本函数 §2.6.1 初始化MPI 系统 §2.6.2 检测MPI 系统是否已经初始化 §2.6.3 得到通信器的进程数及进程在通信器中的序号§2.6.4 退出MPI 系统 §2.6.5 异常终止MPI 程序的执行 §2.6.6 查询处理器名称 §2.6.7 莸取墙上时间及时钟精度 §2.7 MPI 程序的基本结构 §2.7.1 Fortran 77 程序 §2.7.2 C 程序 第三章点对点通信 §3.1 标准阻塞型点对点通信函数 §3.1.1 标准阻塞发送 §3.1.2 阻塞接收 §3.1.3 阻塞型消息传递实例 §3.1.4 其它一些阻塞型消息传递函数 §3.2 消息发送模式 §3.2.1 阻塞型缓冲模式消息发送函数 §3.3 阻塞型与非阻塞型函数 §3.4 非阻塞型点对点通信函数 §3.4.1 非阻塞发送 §3.4.2 非阻塞接收 §3.4.3 通信请求的完成与检测 §3.4.4 通信请求的释放 §3.5 消息探测与通信请求的取消 §3.5.1 消息探测 §3.5.2 通信请求的取消 §3.6 点对点通信函数汇总 §3.7 持久通信请求 §3.7.1 创建持久消息发送请求 §3.7.2 创建持久消息接收请求 §3.7.3 开始基于持久通信请求的通信 §3.7.4 持久通信请求的完成与释放 第四章数据类型 §4.1 与数据类型有关的一些定义 §4.1.1 数据类型定义 §4.1.2 数据类型的大小 §4.1.3 数据类型的下界、上界与域 §4.1.4 MPI_LB 和MPI_UB §4.1.5 数据类型查询函数 §4.2 数据类型创建函数 §4.2.1 MPI_Type_contiguous §4.2.2 MPI_Type_vector §4.2.3 MPI_Type_hvector §4.2.4 MPI_Type_indexed §4.2.5 MPI_Type_hindexed并行计算_实验二_矩阵乘法的OpenMP实现及性能分析
并行计算-实验二-矩阵乘法的OpenMP实现及性能分析
并行算法的般设计策略
并行计算作业一·
并行算法讲义