Tobias Bjerregaard

Jens Sparsø

A Router Architecture for Connection-Oriented Service Guarantees in the MANGO Clockless Network-on-Chip

On-chip networks for future system-on-chip designs need simple, high performance implementations. In order to promote system-level integrity, guaranteed services (GS) need to be provided. We propose a network-on-chip (NoC) router architecture to support this, and demonstrate with a CMOS standard cell design. Our implementation is based on clockless circuit techniques, and thus inherently supports a modular, GALS-oriented design flow. Our router exploits virtual channels to provide connection-oriented GS, as well as connection-less best-effort (BE) routing. The architecture is highly flexible, in that support for different types of BE routing and GS arbitration can be easily plugged into the router.

Introduction

Due to the effects of scaling micro-chip technologies, it has become unavoidably necessary to differentiate between local and global on-chip communication [START_REF] Sylvester | A global wiring paradigm for deep submicron design[END_REF]. The concept of communication-centric design derives from the fact that global communication is becomming more and more costly, in relation to processing power. Physical issues of deep submicron technologies as well as design complexity issues make current, poorly scalable solutions for global on-chip communication, such as busses, unsuited for future large scale system-on-chip (SoC) designs. There is a general consensus that shared, segmented interconnection networks, so called networks-on-chip (NoC), constitute a viable solution space to the problems faced today [START_REF] Benini | Networks on chips: A new SoC paradigm[END_REF][7] [START_REF] Jantsch | Networks on Chip[END_REF]. NoC facilitates a truely modular and scalable design approach in which IP reuse is an integral part. This is called upon in order to make efficient use of the exploding amount of resources available to chip designers, and so within the constraints of ever shortening design cycles.

Chip-wide synchronous operation is becoming prohibitively difficult to achieve in large, high performance chips [START_REF]International technology roadmap for semiconductors (ITRS) 2001[END_REF]. Possible solutions are in the direction of the globally asynchronous locally synchronous (GALS) concept [START_REF] Muttersbach | Globally-Asynchronous Locally-Synchronous Architectures to Simplify the Design of On-CHIP Systems[END_REF], by which a chip consists of synchronous islands which communicate asynchronously. Since a NoC spans the entire chip, it seems natural not to attempt a globally synchronous implementation but instead use a GALS approach or even a fully asynchronous, i.e. clockless, realization. This is illustrated in Figure 1. The very nature of a clockless NoC also makes the integration of cores with different timing characteristics an integral part of the design flow, promoting the concept of modularity. Clockless circuits have a number of advantages over clocked ones. Since they make use of self-timed, data-driven control they operate at the maximum speed possible, and they have zero dynamic power consumption when idle [START_REF] Sparsø | Principles of Asynchronous Circuit Design -a Systems Perspective[END_REF]. These advantages make them ideal for implementing NoC [START_REF] Nielsen | Analysis of low-power SoC interconnection networks[END_REF].

In this paper we present a worm-hole NoC router to be used in MANGO (Message-passing Asynchronous Network-on-Chip providing Guaranteed services through OCP interfaces) the NoC being developed at DTU. Our implementation is based on clockless circuit techniques. To our knowledge, MANGO is the first clockless NoC to provide connection-oriented guaranteed services (GS) as well as connection-less best-effort (BE) routing. It has features, area and performance comparable to a similar class of clocked routers. Additional benefits are an inherent support for GALS systems and zero dynamic idle power. The novelty lies in the concepts of establishing the GS paths and the application of methods we have developed in [START_REF] Bjerregaard | Virtual channel designs for guaranteeing bandwidth in asynchronous network-on-chip[END_REF] to implement non-blocking behaviour amongst several independent streams in the shared part of the link/router. We demonstrate with a 0.12 µm CMOS standard cell implementation.

The paper focuses more on the router architecture and less on circuit realizations. In Section 2 we provide argumentation for the implementation of GS in NoC, and in Section 3 we provide an overview of MANGO. In Sections 4 and 5 we explain the details of the router architecture, and explain how it is possible to provide GS via connections. Finally, in Section 6 we describe our implementation and give a conclusion in Section 7.

Background

When designing NoCs, much research done in the area of multicomputer networks can be readily build upon. The trade-offs differ however, and while pincount and global wiring have been the main limiting factors in multicomputer networks, NoC designers face constraints on area and power. Also latency requirements are more stringent in tightly coupled single-chip systems. As a result, NoC demands simple solutions to ensure high speed and low area.

Traditionally multicomputer networks support besteffort (BE) routing. Much NoC research builds on this by improving on BE routing efficiency under the constraints of single-chip system design [START_REF] Peh | A delay model for router microarchitectures[END_REF] [START_REF] Mullins | Low-latency virtualchannel routers for on-chip networks[END_REF]. In particular the use of virtual channels (VCs) -logically independent channels sharing a physical link -is employed. We propose to use the VC routing resources somewhat differently, i.e. for establishing GS connections. While an improvement of BE routing simply makes better use of existing wires, connection-oriented GS routing adds explicit new features: packets travel along virtual circuits, avoiding the mutual influence that BE packets routed on the same logical network may experience. From an application-level perspective, the predictability that GS incurs promotes system integrity, and simplifies functional verification since there is less call for taking into account the complex dynamics of a shared communication structure. At the circuit level, the circuits needed to implement GS also turn out to be simpler than those needed for BE, since less arbitration is called for during routing control.

Other NoCs which implement GS are AETHEREAL [START_REF] Dielissen | Concepts and implementation of the phillips network-onchip[END_REF] and NOSTRUM [START_REF] Millberg | Guaranteed bandwidth using looped containers in temporally disjoint networks within the Nostrum network on chip[END_REF]. Both employ variants of time division multiplexing (TDM) for allocating bandwidth. TDM is not possible in a clockless NoC which has no notion of time, thus other approaches must be taken. In [START_REF] Felicijan | An asynchronous on-chip network router with quality-of-service (QoS) support[END_REF], a clockless NoC which provides differentiated services by prioritizing VCs is presented. Though this approach delivers improved latency for certain connections, no hard guarantees are provided. In [START_REF] Bjerregaard | Virtual channel designs for guaranteeing bandwidth in asynchronous network-on-chip[END_REF] and [START_REF] Bjerregaard | A scheduling discipline for latency and bandwidth guarantees in asynchronous networkon-chip[END_REF] we have explored the use of VCs in clockless NoC for providing hard per connection bandwidth and latency guarantees respectively. In this paper we describe a supporting router architecture in which the proposed access schemes can be applied, providing end-to-end GS in a segmented network structure.

The MANGO Router

As shown in Figure 1, a MANGO NoC consists of network adapters (NA), routers and links. Each IP core is connected to the network through an NA, providing high level communication services, i.e. OCP transactions [START_REF][END_REF], on the basis of primitive services implemented by the network. Each NA, which also performs the synchronization between the clocked IP core and the clockless network, is connected to a router. The routers are connected by links in a gridtype structure, either homogeneous or heterogeneous. To keep speed up, long links can be implemented as pipelines.

Figure 2 shows a conceptual picture of the MANGO router. The router implements a number of uni-directional ports. Two of these are local ports which connect to the NA. The local ports consist of a number of physical interfaces. The remaining ports are network ports which, via pointto-point links, connect the router to neighboring routers. Each of these ports implement a number of independently Internally, the router consists of a BE router, a GS router, output buffers, and link arbiters. The BE and the GS router are separately implemented. This is done in order to make the router modular. A similar approach is seen in the AETHEREAL router [START_REF] Rijpkema | Trade offs in the design of a router with both guaranteed and best-effort services for networks on chip[END_REF]. The BE router dynamically source-routes connection-less data packets, according to the routing path defined in the packet header. A subset of the VCs are allocated for BE routing. The GS router uses the remaining VCs to route header-less data streams on statically programmable connections. In order to make hard service guarantees, GS connections must be logically independent of other network traffic. In MANGO, a connection implements a logical point-to-point circuit between two different local ports in the network, by reserving a sequence of independently buffered VCs. The GS router provides non-blocking switching between the input ports and the output buffers, therefore GS can be realized purely on the basis of link access arbitration. This will become clear in the following sections. The GS connections are set up by programming these into the GS router via the BE router.

The GS Router

Overview

