Search

In the most general form, clock skew scheduling (CSS) generates a dedicated clock delay for each individual sequential component in the clock distribution network in order to minimize the clock period. Multidomain CSS (MDCSS) relieves this requirement. Instead, sequential components are grouped into several clusters (called clock domains), each of which has a uniform clock delay for all registers within that domain. The skew values of clock domains are provided by a set of deskew buffers with electrically programmable phase shifts and injected after the chip is manufactured. This technique is attractive since, due to process variations, it is becoming overwhelmingly difficult to create precise clock network delays for all sequential elements in a design globally. In this paper, we present a fast algorithm for determining the minimum number of clock domains to be used by MDCSS. The exact solution to this problem cannot be found within a reasonable time if the number of clock domains increases beyond three domains. We show that, even with a small-size circuit, in order to obtain the minimum clock period, more than three clock domains may be required. Therefore, a fast heuristic algorithm is needed to identify these domains. To the best of our knowledge, we present the first efficient heuristic algorithm for this problem. For large benchmark circuits, we solve the problem within 14.7 min on average (as high as 31.7 min for the worst case), while a commercial mixed-integer linear program solver cannot finish in over 5 h. Furthermore, our results show that, for 19 out of 21 small- and medium-size benchmarks, our algorithm yields the optimal solution.

This paper is concerned with multiple motor control using a distributed network control method. Speed and position of multiple motors are synchronized using clock synchronized distributed controllers. CAN (controller area network) is used and a new clock synchronization algorithm is proposed and implemented. To verify the proposed control algorithm, two disks which are attached on two motor shafts are controlled to rotate at the same speed and phase angle with the same time base using network clocks.

In this paper we propose a novel distributed clock synchronization protocol for networks of clocks which have different initial offsets and internal clock speeds. The algorithm is based on an PI-like consensus protocol where the proportional (P) part compensates the different clock speeds while the integral part (I) eliminates the different clock offsets. This synchronization protocol is formally studied in its synchronous implementation and we provide both convergence guarantees as well optimal design using standard optimization tools when the underlaying communication graph is known. We also show how this protocol can be readily used to study the effect of noise and external disturbances on the steady-state performance. Finally, some simulations are presented.

Timestamp conversion is an important consideration in the deployment of distributed architectures. In this article we propose a precise, low-cost solution for on-line and post-processing timestamp conversion in distributed architectures, robust as regards the plugging and unplugging of hardware and the addition of new nodes (that is to say the different pieces of hardware connected to the network), not synchronized, and with no negative impact on the conversion quality. Each node (e.g., a computer) has at least one free-running clock. This clock's time is the reference for all events used by the node. When the local node needs to record the time of an event timestamped by a remote node, the time is converted from the remote node's time to the local node's time. Interval timestamping is used, to take account of time imperfections (e.g. sensor and computer latencies, or due to time conversion between the different computers). A network clock is used, enabling a precise conversion and avoiding exchanges of messages for the conversion of clock correspondences. Moreover, it allows an unlimited number of nodes in the network.

We study the problem of providing a sensor with an accurate estimate of the time, from a novel perspective which is complementary to the well-studied clock synchronization problem. More precisely, we analyze the case in which a sensor node is temporarily unable to run a clock synchronization protocol due to failures or intermittent connectivity, or is willing to skip one or more clock adjustments to save energy, but still requires an accurate estimate of the reference time. We propose and analyze two simple and efficient clock reading methods, one deterministic and the other probabilistic, which are designed to work in synergy with a clock synchronization protocol. Our deterministic method achieves a better time accuracy by exploiting information regarding the sign of the deviation of the hardware clock from the reference time. This algorithm leads to noticeable energy savings since it can be applied to reduce the frequency of the periodic clock adjustments by a factor of 2, while maintaining the same error bound. Moreover, our method is of theoretical interest since it shows how a stronger but realistic clock model leads to a refinement of the optimality bound for the maximum deviation of a clock that is periodically synchronized. We also propose two simple versions of this algorithm: a method that guarantees the monotonicity of the clock values, and a generalization that improves the accuracy in case of clock stability. Our probabilistic method is based on time series forecasting, and provides a probabilistically accurate estimate of the reference time with a constant error bound. It is more flexible than our previous methods since it does not depend on the frequency at which clock synchronization occurs, and can be dynamically tuned according to the application requirements and resource availability. All these methods have broad applicability for their generality. In sensor networks they can be applied to improve the clock accuracy of a sensor node in conditions of network isolation, or to reduce the frequency of the clock adjustments, thus saving energy and increasing the system lifetime.

