时间偏差算法中通讯接口的研究及实现

时间偏差算法是一种实现并行离散事件模拟的协议,其目的在于利用并行平台并发地执行大规模离散事件的模拟,以缩短仿真时间。为保证结果的正确性,并行模拟必须解决同步问题。时间偏差算法利用虚拟时间来同步各模拟部分之间的执行,通讯接口是利用虚拟时间及回退策略实现同步的部分。对该部分进行了深入的研究,提出了一种优化的实现方案,并对其性能进行了分析。     

多线程技术与分布式并发离散事件仿真

随着信息技术的快速发展和在实际的广泛应用,信息交换成本大幅降低,管理实践活动越来越呈现分布和并发特征.对于分布并发事件仿真因为仿真时钟同步问题,原有的离散事件仿真方法不能很好的进行模拟.多线程技术是并发事件仿真的有效方法,Net平台下多线程编程技术为这种实现提供便利,应用多线程技术能够实现对并发离散事件的仿真.最后针对一个分布式机械加工装配的例子用Visio建立起相应UML模型,并由此讨论该方法实现的可行性.     

作战仿真中侦察模型的仿真策略及应用研究

在离散事件仿真中,首事件触发执行是决定整个仿真开始的关键,在研究军事仿真中的装甲车辆作战侦察模型的例子中提出了基于约束满足的仿真算法,触发首事件的执行来推进仿真时钟。与一般的时间步长推进方法相比较,此算法可以显著提高仿真执行的效率。介绍此算法的基础上,详细给出了在装甲车辆仿真中的侦察模型(首事件)中应用的算法步骤。对该算法执行效率进行了验证。并且可以推广到一般意义的离散事件系统仿真中。     

PDES中乐观时间同步的时空损耗研究

并行离散事件仿真对复杂大规模动态系统的研究以及探索其长远的应用提供了便利,近年来日益成为研究的热点。然而时间同步管理是影响并行离散事件仿真系统高效运行的重要因素之一。乐观的同步是采用检测和回退机制,允许逻辑进程积极的处理本地事件。一旦出现同步错误则利用回退机制从错误中恢复到较早状态,然后再恢复执行。这一切都是通过基于检查点状态保存重建机制来实现的,因而状态保存及状态重建必然伴随着时间和空间的损耗。该文深入研究了在乐观同步机制下,仿真执行时间和内存空间的损耗与检查点间隔之间的关系,并通过推理计算给出了检查点间隔的最优取值范围。     

基于远程过程调用和壁垒同步的分布式离散事件仿真模型

针对多处理器高数据量情况的并行离散事件仿真提出了一种高效的仿真模型。仿真采用时间步进的推进方式,运用远程过程调用(RPC)分布调用机制实现仿真成员之间的互操作。仿真中采用壁垒同步机制保证仿真推进时的时间同步,以确保因果关系正确。实践证明,在保证了仿真准确性的前提下,该模型可对传输层和网络层协议进行仿真测试,能够对大数据量进行准确实时的处理,并在一定程度上提高了仿真效率。     

基于PDES的弹性周期同步算法研究

并行分布仿真对复杂大规模动态系统的研究以及探索其长远的应用提供了便利,近年来日益成为研究的热点.然而时间同步管理是关注并确保并行分布仿真正确执行的一种机制,它不但要确保正确的执行因果逻辑关系,而且要保证仿真系统的可重复性.时间管理是影响并行分布仿真系统高效运行的重要因素之一.文章首先指出了常用乐观时间同步机制固有的缺点;其次重点描述了事件推进限这一重要概念及弹性周期同步算法的设计与实现;最后对弹性周期同步算法的性能进行了较为深入的探讨.首先对该算法进行了定性的综合评估,随后详细讨论了弹性周期同步算法的关键性能参数M的定量理论分析与推导.     

离散事件系统规范DEVS研究

离散事件系统是一类常见的系统，如何对这类系统进行描述与建模是离散事件系统仿真研究的核心内容。离散事件系统规范DEVS是一种离散事件系统形式化描述方法，它具有层次化和模块化的特点，利用该方法可对复杂的离散事件系统进行建模、设计、分析和仿真。该文详细介绍了DEVS基本模型和耦合模型，给出了DEVS在耦合运算下的封闭性构造证明，并提出了一种具有嵌套层次结构的DEVS耦合模型实现算法，该算法对基于DEVS描述的离散事件系统的仿真实现具有一定参考价值。     

一种层次的、混合并行离散事件仿真算法