Figure 3 shows a generic output buffered VC router with P input and output ports; a P × P switch is followed by a split module, which splits the incoming traffic to individual VC buffers at the output ports. Since several input ports may attempt to access the same output port simultaneously, congestion may occur. This makes the architecture unsuitable for providing service guarantees.

Figure 4 illustrates our connection-oriented GS router architecture. Again P is the number of ports on each routing node, while V is the number of VCs on each port. As touched upon in Section 3, a connection is a reserved se- quence of VCs through the network. In the router, incomming flits (flowcontrol units) are guided through the switching module (Section 4.2) -by way of steering bits which are appended to the flits in the previous router -to the VC buffer that has been reserved for the given connection.

To prevent flits of different VCs from stalling and blocking each other on the links, VC control must be employed. This ensures that flits will only be transmitted on a link, if there is free buffer space in the target VC buffer. The VC control module (Section 4.3) establishes a VC control channel from the VC buffers back to the VC buffers in the previous router; a step back on a given connection. For each connection, a router thus stores the steering bits needed to guide flits to the VC buffer reserved for the connection in the next router, as well as control channel bits used to establish a VC control channel back to the VC buffer in the previous router. This information is programmed into the router using BE packets (via the programming interface, Figure 2). As seen, the setup information for each hop on a connection is stored in two places: one for the flit forward path, and one for the VC control reverse path. This overhead was accepted because it facilitates some very simple circuits.

The switching module is non-blocking. This means that the latency from the time that a flit is granted access to a link, until it arrives at the designated VC buffer in the following router, is constant. In order to provide hard GS for a connection there is thus only call for link access arbitration. The link arbiter (Section 4.4) is the key element in providing GS. It arbitrates amongst the VCs contending for access to the link, implementing the type of GS that is provided.

The Switching Module

The switching module makes it possible for all input ports to route flits to any combination of VC buffers. It is made entirely without any form of arbitration necessary, making its performance highly predictable and simplifying its design, saving both area and routing latency. Since a VC buffer is part of only one connection, no congestion will occur as only one input will attempt to route to one VC buffer at any given time. Figure 5 shows an input/output port pair in a 5 × 5 port router with eight VCs on each port. This configuration will form the basis for the implementation being used as an example of the architecture. The diagram indicates how the remaining ports are connected. An input port needs only connect to four output ports as it is not useful to route flits back in the direction they came from. The diagram also indicates how a total of five steering bits are used. The first three bits are used by a split module, which directs the flit to one of two 4 × 4 switches at each output port. At each switch two more steering bits are used to direct the flit to one of four VC buffers. At each stage, the steering bits used are stripped, as they are no longer needed.

The switching module, which consitutes a considerable part of the total router area, scales linearly with the number of VCs, and thus with the number of connections supported.

The VC Control Module

In this work we employ share-based VC control, which we have described in [START_REF] Bjerregaard | Virtual channel designs for guaranteeing bandwidth in asynchronous network-on-chip[END_REF]. The scheme, illustrated in Figure 6, uses a single wire per VC to implement non-blocking access to a shared media, e.g. a link. When admitting a flit to the media the sharebox locks, not allowing further flits to pass. The flit passes across the media, to the unsharebox at the far side. The unsharebox implements a latch, into which the flit is accepted. When the flit in turn leaves the unsharebox, the unlock control wire toggles. This unlocks the sharebox, admitting another flit to the media. As long as the media is deadlock free, no flit will stall within it.

In the MANGO router, the link and the switching module constitute the shared media. Even if the link cycle for each flit transmitted on a VC is long, the full link bandwidth is exploited by the unlock handshake of different VCs overlapping. A single VC cannot utilize the full link bandwidth. However with an appropriate link access scheme, our goal to provide well defined worst case guarantees, can be met.

The cycle time of the VC link is sensitive to the forward latency of the flits. In this regard, clockless circuits are advantageous, since they make possible a very short forward latency per pipeline stage. An advantage of the share-based VC control scheme is that it is much cheaper, both area and power wise, than the commonly used credit-based VC control scheme. As shown in [START_REF] Bjerregaard | Virtual channel designs for guaranteeing bandwidth in asynchronous network-on-chip[END_REF], the two schemes can be used together, controlling access to the same link. This is useful when the same link is used for both GS and BE routing. During BE routing it is clearly an advantage using creditbased VC control to improve the average case performance.

As indicated in Figure 4, each input port of the router implements an output unlock wire for each VC, likewise each output port implements an input unlock wire per VC. Under the share-based VC control scheme, the VC control module establishes control channels between arbitrary VC buffers and the inputs, simply by circuit switching the unlock wires, originating in the VC buffers, unto the VC control outputs at the input ports. Thus the VC control module implements a non-blocking (P * V ) × (P * V ) switch. The control channel bits stored in the router map the VC buffers to the appropriate input VC wires, according to the connection path. In our 5 × 5, 8 VC router we simply use 5 * 8 instantiations of a (5 -1) * 8-input multiplexer. For larger number of VCs, it might prove worthwhile to implement a more complex switch structure, e.g. a Clos network, which scales better. The mapping between input and output VCs can be considered static during connection usage.

Link Access

The MANGO router implements output buffers. Since a connection is a reserved sequence of VCs, the target VC buffer of a flit entering the router is deterministic. There is no need for arbitrating amongst VCs on different output ports. Placing the VC buffers at the output simplifies the link access arbitration scheme. Thus simple, fast and low area circuits can be used to implement access schemes. Since the path across the link, through the switching module, to the target VC buffer is fully deterministic and congestion free, by way of the non-blocking switching module described in Section 4.2, the link access is the only critical point on a connection, with regard to congestion. tees can be made for link access, guarantees can be made for the entire connection. Thus link access arbitration is what facilitates GS in MANGO.

The link arbiter shown in Figure 2, 4, 5 and 8 implement the arbitration scheme. According to the arbitration amongst contending VCs, the flits are merged unto the shared link, which connects to the neighboring router. The steering bits which indicate the destination of the flit are appended before the flit is transmitted. In the router implementation presented herein, as a demonstration of the general architecture, we have implemented a fair-share access scheme [START_REF] Bjerregaard | Virtual channel designs for guaranteeing bandwidth in asynchronous network-on-chip[END_REF], by which each of 8 VCs are guaranteed a minimum of one 8th of the total link bandwidth. To keep the area down, our output buffers are a single flit deep plus one flit in the unsharebox. This is enough to ensure the fair-share scheme to function over a sequence of links, providing a hard lower bound on the throughput of a connection. If a VC does not use its allocated bandwidth, the link is automatically used by another contending VC.

It is seen how the GS routing functionality is decoupled from the switching functionality in the router. This makes it an easy and modular task to instantiate new GS schemes.

The BE Router

The BE router, shown in Figure 7, implements a simple source routing scheme. The first flit of a packet is the header flit. The two MSBs of the header indicate one of four output ports. Choosing a direction back to where it came from, the packet is routed to the local port. The header is then rotated two bits, positioning the header bits for the next hop. With 32-bit flits, a packet can make a total of 15 hops. The packets are variable length; a control bit is used to indicate the last flit. The outputs arbitrate fairly between input ports contending for access. Once an input port has gained access, it will retain this until the last flit has been routed, thus keeping packet coherency. The interface used to program GS connections into the GS router, is implemented as an extention on port 0, the local port. Figure 8 shows a com- plete picture of the router, indicating how the BE router is integrated into the GS router architecture. To avoid deadlocks XY-routing is employed.

When a flit enters the BE router, three steering bits have been stripped, and a total of 34 bits remain (see Figure 5), 32 of which are flit data. Of the other two, one is the control bit used to indicate the last flit. The remaining bit can be used to indicate one of two BE VCs. This is not used in the present implementation, but can be used to extend the BE router to provide more complex deadlock free routing, adaptive VC allocation, etc. The VC control of the BE channels is handled separately from the VC control module and can be implemented using a credit-based scheme [START_REF] Bjerregaard | Virtual channel designs for guaranteeing bandwidth in asynchronous network-on-chip[END_REF].

The focus of this paper is means of providing GS by way of the non-blocking GS router. The BE router has been included for the sake of completeness and holds lots of potential for improvement. First of all it should implement credit-based VC control, in order to facilitate improved average case performance. The modular architecture of the MANGO router makes it easy to plug in a new BE router.

Implementation and Results

