编写并行编程的伪代码

Question

如何编写并行编程的伪代码？特别是，如何区分本地和共享变量？如何表示scatter、gather、reduce、broadcast和点对点通信等操作？是否有相关标准？

- Charles Brunet

---

这个问题仍然没有一个好的答案！ - LoveMeow

Answer 1

伪代码基本上只是英语，因此您可以使用清晰明了的语言。它不是一种编程语言，因此您无需像"scatter"这样表示操作...您可以直接说"scatter"。

伪代码没有标准，但好的伪代码应该简单易懂。

- Larry Watanabe

---

由于英语并不是一件平行的事情，我需要一种方式来形式化编程中的并行方面。这就是为什么这个答案不能满足我的原因。 - Charles Brunet

Answer 2

我发现至少有一种并行编程的伪语言：Peril-L。它很正式，但对我来说有点太低级了。

- Charles Brunet

Answer 3

在这里尝试“编写图表”：http://www.websequencediagrams.com/

你将得到最好的两个世界，相当简单的英语语句（“伪代码”）和清晰的图表。我已经能够使用这些图表向我的经理和同事解释相当复杂的并行编程。最后但并非最不重要的是，可以将图表“源”检入源代码控制系统。

- R. Simac

Answer 4

您的问题的简短答案是，没有传统的方式编写并行编程的伪代码。

这是因为有多种方法进行并行编程，涉及不同的并行架构（例如SMP、GPU、集群和其他奇特的系统）和并行编程方法。我提到“编程方法”，因为一般来说，大多数都是库或注释，而不是语言（请参见MPI、OpenMP、TBB等）。因此，即使您可以选择架构和语言，也会难以定义库或注释系统的语义。

幸运的是，已经开发了更严格定义的编程方法。然而，它们通常基于共享内存或消息传递。找到合适的符号/伪代码将取决于您需要定义语义的程度以及您试图表达的并行编程问题的类型。

以下是两个建议：

• PRAM. 共享内存编程与并行随机访问机（PRAM）计算模型密切相关。这已经得到广泛研究，并开发了许多算法。快速搜索文献将带来适合的PRAM符号。
• CSP. 通信顺序进程（CSP）是一种用于表达和推理消息传递系统的形式化（代数）方法。它在许多语言的设计中有影响力，特别是occam。

PRAM模型非常简单，应作为共享内存编程符号的基础。 CSP本身可能对伪代码来说过于数学化，而occam符号可能太冗长。这是Brinch Hansen（并发编程大师）的观点，他设计了自己的相关语言SuperPascal，用作并行算法在出版物中的解释符号。

据我所知，没有其他并行计算语言被开发出来可以以严格的方式定义，或适合用作高级符号。

- James

Answer 5

在进行一些网络研究后，我意识到一种“标准”仍不存在。正如@Larry Watanabe所说，“伪代码基本上只是英语。因此，您可以使用任何清晰明确的语言。它不是一种编程语言，因此您不需要表示像“散布”这样的操作...您只需说“散布”。”

所以，这里是我的个人解决方案，使用algorithm2e：关于“共享内存”，“局部变量”等方面的细节并不多，但是使用相同的策略，您可以找到描述您的想法的方法：

\usepackage[linesnumbered,ruled,vlined]{algorithm2e}
...
\begin{algorithm}
    \DontPrintSemicolon 
    \SetKwBlock{DoParallel}{do in parallel}{end}
    \KwIn{Some inputs}
    \KwOut{The ouput}
    \DoParallel{
        Compute a \;
        Compute b \;
        Compute c \;
    }
    \DoParallel{
        a1\;
        b1\;
        c1\;
    }
    \Return{the solution}\;
    \caption{Parallel Algo}
    \label{algo:parallelAlgorithm}
\end{algorithm}

结果如下：

这是基于使用表达式\SetKwBlock定义新命令的。该包的手册可以在这里找到。我最初也在这里发布了对此问题的答案。

使用定义关键字的策略来描述您想要的算法细节应该总是可行的。请考虑以下几点：

1. 更多细节→越接近您的编程语言。
2. 较少细节→更像伪代码。

总结：这始终是一种权衡：您决定限制在哪里（考虑您所指的目标人群）。

相同的策略已经被用于期刊论文中（例如，请参见this IEEE paper的算法3和4）。

- Leos313

Answer 6

这篇Matthew Adams的文章可能是我见过的最好的介绍，使用一种伪代码形式来演示多线程处理过程。

- HTTP 410

---

仍然不可用 :( - stej

这是他目前的个人网站：https://andrew.adams.pub/。不幸的是，他似乎没有在那里包含任何相关内容。 - webelo

@Webelo，那是一个完全不同的人。你可以在这里找到Matthew的最新博客：https://blogs.endjin.com/author/matthew-adams/ - HTTP 410

@RoadWarrior 感谢您的更正。我仍然无法在此网站上找到您在原始帖子中提到的那篇文章。这篇文章似乎已经丢失了，是吗？ - webelo

@Webelo，如果你给他发电子邮件，我相信他会把文章发送给你。我在2003年遇见过他，他给人留下了友好的印象。 - HTTP 410

Answer 7

你有没有考虑采用行为驱动开发的方法？我最近使用了BDD方法编写了一个相当复杂的多进程/多核心代码，发现它非常有帮助。这种方法最好的部分是我可以用简单的英语描述一切，并专注于问题而不是实现细节。我的前几个迭代都是单线程的，以确保代码通过所有测试并解决问题。我在选择的地方利用多进程提高了系统的性能，同时确保它不会破坏单线程系统通过的测试。重构变得更容易，因为代码已经比我过早地设计优化设计细节要简单得多，我可以专注于监控重构系统的处理时间，因为我得到的结果与之前的迭代完全相同。

看看嵌入式C的测试驱动开发这本书，获取一些想法。我在开发过程中利用了这本书，并将其作为我的图书馆的永久部分。

- Marc