On-Chip Clock Network Skew Measurement using Sub-Sampling

We present a technique for an all-digital on-chip delay measurement system to measure the skews in a clock distribution network. It uses the principle of sub-sampling. Measurements from a prototype fabricated in a 65 nm industrial process, indicate the ability to measure delays with a resolution of 0.5ps and a DNL of 1.2 ps.

An efficient reduction algorithm for computation of interconnect delay variability for statistical timing analysis in clock tree planning

In this paper, we propose a novel and efficient algorithm for modelling sub-65 nm clock interconnect-networks in the presence of process variation. We develop a method for delay analysis of interconnects considering the impact of Gaussian metal process variations. The resistance and capacitance of a distributed RC line are expressed as correlated Gaussian random variables which are then used to compute the standard deviation of delay Probability Distribution Function (PDF) at all nodes in the interconnect network. Main objective is to find delay PDF at a cheaper cost. Convergence of this approach is in probability distribution but not in mean of delay. We validate our approach against SPICE based Monte Carlo simulations while the current method entails significantly lower computational cost.

Compiler-Directed Frequency and Voltage Scaling for a Multiple Clock Domain

Multiple Clock Domain processors provide an attractive solution to the increasingly challenging problems of clock distribution and power dissipation. They allow their chips to be partitioned into different clock domains, and each domain’s frequency (voltage) to be independently configured. This flexibility adds new dimensions to the Dynamic Voltage and Frequency Scaling problem, while providing better scope for saving energy and meeting performance demands. In this paper, we propose a compiler directed approach for MCD-DVFS. We build a formal petri net based program performance model, parameterized by settings of microarchitectural components and resource configurations, and integrate it with our compiler passes for frequency selection.Our model estimates the performance impact of a frequency setting, unlike the existing best techniques which rely on weaker indicators of domain performance such as queue occupancies(used by online methods) and slack manifestation for a particular frequency setting (software based methods).We evaluate our method with subsets of SPECFP2000,Mediabench and Mibench benchmarks. Our mean energy savings is 60.39% (versus 33.91% of the best software technique)in a memory constrained system for cache miss dominated benchmarks, and we meet the performance demands.Our ED2 improves by 22.11% (versus 18.34%) for other benchmarks. For a CPU with restricted frequency settings, our energy consumption is within 4.69% of the optimal.

0.84 ps Resolution Clock Skew Measurement via Subsampling

An all-digital on-chip clock skew measurement system via subsampling is presented. The clock nodes are sub-sampled with a near-frequency asynchronous sampling clock to result in beat signals which are themselves skewed in the same proportion but on a larger time scale. The beat signals are then suitably masked to extract only the skews of the rising edges of the clock signals. We propose a histogram of the arithmetic difference of the beat signals which decouples the relationship of clock jitter to the minimum measurable skew, and allows skews arbitrarily close to zero to be measured with a precision limited largely by measurement time, unlike the conventional XOR based histogram approach. We also analytically show that the proposed approach leads to an unbiased estimate of skew. The measured results from a 65 nm delay measurement front-end indicate that for an input skew range of +/- 1 fan-out-of-4 (FO4) delay, +/- 3 sigma resolution of 0.84 ps can be obtained with an integral error of 0.65 ps. We also experimentally demonstrate that a frequency modulation on a sampling clock maintains precision, indicating the robustness of the technique to jitter. We also show how FM modulation helps in restoring precision in case of rationally related clocks.

A weighted average-based external clock synchronisation protocol for wireless sensor networks

Wireless Sensor Networks (WSNs) have many application scenarios where external clock synchronisation may be required because a WSN may consist of components which are not connected to each other. In this paper, we first propose a novel weighted average-based internal clock synchronisation (WICS) protocol, which synchronises all the clocks of a WSN with the clock of a reference node periodically. Based on this protocol, we then propose our weighted average-based external clock synchronisation (WECS) protocol. We have analysed the proposed protocols for maximum synchronisation error and shown that it is always upper bounded. Extensive simulation studies of the proposed protocols have been carried out using Castalia simulator. Simulation results validate our above theoretical claim and also show that the proposed protocols perform better in comparison to other protocols in terms of synchronisation accuracy. A prototype implementation of the WICS protocol using a few TelosB motes also validates the above conclusions.

