什么是好的（半）异步算法？

Question

我正在寻找一些数据并行算法的数据结构，如列表或图表，它们不使用同步，但使用关键部分为了保持状态一致。

到目前为止，我只遇到过那些要么

• 同步算法：他们对他们改变了数据的本地副本工作，并在一定的时隙交换它们的当前状态，为下一步（如单走平行本地搜索），或者是

• 竞争条件自由：它们细分数据结构，使得每个部分都需单独且安全地共享存储器（例如处理并行快速排序）

你知道的任何可理解（半）的异步算法

1. 细分必须由单独的多个处理器来处理数据，
2. 交流一些在每个步骤由处理器所产生的数据的通过共享内存（例如通过使用临界部分）并且因此是仅仅同步松散但不依赖于心跳计划或其他重量级同步测量的情况下的
3. ？

编辑：我使用由孔祥重技术报告Synchronized and asynchronous parallel algorithms for multiprocessors的术语。

EDIT2：只是为了澄清术语，纸张区分不同类别的算法：

• 同步
• 异步（如心脏搏动对生活的游戏方式）：每个处理器可以主要独立工作，并可以随时通过共享内存将其结果传送给其他处理器。然后，通信可能会影响其他处理器的下一步计算（例如，通过并行二进制搜索在单调收敛间隔中找到函数零）
• 半异步/同步：发生同步，但比在一个同步算法。

Answer 1

异步：有像belief propagation和successive over-relaxation，不像生活，容忍陈旧的数据，因此不需要心跳的迭代算法并行版本。 （尽管系统上的实际实现不是按顺序一致的，但可能需要写屏障。）

半异步：几乎每个数据结构都具有细粒度锁定。通常的想法是只锁定正在工作的部分（例如，对于二叉搜索树，从根锁定路径，可能使用读写器锁）。

Answer 2

我不确定这是否符合“数据结构如列表或图形”的要求，但并行遗传算法可以维护共享的有希望的基因池。一个免费的处理器需要一个处理器并执行一代进化，将优异的结果（也许随机选择的用于遗传多样性的劣势结果）放回池中。