当前位置:文档之家› 高性能计算综述

高性能计算综述

高性能计算综述
高性能计算综述

高性能计算综述

**

**

摘要:高性能计算简称HPC(High Performance Computing),是计算机科学的一个分支,特指当今具有超强计算能力的一类计算机。它致力于开发高性能计算机,主要采用模拟方法,解算当今超大、超高、超复杂的计算任务,研究并行算法及开发相关软件。高性能计算已被公认为继理论科学和实验科学之后,人类认识世界改造世界的第三大科学研究方法。本文就这一领域技术的地位作用、优势、现状与发展、分类、技术难点和研究方向、应用、发展展望等问题作一概要介绍。

关键词:超级计算;高性能计算;高效能计算;大规模并行处理

1 引言

高性能计算( High Performance Computing,HPC)是计算机科学的1个分支,主要指从体系结构、并行算法和软件开发等多个方面研究开发高性能计算机的技术。高性能计算本身并没有确切定义,它是指通过一定途径,获得比当前主流计算机更高性能的计算能力的技术。

高性能计算已被公认为继理论科学和实验科学之后,人类认识世界、改造世界的第三大科学研究方法,是科技创新的重要手段。在当前社会情况下,高性能计算已经成为一个国家综合实力的体现,对国家战略的发展有着重要影响。目前,高性能计算技术已经广泛应用于航空航天、汽车制造、核试验模拟、军事情报搜集处理、天气预报等多方面。通过高性能计算,人们可以完成很多目前计算机无法完成的实验,既可以免除真实实验的巨大费用,又不会对环境造成任何的影响。

通常来讲,高性能计算有2种表现方式:①提升单机的计算能力;②通过网络连接多台计算机,进而提升计算能力。第一种方式多是指提升CPU的处理能力,而随着CPU主频的提高受制于制作工艺,CPU的发展方向已经由单核向多核发展。事实证明,很多情况下CPU 过多的核心反而会降低CPU的处理能力。近几年出现的GPGPU技术已经成为提升单机处理能力的主要技术。第2种方式是通过整合多台网络计算机而提升计算能力,因此性价比较高,已经逐渐成为主流方式。

2 高性能计算的地位作用

美国在计算机与信息技术领域,一直处世界霸主地位。高性能计算机与高性能计算技术被认为是美国国家的制高点技术,历届政府都高度重视,重点发展。克林顿总统时代,大力推进HPCC(High Performance Computing & Communications)计划,大力研制一代代新机

器,建设许多超级计算中心,利用高性能计算机解决许多科技方面的“大挑战问题”,推动众多科学和技术领域的大发展。HPCC计划还把因特网(Internet)公开民用,推向全球,推动了信息化时代的到来。布什总统时代,虽然重点是反恐,但对高性能计算的发展丝毫没有放松。2005年总统IT顾问委员会的专题咨询报告,再次提出“HPC是国家核心竞争力,要大力发展”。奥巴马总统执政以来,经济问题、医改问题一直是当务之急,但也没有放松HPC 发展。2011年1月25日总统国情咨文报告中,再提到中国拥有了世界上最快的计算机,美国决不能松劲。

科学技术发展历来依靠“理论、试验”,而今天“计算”已是第三手段,而且是越来越重要的手段。许多科技领域的发展已离不开“计算”,许多学科已与计算相互复合。HPC在国家科技、国防、产业、金融、服务、生活等方面都占有不可或缺的重要地位。譬如:核物理、核能、核动力、核安全技术;空气动力学(航天、航空、航海、高速运载器);大气、海洋与空间(天气与灾害预报,全球变暖);能源(油气勘探与开采,新能源);生命科学、生物工程、新药研制;新材料;高新制造(汽车、微电子);信息与社会安全(密码学、监控);数据中心与服务中心等等。

中国自1958年开始自主研制计算机,并用于解决中国国内的各种需求,成绩卓著。1983年国防科技大学研制成功中国第一台HPC机———银河亿次计算机YH-1,使中国成为继美、日后国际上少数能自主研制HPC机的国家之一。2010年8月国防科技大学为“ 国家超级计算天津中心”研制成功的天河机TH-1A,其计算速度在当年11月国际TOP500排名中,列世界第一,为国家赢得荣誉,为中国HPC发展与应用作出了新贡献。

全球HPC机的研制,美国占绝对优势,全球最快500台计算机中,美国研制的占3/4以上。其次是日本和中国,欧洲研制的极少。但世界各国都高度重视HPC能力的建设与应用,2011年6月底世界最高性能,500台计算机的装备使用情况如下:

美国:256台,世界绝对第一;

中国:62台,世界第二;

欧洲:125台,其中,德国30台,英国27台,法国25台;

亚洲:103台,其中除中国62台外,日本26台,其他国家拥有很少。

2011年6月底世界最快的10台机器(运算速度均达每秒1000万亿次以上),美国拥有5台,中国和日本各2台,法国1台。

高性能计算机的发展水平已经成为衡量一个国家高新科技水平和综合实力的重要标志。高性能计算机可以对所研究的对象进行数值模拟和动态显示,从而获得实验很难甚至无法得到的结果。它相对于理论科学和实验科学,有其独特的优越性。首先,高性能计算既免除了真实实验的昂贵代价,而且不会对环境产生任何影响,即所谓无损伤研究。第二,高性能计算可以实现全过程全时空的研究 ,获取研究对象发展变化的全部信息。第三,高性能计算可以低成本地反复进行,获得各种条件下全面系统的数据。

事实证明,有了高性能计算不再需要进行核试验,有了高性能计算可以预测海啸和地震

的危害,有了高性能计算可以通晓人类大脑的奥秘和生命的密码。在我国为满足国民经济发展的需要,高性能计算的需求正在迅速增长。无论是国家安全、石油气象等主要领域,还是以生物医药、微观结构研究为代表的新一代科技,都高度依赖高性能计算。它们的发展很大程度上取决于高性能计算的发展。尤其是基础科学领域,对计算的需求永无止境,而且越高性能的计算机越能产生高精度高时效的成果。

3 高性能计算的优势

3.1 计算科学应用是高性能计算技术发展的源动力

计算科学的兴起是 20世纪后半叶最重要的科技进步之一,大大丰富了当今世界的科学研究活动。高性能计算作为计算的高端,代表计算机发展的方向和应用的前沿,更加得到关注和重视。有关高性能计算的突破和发展都被视为科技的重大进步,随着技术的下移,对相关产业的发展有广泛的带动作用。回顾历史,任何时候研制的最高性能的计算机总是服务于当时的科学计算需求,主要研究领域包括新型材料、药物设计、气候模拟、核武器模拟、电磁学、工业产品、海量数据处理、国防和安全等,或者称是以科学计算为最初应用的靶子进行设计的,如日本地球模拟器系统与IBM蓝色基因系统两个项目。而高性能计算机技术逐步向商用领域转移与转化,计算性能及与其相匹配的存储容量、互连网络带宽等指标成为高性能计算机设计者追求的持续关键指标。

我国早期的高性能计算机依赖于进口,极大地限制了应用,这也激发了我国自主研发高性能计算机的决心。随着自主研制的高性能计算机“神威”、“银河”、“曙光”等的发展,美国和日本对我国的限制也一步一步放宽,大型计算机的价格也在下跌。各种因素的综合促进了高性能计算的应用。近几年随着我国在高性能计算技术和应用方面的大力支持,我国各个领域的计算应用开始利用高性能计算工具,高校纷纷开设并行计算相关课程。随着社会信息化步伐的加快,高性能计算应用将快速发展。

3.2 高性能计算机研制推动应用的发展

经过近半个世纪的发展,高性能计算机从最初的向量计算机,历经对称多处理机(SMP)、大规模并行处理机(MPP),一直发展到机群系统( cluster )和星群系统(constellation ),实现了飞速发展。万亿(Tflops)、百万亿乃至千万亿(Pflops)次的高性能计算机将逐渐进入人们的视野。

近两年,关于研制千万亿次高性能计算机的讨论日渐火热。美日两国更是在千万亿次高性能计算机的研制上进行了激烈的竞争,相继推出千万亿次机器的研制计划。例如日本 Riken 高性能计算中心和NEC针对生化领域的MDGRAPE-3,预计在2008年安装在美国能源部橡树岭国家实验室的Cray Baker和IBM的蓝色基因P P计划等。目前预计千万亿次系统将在2009~ 2011年间集中涌现在我国,千万亿次高性能计算机的研制也提上了议事日程。根据十一五高

性能计算机研发计划,我国将在2008年完成2台百万亿次高性能计算机系统的研发,并适时推出千万亿次高性能计算机。

高性能计算机性能的提高必将推动应用的发展。在美国,高性能计算主要用于核武器研究、国家防御、国家安全、能源与环境、生物科学、地球科学、材料科学、天文学、药物设计、物理化学、电子器件及金融领域。日本的高性能计算主要为重大的科学探索和研究服务,如地球模拟器主要用于大气与海洋模拟、固体地球模拟、多尺度模拟等。欧盟国家投资高性能计算主要鼓励生命科学、信息技术、纳米技术、天文和空间科学、食品质量和安全、可持续发展等项目。我国高性能计算以经济发展为目的,涉及气象数值模拟与预报、地震预报、生物信息、药物设计、环境科学、空间科学、材料科学、计算物理、计算化学、流体力学、地震三维成像、油藏数值模拟、天体星系模拟、金融、制造等众多领域。

3.3 高性能计算应用促进科技创新和社会进步

随着研究的深入和竞争的加剧,各领域越来越多地使用高性能计算技术来解决科研和生产中的实际问题。高性能计算应用的发展不但促进了科技创新,也促进了社会的进步。高性能计算应用发展水平逐渐成为衡量一个国家综合国力和国际竞争力的重要指标。

国外的高性能计算应用已经具有相当的规模,在各个领域都有比较成熟的应用实例。在物理、化学、生物等科学研究领域已广泛利用高性能计算手段,在其它领域也广泛被应用。例如在政府部门大量使用高性能计算机,能有效地提高政府对国民经、社会发展的宏观监控和引导能力,包括打击走私、增强税收、进行金融监控和风险预警、环境和资源的监控和分析等等。例如在能源领域,世界上石油公司通过高性能计算机处理石油勘探数据,为能源的发现提供了支撑。在工业产品设计领域,例如美国通用机械(GM)和通用电气(GE)等跨国集团用网络将全球各地设计中心的服务器和贵重设备连接成一个整体,以便于工程师和客户共同设计产品,设计时间可缩短100倍。对很多大型企业来说,采购成本是总成本的重要组成部分,例如福特等集团用高性能计算机构造了一个网上集市,通过网络连到它的3万多个供货商。这种网上采购不仅能降低价格,减少采购费用,还能缩短采购时间。此外,制造、后勤运输、市场调查等领域也都是高性能计算机大显身手的领域。随着“网络计算”和“后PC时代”的到来,全世界将有数十亿的客户端设备,它们需要连到数百万台高性能服务器上。高性能计算机将越来越得到产业界的认同,成为重要的设计、生产和管理工具。

