Abstract-With increasing process fluctuations in nano-scale technology, testing for delay faults is becoming essential in manufacturing test to complement stuck-at-fault testing. Designfor-testability techniques, such as enhanced scan are typically associated with considerable overhead in die-area, circuit performance, and power during normal mode of operation. This paper presents a novel test technique, which can be used as an alternative to the enhanced scan based delay fault testing method, with significantly less design overhead. Instead of using an extra latch as in the enhanced scan method, we propose using supply gating at the first level of logic gates to hold the state of a combinational circuit. Experimental results on a set of ISCAS89 benchmarks show an average reduction of 33% in area overhead with an average improvement of 71% in delay overhead and 90% in power overhead during normal mode of operation, compared to the enhanced scan implementation.

I. INTRODUCTION

Delay faults in a circuit occur when a net functions properly but fails to meet timing requirement. Delay faults are sometimes caused by defects that are not large enough to cause a stuck-at failure by changing logic level, but affect the signal propagation time. However, an emerging cause of delay failure is the uncertainty in circuit design due to process fluctuations, limitation of timing models and static timing analysis tools etc. With growing impact of process variation in sub-100nm technology regime, designers face more uncertainty in circuit design [START_REF] Borkar | Parameter Variations and Impact on Circuits and Microarchitecture[END_REF] and delay faults become more likely. Therefore, it is becoming mandatory for manufacturing test to include delay testing along with stuck-at tests [START_REF] Article | Delay-fault testing mandatory[END_REF] [START_REF]Scan-based transition-fault test can do job[END_REF].

Scan architectures provide an efficient way to test for delay faults with good fault coverage. Scan-based structural delay testing not only helps detection but also diagnosis of delay faults [START_REF] Article | Delay-fault testing mandatory[END_REF] and, hence, is a popular choice for delay fault testing. However, testing for delay faults usually require launching a transition at the input for the circuit under test (CUT), and capturing the response of the circuit at rated clock. Although it is easier to apply a transition at the primary inputs of the CUT by the tester, it is not straight-forward to make a transition at the state inputs. Based on test application procedure, there are three prevalent techniques for scan-based delay testing. In the first one, called broad-side delay test, no transition is applied to the state inputs. State portion of the second pattern is derived as the combinational circuit's response to the first pattern. Although, the testing process is simple and it does not require any additional Design-For-Testability (DFT) logic, the broadside case can suffer from poor fault coverage [START_REF] Wang | Hybrid Delay Scan: A Low Hardware Overhead Scanbased Delay Test Technique for High Fault Coverage and Compact Test Sets[END_REF]. In the second method, referred as skewed-load delay testing, transition in the state inputs is induced by shifting the scan values by one bit position. However, design requirement for skewed-load case can be costly because of fast switching scan enable signal [START_REF] Wang | Hybrid Delay Scan: A Low Hardware Overhead Scanbased Delay Test Technique for High Fault Coverage and Compact Test Sets[END_REF]. Moreover, since the second pattern (launching pattern) is highly correlated to the first one (initialization pattern), the test generation for high fault coverage can be difficult [START_REF] Bushnell | Essentials of Electronic Testing for Digital, Memory, and Mixed-Signal VLSI Circuits[END_REF]. The third approach, referred as enhanced scan method, allows easy application of a transition and enables deterministic choice of any launching pattern in the scan flip-flops for best possible fault coverage [2] [11].

Although enhanced scan method has high combinational path testability, it, however, involves high DFT overhead since it introduces an extra latch, named as hold latch, at the output of a scan flip-flop to hold the initialization pattern [START_REF] Bushnell | Essentials of Electronic Testing for Digital, Memory, and Mixed-Signal VLSI Circuits[END_REF]. The latch resides in the stimulus path between the scan flip-flops and the combinational logic (as shown in Fig. 1) and can considerably affect circuit performance during normal mode of operation. Adding to the overhead, the latch takes up significant amount of die-area and consumes power in normal mode. Fig. 1 (b) also shows a multiplexer-based holding logic as proposed in [START_REF] Zhang | Power Reduction in Test-Per-Scan BIST[END_REF]. Although the authors' objective in [START_REF] Zhang | Power Reduction in Test-Per-Scan BIST[END_REF] is not delay testing, we have observed that a multiplexer can be used (as shown in Fig. 1 (b)) in place of a hold latch to retain the state of a scan flip-flop during scan shifting. There have been a large number of investigations to devise alternative delay fault testing strategies with reduced DFT overhead and acceptable coverage [3] [4] [5] [START_REF] Wang | Hybrid Delay Scan: A Low Hardware Overhead Scanbased Delay Test Technique for High Fault Coverage and Compact Test Sets[END_REF]. However, these techniques are either not as efficient as enhanced scan method with respect to fault coverage and required number of test patterns, or they complicate the test generation/application considerably.

In this paper, we propose a delay fault testing technique, which allows enhanced scan-like test application, but comes at a much lower hardware overhead. The technique, referred as First Level Hold (FLH) employs the principle of "supply gating", in a novel way, to hold the state of combinational logic. Instead of holding the initialization pattern at the scanhold latch as done in the case of enhanced scan [START_REF] Bushnell | Essentials of Electronic Testing for Digital, Memory, and Mixed-Signal VLSI Circuits[END_REF], we hold the state of the combinational circuit in response to the first pattern by gating the VDD and GND of the first level logic gates. Test application remains as in enhanced scan approach, except that the control for holding state is now moved from the hold latches to the gating control of the first level of logic. Fig. 2. Supply gating applied to first level gate unlike enhanced scan test, it does not introduce extra level of logic in the timing path of a circuit and hence, the delay overhead reduces greatly compared to the enhanced scan. We have compared FLH technique with enhanced scan method and a possible MUX-based alternative [START_REF] Zhang | Power Reduction in Test-Per-Scan BIST[END_REF]. Experiments performed on a set of ISCAS89 benchmarks show superior results with FLH in terms of area, delay and power overhead compared to the alternative methods. It is worth noting that FLH also maintains the power-saving advantage of enhanced scan in the test mode, since it prevents redundant switching in the combinational block by isolating it from the activity in scan register.

