A low signal to interference and noise ratio (SINR) wireless environment makes successful reception and accurate detection of packets a challenging task. We can combat a low SINR by using direct-sequence spread spectrum modulation with a sufficiently high processing gain, as well as by employing block codes for FEC on each packet. In this paper, we propose a packet detection and acquisition method for low SINR environments. The received waveform is processed using a non-linear filtering algorithm based on a maximum likelihood ratio calculation to detect the presence of transmitted packets. The algorithm uses the entire packet transmission for chip timing synchronization and code acquisition at the receiver. The performance of the algorithm is analyzed using simula- tions and real packet transmissions captured over the wireless medium. The algorithm is finally implemented on a FPGA which is a part of a wireless transceiver prototype. The experimental results are reported.

We describe an optical ring media access architecture, a media access (MAC) protocol, and a test bed implementation. The optical ring media access architecture is designed to facilitate high-speed broadband access for small business, residential, and mobile users. In our scheme, users can access a wide area network (WAN), such as the Internet, through a media access node (assumed to be a short distance away from the user). The transmission of data from the access node to the destination is done via an optical ring to a central office residing on the ring and from the central office via WAN to the destination, which may be hosted by a media access node on another optical ring. The MAC protocol is based on the earliest deadline first (EDF) scheduling to provide quality of service (QoS) for traffic flows on the ring. The test bed implementation consists of four media access nodes connected by an optical ring. Each node is implemented as a board which consists of an FPGA, an SRAM chip, optical interface modules, etc. Finally, we describe bandwidth and latency measurements showing differentiated performance for prioritized flows.

High-speed networks are expected to carry traffic classes with diverse quality of service (QoS) guarantees. For efficient utilization of resources, sophisticated scheduling protocols are needed; however, these must be implemented without sacrificing the maximum possible bandwidth. This paper presents the architecture and implementation of a self-timed real-time sorting network to be used in packet switches that support a diverse mix of traffic. The sorting network receives packets with appropriately assigned priorities and schedules the packets for departure in a highest-priority-first manner. The circuit implementation uses zero-overhead, self-timed, and self-precharging domino logic to minimize the circuit latency. An experimental sorting network chip has been designed using the techniques described in this paper to support 10 Gb/s links with ATM-size packets.

This tutorial surveys recent advances in asynchronous design methodologies. Whenever possible, actual design examples are used to present the methods. Three primary topics are discussed: (1) asynchronous controllers, (2) asynchronous datapaths, and (3) asynchronous systems. For asynchronous controllers, basic design styles and tools are presented. For asynchronous datapaths, basic issues in timed vs. self-timed, matched delay vs. completion sensing, and power vs. performance tradeoff are discussed. For asynchronous systems, recently fabricated system design examples in processors, coprocessors, and DSP's are described.

We describe a high performance clocking methodology for domino pipelines. Our technique maximizes the clock rate of the circular pipeline ("ring") while maintaining the ring cycle time to be the worst-case combinational logic delay around the ring. It is relatively immune to global clock skew, incurs no latch overhead, allows up to 50% time borrowing, and offers a robust way of preventing race-through problems, adjusted for the worst-case time borrowing.

Asynchronous systems are being viewed as an increasingly viable alternative to purely synchronous systems. This paper gives an overview of the current state of the art in practical asynchronous circuit and system design in four areas: controllers, datapaths, processors, and the design of asynchronous/synchronous interfaces. 1 Asynchronous Control Classical asynchronous controllers were typically implemented as Huffman machines [67]. These machines do not use clocked latches or flip-flops: the state is simply stored on feedback loops. Typically a fundamental mode assumption is required, to insure correct operation: once an input change occurs, no new inputs may arrive until the machine has stabilized. Much of the basic theory on asynchronous state machines was developed by Huffman, Unger, and Mc-Cluskey (see [67]). Hazards, or the potential for glitches, are an important consideration in any asynchronous design [67]. In synchronous systems, the global clock usually filters out the effect of glitches. In asynchronous systems, there is no global clock, so any glitch may be interpreted as a valid signal change, and cause a malfunction. A number of techniques to eliminate combinational hazards, as well as critical races and essential hazards, have been proposed [67, 22, 5]. While this early work laid the foundations of asynchronous controller synthesis, the design methods had major limitations: (i) lack of ability to handle highly-concurrent environments; (ii) poor performance; (iii) problems in hazard elimination (in some methods); and (iv) lack of CAD optimization algorithms and tools. Since the early and mid 1980’s, several controller synthesis methods were developed, to address these limitations. These methods fall into three general categories: (i) state machines; (ii) Petri-net and graph-based methods; and (iii) translation methods. ___________________________