高性能计算应用在高性能计算技术的支持下为我国的科技创新作出了巨大贡献,并且和高性能计算技术在相辅相成中不断发展。近年来,我国对大规模科学计算和高性能计算都给予了极大的重视和投入。国家973计划和863计划均有对高性能计算方面的大量投入,而且包括计算机界的许多学者认识到应用的重要性,特别是高性能计算的应用,给予了高度的关注。在传统的高性能计算应用领域如国防安全,核爆模拟,石油勘探数据处理,天气预报,洋流研究等有更大的发展。在新的应用领域,如生物信息,基因,纳米材料,微电子,工业产品设计和制造等方面也有很快的发展。在信息处理领域,政府、金融、流通领域纷纷用高

性能计算资源处理海量数据。高性能计算的应用得到各方面的关注和重视。

高性能计算相对于理论科学和实验科学,有其独特的优越性。首先,高性能计算既免除了真实实验的昂贵代价,而且不会对环境产生任何影响,即所谓无损伤研究。第二,高性能计算可以实现全过程全时空的研究,获取研究对象发展变化的全部信息。第三,高性能计算可以低成本地反复进行,获得各种条件下全面系统的数据。事实证明,有了高性能计算不再需要进行核试验,有了高性能计算可以预测海啸和地震的危害,有了高性能计算可以通晓人类大脑的奥秘和生命的密码。

3.4 网格是高性能计算应用发展的新趋势

21 世纪网络化是高性能计算应用最重要的趋势,网格(grid)已经成为高性能计算的一个新研究热点。用美国网格计算领导人Foster的话来说,网格是构筑在互联网上的一组新兴技术,它将高速互联网、高性能计算机、大型数据库、传感器、远程设备等融为一体,为科技人员和普通百姓提供更多的资源、功能和交互性,让人们透明地使用计算、存储等其他资源。

在网格方面美国大大领先于其他国家,美国当前对于网格研究的支持可与其70年代对Internet研究的支持相比,10 年后可望普及到国民经济和社会发展的各个领域。TeraGrid 是由美国国家科学基金会发起,由9个超算中心和国家实验室针对科学研究中出现的资源共享、合作研究等问题提出的。T eraGrid利用高性能网络,将分布在全国的高性能计算机、高端科学仪器、数据资源连接在一起,具有超过102Tflops的计算能力和15PB的存储能力。其他国际上比较知名的网格还有欧盟的EGEE、英国的 e -Science和环太平洋网格应用与中间件联盟PRAGMA等。

我国对网格技术的研究也给与大力支持,十五、八六三计划的高性能计算专项和软件专项等重大科研项目都与网格技术有关。中国国家网格(China National Grid, CNGrid)就是“八六三计划”高性能计算机及其核心软件,重大专项支持建立的网格示范平台。CNGrid一期项目有8个计算结点遍布全国六大城市,总计算能力达到16Tflops,存储能力达到200TB,已经支持科学研究、资源环境、制造业和服务业的11个行业应用,包括资源环境网格、航空制造网格、气象网格、科学数据网格、新药研发网格、森林资源与林业生态工程网格、生物信息网格、教育网格、城市交通信息服务网格、仿真应用网格和国家地质调查网格。

3.5 发展公共超级计算中心具有战略意义

超级计算中心是一个现代发达国家不可缺少的信息基础设施。从全球来看,超级计算中心在主要工业化国家和第三世界的部分大国都有部署,都得到政府的大力支持,超级计算中心由政府为主投资进行设备更新和运营支持是全球的普遍模式。我国目前为数不多的超级计算中心由特定的部门建设和应用,有部分的开放,但很难被外界使用。国家科技部和教育部也曾经投资建设了一些高性能计算中心,但缺乏长期持续的支持和发展。近年来有地方政府建立超级计算中心,但缺乏国家级的高性能计算中心,缺乏长远的规划和目标。

从我国的国情出发,设立少数公共超级计算中心不仅能满足我国高性能计算的强烈需求,

同时能使有限的资源得到最有效的利用。众所周知,高性能计算机的发展速度快,初始投资和日常维护都需要大量的资金,如果机器在生命周期内不能最大效益的发挥作用,必然形成资源浪费。一个部门和机构很难建立大规模的计算中心,但峰值的需求又不能得到满足。超级计算中心有大量的用户,各用户之间对资源的峰值需求有交错性,从而使超级计算机保持稳定的高利用率。超级计算中心的初始投资和运营维护费用分摊到所有用户上,能大量节约社会投资,提高政府资金的效率。客户能够使用的高性能资源超出了自身能够建设的范围,但成本却大大降低。所以超级计算中心在美国又被称作“Cycle Shop”。

超级计算中心在高性能计算产业链中扮演着独特的承上启下的重要作用。超级计算中心直接面对高性能计算终端用户,深刻理解用户的需求、各类应用特点,其经验对于高性能计算软硬件厂商非常重要,对高性能计算用户的培养和教育对于扩大高性能计算市场极其重要。同时目前绝大多数的超级计算中心的非盈利特性,使得其没有把运行重点放在直接经济利益回报上,从而能够代表政府去做与产业集合紧密、合作各方多赢的事情。这都有利于一个健康、良好、多赢的高性能计算市场的形成和发展。超级计算中心要自觉地、主动地在学术和市场间广泛合作,游刃有余,串接起不同的价值链,让更多的人力资源、资金、技术、商誉更快地流动和转移。

超级计算中心是各学科知识聚集融合的场地,远远有别于一个单纯在计算机科学方面开展研究的IT研究机构 ,对于推动高性能计算应用的深度和广度至关重要。通过各类基础科学、工程科学的各类科学家和专业技术人员与计算机专家、计算科学专家的互动,能积累丰富的经验、知识和成果。同时,超级计算中心在多学科交融的过程中,可以有更多的机会、更创新的模式为国家知识创新、科技创新提供更有效的支撑。

4 现状与发展

4.1 高性能计算的现状与发展

高性能计算与传统计算相比较,其最大特点是速度快、计算结果精确。而对高性能计算的研究也正围绕着这样一个特点,主要从两个方面进行研究:①致力于开发尖端高性能计算机。②利用现在迅猛发展的网格技术,实现高性能计算。

自1946年第一台计算机ENIAC在宾夕法尼亚大学问世以来,在这短短的50年左右的时间里,"冯、诺依曼"体系的高性能计算机的迅猛发展,并且日益走向成熟

大体来讲,高性能体系结构主要包括:"Cra式"的向量超级计算机集群、可扩展的单处理器和多处理器集群。目前集群系统也正从大规模并行计算机和运行专用软件的集群向运行标准软件的专用集群和由商用硬件和软件自制而成的 Beowulf系统集群系统转变。

网格计算是网络技术发展的新阶段。我们采用网格技术可以将Internet或者某个局域网中的所有这些闲置的软件或者硬件资源都联系起来形成一个潜在的资源池,产生了强大的计算能力。当用户需要进行大规模计算时,他可以使用这个资源池里的资源进行计算,这时就

像家里的用电不需要考虑我们所使用的电源是由哪个发电厂生产的一样,不需要考虑所使用的具体资源所在的位置。这样的话,不管是何时何地,我们的计算机资源都能得到合理的应用,而且能够得到一个理想的计算效果。

在未来的高性能计算的发展中,尖端的高性能计算机是网格计算中的重要计算资源,而网格技术也为未来取得一个高性能计算的能力提供了一个优良的环境。

4.2 中国高性能计算的现状与发展

由于我国在高性能计算技术上起步比较晚,工业水平及相应的经济发展程度低,再加上美国等西方国家一直把高性能计算技术作为重要的战略资源,长期以来对我国的实行全面的封锁和禁运,一直以来我国的高性能计算技术远远地落后于世界先进水平。

20世纪90年代以来,随着“神威”、“银河”、“曙光”、“深腾”等一批知名产品的出现,我国成为继美国、日本之后的第三个具备高性能计算机系统研制能力的国家,被誉为世界未来高性能计算市场的“第三股力量”。我国在高性能计算机研制方面取得了较好的成绩,掌握了研制高性能计算机的一些关键技术,参与研制的单位也由科研院发展到企业界,有力地推动了高性能计算的发展。目前,我国的高性能计算环境已得到重大改善,总计算能力与发达国家的差距逐步缩小。我国的高性能计算技术拓宽了我国科学技术研究的深度和广度,提高了我国工业的生产效率,同时也节约了很多生产成本。我国的高性能计算技术目前主要在石油行业、天气预报、核能模拟、生物工程等领域得到了广泛的应用。

但是中国高性能计算的应用还不够广、不够深入,应用水平和应用效率都比较低下。我国对高性能计算应用的投入还远远不够,应用研发力量薄弱且分散,缺乏跨学科的综合型人才,从事高端应用软件研发的单位很少,企业界基本未介入,没有良好的相互交流的组织渠道等。高性能应用软件的开发和高效并行算法研究尚不能与高端计算机发展同步,在一定程度上存在为计算机“配”软件的思想。我国高性能计算应用的研究与发明明显滞后于高性能计算机的发展。国外品牌还占领着很多关乎国计民生的关键领域和行业,国产高性能服务器的市场份额仍然偏低。

4.3 高性能计算的发展阶段

自1946年ENIA诞生以来,人们就没停止对高性能计算的追求,总体经过以下几个阶段:

4.3.1 PVP

20世纪70年代出现的向量机可以看作是第一代的高性能计算机,以Cray Research公司开发的 Cray系列计算机为代表。当时的并行向量机( Parallel VectorProcessing,PVP) 通过增加处理器个数、扩展存储器的方式不断提升计算能力,占领高性能计算市场达20年之久。其架构如图 1 所示,不过随着并行向量机处理器数目的增加,使得定制费用和维护费用越来越昂贵,性价比越来越低,已难以满足高性能计算机市场化的要求。这个类型的计算机以 CDC公司的CDC8600和CDC STAR- 100为代表。

4.3.2 SMP

随着大规模集成电路的出现,微处理器应运而生.随着微处理器性能的不断提高,对称多处理( Symmetric Multi-Processing,SMP)计算机取代了 PVP,直接导致并行向量机退出了高性能计算市场。这种技术在IL-LIAC IV时代就开始尝试应用了,其架构如图 2 所示:

