什么是好的(半)异步算法？

Question

我在数据结构上寻找一些数据并行算法,例如列表或图形,它们不使用同步但是利用关键部分来保持状态一致.

到目前为止,我只遇到了算法

• 同步:它们处理它们更改的数据的本地副本,并在某些时间段交换它们的当前状态以进行下一步(例如,单步并行本地搜索),或者

• 无竞争条件:它们细分数据结构,使得每个部分可以使用共享内存单独安全地处理(例如并行Quicksort)

你知道任何可理解的(半)异步算法吗？

1. 细分必须由多个处理器单独处理的数据,
2. 处理器通过共享存储器(例如,通过使用关键部分)交换每个步骤中生成的一些数据,因此,
3. 只是松散地同步,但不依赖心跳方案或其他重量级同步措施？

编辑:我使用HT Kung 的技术报告同步和异步并行算法的多处理器术语.

编辑2:为了澄清术语,本文区分了不同类型的算法:

• 同步(例如,生命游戏的心跳方法)
• 异步:每个处理器可以主要独立工作,并可以随时通过共享内存将其结果传送给其他处理器.然后,通信可能影响其他处理器中的下一步计算(例如,通过并行二进制搜索在单独的收敛间隔中找到函数的零)
• 半异步/同步:同步发生,但比同步算法更少.

Answer 1

异步:有迭代算法的并行版本,如置信传播和连续过度放松,与Life不同,它可以容忍陈旧数据,因此不需要心跳.(虽然不是顺序一致的系统上的实际实现可能需要写入障碍.)

半同步:几乎每个数据结构都具有细粒度锁定.通常的想法是仅锁定正在处理的部分(例如,对于二进制搜索树,从根锁定路径,可能使用读写器锁).