We describe a scalable priority queue manager that implements deadline-ordered service disciplines in an output-buffered ATM switch, which can be used as a switching node in high-speed packet switched networks to provide quality of service (QoS) guarantees. The priority queue manager can handle a range of priority levels from 0 to (2/sup 16/-1), a buffer size of 64 k ATM cells, and 16 input links at 2.5 Gb/s. Two main components of the priority queue manager are: (1) a VLSI chip for searching the highest priority levels stored in the queue and for managing queues; (2) standard off-the-shelf SRAMs for cell buffering. In addition, we propose three architectures that combine the priority queue managers to scale up buffer size, number of input links, and bandwidth. We show that a combination of priority queue managers can yield a buffer size of 16 M ATM cells, 256 input links, and 5.8 Gb/s bandwidth.

We discuss a novel architecture for very high speed packet switching with priority-based conflict resolution. An input-queued switch with N/sup 2/ queues is used to prevent head-of-line blocking. Unlike previous designs which use multiple FIFO queues to provide several priority levels, we use hardware priority queues with 16-bit priority encoding. To reduce the hardware complexity, we introduce the concept of grouping fixed-size packets into "ensembles" that are stored by reference in the priority queues. This approach yields large buffer capacity while using relatively short queues.

Modern high-performance asynchronous circuits depend on timing constraints for correct operation, so timing analyzers are essential asynchronous design tools. In this paper we present a 13-valued abstract waveform algebra and a polynomial-time min-max timing simulation algorithm for use in efficient, approximate timing analysis of asynchronous circuits with bounded component delays. Unlike several previous approaches, our algorithm computes separate propagation delay bounds from each circuit input to each internal gate. This is useful for analyzing asynchronous circuits, where the relative transition times of the inputs may not be known a priori, unlike synchronous circuits. We also describe an efficient reconvergent fanout analysis technique that helps in increasing the accuracy of simulation. We have applied our algorithm to build an efficient timing analysis tool for extended burst-mode circuits (a class of timing-dependent asynchronous circuits) implemented in the 30 design style. Our tool analyzes gate-level 30 circuits assuming bounded component delays and determines safe timing constraints for correct operation. Although our results represent conservative approximations to the true timing requirements in the worst case, experiments indicate that our technique is efficient and fairly accurate in practice.

This paper describes a pseudo-polynomial time algorithm for timing analysis of a class of choice-free asynchronous systems, called tightly coupled systems, with both min- and max-type timing constraints and bounded component delays. The algorithm consists of two phases: (1) long-term behavior analysis, that computes bounds on the time separation of events after the system has run for a sufficiently long period of time, and (2) startup behavior analysis, that computes time separations between events during an initial startup period after the system is powered up. The results of the analysis are conservative in the worst case; nevertheless, they are found to be exact in our experiments. To demonstrate the practical utility of the approach, an asynchronous differential equation solver chip has been modeled and analyzed using the proposed algorithm. We report results of datapath timing verification, intercontroller protocol timing verification and performance analysis of the chip using the proposed technique.

This paper presents a technology mapper that optimizes the average performance of asynchronous burst-mode control circuits. More specifically, the mapper can be directed to minimize either the average latency or the average cycle time of the circuit. The input to the mapper is a burst-mode specification and its NAND-decomposed unmapped network. The mapper preprocesses the circuit's specification using stochastic techniques to determine the relative frequency of occurrence of each state transition. Then, it maps the NAND-decomposed network using a given library of gates. Of many possible mappings, the mapper selects a solution that minimizes the sum of the delays (latency or cycle time) of all state transitions, weighted by their relative frequencies, thereby optimizing for average performance. We present experimental results on a large set of benchmark circuits, which demonstrate that our mapped circuits have significantly lower average latency and cycle time than comparable circuits mapped with a leading conventional mapping technique which minimizes the worst case delay. Moreover, these performance improvements can be achieved with manageable run-times and significantly smaller area.

We introduce a new design style called extended burst-mode. The extended burst-mode design style covers a wide spectrum of sequential circuits ranging from delay-insensitive to synchronous. We can synthesize multiple-input change asynchronous finite state machines and many circuits that fall in the gray area (hard to classify as synchronous or asynchronous) which are difficult or impossible to synthesize automatically using existing methods. Our implementation of extended burst-mode machines uses standard CMOS logic, generates low-latency outputs, and guarantees freedom from hazards at the gate level. In Part I, we formally define the extended burst-mode specification, provide an overview of the synthesis methods, and describe the hazard-free synthesis requirements for two different next-state logic synthesis methods: two-level sums-of-products implementation and generalized C-elements implementation. We also present an extension to existing theories for hazard-free combinational synthesis to handle nonmonotonic input changes.