The rest of the paper is organized as follows: Section II illustrates the proposed gating technique for delay testing. Section III presents experimental results in terms of area, delay and power for a set of benchmark circuits. Section IV describes important test issues associated with the proposed technique. Section V describes ways to further reduce DFT overhead and section VI concludes the paper.

II. FIRST LEVEL HOLD FOR DELAY FAULT TEST

The requirement of enhanced scan based delay fault testing is to apply a transition at the state inputs of a combinational block by holding its output state in response to the initial pattern before applying the second pattern. This can be achieved by adding a hold latch as in the enhanced scan or a MUX at the input of the combinational circuit (Fig. 1). We have observed that, interestingly, we can achieve holding the state of the combinational logic by "gating" the supply lines of the first level logic gates. Fig. 2 shows first level supply gating for an inverter chain. If the output of the first level logic gates (OUT1 in Fig. 2) can hold their state in the sleep (i.e. gated) mode, logic gates in their fanout cones can also retain their states.

Let us consider the circuit in Fig. 2 with IN at '0' and OUT1 at '1' when the gating control or SLEEP signal is applied. When the SLEEP signal is '1', the node OUT1 is floated since there is no path to VDD or GND from this node. In this case, the voltage of OUT1 can remain at '1' due to the charge that is held in that node. However, since OUT1 is floated, the charge held in OUT1 node can leak due to leakage of transistors connected to that node, which can result in a change in the state of OUT1 node. This is particularly aggravated if IN switches to '1' in the sleep mode and stays at '1' for a long enough time. This scenario is simulated in Hspice for the circuit shown in Fig. 2 using the 70nm Berkeley Predictive Technology Models [START_REF]Predictive Technology Model[END_REF]. We have observed that the voltage of OUT1 falls below 600mV in less than 100ns. Assuming a scan chain with a length 1000 flip-flops and a scan frequency of 1GHz, the scan time is 1µs which is much longer than 100ns. As OUT1 slowly decays below V dd-V th, in the second inverter (Fig. 2 In order to avoid floated nodes in the sleep mode and ensure hold capability, the outputs of the first level gates need to be forced to VDD or GND, depending on their initial logic state. This can be achieved by adding a latch element (crosscoupled inverters) at the output node. The latch element needs to be enabled only in the sleep mode to hold the output state of the first level gate. The general scheme of the proposed supply gating scheme is shown in Fig. 3 and the transmission gate can use minimum-sized transistors to minimize their impact on area, circuit delay, and power during normal mode of operation. Minimum sized inverters are large enough to be able to hold the state of the output node in the hold mode despite the presence of leakage and noise. Use of minimum sized transistors for the latch element reduces loading on the outputs of first level gates, resulting in minimal delay and power penalty. The size of the supply gating transistors can be optimized for delay under the given area constraint. Fig. 4 shows the simulated waveforms of the FLH scheme applied to the inverter chain in Fig. 2. As observed from the waveforms, the circuit can strongly hold its state (OUT1, OUT2, and OUT3) despite the switching at the input (IN). first pattern (V1), it is applied to the combinational circuit by turning the gating transistors on, while the primary input (PI) bits are applied to PI. After the combinational circuit stabilizes, the second pattern (V2) is scanned-in while V1 is held since the gating transistors in the first level gates are turned off.

A. Scan Design Using FLH

Next, the transition is launched by activating TC and applying the PI bits and the results are latched after one rated clock period.

III. EXPERIMENTAL RESULTS AND COMPARISONS

To estimate the effectiveness of the FLH scheme, we simulated a set of ISCAS89 benchmark circuits and obtained area, power, and performance overhead in case of FLH, enhanced scan, and MUX-based approaches. The simulations were performed using the 70nm BPTM models [START_REF]Predictive Technology Model[END_REF] to observe the effect of gating in a sub-100nm scaled technology. For the latch and mux circuitry, we have used optimized implementation obtained from the LEDA library, as shown in the schematic in Fig. 6. The gate-level netlists were first technology-mapped to LEDA 0.25µm standard cell library using Synopsys design compiler by setting the mapping effort to medium. The library contains complex gate types e.g. "aoi" (and-or-invert) and "mux", and hence, the total number of logic gates is reduced from that in original benchmark. The benchmark circuits are then translated to Hspice netlists and scaled to 70nm. We assumed full-scan implementation of the benchmarks. Power is measured in NanoSim by applying 100 random vectors to the inputs and delay is measured by Hspice simulation of the critical path of a circuit.

Table I shows comparisons of these techniques in terms of area overhead. Since the layout rules for the 70nm node are not available, the measure used for area is the total transistor active area (W * L for a transistor). Enhanced scan circuit has the largest area overhead followed by the MUX-based technique. FLH exhibits the smallest area overhead for most benchmark circuits. In both enhanced scan and MUX-based methods, the holding elements (latch and MUX) are inserted at the state inputs of the circuit. This means that there is one gating element per scan flip-flop (Fig. 1 (a)). However, in FLH, gating logic is inserted in all first level gates (Fig. 5), the number of which depends on the number of unique fanout gates of the scan flip-flops. Therefore, for a circuit with large fan-out for state inputs, such as s838, the area overhead in the FLH technique can be more than the others. However, number of fanouts in a circuit are usually not high (2.3 on average per scan flip-flop as can be obtained from column 2 and 3) to satisfy delay constraint of a circuit, since higher fanout means higher load at the output of a gate and hence, higher delay. Number of unique fanouts, i.e. the first level gates (as shown in column 4) is further less (1.8 on average per scan flipflop) due to overlapping of fanout cones. FLH shows 33% and 26% reduction in area overhead on an average as compared to the enhanced scan and MUX-based techniques, respectively. It is worth noting that FLH does not introduce additional test control signals. Therefore, FLH is expected to have no area penalty over enhanced scan due to routing of test controls.

Table II shows comparison of impact on circuit delay for different benchmark circuits. As observed from Table II, the proposed technique has the least impact (minimal increase) on circuit delay. The MUX-based method shows the largest increase. FLH exhibits reduction of up to 10% in overall circuit delay compared to enhanced scan approach. It is worth noting that the logic depth for the test circuits is fairly high (column 2). Since the original delay of the critical path is very large, the percentage improvement in circuit delay in FLH compared to the others is not very high. However, comparing the percentage reduction in delay overhead in FLH with that in enhanced scan method, an average improvement of 71% is observed. As the logic depth decreases for better performance in sequential circuit, the proposed FLH scheme will show much less delay overhead as compared to enhanced scan.

Table III shows comparison of power in the normal mode of operation. Significant power savings are observed for all the benchmark circuits. In fact, for most benchmark circuits the power dissipations of the FLH circuits are close to the power dissipations of the original circuits. This is because in the proposed technique, the supply gating transistors do not switch in the normal mode. The only source of power overhead is due to switching of the minimum-sized inverters and the diffusion capacitance added to the outputs of the first level gates due to the transmission gate. It is interesting to notice that for a large benchmark circuit such as s13207, the power of the FLH circuit is even less than the power of the original circuit. This can be attributed to two facts: a) the sleep transistor results in active leakage reduction (due to stacking [START_REF] Roy | Leakage current mechanisms and leakage reduction techniques in deep-submicrometer CMOS circuits[END_REF]) for the idle gates b) reduced number of switching at the outputs of first level gates compared to the number of switching at scan flipflop outputs. For a large circuit, at each time instant, there are many idle first level gates during scan shifting. Saving leakage in those gates, hence, reduces overall power. FLH shows an average reduction of 44% overall circuit power compared to the enhanced scan method. However, the percentage reduction in power overhead compared to the enhanced scan is 90% on an average. Larger-sized sleep transistors for gates in the critical path can be used to further reduce the delay penalty. It increases the area overhead but does not affect the switching power of the gates. However, upsizing the hold latch and MUX does In a conventional scan-based circuit, combinational logic suffers from redundant switching in response to changing scan values during the entire period of scan-shifting. Gerstendrfer and Wunderlich [START_REF] Gerstendrfer | Minimized Power Consumption for Scan-based BIST[END_REF] have shown that on an average about 78% of energy in the test mode can be saved by preventing redundant switching in combinational logic by using blocking gates at the output of scan flip-flops. It is worth noting that an enhanced scan flip-flop embeds a blocking gate, and thus, isolates combinational logic from activity in the scan register during shift operation. Although FLH does not insert any blocking logic at the output of scan flip-flops, supply gating at the first level logic gates holds the previous output state of the gate and prevents propagation of switching. FLH is, thus, equally effective in completely eliminating redundant switching power in the combinational logic.

