基于RTEthernet改进的时钟同步算法

以太网其庞大的网络系统在复杂的环境中存在网络链路延迟,节点时钟的漂移,同步能力差等问题。通过研究RTEthernet协议的起源和工作原理,考虑到影响实时以太网时间同步精密度的时钟拜占庭故障、网络传输延迟和漂移率等三个因素,建立了符合RTEthernet协议的通信模型。对FTA时钟同步算法在故障下时钟同步精密度损失率提升较少的问题进行了研究,引入了滑动窗口技术,提出了容错滑动窗口（Fault-Tolerant Sliding Window, FTSW）算法。容错滑动窗口算法能进一步提高分布式系统在进行时钟同步是对故障节点的容错能力。最后,使用CANoe仿真工具对FTSW算法进行仿真验证, FTSW算法的容错性优于FTA时钟同步算法算法,且在系统（七个节点）中存在两个拜占庭故障的情况下,同步后的精密度损失率降低了7.1%。     

基于分布式系统实现时钟同步的统计平均算法

讨论了分布式系统中时钟同步的系统模型,远端时钟读取方法以及双向通信传输过程,给出了3种不同的时钟同步方案,同时,对基于多次同步消息的冗余传输,提出了新的基于统计平均的时钟同步算法。通过多步时间传输协议,在较短同步周期内对时钟进行同步。     

IEEE1588精确时钟同步协议从时钟设计

时钟漂移与传输延时的不确定性是分布式系统时钟同步中不容忽视的问题,它直接影响同步精度。分析了IEEE 1588精确时钟同步协议的同步机制,设计了从时钟的硬件结构,提出了结合数据滤波和锁相环PI调节的高精度时钟同步算法。     

时钟同步的假设检验研究

时钟同步技术是分布式系统中非常活跃的研究领域之一,由于大多数分布式系统实际上是不同步的,因此需要采用容错时钟同步算法确保消息通信的有界延迟,而基于假设检验的时钟同步技术可以避免因错失对两个高概率不同步时钟进行同步调整而造成系统不正常使用的情况。该文讨论了时钟同步的假设检验问题。除了假设检验、两类错误概率,还给出了概率最小时钟偏差、时钟同步概率等概念。在时钟偏差的统计分布特性近似于服务正态分布的假设条件之下,提出了基于非中心t分布的时钟同步假设检验方案。最后,基于服务器和客户端之间双向消息通信传输模式,给出时钟偏差的估计和检验样本。     

小型分布式系统中进程同步的实现

本文主要讨论了分布式系统中进程同步的重要意义,并对两种不同的进程同步方式进行了比较,最后给出了在小型分布式系统中实现时钟同步的一个算法。     

IEEE 1588时钟同步技术在分布式系统中的研究*

为实现分布式系统高精度同步数据采集及实时控制,提出一种基于 IEEE 1588协议的分布式系统时钟同步方法。论文深入分析了IEEE 1588协议的算法原理和本地时钟同步主时钟的过程,提出了时间戳的IEEE 1588实现方案,提供了硬件设计方法,阐述了主从时钟的软件设计流程,在此基础上对主从时钟的同步进行了验证。实验证明：该方法是切实可行的,同步结果达到了10μs同步,为下一步将IEEE 1588大规模应用到分布式工业控制系统中起到了借鉴的作用。     

航天器时间触发系统时钟同步算法的仿真分析

时间触发技术已经逐步应用于航天器导航制导与控制(GNC)系统的信息体系结构设计中,由于时间触发技术使用了经典的Welch-Lynch分布式时钟同步算法[1]因此在工程应用中存在固有的系统级时钟定向漂移问题[2].针对上述问题,提出了一种使用单一精确时钟对全系统进行整体时钟校时的方案,根据分布式系统工作时序的特点,使用同步误差的算法解决了单一节点无法修正整个分布式系统参数的问题,使系统可以在有限偏差范围内不断调整时钟相位,避免了系统级的时间误差累计.使用形式化方法对算法进行了有界性和收敛性证明,并在Matlab/Simulink平台中对基于时间触发体系结构的GNC系统进行了数学建模和仿真,仿真结果表明GNC系统内所有节点的时钟偏差收敛且有界,满足实际使用需求.     

基于NiosⅡ软核的工业以太网精确时钟同步的实现

介绍了基于NiosⅡ嵌入式软核处理器的工业以太网设备间精确时钟同步的设计与实现.利用Altera公司的Nios Ⅱ处理器,添加片内外设和存储器以及与片外存储器和外设相连的接口,通过SOPC(可编程片上系统)技术嵌入到FPGA芯片中形成Nios Ⅱ处理器系统硬件平台;软件部分移植uC/OS-Ⅱ作为操作系统,Lwip(轻量级TCP/IP协议)处理网络协议,在应用层上实现状态转换、同步报文处理和精确时钟算法.测试结果表明时钟同步精度高,并且最终在一个工业以太网实验平台上进行了长期的实际运行,系统稳定性良好.     

