Asynchronous Algorithms: Scalable Algorithms for Multiprocessors

本项目主要研究异步算法的分析、实现和仿真。 异步算法不需要同步，因此特别适合于大规模多处理器或大规模并行系统。此外，异步算法是宽容的处理器和链路故障，并很容易适应实时嵌入式系统中的参数或传感器数据的变化。收敛性的理论分析考虑具有随机时滞的模型。 在多处理器上运行的异步算法是具有随机通信延迟的进程。 利用这种方法，复杂的问题，如随机消息延迟的影响，由于可变的负载条件下的互连网络和可靠性问题的概率链路或处理器故障很容易分析。 该方法也 适用于分析的问题，其中的解决方案随着时间的变化和算法具有良好的时间适应性。 最后，对于陷入周期轨道的算法，可以通过随机化技术来改善其收敛性。 具有上述特征的六种异步算法在加州理工学院可访问的Intel Touchstone DELTA机器上实现。 为了评估异步算法在大规模多处理器系统中的有效性，对每个算法进行了广泛的评估。

This project is concerned with the analysis, implementation and simulation of asynchronous algorithms. Asynchronous algorithms do not require synchronization and thus are particularly suitable for large-scale multiprocessors or massively parallel systems. Moreover, asynchronous algorithms are tolerant to processor and link failures and easily adapt to changes in parameters or sensor data in real-time embedded systems. The theoretical analysis of convergence considers models with stochastic delays. Asynchronous algorithms running on a multiprocessor are processes with random communication delays. With this approach complex problems such as the effects of random message delays due to variable load conditions in the interconnection network and the reliability issues related to probabilistic link or processor failures are easily analyzed. The approach is also applied to the analysis of problems in which the solution changes with time and of algorithms with good time-adaptation. Finally, the convergence of algorithms which are trapped in periodic orbits can be improved through randomization techniques. Six asynchronous algorithms with the above features are implemented on the Intel Touchstone DELTA machine accessible at Caltech. Extensive evaluation of each algorithm is performed in order to assess the effectiveness of asynchronous algorithms in the context of large-scale multiprocessor systems.