The proposed technique can be easily applied to scan-based test-per-scan BIST (Built-In Self Test) [START_REF] Bushnell | Essentials of Electronic Testing for Digital, Memory, and Mixed-Signal VLSI Circuits[END_REF] circuits. A circuit designed with BIST has weighted random pattern generator and output response analyzer built into the circuit. The patterns are applied to both primary inputs and scan cells. If test patterns are applied to the primary inputs serially, as in the scan chain, FLH technique proposed for scan path can be equally used to the fanout logic gates for the primary inputs to provide a transition. Scan insertion with FLH can be easily automated by test synthesis tools by inserting the gating logic of FLH for each scan cell to each of its first level fanout gates. It can be noted that additional logic for FLH (gating transistors and the embedded latch) does not require to modify a logic gate. Hence, it is not necessary to change the standard cell library in case of a cell-based design. However, integrating the gating logic into the layout of a standard-cell element allows more efficient routing and hence, can reduce the area overhead in physical implementation.

V. FURTHER REDUCTION OF AREA/POWER OVERHEAD Transistor downsizing can be applied to all the methods, including FLH, to reduce the area and power overhead. But narrowing transistor width usually trades off circuit performance by affecting critical path delay. FLH, however, has potential to reduce the area penalty further without compromising delay. We designed a low-complexity local fanout reduction algorithm which targets minimization of first level gates under constraint on critical path time. The algorithm is based on identifying the scan flip flops with higher fanouts and then adding two inverters in cascade between output of the scan flip-flops and their fanout gates. No inverter is added in the critical path of the circuits and maximum circuit delay is kept unaltered. We then try to re-synthesize the second inverter with its fanout gates to reduce area penalty due to the additional inverters. If a scan flip-flop already has an inverter connected to it, we do not need the second inverter. The algorithm utilizes the timing slack available in the non-critical paths. We implemented the algorithm applied it on a set of benchmarks with higher number of scan flip-flops. The result is presented in Table IV. It can be observed that we can get as high as 37% improvement (with an average of 18%) in area overhead with fanout optimization under delay constraint. The power in normal mode remains comparable. It is interesting to note that, for some cases (e.g. s5378), the number of first level gates becomes even lower than the number of scan flip-slops. This is because for these benchmarks, most of the high-fanout scan flip-flops have largely reduced fanouts (1 or 2) after the fanout optimization, while overlap among the fanout cones of the other flip-flops is maintained. It results in total number of first level gates lower than the number of flip-flops.