Multi matrix is extended concept of the matrix clock. The concept of multi matrix clock is used in the distributed computing environment, when multicore processor systems are used in the distributed system. Multi matrix clock gives information of own process event as well as information about other processes which are running concurrently. Multi matrix clock synchronization algorithm is based on exchanging clock information among the nodes and tries to eliminate the effects of non-determinism in the message delay and data processing time. Multi matrix clock may contain many matrices at single events. And these matrices always follow the matrix clock synchronization rule. Multi matrix can be used in the check pointing as well as garbage collection.

In this paper, a novel circuit for clock synchronization utilizing an interleaved delay line for coarse tuning and a phase interpolation component for fine tuning is proposed. The interleaved delay line improves the precision to nearly half of conventional SMD and roughly aligns the output clock in two cycles. The rest phase error is compensated by the fine tuning component with binary search scheme and phase interpolation in five clock cycles and the error is suppressed under 3.1 ps. The circuit is designed and implemented using SMIC 130 nm 1P8M process with a 1.2 V voltage supply. The active area of proposed circuit is 260µm×140µm, and the total power consumption is 1.82mW@500MHz. The allowed operation frequency ranges from 200 MHz to 860 MHz, and the duty cycle varies in [32%, 77%]. It is compatible with the clock distribution networks and clock tree synthesis workflow aided by EDA software.

A matrix clock is advance concept after the vector clocks and matrix clock store the information of concurrent other processes which is work together. Matrix clock is giving the solution if in a system there is no any events are occurring at the same time then it gives the unique solution. If we can store the information of sending event or receiving event at the same time at single matrix then we can say that matrix clock implementation which will be effective. Matrix clock is higher dimensional clock that can give the additional knowledge of processes. Matrix clock conclude the higher level of knowledge than any of the vector clock because it stores the matrix and vector clock store the vector level information.

In distributed applications, multiple processes are cooperating with one another by exchanging messages in networks. Information systems like cloud computing systems are getting scalable, which are composed of a huge number of processes. In group communications, messages sent by processes have to be causally delivered to every process in a group. The vector clock is widely used in group communication protocols but cannot be adopted to scalable groups due to communication and computation overheads. In the linear clock, the message length is O(1) but some pairs of messages are unnecessarily ordered even if the messages are not required to be causally delivered. In this paper, we discuss a communication protocol for a scalable group where linear clock and physical clock are used to reduce the number of pairs of messages unnecessarily ordered. We consider a group of multiple processes where the maximum offset of every physical clock is the same, i.e. homogeneous clock but maximum delay time between every pair of processes is not the same, i.e. heterogeneous network. We evaluate the protocol and show the number of pairs of unnecessarily ordered messages can be reduced compared with the linear clock protocol.

With the growing scale of integration, it is demand for next-generation VLSI design to consider not only the number of resources, but also the bitwidths of them. Removing wasted bits of resources, the area and power costs are optimized rather than conventional design. This paper shows that intentional clock skew (useful clock skew) is effective to improve the performance of bitwidth-aware circuits, and formulates a novel problem of clock skew scheduling to minimize the clock period during register allocation and binding under the total bitwidth constraint. A mixed integer linear programming-based approach is presented to formally draw up the problem. Experimental results show that the proposed approach can reduce 9.4% clock period on average over the conventional design.

Clock skew scheduling is a common and well known technique to improve the performance of sequential circuits by exploiting the mismatches in the data path delays. Existing clock skew scheduling techniques, however, cannot effectively consider heavily gated clock networks where a local clock tree exists between clock gating cells and registers. A methodology is proposed in this paper to efficiently achieve clock skew scheduling in circuits with gated clock networks. The methodology is implemented via both linear programming and constraint graph based approaches, and evaluated using the largest ISCAS'89 benchmark circuits with clock gating. The results demonstrate up to approximately 21% reduction in clock period while maintaining the power savings achieved by clock gating. A conventional design flow is used for the experiments, demonstrating the applicability of the proposed algorithms to automation.

