Propagation delay uncertainty in time-of-flight systems

This dissertation presents a study of how propagation delay uncertainty affects the performance of time-of-flight synchronized digital circuits. Time-of-flight synchronization is a new timing method suitable for technologies such as optoelectronics having highly controllable propagation delay. No bistable memory elements are required, and synchronization is accomplished by precise adjustments of interconnect lengths. Delay is distributed over connections so that, nominally, pulses arrive at a common destination simultaneously. Clock gating and pulse stretching are used to restore timing of pulses. Time multiplexing is used to increase computational throughput, whereby a major cycle is divided into a number of minor cycles, each representing an independent virtual machine. What limits the amount of multiplexing that is feasible is the controllability of delay. The principle focus of this research is methods for computing the minimum feasible minor cycle and the amount of stretch needed to prevent synchronization errors. Due to the unique circuit features, timing analysis differs significantly from analysis of conventional digital circuits. Models of delay uncertainty accounting for static and dynamic effects are discussed for discrete and integrated implementations. Methods for placing a minimal set of clock gates necessary for a functional circuit are presented. The minimum feasible major cycle is computed using nominal delays. A method for computing the arrival time and pulse width uncertainty at each node in the circuit is presented. The circuit graph is traversed and device uncertainty functions operating on worst-case input pulse parameters are applied at vertices. Using pulse timing parameters obtained from the traversal, timing constraints are generated. A constrained minimization problem to find the minimum feasible minor cycle is then presented and solved. Two variations on this problem are presented. Circuit structural issues that affect the accuracy of the results are also discussed. The timing analysis algorithms are implemented in a CAD tool called XHatch. Results of XHatch experiments showing the effect of delay uncertainty on the minimum feasible minor cycle for discrete and integrated implementations of circuits are presented. The last chapter presents a statistical model of delay uncertainty and a method for estimating the probability of a synchronization error.