VI. CONCLUSIONS This paper presents First Level Hold (FLH), a novel technique based on supply gating, as a low-cost alternative to

Fig. 1 .

 1 Fig. 1. (a) Scan architecture with additional logic for delay fault test; (b) Holding logic

Fig. 3 .

 3 Fig. 3. Proposed supply gating scheme with output hold capability

Fig. 5 .

 5 Fig. 5. (a) Modified scan architecture with holding logic at first level gates; (b) Timing diagram for delay testing with FLH

Fig. 5 Fig. 6 .

 56 Fig. 5 shows the proposed FLH technique applied to a general sequential circuit. FLH does not require any extra timing control signals. It only uses the test control (TC) signal, that is used in conventional scan-based testing, and its complement ( T C). Enhanced scan method requires two control signals, TC and HOLD. The timing diagram during test application is shown in Fig. 5 (b). During scan-in, TC is set to '0' to prevent activity in the scan chain affecting the combinational circuit. Once scan-shifting is completed for the

  IV. TEST CONSIDERATIONS Fault coverage and fault models remain unaffected with the insertion of FLH logic. During normal mode of operation the gating transistors are turned ON, hence the conventional stuck-at fault model, transition and path delay fault models remain valid. FLH does not require any change in test vectors generated by ATPG tools. Hence, fault coverage for enhanced scan and FLH for a given test set remain unchanged.

  A Novel Low-overhead Delay Testing Technique for Arbitrary Two-Pattern Test Application Swarup Bhunia, Hamid Mahmoodi, Arijit Raychowdhury, and Kaushik Roy School of Electrical and Computer Engineering, Purdue University, IN 47907, USA {bhunias, mahmoodi, araycho, kaushik}ecn.purdue.edu

TABLE IV COMPARISON

 IV OF AREA, POWER IN NORMAL MODE BEFORE AND AFTER scan approach of delay fault testing. The proposed technique does not affect test generation, test application and fault coverage. FLH does not require any extra test control signal. It maintains the power-saving advantage of the enhanced scan method in test mode by suppressing activity in the combinational logic during scan shifting. FLH is more suitable for high-speed applications since it induces significantly less delay in critical path of a circuit. At the same time, it provides the benefit of lower overhead in die-area and power consumption in normal mode of circuit operation.

			FANOUT OPTIMIZATION
	Ckt.	# FFs	Fanout	Area	Combinational
					overhead	power (µW)
			(before)	(after)	improv.	(before)	(after)
	s838	32	96	36	36.86	21.66	19.01
	s1196	18	23	18	10.05	37.82	37.26
	s1423	74	160	86	13.82	61.93	68.81
	s5378	179	280	163	11.43	120.96	126.30
	s9234	211	445	199	28.98	145.99	154.62
	s13207	638	729	589	2.09	322.69	324.73
	s15850	534	837	519	14.31	343.32	336.34
	s35932	1728	2692	1728	26.51	1080.98 1040.12

enhanced

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)

ACKNOWLEDGMENT

This research was funded in part by MARCO GSRC and by National Science Foundation (NSF).


Jianjiang Ceng

Manuel Hohenauer

Rainer Leupers

Gerd Ascheid

Heinrich Meyr

Gunnar Braun

C Compiler Retargeting Based on Instruction Semantics Models

published or not. The documents may come

. Introduction

With the increasing industrial acceptance of ASIPs as SoC building blocks, retargetable C compilers have become important tools in the system-level design flow. For instance, the embedded processor design tool suites from CoWare, Target Compiler Technologies, and Tensilica incorporate retargetable compilers that can be quickly adapted to varying target architectures.

In contrast to traditional compilers that target only a single processor architecture, retargetable compilers can generate code for different targets based on an external, editable processor model. They serve two main purposes in the design flow. First, they are required in processor architecture exploration. In this phase, the initial ASIP architecture gets fine-tuned for the intended applications which are mostly given in the form of C code. Second, retargetable compilers (possibly enhanced with target-specific code optimization techniques) can be used to quickly generate production compilers needed by the ASIP end users for software development.

In the domain of compiler construction for generalpurpose processors, retargetable compilation has been a subject of research for quite some time. Systems like GCC [START_REF]Free Software Foundation GCC[END_REF] or LCC [START_REF] Fraser | A Retargetable C Compiler : Design and Implementation[END_REF] have been successfully used for various CISC and RISC processors. In the context of ASIP design, where a tight link to hardware and SoC design flow is required, two mainstream approaches to retargetable compilation can be identified. The first one builds on a predefined, yet configurable processor core (e.g. Xtensa, ARCtangent) that can be optimized by the user via addition of custom machine instructions. In this case, semi-custom compiler systems (such as a modified GCC) can be used, and retargeting is implemented by making new instructions available to the compiler in the form of intrinsics. While this approach offers the advantage of reusing well-proven compiler tools, it restricts the flexibility of ASIPs and requires manual (and non-portable) C source code modifications.