Design and analysis of a peer-to-peer based distributed clock synchronisation protocol for wireless sensor networks

Clock synchronisation is an important requirement for various applications in wireless sensor networks (WSNs). Most of the existing clock synchronisation protocols for WSNs use some hierarchical structure that introduces an extra overhead due to the dynamic nature of WSNs. Besides, it is difficult to integrate these clock synchronisation protocols with sleep scheduling scheme, which is a major technique to conserve energy. In this paper, we propose a fully distributed peer-to-peer based clock synchronisation protocol, named Distributed Clock Synchronisation Protocol (DCSP), using a novel technique of pullback for complete sensor networks. The pullback technique ensures that synchronisation phases of any pair of clocks always overlap. We have derived an exact expression for a bound on maximum synchronisation error in the DCSP protocol, and simulation study verifies that it is indeed less than the computed upper bound. Experimental study using a few TelosB motes also verifies that the pullback occurs as predicted.

A weighted average based external clock synchronization protocol for wireless sensor networks

Clock synchronization is an extremely important requirement of wireless sensor networks(WSNs). There are many application scenarios such as weather monitoring and forecasting etc. where external clock synchronization may be required because WSN itself may consists of components which are not connected to each other. A usual approach for external clock synchronization in WSNs is to synchronize the clock of a reference node with an external source such as UTC, and the remaining nodes synchronize with the reference node using an internal clock synchronization protocol. In order to provide highly accurate time, both the offset and the drift rate of each clock with respect to reference node are estimated from time to time, and these are used for getting correct time from local clock reading. A problem with this approach is that it is difficult to estimate the offset of a clock with respect to the reference node when drift rate of clocks varies over a period of time. In this paper, we first propose a novel internal clock synchronization protocol based on weighted averaging technique, which synchronizes all the clocks of a WSN to a reference node periodically. We call this protocol weighted average based internal clock synchronization(WICS) protocol. Based on this protocol, we then propose our weighted average based external clock synchronization(WECS) protocol. We have analyzed the proposed protocols for maximum synchronization error and shown that it is always upper bounded. Extensive simulation studies of the proposed protocols have been carried out using Castalia simulator. Simulation results validate our theoretical claim that the maximum synchronization error is always upper bounded and also show that the proposed protocols perform better in comparison to other protocols in terms of synchronization accuracy. A prototype implementation of the proposed internal clock synchronization protocol using a few TelosB motes also validates our claim.

A model for the classification and survey of clock synchronization protocols in WSNs

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.

A Design for Performance Improvement of Clock Synchronization in WSNs using a TDMA-based MAC Protocol

Clock synchronization in a wireless sensor network (WSN) is quite essential as it provides a consistent and a coherent time frame for all the nodes across the network. Typically, clock synchronization is achieved by message passing using a contention-based scheme for media access, like carrier sense multiple access (CSMA). The nodes try to synchronize with each other, by sending synchronization request messages. If many nodes try to send messages simultaneously, contention-based schemes cannot efficiently avoid collisions. In such a situation, there are chances of collisions, and hence, message losses, which, in turn, affects the convergence of the synchronization algorithms. However, the number of collisions can be reduced with a frame based approach like time division multiple access (TDMA) for message passing. In this paper, we propose a design to utilize TDMA-based media access and control (MAC) protocol for the performance improvement of clock synchronization protocols. The basic idea is to use TDMA-based transmissions when the degree of synchronization improves among the sensor nodes during the execution of the clock synchronization algorithm. The design significantly reduces the collisions among the synchronization protocol messages. We have simulated the proposed protocol in Castalia network simulator. The simulation results show that the proposed protocol significantly reduces the time required for synchronization and also improves the accuracy of the synchronization algorithm.

Byzantine-resilient distributed computing systems

This paper is aimed at reviewing the notion of Byzantine-resilient distributed computing systems, the relevant protocols and their possible applications as reported in the literature. The three agreement problems, namely, the consensus problem, the interactive consistency problem, and the generals problem have been discussed. Various agreement protocols for the Byzantine generals problem have been summarized in terms of their performance and level of fault-tolerance. The three classes of Byzantine agreement protocols discussed are the deterministic, randomized, and approximate agreement protocols. Finally, application of the Byzantine agreement protocols to clock synchronization is highlighted.