但是SMP计算机可扩展的处理器数目有限,加之对I /O和存储器操作的不便都限制了其发展。

4.3.3 MPP

20世纪90年代初,大规模并行处理(MassivelyParallel Processing,MPP)成为HPC发展的方向,并以ILLIAC IV和Cray I为代表,MPP架构下多个节点间通过网络进行连接,微处理器之间通过消息传递进行通讯。如图3所示,MPP系统使用专门的网络和操作系统,而与此同时,随着个人 PC 的发展,集群出现了。

4.3.4 集群

集群是价格低廉并且方便的高性能计算方法,通过本地网络连接多台计算机来共同完成工作,集群中的计算机处于平等地位,通过相互协作完成计算。集群以较低的成本获得计算能力大幅度的提升,使高性能计算趋于平民化。集群结构如图4所示,集群获得了计算能力成倍的提高,与之相伴的就是并行与分布式计算技术。

并行计算(Parallel Computing,或并行处理、平行计算)一般是指许多指令得以同时进行的计算模式。分布式计算(Distributed Computing)是一种把需要进行大量计算的工程数据分成小块,由多台计算机分别计算,上传运算结果后,将结果统一合并得出数据结论的计算模式。目前实现并行与分布式计算最常见的技术是PVM和MPI。MPI已经成为并行计算的标准。

集群的扩展毕竟是有限的,于是人们想将互联网上尽可能多的闲置计算机资源纳入到集群中来,这样就产生了网格计算技术,网格计算是分布式计算的1 种。

4.3.5 网格

网格(Grid)这个词源于电力网格(Power Grid)。“网格”与“电力网格”形神相似。一方面,计算机网纵横交错,很像电力网络;另一方面,电力网格用高压线路把分散在各地的发电站连接在一起,向用户提供源源不断的电力,用户只需插上插头、打开开关就能用电,不需要知道电能是从哪个电站送来的,也不需要知道它是水电、火电还是核电。建设网格的目的也是一样,其最终目的是希望它能够把分布在因特网上数以亿计的计算机、存储器、贵重设备、数据库等整合起来,形成一个虚拟的、空前强大的超级计算机,以满足不断增长的计算、存储需求,并使信息世界成为一个有机的整体。网格的架构如图 5 所示:

网格本质上是计算机集群,但是与集群有所不同。集群只是将多台计算机通过网络连接在一起,通过软件分工合作,来共同完成任务,然后将结果反馈集中。对用户来讲,面对的好像不是多台计算机的集群,而是1台计算机。集群要提升计算能力,只能通过增加服务器1种途径。而对于1个集群来讲,能增加的服务器数量显然是有限的,这也就限制了集群计算能力的进一步提升,而且随着服务器数量的增加,集群的性价比也会不断地下降。而对于网格来说,它面对的是整个因特网上的计算机,理论上具有无限扩展的可能,可以虚拟出空前强大的计算机。另外,集群在执行任务时要求集群中的每台计算机都是同构的,而网格则不需要。网格可以动态地获取限制资源并加以利用,也可以在任务完成后马上释放资源,合理使用负载,而这一点集群是做不到的。

4.3.6 云计算

随着高性能计算技术的进一步发展,出现了“云计算”技术,云计算的核心思想是将大量用网络连接的计算资源虚拟化后进行统一管理和调度,构成1个计算资源池向用户按需提供服务。提供资源的网络被称为“云”,“云”中的资源在使用者看来是可以无限扩展的,并且可以随时获取,按需使用,按使用付费。云计算网络的架构如图6所示:

网格计算和云计算看起来比较相似,都是将网络上的资源形成1个资源池,然后按需分配给使用者,很多人甚至将云计算叫做“网格2.0” ,但实际上两者在本质上是有所不同的。

一般情况下,网格是针对某种具体的需求而开发出来的,用于完成特定的任务,因此会出现各种各样的网格,比如生物网格、地理网格、国家教育网格等等。网格的作用是为了获得更强大的计算能力,它将1个需要巨大计算量的任务细化成多个相互之间不关联的子任务,然后通过网格软件从纳入网格中的所有计算机资源中寻找空闲资源,将子任务分发给空闲节点进行计算。子节点在完成计算后会将结果返回进行汇总,然后再接收下个任务。若子节点在运算过程中发生崩溃,没能及时返回结果,也不会影响整个项目的进行,其所承担的任务

会被调度系统分配给其他的节点继续完成。从这一方面讲,作业调度是网格的核心价值,而云计算网络是通用的,目前还没有出现以某个具体应用命名的云网络。云计算网络的目的不再是单纯追求强大的计算能力,而更像是为了按需分配资源。比如某企业在云计算网络中租用了1台虚拟服务器,当某些特定时刻,计算量或者网络的访问量激增的时候,云计算网络会动态地增加该服务器的计算能力和网络带宽,以满足企业的需要。当需求变小的时候,云计算网络又会动态地释放部分资源,使资源的调度总是维持在一个比较合理的水平。企业只需要按照使用情况付费,而不需要像以前那样必须去购买能够满足最大需求的物理设备。

云计算作为一种新的高性能计算网络目前仍在发展中,上述几种高性能计算方式的优缺点总结如表1所示。

4.3.7 GPGPU

近几年,出现了GPGPU( General Purpose GPU 通用计算图形处理器),即使用GPU进行通用运算的技术,并由此产生了CPU + GPU的高性能计算方式。该方式下CPU专注于串行计算,而并行计算部分交由GPU 来完成。GPU 参与并行运算后,将计算机的运算能力提升了几倍到几十倍,将 PC 转变成了高性能计算机。

目前的GPU并行运算技术有2种,分别为NVIDIA公司的基于Geforce8以上显卡的 CUDA 技术和AMD公司的基于ATI显卡的 Stream 技术。而 Intel公司也在开发自己的 GPGPU技术。

5 高性能计算机的分类

依据市场对HPC机的应用需求,HPC机可以分为两大类:

(1)服务型(容量型)

1)普及计算型:一般的计算中心,面向各种各样用户算题需求,同时为多个用户算题服务,系统要易得,用得起,一般不特别追求计算高效高速,也不强调一个用户独霸全系统。

2)数据型:各种数据中心、服务中心,面向大量或巨量用户的同时访问,要求响应快、服务好。譬如Google搜索服务,全球有600万台服务器构成的HPC系统来支撑服务。

3)音视频型:视频制作,大片点播中心,网游支持中心等。譬如,“阿凡达”3D影片制作,

用了一台每秒运算205万亿次的HPC机,是HP公司生产的总共3.5万核的Cluster机。

这类HPC机大量需求,市场巨大。它要求便宜易得,用得起,其应用特性是同时为众多用户服务,高性能主要表现为巨大的用户量,故可称为“容量型HPC机”,是一群小鸡共同吃一堆谷物的方式。“商用CPU+商用互连网络+开源软件” 组成的cluster机非常合适。(2)计算型(能力型)

该型HPC机主要应用于大规模的科技工程问题计算求解,系统可以同时支持多个用户算题,但特别强调全系统同时为一个用户题高效便捷求解服务。机器能力表现为如同一头大象,可扛起千斤重担。这类机器被称为“能力型HPC机”,是高端HPC机,要求其大规模处理器的访存快捷、并行协同计算好、相互通信高效、机器能耗合理、系统可靠可维。无疑这类机器需要特殊设计、制作。

这类HPC机,市场需求不大,但是是高端需求,是技术制高点。能做这类机器的单位、公司全球仅少数几家。设计制作这类机器的技术途径大致有:①自己设计定制专用CPU;②商用CPU+自己设计定制的专用高效加速处理器,构成异构型机;③自己设计定制的高速高效互连网络。

6 高性能计算的主要技术难点和研究方向

架构HPC机至今唯一技术途径是:由CPU+本地存储器构成一个结点机,然后把大量结点机互连成系统,以大规模并行计算来获得高速、高性能。并行的结点机数或称“核”(core,可执行计算程序的基础单元)数,现已高达几十万个。HPC计算技术发展的难点均由此产生,规模越大,矛盾越突出,这可能是相伴HPC终身的永恒主题。高性能计算的主要技术难点是: (1)难用:如何把一个计算问题分解为可并行协同计算的几千、几万、几十万个小问题,即“大规模的并行算法”,是个巨大的难题;计算对象———数据,如何合理放置到几千、几万、几十万个结点上去,使核的计算能方便快速得到和交换数据(结点间数据交换是很低效的),是相关的又一大难题,即“数据流的组织”问题;人的思维及传统的程序概念是串行执行的,如此大规模的并行,程序怎么编,所编程序如何在结点机架构不同的系统间可移植,都是很困难的,即“可编程、可移植”问题。

(2)低效:由于上述的难题难以很好解决,实际问题的有限并行度与机器大规模并行的架构不匹配,高速运算能力与访存取数很慢的不匹配,结点机高性能与结点机之间的极慢的通信传输能力不匹配等等导致HPC机解算实际问题时低效,全系统的计算能力实际能用上的只有几成,譬如30%就不错了,差的只有5%。当然,对特定问题、针对特定的机器架构,由高手精心设计程序,也可以获得很高的可用率,这也是HPC机的魅力所在。

(3)高成本:大规模,几百个大机柜,成千上万个结点机,机器价格很高,1千万亿次/秒的HPC机要上亿美元,而巨大的功耗(兆瓦级)及相应的散热冷却,也代价高昂,年电费需上千万元,有人戏称买得起用不起。如此庞大系统,如此高功耗高热,又会使系统稳定可靠性大为降低,有的平均只能稳定几小时,系统维护成本也很高。

由此10年前就有人提出,高性能计算要向高效能方向努力,highperformance改为(或强调)highproduc-tivity。高效能就是要解决或缓解上述难题,其含义是:①提高:HPC系统的实用性能,HPC系统的可编程性,HPC系统的可靠、可信性;②同时降低:HPC系统的开发与硬件成本,HPC系统的运行成本(特别是功耗),HPC系统的维护成本。因此,HPC技术的主要研究方向是:

(1)高效能并行计算机体系结构:首先是处理器的高效架构,CPU既是高性能的核心动力,也是高性能的核心基础,单片上众核已是CPU的主流方向,Intel展示过80核的单片CPU;CPU内嵌加速处理器(如GPU)也是成功的方向;面向计算领域的专用新型异构众核体系结构,算法与体系结构紧密结合,可能是有前途的方向。

(2)以存储为中心的体系架构:访存速度的提升远落后于CPU计算速度的高速增长(即“存储墙”壁垒),如何加速数据流的提供是提高HPC计算效率的核心关键。目前流行的是越来越复杂的多级Cache(缓存),需要有创新思路和精巧的新设计。革命性的举措是以存储为中心来设计组织系统,让计算部件从目前的主导地位变为从属地位。但这一思想提出多年难有突破,也许专用机上有希望。