International audience; This paper studies the clock synchronization problem in highly dynamic networks. We show that diffusive synchronization algorithms are well adapted to environments in which the network topology may change unpredictably. In a diffusive algorithm, each node repeatedly (i) estimates the clock difference to its neighbors via broadcast of zero-bit messages, and (ii) updates its local clock according to a weighted average of the estimated differences. The system model allows for drifting local clocks, running at possibly different frequencies. We show that having a rooted spanning tree in the network at every time instance suffices to solve clock synchronization. We do not require any stability of the spanning tree, nor do we impose that the links of the spanning tree be known to the nodes. Explicit bounds on the convergence speed are obtained. In particular, our results settle an open question posed by Simeone and Spagnolini to reach clock synchronization in dynamic networks in the presence of nonzero clock drift. We also identify certain reasonable assumptions that allow for a significant higher convergence speed, e.g., bidirectional networks or random graph models.

Clock networks dissipate a significant fraction of the entire chip power budget. In contrast to most of the traditional works that handle the power optimization problem with clock routing or buffer sizing, we propose a novel register clustering methodology for power reduction of clock trees. Moreover, a fast three-stage clock tree synthesis (CTS) approach based on register clustering is presented to verify the validity of the methodology. By comparison with the state-of-the-art low power CTS research works Contango2.0 [21] and the CTS of Purdue University [16], our three-stage CTS approach achieves 1.30×, 1.07× smaller power consumption while exhibiting 2.01×, 1.52× smaller skew. Furthermore, the runtime of our CTS approach is 17.36×, 8.16× shorter than that of [21] and [16] respectively.

Incorporating timing constraints explicitly imposed by the data and control paths during clock network synthesis can enhance the robustness of the synthesized clock networks. With these constraints, a clock scheduler can be used to guide the synthesis of a clock network by specifying a set of feasible arrival times at the respective sequential elements. Clock scheduling can be either static or dynamic. In static clock scheduling, a clock schedule is first specified; next, a clock network is constructed realizing the prescribed schedule. Clock trees constructed using this approach may consume significant routing resources. In dynamic clock scheduling, the clock tree and clock schedule are both simultaneously constructed and determined, respectively. In earlier studies, the scalability of dynamic clock scheduling, which is essentially a shortest path problem, has been limited. The bottleneck is in finding the shortest paths between different vertices in an incrementally changing weighted graph. In this work, we present two clock schedulers that address the scalability issues by exploiting the sparsity of this weighted graph. Experimental results show that the proposed clock schedulers are one to two orders of magnitude faster compared to a published scheduler in an earlier work. The proposed clock schedulers are scalable, and are tested on a synthesized circuit with 348 710 cells, 57 491 sequential elements, and 496 727 explicit timing constraints.

Clock synchronization in wireless sensor networks (WSNs) assures that sensor nodes have the same reference clock time. This is necessary not only for various WSN applications but also for many system level protocols for WSNs such as MAC protocols, and protocols for sleep scheduling of sensor nodes. Clock value of a node at a particular instant of time depends on its initial value and the frequency of the crystal oscillator used in the sensor node. The frequency of the crystal oscillator varies from node to node, and may also change over time depending upon many factors like temperature, humidity, etc. As a result, clock values of different sensor nodes diverge from each other and also from the real time clock, and hence, there is a requirement for clock synchronization in WSNs. Consequently, many clock synchronization protocols for WSNs have been proposed in the recent past. These protocols differ from each other considerably, and so, there is a need to understand them using a common platform. Towards this goal, this survey paper categorizes the features of clock synchronization protocols for WSNs into three types, viz, structural features, technical features, and global objective features. Each of these categories has different options to further segregate the features for better understanding. The features of clock synchronization protocols that have been used in this survey include all the features which have been used in existing surveys as well as new features such as how the clock value is propagated, when the clock value is propagated, and when the physical clock is updated, which are required for better understanding of the clock synchronization protocols in WSNs in a systematic way. This paper also gives a brief description of a few basic clock synchronization protocols for WSNs, and shows how these protocols fit into the above classification criteria. In addition, the recent clock synchronization protocols for WSNs, which are based on the above basic clock synchronization protocols, are also given alongside the corresponding basic clock synchronization protocols. Indeed, the proposed model for characterizing the clock synchronization protocols in WSNs can be used not only for analyzing the existing protocols but also for designing new clock synchronization protocols. (C) 2014 Elsevier B.V. All rights reserved.

Clock synchronization is mostly needed in the distributed real-time system. Currently, the most popular Network Time Protocol (NTP) algorithm cannot meet the needs well due to its low accuracy (about 10 milliseconds) and high cost. Thus, an improved high-accuracy clock synchronization method is proposed in this paper to overcome errors and offsets. With this method, the error of clocks among computer nodes in distributed real-time system can be less than 2 milliseconds and high availability can be achieved. The method has been applied in national key engineering project.