Microprocessor-based event sequence recorder

An event sequence recorder is a specialized piece of equipment that accepts inputs from switches and contactors, and prints the sequence in which they operate. This paper describes an event sequence recorder based on an Intel 8085 microprocessor. It scans the inputs every millisecond and prints in a compact form the channel number, type of event (normal or abnormal) and time of occurrence. It also communicates these events over an RS232C link to a remote computer. A realtime calendar/clock is included. The system described has been designed for continuous operation in process plants, power stations etc. The system has been tested and found to be working satisfactorily.

Simple period timing device for laser Doppler signals

A period timing device suitable for processing laser Doppler anemometer signals has been described here. The important features of this instrument are: it is inexpensive, simple to operate, and easy to fabricate. When the concentration of scattering particles is low the Doppler signal is in the form of a burst and the Doppler frequency is measured by timing the zero crossings of the signal. But the presence of noise calls for the use of validation criterion, and a 5–8 cycles comparison has been used in this instrument. Validation criterion requires the differential count between the 5 and 8 cycles to be multiplied by predetermined numbers that prescribe the accuracy of measurement. By choosing these numbers to be binary numbers, much simplification in circuit design has been accomplished since this permits the use of shift registers for multiplication. Validation accuracies of 1.6%, 3.2%, 6.3%, and 12.5% are possible with this device. The design presented here is for a 16-bit processor and uses TTL components. By substituting Schottky barrier TTLs the clock frequency can be increased from about 10 to 30 MHz resulting in an extension in the range of the instrument. Review of Scientific Instruments is copyrighted by The American Institute of Physics.

Simple period timing device for laser Doppler signals

A period timing device suitable for processing laser Doppler anemometer signals has been described here. The important features of this instrument are: it is inexpensive, simple to operate, and easy to fabricate. When the concentration of scattering particles is low the Doppler signal is in the form of a burst and the Doppler frequency is measured by timing the zero crossings of the signal. But the presence of noise calls for the use of validation criterion, and a 5–8 cycles comparison has been used in this instrument. Validation criterion requires the differential count between the 5 and 8 cycles to be multiplied by predetermined numbers that prescribe the accuracy of measurement. By choosing these numbers to be binary numbers, much simplification in circuit design has been accomplished since this permits the use of shift registers for multiplication. Validation accuracies of 1.6%, 3.2%, 6.3%, and 12.5% are possible with this device. The design presented here is for a 16-bit processor and uses TTL components. By substituting Schottky barrier TTLs the clock frequency can be increased from about 10 to 30 MHz resulting in an extension in the range of the instrument. Review of Scientific Instruments is copyrighted by The American Institute of Physics.

MIPS: metal interactions in protein structures

MIPS (metal interactions in protein structures) is a database of metals in the three-dimensional acromolecular structures available in the Protein Data Bank. Bound metal ions in proteins have both catalytic and structural functions. The proposed database serves as an open resource for the analysis and visualization of all metals and their interactions with macromolecular (protein and nucleic acid) structures. MIPS can be searched via a user-friendly interface, and the interactions between metals and protein molecules, and the geometric parameters, can be viewed in both textual and graphical format using the freely available graphics plug-in Jmol. MIPS is updated regularly, by means of programmed scripts to find metal-containing proteins from newly released protein structures. The database is useful for studying the properties of coordination between metals and protein molecules. It also helps to improve understanding of the relationship between macromolecular structure and function. This database is intended to serve the scientific community working in the areas of chemical and structural biology, and is freely available to all users, around the clock, at http://dicsoft2.physics.iisc.ernet.in/mips/.

MLDB: macromolecule ligand database

MLDB (macromolecule ligand database) is a knowledge base containing ligands co-crystallized with the three-dimensional structures available in the Protein Data Bank. The proposed knowledge base serves as an open resource for the analysis and visualization of all ligands and their interactions with macromolecular structures. MLDB can be used to search ligands, and their interactions can be visualized both in text and graphical formats. MLDB will be updated at regular intervals (weekly) with automated Perl scripts. The knowledge base is intended to serve the scientific community working in the areas of molecular and structural biology. It is available free to users around the clock and can be accessed at http://dicsoft2.physics.iisc.ernet.in/mldb/.