(3)基于光的高可扩展互联网络技术:HPC内大量结点机之间的互联网络是数据流组织及机间通信的渠道,是HPC效率发挥的关键。机间访问比结点机内部访问慢几个量级,提高互联网络的性能(带宽、时延)可大为提升HPC的效能,是 HPC机研制的核心技术。另一方面,光互连比电互连有许多优势,目前HPC机机柜之间已普遍采用光互连。下一步是在机柜内实现光互连,进一步在板内、以至芯片内采用光互连。这方面的研究在广泛深入展开,竞争极为激烈。光传输中一个重大技术壁垒是交换,目前仍借助电。如能突破“全光交换技术”,将是信息技术中的一次革命性的发展。

(4)多层次低功耗控制技术:HPC的高功耗是其发展的主要障碍之一,是影响成本、节能、系统可靠性的主要因素,降低功耗是一巨大挑战。目前接近10PFLOPS的顶级HPC机功耗达10兆瓦,若无有效技术创新,1EFLOPS(即1000PFLOPS)的HPC机功耗达1000MW,是无法接受的。控制、降低功耗要多层次上下功夫,芯片低功耗是基础,是最重要的举措。需要工艺、体系结构两方面的创新。此外控制硬件分而治之(不工作的部件降功耗,休闲),软硬件结合控制分而治之(编译给出部件忙闲状态,操作系统管理硬件资源)……也是重要技术途径。

(5)面向体系结构的编译与优化技术:大规模并行是编译和优化的大难题,几十万、上百万个核的并行编程与优化是巨大挑战。面向体系结构,算法、体系结构、编译三结合来研究,可能是一条有效的技术途径。面向新的体系结构,创新新的编程语言、编程平台、编程和优化工具,以隐藏复杂的体系结构,方便用户使用,提高硬件应用效率,是推广HPC机应用的重要工作。

(6)系统可靠稳定性:巨大的规模,巨大的功耗,使HPC机可靠性大为降低,以至不可接受。后果是大型算题经常中途夭折,得不到结果,大量浪费机器资源和人力资源。如何

把故障部件从系统中隔离出去,进行维修,修好再加入系统,这一全过程中仍保持系统及用户题计算持续有效运行是巨大挑战。有人已提出“连续故障”(即系统不断出故障,稳定工作时间很短)的概念,要求此时全系统不崩溃,仍能让联机用户题有效计算下去。

7 高性能计算的应用

在国际高科技竞争日益激烈的今天,高性能计算技术已成为体现一个国家综合实力的一种标志。最早高性能计算主要面向科学计算、数值计算等应用,例如:天气预报、航天飞行、地震资料处理、基因匹配与拼接研究等。在飞机制造方面,为了确保飞行的安全,飞机在飞行前必须经过大量的试验。传统的飞机设计通过"风洞实验",模拟飞机在空中飞行的环境,这需要逾亿元的费用,目前我们采用了高性能计算机来模拟仿真"风洞实验",从而精确计算各种指标。这样不仅使飞机研发周期缩短了,而且研发费用也大幅下降。

目前随着信息社会的迅猛发展,越来越多的领域都涉及到处理海量的数据。这些需求迫使高性能计算已经不只是局限在科学计算、国家高端科技上,在工业和商业领域也不断地体现其价值。例如:船舶设计、汽车制造、证券指数计算、电力安全评估、建筑工程抗震性评估、电磁辐射计算等。在大型建筑和桥梁的设计和施工过程中,设计者必须考虑到许多因素,诸如材料承受力、天气、温度、共振等方面,而且这些因素之间是互相关联,相互作用的。我们要保证建筑和桥梁在竣工后能够安全可靠地使用,必须充分分析这些所有因素相互作用对建筑和桥梁产生的所有影响,在这个分析过程中涉及到大量复杂的计算。采用高性能计算机辅助设计,在计算机中不仅计算各个因素所产生的影响,而且能够有很明显的视觉效果。这样不仅大大的提高了效率,减少了研发成本,而且设计出来的建筑、桥梁不但满足各项安全指标,而且还美观。

汽车设计方面,上海超级计算中心把基于大规模并行计算机和并行商业软件的计算资源提供给用户用于汽车碰撞模拟和汽车外形 CFD模拟,同时和专业工程咨询公司联合为汽车设计和制造厂家提供汽车设计的工程咨询服务。满足了不同用户、不同层次的需求,对推动中国汽车自主研发起到了重要作用。例如,目前典型的汽车碰撞计算题目规模在50万到80万有限元单元。用一般的工作站计算,需要100多小时,而使用“曙光4000A”的32CPU,可以在4小时内完成计算,对缩短汽车研发周期具有重大的作用。

航空航天是高性能计算传统的应用领域。飞机的外形布局、构形都需要通过计算和试验的方式进行筛选、优化、评定和验证。传统的风洞试验非常昂贵,而计算机模拟可以大大减少试验次数,同时加快研制进程。航空航天设计中采用了大量的计算模拟,这些计算需要大规模的计算机和商业程序。上海超级计算中心自2003年6月以来为上海飞机设计研究所提供支线飞机的空气动力学计算,计算规模达到了600万单元,至今共完成几百个飞行工况的计算分析,总机时超过了40万个CPU小时,获得的有效数据量超过800GB,为支线飞机的研制提供了重大保障。另一方面的应用,飞机大攻角气动特性分析需要更大规模的计算,上海超级计算中心利用“曙光4000A”对1300万网格的飞机CFD课题进行了计算,这也是目前国内

该领域最大规模的计算。物不仅阻碍节点移动,也限制了信号的无线传输,利用现有算法进行分簇,簇的数目将增多。OCA算法通过设置备用节点改善了网络的连通性,并且对最小ID 算法进行改进来减少簇的数目,降低簇的更新,从而适应了障碍物环境下的分簇。模拟结果表明OCA算法可以在一定程度上改善网络性能。

材料设计是高性能计算的重要应用领域。红外光电技术是世界各国政府共同关注的战略性高技术,目前国际上对红外光电功能材料的研究已从一般性常规的基本科学问题转向器件应用中高准确度物理模型的建立与相应的特定物性的科学研究。上海技术物理研究所利用“曙光4000A”主要研究红外光电子器件材料中的缺陷、杂质和沉积的量子特征体系对电子结构、声子结构和电导等物理性质的影响,计算的理论方法基于当今广泛采用的密度函数理论和线性响应理论。在长期的研究中得到了很有价值的成果。

地质勘探方面,高性能计算主要用于研究地震波在地下各种复杂介质中的传播规律,通过地球内部结构的研究,进行工业油气勘探和开发。在求解三维波动方程中庞大的计算量成为实际模拟面临的主要难题,而高性能计算机是使用维波动方程实现地震波传播数值模拟的重要保障。同济大学地球物理系和上海超级计算中心合作,实现了自行开发的波动方程数值模拟程序在超级计算机上的并行化,并对国外已完成的案例进行了对比计算,结果优于国外,同时对大庆油田陆相断陷模型进行了实际计算,获得了重要的地层发现。

市政工程方面,目前地震安全性评价仅限于对工程场地的地震动参数进行评价,并且仅采用一维等效线性模型计算土层的地震反应,没有考虑地面三维形状的影响和土层与结构的耦合效应。考虑地面三维形状和土层结构耦合效应的特大型工程地震安全性评价的核心是一个大规模非线性结构动力学正问题,采用普通计算机根本无法完成,必须采用大规模的超级计算机。上海交通大学,上海超级计算中心,上海隧道设计院,上海地震工程研究所针对特大型工程地震安全性评价的要求,设计并行算法,开发并行软件,利用上海超级计算中心的曙光 4000A超级计算机解决特大型工程地震安全性评价中的海量计算问题。应用于上海外环线沉管式隧道,复兴东路盾构式隧道,上海液化天然气工程,上海世博会变电站工程等重大工程的地震安全性评价,取得了出色的实用性成果。

总而言之,越来越多的领域应用到高性能计算技术,高性能计算不仅极大幅度地加快计算的速度,缩短了研制和生产周期,同时,其配套的一些技术如计算机仿真模拟、计算机辅助设计让生产和研制结果更直观呈现在我们面前。中国科学院计算技术研究所所长李国杰院士说,高性能计算机是真正的先进生产力,是最典型的第一生产力。它对保障国家安全、促进科技进步、推动经济发展有着不可替代的重要作用,被各个国家提到一个重要的战略地位。

8 展望未来

高性能计算的最终目标是应用。为了更好地完成预定的大规模科学计算任务,不仅要有好的高性能计算机,还要有与之相匹配的高质量的高性能应用。但是,目前我国高性能计算机的实用效率还停留在较低的水平,应用水平低成为高性能计算的薄弱环节。我国的高性能

计算事业要走可持续均衡发展的道路,如何使当前的建设成果充分发挥其效益并可持续发展,改善应用水平较低的现状,是我们必须思考的问题。

我国对加强高性能计算环境和超级计算中心建设一直给予高度重视和大量投入,,但是高性能计算环境建设不能盲目地以追求计算机峰值为目的,而是以应用需求为向导,以应用水平为依据,针对不同应用的计算特点,引进不同体系结构的计算机系统。在高性能计算环境建设中,还需要软件和硬件建设并重,优化编程模型和并行算法,改进操作系统、编译器等系统软件,加大自主软件的开发和集成力度,使高性能计算环境真正发挥应有的作用。在高性能计算环境运行过程中,需要加强管理,对作业进行合理调度,提高系统利用率。

高性能计算机的问世给科学研究及工农业生产等带来了前所未有的发展,同时对用户使用计算机也提出了更高的要求。高性能计算机规模的不断扩大、多核处理器的出现都加大了用户使用计算机的难度。针对拥有多处理器(核)的高性能计算机系统,开展操作系统多核版本的研究、多级并行编程模型、软件工具和编译器的开发、现有M PI,OpenM P编程模型的优化,并行算法的改进等工作,对提高应用软件在多核(16 核P节点)、流计算 ( IBM Cell,GPU) 等下一代计算机系统上的运行效率至关重要。并行应用的可扩展性也是百万亿次、千万亿次大规模计算机系统面临的一个很大的挑战。只有开发易于使用的高性能计算机系统,,进一步优化系统配置,根据用户的使用特点实现按需定制,降低高性能计算机的使用门槛,才能提高高性能计算机的实用效率。