We introduce a new design style called extended burst-mode. The extended burst-mode design style covers a wide spectrum of sequential circuits ranging from delay-insensitive to synchronous. We can synthesize multiple-input change asynchronous finite state machines and many circuits that fall in the gray area (hard to classify as synchronous or asynchronous) which are difficult or impossible to synthesize automatically using existing methods. Our implementation of extended burst-mode machines uses standard CMOS logic, generates low-latency outputs, and guarantees freedom from hazards at the gate level. In Part II, we present a complete set of automated sequential synthesis algorithms: hazard-free state assignment, hazard-free state minimization, and critical-rare-free state encoding. Experimental data from a large set of examples are presented and compared to competing methods whenever possible.

This paper describes a novel communication scheme, which is guaranteed to be free of synchronization failures, amongst multiple synchronous and asynchronous modules operating independently. In this scheme, communication between every pair of modules is done through an asynchronous first-in first-out (FIFO) channel; communication between a module and the FIFO is done using a request/acknowledge handshaking. Synchronization of handshake signals to the local module clock is done in an unconventional way-the local clock built out of a ring oscillator is paused or stretched, if necessary, to ensure that the handshake signal satisfies setup and hold time constraints with respect to the local clock. In order to validate this scheme, we implemented a test chip in 0.5-/spl mu/m CMOS. This chip is designed as a ring, composed of two synchronous modules, an asynchronous module, and two asynchronous FIFOs. Each module functions as a receiver to one module and a sender to another module. Test results show that the chip functions reliably up to 456 MHz.

High speed networks are expected to carry traffic classes with diverse Quality of Service (QoS) guarantees. For efficient utilization of resources, sophisticated scheduling protocols are needed; however; these must be implemented without sacrificing the maximum possible bandwidth. This paper presents the architecture and implementation of a self-timed real-time sorting network to be used in packet switches that support a diverse mix of traffic. The sorting network receives packets with appropriately assigned priorities, and schedules the packets for departure in a highest-priority-first manner. The circuit implementation uses zero-overhead, self-timed, self-precharging domino logic and timed-roadblock techniques to minimize the circuit latency. Experimental chips being built using the techniques described in this paper support 10 Gb/s links with ATM size packets.