We have implemented a 32-bit MANGO router using 0.12 µm CMOS standard cells. The router is designed with 4-phase bundled data clockless control circuits. It is a relatively small entity, thus internal timing is quite predictable. The links between neighboring routers are much longer, and thus more sensitive to timing variations. In order to make assembling a NoC-based SoC a modular and timing safe exercise, and in order to save power, we advocate delay insensitive signaling between routers, e.g. 1-of-4 signaling [START_REF] Bainbridge | Delay insensitive system-onchip interconnect using 1-of-4 data encoding[END_REF]. This will be realized in future MANGO versions.

The router has local input and output ports providing 5 interfaces each (4 for GS and 1 for BE) and 4 input and 4 output network ports (each implementing 8 VCs). The router simultaneously supports connection-less BE routing plus a total of 32 independently buffered GS connections. Each VC provides one 8th of the bandwidth on a link. The performance in netlist simulations using worst-case timing parameters (1.08 V/125 C) was 515 MHz per port (795 MHz under typical timing conditions). The pre-layout area was 0.188 mm 2 . The area usage is detailed in Table 1. The switching module and the VC buffers together account for more than half of the total area. Much area could be saved by using custom-designed buffers. As a quick comparison, a 0.13 µm instantiation of the globally synchronous AETHEREAL NoC, which also provides per connection bandwidth guarantees, had a port speed of 500 MHz and a laidout area of 0.175 mm 2 [8], using custom hardware FIFOs. The AETHEREAL router supports up to 256 connections. These are however not independently buffered -a key feature of the MANGO router connections. Thus end-to-end flowcontrol is needed, e.g. using credits. In the MANGO architecture end-to-end flowcontrol is inherent. Also, in order to save area, routing infomation is not stored locally in AETHEREAL. Connections thus need to support the routing overhead of a packet header. This is unwarranted in the architecture presented herein.

Conclusion

In this paper, we have presented MANGO (Messagepassing Asynchronous Network-on-Chip providing Guaranteed services through OCP interfaces), the NoC being developed at DTU. The MANGO router is implemented using clockless circuit techniques and thus inherently supports a modular, GALS oriented design flow. It exploits virtual channels to provide connection-oriented service guarantees (GS), as well as connection-less best-effort routing. We view the predictability of GS as a way to promote systemlevel integrity. A 32-bit 5×5 MANGO router using 0.12 µm CMOS standard cells was implemented, which supports 32 independently buffered connections, has a worst-case port speed of 515 MHz and a pre-layout area of 0.188 mm 2 .

Figure 1 .

 1 Figure 1. A shared clockless network connecting independently clocked IP cores facilitates modularity in large scale SoC designs.

Figure 2 .

 2 Figure 2. The MANGO router conceptually.

Figure 3 .

 3 Figure 3. Generic output buffered virtual channel router architecture.

Figure 4 .

 4 Figure 4. The MANGO GS router implements non-blocking input to output switching.

Figure 5 .

 5 Figure 5. Input/output port pair of the switching fabric of a 5x5 GS router with 8 VCs/port.

Figure 6 .

 6 Figure 6. Share-based VC control.

Figure 7 .

 7 Figure 7. The BE router.

Figure 8 .

 8 Figure 8. The BE router is integrated into the GS router, using a subset of the VCs.

Table 1 . Area usage in the MANGO router.

 1

	Module	Area
	Connection table	0.005 mm 2
	Switching module 0.065 mm 2
	VC buffers	0.047 mm 2
	Link access	0.022 mm 2
	VC control	0.016 mm 2
	BE router	0.033 mm 2
	Total	0.188 mm 2

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)


Sobeeh Almukhaizim

Yiorgos Makris

Concurrent Error Detection in Asynchronous Burst-Mode Controllers

We discuss the problem of Concurrent Error Detection (CED) in a popular class of asynchronous controllers, namely Burst-Mode machines. We first outline the particularities of these clock-less circuits, including the use of redundancy to ensure hazard-free operation, and we explain how they limit the applicability and effectiveness of traditional CED methods, such as duplication. We then demonstrate how duplication can be enhanced to resolve these limitations through additional hardware for comparison synchronization and detection of error-induced hazards, which jeopardize the interaction of the circuit with its environment. Finally, we propose a Transition-Triggered CED method which employs a transition prediction function to eliminate the need for hazard detection circuitry and hazard-free implementation of the duplicate. As indicated by experimental results, the proposed method reduces significantly the cost of CED, with an average of 22% in hardware savings.

Introduction

Asynchronous circuits promise a wide range of benefits, including elimination of clock distribution networks and clock skew problems, improved performance, reduced power consumption, and modularity. Nevertheless, adoption of a fully asynchronous design style for general purpose circuits has been rather limited, mainly because of the lack of supporting CAD tools and methodologies. Indeed, asynchronous circuits present their own set of challenges, making the porting of design and test methods from the synchronous domain neither straightforward nor always possible. In certain control-dominated applications, however, the use of asynchronous circuits has resulted in irrefutable advantages. For example, an asynchronous implementation of an instruction decoder exhibits a performance that is at least three times better than the performance of a highly tuned synchronous version [START_REF] Chou | Average-case optimized technology mapping of one-hot domino circuits[END_REF]. As a result, asynchronous controllers have attracted a lot of attention and several styles have been proposed for their design [START_REF] Shi | An effecient algorithm for constrained encoding and its applications[END_REF][START_REF] Yun | Automatic synthesis of extended burst-mode circuits[END_REF][START_REF] Lin | Synthesis of hazard-free multi-level logic under multiple-input changes from binary decision diagrams[END_REF]. Among them, Burst-Mode machines constitute one of the most popular classes.

In this paper, we address the problem of Concurrent Error Detection (CED) in asynchronous Burst-Mode machines. CED methods are typically employed to monitor the behavior of a circuit and detect any deviation from the correct func- * The author is supported through a scholarship from Kuwait University. tionality due to transient errors such as Single Event Upsets (SEU). While a wide variety of CED methods have been developed for synchronous controllers, their asynchronous counterparts are intrinsically different, limiting the effectiveness of these methods. To demonstrate this problem, we discuss the applicability of duplication, the most common synchronous CED method, to asynchronous Burst-Mode controllers. We show that direct use of duplication is jeopardized by two inherent properties of these circuits:

• Lack of a global clock: Clock-less operation allows a circuit and its duplicate to produce results autonomously and at their own pace. As a result, even in error-free operation, the outputs of these circuits are not always equal. Therefore, in order to avoid false alarms, a comparison synchronization method is required.

• Existence of redundant logic: Redundancy in the implementation of the circuit is necessary to ensure hazard-free operation, as required by the communication protocol between a Burst-Mode machine and its environment. As a result of redundancy, some errors cause only hazards but no functional discrepancy, so they cannot be detected by comparison. Therefore, in order to monitor the correct interaction of the circuit and its environment, a hazard-detection method is also required.

In short, remedial action in the form of additional hardware needs to be taken. To address the first issue, we propose a comparison synchronization method which utilizes control information inherent to the operation of asynchronous Burst-Mode controllers. To address the second issue, we propose the addition of hazard detection circuitry to the output and state bits of the original circuit. Thus, duplication-based CED is enhanced to guarantee detection of all functional errors and hazards in asynchronous Burst-Mode machines.

We then propose a Transition-Triggered CED method that reduces the overhead incurred by the enhanced duplication described above. More specifically, our method uses a transition prediction function which is derived from the functionality of the asynchronous Burst-Mode machine. In conjunction with the comparison synchronizer, this function eliminates the need for a hazard-free duplicate and is used as a less expensive method to perform hazard detection.

The few asynchronous CED methods that exist in the literature assume the existence of explicit completion signals in order to synchronize the comparison [START_REF] Verdel | Duplication-based concurrent error detection in asynchronous circuits: shortcomings and remedies[END_REF][START_REF] Piestrak | Towards totally self-checking delay-insensitive systems[END_REF][START_REF] Rennels | Concurrent error detection in self-timed VLSI[END_REF]. In contrast, the proposed method utilizes the predefined behavior of Burst-Mode controllers for the synchronization. Moreover, errors in redundant logic that cause only hazards but no functional discrepancy were not considered in previous methods. The remainder of the paper is organized as follows. In Section 2, we briefly introduce the class of asynchronous Burst-Mode controllers. In Section 3, we discuss the shortcomings of duplication-based CED when applied to these circuits and we demonstrate the required remedial action. In Section 4, we describe the Transition-Triggered CED method that we have developed for reducing the cost of duplication in asynchronous Burst-Mode machines. Finally, in Section 5, we provide experimental results quantifying the hardware savings achieved by the proposed method.

