编程基础/理解高性能计算

对顺序编程和并行编程概念之间区别的解释，以及每个概念的示例。带有一些使用并行编程概念解决问题的例子，对计算机的历史进行简要概述。建议不同学习者群体探索高性能计算。包含软件程序、源代码文件和多个互联网链接。

前言 - 2009 年 11 月 13 日

本模块创建为 2008-09 年开放教育杯：高性能计算竞赛的参赛作品。比赛由莱斯大学肯尼迪信息技术研究所执行主任 Jan Erik Odegard 博士监督。它被提交到“并行算法和应用”类别，并专门设计为针对对高性能计算 (HPC) 了解甚少的初中生到大学本科生的入门课程。

该模块获得了“并行算法和应用”类别的“最佳模块”奖，包括 500 美元的奖金。

那些为比赛审查参赛作品的人对改进提出了一些建议，其中大部分已被纳入本模块的修订版中。一如既往；感谢他们和所有对改进教学材料提出建议的人。

肯尼斯·勒罗伊·巴斯比

高性能计算简介

将多台计算机或多个计算机处理器组合在一起以更快地完成任务被称为高性能计算 (HPC)。我们想解释如何使用并行编程算法或概念来实现这一点。

从单处理器到并行的转变

我们将通过提供两个简单的示例来开始我们的解释。

示例 1

吃饱喝足后，你把鸡腿骨从车窗扔出去（你真不应该乱扔垃圾！），但没过多久，一只蚂蚁就发现了你扔掉的鸡腿骨。一只蚂蚁可以咬掉骨头上的残留物，一次运回蚁巢；但这可能需要他整整一天（24 小时）的工作时间。但是，如果他得到帮助呢？它向一些同伴发出信号，作为一个小型的蚁群，他们分配了 10 只蚂蚁来完成这项任务。10 倍的工人需要十分之一的时间。10 只蚂蚁在 2 小时 24 分钟内完成了任务。

我又扔了一块骨头出窗外。一只蚂蚁找到了它，蚁群分配了 50 只蚂蚁来完成清理骨头的任务。在不到 30 分钟（确切地说是 28.8 分钟）的时间里，50 只蚂蚁并行工作完成了任务。

示例 2

一名油漆工可能需要 8 个小时才能粉刷一座中等大小房屋的外墙。但是，如果他能找到一支 10 人的油漆工队伍同时工作（或者换句话说，并行工作），那么只需 48 分钟。如果是一支 50 人的油漆工队伍，假设他们可以工作并且不会互相干扰，那么怎么样呢？只需要不到 10 分钟（确切地说是 9.6 分钟）。

现在让我们确保我们理解在给出的示例中完成了相同的工作量。工作只是在更短的时间内完成，因为我们投入了更多的工人。并非所有任务都可以这样划分，但当可以将任务划分为多个工人时，我们可以利用工人并行完成其任务子部分的优势。让我们看另一个例子。

示例 3

我想从德克萨斯州休斯敦开车到德克萨斯州达拉斯；距离约 250 英里。为了便于计算，假设我每小时可以行驶 50 英里。这将需要我 5 个小时。那么，我可以将任务分配给 5 辆车，让每辆车行驶 50 英里，在 1 个小时内到达达拉斯。对吗？

好吧，错了。从休斯敦到达拉斯的驾驶任务无法划分为可以并行完成的任务。这项任务只能由一个人按顺序从休斯敦到达拉斯开车行驶 5 个小时。我用“线”这个词，因为它有助于我们联系到“线性”这个词。线性任务不能分解成更小的任务，由多个工人并行完成。在计算机世界中，与线性概念相关的词是顺序处理。我必须按顺序一次行驶一英里才能到达达拉斯。

我们的自然倾向是在可能的情况下共享工作，即并行工作。作为一个群体，我们可以更快地完成许多可以并行完成的任务。

计算机的诞生 - 与中央处理器 (CPU) 故事的“平行”

“ENIAC，即电子数值积分计算机的缩写，是第一台通用电子计算机（1946 年 7 月）。它是第一台图灵完备的、能够重新编程以解决各种计算问题的数字计算机。ENIAC 有 20 个十进制带符号累加器，它们使用十进制补码表示，每秒可以执行 5,000 次简单的加法或减法运算，这些运算发生在任何一个累加器和一个源（例如，另一个累加器或一个常数发射器）之间。可以连接多个累加器同时运行，因此由于并行操作，峰值运行速度可能要高得多。”（来自维基百科的 ENIAC）