分布式系统时钟同步设计与实现

时钟同步是分布式系统的核心技术之一，考虑到分布式系统的可扩展性及同步精度要求，提出了基于GPS与NTP的混合同步方案解决系统时间同步问题，并对其原理与实现进行了阐述。     

一种分布式时钟同步技术设计

时钟同步是分布式网络内各节点设备协同工作的重要前提,网络内许多任务的完成都需以时钟同步作为基础;为了实现分布式系统中高精度的时钟同步,文章在现有的时钟同步技术的基础上,设计了一种分布式时钟同步技术,以北斗卫星授时技术作为主同步机制,单向时钟同步技术作为辅助同步机制;即在正常情况下网络中的节点设备利用北斗卫星进行授时,而在无法顺利接收北斗授时信号的少数情况下,节点设备之间利用单向时钟同步技术完成时钟同步,两者结合共同实现不同情况下高精度的时钟同步;在LabVIEW编程环境下设计仿真程序对方案进行验证,结果表明,该方案可以实现分布式系统中的时钟同步,方案的可行性可以得到验证,然后通过进一步的误差分析可知,误差处在一个可接受的范围内.     

多处理器计算环境中基于能量节约的实时动态调度算法

当前处理器由于较高的能量消耗，导致处理器热量散发的提高及系统可靠性的降低，已经成为目前计算机领域较为关心的问题．然而目前一些有效降低能量消耗的技术大多针对单处理器系统，较少考虑多处理器系统．提出的调度算法针对多处理器计算环境，以执行时间最快的任务优先调度为基础，结合其它有效技术（共享空闲时间回收），使得实时任务在其截止期内完成的同时能够有效地减低整个系统的能量消耗．针对独立任务集及具有依赖关系的任务集，提出两种针对同构计算环境的算法：STFBA1（Shortest—Task—First—Based Algorithm）及STFBA2，及两钟针对多任务集的算法HSA1（Hybrid Seheduling Algorithm）及HAS2．在单任务集计算环境下，与目前所知的有效算法相比，算法具有更好的性能（调度长度及能量消耗）．在多任务集计算环境下，基于混合调度策略的算法能够明显改进调度性能．     

实时多处理器系统中基于能量节约的动态调度算法

当前处理器由于较高的能量消耗。导致处理器热量散发的提高及系统可靠性的降低，已经成为目前计算机领域较为关心的问题．然而目前一些有效降低能量消耗的技术大多针对单处理器系统，较少考虑多处理器系统．本文提出的调度算法针对多处理器系统，以最短任务优先调度为基础，结合其它有效技术，如共享空闲时间回收等，使得实时任务在其截止期内完成的同时能够有效地减低整个系统的能量消耗．针对独立任务集及具有依赖关系的任务集，本文提出两种算法：STFBA1及STFBA2（Shortest Task First—Based Algorithm）．与目前所知的有效算法相比，我们的算法具有更好的性能（调度长度及能量消耗）．     

Energy and transition-aware runtime task scheduling for multicore processors

Many embedded or portable devices have large demands on running real-time applications. The designers start to adopt the multicore processors in these devices. The multi-core processors, however, cause much higher power consumption than ever before. To resolve this problem, many researchers have focused their studies on designing the energy-aware task scheduling algorithms for multicore processors. Conventional scheduling algorithms assumed that each core can operate under different voltage levels. However, they have not considered the effects of voltage transition overheads, which may defeat the benefit of task scheduling. In this paper, we aim to resolve this scheduling problem with voltage transition overhead consideration. We formalize this problem by an integer linear programming model and propose a heuristic algorithm for a runtime environment. The experimental results show that the proposed online heuristic algorithm can obtain the comparable results with the optimal scheduling derived by the offline integer linear programming approach.     

Complete exchange on the CM-5 and Touchstone Delta

The complete exchange (or all-to-all personalized) communication pattern occurs frequently in many important parallel computing applications. It is the densest form of communication because all processors need to communicate with all other processors. This can result in severe link contention and degrade performance considerably. Hence, it is necessary to use efficient algorithms in order to get good performance over a wide range of message and multiprocessor sizes. In this paper we present several algorithms to perform complete exchange on the Thinking Machines CM-5 and the Intel Touchstone Delta multiprocessors. Since these machines have different architectures and communication capabilities, different algorithms are needed to get the best performance on each of them. We present four algorithms for the CM-5 and six algorithms for the Delta. Complete exchange algorithms generally assume that the number of processors is a power of two. However, on the Delta the number of processors allocated by a user need not be a power of two. We propose algorithms that are even applicable to non-power-of-two meshes on the Delta. We have developed analytical models to estimate the performance of the algorithms on the basis of system parameters. Performance results on the CM-5 and Delta are also presented and analyzed.     