The second approach is based on the paradigm of architecture description languages (ADLs) that permit highlevel (i.e. beyond RTL) modeling of processors for early design phases such as architecture exploration and systemlevel verification. The challenge in retargetable compilation based on ADL models, however, is the large variety of potential target architectures, which is essentially only limited by ADL's capabilities. The ADL approach permits very high flexibility in ASIP design, but demands advanced techniques for efficient compiler retargeting.

In this paper, we describe a novel technique of compiler retargeting for LISA 2.0, a C/C++ based industrial ADL [3]. The proposed technique allows for a high degree of automation by extracting the core part of the compiler backend (the code selector that maps intermediate code to assembly) from the ADL model largely without user interaction. In this way, a high speedup in compiler generation is achieved, that eventually contributes to a more efficient ASIP design flow. Our technique is based on the instruction semantics information in LISA 2.0 models which provides a higher abstraction view of instruction behaviors than C/C++ descriptions.

The remainder of this paper is structured as follows. In section 2, we provide a survey of related works. Section 3 gives a brief system overview, while section 4 summarizes LISA's instruction semantics modelling concept. The focus of this paper is the automatic generation of code selectors. Section 5 this described in detail. The results of two case studies are given in section 6, and section 7 gives concluding remarks.

. Related work

Early retargetable compilers for ASIPs include FlexWare [START_REF] Liem | Industrial Experience Using Rule-driven Retargetable Code Generation for Multimedia Applications[END_REF], SPAM [START_REF] Araujo | Code Generation Algorithms for Digital Signal Processors[END_REF], and RECORD [START_REF] Leupers | Retargetable Generation of Code Selectors from HDL Processor Models[END_REF]. The last one builds on the MIMOLA modeling language and extracts code selector descriptions that can be further processed by iburg [START_REF] Fraser | Engineering a Simple, Efficient Code Generator Generator[END_REF] to generate a code selector. The range of possible target architectures is limited, though, mainly due to the use of specialized processor modeling formalisms.

ASIP design systems using dedicated ADLs include AVIV [START_REF] Hanono | Instruction Selection, Resource Allocation, and Scheduling in the AVIV Retargetable Code Generator[END_REF], CHESS [START_REF] Praet | A Graph Based Processor Model for Retargetable Code Generation[END_REF], Mescal [START_REF] Qin | Flexible and Formal Modeling of Microprocessors with Application to Retargetable Simulation[END_REF], Expression [START_REF] Halambi | EXPRESSION: A Language for Architecture Exploration through Compiler/Simulator Retargetability. Design Automation & Test in Europe[END_REF], ASIPMeister [START_REF] Kobayashi | Compiler Generation in PEAS-III: an ASIP Development System[END_REF], and ArchC [START_REF] Viana | Exploring Memory Hierarchy with ArchC[END_REF], some of which include retargetable C compilers. Several of these systems focus on a specific class of ASIP architectures, e.g. DSP or VLIW, while others limit flexibility through a predefined library of processor components. Such kind of constraints is introduced by the fact that different processor development tools can hardly share the same description of instructions. For example, the generation of instruction set simulators requires a very detailed behavior description, while C compiler generation needs a clear description of instruction semantics without any structural or internal behavioral detail. So far, such contradictory demands are solved by introducing specific ADL constructs which provide information for the generation of different tools. For example, in the Expression ADL, there exist dedicated operation mapping sections that guide the code selector generation, while simulator generation is driven by other language constructs.

nML [START_REF] Praet | A Graph Based Processor Model for Retargetable Code Generation[END_REF] and AXYS LISA [14] both have a hierarchical structure of descriptions, similar to the LISA 2.0. However, few information about their compiler generation is available. We have described an earlier version of the LISA 2.0 based retargetable compiler framework in [START_REF] Hohenauer | A Methodology and Tool Suite for C Compiler Generation from ADL Processor Models[END_REF]. Though most of the compiler components can be generated automatically, the code selector generation still requires some manual efforts. The technique proposed in this paper aims to further automate the code selector description generation.

System overview

C compiler generation is part of the LISA ASIP design flow sketched in fig. 1. A retargetable C compiler is integrated with CoWare's LISATek Processor Designer tool suite [3] that supports ASIP design by generating software development tools, synthesizable HDL models, and co-simulation interfaces from the LISA 2.0 processor models. With this approach, ASIP design is simplified due to a high degree of automation and the fact that just one processor model is needed for the entire design flow.

Figure 1. LISA 2.0 Based Design Flow

The main challenge of the compiler retargeting in this design flow is adaptation of the compiler backend (or code generator). A backend generally has a code selector, a register allocator, and an instruction scheduler. We use the CoSy system from ACE [START_REF]Associated Compiler Experts[END_REF] as compiler development framework. The CoSy system contains a complete C/C++ frontend, a set of processor independent optimization engines and a retargetable compiler backend. The register allocator provided by the CoSy needs the names of allocatable registers to generate a target specific register allocator. In [START_REF] Hohenauer | A Methodology and Tool Suite for C Compiler Generation from ADL Processor Models[END_REF], works have been done to extract these information from LISA 2.0 models. We implemented our own instruction scheduler. Techniques, which are used to automatically generate scheduler descriptions, are described in [START_REF] Wahlen | Instruction Scheduler Generation for Retargetable Compilation[END_REF]. The code selector generation in our previous work relied on a semi-automatic GUI based approach. Based on a LISA 2.0 model, compiler designers can use a GUI to specify code selector's mapping rules. According to our experience, this part of work is the most time consuming part in the whole retargeting process. Moreover, for a designer without enough compiler knowledge, it is difficult to determine if the created rules are complete for a working C compiler or not. Hence, further automation of the code selector generation is desired.

