算法设计与分析 算法设计与分析讲义chapter9.docVIP

算法设计与分析 算法设计与分析讲义chapter9 导读：就爱阅读网友为您分享以下“算法设计与分析讲义chapter9”的资讯，希望对您有所帮助，感谢您对92的支持! 第九章 并行算法的设计与分析 9.1 并行计算机系统的发展 自从四十年代第一台电子计算机问世以来，计算技术的发展异常迅速，对人类活动的各个方面都产生了深刻的影响。伴随着计算机的迅猛发展，计算机应用日新月异，从科学计算到人类智能的模拟，对计算机的处理能力提出了越来越高的要求。提高计算机的处理能力一直是计算机发展的源动力。计算机科学家一直在追求三Ｔ(Trillion，万亿)目标，即:每秒一万亿次的运算速度，一万亿字节的存储容量，每秒一万亿字节的数据通信能力。这三个目标的每一个都是现有超级计算机性能的一千倍。 在计算机问世后的数十年间，计算机始终沿袭着Von Neumann计算机结构的顺序操作方式。提高计算机的速度一直被认为是加快时钟频率。到70年代初，顺序运行速度的提高显著地减慢了，其主要原因是元器件的速度已接近物理极限。人们开始了新的探索。以Cray为代表的计算机科学家企图在这个瓶颈周围探索一条迂回道路。他们把器件更紧密地组合在一起以便最大限度地减少 他们把CPU电讯号的传递距离，并采用了新的电路散热技术。同时，他们也采用了并行化技术。 分成若干相互协作的子单元，并把这些子单元装配成一条计算流水线。这种方法导致了并行向量 CRAY RESEARCH公司的CRAY1和CRAY2计算机系统、处理计算机系统的出现。日本NEC公司 的SX-3计算机、日本富士通公司的VP-2600等都是并行向量处理系统的典型实例。这些机器的运算速度最多只达到5.5Gflops，距离每秒一万亿次还相距甚远。 日本的计算机制造者和CRAY寄希望于延用老的设计，使用砷化镓芯片取代硅芯片，以取得更高的速度。砷化镓芯片是以故障率高而昭著于世的。这种选择是一场代价昂贵的赌博。即使这种砷化镓计算机能够成功，也只能达到20Gflops的速度，距离一万亿次计算速度还相差50倍。 追求三Ｔ目标的另一种探索是增加计算机系统中处理器的数量。这种探索导致了大规模并行计算机(MPP)的出现。MPP计算机把大量的处理器集中在一起，以获得高速度。它把逻辑部件、存储器和通信网集成一体。通常，MPP计算机中的单个处理器的速度要比CRAY1的处理器慢，但是当我们把一个问题分解成许多子问题时，这个处理器集群就能以极高的速度来解决这个问题。第一台多处理器并行计算机Illiac是在1975年投入运行的。Illiac是一台由64个处理器组成的阵列式并行计算机。1982年，CRAY X-MP诞生。它把两台CRAY1处理器组合在一起。两个处理器共享一个公共存储器。两个处理器可以执行不同的指令流。CRAY X-MP是第一台超过CRAY1计算机的计算速度的超级计算机。1987年，Daniel Hillis的Connection Machine(CM)问世。CM计算机是一台彻底摆脱了Von Neumann结构的MPP计算机。 CM计算机问世后不仅站住了脚，而且取得了举世瞩目的迅猛发展，CM1、CM2和CM5先后投入市场。 CM计算机的出现使人们相信， 具有数万、数十