高性能计算应用的目标往往是解决综合性、系统性的复杂问题,涉及问题抽象、模型建立、并行算法、并行编程、应用测试等多个领域。因此,加强既懂专业知识又懂计算科学的复合型人才的培养,及不同学科科技人员之间的交流与合作是当务之急。此外,需要积极拓展多种形式的国内外合作,建设各领域的应用网格系统,实现高性能计算资源的整合与共享,提高资源利用效率,为全国更多的用户提供高性能计算应用服务,推进中国网格技术与应用的发展。

参考文献

[1] 周毓麟, 沈隆钧. 高性能计算的应用及战略地位[J]. 中国科学院院刊, 1999(3):184-187.

[2] 韩冀中. 高性能计算技术的发展现状及趋势[J]. 中国工程科学, 2000, 2(1):85-86.

[3] 李根国, 桂亚东, 刘欣. 浅谈高性能计算的地位及应用[J]. 计算机应用与软件, 2006, 23(9):3-4.

[4] 郑晓鸣. 浅析高性能计算的现状与发展[J]. 福建电脑, 2007(2):211-211.

[5] 赵毅, 朱鹏, 迟学斌,等. 浅析高性能计算应用的需求与发展[J]. 计算机研究与发展, 2007, 44(10):1640-1646.

[6] 张军华, 臧胜涛, 单联瑜,等. 高性能计算的发展现状及趋势[J]. 石油地球物理勘探, 2010, 45(6):918-925.

[7] 周兴铭. 高性能计算技术发展[J]. 自然杂志, 2011, 33(5):249-254.

[8] 李波, 曹福毅, 王祥凤. 高性能计算技术发展概述[J]. 沈阳工程学院学报(自然科学版), 2012, 08(3):66-68+83.

并行计算综述

并行计算综述 姓名:尹航学号:S131020012 专业:计算机科学与技术摘要:本文对并行计算的基本概念和基本理论进行了分析和研究。主要内容有:并行计算提出的背景,目前国内外的研究现状,并行计算概念和并行计算机类型,并行计算的性能评价,并行计算模型,并行编程环境与并行编程语言。 关键词:并行计算;性能评价;并行计算模型;并行编程 1. 前言 网络并行计算是近几年国际上并行计算新出现的一个重要研究方向,也是热门课题。网络并行计算就是利用互联网上的计算机资源实现其它问题的计算,这种并行计算环境的显著优点是投资少、见效快、灵活性强等。由于科学计算的要求,越来越多的用户希望能具有并行计算的环境,但除了少数计算机大户(石油、天气预报等)外,很多用户由于工业资金的不足而不能使用并行计算机。一旦实现并行计算,就可以通过网络实现超级计算。这样,就不必要购买昂贵的并行计算机。 目前,国内一般的应用单位都具有局域网或广域网的结点,基本上具备网络计算的硬件环境。其次,网络并行计算的系统软件PVM是当前国际上公认的一种消息传递标准软件系统。有了该软件系统,可以在不具备并行机的情况下进行并行计算。该软件是美国国家基金资助的开放软件,没有版权问题。可以从国际互联网上获得其源代码及其相应的辅助工具程序。这无疑给人们对计算大问题带来了良好的机遇。这种计算环境特别适合我国国情。 近几年国内一些高校和科研院所投入了一些力量来进行并行计算软件的应用理论和方法的研究,并取得了可喜的成绩。到目前为止,网络并行计算已经在勘探地球物理、机械制造、计算数学、石油资源、数字模拟等许多应用领域开展研究。这将在计算机的应用的各应用领域科学开创一个崭新的环境。 2. 并行计算简介[1] 2.1并行计算与科学计算 并行计算(Parallel Computing),简单地讲,就是在并行计算机上所作的计算,它和常说的高性能计算(High Performance Computing)、超级计算(Super Computing)是同义词,因为任何高性能计算和超级计算都离不开并行技术。

数值分析综述-《数值分析与算法》徐士良

第2章矩阵与线性代数方程组 一般的线性代数方程组,A非奇异可根据Cramer法则求解方程唯一解但是它的计算量很大。 高斯消元法的算法时间复杂度是O(n3),可以解一系列的线性方程;所占数据空间符合原地工作的原则。但是算法对数值计算不稳定(当分母为0或很小时)。可以用在计算机中来解决数千条等式及未知数。不过,如果有过百万条等式时,这个算法会十分费时。 解决高斯法中的不稳定性,在每次归一化前增加选主元(列选主元、全选主元)过程。但是列选主元法仍不稳定,不适求解大规模线性代数方程组。全选主元的高斯消去法,则在复杂度降低的同时能够避免舍入误差,保证数值稳定性。 高斯-约当消去法算法产生出来的矩阵是一个简化行梯阵式,而不是高斯消元法中的行梯阵式。相比起高斯消元法,此算法的效率比较低,却可把方程组的解用矩阵一次过表示出来。线性代数方程组的迭代解法 简单迭代法:迭代格式发散但迭代值序列不一定发散,但收敛格式收敛,迭代值序列收敛于方程组的准确解与选取迭代初值无关。 雅可比迭代法: 计算公式简单,且计算过程中原始矩阵A始终不变,比较容易并行计算。但是收敛速度较慢,而且占据的存储空间较大,所以工程中一般不直接用雅克比迭代法,而用其改进方法。 高斯-赛德尔迭代法:较上面的迭代复杂,但是矩阵的条件相对宽松。 松弛法:需要根据经验去调整,收敛速度依赖松弛参数的选择,收敛条件的要求更宽松。共轭梯度法:是介于最速下降法与牛顿法之间的一个方法,它仅需利用一阶导数信息,但克服了最速下降法收敛慢的缺点,又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点,在各种优化算法中,共轭梯度法是非常重要的一种。其优点是所需存储量小,具有步收敛性,稳定性高,而且不需要任何外来参数。共轭梯度法不仅是解决大型线性方程组最有用的方法之一,也是解大型非线性最优化最有效的算法之一。 第3章矩阵特征值 乘幂法计算绝对值最大的特征值:其收敛速度受限于最大与次大特征值比值绝对值的大小,实际应用中采用加速技术。 求对称特征值的雅克比方法96:每进行一次选装变换钱都需要在飞对角线的元素中选取绝对值最大的元素,很费时间,雅克比过关法对此做了改进。 QR方法求一般实矩阵的全部特征值98下100下:重复多次进行QR分解费时,计算工作量很大。一般先进行相似变换然后进行QR分解。但是这样仍然收敛速度慢,一般是线性收敛。实际应用中使用双重步QR变换将带原点的QR算法中相邻两步合并一步,加速收敛避免复数运算。 第4章非线性方程与方程组 二分法:每次运算后,区间长度减少一半,是线形收敛。优点是简单,但是不能计算复根和重根。 简单迭代法:直接的方法从原方程中隐含的求出x,从而确定迭代函数 (x),这种迭代法收敛速度较慢,迭代次数多。 埃特金迭代法113中:对简单迭代进行改进,使在其不满足收敛条件下迭代过程也收敛,在其收敛时加快收敛速度,减少迭代次数降低时间复杂度。 牛顿迭代法:其最大优点是在方程f(x) = 0的单根附近具有平方收敛,收敛速度快。而且该法还可以用来求方程的重根、复根。缺点:初值的选择会影响收敛结果。 牛顿下山法:保证函数值稳定下降,且有牛顿法的收敛速度。

数值计算方法学习心得

数值计算方法学习心得 ------一个代码的方法是很重要,一个算法的思想也很重要,但 在我看来,更重要的是解决问题的方法,就像爱因斯坦说的内容比 思维本身更重要。 我上去讲的那次其实做了挺充分的准备,程序的运行,pdf文档,算法公式的推导,程序伪代码,不过有一点缺陷的地方,很多细节 没有讲的很清楚吧,下来之后也是更清楚了这个问题。 然后一学期下来,总的来说,看其他同学的分享,我也学习到 许多东西,并非只是代码的方法,更多的是章胜同学的口才,攀忠 的排版,小冯的深入挖掘…都是对我而言比算法更加值得珍惜的东西,又骄傲地回想一下,曾同为一个项目组的我们也更加感到做项 目对自己发展的巨大帮助了。 同时从这些次的实验中我发现以前学到的很多知识都非常有用。 比如说,以前做项目的时候,项目导师一直要求对于要上传的 文件尽量用pdf格式,不管是ppt还是文档,这便算是对产权的一种 保护。 再比如代码分享,最基础的要求便是——其他人拿到你的代码 也能运行出来,其次是代码分享的规范性,像我们可以用轻量级Ubuntu Pastebin,以前做过一小段时间acm,集训队里对于代码的分享都是推荐用这个,像数值计算实验我觉得用这个也差不多了,其 次项目级代码还是推荐github(被微软收购了),它的又是可能更 多在于个人代码平台的搭建,当然像readme文档及必要的一些数据 集放在上面都更方便一些。

然后在实验中,发现debug能力的重要性,对于代码错误点的 正确分析,以及一些与他人交流的“正规”途径,讨论算法可能出 错的地方以及要注意的细节等,比如acm比赛都是以三人为一小组,讨论过后,讲了一遍会发现自己对算法理解更加深刻。 然后学习算法,做项目做算法一般的正常流程是看论文,尽量 看英文文献,一般就是第一手资料,然后根据论文对算法的描述, 就是如同课上的流程一样,对算法进一步理解,然后进行复现,最 后就是尝试自己改进。比如知网查询牛顿法相关论文,会找到大量 可以参考的文献。 最后的最后,想说一下,计算机专业的同学看这个数值分析, 不一定行云流水,但肯定不至于看不懂写不出来,所以我们还是要 提高自己的核心竞争力,就是利用我们的优势,对于这种算法方面 的编程,至少比他们用的更加熟练,至少面对一个问题,我们能思 考出对应问题的最佳算法是哪一个更合适解决问题。 附记: 对课程的一些小建议: 1. debug的能力不容忽视,比如给一个关于代码实现已知错误的代码给同学们,让同学们自己思考一下,然后分享各自的debug方法,一步一步的去修改代码,最后集全班的力量完成代码的debug,这往往更能提升同学们的代码能力。 2. 课堂上的效率其实是有点低的,可能会给学生带来一些负反馈,降低学习热情。 3. 总的来说还是从这门课程中学到许多东西。 数值分析学习心得体会

潮流计算(matlab)实例计算

