一个平凡问题的四种解决方案 - Guy Steele Jr.

Four Solutions to a Trivial Problem - Guy Steele Jr.

频道:Google TechTalks · 时长:1:01:47 · 发布:2016-01-28 · 播放:36435

在 YouTube 观看

简介

Guy Steele 提出了一个小几何问题,并比较了四种计算方法:一种经典的顺序解决方案和三种适合并行的方案。每种都用图形和可运行代码说明,权衡总工作量与求解时间。

HN 为什么推荐

HN 指出它是一个清晰的教训:结合性等代数性质解锁并行性,适用于任何语言。

如果你对数据并行感兴趣,请观看 Guy Steele 的演讲 [1][2][3]! — HN, 2020

函数式编程 · 算法与数据结构

中文字幕节选

马特:今天我们请到了盖伊·斯蒂尔,这个名字对很多人来说可能很熟悉。 他参与了许多编程语言的规范制定, 包括Common Lisp和Java, 我想这个办公室里有些人可能会用到这些。 他让我把介绍保持简短,所以现在有请他自己来讲。 [掌声] 小盖伊·L·斯蒂尔:好的,谢谢你,马特。 很高兴来到这里。我看到房间里有很多熟悉的面孔,包括 一些我没想到今天会见到的人,所以感谢你们的到来。 希望你们喜欢这次演讲。 这次演讲是关于并行编程的。 我觉得在谷歌,我可能 有点像是在向唱诗班布道并行编程, 但我有自己的视角。 这是我在其他地方也会做的演讲, 所以至少你们可以听到 我在其他地方传达的信息,最近一次是上个月在哈佛。 所以这次演讲的主要观点是 我认为编写并行应用程序的最佳方式 是尽可能不必考虑并行性。 由于某些原因,并行性对我们的大脑来说很难理解, 而且需要分离关注点。 我认为问题不在于思考并行性本身, 而在于思考计算的独立性。 问题在于我们今天的编程语言 不能帮助我们表达或指示 计算何时相对独立。 我有一个特别的困扰,与累积范式有关。 累积往往是固有的顺序性。 所以,简而言之,我的口号,我过于简化的口号是:累加器是坏的。 分而治之是好的。 现在,我认为这是一个老生常谈的信息。 我不是第一个发现这一点的人。 但我认为我们需要认真对待它。 此外,代数性质也很重要。 我有应用代数的背景, 我认为这影响了我的编程。 我认为让程序员意识到他们代码的代数性质, 并将其中一些性质传达给编译器,可能是值得的。 那么,首先,让我们把一堆数字加起来。 假设我有一个数组x,长度为100万, 我想把x中的所有数字加起来。 这里有一些代码。它可以并行化吗? 问题是,谁在乎呢? 有一个bug。我忘了初始化SUM。 [笑声] 这是一个非常常见的bug,它一直困扰着我。 [轻笑] 好的。有了这段代码,它可以并行化吗? 嗯,问题在于这段代码本身就很糟糕。 它有一种固有的顺序性。 我们使用了这个DO循环,其语义本质上是顺序的。 聪明的编译器必须撤销这一点。 事实上,弗兰·艾伦因为毕生致力于编写编译器而获得了图灵奖, 这些编译器可以撤销这样的代码,并将其转换为 并行计算机真正可以运行的代码。 那么,数学家会怎么说把一堆东西加起来? 嗯,我们有这个大的西格玛符号, 而显式参数化的版本看起来很像那个DO循环。 当i从1到100万时,选择x下标i并将它们相加。 或者我们只是写一个大西格玛在前面, 让数学家去弄清楚如何把它们全部加起来。 把这个和Fortran 90中的SUM内建函数比较一下。 它说明了要做什么——我想把一堆东西加起来—— 但没有告诉你如何做,所以还没有对策略做出承诺。 而我所主张的就是不要过早地 对做某事的策略做出承诺,如果你能直接说出你想要完成什么。 好,让我们回到这个DO循环。 它是用一种与Fortran非常相似的语言写的。

HN 上的讨论

嗨,我是作者。引言中隐藏的信息之一是:如果你对数据并行感兴趣,请观看Guy Steele的演讲 [1][2][3]!这些演讲并非Julia专属,其思想适用于任何语言并且非常有用。我的库深受这些演讲的启发。当然,如果你还没用过Julia,如果(数据)并行能给你一个尝试它的理由,那就太好了!它拥有可组合的多线程并行性的绝佳基础 [4]。[1] 如何思考并行编程:不![LINK] [2] 一个平凡问题的四种解决方案 [VIDEO] [3] 为并行执行组织函数式代码;或,foldl和foldr被认为略有危害 [LINK] [4] 宣布Julia中的可组合多线程并行性 [LINK] — tkf, 2020-10
Guy Steele Jr. 参与开发了一门叫“Fortress”的语言。他做过几个不错的演讲:-(玩具问题)[VIDEO] -(并行性)[LINK] -(语言)[LINK] — MathMonkeyMan, 2023-07
这种面试风格是扯淡。这意味着面试官知道一个更“聪明”的解决方案,并期望你当场有同样的聪明顿悟,或者已经研究过这个问题。两者实际上都不是很有用的招聘标准。Guy Steele在谷歌做了一次非常有趣的客座演讲[1],关于解决这个确切问题的四种不同方法,而它作为一个长达一小时的谷歌演讲的有趣话题,这应该是一个线索,表明你不应该被期望在40分钟内在白板上发明出最佳解决方案。[1] [VIDEO] — heleninboodler, 2022-09
我很喜欢Guy Steele关于同一主题的演讲,关于不一定非要强制对非顺序问题采用顺序解决方案:《一个平凡问题的四种解决方案》 - Guy Steele Jr.:[VIDEO] 在问题中寻找可交换和/或可结合的步骤,以利用并行性。 — platz, 2018-08
我认为APL在并行(特别是GPU)编程方面有很多值得我们学习的地方。我重新观看了几个Aaron Hsu的演讲,并听了他的arraycast播客[1]。在研究即将发布的关于幺半群的博客文章时,我尝试用APL实现Guy Steele的“一个平凡问题的四种解决方案”演讲[2]中的问题(实际上我尝试了GNU APL,因为我不需要任何花哨的东西)。这就是我想出的:+/((⌽⌈\⌽a)⌊⌈\a)-a 这反过来应该可以完全并行化并在GPU上快速运行,因为它基于几个扫描(广义前缀和)操作。现代基于编译器的机器学习框架中有相当多的APL基因,主要是通过numpy。Hsu博士很好地证明了APL具有相当多的能力,而这些能力在后来的numpy等衍生品中被大大稀释了。我特别喜欢幂(⍣)运算符[3],它表示并行迭代,我认为通常可以转换为计算着色器中的每线程while或for循环。我不相信numpy有类似的东西(但欢… — raphlinus, 2022-02

相关视频