Clock network synthesis is an important part of digital integrate circuit design. For the purpose of further reducing the effect of clock skew and On-chip Variation, this paper realized a clock mesh structure by using Encounter EDI tool basing on traditional clock tree synthesis. Experiment results validated the advantage of clock mesh in clock skew optimizing and On-chip Variation.

Time synchronization is critical in distributed environments. A variety of network protocols, middleware and business applications rely on proper time synchronization across the computational infrastructure and depend on the clock accuracy. The Network Time Protocol (NTP) is the current widely accepted standard for synchronizing clocks over the Internet. NTP uses a hierarchical scheme in order to synchronize the clocks in the network. In this paper we present a novel non-hierarchical peer-to-peer approach for time synchronization termed CTP--Classless Time Protocol. This approach exploits convex optimization theory in order to evaluate the impact of each clock offset on the overall objective function. We define the clock offset problem as an optimization problem and derive its optimal solution. Based on the solution we develop a distributed protocol that can be implemented over a communication network, prove its convergence to the optimal clock offsets and show its properties. For compatibility, CTP may use the packet format and number of measurements used by NTP. We also present methodology and numerical results for evaluating and comparing the accuracy of time synchronization schemes. We show that the CTP outperforms hierarchical schemes such as NTP in the sense of clock accuracy with respect to a universal clock.

This paper proposes the integration of internal and external clock synchronization by a combination of a fault-tolerant distributed algorithm for clock state correction with a central algorithm for clock rate correction. By means of hardware and simulation experiments it is shown that this combination improves the precision of the global time base in a distributed single cluster system while reducing the need for high-quality oscillators. Simulation results have shown that the rate-correction algorithm contributes not only in the internal clock synchronization of a single cluster system, but it can be used for external clock synchronization of a multi-cluster system with a reference clock. Therefore, deployment of the rate-correction algorithm integrates internal and external clock synchronization in one mechanism. Experimental results show that a failure in the clock rate correction will not hinder the distributed fault-tolerant clock state synchronization algorithm, since the state correction operates independently from the rate correction. The paper introduces new algorithms and presents experimental results on the achieved improvements in the precision measured in a time-triggered system. Results of simulation experiments of the new algorithms in single-cluster and multi-cluster configurations are also presented.

Owning to the asymmetry of Internet paths, more and more studies have turned to the measurement of one-way metrics. Since the clocks at end systems often behave diversely, the synchronization between end hosts is what we care about all along. In this paper, we firstly propose a general model for clock skew estimation in one-way measurements, which turns the problem of clock skew estimation to the solution of n-dimension equation group, and give the equation group needed based on different presumptions. We then present Piece-wise Reliable Clock Skew Estimation Algorithm (PRCSEA), which introduces reliability test to estimation results and eliminates the extra presumptions needed by other algorithms, such as only one clock adjustment in the measurements. PRCSEA solves the skew estimation problem in a heuristic way, and it can handle many special cases affecting the estimation of clock skew, such as routing change, clock hiccup and network congestion. PRCSEA is the only algorithm that can handle clock drift to the best of our knowledge.

We introduce the distributed gradient clock synchronization problem. As in traditional distributed clock synchronization, we consider a network of nodes equipped with hardware clocks with bounded drift. Nodes compute logical clock values based on their hardware clocks and message exchanges, and the goal is to synchronize the nodes' logical clocks as closely as possible, while satisfying certain validity conditions. The new feature of gradient clock synchronization (GCS for short) is to require that the skew between any two nodes' logical clocks be bounded by a nondecreasing function of the uncertainty in message delay (call this the distance) between the two nodes, and other network parameters. That is, we require nearby nodes to be closely synchronized, and allow faraway nodes to be more loosely synchronized. We contrast GCS with traditional clock synchronization, and discuss several practical motivations for GCS, mostly arising in sensor and ad-hoc networks. Our main result is that the worst case clock skew between two nodes at distance d or less from each other is Ω (d+log D/log log D), where D is the diameter1 of the network. This means that clock synchronization is not a local property, in the sense that the clock skew between two nodes depends not only on the distance between the nodes, but also on the size of the network. Our lower bound implies, for example, that the TDMA protocol with a fixed slot granularity will fail as the network grows, even if the maximum degree of each node stays constant.