We examine the implications of a new hazard-free combinational logic synthesis method, which generates multiplexor-based networks from binary decision diagrams (BDD's)-representations of logic functions factored recursively with respect to input variables-on extended burst-mode asynchronous synthesis. First, this method guarantees that there exists a hazard-free BDD-based implementation for every legal extended burst-mode specification. Second, it reduces the constraints on state minimization and assignment, which reduces the number of additional state variables required in many cases. Third, in cases where conditional signals are sampled, it eliminates the need for state variable changes preceding output changes, which reduces overall input-to-output latency. Last, we describe a circuit that exemplifies how the BDD variable ordering affects the path delay.

This paper presents an architectural enhancement to reduce the power consumption of the full-search block-matching (FSBM) motion estimation. Our approach is based on eliminating unnecessary computation using conservative approximation. Augmenting the estimation technique to a conventional systolic-architecture-based VLSI motion estimation reduces the power consumption by a factor of 2, while still preserving the optimal solution and the throughput. A register-transfer level implementation as well as simulation results on benchmark video clips are presented.

This paper describes the design and verification of a high-performance asynchronous differential equation solver benchmark circuit. The design has low-control-overhead which allows its average-case speed (tested at 22/spl deg/C and 3.3 V) to be 48% faster than any comparable synchronous design (designed to operate at 100/spl deg/C and 3 V for the slow process corner). The techniques to reduce completion sensing overhead and hide control overhead at the circuit, architectural, and protocol levels are discussed. In addition, symbolic model checking techniques are described that were used to gain higher confidence in the correctness of the timed distributed control.

Recent practical advances in asynchronous circuit and system design have resulted in renewed interest by circuit designers. Asynchronous systems are being viewed as an increasingly viable alternative to globally synchronous system organization. This tutorial will present the current state of the art in asynchronous circuit and system design in three different areas. The first section details asynchronous control systems. The second describes a variety of approaches to asynchronous datapaths. The third section is on asynchronous and self-timed circuits applied to the design of general purpose processors.

This paper describes a novel communication scheme, which is guaranteed to be free of synchronization failures, amongst multiple synchronous modules operating independently. In this scheme, communication between every pair of modules is done through an asynchronous FIFO channel; communication between a module and the FIFO is done using a request/acknowledge handshaking. Synchronization of handshaking signals to the local module clock is done in an unconventional way-the local clock built out of a ring oscillator is paused or stretched, if necessary, to ensure that the handshaking signal satisfies setup and hold time constraints with respect to the local clock. We constructed a test bed consisting of two synchronous modules with pausible clocking control and an asynchronous FIFO on a MOSIS 1.2 /spl mu/m CMOS chip. The resulting system functions reliably up to the local clock frequency of 220 MHz (according to SPICE simulation)-the maximum clock rate is limited by the ring oscillator not the pausible clocking control. Preliminary test results indicate that the fabricated chips operate correctly as simulated.

This paper describes two techniques to quantify energy consumption of burst-mode asynchronous (clock-less) control circuits. The circuit specifications considered are extended burst-mode specifications, and the implementations are multi-level logic implementations whose outputs are guaranteed to be free of any voltage glitches (hazards). Both techniques use stochastic analysis to combine a small number of simulations in order to quantify average energy per external signal transition. The first technique uses N-valued simulation to derive mathematically tight upper and lower bounds of energy consumption. Using this technique we bound the effect of hazards under all possible operating conditions and environments for a given circuit. Additionally, to drive synthesis tools for low-power we propose a second technique that uses fixed-delay simulation to derive a realistic estimate of energy consumption within our derived upper and lower bounds. We demonstrate the feasibility of both these techniques on a variety of burst-mode control circuits used in an industrial-quality chip. Our preliminary results indicate that less than 5% of the power of typical multi-level burst-mode circuits can be attributed to hazards.

We describe the design of a high performance asynchronous SCSI (small computer systems interface) controller data path and the associated control circuits. The data path is an asynchronous pipeline and the control circuits for the data path are built out of extended burst-mode machines. This design is functionally compatible with a widely used commercial SCSI controller and was simulated correctly with respect to all of the applicable test vectors used for the commercial design. The technology used for this design is a 0.8 /spl mu/m CMOS standard cell. The performance is limited by the SCSI specification, not the design itself, and the area is competitive with the commercial design. This design improves the data transfer throughput by up to 2.5 times from previous work by incorporating a FIFO and a distributed control scheme based on extended burst-mode state machines.

We present a design style and synthesis algorithm that encompasses both asynchronous and synchronous state machines. Our proposed design style not only supports generalized "burst-mode" multiple-input change asynchronous designs, but also allows the automatic synthesis of any synchronous Moore machine using only basic gates (and not state-holding elements). Moreover, the synthesis method covers many circuit styles in the range between burst-mode and fully synchronous. We can easily specify and synthesize sequential circuits which change state on both rising and falling clock edges, have multiple-phase clocks, etc., and mixed synchronous/asynchronous designs, subject only to setup and hold-time constraints. To demonstrate the effectiveness of the design style and the synthesis tool, we present a modified version of a previously published large practical controller design - the SCSI data transfer controller redesigned to improve performance and to eliminate preprocessing circuit for converting "level-sensitive" signals to "edge-sensitive" signals, often a cumbersome manual design process, by interfacing directly with "level-sensitive" signals.

An automatic synthesis tool (3D) for designing asynchronous controllers from burst-mode specifications, a class of specifications allowing multiple input change fundamental mode operation, is described. An algorithm for constructing a three-dimensional next-state table, a heuristic for encoding states, and a procedure for generating necessary constraints for exact logic minimization are presented. The effectiveness of the 3D implementation and the synthesis procedure on numerous designs including a large realistic example (asynchronous data transfer protocol of the SCSI bus controller) is demonstrated. The latency (input to output delay) and the cycle time (time required for the circuit to stabilize after the excitation) for all benchmark designs using a 0.8- mu m CMOS standard cell library are estimated.>

The authors evaluate their proposed asynchronous state-machine synthesis method, which uses locally synthesized clocks, on two realistic examples: a DRAM controller and a small computer systems interface controller. These circuits are designed to satisfy existing interface specifications, and are substantially larger than interfaces that have been created by competing methods, such as signal transition graph synthesis. The performance of the resulting implementations is at least as good as that of comparable synchronous implementations.>

A synthesis procedure for designing asynchronous controllers from burst-mode specifications, a class of specifications allowing multiple-input-change fundamental mode operation, is described. This implementation of burst-mode state machines uses standard combinational logic, generates low-latency outputs and guarantees freedom from hazards at the gate level. It requires no locally synthesized clock and no storage elements. In addition, primary outputs as well as additional state variables are used as feedback variables. The state assignment technique is based on the construction of a three-dimensional next-state table.>