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.