This paper is motivated by the problem of coordinating a group of autonomous agents with asynchronous, uncertain clocks. Timing uncertainty is commonly studied in networked control, but most work focuses on a single controller. Coordination problems also have a large literature, but the effect of uncertain, asynchronous timing is less understood. This paper studies multi-agent systems in which each agent has linear dynamics and a simple stochastic clock derived from a Poisson process. Necessary and sufficient conditions for stability are given based on linear matrix inequalities (LMIs). The analysis is then applied to networked control with random sampling times, as well as an asynchronous consensus protocol.

In modern distributed measure and control systems, transmission and processing of real-time data requires each communication node to work in a unified time base in order to ensure the timeliness of data transmission. IEEE1588 precision clock synchronization protocol (PTP) is aimed to solve the high-precision clock synchronization, which supports software or hardware implementation. This paper analyzes the factors that affect the accuracy of clock synchronization. Considering the special requirements of the protocol implemented in embedded systems, we propose an adaptive exponential smoothing algorithm to achieve high-precision clock synchronization. Experiments show that this algorithm can significantly improve the accuracy of clock synchronization.

Clock synchronization is a crucial issue for scalable and accurate network performance measurements, especially when no external time sources are introduced. The paper presents a clustering based efficient and robust algorithm Optimized Top-Down Time series Segmentation (OTDTS) for clock synchronization between end-to-end systems. The computational complexity of OTDTS is of order O(KN2). Based on the one-way probe delay traces, the algorithm segments the delay time series at proper points, at which clock dynamics occur. End systems could achieve relative clock synchronization by estimating and removing the clock skew of each segment. Simulations on artificial data set and practical Internet measurement illustrate the availability and efficiency of OTDTS.

One reported weakness of the Controller Area Network protocol is its lack of a clock synchronization service. In this paper, we present the architecture of a hardware clock subsystem which provides CAN networks with such a clock synchronization service. Our architecture presents significant advantages in front of previously suggested solutions. First, it is orthogonal to any CAN network. Second, it is compatible with timer-driven as well as clock-driven real-time distributed systems. Third, it achieves high-precision clock synchronization. And fourth, it presents a fault-tolerant behaviour.

Matrix clocks are a generalization of the notion of vector clocks that allows the local representation of causal precedence to reach into an asynchronous distributed computation's past with depth $x$, where $x\ge 1$ is an integer. Maintaining matrix clocks correctly in a system of $n$ nodes requires that everymessage be accompanied by $O(n^x)$ numbers, which reflects an exponential dependency of the complexity of matrix clocks upon the desired depth $x$. We introduce a novel type of matrix clock, one that requires only $nx$ numbers to be attached to each message while maintaining what for many applications may be the most significant portion of the information that the original matrix clock carries. In order to illustrate the new clock's applicability, we demonstrate its use in the monitoring of certain resource-sharing computations.

This paper presents an innovative method to synchronize physical clocks for a computational grid, in particular for a computational grid linked through the asynchronous Intranet or Internet environments. The method discussed is an asynchronous self-adaptive clock synchronization mechanism. Two strategies for clock synchronisation are introduced. (1) Use continuous time intervals to calculate the precision of clocks, which can reduce the effect of network delay efficiently. (2) Every node synchronizes its clock with its leader actively. In addition, a node self-adaptive model is presented, and the relationship between the clock precision and synchronization time is induced, hence a node can predict when it should begin the synchronization process. Detailed simulation and extension of this issue are provided at the end of the paper. The presented model is both practical and feasible.

Nowadays, more and more often, complex systems are built by assembling together different system components. This technology also affects the construction of heterogeneous and/or hybrid systems where components can represent hardware sensors, software controllers, etc. Moreover the resulting system is normally distributed. These systems have often real-time constraints/requirements and each component is characterized by its own speed determined by its local clock. In this paper we present a framework to specify and statically analyze the architecture of a system as a network of (parallel) components, each one with its own local clock. Configuring the system means to formally define how to get the global clock out of the local clocks. This clock configuration step is “optimal” that is, it is the best way to relate the local clocks so that the maximum number of synchronizations in the system can happen. Besides the usual behavioral and timing analysis, it is, for example, possible to verify if, and how changing the local speed of a component can affect the global performance of the system.Components behaviors are specified by means of a simple process algebra. Local clocks are modeled as higher order terms in a given signature, and unification is used to define the common clock. Then an operational semantics defines which transitions a process can perform and which transitions let time to elapse. A set of case studies illustrate the approach.