Asynchronous Burst-Mode Machines

In this section, we introduce briefly the fundamentals of asynchronous Burst-Mode machines. We then outline the synthesis process for realizing an asynchronous Burst-Mode implementation from a given Finite State Machine (FSM) description [START_REF] Fuhrer | Sequential Optimization of Asynchronous and Synchronous Finite-State Machines: Algorithms and Tools[END_REF] and we give an example.

Fundamentals

Burst-Mode machines constitute a class of Huffman circuits [START_REF] Huffman | The Synthesis of Sequential Switching Networks[END_REF], which is widely used for designing and implementing asynchronous controllers [START_REF] Fuhrer | Sequential Optimization of Asynchronous and Synchronous Finite-State Machines: Algorithms and Tools[END_REF][START_REF] Nowick | Automatic Synthesis of Burst-Mode Asynchronous Controllers[END_REF][START_REF] Nowick | Exact two-level minimization of hazard-free logic with multiple-input changes[END_REF][START_REF] Fuhrer | Optimista: State minimization of asynchronous FSMs for optimum logic[END_REF]. As shown in Fig. 1, Huffman circuits consist of a set of combinational functions, computing the next state and output of the circuit, and a set of feedback lines, storing the state of the circuit. No clock and no state registers are used in these circuits, however, delay elements are often added to eliminate essential hazards 1 [START_REF] Unger | Asynchronous Sequential Switching Circuits[END_REF]. Given the absence of a global clock, communication protocols are needed to ensure the correct interaction of an asynchronous circuit and its environment. These protocols define the properties of the stimuli that the environment is allowed to provide to the circuit, as well as the properties of the responses that the circuit will generate. Based on these protocols, several classes of circuits are distinguished.

The key aspect of the protocol used in Burst-Mode machines, as indicated by their name, is that the interaction of 1 Essential hazards arise when a state change completes before the input change is fully processed. To prevent this early state change from propagating through the combinational logic, delay may be added to the feedback. the circuit and its environment happens in Bursts. An input burst is defined as a set of bit changes in one or more inputs of the circuit, which are allowed to occur in any order and without any constraint in their relative time of arrival. Once an input burst is complete, and only then, the circuit responds through a hazard-free state and output change to the environment. We emphasize the protocol requirement for hazard-free state and output changes. Since no clock is used, synchronization between the circuit and its environment is based on the fact that any change in the state or output of the circuit signifies completion of an evaluation cycle. Therefore, all hazards should be eliminated to ensure correct circuit functionality and interaction with its environment.

In order to implement a circuit that complies to the aforementioned communication protocol, two features are added during the synthesis process. First, in order to make the functionality of the circuit critical-race2 free, dichotomies are added to constrain the binary state encoding of the circuit [START_REF] Micheli | Optimal state assignment for finite state machine[END_REF]. Consequently, the resulting state codes ensure that a transition between two states never reaches a transient state with a different destination state for the current input. Second, to make the next state and output functions hazard-free, redundant implicants are added to their implementation [START_REF] Mccluskey | Minimization of boolean functions[END_REF].

The popularity of Burst-Mode machines owes itself in part to the extensive research efforts that have been invested in methods and tools for automating their design [START_REF] Fuhrer | Sequential Optimization of Asynchronous and Synchronous Finite-State Machines: Algorithms and Tools[END_REF][START_REF] Nowick | Automatic Synthesis of Burst-Mode Asynchronous Controllers[END_REF][START_REF] Nowick | Exact two-level minimization of hazard-free logic with multiple-input changes[END_REF][START_REF] Fuhrer | Optimista: State minimization of asynchronous FSMs for optimum logic[END_REF]. For the purpose of this work, we used a comprehensive asynchronous Burst-Mode logic synthesis package called MIN-IMALIST [START_REF] Fuhrer | Sequential Optimization of Asynchronous and Synchronous Finite-State Machines: Algorithms and Tools[END_REF]. The above constraints, along with several optimization algorithms are incorporated in MINIMALIST, yielding a minimal hazard-free logic implementation.

Example

An asynchronous Burst-Mode machine is described using a state transition table such as the one shown in Fig. 2. The rows in the table correspond to the current symbolic state, the columns correspond to the inputs and the entry indicates the next state and the outputs. For example, if the circuit is in state S 0 , an input-burst of 1010 will cause a transition to state S 2 and will generate an output of 00. Let us now assume that the next input burst is 1001, i.e. input c is lowered and input d is raised, and that c is lowered first and then d is raised, i.e. 1001 → 1000 → 1001. The circuit responds only after the input burst is complete, so between the time that c is lowered and the time that d is raised, the next state and output function do not change. Once the input burst is complete, the circuit will make a transition to state S 0 and will compute the output, which in this case remains the same, 00.

We note that, depending on the encoding of the states, a critical-race may occur during this transition. For example, if the states are encoded as S 0 = 00, S A dash in a table entry signifies that the corresponding combination of current state and input is not permitted by the communication protocol between the circuit and the environment. For example, if the circuit is in state S 1 , an inputburst of 0010 is not allowed to occur. The synthesis process of MINIMALIST starts by performing state minimization on the symbolic state transition table, constrained such that the reduced state transition table has a hazard-free logic implementation [START_REF] Fuhrer | Optimista: State minimization of asynchronous FSMs for optimum logic[END_REF]. In the example of Fig. 2, the state transition table is already minimal. Next, dichotomies are added to ensure a critical-race free state encoding. Solving the dichotomies results in the state encoding S 0 = 00, S 1 = 01, and S 2 = 10 for the example circuit and the symbolic states are replaced by their binary values. The last step is to generate a minimal cost hazard-free logic implementation of the circuit [START_REF] Nowick | Exact two-level minimization of hazard-free logic with multiple-input changes[END_REF]. Fig. 3 shows the resulting implementation of the example asynchronous Burst-Mode machine, which includes some logic redundancy to ensure hazard-free operation.

Duplication in Burst-Mode Controllers

In this section, we discuss the shortcomings of duplication-based CED when applied to asynchronous Burst-Mode controllers and we propose remedies.

Shortcomings

Duplication-based CED is the simplest and most commonly used method in synchronous circuits. It employs a copy of the original circuit and a comparator to continuously check the results of the two circuits and identify any errorinduced discrepancies. Duplication, however, cannot be directly applied on asynchronous Burst-Mode controllers due The lack of a synchronizing clock introduces uncertainty as to when the responses of the two circuits should be compared. Process variations, input skew and the fact that the two circuits are separate entities are few of the reasons why two identical circuits may compute the correct response with different delay. Consequently, the output of the comparator may temporarily indicate an error, which in this case is a false alarm. The use of duplication-based CED is no longer straightforward without the requirement that the outputs be checked only when both are supposed to be ready.

Logic redundancy in Burst-Mode machines prevents hazards from occurring during error-free operation. As a result, some errors may cause only hazards but no functional discrepancy. For example, if the current state in the circuit of Fig. 3 is S 1 and the input changes from 1100 to 1000 then the next state should be S 1 , as indicated in Fig. 2. However, an error inducing a logic value of '0' at the output of gate 4 will result in a hazard at the next state lines. This is illustrated in the timing diagram of Fig. 4. The dashed line represents the logic value if the error was not present. In this example, the change of input b affects the next state function Y 1 before the change in gate 1 reaches Y 1 . During that time, Y 1 is at the logic value of '1' due to gate 4. Consequently, an error in gate 4 will generate a hazard at Y 1 but will not affect correctness of the results. Interestingly, the number of such errors is significant, exceeding 30% in many circuits.

Proposed Remedies

Based on the communication protocol, an asynchronous Burst-Mode machine changes its state and output only after an input burst is complete. Similarly, the environment is not allowed to provide a new input burst until the output burst of the circuit is complete, i.e. until it has finished evaluation of the previous input burst. This restriction forms the basis for synchronizing the comparison between the original and When the last bit of the input burst changes, the circuit starts evaluating its new state and output, which will be checked by the comparison window generated by the first bit change of the next input burst.