今天许多人可能并不理解，第一台计算机使用电子元件中的十进制算术，并且通过使用多个累加器来提高速度，它是一台并行处理机器。然而，这种情况并没有持续很久。在它的建设过程中

“EDVAC 的第一份报告草案（通常简称为第一份草案） - 电子离散变量自动计算机，是一份由约翰·冯·诺依曼撰写的 101 页的未完成文件，于 1945 年 6 月 30 日由赫尔曼·戈德斯廷（保密 ENIAC 项目的安全官）分发。它包含了第一个公开发表的描述，描述了使用存储程序概念的计算机逻辑设计，这种概念后来被称为冯·诺依曼体系结构。”（来自维基百科的 EDVAC 的第一份报告草案）

“冯·诺依曼体系结构是存储程序式数字计算机的一种设计模型，它使用一个 [中央] 处理 [单元] 和一个单独的存储结构来存储指令和数据。它以数学家和早期计算机科学家约翰·冯·诺依曼的名字命名。此类计算机实现了通用图灵机，并具有顺序体系结构。”（来自维基百科的冯·诺依曼体系结构）

冯·诺依曼还建议使用二进制（以 2 为底）计数系统来进行电子设计。冯·诺依曼架构的一个特点是，它用单个使用二进制（或数字）电子系统的中央处理器来替代多个使用十进制电子系统的处理器。用我们蚂蚁的例子来比喻，这个想法就是使用一只非常快的蚂蚁来替代 10 只慢蚂蚁。如果一只非常快的蚂蚁在一小时内能完成 1000 项任务，那么它将比 10 只蚂蚁在一小时内完成 10 项任务，或者每小时完成 100 项任务更强大（能够完成更多任务）。

接下来的历史大家都知道了——在接下来的大约四十年（1951 年到 1991 年）中，大多数商业制造的计算机都遵循冯·诺依曼架构。电子工程师们不断地制造出更可靠、更快的电子设备。从真空管到晶体管，再到集成电路，最后到我们今天所说的“芯片”技术。这种转变使计算机的故障率降低（更可靠）、体积更小、功耗更低、速度更快。个人计算机在 20 世纪 70 年代后期推出，并在十年内变得更加普遍，并且被广泛使用。

有一个缺点，就是大多数编程工作都集中在改进线性（或顺序）的思维方式或解决问题的方法上。毕竟，计算机电子工程师每年都会制造出速度更快的计算机。每个人都知道计算机只有一个中央处理器（CPU），对吧？

对强大性能的需求

错了。计算机科学家和电子工程师从 1946 年开始就一直在尝试使用多处理器计算机进行并行编程。但是直到 20 世纪 80 年代，我们才看到第一批并行处理计算机（由克雷和其他计算机公司制造）作为商业制造的计算机出售。现在是另一个例子的时候了。

示例 4

从一个城市到另一个城市，火车上的一头大象死了。他们决定把大象扔下火车（真是可耻，他们把乡村弄得乱七八糟），但是很快，一只“超级”蚂蚁（比大多数普通蚂蚁更快）发现了大象。这个任务比你扔掉的鸡骨头大得多。一只“超级”蚂蚁可以单独完成任务（一次咬掉大象的一块，然后把它运到蚁穴里），但可能需要整整一年。毕竟，这比吃鸡骨头需要做更多的工作。但是，如果它得到帮助呢？它给一些同伴发了信号，因为它们是一个庞大的“超级”蚂蚁群，所以它们总共分配了 2190 只蚂蚁来完成这项任务。哇，它们在六个小时内就吃掉了大象。

这个大象的例子正是计算机科学家们所达到的境界。电子工程师们将继续改进单一中央处理单元计算机的速度，但速度提升不够快，无法满足解决需要强大计算能力的任务的需求。一些需要强大计算能力的新任务包括人类基因组计划、通过创建地质构造的 3 维图像来寻找石油和天然气，以及研究宇宙中的引力；仅举几个例子。解决方案：并行处理来解救。基本上，获得这种强大计算能力的唯一方法是实现并行处理技术。在 20 世纪 70 年代后期和 80 年代初期，科学家们看到了更充分地探索并行处理范式的必要性，从而诞生了高性能计算。从 20 世纪 80 年代开始，各种国家和国际会议开始举行，以促进高性能计算的发展。例如，在 2008 年 11 月，超级计算会议“SC08”举办了 20 周年庆典。