This paper presents a survey of implementation of logical time in asynchronous distributed systems. We provide an argument that justifies the use of logical time as a mechanism for detecting causal relationships between events. Further, we formally introduce the notion of a logical time system (a logical clock) and proceed to discuss the properties of the scalar, vector, and matrix clocks. Finally, we consider the modifications of the vector clock that reduce the average communication overhead while retaining the property of isomorphism.

This paper presents a practical solution for detecting synchronization errors in parallel programs. These errors are: a lack of synchronization resulting in data races, conflicting synchronization resulting in deadlock and redundant synchronization resulting in a performance penalty. The solution consists of a combination of RecPlay, an efficient execution replay mechanism combined with automatic on-the-fly data race detection, deadlock detection and the detection of redundant synchronization during a replayed execution. The detection of data races, deadlocks and redundant synchronization normally introduces an important overhead during an execution, possibly altering the execution. However, by performing these extensive operations during a replayed and therefore unaltered execution there is almost no probe effect. Furthermore, the memory consumption during the data race detection is limited through the use of multilevel bitmaps and snooped matrix clocks. As the record phase of RecPlay is highly efficient, there is no need to switch it off, hereby eliminating the possibility of Heisenbugs because tracing can be left on all the time.

In this study, an innovative distributed method for achieving external clock synchronization is presented. Based on discrete-time clock models, it can realize synchronization of clocks while enabling their time to change at the same pace simultaneously. Stronger robustness against noisy measurements and clock rate drifts is gained by combining both controller and estimator design methods into the protocol. Additionally, a specifically designed communication scheme is proposed to make our protocols independent on global physical time. To render our protocols more practical, the control variable for clock synchronization is ensured bounded and a stopping criterion for implementation of the protocols is established. Finally, performance of the method is illustrated by certain numerical simulations.

A clock tree typically consumes substantial dynamic power, and thus the considerable heat generated by itself can cause serious clock-skew variations. In this paper, we propose a self-heating-aware buffered clock tree synthesis flow. A mixed integer linear programming (MILP) formulation is proposed to simultaneously model heat spreading, place buffers, and determine a temperature-aware clock tree topology. The formulation is then transformed into a succession of low-complexity feasibility problems to further reduce the runtime. In addition, a fast superposition approach is proposed to incrementally update thermal profiles to reduce simulation time. Experimental results show that our synthesis flow can achieve averagely 50.57% worst-case clock skew reduction, compared with the original symmetrical clock tree.

This paper describes a methodology used for the implementation flow of a system on chip circuit containing a complex clock design. The clock generation module contained 2 clock sources and 11 generated clocks. Many of them have interactive relationship. and the 2 clock sources generate the internal clocks in various modes. It uses the combination of bottom-up strategy and top-down strategy to accomplish the clock generation module implementation first, and then finish the whole chip design. This methodology of the solution makes the whole structure of the design distinct, saves a lot of iterative time, and reduces chip power consumption.

Synchronization and localization are critical challenges for the coherent functioning of a wireless network, which are conventionally solved independently. Recently, various estimators have been proposed for pairwise synchronization between immobile nodes, based on time stamp exchanges via two-way communication. In this paper, we consider a \textit{network of mobile nodes} for which a novel joint time-range model is presented, treating both unsynchronized clocks and the pairwise distances as a polynomial function of \textit{true} time. For a set of nodes, a pairwise least squares solution is proposed for estimating the pairwise range parameters between the nodes, in addition to estimating the clock offsets and clock skews. Extending these pairwise solutions to network-wide ranging and clock synchronization, we present a central data fusion based global least squares algorithm. A unique solution is non-existent without a constraint on the cost function (\eg clock reference node). Ergo, a constrained framework is proposed and a new Constrained \Cramer\ Rao Bound (CCRB) is derived for the joint time-range model. In addition, various constraints are proposed and their effects on the proposed algorithms are studied. Simulations are conducted and the proposed algorithm is shown to approach the theoretical limits., Comment: In submission

Clocks have a small in-built error. As the error is unique, each clock can be identified. This paper explores remote computer identification based on the estimation of clock skew computed from network packets. The previous knowledge of the method is expanded in various ways: (1) we argue about the amount of data that is necessary to get accurate clock skew estimation, (2) the study of different time stamp sources unveils several irregularities that hinders the identification, and (3) the distribution of clock skew in real network makes the precise identification hard or even impossible.

