类型1.pptVIP

Slides for Parallel Programming Techniques Applications Using Networked Workstations Parallel Computers 2nd ed., by B. Wilkinson M. Allen, @ 2004 Pearson Education Inc. All rights reserved. Pipelined Computations 流水线计算 Lecture 6, Chapter 5 Pipelined Computations 问题被分成一系列必须是一个接一个完成的任务 (顺序程序设计的基础). 每个任务由独立的进程或处理器所执行. 例一：求和 将数组 a 元素累加求和: for (i = 0; i n; i++) sum = sum + a[i]; 此for循环语句可拆成下面的语句 sum = sum + a[0]; sum = sum + a[1]; sum = sum + a[2]; sum = sum + a[3]; sum = sum + a[4]; . . . 用流水线法 例二 频率过滤器 - 目标是从数字化信号f(t)中去掉特定的频率 (f0, f1, f2,f3, etc.) 信号从流水线的左方进入，每一级负责去掉一个频率: 流水线计算适用范围 假设问题可分解成一系列的顺序任务，下面三种计算类型可以用流水线方法来加速: 类型1. 如果需要对该问题运行多个实例的。 类型2. 如果必须处理一系列数据的，而每个数据需要多次操作的。 类型3. 如果进程在完成自己的所有内部操作之前能够把下一个进程启动所需要的信息向前传送的。 “类型1” 流水线 时空 图表 每个实例(instance)需要依次经历6个顺序进程 类型1的另一种时空图标 个人感觉：此问题还不如对每个实例按照工作池(work pool)的动态方法好 “类型2” 流水线时空图表 个人感觉还是工作池的方法要好 “类型3” 流水线 时空图表 在前一个进程结束之前就将信息从当前进程传到下一级。 If the number of stages is larger than the number of processors in any pipeline, a group of stages can be assigned to each processor: 如果阶级数大于进程数，就将级分组成批给每个进程 Computing Platform for Pipelined Applications Multiprocessor system with a line configuration 线性结构的多处理器系统：方便，廉价， 相邻的处理器支持同时消息传递。 以太网 流水线程序举例 (Examples of each type of computation) Pipeline Program Examples 多组数 进行组内数的相加 类型1的流水线计算 ai ai ai ai ai 中间的每个进程 Pi : recv(accumulation, Pi-1); accumulation = accumulation + number; send(accumulation, Pi+1); 第一个进程, P0, send(number, P1); 最后一个进程, Pn-1, recv(number, Pn-2); accumulation = accumulation + number; SPMD program if (process 0) { recv(accumulation, process-1); accumulation = accumulation + number; } if (process n-1) send(accumulation, process+1); 在最后进程中得到结果。 除了加法运算，其他算术运算都可如此编程。 各进程的程序可以合写成： 数多了，应该采用数据划分来减少通信开销。 Pipelined addition numbers Master process and ring configuration Sorting Numbers A parallel version of insertion sort. (插入排序) Pipeline for sorting using insertion sort 类型2的流水线计算 进程 Pi 的基本算法 recv(number, Pi-1); if (number x) { send(x, Pi+1); x = number