Instruction semantics

The LISA 2.0 processor models comprise resource specifications (e.g. registers, memories, and pipelines) and operations. Operations contain machine descriptions from different views such as assembly syntax, pipeline timing, binary encoding, and behavior. In the standard LISA 2.0 behavior view of instructions, plain C/C++ code is used for sake of highest flexibility and simulation speed. Since the same behavior may be described with numerous syntactic variances in C/C++, it is generally not possible to accurately extract the high-level semantic meaning of the instructions automatically from it. Therefore, we added a semantics view of operations that captures behavior at a higher abstraction level [START_REF] Ceng | Modeling Instruction Semantics in ADL Processor Descriptions for C Compiler Retargeting[END_REF].

Our approach is to capture instruction semantics explicitly by using a limited and precisely defined set of microoperations, similar to MIMOLA. Each micro-operation describes a computation on the processor resources that can typically be executed by a data path component. For example, the _ADD operator in fig. 2 represents an addition operation. The side effects of instructions are captured by annotation besides the micro-operations. The _C and _Z in the example indicate that carry flag and zero flag are affected by the calculation. Rs1 and Rs2 are input operands. The right arrow denotes Rd as the destination of the result. As mentioned before, LISA 2.0 processor models have a hierarchical structure. Rd, Rs1 and Rs2 in this example all refer to the reg_32 operation. Then, the semantics of the reg_32 operation defines those of the operands. In LISA, a concise semantics description is achieved through using such a structure.

OPERATION ADD IN pipe.EX{ DECLARE{ GROUP Rs1, Rs2, Rd = { reg_32 }; } ... SEMANTICS{ _ADD|_C, _Z|(Rs1, Rs2)->Rd; } }

Figure 2. LISA Operation with Semantics

The semantics view of LISA 2.0 ignores all structural details like pipelining, and provides a clean and unambiguous instruction behavior description. This can be used for several purposes. In [START_REF] Braun | A Novel Approach for Flexible and Consistent ADL-driven ASIP Design[END_REF], we have presented a technique for synthesizing instruction-set simulators from the instruction semantics. Since the semantics description is much simpler than the C/C++ description, this helps accelerating the modelling process in early architecture exploration when the concrete micro-architecture is not fully determined. Another important use of the semantics is compiler generation, especially code selector generation.

Code-selector description generation

The code selector generator in CoSy uses the dynamic programming tree matching algorithm [START_REF] Aho | Code generation using tree matching and dynamic pogramming[END_REF]. It requires a tree grammar description of the target instruction set. The same approach is used in other code selector generators, e.g. iburg [START_REF] Fraser | Engineering a Simple, Efficient Code Generator Generator[END_REF]. A tree grammar G = (N, T, P, S) consists of finite sets N and T of nonterminal and terminal symbols, respectively, as well as a set P of mapping rules and a start symbol S ∈ N [START_REF] Fraser | Engineering a Simple, Efficient Code Generator Generator[END_REF]. The terminals T essentially describe the operations of the source language (e.g. C) and thus are target machine independent. Likewise, the start symbol S requires no special retargeting effort. Only the nonterminals, N , and the rules, P , need to be adapted to the target machine. N basically reflects available registers, memories, and addressing modes, while P defines how source language operations are implemented by the target instructions. Each mapping rule in P has the form of a tree pattern that may serve to cover a data-flow graph fragment during code selection. In the following sections, we describe how N and P are automatically generated from instruction semantics information.

Nonterminal generation

In tree grammar descriptions, nonterminals act as temporary variables connecting different grammar rules. For code selectors, they represent temporary storage locations like registers and memories that the compiler can use. Depending on the type of locations, nonterminals can be divided into four categories: register nonterminals representing the compiler usable registers, immediate nonterminals carrying the constant values that can be directly encoded in instruction codings, addressing mode nonterminals encapsulating the addressing modes, and condition nonterminals which are normally flag registers that are affected by different instructions.

In LISA 2.0 processor models, accesses to these storage location or processor resources are normally described in a wrapper operation, like the operation reg_32 in fig.

3. In the instruction semantics description a set of microoperators are provided to capture the semantics of the wrappers. The _REGI operator in the example stands for a register access. Its operand GPR is the name of the LISA resource that is used as register bank. The index of the accessed register is given by index, a LISA label whose value is determined by the instruction coding. Another important information, the bit-width of the registers, is specified with the notation <0,32> which means the register is 32 bit wide and the least significant bit is bit 0. Given this operation, a register nonterminal is generated, which can hold any type of data when its size fits.

OPERATION reg_32{

DECLARE{ LABEL index; } CODING { value=0bx [START_REF] Liem | Industrial Experience Using Rule-driven Retargetable Code Generation for Multimedia Applications[END_REF] } SEMANTICS { _REGI(GPR[index])<0,32>; } ... }

Figure 3. Register Wrapper Operation