Error-induced hazards can be detected by adding the circuit of Fig. 6 to the next state and output bits of the circuit. Hazard detection is based on the fact that no more than one transition, either rising or falling, is allowed on these lines after each input burst. The hazard detection circuit is able to observe the occurrence of both a rising and a falling transition on a state or output bit. Every time an input changes, the transitions detected in the hazard detection circuit are reset. Subsequently, the upper feedback loop monitors the line and latches a rising transition while the lower feedback loop does the same for a falling transition. If both transitions are observed, then the hazard signal is asserted.

The enhanced duplication-based CED method is illustrated in Fig. 7. The change detection circuit is added to every input line and the hazard detection circuit is added to every output and state line of the original circuit only. Since the duplicate circuit does not interact with the environment, hazard detection in the duplicate circuit is not required. Finally, the error indication signal is asserted if the comparator detects a mismatch between the two circuits after an input change or if a hazard is observed in the original circuit.

Proposed Transition-Triggered CED

In an effort to reduce the cost of duplication in asynchronous Burst-Mode machines, we propose in this section a Transition-Triggered CED method which is shown in Fig. 9. Our method starts with the observation that hazards in the duplicate circuit do not affect the communication protocol between the original circuit and the environment. Therefore, the redundant logic used to make the original circuit hazardfree is not necessary in the duplicate circuit. By allowing hazards to occur in the duplicate circuit, its logic implementation can be optimized to reduce the cost. Hazards on the Interestingly, the transition prediction function can be used in conjunction with the comparison synchronizer to further reduce the cost of CED in two ways. First, the hazard detection circuit that was added to each output and state line can be eliminated: the transition prediction function indicates when changes are allowed to occur at the next state and output signals of the original circuit, while the change detection circuit of Fig. 5 indicates when such changes actually occur. An error-induced hazard in the original circuit would result in a mismatch between these two signals and may, thus, be detected without the addition of explicit hazard detection circuitry. Second, the functionality of the duplicate circuit can be optimized further. Since the hazard-free operation of the original circuit during an input burst is checked by the transition prediction function and the response change signal, comparison between the original circuit and the optimized duplicate is necessary only after an input burst is complete. Therefore, the functionality of the optimized duplicate for incomplete input bursts can be considered as "don't-care", allowing for further hardware reduction in its implementation.

The functionality of the optimized duplicate and the transition prediction function is illustrated in the state transition table of Fig. 8. In contrast to the table of Fig. 2, only entries with a change in the output or next state lines are defined for the duplicate circuit; the rest are "don't cares". The transition prediction function is defined for every defined entry in the state transition table of the original circuit and takes a logic value of '1' only when a transition appears in the next state or output lines at the end of an input burst. The state transition table shown in Fig. 8 is used to design the proposed Transition-Triggered CED method illustrated in Fig. 9. The state of the transition prediction function and the optimized duplicate circuit changes after an input burst is complete and in next state or output between input changes is stored using gates 1 and 2. Every time an input changes, two comparisons are performed: First, the change in the next state and outputs signal is compared to the transition prediction function using gate 3, in order to detect any unexpected transitions in the original circuit. Second, the result of the comparator is enabled, using the transition prediction function in gate 4, to check the response of the original circuit for correctness. The logic OR of these two comparisons, which is computed in gate 5, constitutes the error indication signal.

-,--0 -,--0 - - - - - - S 0,011 -, --0 S2,001 - S1,001 - - - S0,001 - - - - - - - S1,101 -, --0 - - -, --0 - - - - - - - - - - - -,--0 S 0,001 -, --0 -, --0 - - - - S 0 S 1 S 2

States Figure 8. Optimized Symbolic State Transition Table with a Transition Prediction Function

Experimental Results

