标题： 无同步收敛 显示英文标题

标题： Convergence Sans Synchronization

摘要： 我们目前看到多处理器系统使用量和规模的持续上升，因此社区对开发快速并行处理算法的兴趣日益增加。 然而，大多数算法需要一种同步机制，这在计算资源和时间方面成本很高。 如果一个算法可以异步执行，那么它可以利用所有可用的计算能力，节点可以在没有调度或锁定的情况下执行。 然而，要证明一个算法在异步情况下保证收敛，我们需要生成整个全局状态转移图，并检查是否存在循环。 这需要的时间随着全局状态空间的大小呈指数增长。 在本论文中，我们提出了一种理论，解释了多处理器算法所需的必要和充分属性，以保证即使在没有同步的情况下也能收敛。 我们为各种不需要同步的问题开发了算法。 此外，我们展示了几个现有算法可以无需任何同步机制执行。 我们工作的显著理论优势在于证明了一个算法即使在异步情况下也可以收敛。 我们的理论表明，我们可以通过仅证明计算节点的局部状态转移图形成偏序，而不是生成整个全局状态空间并确定其中是否存在循环，从而得出关于算法的结论。 因此，生成此类证明（无论是正式的还是社会的）的复杂性大大降低。 实验表明，当我们比较文献中算法的执行时间和我们设计的算法的执行时间时，收敛所需的时间显著减少。 当我们在一个调度器下运行一个保证在异步情况下收敛的算法与在异步情况下运行该算法时，我们得到了类似的结果。 显示英文摘要

摘要： We currently see a steady rise in the usage and size of multiprocessor systems, and so the community is evermore interested in developing fast parallel processing algorithms. However, most algorithms require a synchronization mechanism, which is costly in terms of computational resources and time. If an algorithm can be executed in asynchrony, then it can use all the available computation power, and the nodes can execute without being scheduled or locked. However, to show that an algorithm guarantees convergence in asynchrony, we need to generate the entire global state transition graph and check for the absence of cycles. This takes time exponential in the size of the global state space. In this dissertation, we present a theory that explains the necessary and sufficient properties of a multiprocessor algorithm that guarantees convergence even without synchronization. We develop algorithms for various problems that do not require synchronization. Additionally, we show for several existing algorithms that they can be executed without any synchronization mechanism. A significant theoretical benefit of our work is in proving that an algorithm can converge even in asynchrony. Our theory implies that we can make such conclusions about an algorithm, by only showing that the local state transition graph of a computing node forms a partial order, rather than generating the entire global state space and determining the absence of cycles in it. Thus, the complexity of rendering such proofs, formal or social, is phenomenally reduced. Experiments show a significant reduction in time taken to converge, when we compare the execution time of algorithms in the literature versus the algorithms that we design. We get similar results when we run an algorithm, that guarantees convergence in asynchrony, under a scheduler versus in asynchrony.