潮流例题:根据给定的参数或工程具体要求(如图),收集和查阅资料;学习相关软件(软件自选:本设计选择Matlab进行设计)。 2.在给定的电力网络上画出等值电路图。 3.运用计算机进行潮流计算。 4.编写设计说明书。 一、设计原理 1.牛顿-拉夫逊原理 牛顿迭代法是取x0 之后,在这个基础上,找到比x0 更接近的方程的跟,一步一步迭代,从而找到更接近方程根的近似跟。牛顿迭代法是求方程根的重要方法之一,其最大优点是在方程f(x) = 0 的单根附近具有平方收敛,而且该法还可以用来求方程的重根、复根。电力系统潮流计算,一般来说,各个母线所供负荷的功率是已知的,各个节点电压是未知的(平衡节点外)可以根据网络结构形成节点导纳矩阵,然后由节点导纳矩阵列写功率方程,由于功率方程里功率是已知的,电压的幅值和相角是未知的,这样潮流计算的问题就转化为求解非线性方程组的问题了。为了便于用迭代法解方程组,需要将上述功率方程改写成功率平衡方程,并对功率平衡方程求偏导,得出对应的雅可比矩阵,给未知节点赋电压初值,一般为额定电压,将初值带入功率平衡方程,得到功率不平衡量,这样由功率不平衡量、雅可比矩阵、节点电压不平衡量(未知的)构成了误差方程,解误差方程,得到节点电压不平衡量,节点电压加上节点电压不平衡量构成新的节点电压初值,将新的初值带入原来的功率平衡方程,并重新形成雅可比矩阵,然后计算新

的电压不平衡量,这样不断迭代,不断修正,一般迭代三到五次就能收敛。 牛顿—拉夫逊迭代法的一般步骤: (1)形成各节点导纳矩阵Y。 (2)设个节点电压的初始值U和相角初始值e 还有迭代次数初值为0。 (3)计算各个节点的功率不平衡量。 (4)根据收敛条件判断是否满足,若不满足则向下进行。 (5)计算雅可比矩阵中的各元素。 (6)修正方程式个节点电压 (7)利用新值自第(3)步开始进入下一次迭代,直至达到精度退出循环。 (8)计算平衡节点输出功率和各线路功率 2.网络节点的优化 1)静态地按最少出线支路数编号 这种方法由称为静态优化法。在编号以前。首先统计电力网络个节点的出线支路数,然后,按出线支路数有少到多的节点顺序编号。当由n 个节点的出线支路相同时,则可以按任意次序对这n 个节点进行编号。这种编号方法的根据是导纳矩阵中,出线支路数最少的节点所对应的行中非零元素也2)动态地按增加出线支路数最少编号在上述的方法中,各节点的出线支路数是按原始网络统计出来的,在编号过程中认为固定不变的,事实上,在节点消去过程中,每消去一个节点以后,与该节点相连的各节点的出线支路数将发生变化(增加,减少或保持不变)。因此,如果每消去一个节点后,立即修正尚未编号节点的出线支路数,然后选其中支路数最少的一个节点进行编号,就可以预期得到更好的效果,动态按最少出线支路数编号方法的特点就是按出线最少原则编号时考虑了消去过程中各节点出线支路数目的变动情况。 3.MATLAB编程应用 Matlab 是“Matrix Laboratory”的缩写,主要包括:一般数值分析,矩阵运算、数字信号处理、建模、系统控制、优化和图形显示等应用程序。由于使用Matlab 编程运算与人进行科学计算的思路和表达方式完全一致,所以不像学习高级语言那样难于掌握,而且编程效率和计算效率极高,还可在计算机上直接输出结果和精美的图形拷贝,所以它的确为一高效的科研助手。 二、设计内容 1.设计流程图

数值分析作业思考题汇总