In this section, we compare the area overhead of the proposed CED method to duplication-based CED. The specifications of the circuits used in these experiments are provided along with MINIMALIST in [START_REF]Tools (MINIMALIST[END_REF]. The circuits are first synthesized using MINIMALIST to generate an asynchronous implementation in pla [START_REF] Sentovich | SIS: a system for sequential circuit synthesis[END_REF] format. Next, the change de-tection, hazard detection and duplicate circuits are added to the original circuit, as described in Section 3.2, to perform duplication-based CED. The optimized duplicate circuit of the proposed Transition-Triggered CED is produced using espresso [START_REF] Sentovich | SIS: a system for sequential circuit synthesis[END_REF] based on the specification of the original circuit. The transition prediction function is generated using MINIMALIST to ensure hazard-free behavior. The change detection circuit, state multiplexors, and output comparator are added to the original circuit, as described in Section 4, to perform the proposed Transition-Triggered CED.

The results are analytically presented for the individual components of duplication-based CED in Table 1 and the proposed Transition-Triggered CED in Table 2. The gate count of the circuits is normalized to the equivalent number of 2-input NAND-gates. Under the first major heading in Table 1, we provide details about the circuits that were used: name, number of primary inputs, number of states and number of primary outputs. The literal and gate count of the original circuit, the duplicate circuit, the hazard detection circuit, the comparator and the CED synchronizer are presented in the second, third, fourth, fifth and sixth major heading, respectively. The last major heading summarizes the total literal and gate count for duplication-based CED. The results for the proposed Transition-Triggered CED method are illustrated in Table 2. Under the first two major headings, we repeat the original circuit information that appears in Table 1. The literal and gate count of the optimized duplicate circuit, the state multiplexors, the transition prediction function, the comparator and the CED synchronizer are presented in the third, fourth, fifth, sixth and seventh major heading, respectively. The last column summarizes the total literal and gate count for the proposed Transition-Triggered CED.

The average gate-count reduction of the proposed method over duplication-based CED over all benchmark circuits is 22.56%. In small benchmark circuits, the cost of the hazard detection circuit is very high relatively to the cost of the original circuit and, thus, the proposed method outperforms duplication-based CED significantly. For example, this is the case for tangrammixer and hpir. Moreover, the proposed method also reduces significantly the cost for large circuits, where the ratio of the cost of the hazard detection circuit to the original circuit is small. For example, this is the case for pesendif c and p1, where the cost is reduced by more than 22%. The cost of the optimized duplicate circuit is very close to the cost of the original circuit for small benchmarks. For example, this is the case for circuits concurmixer and hpir. This is attributed to the small amount of redundant logic used to design a hazard-free implementation of the specification of these circuits. In more complex circuits, such as while concur and rfcontrol, the cost of the optimized circuit is almost 50% of the cost of the original circuit. Moreover, the cost of the optimized duplicate of the largest asynchronous controller, p1, is less than 42% of the cost of the original circuit. As the circuit specification becomes more complex, the percentage of redundant logic that can be saved by Transition-Triggered CED over duplication-based CED also increases.

Conclusion

Duplication-based CED is not directly applicable to the class of asynchronous Burst-Mode controllers due to the lack of a global clock, the existence of redundant logic, and the communication protocol between these circuits and the environment. We showed that these obstacles can be overcome at the expense of additional hardware for comparison synchronization and hazard detection, resulting in a comprehensive CED method that detects not only the functional correctness of the circuit, but also its correct interaction with the environment. Furthermore, we demonstrated that a transition prediction function can be used to reduce the incurred overhead. The proposed Transition-Triggered CED method eliminates the additional hazard detection circuitry and permits a less expensive implementation of the duplicate circuit. Thus, as indicated through experimental results, an average of 22% in hardware savings is achieved.

4 Figure 4 .

 44 Figure 4. Timing Diagram Illustrating a Hazard to two reasons: (i) the lack of a global synchronization clock and (ii) the existence of redundant logic in the circuit.The lack of a synchronizing clock introduces uncertainty as to when the responses of the two circuits should be compared. Process variations, input skew and the fact that the two circuits are separate entities are few of the reasons why two identical circuits may compute the correct response with different delay. Consequently, the output of the comparator may temporarily indicate an error, which in this case is a false alarm. The use of duplication-based CED is no longer straightforward without the requirement that the outputs be checked only when both are supposed to be ready.Logic redundancy in Burst-Mode machines prevents hazards from occurring during error-free operation. As a result, some errors may cause only hazards but no functional discrepancy. For example, if the current state in the circuit of Fig.3is S 1 and the input changes from 1100 to 1000 then the next state should be S 1 , as indicated in Fig.2. However, an error inducing a logic value of '0' at the output of gate 4 will result in a hazard at the next state lines. This is illustrated in the timing diagram of Fig.4. The dashed line represents the logic value if the error was not present. In this example, the change of input b affects the next state function Y 1 before the change in gate 1 reaches Y 1 . During that time, Y 1 is at the logic value of '1' due to gate 4. Consequently, an error in gate 4 will generate a hazard at Y 1 but will not affect correctness of the results. Interestingly, the number of such errors is significant, exceeding 30% in many circuits.

Figure 6 .

 6 Figure 5. Change Detection Circuit

Figure 7 .

 7 Figure 7. Enhanced Duplication-Based CEDfeedback lines of the optimized duplicate, however, jeopardize the operation of the asynchronous circuit. To avoid this problem, we use multiplexors on the state lines of the optimized duplicate circuit to select between the current state and the next state. The multiplexors are controlled using an additional Transition Prediction Function, which signifies the end of an input burst. The implementation of the transition prediction function needs to be hazard-free to avoid propagation of an incorrect next state through the multiplexors.Interestingly, the transition prediction function can be used in conjunction with the comparison synchronizer to further reduce the cost of CED in two ways. First, the hazard detection circuit that was added to each output and state line can be eliminated: the transition prediction function indicates when changes are allowed to occur at the next state and output signals of the original circuit, while the change detection circuit of Fig.5indicates when such changes actually occur. An error-induced hazard in the original circuit would result in a mismatch between these two signals and may, thus, be detected without the addition of explicit hazard detection circuitry. Second, the functionality of the duplicate circuit can be optimized further. Since the hazard-free operation of the original circuit during an input burst is checked by the transition prediction function and the response change signal, comparison between the original circuit and the optimized duplicate is necessary only after an input burst is complete. Therefore, the functionality of the optimized duplicate for incomplete input bursts can be considered as "don't-care", allowing for further hardware reduction in its implementation.The functionality of the optimized duplicate and the transition prediction function is illustrated in the state transition table of Fig.8. In contrast to the table of Fig.2, only entries with a change in the output or next state lines are defined for the duplicate circuit; the rest are "don't cares". The transition prediction function is defined for every defined entry in the state transition table of the original circuit and takes a logic value of '1' only when a transition appears in the next state or output lines at the end of an input burst. The state transition table shown in Fig.8is used to design the proposed Transition-Triggered CED method illustrated in Fig.9. The state of the transition prediction function and the optimized duplicate circuit changes after an input burst is complete and

Figure 10 .

 10 Figure 9. Transition-Triggered CED

Table 1 . Experimental Results for Duplication-Based CED

 1

		Circuit		Original	Duplicate	H. D. Circuit	Comparator	Synchronizer	Total
	Name	I/S/O	Lit.	Gates	Lit.	Gates	Lit.	Gates	Lit.	Gates	Lit.	Gates	Lit.	Gates
	concur-mixer	3/3/3	26	16	26	16	78	70	38	25	22	17	190	144
	martin-q-element	2/2/2	14	9	14	9	46	41	22	14	14	12	110	85
	opt-token-distributor	4/6/4	74	41	74	41	112	98	56	35	30	23	346	238
	pe-send-ifc	5/5/3	110	58	110	58	96	84	48	30	38	30	402	260
	tangram-mixer	3/2/2	17	10	17	10	46	41	22	14	22	17	124	92
	p1		13/11/14	458	238	458	238	278	247	134	85	142	77	1470	885
	while concur	4/4/3	41	24	41	24	96	84	48	30	30	23	256	185
	rf-control	6/6/5	75	37	75	37	128	112	64	40	48	36	390	262
	hp-ir		3/2/2	13	8	13	8	46	41	22	14	22	17	116	88
	while	4/3/3	27	16	27	16	78	70	38	25	30	23	200	150
	Circuit		Original	Opt. Duplicate	Muxes	Transition Func.	Comparator	Synchronizer	Total
	Name	I/S/O	Lit.	Gates	Lit.	Gates	Lit.	Gates	Lit.	Gates	Lit.	Gates	Lit.	Gates	Lit.	Gates
	concur-mixer	3/3/3	26	16	22	14	12	7	6	3	38	25	60	47	164	112
	martin-q-element	2/2/2	14	9	12	7	6	4	4	3	22	14	36	29	94	66
	opt-token-distributor	4/6/4	74	41	46	22	18	11	23	14	56	35	86	65	303	188
	pe-send-ifc	5/5/3	110	58	48	27	18	11	20	10	48	30	86	65	330	201
	tangram-mixer	3/2/2	17	10	13	8	6	4	7	4	22	14	44	34	109	74
	p1	13/11/14	458	238	185	99	24	14	92	49	134	85	276	180	1169	665
	while concur	4/4/3	41	24	21	12	18	11	18	11	48	30	78	59	224	147
	rf-control	6/6/5	75	37	34	19	18	11	25	15	64	40	112	84	328	206
	hp-ir	3/2/2	13	8	10	6	6	4	8	5	22	14	44	34	103	71
	while	4/3/3	27	16	13	9	12	7	17	9	38	25	68	53	175	119

Table 2 . Experimental Results for Transition-Triggered CED

 2

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

A critical-race hazard exists if two state variables change value and the machine's next state depends on the order of arrival of these changes[START_REF] Huffman | The Synthesis of Sequential Switching Networks[END_REF][START_REF] Unger | Asynchronous Sequential Switching Circuits[END_REF].Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE


Hamidreza Hashempour

Luca Schiano
email: lschiano@ece.neu.edu

Fabrizio Lombardi
email: lombardi@ece.neu.edu

Evaluation of Error-Resilience for Reliable Compression of Test Data

Keywords: error resilience, fault tolerance, yield, reliable operation of ATE, compression

This paper addresses error-resilience as the capability to tolerate bit-flips in a compressed test data stream (which is transferred from an Automatic Test Equipment (ATE) to the Device-Under-Test (DUT)). In an ATE, bit-flips may occur in either the electronics components of the loadboard, or the high speed serial communication links (between the user interface workstation and the head). It is shown that errors caused by bit-flips can seriously degrade the test quality (as measured by coverage) of the compressed data streams. The effects of bit-flips on compression are analyzed and various

test data compression techniques are evaluated. It is shown that for benchmark circuits, coverage of test sets can be reduced by 10%-30%.

Introduction

The electronic industry has been highly affected by the widespread use of third party ready-to-use Intellectual Property (IP) cores [START_REF] Zorian | Test Requirements for Embedded Core-Based Systems and IEEE P1500[END_REF] for assembling complex ICs. Recently, the integration of multiple cores has resulted in the manufacturing of System-on-a-Chip (SoC) on the same silicon die. A complete test set for a SoC includes test sets for each core (often provided by the core vendor). The aggregate volume of these test sets can be very large, in most cases well in the range of a few Gb. The application of such large volume of test data requires significant storage facilities on an ATE and may take long time to execute. Large storage translates into higher equipment cost while long test application time impacts the ATE throughput (DUTs tested per unit time), thus increasing the overall cost of test.

To address these problems, test data compression through so-called resource partitioning has been introduced. By compressing the initial test sets, a smaller volume of data is loaded on the ATE, so reducing the cost of storage. Additionally, the compressed test data is trans-ferred to the DUT where it is decompressed and applied. As a smaller volume of data is transferred, then test application time can be reduced too. Traditionally, a reduction in data volume has been accomplished through vector compaction [START_REF] Hamzaoglu | Test Set Compaction Algorithms for Combinational Circuits[END_REF], however compression can be applied to already compacted data to further reduce its volume.

Current literature has addressed compression mostly with respect to its efficiency in reducing data volume (commonly quantified by the compression ratio), test application time, and overhead complexity (often for the on-DUT decompression circuitry). In [START_REF] Jas | Test Vector Decompression via Cyclical Scan Chains and Its Application to Testing Core-Based Designs[END_REF], Run-Length coding has been proposed for compression. This has been extended by Golomb and Frequency-Directed-Run length (FDR) coding techniques in which variable length codewords are used for runs of 0 [START_REF] Chandra | System-on-a-Chip Test-Data Compression and Decompression Architectures Based on Golomb Codes[END_REF] [START_REF] Chandra | Frequency-Directed Run-Length (FDR) Codes With Application to Systemon-a-Chip Test Data Compression[END_REF]. In [START_REF] Iyengar | Huffman Encoding of Test Sets for Sequential Circuits[END_REF], Huffman coding has been applied to fixed length symbols. The application of Huffman coding to variable length symbols has been studied in the so-called Variable-Input-Huffman Coding (VIHC) [START_REF] Gonciari | Variable-Length Input Huffman Coding for System-ona-Chip Test[END_REF]. To avoid the exponential complexity of a Huffman decoder with an increasing length of symbols, [START_REF] Jas | An Efficient Test Vector Compression Scheme Using Selective Huffman Coding[END_REF] has introduced Selective Huffman coding.

For manufacturing testing of VLSI systems such as SoC, the transfer of compressed data between the ATE and the DUT must be also considered. A recent work [START_REF] Hashempour | Error-Resilient Test Data Compression Using Tunstall Codes[END_REF] has statistically evaluated the error-resilience of Huffman coding and proposed a modified version of Tunstall [START_REF] Tunstall | Synthesis of Noiseless Compression Codes[END_REF] coding to achieve a higher level of error-resilience against bit-flips. Test data has been modified by adding redundancy (one extra bit) to each codeword to preserve vector boundaries in the compressed stream [START_REF] Hashempour | Error-Resilient Test Data Compression Using Tunstall Codes[END_REF]. This is referred to as bitpadding. The added bit is 1 if the codeword starts a new test vector, it is 0 otherwise. In this paper, we expand upon [START_REF] Hashempour | Error-Resilient Test Data Compression Using Tunstall Codes[END_REF] by considering the following novel features:

• We show that the so-called "Shift and Propagation" effects discussed in [START_REF] Hashempour | Error-Resilient Test Data Compression Using Tunstall Codes[END_REF] are closely related and Shift is a special case of Propagation.

• We expand our evaluation to 3 other compression techniques, namely, VIHC, Golomb, and FDR.

The rest of this paper is organized as follows: Section 2 presents the basic principles of error-resilience and its importance within the context of reliable ATE operation. Section 3 presents the effect of bit-flips on existing compression approaches; it also discusses "Shift and Propagation" effects, and shows their relationship. Section 4 presents the experimental framework of this analysis; results and comparison for four widely used compression techniques are presented for error-resilience. Section 5 concludes the paper.

Basic Concepts

In today's ATE architectures, the high volume and the speed of communication may result in the likely occurrence of errors in data transmission. These errors are caused by bit-flips which affect the test data stream. Bit-flips can also occur in the head of the ATE: the presence of a transmission line between the ATE pins and the DUT may be affected by noise in the so-called loadboard, leading to errors due to bit-flips. Moreover, the generation of test inputs as pin waveforms to the DUT, can also introduce an additional source of bit-flips (for example a ground bounce at the DUT receiver connected to the loadboard can result into bit-flips if the voltage levels are close to the margins such as for 3.3V or 1.5V DUTs). In general, once the ATE test program and loadboard are fully debugged, the occurrence of bit-flips can be reduced. However as testing requires very high speed (tens of millions of ATE cycles over hundreds of pins), bit-flips must be considered to be unavoidable in ATE environments [START_REF] West | Private Communication[END_REF]. Bit-flips can negatively affect the testing process over its entire spectrum: while developing test programs, bit-flips increase costs associated with debugging and development, while reducing productivity. During manufacturing test, a bit-flip can change data such that the coverage of the erroneous (decompressed) test set (as affected by bit-flips) can be reduced. Reduction in coverage translates into a lower yield and an increase in Defects Per Million (DPM) for products shipped to customers.

Bit-Flips and Compression

The effect of a bit-flip is significant when test data compression is required. On average, bits in a compressed bitstream carry more information compared with the initial uncompressed stream because compression techniques rely on removing redundancy. Consequently, on average a bit-flip in a compressed bit stream can destroy significantly more information.

Example 1: Consider a compressed test data with a compression ratio of 95%, i.e. a 20 times reduction in data volume. On average, each bit in the compressed bit stream is expanded into 20 bits of the initial uncompressed stream. If a bit-flip occurs in the compressed bit stream, then we can expect 20 bits to be affected in the uncompressed stream. These bits can be scattered over the uncompressed stream, thus affecting multiple vectors and seriously degrading the coverage of the decompressed test set.

In this paper, we refer to error-resilience as the ability of a data stream (encoded using a specified compression technique) to tolerate bit-flips. Error-resilience is measured by the coverage of the compressed test stream in the presence of bit-flips. The coverage of the uncompressed test set is equivalent to the error-resilience in the presence of no bit-flip. It also represents the (relative) maximum level of coverage. Other measures for error-resilience (such as the manufacturing yield and Defects-Per-Million (DPM)) can be statistically related to coverage using previously published techniques [START_REF] Agrawal | Fault Coverage Requirement in Production Testing of LSI Circuits[END_REF] [START_REF] Williams | Defect Level as a Function of Fault Coverage[END_REF].

An approach which addresses the negative effects of bitflips, is based on the use of Error-Correcting-Codes (ECC), for example the data downloaded from the ATE workstation to the test head is often coded using additional bits such as parity or Cyclic-Redundancy-Codes (CRC). However, this is not readily applicable to test data compression due to its negative impact on different figures of merit such as the additional hardware resources required on the DUT, the time it may take to correct the flipped bits, and the added redundancy on the compression ratio. A different technique is based on the application of inherent error-resilient compression codes such as Tunstall [START_REF] Tunstall | Synthesis of Noiseless Compression Codes[END_REF]. Figure 1 compares the coverage reduction as a function of the bit-flip count for Huffman and Tunstall codes. Both techniques have been made partially error-resilient using the bit-padding technique of [START_REF] Hashempour | Error-Resilient Test Data Compression Using Tunstall Codes[END_REF].

Analysis

A compression technique often partitions the uncompressed test data into a set of allowed symbols {s i |1 ≤ i ≤ S}, where S is the total number of different symbols. A coding technique maps each symbol s i to a corresponding codeword c i . The compressed bit-stream can be represented by an ordering π of codewords,

(c π(1) , c π(2) , • • • , c π(N ) )
where N is the total number of symbols/codewords in the test data.

A bit-flip can change the compressed sequence in a complex manner; this is a function of different parameters such as compression ratio, number of symbols, length of symbols/codewords, and the ordering π. However, a bit-flip always affects a codeword in one of the following manners:

• The affected codeword is broken into k ≥ 1 valid codewords.

• The affected codeword is broken into k ≥ 0 valid codewords and a so-called "dangling suffix" which is not a valid codeword.

Example 2: Consider the set of Huffman codewords given by {0, 10, 110, 111}. A bit-flip affecting codeword 0 results into a zero valid codeword and a dangling suffix of 1 which is not a valid codeword. A bit-flip affecting the first bit of codeword 10, results into 00, i.e. two valid codewords. A bit-flip at the second bit of codeword 111, results into 101, i.e. one valid codeword and a dangling suffix of 1 which is not valid.

The significant feature of the first case is that if a codeword c π(i) in the compressed bit stream is affected by a bitflip, then all codewords c π(i+1) to c π(N ) occurring next, will be unaffected. The only effect of the bit-flip is to have k additional codewords between c π(i-1) and c π(i+1) as a result of c π(i) being broken. In this case, the correct sequence of codewords starting from c π(i+1) is shifted by k codewords. This is shown in Figure 2. The significant feature of the second case is that if a codeword c π(i) is affected by a bit-flip, the dangling suffix will form a valid codeword with a portion of c π(i+1) . This . If c π(i+1) is also left with a dangling suffix, the suffix will form a valid codeword with a portion of c π(i+2) and so on. If eventually c π(i+j) does not have a dangling suffix, error propagation will stop and c π(i+j+1) to c π(N ) will be unaffected. However, the entire compressed stream between c π(i+1) and c π(i+j) is corrupted and therefore made useless. This is shown in Figure 3.

A simple comparison between these two cases, highlights the relationship between shift and propagation due to a bit-flip. In the first case, a codeword (c π(i) ) is lost and the remaining codewords are shifted by at least one codeword (since k ≥ 1). In the second case, j + 1 codewords (from c π(i) to c π(i+j) ) are lost, and the remaining codewords are shifted by at least one codeword. Propagation and shift only differ in the number of lost (corrupted) codewords. A shift is a special case of propagation in which only one codeword is lost, i.e. j = 0. Propagation always comes with shifts.

An important observation is that a coding technique with constant length codewords, will never have a propagation with j > 0, independently of the number of bit-flips or their location. This occurs because a bit-flip can never break a constant length codeword into more than one valid codewords and a dangling suffix is never encountered. This means that Run-Length and Tunstall codes will have at most one lost (corrupt) codeword and a possible shift effect.

Defect Level Considerations

With bit-flips occurring, portions of the test set can be lost at decompression. This translates into a reduction of coverage, i.e. some faults cannot be tested and defective DUTs with these undetected faults could pass the testing process. These falsely fault-free DUTs will increase the defect level (DL). Let y and DL be the initial yield and defect level respectively. For a coverage f , the following relation holds [START_REF] Williams | Defect Level as a Function of Fault Coverage[END_REF]:

DL = 1 -y 1-f (1)
Assume that the coverages before and after bit-flips are given by f 1 and f 2 respectively. Then DL 2 -DL 1 is the increase in defect level due to bit-flips, i.e.

DL 2 -DL 1 = y 1-f1 -y 1-f2 (2)
Figure 4 shows the increase in DPM 1 (the number of Defective parts Per Million DUTs) as a function of coverage loss f 1 -f 2 when f 1 = 100% for three initial values of yield (i.e. y). A very small change in coverage (even 1%) can significantly increase the DPM. This highlights the importance of error-resilience for data compression in a manufacturing environment.

Experimental Results

To evaluate error-resilience and related phenomena, the MINTEST dynamically compacted test-cubes for the fullscan versions of the 6 largest ISCAS89 circuits are considered [START_REF] Hamzaoglu | Test Set Compaction Algorithms for Combinational Circuits[END_REF]. All don't care bits are set to 0. Test vectors are reordered using the LKH hueristic [START_REF] Hashempour | ATE-Amenable Test Data Compression With no Cyclic Scan Registers[END_REF]; however, they are not differentiated because it has been shown that differentiation can further reduce error-resilience [START_REF] Hashempour | Error-Resilient Test Data Compression Using Tunstall Codes[END_REF]. Four widely cited compression techniques (Golomb, Huffman, FDR, and VIHC) are used to compress test vectors of each circuit. Huffman symbols are 4-bit, VIHC symbols are at most 16 bits long, the parameter m of Golomb was chosen for maximal compression per circuit, and the parameter k of FDR is set according to the longest run of 0.

Bit-flips are injected into the compressed test stream of each circuit. The measure of bit-flip count is considered because it is independent of the test data size. The location of the bit-flips is assumed to be uniformly distributed over the entire compressed bit-stream. The erroneous data is then decompressed and its coverage is established. The reduction in coverage is the measure by which the effect of bit-flips on the error-resilience is evaluated. As the bit-flip location is statistical in nature, then each bit-flip count is repeated 50 times; the average coverage and standard deviation over all experiments are measured. Figure 5 shows the experimental framework for evaluating error-resilience.

Table 1, Table 2, Table 3, and Table 4 show the average coverage and standard deviation as representative of error-resilience of Golomb, Huffman, FDR, and VIHC respectively. Table 5 compares the average coverage over all benchmark circuits for different coding techniques. In all tables, a column corresponds to a specific bit-flip count, for example "1b" means only 1 bit-flip has been injected. Huffman coding results in a much lower coverage loss due to bit-flips. The coverage loss is about 10% for 1 bit-flip and increases in the worst case to 27% for 10 bit-flips in Huffman coding. For only 1 bit-flip, Golomb, FDR, and VIHC have approximately 14% coverage loss from the 97% maximum coverage level. For an initial yield of 85%, this translates into an increase in DPM of almost 22000, i.e. 22000 defective DUTs will be shipped to customers. This is obviously non acceptable2 and stresses the importance of errorresilient in data compression methods for high quality manufacturing test.

Figure 6 shows the decrease in coverage from its maximum value as a function of the bit-flip count. The results are averaged over all 6 benchmarks examined in Table 1

Conclusion

Error-resilience for reliable test data compression has been introduced in this paper; it has been shown that bitflips in an ATE can seriously affect compression resulting in corrupted test data for decompression. The reduction in fault coverage of the erroneous test data has been evaluated for four compression techniques. It has been reported that a fault coverage loss of 10%-30% can occur for large benchmark circuits due to the combined effect of data compression and bit-flips which can negatively affect DPM.

Figure 1 .

 1 Figure 1. Average fault coverage of Tunstall and Huffman codes over the six largest ISCAS89 benchmarks (with Bit-Padding [10]) versus bit-flip count

Figure 2 .

 2 Figure 2. Conceptual view of the shift effect due to a bit-flip

Figure 3 .

 3 Figure 3. Conceptual view of the propagation effect due to a bit-flip

Figure 4 .

 4 Figure 4. Increase in the number of defective DUTs per million versus fault coverage loss

1 6 BitFigure 5 .

 65 Figure 5. Experimental framework

Figure 6 .

 6 Figure 6. Average fault coverage over all benchmarks versus bit-flip count

Table 4 .

 4 to

		Standard Deviation		Average Coverage
	Benchmark	1b	2b	5b	10b	1b	2b	5b	10b Maximum
	s5378	7%	8%	6%	5% 91% 86% 80% 77%	99.13%
	s9234	15% 16% 11% 9% 72% 65% 50% 51%	93.47%
	s13207	13% 11% 8%	6% 85% 77% 70% 65%	98.46%
	s15850	10% 11% 7%	6% 78% 77% 66% 65%	96.68%
	s38417	10% 10% 7%	6% 87% 82% 78% 73%	99.47%
	s38584	10% 9%	6%	5% 81% 75% 72% 70%	95.85%

Table 1 . Average and Standard Deviation of fault coverage for Golomb compression

 1

		Standard Deviation		Average Coverage
	Benchmark	1b	2b	5b	10b	1b	2b	5b	10b Maximum
	s5378	9%	8%	7%	5% 90% 85% 80% 75%	99.13%
	s9234	16% 15% 11% 6% 80% 68% 64% 52%	93.47%
	s13207	13% 11% 8%	6% 86% 79% 70% 67%	98.46%
	s15850	13% 12% 8%	4% 82% 76% 67% 66%	96.68%
	s38417	11% 10% 6%	6% 87% 84% 75% 73%	99.47%
	s38584	10% 9%	6%	5% 81% 76% 72% 68%	95.85%

Table 2 . Average and Standard Deviation of fault coverage for FDR compression

 2

			Standard Deviation		Average Coverage
	Benchmark	1b	2b	5b	10b	1b	2b	5b	10b Maximum
	s5378	9%	8%	8%	6% 93% 87% 83% 78%	99.13%
	s9234	18% 19% 15% 11% 78% 73% 64% 57%	93.47%
	s13207	6% 11% 10% 9% 92% 85% 79% 74%	98.46%
	s15850	14% 13% 9%	7% 84% 76% 70% 64%	96.68%
	s38417	12% 12% 9%	7% 89% 85% 80% 75%	99.47%
	s38584	10% 11% 10% 6% 85% 78% 72% 71%	95.85%

Table 3 . Average and Standard Deviation of fault coverage for Huffman compression

 3

		Standard Deviation		Average Coverage
	Benchmark	1b	2b	5b	10b	1b	2b	5b	10b Maximum
	s5378	9%	8%	7%	6% 89% 85% 80% 76%	99.13%
	s9234	16% 16% 12% 6% 75% 66% 59% 52%	93.47%
	s13207	12% 11% 7%	5% 85% 77% 69% 66%	98.46%
	s15850	17% 10% 8%	5% 79% 74% 68% 66%	96.68%
	s38417	10% 12% 7%	5% 86% 82% 76% 73%	99.47%
	s38584	9%	8%	5%	5% 85% 75% 73% 69%	95.85%

Table 4 . Average and Standard Deviation of fault coverage for VIHC compression

 4

		Average Fault Coverage
	Coding	1b	2b	5b	10b
	Golomb	82% 77% 69% 67%
	FDR	84% 78% 71% 67%
	Huffman 87% 81% 75% 70%
	VIHC	83% 76% 71% 67%
	Maximum 97% 97% 97% 97%

Table 5 . Average fault coverage over all bench- marks for compression techniques

 5

		100
		95								Huffman Golomb
										FDR
	Fault Coverage (%)	75 80 85 90								VIHC
		70
		0 65	1	2	3	4	5	6	7	8	9	10
						Bit-Flip Count

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Typical DPM values are 500 or less Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE