单词 | 极度并行算法 |
释义 | 【极度并行算法】 拼译:super-parallel algorithm 随着超级并行计算机与智能计算机进入并行计算(Parallel computiing)的时代,美、日与西欧正集中力量在这一高技术领域开展竞争。 “极度并行”一词是钱学森1987年在国防科工委组织的第1届全国并行算法学术讨论会上提出的。他按处理机的个数将并行计算划分为浅度并行(10~100个)、深度并行(100~10000个)与极度并行(10000个以上)3级,并指出:并行计算正朝着极度并行的方向发展。因为当时美国Thinking Machines公司生产的Connection Machine(CM机)有64K个(216=65536台)处理机,它能高效地进行图象处理。日本在完成第5代计算机计划(并行推理机PIM)之后,现在开始执行的实况计算计划Real-World Computing Project),它以神经计算(neuro-computing)与极度并行(superparallelism)为特征。各种拟物与仿生算法用于优化、搜索与学习推动了神经计算的发展。在大型科学计算方面,当前以每秒万亿次浮点运算为目标的并行计算计划正在进行。它也是以极度并行为手段的。据1992年2月13日《纽约时报》报导:IBM公司宣布它将建立一个名为高度并行超级机实验室,采用极度并行计算技术与传统的超级机挑战。CRAY计算机公司也宣布不再制造CRAY 3超级机,并放弃制造更高档的计算机来与极度并行机竞争。这表明:极度并行计算已是大势所趋。用于科学计算的世界第1台并行计算机ILLIAC IV,于1972年投入运行。它的64台处理机组成一个具环状特征的8×8网阵列。它的拓扑结构如同在汽车轮胎上的一张网:环面上(轮胎上)均匀分布着8个圆,每个圆上均匀分布着8台处理机,相邻的圆上对应的处理机相联。这种结构很容易扩充为一极度并行阵列计算机:即环面上均匀分布n个圆,每个圆上均匀分布m台处理机,即成为一个”×m阵列。这样一来,原来为ILLIAC IV设计的系统软件与算法就可转移到这一新的极度并行计算机上去。今天的大规模并行计算机(Massively Parallel Computer)大致都采用“类似”的可扩充拓扑结构模型。如Hypercube、CM-2、SUPRENUM、PAX等等。这样,既可保证系统的可扩张性,由浅度并行、深度并行到极度并行,又可保持不同并行度的计算机之间的软件、算法的继承性与兼容性。从硬件来说,极度并行计算的主要矛盾是:运算的超高速度与0/I及通讯的低速度之间的矛盾;从软件来说是并行算法的设计、编程与调度的困难。解决前一矛盾的主要手段是采用多媒体技术,如可视化技术;解决后一矛盾的方法是从根本上改变模拟复杂系统与非线性现象的计算模型,以实现算法的同步化。从极度并行计算的发展史看,它是沿两个方向进行的。一个是从解决大型科学计算问题与大规模数据处理而发展起来的,可划分为4个阶段:(1)并行计算机前期(1971年以前),即ILLIAC IV计算机投入使用以前,为并行计算预研期。(2)并行计算初期(1972~1981),即SIMD计算的实践期与MIMD计算的预研期。(3)并行计算全盛期(1982~1991),它以巨型并行机CRAY XMP的出现为标志。(4)并行计算成熟期(1992-),并行计算机的标准化与并行算法的软件化。极度并行计算的另一方向是神经计算。为开发智能计算机系统而研究的各种神经网络及其联接机制(connectionism)正是沿着这个方向前进的。典型的例子是Boltzmann机。人工神经网络的研究已有半个世纪的历史。但是直到现在还没有一台真正的神经计算机。人们通常以Hopfield于1985年构造的第1个有实用意义的模拟装置为转折点来划分神经网络的发展阶段。因此1985年以前只是神经网络的预研期。1985年以后国际上才进入神经网络研究的实践期。非线性现象的研究是推动计算机发展的动力。今天拥有了每秒百亿次浮点运算的计算机,现在又提出每秒万亿次的要求。它只有向极度并行方向发展才能满足非线性现象研究中对计算机效能不断增加的需求。但是并不是所有的非线性数学模型都适合于极度并行处理。物理学家为量子力学建立的一个描述宇宙在亚原子级上行为的“标准模型”就是这种例子。他们转而根据格子结构(Lattice gauge)理论的方法在并行计算机上进行模拟,这方法称离散的量子色动力学(quantum chromodynamics-QCD)模型。该模型定义在具有周期边界条件的四维超立方格子上。要在一个163×48(空间-时间)网格上进行约束近似的模拟计算,如果使用每秒亿次浮点运算(100Mflops)的超级计算机,通常也要花上几千小时。为了使误差控制在百分之几的水平,计算机的吞吐量至少还得提高几百倍。为此英、美、日、意等国的科学家采用大规模并行计算。日本星野力与白川友纪研制的QCDPAX,具有288个处理机,其峰速达9.2 Gflops.为了适应QCD计算机的需要,它正朝着极度并行的方向演化。另一个例子是流体流动的模拟。过去人们总是用NavierStokes方程来描述流体的宏观流动现象。1985年8月,Frisch,Hasslacher和Pomeau证明:人们可以用格子气方法(lattice gas method)来近似解Navier-Stokes方程。他们应用此法于1985年9月在Los Alamos成功地作了首例流体流过平板的计算。这是流体力学计算史上的一次突破:采用细胞自动机与统计力学的方法设计出一个模拟流体流动的时-空完全离散的格子气自动机(lattice gas automaton)模型。为流体力学计算的极度并行化开创了一个新天地。美法等国已研制成一些极度并行的格子气自动机(硬件)来进行流体力学计算。建立在细胞自动机理论基础上的各种复杂系统与非线性现象的自动机模型越来越多。武汉大学一批年轻的科学家将细胞自动机理论与可视化技术相结合探索求解非线性微分方程的新途径:数值计算中的极度并行算法。他们设计了一些多粒子、多速度的格子气自动机模拟流体的各种复杂运动,包括Benard花纹、射流、绕流,最近设计的一个带有随机碰撞规则的多粒子、多速度模型,成功地模拟了激波运动。模拟其他复杂系统与非线性现象的自动机模型的研究也进行得十分顺利。由于这些问题的传统解法都是建立在非线性微分方程的数值计算上,故不宜并行处理,而上述模型则是建立在细胞自动机理论基础上的,所以它们都是极度并行化的。为了要模拟大脑的并行信息处理功能,特别是记忆、搜索、学习、优化与推理等数值与非数值计算的功能,就希望研制一类具有上述功能的计算机。我们称上述功能为神经计算,或称具有上述功能的机器为神经计算机(或智能计算机)。“神经计算”(neuro-computing)是一个抽象的概念,是从人脑功能中抽象出来的。现在的计算机具有部分神经计算功能,人工神经网络也具有部分神经计算功能。比如“记忆”,各种机器的记忆方式与效率可以全然不同,但存储信息的功能则一样。计算机是将信息化成二进制数字的形式来存储的。人工神经网络是通过改变其拓扑结构(包括它的联接权)实现的。目前通用计算机强调数字信息的处理功能,其它信息都要先转化为数字信息才能进行处理,处理的方式通常是串行的,通过执行一系列指令来实现。人工神经网络则可以处理连续统信息(或模拟量),处理的方式通常是并行的。有各式各样的神经网络,从Hopfeild的电神经网络到日本三菱公司的光互连神经网络,以及一些抽象的神经网络模型,如Boltzmann机等,它们都具有某种神经计算功能。三菱电气公司制成的试验性“光互连神经计算机”,是一个能识别26个字母的3层神经网络。人工神经网络最基本的功能是学习,不同的神经网络采用不同的学习方法与策略,即学习算法。例如多层神经网络,它是由输入层、若干隐蔽层和输出层组成。通常采用误差反传学习算法。更一般的神经网络模型具有更强的知识表示、学习与优化功能。如波尔茨曼机(Boltzmann),其动态过程是“模拟退火算法”(Simulated annealing algorithm)决定的。神经计算的另一类演化算法是1975年由Holland发明的遗传算法(genetic algorthm)。它模仿生物进化过程。因为生物演化的过程就是生物对环境的适应与优化过程。它由选择、杂交、变异、繁殖等过程组成。既可用于搜索、优化,也可用于学习,它有可能成为神经计算的主要算法。神经计算可分成两类,一类称为“拟物”算法,如模拟退火算法、弹性网络算法等,它们模拟大自然中的物理、化学系统的能量极小化过程或渐近平衡过程;另一类称为“仿生”算法,如遗传算法、达尔文算法、神经网络算法等。它们模仿生物适应生存环境的过程。它们都是极度并行的。【参考文献】:1 Frisch U,et al.Physical Review Letters,1986,56:1505~15082 Hasslacher B.Los Alamos Science(Special Issue).1987,175~2173 康立山,等.数值计算与计算机应用,1988,9(3)4 康立山,等.数值计算与计算机应用,1988,9(4)5 Shirakawa T,et al.Proc.Supercomputing,1989,495~5046 Aarts E H L,et al.Simulated Annealing and Boltzmann Machines,Wiley,Chichester,1 9897 Golderg D.Optimization and Machine Learning,AddisonWesley,Reading,MA,19898 武汉大学并行计算研究室.武汉大学学报(自然科学版),1991,99 Amari S.Mathematical theory of neural learning,New Generation Compuing,1991,8(4)∶281~294(武汉大学陈毓屏副教授撰) |
随便看 |
科学参考收录了7804条科技类词条,基本涵盖了常见科技类参考文献及英语词汇的翻译,是科学学习和研究的有利工具。