Similar to the register nonterminals, the generation of the immediate and the addressing mode nonterminals is based on two related micro-operators, _IMMI and _INDIR. Once these micro-operators are detected, the generator will create the corresponding nonterminals. Generally, the condition nonterminals represent the flag registers; their existence then depends on the use of four predefined flags, carry (_C), zero (_Z), overflow (_O), and negative (_N) flags. For example, the semantics statement in fig. 2 has the side effects of writing the carry and zero flag. Accordingly, a condition nonterminal is generated. These four kinds of nonterminals are processor specific elements in the mapping rules. They are created before the generation of the mapping rules.

Mapping Rule Generation

In general a mapping rule (a.k.a. tree rewriting rule) consists of three parts: a tree pattern, the result of the rule which is normally a nonterminal, and one or several associated machine instructions. The tree pattern represents a C level computation which can be performed by the processor. The input operand(s) of the computation is(are) also nonterminals. To generate mapping rules for a working code selector description, two questions need to be answered. The first one is, what tree patterns are needed to cover the complete set of C level operations for the target processor, and the second is, how the C level operations are mapped to the machine instructions.

Basic Rules

A complete code selector description must cover all the operations that the C language might need. Since the C language does not change, the C level operations needed to be covered by a code selector are actually fixed. This makes it possible that a set of mapping rule templates can be prepared without the knowledge of a target processor. We created a set of such templates, and call them basic rules. Table 1 lists a basic rule and a CoSy mapping rule side by side. The mirPlus operator in both rules is a C level addition operation defined in CoSy. There are two major differences between basic rules and CoSy mapping rules. First, the operands in the tree patterns of the basic rules are placeholders, like a, b, and c, instead of nonterminals nt_reg used in CoSy rules. From a basic rule, it is very easy to create tree patterns fitting the target processor by replacing the placeholders with nonterminals generated in the previous step. In the generator, the basic rules needed by a complete coverage of C operations are put together in a so called basic library. It is used by the code selector generation for all target architectures.

Table 1. Basic Rule and CoSy Rule

The second major difference between basic rules and CoSy rules is that a CoSy rule has assembly instructions associated, e.g. the fprintf function prints an assembly instruction to the output file, while a basic rule has one or several semantics statements. In the generation procedure, when the suitable tree patterns are available, the next task is to find instructions that can perform the C operations in the tree pattern. This requires the semantics linked with the basic rules. The generator searches the instruction semantics described in the LISA model and selects the suitable instruction based on the result of the matching of the semantics.

In principle, most of the C operations can be covered by single instructions, which is the simplest case. We call this one-to-one mapping: one C operation maps to one machine instruction. However, ASIP designers always try to make the architecture as simple as possible, only if the application can be executed efficiently. Rarely used instructions might be left out of the design, but they are needed by a complete C compiler. One-to-many mapping is then used, which implements a C-level operation with a sequence of instructions. Moreover, the ASIP designers not only simplify the instruction set but also add instructions for program hot spots. These instructions accelerate the program execution by performing many C-level operations at once. To utilize them in a compiler, many-to-one mapping rules are needed. The following sections describe how the instructions are selected for these three kinds of mapping rules with the help of instruction semantics information.

One-to-one mapping

As the simplest mapping method of all, one-to-one mapping is first used by the generator to find suitable instructions. The semantics statements of the basic rules are compared with the instruction semantics in the LISA model. Since some side effects in a real instruction might not be interesting to a C compiler, a successful one-to-one mapping does not require two totally identical semantics patterns. For example, suppose the generator tries to find a suitable instruction for the basic rule in table 1, and the semantics of the LISA operation depicted in fig. 2 is examined. Because the writing to carry and zero flag does not influence the result of an arithmetic addition in C level, the side effects in the instruction semantics are then ignored by the generator, and the instruction is chosen for the tree pattern generated from the basic rule. Eventually, a complete one-to-one mapping rule, in the form of the CoSy rule in table 1, is created.

Such adaptation in the one-to-one mapping can only compromise those effects not affecting the calculation results. Micro-operators still must be exactly the same for both compared semantics. If, due to the simplification made by the designers, a processor does not have the instruction to provide a one-to-one mapping, one-to-many mapping is then used.

One-to-many mapping

In one-to-one mapping, the semantics statements in the basic rules are used by the generator to find a suitable instruction. However, if a processor does not have one instruction which can complete the calculation or operation, the generator needs to find a sequence of instructions, i.e. one-to-many mapping. For this purpose, it is important for the generator to know how the semantics statement in a basic rule can be implemented through a set of other semantics statements without affecting the result of computation. This is achieved by using the semantics transformations.

A semantics transformation specifies a sequence of semantics statements which together performs the same computation carried out by the original statement. An example can be found in fig. 4. The _NEG micro-operator represents a two's complement negation. The specified transformation provides a mathematically equivalent solution to do the negation operation. _NOT is the one's complement micro-operator. A two's complement can be done by doing a one's complement and plus one. With this transformation available, if the generator fails to find an instruction doing negation, it will then look for two instructions to do the complement and the addition operations sequentially. In principle this approach can be used to lower any operation, only if an equivalent transformation exists and can be expressed in the form of semantics statements. In the LISA compiler generator, a set of commonly used transformations are provided by default in a so called transformation library. Because of the variance of different instructions implemented in various architectures, it is not possible to specify a transformation library that can fit every ASIP under design. We provide the transformation library in form of a text file, so that if a C operation needs to be implemented with a very specific sequence of instructions the designer can create a custom transformation himself.

Many-to-one mapping