并行仿真算法是并行离散事件仿真中心的核心问题，对于具体的应用系统，采用不同的并行仿真算法将导致其仿真性能大的差异，提出了一种针对于分布环境中特定应用系统仿真的层次的，混合并行离散事件仿真算法，测试和应用表明，和通常的保守机制或者乐观机制相比，能够较大地提高仿真效率，并且具有良好的可扩展性，首先给出了在通信开销不可忽略的环境下，保守机制和乐观机制的性能测试结果和两者适用情况的分析，然后根据测试结果和具体应用系统的特点，提出了层次的，混合并行离散事件仿真算法，给出了LP级和组级算法算，最后对算法进行了测试和性能分析。     

基于分布对象的离散事件仿真系统

分布对象技术将面向对象的概念揉合到分布计算中,使得基于对象的软件成员在分布异构环境中可重用、可移植和可互操作。文章把分布对象技术用于离散事件系统仿真中,通过对离散事件系统中分布对象的标识,分布对象间同步机制的讨论,提出了基于分布对象离散事件仿真系统的结构,定义了分布仿真对象的接口。     

分级调度的分布离散事件系统仿真策略

分布离散事件系统仿真中的仿真策略,是离散事件系统仿真领域研究的一个关键问题。文章提出了基于事件分级调度的仿真调度算法,并详细介绍了算法的基本思想,给出了算法的步骤和流程图,最后对算法进行了简要的分析。     

Dataflow computer extension towards real-time processing

This paper presents an extended architecture and a scheduling algorithm for a dataflow computer aimed at real-time processing. From the real-time processing point of view, current dataflow computers have several problems which stem from their hardware mechanisms for scheduling instructions based on data synchronization. This mechanism extracts as many eligible instructions as possible for execution of a program, then executes them in parallel. Hence, the computation in a dataflow computer is generally difficult to interrupt and schedule using software. To realize a controllable dataflow computation, two basic mechanisms are introduced for serializing concurrent processes and interrupting the execution of a process. A parallel and distributed algorithm for the scheduler is presented, with these two mechanisms, which controls and decides state transitions and execution order of the processes based on priority and execution depth, while still maintaining the number of the running state processes at a preferred value. To gear the scheduler algorithm to meet one of the requirements for real-time processing, such as time-constrained computing, a data-parallel algorithm for selection of the user-process with the current highest priority in O (x log _x n) time is proposed, where n is the number of priority levels.     

面向并发程序中锁机制的智能化推荐方法

软件开发人员在并发编程中面临着各种Java锁的选择。针对如何选择合适的锁机制进而提高程序性能的问题,提出了一种帮助并发程序开发人员选择锁机制的推荐方法LockRec。首先,采用程序静态分析技术,对并发程序中锁机制的使用进行分析并确定影响程序性能的程序特征属性;然后,使用改进的随机森林算法构建锁机制推荐模型,以帮助开发人员在同步锁、可重入锁、读写锁、邮戳锁这四种锁之中进行选择。分别选取了四种现有的机器学习数据集对LockRec进行了实验,所提方法的推荐准确率均值可达95.1%;此外使用真实并发程序对LockRec的推荐结果进行分析。实验结果表明LockRec可以有效提高并发程序的执行效率。     

一个支持非独立“与”并行的逻辑程序“与”并行执行模型

本提出了一种支持非独立“与”并行的新型“与”并行执行模型ＤＡＰＭ，它通过在共享变元之间建立一种类似生产和消费的同步依赖关系以防止它们在并行执行时产生的约束冲突。与其它模型相比，ＤＡＰＭ可以开发更多的“与”并行。本还从理论上对ＤＡＰＭ的运行代价进行了分析，其分析结果表明ＤＡＰＭ只需较小的运行时刻支持。     

Dynamic synchrony among atomic actions

Synchrony continues to be an important concern in concurrent programming. Existing languages and models have introduced a great diversity of constructs for expressing and managing synchronization among sequential processes or atomic actions. The authors put forth a model in which synchrony is viewed as a relation among atomic actions, a relation which may evolve with time. The model is shown to be convenient for expressing formally the semantics of synchrony as it appears in many of the languages and models proposed to date. Among such models Swarm is singled out for its use of dynamic synchrony. The Swarm notation is briefly reviewed. A new concurrent algorithm for the leader election problem illustrates the use of dynamic synchrony in Swarm     

基于网络编码的手机用户群文件共享和同步

为了快速、准确的实现一跳范围内手机用户群的文件共享,以达到手机用户之间进行协同工作的目的,在Android操作平台上设计、实施了本系统。在系统中提出了基于网络编码的可靠广播算法来保证文件传输的可靠性和快速性,并通过基于机会编码的全网同步算法来实现任一时刻手机群中各节点文件同步。通过真实实验验证了系统中文件共享的时延并不会随着手机群中节点数目的增加而增加,文件同步时网络中数据量大幅度下降,因此相比并发共享等其它方法,系统提供了一种快速、可靠的手机群文件共享和同步方法。     

