A Novel Rollback Algorithm in Parallel and Distributed System Simulation
A Novel Rollback Algorithm in Parallel and Distributed System Simulation
复制标题
并行分布式系统仿真中的一种新型回滚算法
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Kedi Huang
中科院分区：
文献类型：
--
作者：
Xuehui Wang;Lei Zhang;Kedi Huang
模拟是分析新系统设计、对现有系统进行改造和提出操作规则更改建议的有力工具。在本文中，我们仅讨论并行和分布式仿真(PDS)。为了以更好的一致性、更快的速度对大规模复杂系统进行仿真，PDS普遍采用的方法是使仿真程序在多处理器和分布式计算平台上执行。时间管理算法是并行分布式系统仿真中的关键技术之一，通常分为保守同步和乐观同步两大类。对这两种算法的基本原理和实现机制进行了综述。本文的剩余部分将重点介绍一种新的回滚算法，我们称之为智能回滚算法。然后，对乐观时间管理中的回滚算法进行了详细的描述，包括调度器的优先级队列、回滚管理器、取消策略和前滚操作。在这篇文章中，核心问题涉及不同处理器上的计算同步。最后，我们讨论了如何获得相对最小的回滚，以及如何实现动态分配和回收。
Simulation is a powerful tool for the analysis of new system designs, retrofits to existing systems and proposed changes to operating rules. In this paper we limit our discussion to parallel and distributed simulation (PDS). In order to simulate large-scale complex systems with better consistency, further more as fast as possible, the universally adoptive approach of PDS is that make the execution of simulation programs on multiprocessor and distributed computing platforms. Time management algorithm is one of the key techniques in the parallel and distributed system simulation, which broadly fall into conservative and optimistic synchronization. A survey of both the two algorithms is presented focusing on fundamental principles and mechanisms. The remainder of this paper is focused on one of the novel rollback algorithm; we call it as smart rollback algorithm. And then, we provide and describe the novel rollback algorithm in optimistic time management in detail, including scheduler’s priority queue, rollback manager, cancellation strategies, and roll forward operation. Among this paper, central issues concern the synchronization of computations on different processors. Finally, we discuss how to get the relatively minimal rollback, and how to realize the dynamic allocation and reclamation.