Many-to-one mapping is especially important for ASIP design, because ASIPs heavily employ instructions that perform composite operations to accelerate application execution. However, since the designers can implement arbitrary combinations of operations in one instruction, it is difficult for the generator to prepare the tree patterns without knowing what the instructions do. Our approach is analyzing the instruction semantics in the LISA model and try to create a tree pattern with several C level operations out of it.

Take the MAC (Multiply and Accumulate) instruction, which is a commonly used composite operation, as an example. Suppose the ASIP designer describes its semantics with the semantics statement in fig. 5. Two micro-operators are used, _ADD and _MULII. _MULII is a signed integer multiplication. The generator has the knowledge of the mapping between the semantics micro-operators and the CoSy tree pattern nodes. With this knowledge, it can then create a corresponding tree pattern from the instruction semantics without user interaction. In the example, mirPlus is the CoSy tree pattern node corresponding to the micro-operator _ADD, and mirMult maps to the _MULII operator. If the source code contains a concatenated multiply and addition operation, this many-to-one mapping rule will tell the code selector to use the MAC instruction instead of two separate multiply and addition instructions.

Semantics Intrinsics

Generally, the many-to-one mapping works for the arithmetic instructions whose semantics can be described with a chain of micro-operations like in the example 5. However, it is not applicable to those instructions performing multiple data assignments, e.g. SIMD (Single Instruction Multiple Data) instructions. Since the tree matching algorithm covers one sub-tree at a time, it is not possible to do SIMD instruction mapping without changing the internal intermediate representation of the source code. Another approach to utilize such instructions is using compiler known functions (a.k.a compiler intrinsics) which are directly translated into corresponding instructions by a compiler. For this, we use semantics intrinsics to describe those instructions who have complex semantics that cannot be used by tree matchers, like SIMD instructions. In LISA 2.0 models, the semantics intrinsics are used as customer micro-operators, e.g. the "_DADD" in the example 6. For the generator, the real semantics of the intrinsics is no more important, since creating corresponding function definition is a straightforward one-to-one translation.

Experimental results

To examine the efficiency of our compiler generator, we have done case studies using the ST220 and PP32 processors as target architectures, the same as in our previous work [START_REF] Hohenauer | A Methodology and Tool Suite for C Compiler Generation from ADL Processor Models[END_REF]. Since the instruction semantics description of LISA 2.0 is quite straight forward, it is very easy for a LISA model developer to extend a model with semantics. For our two driver architectures, on average, it took 2 man weeks to develop the semantics models [START_REF] Ceng | Modeling Instruction Semantics in ADL Processor Descriptions for C Compiler Retargeting[END_REF]. Based on them, most of the mapping rules needed by a C compiler are automatically generated. The CPU time used by the generator is negligible. However, both processors need a few custom transformations to cover some C operations. Table 2 provides the statistics of the generated rules for both processors and the number of custom transformations.

The custom transformations of both processors are mainly used to cover operations which cannot be executed with one machine instruction such as the signed/unsigned division and the modulo operation. Several standard library functions are invoked by the transformations to accomplish such operations. For ST220, a transforma-tion is used to perform the one's complement operation with a ST220 specific instruction that does bitwise not and or (NOR) at once. PP32 also has some very specific transformations. For example, the load of a 32 bit immediate value is done with two instructions. The first one loads the higher half of the value into the target register and left shift the result by 16 bits. The second one adds the lower 16 bits to the target register.

one-to-one one-to-many many-to-one user trans.

Table 2. Rule Statistics of ST220 & PP32

The generated compilers have been verified using the Supertest compiler validation test suite of the CoSy system. The code quality is examined against our previous work in [START_REF] Hohenauer | A Methodology and Tool Suite for C Compiler Generation from ADL Processor Models[END_REF]. The results are pretty close. The semantics generated compilers have an average of 5% cycle count overhead, and the code size is about 18% larger. These overheads are mainly due to the fact that the basic rules used for the mapping rule generation are designed to be conservative, so that they can be used by all architectures. The manually crafted code selector has a more aggressive instruction selection policy, e.g. the integral promotion for some of the C arithmetic operators was omitted with the assumption that the values in the registers are always correctly sign or zero extended. In general, the code quality produced by the generated compiler still cannot compete with the handwritten highly optimized compiler. However, the major focus of this work is to push the automation of compiler generation to its edge.

Conclusions

In this paper, we have presented a novel approach to automatically generate C compilers from the LISA instruction semantics models. Though using a semantics description introduces certain redundancies, they are kept minimal and local in the model. Three different mapping rule generation methods were developed. With them, compiler designers only need to take care of architecture specific features of their processors. The generator will do most of the work automatically. Moreover, since the semantics actually describes the instruction behavior, it is much easier for the ASIP designers to use them. Less compiler knowledge is required to build a compiler using our approach. A user extensible library is employed in our generator, so that flexibility is kept. Two contemporary processors were tested, and both present promising results. However, the code quality of both compilers can only be considered as results from outof-box compilers. To improve it, further code optimization techniques are needed. In future, we will focus our work on providing ASIP designers a retargetable interface to the compiler, so that they can develop specific optimization for ASIP code generation.

  COSYIR mirPlus(a,b)→c; RULE o:mirPlus(a:nt reg,b:nt reg)→c:nt reg; PATTERN {_ADD(a,b)→c;} EMIT { fprintf(outfile, "add %s=%s, %s", c, a, b); }

Figure 4 .

 4 Figure 4. One-to-many Mapping

Figure 5 .

 5 Figure 5. Many-to-one Mapping

"

  Figure 6. Semantics Intrinsics

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)