¥ 数值分析思考题1 1、讨论绝对误差(限)、相对误差(限)与有效数字之间的关系。 2、相对误差在什么情况下可以用下式代替 3、查阅何谓问题的“病态性”,并区分与“数值稳定性”的不同点。 4、取 ,计算 ,下列方法中哪种最好为什么(1)(3 3-,(2)(2 7-,(3) ()3 1 3+ ,(4) ()6 1 1 ,(5)99- , 数值实验 数值实验综述:线性代数方程组的解法是一切科学计算的基础与核心问题。求解方法大致可分为直接法和迭代法两大类。直接法——指在没有舍入误差的情况下经过有限次运算可求得方程组的精确解的方法,因此也称为精确法。当系数矩阵是方的、稠密的、无任何特殊结构的中小规模线性方程组时,Gauss消去法是目前最基本和常用的方法。如若系数矩阵具有某种特殊形式,则为了尽可能地减少计算量与存储量,需采用其他专门的方法来求解。 Gauss消去等同于矩阵的三角分解,但它存在潜在的不稳定性,故需要选主元素。对正定对称矩阵,采用平方根方法无需选主元。方程组的性态与方程组的条件数有关,对于病态的方程组必须采用特殊的方法进行求解。 数值计算方法上机题目1 1、实验1. 病态问题 实验目的: 算法有“优”与“劣”之分,问题也有“好”和“坏”之别。所谓坏问题就是问题本身的解对数据变化的比较敏感,反之属于好问题。希望读者通过本实验对此有一个初步的体会。 数值分析的大部分研究课题中,如线性代数方程组、矩阵特征值问题、非线性方程及方程组等都存在病态的问题。病态问题要通过研究和构造特殊的算法来解决,当然一般要付出一些代价(如耗用更多的机器时间、占用更多的存储空间等)。 $ r e x x e x x ** * ** - == 141 . ≈)61

电力系统分析潮流计算例题

电力系统的潮流计算 西安交通大学自动化学院 2012.10 3.1 电网结构如图3—11所示,其额定电压为10KV 。已知各节点的负荷功率及参数: MVA j S )2.03.0(2 +=, MVA j S )3.05.0(3+=, MVA j S )15.02.0(4+= Ω+=)4.22.1(12j Z ,Ω+=)0.20.1(23j Z ,Ω+=)0.35.1(24j Z 试求电压和功率分布。 解:(1)先假设各节点电压均为额定电压,求线路始端功率。 0068.00034.0)21(103.05.0)(2 2223232232323j j jX R V Q P S N +=++=++=?0019.00009.0)35.1(10 15.02.0)(2 2 224242242424j j jX R V Q P S N +=++=++=?

则: 3068.05034.023323j S S S +=?+= 1519.02009.024424j S S S +=?+= 6587.00043.122423' 12 j S S S S +=++= 又 0346 .00173.0)4.22.1(106587.00043.1)(2 2 212122'12'1212j j jX R V Q P S N +=++=++=? 故: 6933.00216.112'1212 j S S S +=?+= (2) 再用已知的线路始端电压kV V 5.101 =及上述求得的线路始端功率 12 S ,求出线 路 各 点 电 压 。

kV V X Q R P V 2752.05 .104.26933.02.10216.1)(11212121212=?+?=+=? kV V V V 2248.101212=?-≈ kV V V V kV V X Q R P V 1508.100740.0) (24242 2424242424=?-≈?=+=? kV V V V kV V X Q R P V 1156.101092.0) (23232 2323232323=?-≈?=+=? (3)根据上述求得的线路各点电压,重新计算各线路的功率损耗和线路始端功率。 0066.00033.0)21(12.103.05.02 2 223j j S +=++=? 0018.00009.0)35.1(15 .1015.02.02 2 224j j S +=++=? 故 3066.05033.023323j S S S +=?+= 1518.02009.024424j S S S +=?+= 则 6584.00042.122423' 12 j S S S S +=++= 又 0331.00166.0)4.22.1(22 .106584.00042.12 2 212j j S +=++=? 从而可得线路始端功率 6915.00208.112 j S +=

数值分析综述报告

淮阴工学院 《数值分析》考试 ──基于Matlab的方法综合应用报告 班级:金融1121 姓名:姚婷婷 学号:1124104129 成绩: 数理学院 2014年6月7日

《数值分析》课程综述报告 前言: 数值分析也称计算方法,它与计算工具的发展密切相关。数值分析是一门为科学计算提供必需的理论基础和有效、实用方法的数学课程,它的任务是研究求解各类数学问题的数值方法和有关的理论。 正文: 第一章 近似计算与误差分析 1、产生误差的原因:①模型误差;②观测误差;③截断误差;④舍入误差。 2、四则运算的误差: ①加减法运算 ()()()****x y x y δδδ±=+ ②乘法运算 ()()() ****** *** ******xy x y xy xy xy x y x y y y x x x y x y y x δδδ-=-+-≤-+-?=+ ③ 除法运算: ()()() () () ***** ******* * * ** * * ** * *2 ** x x xy x y y y yy xy x y x y x y yy x x y y y x yy x y y x x y y δδ δ--=-+-=-+-= +?? ?≈ ??? 3、科学表示法、有效数字、近似值的精度 任何一个实数都可以表示成如下的形式: 其中:是正整数,是整数, 如果是数的近似值 并且 则称该近似值具有位有效数字(significant digit )。

此时,该近似值的相对误差为 另一方面,若已知 ()() *111 1021n r x a δ-≤ + 那么, ()()***1112110.10 211 102 r m n n m n x x x x a a a a δ----≤?=+≤ 即:*x 至少有n 位有效数字。 例: 3.141592653589793...π= 取其近似值如下: x*=3.14 x * =3.14159 x*=3.1415 x*=3.141 **213 100.314 110.0016...0.005101022 x x π--=?-=<=?=? **516 100.314159 110.0000026...0.00000510102 2 x x π--=?-=<=?=? **314 100.31415 110.000092...0.0001101022 x x π--=?-=<

最短路径的并行算法综述

最短路径的并行算法综述 SA02011105 陈艾 (aiai@https://www.doczj.com/doc/e42388984.html,) 摘要:最短路径问题是图论中的一个典范问题,它被应用于众多领域。最短路径问题可以分成两类:单源最短路径、所有顶点对间的最短路径。本文对最短路径的并行算法进行综述,并介绍目前最短路径问题中的一个热点问题K条最短路径。 关键字:最短路径,单源最短路径,所有顶点对间的最短路径,K条最短路径 A Summary on Parallel Algorthms for Shortest Path Problems SA02011105 CHEN Ai Abstract:The shortest path problem plays an important role in graph theory .It is applied to numerous area . It is composed of two parts: single source shortest paths and all pairs shortest paths. This paper presents a summary on parallel algorithms for the shortest path problems including introducing a hot issue k shortest paths in shortest path problems at present. Keywords:Shortest paths,Single source shortest paths,All pairs shortest paths,K shortest paths 1. 引言 二十世纪中后期,随着计算机的出现和发展,图论的研究得到广泛重视,最短路径问题是图论中的一个典范问题,它已经被应用于众多领域。最短路径问题最直接的应用当数在地理信息领域,如:GIS网络分析、城市规划、电子导航等。在交通咨询方面,寻找交通路网中两个城市间最短的行车路线就是最短路径问题的一个典型的例子。在网络通信领域,信息包传递的路径选择问题也与最短路径问题息息相关。举个例子,OPSF开放路由选择协议,每 1 SA02011105 陈艾

蒙特卡罗方法并行计算

Monte Carlo Methods in Parallel Computing Chuanyi Ding ding@https://www.doczj.com/doc/e42388984.html, Eric Haskin haskin@https://www.doczj.com/doc/e42388984.html, Copyright by UNM/ARC November 1995 Outline What Is Monte Carlo? Example 1 - Monte Carlo Integration To Estimate Pi Example 2 - Monte Carlo solutions of Poisson's Equation Example 3 - Monte Carlo Estimates of Thermodynamic Properties General Remarks on Parallel Monte Carlo What is Monte Carlo? ? A powerful method that can be applied to otherwise intractable problems ? A game of chance devised so that the outcome from a large number of plays is the value of the quantity sought ?On computers random number generators let us play the game ?The game of chance can be a direct analog of the process being studied or artificial ?Different games can often be devised to solve the same problem ?The art of Monte Carlo is in devising a suitably efficient game.

导数的数值计算方法[文献综述]

毕业论文文献综述 信息与计算科学 导数的数值计算方法 一、 前言部分 导数概念的产生有着直觉的起源,与曲线的切线和运动质点的速度有密切的关系.导数用于描述函数变化率,刻画函数的因变量随自变量变化的快慢程度.比如说,物理上考虑功随时间的变化率(称为功率),化学上考虑反应物的量对时间的变化率(称为反应速度),经济学上考虑生产某种产品的成本随产量的变化率(称为边际成本)等等,这些变化率在数学上都可用导数表示. 导数由于其应用的广泛性,为我们解决所学过的有关函数问题提供了一般性的方法,导数是研究函数的切线、单调性、极值与最值等问题的有力工具;运用它可以简捷地解决一些实际问题,导数的概念是用来研究函数在一点及其附近的局部性质的精确工具,而对于函数在某点附近的性质还可以应用另一种方法来研究,就是通过最为简单的线性函数来逼近,这就是微分的方法.微分学是数学分析的重要组成部分,微分中值定理作为微分学的核心,是沟通导数和函数值之间的桥梁, Rolle 中值定理, Lagrange 中值定理, Cauchy 中值定理, Taylor 公式是微分学的基本定理, 统称为微分学的中值定理,这四个定理作为微分学的基本定理,是研究函数形态的有力工具 ] 1[.在微分学中,函数的导数是通过极限定义的,但 当函数用表格给出时,就不可用定义来求其导数,只能用近似方法求数值导数] 2[.最简单 的数值微分公式是用差商近似地代替微商,常见的有 [3] . ()()() 'f x h f x f x h +-≈ , ()()() 'f x f x h f x h --≈, ()()() '2f x h f x h f x h +--≈ . 需要注意的是微分是非常敏感的问题,数据的微小扰动会使结果产生很大的变化] 4[.

数值分析实验报告总结

数值分析实验报告总结 随着电子计算机的普及与发展,科学计算已成为现代科 学的重要组成部分,因而数值计算方法的内容也愈来愈广泛和丰富。通过本学期的学习,主要掌握了一些数值方法的基本原理、具体算法,并通过编程在计算机上来实现这些算法。 算法算法是指由基本算术运算及运算顺序的规定构成的完 整的解题步骤。算法可以使用框图、算法语言、数学语言、自然语言来进行描述。具有的特征:正确性、有穷性、适用范围广、运算工作量少、使用资源少、逻辑结构简单、便于实现、计算结果可靠。 误差 计算机的计算结果通常是近似的,因此算法必有误差, 并且应能估计误差。误差是指近似值与真正值之差。绝对误差是指近似值与真正值之差或差的绝对值;相对误差:是指近似值与真正值之比或比的绝对值。误差来源见表 第三章泛函分析泛函分析概要 泛函分析是研究“函数的函数”、函数空间和它们之间 变换的一门较新的数学分支,隶属分析数学。它以各种学科

如果 a 是相容范数,且任何满足 为具体背景,在集合的基础上,把客观世界中的研究对象抽 范数 范数,是具有“长度”概念的函数。在线性代数、泛函 分析及相关的数学领域,泛函是一个函数,其为矢量空间内 的所有矢量赋予非零的正长度或大小。这里以 Cn 空间为例, Rn 空间类似。最常用的范数就是 P-范数。那么 当P 取1, 2 ,s 的时候分别是以下几种最简单的情形: 其中2-范数就是通常意义下的距离。 对于这些范数有以下不等式: 1 < n1/2 另外,若p 和q 是赫德尔共轭指标,即 1/p+1/q=1 么有赫德尔不等式: II = ||xH*y| 当p=q=2时就是柯西-许瓦兹不等式 般来讲矩阵范数除了正定性,齐次性和三角不等式之 矩阵范数通常也称为相容范数。 象为元素和空间。女口:距离空间,赋范线性空间, 内积空间。 1-范数: 1= x1 + x2 +?+ xn 2-范数: x 2=1/2 8 -范数: 8 =max oo ,那 外,还规定其必须满足相容性: 所以

基于GPU并行计算的图像二值化研究【文献综述】

文献综述 计算机科学与技术 基于GPU并行计算的图像二值化研究 引言: 图像是当今社会运用的越来越多的元素之一,不过是动画还是静态的图片都是图像的动静呈现,所以对图像的处理也就越来越得到人们的关注。图像重要性,图像处理就是在图像中得到可靠的信息。而图像的二值化处理也是当今正盛行的一种图像的处理方法,它把图像原始化,使得数据更加简单的表现。 本毕业设计是GPU与二值化的并行运算,这无疑就是一种加速算法,也就是讲在二值化处理本来就跟快的基础上,能够更快的读取图像中的信息,得到我们想要的数据。而现在最常用的一种加速算法就是CUDA算法,他的并行运算可以使得二值化运算提高几十倍,在图像处理中是一个很庞大的数据。CUDA的并行运算在处理小图像时并不能很明显的突出速度,但是当遇到有大量的图像需要处理,而且图像又很大的情况下,这种并行运算可以节省很多时间。 1图像处理简介 1.1图像处理的概念 图像处理一般指数字图像处理。数字图像是指用数字摄像机、扫描仪等设备经过采样和数字化得到的一个大的二维数组,该数组的元素称为像素,其值为一整数,称为灰度值。图像处理技术的主要内容包括图像压缩,增强和复原,匹配、描述和识别3个部分。 常见的处理有图像数字化、图像编码、图像增强、图像复原、图像分割和图像分析等。图像处理一般指数字图像处理。虽然某些处理也可以用光学方法或模拟技术实现,但它们远不及数字图像处理那样灵活和方便,因而数字图像处理成为图像处理的主要方面。 1.2 图像二值化技术的简介 首先,图像的二值化有利于图像的进一步处理,使图像变得简单,而且数据量减小,能凸显出感兴趣的目标的轮廓。其次,要进行二值图像的处理与分析,首先要把灰度图像二值化,得到二值化图像。所有灰度大于或等于阀值的像素被判定为属于特定物体,其灰度值为255表示,否则这些像素点被排除在物体区域以外,灰度值为0,

数值计算方法设计论文

课程设计(论文) 题目: 三次样条插值问题 学院: ___ 理学院 _ 专业: __ _ 数学与应用数学 班级:数学08-2班 学生姓名: 魏建波 学生学号: 080524010219 指导教师:李文宇 2010年12月17日

课程设计任务书

目录 摘要……………………………………………………………………… 一、前言………………………………………………………………… (一)Lagrange插值的起源和发展过程……………………………………… (二)本文所要达到的目的……………………………………………………… 二、插值函数…………………………………………………………… (一)函数插值的基本思想…………………………………………………… (二)Lagrange插值的构造方法……………………………………………… 三、MATLAB程序………………………………………………………… (一)Lagrange程序…………………………………………………………… (二)龙格程序………………………………………………………………… 四、理论证明…………………………………………………………… 五、综述……………………………………………………………………谢辞………………………………………………………………………参考文献…………………………………………………………………

摘要

前言 要求:500字以上,宋体小四,行距20磅,主要内容写该算法的产生及发展、应用领域等。 题目 整体要求:报告页数,正文在8页以上 字体:宋体小四(行距20磅) 内容:1、理论依据 2、问题描述 3、问题分析 4、求解计算(程序) 5、结论 注:(1)页码编号从正文页开始 (2)标题可根据情况自己适当改动 示例见下: 2判别…………………… 2.1 判……………… 2.1.1 判别……………… 所谓的判别分析,………………………………………………方法[3]。 2.1.2 判………………………… 常用的有四种判别方法:…………………………………………………步判别法[6]。 1. 马氏………………

数值计算方法第4次作业

第四章 问题一 一、问题综述 在离地球表面高度为y处的重力加速度如下: 计算高度y=55000m处的重力加速度值。 二、问题分析 以高度y作为自变量,重力加速度的值为因变量。得到以下信息: f(0)=9.8100; f(30000)=9.7487; f(60000)=9.6879; f(90000)=9.6278; f(120000)=9.5682; 本题要求的就是f(55000)的值。 以下将采用课堂中学到的Lagrange插值多项式法、Newton插值多项式法、分段低次插值法和样条插值法求解该问题。 三、问题解决 1. lagrange插值多项式法 对某个多项式函数,已知有给定的k+ 1个取值点: 其中对应着自变量的位置,而对应着函数在这个位置的取值。 假设任意两个不同的x j都互不相同,那么应用拉格朗日插值公式所得到的拉格朗日插值多项式为:

其中每个为拉格朗日基本多项式(或称插值基函数),其表达式为: 拉格朗日基本多项式的特点是在上取值为1,在其它的点上取值为0。 源程序lagrange.m function [c,f]=lagrange(x,y,a) % 输入:x是自变量的矩阵;y是因变量的矩阵;a是要计算的值的自变量; % 输出:c是插值多项式系数矩阵;f是所求自变量对应的因变量; m=length(x); l=zeros(m,m); % l是权矩阵 f=0; for i=1:m v=1; for j=1:m if i~=j v=conv(v,poly(x(j)))/(x(i)-x(j)); % v是l_i(x)的系数矩阵 end end l(i,:)=v; % l矩阵的每一行都是x从高次到低次的系数矩阵 end c=vpa(y*l,10); % 对应阶次的系数相加,乘以y,显示10位有效数字 for k=1:m f=f+c(k)*a^(m-k); end 输入矩阵 x=[0 30000 60000 90000 120000] y=[9.81 9.7487 9.6879 9.6278 9.5682] a=55000 再运行源函数,可得: c = [ -2.057613169e-23, 4.938271605e-18, -3.703703702e-14, -0.000002046111111, 9.81] f = 9.6979851723251649906109417384537

数值计算方法总结计划复习总结提纲.docx

数值计算方法复习提纲 第一章数值计算中的误差分析 1 2.了解误差 ( 绝对误差、相对误差 ) 3.掌握算法及其稳定性,设计算法遵循的原则。 1、误差的来源 模型误差 观测误差 截断误差 舍入误差 2误差与有效数字 绝对误差E(x)=x-x * 绝对误差限x*x x* 相对误差E r (x) ( x x* ) / x ( x x* ) / x* 有效数字 x*0.a1 a2 ....a n10 m 若x x*110m n ,称x*有n位有效数字。 2 有效数字与误差关系 ( 1)m 一定时,有效数字n 越多,绝对误差限越小; ( 2)x*有 n 位有效数字,则相对误差限为E r (x)1 10 (n 1)。 2a1 选择算法应遵循的原则 1、选用数值稳定的算法,控制误差传播; 例 I n 11n x dx e x e I 0 1 1 I n1nI n1 e △ x n n! △x0 2、简化计算步骤,减少运算次数; 3、避免两个相近数相减,和接近零的数作分母;避免

第二章线性方程组的数值解法 1.了解 Gauss 消元法、主元消元法基本思想及算法; 2.掌握矩阵的三角分解,并利用三角分解求解方程组; (Doolittle 分解; Crout分解; Cholesky分解;追赶法) 3.掌握迭代法的基本思想,Jacobi 迭代法与 Gauss-Seidel 4.掌握向量与矩阵的范数及其性质, 迭代法的收敛性及其判定。 本章主要解决线性方程组求解问题,假设n 行 n 列线性方程组有唯一解,如何得到其解? a 11x 1 a 12 x 2... a 1n x n b1 a 21x 1 a 22 x 2... a 2n x n b2 ... a n1x 1 a n 2 x 2... a nn x n b n 两类方法,第一是直接解法,得到其精确解; 第二是迭代解法,得到其近似解。 一、Gauss消去法 1、顺序G auss 消去法 记方程组为: a11(1) x1a12(1) x2... a1(1n) x n b1(1) a21(1) x1a22(1) x2... a2(1n) x n b2(1) ... a n(11) x1a n(12) x2... a nn(1) x n b n(1) 消元过程: 经n-1步消元,化为上三角方程组 a11(1) x1b1(1) a 21(2) x1a22(2 ) x2b2( 2 ) ... a n(1n) x1a n(n2) x2...a nn(n ) x n b n( n ) 第k步 若a kk(k)0 ( k 1)( k) a ik(k )(k )( k 1)( k )a ik(k )( k) a ij a ij a kk(k ) a kj b i b i a kk(k )b k k 1,...n 1 i, j k 1,....,n 回代过程:

P-Q分解法潮流计算方法改进综述

P-Q分解法潮流计算方法改进综述 摘要:本文介绍了P-Q分解法潮流计算方法的数学模型,简化假设及特点,总 结了P-Q分解法在低压配电网络中,随着支路R/X比值的增大所带来的迭代次数 增大和不收敛性的解决方法,及该方法在不同假设条件下收敛性,并提出了自己 的见解。 关键词: P-Q分解法;收敛性;大R/X比支路 1 潮流计算的数学模型 P-Q分解法又称为快速解耦法,是基于牛顿-拉夫逊法的改进,其基本思想是:把节点功率表示为电压向量的极坐标方程式,抓住主要矛盾,把有功功率误差作 为修正电压向量角度的依据,把无功功率误差作为修正电压幅值的依据,把有功 功率和无功功率迭代分开进行【1】。 对一个有 n 个节点的系统,假定第1个为平衡节点,第 2~m+1号节点为PQ 节点,第m+2~n号节点为PV节点,则对于每一个PQ或PV节点,都可以在极坐 标形式下写出一个有功功率的不平衡方程式: 这些假设密切地结合了电力系统的某些固有特点,作为电力系统潮流计算广泛使用的一 种算法,P-Q分解法无论是内存占用量还是计算速度方面都比牛顿-拉夫逊法有了较大的改进,主要反映在以下三点: ① 在修正方程式中,B’和B’’二者的阶数不同。B’为n-1 阶,B ‘’为m阶方阵,简化了牛 顿法的一个n+m-1的方程组,显著减少了方程组的求解难度,相应地也提高了计算速度。 ②用常系数矩阵B’和B’’代替了变系数雅可比矩阵,而且系数矩阵的元素在迭代过程中 保持不变。系数矩阵的元素是由导纳矩阵元素的虚部构成的,可以在进行迭代过程以前,对 系数矩阵形成因子表,然后反复利用因子表对不同的常数项△P/V 或△Q/V进行前代和回代 运算,就可以迅速求得电压修正量,从而提高了迭代速度,大大地缩短了每次迭代所需的时 间【2】。 ③用对称的B’和B’’代替了不对称的雅可比矩阵,因此只需要存储因子表的上三角部分,这样减少了三角分解的计算量和内存【2】。 3 P-Q分解法的收敛性改进 在各种文献中,都有对P-Q分解法从不同方面提出了讨论和改进,有些是对硬件的改进,如使用并行算法和相应的并行软件来替代原来的串行处理,有些是对算法程序做出了改进, 方法众多,不在此累述。但是我注意到,在实际应用中,由于理论与实际复杂多变的差别, 一些网络如果不满足P-Q分解法的前提假设,可能会出现迭代次数增加或不收敛的情况,而 一些病态系统或重负荷系统,特别是放射状电力网络的系统,也会出现计算过程的振荡或不 收敛的情况。针对此类异常网络,从网络参数改进的角度出发,对此做出了总结。 3.1 大R/X比支路的处理 一般来说,110KV以上的高压电力网中,输电线支路易满足R<

(整理)数值分析计算方法超级总结

工程硕士《数值分析》总复习题(2011年用) [由教材中的习题、例题和历届考试题选编而成,供教师讲解和学生复习用] 一. 解答下列问题: 1)下列所取近似值有多少位有效数字( 注意根据什么? ): a) 对 e = 2.718281828459045…,取* x = 2.71828 b) 数学家祖冲之取 113355 作为π的近似值. c) 经过四舍五入得出的近似值12345,-0.001, 90.55000, 它们的有效 数字位数分别为 位, 位, 位。 2) 简述下名词: a) 截断误差 (不超过60字) b) 舍入误差 (不超过60字) c) 算法数值稳定性 (不超过60字) 3) 试推导( 按定义或利用近似公式 ): 计算3 x 时的相对误差约等于x 的相对 误差的3倍。 4) 计算球体积3 34r V π= 时,为使其相对误差不超过 0.3% ,求半径r 的相对 误差的允许范围。 5) 计算下式 341 8 )1(3)1(7)1(5)1(22345+-+---+---=x x x x x x P )( 时,为了减少乘除法次数, 通常采用什么算法? 将算式加工成什么形式? 6) 递推公式 ?????=-==- ,2,1,1102 10n y y y n n 如果取 * 041.12y y =≈= ( 三位有效数字 ) 作近似计算, 问计算到 10y 时误差为初始误差的多少倍? 这个计算过程数值稳定吗 ? 二. 插值问题: 1) 设函数 )(x f 在五个互异节点 54321,,,,x x x x x 上对应的函数值为 54321,,,,f f f f f ,根据定理,必存在唯一的次数 (A ) 的插值多项式 )(x P ,满足插值条件 ( B ) . 对此,为了构造Lagrange 插值多项式 )(x L ,由5个节点作 ( C ) 个、次数均为 ( D ) 次的插值基函数

潮流计算-开题报告

科学技术学院毕业设计(论文)开题报告 题目:电力系统潮流分析计算机辅助设计 学科部:信息学科部 专业:电气工程及其自动化 班级:电气082班 学号:7022808070 姓名:黄义军 指导教师:刘爱国 填表日期:2011 年12 月 5 日

一、选题的依据及意义: 电力系统潮流计算是研究电力系统稳态运行情况的一种基本电气计算。它的任务是根据给定的运行条件和网路结构确定整个系统的运行状态,如各母线上的电压(幅值及相角)、网络中的功率分布以及功率损耗等。电力系统潮流计算的结果是电力系统稳定计算和故障分析的基础。 潮流计算经历了一个由手工, 利用交、直流计算台到应用数字电子计算机的发展过程。现在的潮流算法都以计算机的应用为前提。 利用电子计算机进行潮流计算从20世纪50年代中期就已经开始。此后,潮流计算曾采用了各种不同的方法,这些方法的发展主要是围绕着对潮流计算的一些基本要求进行的。一般要满足四个基本要求: a)可靠收敛 b)计算速度快 c)使用方便灵活 d)内存占用量少 它们也是对潮流算法进行评价的主要依据。 在电力系统运行方式和规划方案的研究中,都需要进行潮流计算以比较运行方式或规划供电方案的可行性、可靠性和经济性。同时,为了实时监控电力系统的运行状态,也需要进行大量而快速的潮流计算。因此,潮流计算是电力系统中应用最广泛、最基本和最重要的一种电气运算。在系统规划设计和安排系统的运行方式时,采用离线潮流计算;在电力系统运行状态的实时监控中,则采用在线潮流计算。 二、国内外研究现状及发展趋势(含文献综述): 在用数字计算机求解电力系统潮流问题的开始阶段,人们普遍采用以节点导纳矩阵为基础的高斯-赛德尔迭代法(一下简称导纳法)[1,2]。这个方法的原理比较简单,要求的数字计算机的内存量也比较小,适应当时的电子数字计算机制作水平和电力系统理论水平,于是电力系统计算人员转向以阻抗矩阵为主的逐次代入法(以下简称阻抗法)[2,3]。 20世纪60年代初,数字计算机已经发展到第二代,计算机的内存和计算速度发生了很大的飞跃,从而为阻抗法的采用创造了条件。阻抗矩阵是满矩阵,阻抗法要求计算机储存表征系统接线和参数的阻抗矩阵。这就需要较大的内存量。而且阻抗法每迭代一次都要求顺次取阻抗矩阵中的每一个元素进行计算,因此,每次迭代的计算量很大。 阻抗法改善了电力系统潮流计算问题的收敛性,解决了导纳法无法解决的一些系统的潮流计算,在当时获得了广泛的应用,曾为我国电力系统设计、运行和研究作出了很大的贡献。但是,阻抗法的主要缺点就是占用计算机的内存很大,每次迭代的计算量很大。当系统不断扩大时,这些缺点就更加突出。为了克服阻抗法在内存和速度方面的缺点,后来发展了以阻抗矩阵为基础的分块阻抗法[3,4]。这个方法把一个大系统分割为几个小的地区系统,在计算机内只需存储各个地区系统的阻抗矩阵及它们之间的联络线的阻抗,这样不仅大幅度的节省

相关主题
相关文档 最新文档