Skip to content

Concurrency

多核时代与并行算法

https://zhuanlan.zhihu.com/p/89863627

事实上许多并行算法和快排一样，本质上并不复杂，但需要的只是摒弃我们对于传统算法的理解而做到使用并行的思维去思考问题，也就是我们称之为 Parallel Thinking 。

为此我们提出了一种基于 join 操作的树结构 [3]。join 这个函数是说，给定两棵树 T1 和 T2，以及一个结点 k，返回一个合法的平衡树 T = [T1, k, T2]，它等价于用 k 连接 T1 和 T2，但是要求输出树满足平衡条件。显然对于 BST 来说，这个算法只有在 k 大于 T1 里所有数，并小于 T2 里所有数时才有意义。当这个 join 算法可以被正确地实现时，我们就可以把许多树上的算法并行。总体的思路依然是利用分治法。对于一棵树，我们并行地递归地处理左子树和右子树，并把它们用树根 join 起来。许多时候，操作后的左右子树不再平衡，但是正如上面所说，join 会处理平衡问题。通过抽象出 join 这个元操作，并行别的算法的思路就变得简洁。

A Static Verification Framework for Message Passing in Go using Behavioural Types

Verifying message passing concurrency

concurrent behavioural types [24], which have been developed extensively in concurrency theory since the early 90s.

  1. What are the other application of behavioral types? Is it complete?
  2. How we could develop on top of this work?
  3. How does the model checker work?