Task Allocation and Checkpointing in Distributed Computer Systems

随着基于消息的分布式并行计算系统的可用性越来越高，构造并行算法并将其映射到并行体系结构上的困难也变得越来越重要。目前，算法开发和编程过程通常包括算法子任务到处理器的显式映射。这个问题通常是手动处理的，通常会导致计算和通信负载平衡效率低下，进而导致可能获得的加速比的总体降低。当考虑分布式体系结构时，当处理器和/或通信链路出现故障，但必须继续以合理的速率处理剩余的计算资源时，问题会加剧。这需要有效地完成进程和数据检查点，并在检测到故障和定位故障时重新配置系统并重新分配任务。本文主要研究检查点问题和任务重分配问题。这项研究计划的目的是研究在分布式计算机系统中将任务分配给其可靠性特征已被表征的处理器的方法。目标是通过开发分布式检查点和快速任务重新分配方案，确保在发生故障(处理器或链路)后有效地使用剩余的分布式资源。

With the increasing availability of message based distributed parallel computing systems, the difficulties associated with constructing parallel algorithms and mapping them onto parallel architectures have grown in importance. Currently, the algorithm development and programming process typically includes the explicit mapping of algorithm subtasks to processors. This problem is typically dealt with manually and often results in inefficient computation and communication load balancing which in turn leads to an overall reduction in the speedups potentially obtainable. The problem is exacerbated when distributed architectures are considered where processors and/or communications links are subject to failure, yet must continue processing at reasonable rates with the remaining computing resources. This requires that process and data checkpointing be done effectively and that, on detection and location of failures, the system be reconfigured and tasks reallocated. This work focuses on the checkpointing and task reallocation problems. This research program is aimed at investigating approaches to allocating tasks to processors in distributed computer systems whose reliability characteristics have been characterized. The goal is to ensure effective use of the remaining distributed resources after failure (processor or link) has occurred through the development of distributed checkpointing and fast task reallocation schemes.