云计算环境中面向DAG任务的多目标调度算法

为了实现任务执行效率与执行代价的同步优化,提出了一种云计算环境中的DAG任务多目标调度优化算法。算法将多目标最优化问题以满足Pareto最优的均衡最优解集合的形式进行建模,以启发式方式对模型进行求解;同时,为了衡量多目标均衡解的质量,设计了基于hypervolume方法的评估机制,从而可以得到相互冲突目标间的均衡调度解。通过配置云环境与三种人工合成工作流和两种现实科学工作流的仿真实验测试,结果表明,比较同类单目标算法和多目标启发式算法,算法不仅求解质量更高,而且解的均衡度更好,更加符合现实云的资源使用特征与工作流调度模式。     

Formalizing the specification and execution of workflows using the event calculus

The event calculus is a logic programming formalism for representing events and their effects especially in database applications. This paper proposes the event calculus as a logic-based methodology for the specification and execution of workflows. It is shown that the control flow graph of a workflow specification can be expressed as a set of logical formulas and the event calculus can be used to specify the role of a workflow manager through a set of rules for the execution dependencies of activities. The proposed framework for a workflow manager maintains a history of events to control the execution of activities. The events are instructions to the workflow manager to coordinate the execution of activities. Based on the already occurred events, the workflow manager triggers new events to schedule new activities in accordance with the control flow graph of the workflow. The net effect is an alternative approach for defining a workflow engine whose operational semantics is naturally integrated with the operational semantics of a deductive database. Within this framework it is possible to model sequential and concurrent activities with or without synchronization. It is also possible to model agent assignment and execution of concurrent workflow instances. The paper, thus, contributes a logical perspective to the task of developing formalization for the workflow management systems.     

Parallel distributed-time logic simulation

The Chandy-Misra algorithm offers more parallelism than the standard event-driven algorithm for digital logic simulation. With suitable enhancements, the Chandy-Misra algorithm also offers significantly better parallel performance. The authors present methods to optimize the algorithm using information about the large number of global synchronization points, called deadlocks, that limit performance. They classify deadlocks and describe them in terms of circuit structure. The proposed methods that use domain-specific knowledge to avoid deadlocks and present a way to reduce greatly the time it takes to resolve a deadlock. For one benchmark circuit, the authors eliminated all deadlocks using their techniques and increased the average number of logic elements available for concurrent execution from 45 to 160. Simulation results for a 60-processor machine show that the Chandy-Misra algorithm outperforms the event-driven algorithm by a factor of 2 to 15     

Core frequency adjustment to optimize Time Warp on many-core processors

Time Warp synchronized parallel discrete event simulators are organized to operate asynchronously and aggressively without explicit synchronization between the concurrently executing simulation objects. In place of an explicit synchronization mechanism, the concurrent simulators implement an independent but common virtual clock model and a rollback/recovery mechanism to restore causal order when out-of-order events are detected. When the critical path of execution of the simulation is balanced across this parallel threads of execution, this can result in a highly effective, lightweight synchronization mechanism to implement parallel simulation. However, imbalances in the workload across the threads can result in excessive rollback in some threads and slowed progress of the critical path. On small shared memory multi-core systems, a lowest time-stamp scheduling policy can effectively balance the workload. However, on larger many-core chips, conventional load balancing and workload migration will once again become necessary. Fortunately, emerging many-core chips contain some interesting features that can potentially be exploited to improve the performance of parallel simulations. In particular, the recently developed Intel Single-chip Cloud Computer (SCC) provides mechanisms for the runtime control of the frequency and voltage settings of the chip. Furthermore, the frequency and voltage settings are independently set within different regions (called islands) of the chip. Thus, in a Time Warp simulation, one could increase the frequency of the cores executing threads on the critical path (those experiencing infrequent rollback) and decrease the frequency of the cores executing threads off the critical path (those experiencing excessive rollback). This paper investigates the run-time control and adjustment of core frequency in some contemporary x86 multi-core processors to identify the platforms that can support the exploration of dynamic run-time control of core frequency settings. The results show that while all multi-core processors have software controllable core frequency modulation capabilities, they are generally not fully independent as the system comes under load and are therefore unsuitable for these studies. Fortunately, one processor, the AMD X6 line, provides software control for core frequencies that can be fixed (by software) even as the system operates under load.