并行计算课程作业.doc

并行计算课程作业一、 设计项目建议书 （60）请围绕本课程学习内容，按参考题目或自由选题以项目小组（每组2人）提交项目建议书文档，内容包括：1、 项目名称2、 项目参与者：姓名、学号、专业方向3、 项目主要内容和意义（120字）4、 立项依据：国内外研究概况、水平和发展趋势，重点解决的关键问题，主要参考文献目录和出处5、 项目设计报告：研究方案，实现原理，所需硬件框图，软件流程，关键伪代码描述，预期结果6、 研究计划安排和分阶段目标及人员分工7、 存在的问题和不足之处参考问题:1、 一家公司正面临满足服务要求的困难：从一个巨大的数据库中检索数据。该公司已有的做法是将要检索的条款清单交给程序，由该程序从数据库中找到它们。但近年来条款清单迅速膨胀到如此大的程度，使得检索过程非常耗时。为此该公司要求用多台机器并行地进行检索，并将要检索的条款清单加以分割，以便在多台机器上完成检索。2、 目前，一些学生拷贝其它同学完成的作业作为自己提交的作业，这是一种公认的剽窃行为。为此，更有创造力的学生在提交作业前做了一些改变：改变变量名，改变缩排，有时甚至改变循环结构（用”for”替代”while”）。每年有400名学生，每一次编程作业大约需要进行80000次程序比较。要求使用多台计算机，能并行地检查出400份作业存在的复制现象。3、 在一个红绿灯控制的十字路口，车辆从四个方向驶过来，要么穿过十字路口直走，要么左转弯要么右转弯。平均有70的车辆直走，10的右转弯，20的左转弯，每辆车以同样速度到达路口。要求设计一套方案，可同时反映多个路口车辆行驶状况。4、 旅行商问题是一个经典的计算机科学问题：从一个城市出发，目标是沿某一路径访问n个城市，且每个城市只访问一次，要使旅行的距离为最小。n个城市可以认为有不同的连接，用一加权图描述连接。从含有n个主要城市的地图上获得实际数据，设计一个并行算法解决该旅行商问题。5、 在一个计算机网络中，工作站和主服务器通过单个以太网连接，并以随机的间隔互相传递消息。设计一个算法模拟随机请求并向其它工作站传递消息，计算消息的大小和解决消息冲突。6、 一个简单的流媒体播放器由以下部分组成：一个监视网络端口到达数据的线程，一个对数据包解压缩并产生图像序列中的帧的解压缩器线程，以及一个在规划的间隔显示帧的绘制线程。这3个线程必须通过共享缓冲实现通信界于网络和解压缩器之间的输入缓冲，以及介于解压缩器与绘制器之间的输出缓冲。请设计一个方案实现该播放器播放。7、 银行曾使用过两个竞争算法中的一个或另一个来处理出纳处的顾客流量：单队列和多对列。在多队列方法中，每个出纳有其自己的队列，就像超市中的那样。在这种模型的标准形式中，顾客进入银行，选择一个队列排队，一直呆在队列中直到出纳员为他服务。一种流行的变通方法允许“跳队”，即队列中的每位顾客在不断地评估如果他站到另一队是否会使得他得到更快服务的机会。而在单队列方法中，只有一个队列。队列头部的顾客首先被出纳选择完成任务。请设计一个算法模拟标准的多队列和单队列方法。二、计算题 （40）1在环中，多对多广播有两种不同的实现方法：（1）标准环算法；（2）超立方体算法。1） 上述两种方法的运行时间各是多少？如果k个消息必须在同一时间通过同一链路，那么假定这些消息的有效字传送时间为ktw。同时假定ts=100tw。2） 如果消息m非常大，那么上述两种算法哪个更好，为什么？3） 如果消息m非常小（可能是一个字），那么哪个算法更好，为什么？2若并行计算机使用存储转发路由选择。大小为m的消息经长度为d的路径从传送到的成本为。一种可替代的传送大小为m的消息的方法如下：将消息分成k部分，每部分的大小为m/k，然后将这k个不同的消息一个接一个地从从传送到。对于这种新方法，在下面两种情况下，导出将大小为m的消息传送到d站以外所需时间的表达式。1） 假设在路径中，当前一条消息到达下一个节点后，另一条消息就能从从发出。2） 假设只有当前一条消息到达后另一条消息才能从发出。对于每种情况，当k的值在1和m之间变化时，试讨论表达式的值。如果很大，或者0时，k的最优值是多少？3考虑全归约操作中，其中每个处理器开始时有一个m字的数组，并且需要得到每个处理器的数组中各自的字的全局和。在环上实现这一操作有下面三种选择：1） 先进行所有数组的多对多广播，再在本地对数组中每个元素求和。2） 先在单节点上累积数组的元素，然后对结果数组进行一次一对多广播。3） 使用多对多广播模式的一个算法，但只是简单地进行加法操作而不对消息进行链接。（1） 对上述的每一种情况，计算用m, ts, tw表示的运行时间。（2） 假设ts=100, tw=1, 并且m非常大，上述三种选择哪一种更好？（3） 假设ts=100, tw=1, 并且m非常小（例如m=1），上述三种选择哪一种更好？4考虑一台有个处理器的共享地址空间并行计算机。假设每个处理器都有一些本地内存，被储存在的本地内存中。此外，在它的本地内存中计算。假定它在非本地内存中进行一次读或写需要的时间是，在本地内存中进行一次读或写需要的时间是。请推导下列算法在这台并行计算机上的并行运行时间的表达式。 CREW PRAM上两个矩阵A和B相乘的算法，得出矩阵 1. procedure MAT_MULT_CREW_PRAM(A, B, C, n)2. begin3. Organize the processes into