并行计算机体系结构第一章.ppt

并行计算机体系结构技术与分析,杨晓霞Email：,授课内容,计算机系统结构的演变并行计算机系统的性能度量流水和向量处理并行存储系统和同步机制互联网络,第一章 计算机体系结构的演变,计算机性能的高速增长受益于：,电路技术的发展体系结构技术的发展,计算机系统中的层次概念计算机系统软件硬件/固件计算机语言由低级向高级发展 高一级语言的语句相对于低级语言功能更强，更便于应用，但又都以低级语言为基础。从计算机语言的角度，把计算机系统按功能划分成多级层次结构。,第一章 计算机体系结构的演变,计算机硬件系统五大功能部件包括：运算器、控制器存储器（高速缓存 主存储器 虚拟存储器）输入设备、输出设备这些设备和部件通过 总线 和 接口 连结在一起，构成一台完整的计算机，如下图所示：,第一章 计算机体系结构的演变,输入设备,输出设备,输入出接口和总线,控 制 器,运 算 器,虚拟存储器,主存储器,高速缓存,第一章 计算机体系结构的演变,数据总线地址总线控制总线,计算机主机,计算机外围设备,计算机的CPU,第一章 计算机体系结构的演变,围绕运算器部件构建系统 围绕存储器部件构建系统,第一章 计算机体系结构的演变,运 算 器,运算器部件是计算机中进行数据加工的部件，其主要功能包括：1.执行数值数据的加减乘除等算术运算，执行逻辑数据的与或非等逻辑运算，由一个被称为 ALU 的线路完成。2.暂时存放参加运算的数据和中间结果，由多个通用寄存器和乘商寄存器承担。3.运算器通常也是数据传输的通路。,第一章 计算机体系结构的演变,控 制 器,运 算 器,控制器是计算机中控制执行指令的部件，向计算机各功能部件提供每一时刻协同运行所需要的控制信号：1.正确分析与执行每条指令：取指令分析指令执行指令。2.保证指令按规定序列自动连续地执行。3.对各种异常情况和请求及时响应和处理。,第一章 计算机体系结构的演变,虚拟存储器,主存储器,高速缓存,控 制 器,运 算 器,由高速缓冲存储器、主存储器、虚拟存储器所组成的多级存储器系统，是计算机中用于存储程序和数据的部件。这三级存储器各自的功能分工、所用的存储介质的工作原理和特性各不相同,第一章 计算机体系结构的演变,输入设备,虚拟存储器,主存储器,高速缓存,控 制 器,运 算 器,输入设备是向计算机中送入程序和数据的具有一定独立功能的设备，通过 接口 和 总线与计算机主机连通，用于人机交互联系，如计算机键盘和鼠标等。,第一章 计算机体系结构的演变,输入设备,输出设备,虚拟存储器,主存储器,高速缓存,控 制 器,运 算 器,输出设备是计算机中用于送出计算机内部信息的设备，例如打印机、显示器等。,第一章 计算机体系结构的演变,输入设备,输出设备,虚拟存储器,主存储器,高速缓存,控 制 器,运 算 器,这些部件和设备通过总线和接口连接在一起,构成计算机整机系统，协同运行。,入出接口和总线,第一章 计算机体系结构的演变,计算机软件要包含语言支持功能。计算机通常使用它的硬件可以直接识别、用电子线路容易处理的一种语言，这就是计算机的机器语言，又称为二进制代码语言，也就是计算机的指令；使用计算机的人员往往要使用更“高级”一些的汇编语言和高级程序设计语言，在这两种语言之间需要完成必要的处理和翻译。计算机软件还要为计算机系统本身提供性能良好的资源管理功能，为使用人员提供尽可能多的帮助。把资源管理和调度功能留给计算机系统软件来完成更可靠，完成这一功能的软件就是计算机的操作系统。操作系统的存在，又为使用计算机的用户提供了许多支持，与程序设计语言相结合，使得程序设计更简化，建立用户的应用程序和操作计算机更方便。,第一章 计算机体系结构的演变,软件,硬件或固件,多级层次结构,(1)虚拟机：由软件实现的机器。(2)语言实现的两种基本技术 翻译：先把N+1级程序全部变换成N级程序后，再去执行 新产生的N级程序，在执行过程中N+1级程序不再被访问。解释：每当一条N+1级指令被译码后，就直接去执行一串 等效的N级指令，然后再去取下一条N+1级的指令，依此 重复进行。,解释执行比翻译花的时间多，但存储空间占用较少。,第一章 计算机体系结构的演变,1.计算机体系结构的定义：程序员所看到的计算机的属性，即概念性结构与功能特性。2.按照计算机系统的多级层次结构，不同级程序员所看到的计算机具有不同的属性。3.透明性 在计算机技术中，对这种本来是存在的事物或属性，但从某种角度看又好象不存在。,第一章 计算机体系结构的演变,4.Amdahl提出的体系结构：传统机器级的体系结构。即一般所说的机器语言程序员所看到的传统机器级所具有的属性。,5.对于通用寄存器型机器，这些属性主要是指：,(1)数据表示（硬件能直接辩认和处理的数据类型）(2)寻址规则（包括最小寻址单元、寻址方式及其表示）(3)寄存器定义（包括各种寄存器的定义、数量和使用方式）,第一章 计算机体系结构的演变,(4)指令集（包括机器指令的操作类型和格式、指令间的排 序和控制机构等）(5)中断系统（中断的类型和中断响应硬件的功能等）(6)机器工作状态的定义和切换（如管态和目态等）(7)存储系统（主存容量、程序员可用的最大存储容量等）,第一章 计算机体系结构的演变,(8)信息保护（包括信息保护方式和硬件对信息保护的支持）(9)I/O结构（包括I/O连接方式、处理机/存储器与I/O设备 间数据传送的方式和格式以及I/O操作的状态等）,经典计算机体系结构概念的实质：计算机系统中软硬件界面的确定，其界面之上的是软件的功能，界面之下的是硬件和固件的功能。,第一章 计算机体系结构的演变,计算机组成：计算机体系结构的逻辑实现。研究硬件系统各组成部分的内部构造和相互联系,以实现机器指令级的各种功能和特性,包括机器内部的数据流和控制流的组成以及逻辑设计等。目标是最合理地方式将各种设备和部件连接为计算机,以达到最优的性价比,从而实现所确定的系统结构2.计算机实现：计算机组成的物理实现。它包括处理机、主存等部件的物理结构,器件的集成度和速度,信号传输，器件、模块、插件、底板的划分与连接,专用器件的设计,电源、冷却、装配等技术以及有关的制造技术和工艺等。它着眼于器件技术和微组装技术。一种体系结构可以有多种组成;一种组成可以有多种物理实现。,第一章 计算机体系结构的演变,(2)IBM PC系列机（处理器、处理器字宽、主要I/O总线、存储空间、主要操作系统和计算机结构）,如：IBM 370系列有370/115、125、135、145、158、168等一系列从低速到高速的各种型号。,3.系列机(1)系列机 在一个厂家内生产的具有相同的体系结构，但具有不同组成和实现的一系列不同型号的机器。,第一章 计算机体系结构的演变,第一章 计算机体系结构的演变,第一章 计算机体系结构的演变,第一章 计算机体系结构的演变,计算机 PC和PC XT PC AT 80386 PC 80486 PC Pentium PCPentium II PCPentium III PCPentium 4 PC,时间19811982198519891993199719992000,处理器8088802868038680486PentiumPentium IIPentium IIIPentium 4,字宽16位16位32位32位32位32位32位32位,主要I/O总线PC总线AT（ISA）ISA/EISAISA+VLISA+PCIISA+PCI+AGPPCI+AGP+USBPCI-X+AGP+USB,存储空间20位24位32位32位32位32位32位32位,主要操作系统DOSDOS、XENIXDOS、Windows 3.0 DOS、Windows 3.1DOS、Windows 3.1Windows 95Windows 98、2000Windows Me、XP,第一章 计算机体系结构的演变,4.软件兼容:同一个软件可以不加修改地运行于体系结构相同的各档机器，而且它们所获得的结果一样，差别只在于有不同的运行时间。,第一章 计算机体系结构的演变,向上(下)兼容：按某档机器编制的程序，不加修改的就能运 行于比它高(低)档的机器。向前(后)兼容：按某个时期投入市场的某种型号机器编制的 程序，不加修改地就能运行于在它之前(后)投入市场的机器。,向后兼容是软件兼容的根本特征，也是系列机的根本特征。,5.兼容机 不同厂家生产的具有相同体系结构的计算机。,第一章 计算机体系结构的演变,1.3计算机体系结构的发展,存储程序计算机体系结构及其发展,第一章 计算机体系结构的演变,1.存储程序计算机的主要特点,(1)机器以运算器为中心；(2)采用存储程序原理；(3)存储器是按地址访问的、线性编址的空间；(4)控制流由指令流产生；(5)指令由操作码和地址码组成；(6)数据以二进制编码表示，采用二进制运算。,第一章 计算机体系结构的演变,2.对体系结构进行的改进,(1)分布的I/O处理能力 以运算器为中心带来了慢速输入输出操作占用快速运算器的问题。为了解决这一问题，人们提出了各种输入输出方式。,第一章 计算机体系结构的演变,第一章 计算机体系结构的演变,(2)保护的存储器空间,是否把指令和数据放在同一存储器中？优点:,不必预先区分指令和数据，易实现存储管理软件；程序和指令在执行过程中可以被修改，因而可以编写出灵 活的可修改的程序；对于存取指令和数据仅需一套读/写和寻址电路，硬件简单；数据可以分配于任何可用空间，从而可更有效地利用存储 空间等。,第一章 计算机体系结构的演变,缺点：,不利于进行程序调试诊断；不利于实现程序的可再入性和程序的递归调用；不利于重叠和流水方式的操作。,现在绝大多数计算机都规定，在执行进程中不准修改程序。,第一章 计算机体系结构的演变,(3)存储器组织结构的发展,相联存储器和相联处理机 通用寄存器 高速缓冲存储器和多级存储器组织结构,(4)并行处理技术 如何挖掘传统机器中的并行性？改进CPU的组成,重叠方式 先行控制,第一章 计算机体系结构的演变,在体系结构上对某些计算问题实现并行计算。如向量计算 多机并行处理系统 把一个作业(程序)划分成能并行执行的多个任 务(程序段)，把每个任务分配给一个处理机执行。,多操作部件 流水方式,第一章 计算机体系结构的演变,复杂指令集计算机(CISC)精简指令集计算机(RISC),(5)指令集结构的发展 指令集的功能,指令的地址空间和寻址方式 多种灵活的寻址方式。,第一章 计算机体系结构的演变,计算机的分代和分型1.计算机到目前为止已经发展了五代 这五代计算机分别具有明显的器件、体系结 构技术和软件技术的特征。2.计算机可以根据价格分为五个档次：巨型机、大型机、中型机、小型机、微型机,第一章 计算机体系结构的演变,3.计算机系统性能虽时间“下移”,第一章 计算机体系结构的演变,4.根据当前的计算机应用市场的现状和价格特征，通常把计算机分为服务器、桌面系统和嵌入式计 算三大领域。,第一章 计算机体系结构的演变,5.新型体系结构的设计(1)合理地增加计算机系统中硬件的功能比例，这种体系结构对操作系统、高级语言甚至应 用软件提供更多更好的支持；(2)通过多种途径提高计算机体系结构中的并行 性等级，使得凡是能并行计算和处理的问题 都能并行计算和处理，使这种体系结构和组 成对算法提供更多更好的支持。,第一章 计算机体系结构的演变,应用需求的发展 1.计算机的设计受两方面因素的影响2.软件技术最重要的发展趋势(1)程序及数据所使用存储器容量的不断增大；(2)编译器的重要性日益突出，逐渐成为用户 与计算机的主要界面。,计算机现在和未来的使用方法 下层的实现技术,第一章 计算机体系结构的演变,3.计算机技术和市场分化成为桌面计算、服务器和嵌入式计算三个部分，这三个不同的领域应 用需求的特点对计算机系统设计的影响巨大。,桌面计算市场是销售额最大的市场，是对性能价格比要求 最为苛刻和敏感的市场。服务器市场对计算机的要求是可用性、大容量和可扩展性。嵌入式计算与解决的应用问题密切相关，需求千差万别。,第一章 计算机体系结构的演变,计算机体系结构的研究包括硬件组织和程序设计软件需求两方面的内容从汇编程序员角度看计算机体系结构可以用指令系统来抽象，包括寻址方式、操作码、寄存器和虚拟存储器。从硬件实现看，抽象机由CPU、高速缓存、总线、微代码、流水线、物理存储器等,1.1 计算机体系结构的分类,1.1 计算机体系结构的分类,先行、并行性和流水线技术 先行：一次性多取一些指令放入先行栈中。I/E Overlap是指时间方面的重叠。由时间并行发展到功能并行。功能并行有两种形式：同时使用多个功能部件和不同级别使用流水线技术 指令执行流水线。算术计算流水线、存储器存取操作。,1.1 计算机体系结构的分类,1.1 计算机体系结构的分类,Flynn分类法 根据指令和数据流概念提出了不同计算机系统结构的分类法。SISD传统顺序及。向量计算机用标量和向量硬件装备，或者以SIMD机的形式出现。并行计算机一般属于MIMD机。MISD，执行不同的指令的时候，同一数据流通过处理机线性阵列。这种系统结构师流水线执行特定算法的波动阵列,1.1 计算机体系结构的分类,CU,PU,MU,IS,IS,DS,SISD,DS,IS,DS,DS,CU,IS,LM,PE,LM,PE,DS,SIMD,1.1 计算机体系结构的分类,MIMD,DS,CU,IS,PE,DS,MISD,I/O,共享存储器,I/O,共享存储器,CU,PE,IS,IS,IS,I/O,1.1 计算机体系结构的分类,并行/向量计算机真正的并行计算机是以MIMD模式执行程序的计算机。并行计算机有两大类，共享存储型多处理机和消息传递型多计算机。多处理机和多计算机交换数据的方式不同流水线向量处理机：M-M，R-R,1.1 计算机体系结构的分类,开发层次 硬件结构在不同的机器中不一样。主要与机器目标应用领域有关，由设计人员确定开发与硬件无关的程序设计环境。用户程序可以以最小的代价移植到不同的计算机上,与机器有关,与机器无关,1.1 计算机体系结构的分类,支撑语言和通信模型与计算机系统的结构有关。从程序员的观点出发，这两层是透明的。编译器和操作系统设计能够为程序员消除限制但是从结构设计师的角度看，需要同时考虑硬件和软件对开发的影响。影响并行发展和应用的还是软件方面问题,Moore定律：集成电路芯片的集成度每3年增至4倍：集成电路的特征尺寸随时间按指数规律减小。特征尺寸的减小一方面导致芯片上晶体管尺寸变小，晶体管数量增加，互联线缩短，工作频率提高，能实现更多功能 另一方面芯片总功率增加，散热困难。连线变细使电阻增大，线的时间常数增加，影响信号传输质量。Moore定律还能持续15-20年。但是处理器性能每年增加60%，存储器只增加7%，速度差距增大。,1.2 几个经验定律,Amdahl准则：一个平衡的计算机系统，其CPU每1MIPS的速度应有1MB的主存容量和1Mb/s的I/O吞吐率。Amdahl定律：设系统完成两类工作，分别占工作总量的和1-，当使完成的工作加快n倍时，系统的加速比S(n)=n/(+n(1-)。加快经常性事件的操作速度,1.2 几个经验定律,地址消耗法则：程序对主存容量需求的增加每年增加1.5-2倍，对应的地址码增加0.5-1倍。90/50成功转移法则：向后转移指令有90%的成功率，向前转移的指令有50%的成功率。为预测转移提供参考，影响流水线的因素。,1.2 几个经验定律,访存局部性原理：空间局部性和时间局部性。多层次存储系统存在的依据。90/10局部性原理：一个程序执行时间的90%用在程序10%的指令执行上。RISC和CISC这几准则。,1.2 几个经验定律,2:1cache法则：容量为C的直接相联cache的失效率与容量为C/2的二路相联cache的是失效率大致相同。用控制的复杂性换取cache容量的减小微缩化定律：做的越小，速度越快。,1.2 几个经验定律,1.3 微处理器,1979年Intel推出只有2250个晶体管、频率为108kHz的为处理器4004,2000年4200万个晶体管、频率可以达到1.5GHz的奔腾4。微处理器的晶体管增加4个数量级，频率也增加4个数量级，工艺从10um发展到0.18um，并发展到65nm。,提高微处理器性能的方法,指令的执行过程：从存储器取指令，译码，取操作数，控制相应功能部件进行规定操作，保存操作结果。提高计算机的执行速度就要对程序执行过程中涉及的指令部件、存储部件和功能部件进行加速，平衡它们之间的性能。防止指令流水线断流，提高存储器对指令和数据高带宽、低延迟的访问支持，减少功能部件的资源冲突。,提高微处理器性能的方法,主要措施：（1）提高主频：提高性能的最直接的方法。可以通过细化流水线。增加流水级数实现。但是往往会受到存储性能的限制。（2）多线程：可以隐藏访存延迟，是提高系统吞吐率的有效方法。（3）2Bump技术：脉冲上升沿和下降沿都进行信息的传送和接受，将频率提高两倍（4）提高IPC：每拍并行流出多条指令是标量处理器中多个功能部件并行工作,提高微处理器性能的方法,主要措施：（4）提供IPC的方法：超标量、超流水、超长指令字（5）合理分配软硬件功能：不经常使用的功能交由软件完成，经常使用的功能交由硬件完成。（6）优化片内cache（7）加大通用存储器（8）无序流出/乱序执行：不相关的指令中，后面的指令可以提前流出，提高IPC；无资源冲突的指令可以提前执行，减少功能部件和寄存器的空闲，提高计算速度。,提高微处理器性能的方法,主要措施：（9）预取：指令中增加具有按时功能的指令，提示硬件提前执行加载指令，隐藏访存的延迟（10）分支预测：硬件动态预测和软件静态预测。基于程序分支的历史记录来预测未来分支的趋势。设置踪迹缓存，记录程序执行的动态指令序列。,微处理器的发展,RISC-CISC-RISCRISC：指令格式固定，算术逻辑指令是单拍完成的，用简单的加载和存储指令支持存储器访存，硬连线控制逻辑，大的指令和数据cache，功能部件全部流水化，编译器可以优化代码。CISC有大量的用户和丰富的软件资源。CISC和RISC相互借鉴，出现了VLIW等新的EPIC体系结构。,微处理器的发展,现代计算机的组成不能仅仅用硬件来描述，一个完整的计算机系统应该包含指令系统、系统软件、应用程序和用户结构。计算问题-算法和数据结构高级语言-应用程序-操作系统-硬件组成-性能评价,微处理器的发展,性能评价,HLL高级语言,算法和数据结构,计算问题,映射,编程,绑定编译、加载,微处理器的发展,计算问题 数值计算：用复杂的数学公式进行整数或者浮点运算 商务公务中的字母数字处理：精确的事物处理、大型数据库管理和信息检索 人工智能（AI）：逻辑推理和符号处理,微处理器的发展,算法与数据结构 计算问题：专门的确定性算法和规则的数据结构 符号处理：用启发式或不确定性算法对大型数据库进行操作算法的提出和数据结构的实现需要多学科交叉配合。目前提出了很多确定性算法和启发式算法在并行计算机上的设计和映射问题,微处理器的发展,HLL编写的源代码通过编译器成为目标代码，目标代码经过汇编程序转换成机器能识别的机器码。加载程序通过操作系统内核启动程序执行。现代的高级语言都是在顺序语言的基础上开发来的，目前应用于并行系统的语言常见的有在传统语言上进行扩充，或者重新开发适合于并行系统的语言,微处理器的发展,编译器支持-改进编译器的三种方式 预处理程序：采用顺序编译器和目标计算机的底层程序库实现高级并行 预编译器：程序流优化、相关性检查和有限的优化来检测并行性 第三种：开发一种新的，并行化向量化的编译器。能自动检测目标代码的并行性，并将顺序结构转化为并行结构。但是现代的编译器无法检测所有的并行并自动进行需要用户显示表达编译,补充知识：1.4 多计算机和多处理机,共享存储型多处理机 UMA均匀存储器存取 NUMA-非均匀存储器存取 COMA只有高速缓存的存储器结构非共享分布存储器,1.4.1 共享存储型多处理机,UMA-均匀存储器存取。物理存储器被所有处理机均匀共享，并且所有处理机对所有存储字具有相同的存取时间,是否具备I/O能力对称多处理机非对称多处理机,1.4.1 共享存储型多处理机,1.4.1 共享存储型多处理机,假定经过共享存储器的处理机之间的每次通讯操作需要K个周期。假设取指令和加载数据的开销忽略不计。顺序机器上执行程序2N个周期。假设M个处理机，将循环操作分成M段，每段有L=N/M个元素。第一个循环可以在L个周期完成，第二部分循环可以在L个周期计算出M个部和，如后面图,1.4.1 共享存储型多处理机,每一对部分和的相加需要通过共享存储器，k个周期。为了计算m个部分和，设计一个l层二进制加法树，其中l=log2m。加法树用l（k+1）个周期合并m个部分和。这样 2L+l（k+1）个周期能够得到最终和,1.4.1 共享存储型多处理机,假设数组中有N=220个元素。顺序执行需要221个机器周期。假设通信开销k=200个周期，同时设M=256，则执行完成需要 213+1608=9800个机器周期。则性能提高为221/9800=2。也就是说我们用256个处理机的并行换来了214倍性能的提高，因为其中的通信开销,1.4.1 共享存储型多处理机,NUMA-非均匀存储器存取,1.4.1 共享存储型多处理机,COMA模型-是一种NUMA机的特例,D：高速缓存目录远程高速缓存的访问借助于分布高速缓存目录,1.4.2 分布存储型多计算机,1.4.3 MIMD计算机分类,并行计算机可以是SIMD结构，也可以是MIMD模型。SIMD不是规模可扩展的。未来的通用计算机系统结构的发展趋势是采用有全局共享虚拟地址空间的分布式存储器的MIMD结构。共享存储型多处理机可以看做具有单地址空间的系统。可扩展的多处理机或多计算机必须采用分布共享存储器，不能扩展的多处理机则用集中共享存储器,1.4.3 MIMD计算机分类,MIMD分类 1.集中式多计算机 2.多计算机多地址空间消息传递计算 3.多处理机单地址空间共享存储计算 4.分布存储型多处理机（可扩展）,1.5 多向量机和SIMD计算机,1.3.1 向量超级计算机,1.5.2 SIMD超级计算机,1.5.2 SIMD超级计算机,SIMD机器的操作模型可以用五元组表示：M=（N,C,I,M,R）其中N为机器的处理单元数；C为由控制部件直接执行的指令集；I为由CU广播至所有PE进行并行执行的指令集；M为屏蔽方案集；R是数据寻径功能集,1.6 PRAM和VLSI模型,PRAM-并行随机存取机VLSI-超大规模集成电路仅介绍理论模型,1.6.1 并行随机存取机,时间和空间复杂性 计算机求解一个规模为s的问题的算法复杂性取决于所需的执行时间和存储空间。时间、空间复杂性是问题规模的函数，用数量级符号表示的时间复杂性函数就是算法的渐近时间复杂性，一般复杂性计算都需要考虑最坏情况。渐近空间复杂性主要与大问题的数据存储有关，而程序存储的要求和输入数据的存储不计算在内,1.6.1 并行随机存取机,时间和空间复杂性 一般来看，并行复杂性应该比串行复杂性低，至少相近。这里我们只是考虑确定算法，其中每个操作步骤是唯一确定的。不确定算法可能产生结果集合中的一个结果，但是目前还不存在能运行不确定性算法的实际计算机。,1.6.1 并行随机存取机,NP完全性 如果存在一个多项式p(s)，对任何问题规模s的时间复杂性为O(p(s)，则算法具有多项式复杂性。具有多项式复杂性算法的问题集成为P类。能以多项式时间用不确定算法求解的问题集成为NP问题。NP包含P，因为确定算法是不确定算法的特殊情况。NPC完全难解问题,1.6.1 并行随机存取机,将几个数排序和对两个n*n矩阵相乘算法的多项式时间复杂性分别为O(nlogn)和O(n3)，这两个问题属于P类问题履行推销员问题复杂性为O(n22n)和复杂性为O(2n/2)的背包问题开发了一些非多项式算法，未找到确定性多项式算法，因此此类问题属于NP问题。,1.6.1 并行随机存取机,PRAM 模型:N-PRAM有一个全局可寻址存储器，存储器修改操作有四种可能ER（互斥读）EWCRCW,1.6.1 并行随机存取机,PRAM方案 EREW、CREW、ERCW、CRCW其中CW需要面对写冲突问题，写冲突可以用下面策略进行分解共用-所有同时进行的写操作将相同数据写入热点单元任选-选其中任何一个数据，其他忽略不计最小值；优先-对要写的数用求和或求最大值等函数组合,1.6.1 并行随机存取机,在一台处理机数为n3/logn的PRAM上，用O(logn)时间完成两个n*n矩阵的乘法首先假设最初处理机数n3个。用n3个处理机完成n3个乘法，为了得到矩阵结果，我们需要将这些乘法结果中的每n个乘积项用n3个处理机相加。需要O(logn)。但是在进行加法运算的时候最多有n3/2个处于忙绿状态,1.6.1 并行随机存取机,将处理机的数目将为n3/logn，则每个PE负责计算logn个乘积项并将它们求和。首先每个PE产生n/logn个部分和（本应该是n个部分和，但是没有求全），每一个部分和由logn次乘法和(logn-1)次加法完成。这样最后的加法能在log(n/logn)完成。所以执行时间为2logn-1+log(n/logn),1.6.2 VLSI 复杂性模型,VLSI电路下届：用VLSI芯片执行并行算法时对存储器，I/O机通信设备设置一定的限制得到的。AT2模型：其中A是用VLSI电路芯片完成给定运算的芯片面积，T为执行时间。设问题的规模为s。则有 AT2=O(f(s)A是芯片复杂性的度量，T是一个问题实例从加载输入到得到全部输出位置所需要的时间,1.6.2 VLSI 复杂性模型,芯片面积A的存储界限 许多计算在需要处理大型数据集时要受到存储器的限制，要在硅片上实现某种运算，如何密集地将信息安置在芯片上也会受到限制。计算对存储量的需求往往决定了芯片面积A的下限 芯片处理的信息总线可以看作是通过芯片面积的信息流。每一位流过芯片的一个单位面积。芯片面积实际上限制了存储在芯片上的位数,1.6.2 VLSI 复杂性模型,AT的I/O界限 AT代表了立方体的体积。当信息在T时间内通过芯片时，输入的位数不能超过此立方体的体积。AT可以反映I/O的界限 A相当于硅片上输入和输出地数据。最大的I/O就是由这个面积的大小决定的。T可以看做在基片上的计算时间。AT表示计算过程中通过芯片的信息总量,1.6.2 VLSI 复杂性模型,等分通信界限 根AT 主要指出芯片之间交换的最大信息量。也就是限定了计算的通信带宽。这就是AT2,