Google TechTalks
4 HN recommenders · recommended in 7 months, 2017–2023
1:01:47 · 36K views · Jan 28, 2016
Guy Steele presents a small geometric problem and compares four computational approaches: a classic sequential solution and three parallel-friendly ones. Each is illustrated pictorially and with working code, weighing total work against time to solution.
HN points to it as a clear lesson that algebraic properties like associativity unlock parallelism, applicable in any language.
7 comments from Hacker News
Hi, the author here. One of the hidden messages of the introduction is: watch Guy Steele's talks [1][2][3] if you are interested in data parallelism! These talks are not Julia-specific and the idea is applicable and very useful in any languages. My libraries are heavily inspired by these talks. Of course, if you haven't used Julia yet, it'd be great if (data) parallelism gives you an excuse to try it out! It has a fantastic foundation for composable multi-threaded parallelism [4]. [1] How to Think about Parallel Programming: Not! [LINK] [2] Four Solutions to a Trivial Problem this video [3] Organizing Functional Code for Parallel Execution; or, foldl and foldr Considered Slightly Harmful [LINK] [4] Announcing composable multi-threaded parallelism in Julia [LINK]
This type of interviewing style is bullshit. It means the interviewer knows a better solution that is "clever" and expects you to either have the same cleverness epiphany on the spot or to have studied this question. Neither is actually very useful as a hiring criterion. Guy Steele gave an incredibly interesting guest talk[1] at google about four different ways to solve this exact problem, and the fact that it's an interesting enough topic for an hour long google talk should probably be a clue that you shouldn't be expected to invent the best solution on the whiteboard in 40 minutes. [1] this video
I enjoyed this talk along the same lines by Guy Steele, regarding not necessarily forcing a sequential solution to a non-sequential problem: Four Solutions to a Trivial Problem - Guy Steele Jr.: this video Look for steps that are commutative and/or associative in the problem to exploit parallelism.
Guy Steele Jr. worked on a language called "Fortress." There are a few good talks that he gives: - (toy problem) this video - (parallelism) [LINK] - (languages) [LINK]
I think APL has a lot to teach us about parallel (specifically GPU) programming. I've rewatched a few talks with Aaron Hsu and listened to his arraycast podcast[1]. In researching an upcoming blog post on monoids, I tried implementing the problem in Guy Steele's "Four Solutions to a Trivial Problem" talk[2] in APL (actually I tried GNU APL for this, because I didn't need anything fancy). This is what I came up with: +/((⌽⌈\⌽a)⌊⌈\a)-a That in turn should be fully parallelizable and run fast on the GPU, as it's based on a couple scan (generalized prefix sum) operations. There's a considerable amount of DNA from APL in modern compiler-based machine learning frameworks, mostly by way of numpy. Dr. Hsu makes a good case that APL has quite a bit of power which is considerably diluted in later spins such as numpy. I'm especially fond of the power (⍣) operator[3], which represents parallel iteration and I think can often be translated to a per-thread while or for loop in a compute shader. I don't believe numpy has anything quite like that (but feel free to correct me!). [1]: [LINK] [2]: this video [3]: [LINK]