Selecting a clock period is an essential step in implementing hardware from behavioral descriptions. Current methods either estimate the clock prior to scheduling or involve exhaustive runs of the high-level synthesis tools to obtain a globally optimum clock period. Further, the potential benefits of allowing the use of multiple clocks for performance optimization has not been investigated. This paper presents a clock selection method that works simultaneously with synthesis by selecting a clock from an optimal clock set. The synthesis is iterative and is optimized by evolutionary techniques. The method is very flexible and can accommodate a large set of potentially optimal clocks. We also present multirate clock synthesis with path-dependent clock selection where different paths in a control data flow graph (CDFG) are optimized with different clock periods. The results shown prove the method's effectiveness.

In this paper, we investigate reducing the power consumption of a synchronous digital system by minimizing the total power consumed by the clock signals. We construct activity-driven clock trees wherein sections of the clock tree are turned off by gating the clock signals. Since gating the clock signal implies that additional control signals and gates are needed, there exists a tradeoff between the amount of clock tree gating and the total power consumption of the clock tree. We exploit similarities in the switching activity of the clocked modules to reduce the number of clock gates. Assuming a given switching activity of the modules, we propose three novel activity-driven problems: a clock tree construction problem, a clock gate insertion problem, and a zero-skew clock gate insertion problem. The objective of these problems is to minimize the system's power consumption by constructing an activity-driven clock tree. We propose an approximation algorithm based on recursive matching to solve the clock tree construction problem. We also propose an exact algorithm employing the dynamic programming paradigm to solve the gate insertion problems. Finally, we present experimental results that verify the effectiveness of our approach. This paper is a step in understanding how high-level decisions (e.g., behavioral design) can affect a low-level design (e.g., clock design).

Clock skew modeling is important in the performance evaluation and prediction of clock distribution networks. This paper addresses the problem of statistical skew modeling for general clock distribution networks in the presence of process variations. The only available statistical skew model is not suitable for modeling the clock skews of general clock distribution networks in which clock paths are not identical. The old model is also too conservative for estimating the clock skew of a well-balanced clock network that has identical but strongly correlated clock paths (for instance, a well-balanced H-tree). In order to provide a more accurate and more general statistical skew model for general clock distributions, we propose a new approach to estimating the mean values and variances of both clock skews and the maximal clock delay of general clock distribution networks. Based on the new approach, a closed-form model is also obtained for well-balanced H-tree clock distribution networks. The paths delay correlation caused by the overlapped parts of path lengths is considered in the new approach, so the mean values and the variances of both clock skews and the maximal clock delay are accurately estimated for general clock distribution networks. This enables an accurate estimate of yields of both clock skew and maximal clock delay to be made for a general clock distribution network.

One of the requirements for distributed control and estimation applications in wireless networks is that all nodes have a common timescale. Recently, a clock synchronization method has been proposed which is based on a model consisting of heterogeneous double-integrators and distributed linear update rules. In this paper, we extend these results to networks with directed communication topology. We provide necessary and sufficient conditions under which synchronization is guaranteed over directed graphs and present an easy-to-check graphical stability condition for analysis and design purposes. Furthermore, we characterize the resulting common clock speed of the synchronized network. Various numerical examples illustrate the results.

Clock synchronization allows the establishment of a global time base, a requirement for many distributed systems applications. The properties that can be expected from clocks in a computer system are presented and formalized. Some of these properties are not present in the physical clock, and they must be enforced by means of clock synchronization. Several solutions can be found in the literature. A classification for is presented, which will make easier the choice of a clock synchronization solution for a specific system.

Communications between processing elements (PEs)in very large scale parallel systems become more challenging as the function and speed of the PEs improve continuously. Clocked I/O ports may malfunction if data read failure occurs due to clock skew. There are many drawbacks in global clock distribution utilized to reduce the clock skew. This paper addresses a self-tested self-synchronization (STSS) method for vector transfer between PEs. A test signal is added to remove the data read failure. The advantages of this method are: very high data throughput, less power consumption in clock distribution, no constraints on clock skew and system scale, easy in design, less latency. A failure zone concept is used to characterize the behavior of storage elements. By using a jitter injected test signal, a robust vector transfer between PEs with arbitrary clock phases is achieved and the headache problem of the global synchronization is avoided.

