256-Parallel Computer Architecture并行计算机体系结构Lecture 4.pptVIP

Parallel Computer Architecture并行计算机体系结构Lecture 4 March 9, 2009 Wu junmin (jmwu@ustc.edu.cn) Overview Review of Lec3 性能提高（任务划分、分配、调度） Interconnection networks Review of Lec3 并行计算机的性能指标 Review of Lec3 加速比性能定律 并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。 Amdahl 定律 Gustafson定律 Sun Ni定律 可扩放性评测标准 等效率度量标准 等速度度量标准 平均延迟度量标准 程序级性能评测 基准测试程序（Benchmark） 一组标准的测试程序 提供一组控制测试条件 步骤的规则说明（测试平台环境、输入数据、输出结果和性能指标等 ） 基准测试程序的分类 真实程序 ：C compiler, Text editor, spice 核心程序 : Livermore 24 loops, Linpack 小测试程序 : 皇后问题、排序问题、求素数 合成测试程序 : Whetstone 、Dhrystone 应用：科学计算、商业应用、网络服务、多媒体应用 宏观测试程序（Macro-benchmark）：计算机系统作为一个整体来测试其性能 微观测试程序（Micro-benchmark） ：测试机器的某一特定方面的性质 Benchmark Suites Overview Review of Lec3 性能提高（任务划分、分配、调度） Interconnection networks 并行算法的设计过程 并行算法（程序）的设计步骤： 任务划分（Partitioning）：将整个计算分解为一些小的任务，其目的是尽量开拓并行执行的机会； 通信（Communication）：分析确定诸任务执行中所需交换的数据和协调诸任务的执行，由此可检测上述划分的合理性; 任务组合（Agglomeration）：按性能要求和实现的代价来考察前两阶段的结果，必要时可将一些小的任务组合成更大的任务以提高性能或减少通信开销; 处理器映射（Mapping）：将每个任务分配到一个处理器上，其目的是最小化全局执行时间和通信成本以及最大化处理器的利用率。 并行算法的设计过程（cont‘d) 任务划分 域分解（Domain Decomposition）也叫数据划分 算法（或程序）的输入数据、计算的输出数据、或者算法所产生的中间结果。 首先分解与问题相关的数据，使这些小的数据片尽可能大致相等；再将每个计算关联到它所操作的数据上。 划分将会产生一系列的任务，每个任务包括一些数据及其上的操作。当一个操作可能需要别的任务中的数据时，就会产生通信要求。 功能分解（Functional Decomposition）也称计算划分。 关注于被执行的计算上，而不是计算所需的数据上； 如果所作的计算划分是成功的，再继续研究计算所需的数据，如果这些数据基本上不相交，就意味着划分的成功； 如果这些数据有相当的重叠，就意味着必然带来大量的通信，这暗示着应该考虑数据分解。 一个并行程序通常同时存在数据和功能并行的机会。 功能并行的并行度通常比较有限，并且不会随着问题规模的的扩大而增加；不同的函数所涉及的数据集的大小可能差异很大，因此也难于实现负载平衡。 数据并行则一般具有较好的可扩放性，也易于实现负载平衡。 现有的绝大多数大规模的并行程序属于数据并行应用，但功能分解有时能提示问题的内在结构，展示出优化的机遇。 任务划分例1 任务划分例2 例2的另一种任务依赖图 粒度与并发度 粒度(Granularity): Fine-grained:分解成很多小的任务，如例1 Coarse-grained:分解成不多的大的任务，如在例1中分解成4个任务 并发度(Concurrency): 最大并发度：任何时刻可以同时执行的任务数。 平均并发度：整个执行过程中平均并行执行的任务数。 通常粒度和任务依赖图都会影响并发度 任务交互图(task interaction graph):影响并发度 由于编程模式和任务划分，在任务依赖图中不相关的任务间也有交互 在分布存储，例1的各个任务间共享向量。 例2的并发度 任务相关图 任务划分的几种方法(1) Recursive decomposition: Divide-and-conquer 划分成子任务，子任务递归解决。子任务间存在并发性。 例子：快排序 任务划分的几种方法(2) 任务划分的几种方法(3) 任务划分的几种方法(4) 任务划分的几种方法(5) Exp