Approximation algorithms in partitioning real-time tasks with replications

Today is an era where multiprocessor technology plays a major role in designs of modern computer architecture. While multiprocessor systems offer extra computing power, it also opens a new range of opportunities to improve fault-robustness. This paper focuses on a problem of achieving fault-tolerance using replications in real-time, multiprocessor systems. In the problem, multiple replicas, or copies, of a computing task are executed on distinct processors to resist potential processor failures and computing faults. Two greedy, approximation heuristics, named Worst Fit Increasing K-Replication and First Fit Increasing K-Replication, are studied to maximise the number of real-time tasks assigned on a system with identical processors, respecting to the tasks’ replicating and timely requirements. Worst case performance is analysed by using an approximation ratio between the algorithms and an optimal solution. We mathematically prove that the ratios of using both algorithms are infinitely close to 2. Simulations are performed on a large set of testing cases which can be used to bring to light the average performance of using the algorithms in practice. The results show that both heuristic algorithms provide simple but fast and effective solutions to solve the problem.     

Performance Measures for Evaluating Algorithms for SIMD Machines

This paper examines measures for evaluating the performance of algorithms for single instruction stream–multiple data stream (SIMD) machines. The SIMD mode of parallelism involves using a large number of processors synchronized together. All processors execute the same instruction at the same time; however, each processor operates on a different data item. The complexity of parallel algorithms is, in general, a function of the machine size (number of processors), problem size, and type of interconnection network used to provide communications among the processors. Measures which quantify the effect of changing the machine-size/problem-size/network-type relationships are therefore needed. A number of such measures are presented and are applied to an example SIMD algorithm from the image processing problem domain. The measures discussed and compared include execution time, speed, parallel efficiency, overhead ratio, processor utilization, redundancy, cost effectiveness, speed-up of the parallel algorithm over the corresponding serial algorithm, and an additive measure called "sprice" which assigns a weighted value to computations and processors.     

基于异构分布式系统的实时容错调度算法

目前文献中研究的实时容错调度算法都是基于同构分布式系统，系统中的所有处理机完全相同。该文首先建立了一个基于异构分布式系统实时容错调度模型，异构分布式系统中的各个处理机均不相同。基于该异构分布式系统模型，该文引入了可靠性代价（reliability cost）概念，并提出两种静态实时容错调度算法（RTFTNO和RTFTRC）用于调度周期性实时容错任务。算法RTFTRC在调度任务时，尽量使系统的可靠性代价最小；而算法RTFTNO在调度实时任务时，没有考虑系统的可靠性代价。该文详细讨论了两种调度算法的性能。性能模拟实验分别比较了两个算法的可靠性代价，超时比率和可调度性；并研究了任务的计算时间与可靠性代价的关系以及调度长度阈值与最小处理机个数的关系。实验结果表明，算法RTFTRC的性能优于算法RTFTNO。     

A scattering framework for decentralized estimation problems

In this paper we develop a comprehensive framework for the study of decentralized estimation problems. This approach imbeds a decentralized estimation problem into an equivalent scattering problem, and makes use of the super-position principle to relate local and centralized estimates. Some decentralized filtering and smoothing algorithms are obtained for a simple estimation structure consisting of a central processor and of two local processors. The case when the local processors exchange some information is considered, as well as the case when the local state-space models differ from the central model.     

Reliable synchronization in distributed systems

In distributed computer systems, processors often need to be synchronized to maintain correctness and consistency. Unlike shared-memory parallel systems, the lack of shared memory and a clock considerably complicates the task of synchronization in distributed systems. The objective of this article is two-fold: (1) We present a new randomized agreement algorithm to synchronize cooperating processors in a distributed system. This algorithm achieves the desired agreement in expected five rounds of message exchanges, tolerating a maximum of one-fifth of the processors failures. The algorithm belongs to the class of broadcast-based synchronization problems. (2) We present a new self-stabilization algorithm for an acyclic directed-graph structured distributed systems. This new fault-tolerant algorithm survives all imaginable faults in distributed systems. The algorithm belongs to arbiter-based and broadcast-based synchronization problems.     

一种用于异构环境中任务调度的高效算法

在异构计算环境中,有效的任务调度对于获得高性能是十分重要的。现在虽然已经有许多异构处理器调度算法,但它们或者不具有良好的效果,或者算法代价太高。提出了一种新的基于表的调度算法APS。APS利用有向无环图来计算任务优先级,并采用基于调度的策略分配任务到不同处理器,以获得任务最少完工时间。将APS和LMT,HEFT,CPOP算法做比较之后得出：在大多数情况下APS算法都能获得更好性能。