Many distributed algorithms require knowledge of the causal relationships between events. Examples include optimistic recovery protocols, distributed debugging systems, and causal distributed shared memory. Determining causal relationships can be difficult, however, because there is no global clock and local clocks cannot be perfectly synchronized. Vector time is a useful abstraction for capturing the causal relationships between events and, unlike Lamport's logical clocks, allows identification of concurrent events. Some drawbacks of vector time include transmission and logging overhead, since the size of a vector clock is linear in the number of processes. This paper presents a technique to reduce these overheads for applications that dynamically create and destroy processes and log event information with attached vector timestamps. The reduction in logging overhead comes at the expense of a more complicated timestamp comparison protocol and more sophisticated data structures for maintaining vector time. Distributed process recovery mechanisms and debugging systems that require “on-the-fly” causality information can benefit directly from the proposed technique

This paper establishes the necessary and sufficient condition for a correct clock resetting such that the functionality of vector clocks can be preserved. A clock reset protocol is presented with its applicability and limitation discussed. Our result indicates that for some applications, the potential of clock overflow can be completely prevented by carefully choosing the condition for initiating the clock reset protocol.

A vector clock is a valuable tool for maintaining run time concurrency information in parallel programs. A novel method is presented for modifying vector clocks to make them suitable for programs with nested fork join parallelism (having a variable number of tasks). The resulting kind of clock is called a clock tree, due to its tree structure. The clock tree method compares favorably with other timestamping methods for variable parallelism: task identifier reuse and task recycling. The worst case space requirements of clock trees equals the best case for the latter two methods, and the average size of a clock tree is much smaller than the size of a vector with task recycling. Furthermore, the algorithm for maintaining clock trees does not require a shared data structure and thus avoids the serialization bottleneck that task recycling suffers from.

An integrated top-down design system is presented in this paper for synthesizing clock distribution networks for application to synchronous digital systems. The timing behavior of a synchronous digital circuit is obtained from the register transfer level description of the circuit, and used to determine a non-zero clock skew schedule which reduces the clock period as compared to zero skew-based approaches. Concurrently, the permissible range of clock skew for each local data path is calculated to determine the maximum allowed variation of the scheduled clock skew such that no synchronization failures occur. The choice of clock skew values considers several design objectives, such as minimizing the effects of process parameter variations, imposing a zero clock skew constraint among the input and output registers, and constraining the permissible range of each local data path to a minimum value. The clock skew schedule and the worst case variation of the primary process parameters are used to determine the hierarchical topology of the clock distribution network, defining the number of levels and branches of the clock tree and the delay associated with each branch. The delay of each branch of the clock tree is physically implemented with distributed buffers targeted in CMOS technology using a circuit model that integrates short-channel devices with the signal waveform shape and the characteristics of the clock tree interconnect. A bottom-up approach for calculating the worst case variation of the clock skew due to process parameter variations is integrated with the top-down synthesis system. Thus, the local clock skews and a clock distribution network are obtained which are more tolerant to process parameter variations. This methodology and related algorithms have been demonstrated on several MCNC/ISCAS-89 benchmark circuits. Increases in system-wide clock frequency of up to 43% as compared with zero clock skew implementations are shown. Furthermore, examples of clock distribution networks that exploit intentional localized clock skew are presented which are tolerant to process parameter variations with worst case clock skew variations of up to 30%.

This paper discusses an effective clock methodology for the design of high-performance microprocessors. Key attributes include the clustering and balancing of clock loads, multiple clock domains, a balanced clock router with variable width wires to minimize skew, hierarchical clock wiring, automated verification, an interface to the Cadence Design Framework II™ environment, and a complete network model of the clock distribution, including loads. This clock methodology enabled creation of the entire clock network, including verification, in less than three days with approximately 180 ps of skew.

In this paper, we develop and analyze a simple interval-based algorithm suitable for fault-tolerant external clock synchronization. Unlike usual internal synchronization approaches, our convergence function-based algorithm provides approximately synchronized clocks maintaining both precision and accuracy w.r.t. external time. This is accomplished by means of a time representation relying on intervals that capture external time, providing accuracy information encoded in interval lengths. The algorithm, which is generic w.r.t. the convergence function and relies on either instantaneous correction or continuous amortization for clock adjustment, is analyzed by utilizing a novel, interval-based framework for establishing worst-case precision and accuracy bounds subject to a fairly detailed system model. Apart from individual clock rate and transmission delay bounds, our system model incorporates non-standard features like clock granularity and broadcast latencies as well. Relying on a suitable notion of internal global time, our analysis unifies treatment of precision and accuracy, ending up in striking conceptual beauty and expressive power.