天气预报是高性能计算需求的良好例子。使用最快的中央处理单元计算机可能需要一年时间才能预测明天的天气。信息是正确的，但晚了 365 天。使用并行处理技术和强大的“高性能计算机”，我们可能能够在 6 个小时内预测明天的天气。不仅正确，而且及时有用。

衡量计算机性能

大多数人都熟悉千兆赫兹（每秒数十亿条指令）这个单位，它用来描述单个 CPU 处理器的运行速度。如今，大多数微型计算机的运行速度约为 3 GHz，即每秒 30 亿条指令。尽管 30 亿听起来很快，但其中许多指令都是简单的操作。

超级计算使用一个涉及浮点运算的测量值作为基准来比较计算机性能。“在计算中，FLOPS（或 flops 或 flop/s）是每秒浮点运算的缩写。” 并且再次，“2008 年 5 月 25 日，由 IBM 制造的名为“Roadrunner”的美国军用超级计算机，通过每秒处理超过 1.026 万亿次运算，达到了每秒一千万亿次运算的计算里程碑。”（FLOPS 来自维基百科）对于我们这些不熟悉的人来说

示例 5：了解性能

3 billion or 3 GHz is:                  3,000,000,000
1 quadrillion or 1 pedaflop is: 1,000,000,000,000,000

你也要意识到，你的个人计算机在使用 FLOPS 测量时，并非执行 3 千兆次浮点运算，而是更慢的运算。

高性能计算变得个人化

让计算机达到个人水平（1951 年到 1981 年）花了数年时间（大约 30 年）。让多处理器计算机达到个人水平（20 世纪 80 年代后期至今，2009 年）花了大约 20 年。目前，公众可以使用带有“双核”和“四核”处理器的计算机。在不久的将来，微型计算机将拥有 8 到 16 个核心处理器。人们会问：“我为什么要用这么强大的计算机？” 有数十种应用，但我至少能想到一个几乎每个人都想要的东西：高质量的语音识别。没错！我想和我的计算机说话。扔掉你的鼠标，扔掉你的键盘，不再需要触控板——和它说话。

同样，一个缺点是，大多数编程工作都集中在教授和学习顺序处理的思维方式或解决问题的方法上。教育工作者现在需要教授，程序员现在需要发展使用并行概念和算法的编程技能。

总结

我们一直在顺序和并行概念之间来回切换。我们讨论了我们自然倾向于并行完成工作的特点。但是，随着计算机的诞生，并行概念被放在一边，计算机行业实施了一种更快的单处理器方法（顺序）。我们解释了顺序处理的局限性和对计算能力的需求。因此，高性能计算诞生了。并行处理计算机正在迁移到我们的家中。随着这种迁移，迫切需要教育现有的一代，并培养下一代科学家和程序员，让他们能够利用高性能计算的优势。

适合学习者的活动

高性能计算正在影响我们做的一切。学习、工作，甚至我们的休闲娱乐都受到 HPC 的影响。为了帮助更多人了解 HPC，我列出了适合学习者的活动，这些活动是根据学习者在编程技能方面的水平来划分的。

具备计算机素养但没有编程技能

我们提供了两个计算机程序，可以帮助学生了解并行处理的影响。第一个是“线性到并行计算器”，学生输入一个人完成任务需要多长时间，询问有多少人会作为一个组来完成任务，然后计算这个组完成任务需要多长时间。第二个是“并行速度演示程序”，它模拟并行处理。它在显示器上显示前 60 个阶乘数，并在 60 秒内完成，然后显示 10 个处理器如何在 6 秒内完成，然后显示 100 个处理器如何在不到 1 秒内完成。这两个程序都是编译好的，可以在英特尔 CPU 机器上使用（针对 Windows 操作系统编译）。

从 Connexions 下载可执行文件：线性到并行计算器

从 Connexions 下载可执行文件：并行速度演示程序

一个有趣的活动是加入一个通过互联网连接使用数千台个人微型计算机进行并行处理的团队。在维基百科上的“FLOPS”文章中列出了几个分布式处理项目。其中一个团队是“伟大的互联网梅森素数搜索 - GIMPS”。

GIMPS 网站的链接是：http://www.mersenne.org/

