并行计算与计算机集群/软件

软件

在传统的程序设计中，程序通常被认为类似于一种文档格式：它们以一个标题部分开始；然后进入循环，反复执行相同任务或一系列任务，直到满足某个条件，最后执行某种形式的退出清理。在循环条件期间，程序在执行任何后续条件之前完成单个任务，因此每个任务都按顺序执行其先前和后续任务。

有时，在串行设计中，各个任务之间没有相互影响，因此可以以任何顺序执行。在这些情况下，每个任务都适合并行化。但是，许多程序是分阶段的 - 任务之间相互依赖，并且依赖程度决定了一组串行任务可以被重新设计为并行执行的简单程度。

设计并行任务

在开始认真进行并行化任务套件的实现工作之前，有必要识别任务之间的相互依赖关系。为了说明并行化过程所面临的主要问题，可以使用一些相当基本的数学问题作为例子。

所有数字的总和

卡尔·弗里德里希·高斯和他同班同学所面临的著名问题：将 1 到 100 之间的整数加起来。假设没有数学公式 [(1 + N)*(N/2)] 来计算这个问题，并且确实需要将各个数字逐个加起来

将任何一组整数加在一起的数学性质允许加法以任何顺序进行。例如，1 + 2 + 3 + 4 和 4 + 3 + 2 + 1 都会得到相同的总和 10。同样地，(1 + 2) + (3 + 4) 会得到等效的计算结果 3 + 7，最终得到相同的总和 10。仅将四个数字相加的问题也可以用不同的方式描述：1 + (2 + 3) + 4 或 (1 + (2 + (3 + 4)))。为了提供有效的并行化，重要的是设计如何最好地拆分手头的問題。后两个例子显示出比将问题分成两半的依赖性更多

细分	# 计算	# 独立计算
(1 + 2) + (3 + 4)	3: 1+2=3; 3+4=7; 3+7=10	2: 1+2=3; 3+4=7
1 + (2 + 3) + 4	3: 2+3=5; 5+1=6; 6+4=10	0: 所有计算都是相互依赖的
(1 + (2 + (3 + 4)))	3: 3+4=7; 7+2=9; 9+1=10	0: 所有计算都是相互依赖的

这种将问题分成两半的方法适用于数字数量是 2 的倍数的任何数字序列：8、16、32。然而，将这种初始方法应用于使用偶数个数字的更长序列会带来另一个问题：1 + 2 + 3 + 4 + 5 + 6。这个计算不能再简单地分成两半：1 + (2 + 3) + (4 + 5) + 6。已知 1 + 6 的计算可以完成，但在这种方法中，它被遗漏了。为了克服这一缺陷，因此需要改变方法，使其适用于所有偶数个数字：配对。使用配对，可以减少计算：(1 + 2) + (3 + 4) + (5 + 6)。并行化现在将原始问题简化为 3 + 7 + 11。现在，问题进入了一个全新的阶段...

这个问题仍然没有为所有数字的计数解决 - 到目前为止，只有偶数计数得到了解决。由于数学性质，不可能将 3 + 7 + 11 的求和分解为 3 + 7 和 7 + 11 的单独部分，因此了解你的主题内容变得越来越重要：确保各个部分不会重复整个或另一个部分的一部分。对于手头的这个问题，那么，一个合理的假设是，手头的任务可以分割成对和对的对，直到整个问题被消耗，可能除掉一个单独的数字作为最后一步。因此，1 + 2 + 3 + 4 + 5 + 6 可以简化为((1 + 2) + (3 + 4)) + (5 + 6)，因为它是最有效的。

最后一步

并行化问题设计追求的最后一步可能是令人惊讶的逆转：可以将各个任务更好地实现为串行过程吗？了解问题要实现的架构成为另一个设计原则。在对少量任何数字（不一定像上面那样连续）进行加法的情况下，大多数 MPU 能够以 ((a + b) + c) + d 的形式比以 (a + b) + (c + d) 的形式更快、更有效地执行片上计算，因为需要将数据加载和存储到寄存器中。两种任务的命令序列可能如下所示

伪计算周期	((a + b) + c) + d	(a + b) + (c + d)
1	将a加载到累加器中	将a加载到累加器中
2	将b加载到第二个寄存器中	将b加载到第二个寄存器中
3	将第二个寄存器加到累加器中	将第二个寄存器加到累加器中
4	将c加载到第二个寄存器中	将累加器的部分 1结果存储到内存或另一个寄存器中
5	将第二个寄存器加到累加器中	将c加载到累加器中
6	将d加载到第二个寄存器中	将d加载到第二个寄存器中
7	将第二个寄存器加到累加器中	将第二个寄存器加到累加器中
8	将结果存储到主内存中	将部分 1结果加载到第二个寄存器中
9		将第二个寄存器加到累加器中
10		将结果存储到主内存中

具体理论

...?

编译器

...?

外部链接