Asynchronous Algorithms: Scalable Algorithms for Multiprocessors

本课题涉及异步算法的分析、实现和仿真。异步算法不需要同步，因此特别适合大规模多处理器或大规模并行系统。此外，异步算法对处理器和链路故障具有容忍度，并且易于适应实时嵌入式系统中参数或传感器数据的变化。收敛性的理论分析考虑了随机时滞模型。在多处理器上运行的异步算法是具有随机通信延迟的进程。用这种方法可以很容易地分析复杂的问题，如互连网络中可变负载条件引起的随机消息延迟的影响，以及与概率链路或处理器故障相关的可靠性问题。该方法也适用于解随时间变化的问题和具有较好时间适应性的算法的分析。最后，通过随机化技术可以提高算法在周期性轨道中的收敛性。具有上述特征的六种异步算法在加州理工学院可访问的英特尔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.