另一个活动是“谷歌”一些关键词。注意 - “谷歌”可能会让人困惑，并且经常难以专注于你想要的确切主题。

高性能计算
计算科学
超级计算
分布式处理

学习编程基础

正在学习编程并且目前正在学习模块化/结构化编程和/或面向对象编程的学生可能想回顾上面列出的演示程序的源代码文件。这些程序不进行并行编程，但学生可以修改或改进它们以更好地解释并行编程概念。

您可能需要右键单击链接并选择“目标另存为”才能下载这些源代码文件。

从 Connexions 下载源代码文件：线性到并行计算器

从 Connexions 下载源代码文件：并行速度演示程序

另一个合适的活动是“谷歌”上面列出的一些关键词。凭借你对编程的基本理解，你将比那些没有编程经验的人更理解这些材料。你应该感觉到并行编程正在成为计算机专业人员工作和职业中越来越重要的部分。

查看“全球超级计算机500强”榜单：http://www.top500.org/

查看下一节提供的源代码列表，但请记住，你无法在你的普通计算机上编译或运行它们。

大学本科高年级学生

挑战在于尝试并行计算，而不仅仅是谈论它。

在 2006 年 5 月 21 日至 5 月 26 日的那一周，本文作者参加了关于并行和分布式计算的研讨会。研讨会由国家计算科学研究所举办，介绍了使用多台计算机进行并行编程（将一组微型计算机分组或集群成一台超级微型计算机）。会议强调了与计算机行业相关的几个重要要点。

在过去的几年里，超级微型计算机变得更加强大，也更易获得。
台式计算机开始使用多个处理器（或内核）构建，并且在几年内，我们将拥有多个（10 到 30 个）内核处理器。
超级微型计算能力的应用非常广泛，并在所有领域不断增长：科学研究、工程应用、计算机游戏和教育的 3D 动画等。
缺乏了解如何管理和利用这种发展中资源的教育工作者、科学研究人员和计算机专业人员。所需的计算机专业人员包括：知道如何创建和维护超级微型计算机的技术人员；以及知道如何创建使用并行编程概念的计算机应用程序的程序员。

最后一点是强调给那些开始计算机编程职业的人，随着你继续你的教育，你应该意识到计算机编程作为一种职业的不断变化的本质。在几年内，所有专业程序员都必须熟悉并行编程。

在会议期间，本文作者编写了一个程序，使用两种不同的方法对一个包含 150,000 个整数的数组进行排序。第一种方法是不使用并行处理。当它被编译并在单台机器上执行时，它花了 120.324 秒才运行（2 分钟）。第二种方法是重新设计程序，以便它的一部分可以在多个处理器上同时运行。当它被编译并在一个微型计算机集群中的 11 台机器上执行时，它花了 20.974 秒才运行。这大约快了 6 倍。因此，并行编程将成为利用不久的将来多处理器硬件的必要条件。

在普通计算机实验室中，使用存储在 CD 中的 Linix 操作系统设置了分布式计算环境。在用 CD 启动多台计算机后，计算机可以在“消息传递接口”或 MPI 命令的支持下相互通信。这种模型称为可启动集群 CD（BCCD），可从以下位置获取

可启动集群 CD - 爱荷华州立大学：http://www.bccd.net/

在上述研讨会中使用的源代码文件被修改为版本 8，因此文件名中包含 8。非并行处理的“超级”代码名为：nonps8.cpp，并行处理的“超级”代码名为：ps8.cpp（注意：并行处理代码包含一些注释，描述了代码的一部分由标记为“SERVER_NODE”的机器运行，而代码的一部分由另外 10 台机器（客户端）运行。客户端机器使用“消息传递接口”或 MPI 命令向服务器节点发送关键信息。）

您可能需要右键单击链接并选择“目标另存为”才能下载这些源代码文件。

从 Connexions 下载源代码文件：nonps8.cpp

从 Connexions 下载源代码文件：ps8.cpp

在研讨会期间，演示者提供了两个包含超级计算机信息的著名资源

俄克拉荷马大学 - 教育与研究超级计算中心：http://www.oscer.ou.edu/education.php

康特拉科斯塔学院 - 高性能计算：http://contracosta.edu/hpc/resources/presentations/

您还可以“谷歌”主题的关键词，并花几天时间阅读和尝试高性能计算。

考虑查看下一节中提供的“教育资源”链接。