Loïc Lagadec
email: loic.lagadec@univ-brest.fr

Bernard Pottier

Alix Poungou Lester

A layered methodology for fast deployment of new technologies

Few efforts have been reported in building computing architectures out of nanodevices by contrast with the extensive research focusing on nanodevices fabrication aspects. Addressing mass market and reducing time-to-market appear now as key issues. We propose a layered approach, taking advantage of FPGAs good characteristics, to offer the promise of fast deployment of new technologies.

I. INTRODUCTION

A variety of nanodevice technologies have been demonstrated. While there are many practical challenges still remaining, a key issue is now "How do we enable fast deployment of new technologies to mass market?"

Despite research projects will go on offering new computing solutions to implement applications, it remains difficult to assess the real interest for final products, as well as to produce some usable development environment for these products.

Applying a methodology similar to the interpreters or the virtual machines met in the early years of microprocessors, can lead to similar benefits in terms of quick availability on new architectures. The original idea was to define portable machines description in order to isolate the compiler, tools and OS from the fast evolution of real architectures. These portable machines had simple specifications so that they could effectively be implemented on a target.

In the case of nano technologies, we propose a CAD open framework that will enable the following porting flow:

• Layer 0, target technology : modeled as tiles, connectivities, logic, switching elements, • Layer 1, gate array/FPGA : model described on the target technology, • Layer 2, application : model described on the Layer 1 model, This flow only makes sense if the CAD algorithms allowing to implement logic functions, to place and route, to floor plan, are easily available: L0 to L1 to implement the micro architecture, L1 to L2 to implement the application. The answer we propose is to use interpretative and generic techniques for the CAD tools.

This paper focuses on implementing a FPGA on a nano-tube technology called NASIC. This implementation is a tiling of cells that own logic and routing capabilities. Once the FPGA is implemented it can act as a L1 target to port L2 applications and to investigate costs and performances.

In the practical case of NASIC the primitives are the cell Look Up Table (LUT), the routing switch, and a register assembled together following the technology rules.

Given an available L1, an estimated time to build up an L0 is within the order of 6 man-months. As the model is parametric, it is easy to vary the L0 definition on details such as tile sizes, routing capabilities ...

II. NANOSCALE FPGA

A. Nanoscale FPGA in NASIC 1) Nanodevices: The most mature among all knownnanoelectronic devices are the carbon nano tubes [START_REF] White | Helical and rotational symmetry of nanoscale graphitic tubules[END_REF], [START_REF] Chiu | Towards carbon nanotube-based molecular electronics[END_REF] and silicon nano wires [START_REF] Cui | Doping and electrical transport in silicon nanowires[END_REF]. A large part of research in nano electronics entirely focuses on these two technologies due to their CMOS similarity. These filiform technologies are synthesized with few nanometer in diameter and micrometer in length. they can act as the metallic wires, semiconductors or insulating materials [START_REF] Mintmire | Are fullerene tubes metallic?[END_REF], [START_REF] Saito | Electronic structure of graphene tubules based-on c 60[END_REF], [START_REF] Dekker | Carbon nanotubes as molecular quantum wires[END_REF] and are used to fabricate mechanic switches [START_REF] Kueckes | Carbon nanotube based nonvolatile random access memory for molecular computing[END_REF].

2) NASICs technology: The Nanoscale Application-Specific Integrated Circuits (NASICs) concept and architectures have been developed at UMAss by Moritz [START_REF] Moritz | Latching on the wire and pipelining in nanoscale designs[END_REF]. NASICs rely on nano-arrays of orthogonally crossed nanowires, surrounded by microwires that are used to carry on the control signals.

The NASIC circuits operate based on a temporary storage of data on a nanowire, each nanowire having a transistor at both ends connected to a clock phase. The figure 1 shows a simple realization of the AND function with such a technology. The grid is built out of two orthogonal plans of nanowires with different doping: the red nanowires are p-doped and the blue nanowires are n-doped. Each junction of two nanowires can contain active nanodevices (n-FET or p-FET transistors) or be detached. In this design, signals are expressed in both their original form and their complementary form.

The logic implementation is based on the PLA model, but as the complementary signals must be generated, additional lines appear (in fig. 1, only the bottom line is required for a classical implementation). The product terms of the function are realized with the p-doped nanodevices (left part of the figure) and the sum of the product terms are coupled with the n-doped nanodevices (right part of the figure).

3) NASICs circuit and design rules: The NASIC approach has been demonstrated through implementing a WIre Streaming Processor (WISP) [START_REF] Moritz | Latching on the wire and pipelining in nanoscale designs[END_REF]. WISP is a simple but complete In addition to offering a demonstrator of a computing architecture based on nanodevices, WISP has mainly been a test-bed for different strategies to be applied when designing computing architectures, that can be wide spread reused.

4) Layered adapter: A preliminary work has targeted the definition of a virtual FPGA architecture [START_REF] Lagadec | Placing, routing and editing virtuals fpgas[END_REF], coupled with some exploration tools. The implementation flow of an application follows bottom-up approach i.e. a CMOS technology, programming support (physical FPGAs) and a computation model (virtual FPGAs) as shown in the figure 2.

The virtual FPGA concept favors portability of applications from a FPGA family to another at the expense of some performances loss, hence some domain-specific functionalities are also integrated into the virtual FPGAs in order to minimize these costs.

The know-how developed in this scope can benefit to addressing new target technologies such as the NASICs, assuming a layered scheme can fit to. In particular, realizing an FPGA (computation model) based on a programming support (NASIC tiles) implemented on a technology (grid of carbon nano tubes or silicon nanowires) conforms to the proposed layered approach.

5) Reconfigurable architectures: Reconfigurable architectures can be seen as a compute and configuration plans stacking up. The configuration plan stores the behavior of the architecture (switch activation, logic functions, etc. . . ) whereas the compute plan implements the application. Hence, migrating from a circuit to a reconfigurable circuit requires to implement configuration storage mechanisms. These directly benefit from the WISP Register File design.

B. NFPGA architecture

The FPGA (L1 architecture) acting as a demonstrator is wilfully simple but still owns parametric characteristic to favor prospection. The FPGA exhibits regular tiling of cells. The cells are made up from a short list of basic elements. Hence, designing a FPGA relies on design rules for elements composition and on a circuit level description of these elements.

a) Architecture composition: The L1 tile is made up of a LUT and neighbor-to-neighbor directional routing resources.

As illustrated in the figure 3, the schematic view of the NFPGA cell consists of two parts: a LUT which regroups a decoder and RAM memories, and routing representing the input-output multiplexers. • Look-Up Table A LUT (figure 5) contains 2 N inputs coming from the address decoder and 2 * K bits of data to be stored. The LUT outputs 2 * K bits. The LUT inputs are in the configuration plan whereas the LUT's outputs are back in the compute plan. • Routing configuration The programmable interconnect relies on multiplexers. The routing configuration drives these multiplexers be-havior (figure 6) by providing some signals to the switch block. Note that all of the outputs must be concurrently read in this case (2 × 2 signals per each of the 4 multiplexers) by contrast with the LUT's outputs that can be seen as picking up K signals out of 2 N .

III. TOOLS

A. L0 to L1 model 1) L0 model: The L0 model is an extension of the Madeo framework [START_REF] Lagadec | Abstraction and modélisation et outils de CAO pour les architectures reconfigurables[END_REF]. The Madeo framework originally applied to FPGAs, with technical realizations over JBits/Virtex or some prospective architectures such as LPPGA [START_REF] Varghese | The design of a low energy fpga[END_REF]. Hardware elements are described with their geometric properties and tiling. This description relies on the Madeo HDL, as shown in table I.

The Madeo framework includes a set of back end tools that apply to any L0 assuming it can be described using Madeo HDL : placer router, editor, user interfaces, etc. . . Hence by enforcing new technologies fit within the Madeo HDL/model framework (see table II), the back end is compatible.

2) L1 model: The L1 model describes the NFPGA as an application to be implemented over the L0 level. L1 appears as a regular tiling of modules. the modules appear as a graph of logic descriptions. As an example, the nano grid f of table III). From a practical point of view, the NFPGA is represented by a 2-dimension matrix where the cells contain, each one, a K-LUT and 4xN 4-to-1 multiplexers, where N is the width of the channels. The structure model of the NPGFA cell is extensible due to the variability of both the channel width and both the LUT size. The cell complexity strongly depends on these two parameters. ) " end of NAMED " PRODUCE NanoGrid

) " END of PRODUCE " CATEGORY ENS07 ) "END of CATEGORY"

TABLE II PARTIAL L0 DESCRIPTION OF NASICS (NANOARRAY)

.i 22 .o 2 -------0000 01 ------0-001 01 -----0--010 01 ----0---011 01 ---0----100 01 --0-----101 01 -0------110 01 0-------111 01 -------1000 10 ------1-001 10 -----1--010 10 ----1---011 10 ---1----100 10 --1-----101 10 -1------110 10 1-------111 10 .e The structure of the multiplexers is simplified by the use of the disjoint routing.

We need to consider a regular tiling mechanism for the matrix, agglomerate structuration mechanism for the cell and the basic elements. In each cell, there are N output multiplexers for feeding a LUT, K input multiplexers and a K-LUT.

B. Synthesis

Using the layouts of the FPGA-basic elements designed in the NASIC technology, the NASIC implementation of the aforementioned parts can be realized by combining the topologies of the elements composing each part according to the Moritz-design rules.

1) Basic element synthesis:

The first version of the NFPGA synthesis was focused on the synthesis at the first level of the structuring hierarchy (Cell level). To simplify the cell synthesis , the implementation of this one is divided into two implementations: the routing implementation (input and output multiplexers) and the logic implementation (LUT). This technique permit to regard th 2) Floorplanning: Floorplanning consists in minimizing the global design area by applying some transformation over an assembly of modules (rotation, translation, swap, etc. . . ). This general situation must be specialized in a NASIC scope as both internal floorplanning (see figure 9) and external floorplanning (WISP-0 implementation illustrates such a floorplanning in [START_REF] Moritz | Wire-streaming processor on 2-d naniwires fabrics[END_REF]) are required. However, internal floorplanning can be archived when placing elements (by allocating a nanowire to only one signal, floorplanning shows a diagonal effect). External floorplanning relies on Transitive Closure Graphs (TCG) to ensure non slicing floorplans when performing annealing schedule [START_REF] Lin | TCG: A transitive closure graph-based representation for non-slicing floorplans[END_REF].

IV. CONCLUSION Among other challenges the emerging nanodevices have to face, is the lack of stable computing support that prevents from reaching mass market. On the other side, reconfigurable architectures are nowadays widespreadly used due to the ease of tailoring versions to meet application-specific requirements while preserving the cost low by cross recouping them over many applicative fields.

This paper brings a solution to implement, at low cost, well known regular FPGA architectures on top of emerging devices. The key idea behind this work is to offer to application designers a stable layer on top of which to work. This approach has already proved to be highly efficient during the early days of microprocessors. We argue transposing it to nanodevices will be as fruitful.

Fig. 1 .

 1 Fig. 1. 1-bit AND gate realized with nanowires FETs

Fig. 2 .

 2 Fig. 2. Computation models in the reconfigurable Area

Fig. 3 .Fig. 4 .

 34 Fig. 3. Schematic of the nano scale FPGA cell. All internal connections between the modules are directional.b) Basic elements:• DecoderThe figure4represents the address decoder layout with 4 input bits hence 8 nanowires (the signals a i and their

Fig. 5 .

 5 Fig. 5. LUT layout.

Fig. 6 .

 6 Fig. 6. Routing configuration layout. • Switch block The figure 7 shows a 4-to-1 multiplexer. It takes as inputs the signals F, North, South, East and their complementaries (compute plan), gives the signal Out and its complementary. The inputs a i and their complementary signals are the address bits coming from the previous routing configuration stage (configuration plan) which select the 4 input signals to be switched towards the output. The 4 white spots in the bottom of the grid are used to direct the North and South signals in the proper computing direction. The top part represents all possible combinations of the multiplexer output.

Fig. 7 .

 7 Fig. 7. Switch connection points.

  36) "END of NANOGRID" REPRESENTATION (DEFAULTCOLOR gray ) "END of DEFAULTCOLOR" (COLOR black ) "END of COLOR" (TEXT 60 40 'function name') "END of TEXT" ) "END of REPRESENTATION" NAMED f

Fig. 8 .Fig. 9 .

 89 Fig. 8. The L1 layout of a 3-LUT over a Nasic L0

TABLE I PARTIAL

 I L0 DESCRIPTION OF NFPGA II can implement the function f unction of table I, provided it appears as a RTL description (table

input bits hence 8 nanowires (the signals a i and their © EDA Publishing/ENS 2007 ISBN :978-2-35500-003-4

© EDA Publishing/ENS 2007 ISBN :978-2-35500-003-4

ACKNOWLEDGMENT

Thanks to Damien Picard for his contribution to the automation of the L1 to L0 translation.


Catherine Dezan
email: catherine.dezan@univ-brest.fr

Loic Lagadec
email: loic.lagadec@univ-brest.fr

Michael Leuchtenburg

Teng Wang
email: twang@ecs.umass.edu

Pritish Narayanan
email: pnarayanan@ecs.umass.edu

Andras Moritz
email: andras@ecs.umass.edu

BUILDING CAD PROTOTYPING TOOL FOR EMERGING NANOSCALE FABRICS

The design of CAD tools for nanofabrics involves new challenges not encountered with conventional CMOS technology. In this paper, we describe the design of a prototyping CAD tool targeting design automation of applications on a wide range of nanofabrics. Our proposal is based on a variety of models that capture as well as isolate the differences between the fabrics. This tool supports the design flow from behavioral description to final layout. It integrates fault-tolerant techniques and fabric-related density transformations with more conventional design automation techniques. After an overview of common requirements, physical models, and associated techniques, a case study in the context of NASIC fabrics is used to illustrate some of the concepts.

INTRODUCTION

As an alternative to CMOS based designs, novel nanofabrics are being proposed based on a combination of lithographic processes and bottom-up self-assembly based manufacturing. These fabrics include NanoPLA [START_REF] Dehon | Nanowire-based programmable architectures[END_REF], CMOL [START_REF] Strukov | CMOL FPGA: a reconfigurable architecture for hybrid digital circuits with two-terminal nanodevices[END_REF], FPNI [START_REF] Snider | Nano/CMOS architectures using a field-programmable nanowire interconnect[END_REF], and NASIC [START_REF] Moritz | Fault-tolerant nanoscale processors on semiconductor nanowire grids[END_REF] -to name a few. They are based on a variety of devices such as FETs, spin-based devices, diodes, and molecular switches. Furthermore, all these architectures would include some support in CMOS: some like FPNI would move the entire logic into CMOS, others, like NASIC, would only provide the control circuitry in CMOS. Other differences include fault handling: some proposals would use reconfigurable approaches, while others would rely on built-in techniques based on redundancy, voting, error correction, and/or unique fabric structures. The architectures proposed range from general purpose processors, to programmable logic arrays similar to FPGAs, and to more specialized devices such as cellular arrays and cellular neural networks.

In order to implement an application on a nanofabric, specific tools are already proposed by the respective research groups [START_REF] Dehon | Nanowire-based programmable architectures[END_REF] [START_REF] Strukov | A Reconfigurable architecture for hybrid CMOS/nanodevice circuits[END_REF]. It is clear that CAD tools are necessary to be able to design and evaluate the capabilities of larger-scale systems. As the underlying technologies are still evolving according to advances in devices, manufacturing, and fabric structures, CAD tools for nanofabrics should be ideally generic enough to integrate added features or to enable new paradigms.

This paper proposes a prototyping CAD tool that considers a nanofabric specified through a variety of models to allow optimizations on generic data structures. Through a computational model, an architectural model, a technological model and a fault model all key aspects of a particular fabric can be captured. The proposed models interact with the behavioral tools and the physical tools to produce an abstract layout of the design from high-level description. Parts that are mapped to nanoscale are separated from parts that use conventional CMOS technology.

Through this design process, a particular attention is given to fault tolerance techniques. Fault management is one of the key differences between CMOS and nanoscale design automations. To date, this tool utilizes redundancy-based techniques, errorcorrection circuits, and defect map information for reconfigurable fabrics to achieve reliable computation. Our objective is to enable future extensions as it would be impossible to start with all optimizations and fault management techniques in place in the first version. Much of this is still cutting edge research.

In summary, this paper makes the following key contributions: (1) it discusses the overall architecture of a generic CAD prototyping tool for nanoscale designs; (2) it introduces nanofabric related models to allow fairly generic processing in the presence of very different assumptions. Our objective is to create a tool that could be used by most research groups in this field. The paper is organized as follows. Section 2 gives an overview of the general organization of the proposed CAD tool and the following sections discuss the different contributions. Each section gives an illustration based on NASIC Fabric.

A PROTOTYPING TOOL BASED ON NANOFABRIC SPECIFICATION

The prototyping tool presented here is named NanoMadeo. It is based on four specific models that specify the nanofabrics. These models provide some abstractions of the nanofabrics concerning their computation paradigm (computational model), their structural organization (structural model) and technological constraints (technological model), including their fault-tolerance ability (fault model). These models interact with behavioral transformations, structural transformations and physical tools, needed to design and to implement an application onto the nanofabric support. The general flow of this tool is presented in figure 1 and the specific models are detailed in the following sections.

Computational Model

CAD tool for emerging nanofabric is intended to handle use both traditional CMOS and nanoscale technologies. The distribution of functionality between the two depends on the nanoscale capabilities, the trade-off between area and performance and the reliability of the underlying nanoscale technology.

For instance, the nanoscale parts of the system can be used solely for computation in order to gain orders of magnitude improvements in density and performance compared to CMOS technology [START_REF] He | Defect-Aware High-Level Synthesis Targeted at Reconfigurable Nanofabrics[END_REF]. However, this may have some drawbacks like the need for signal restoration when using nanowire diodes or the inversion problem with Single Electron Transistor (SET) technology. The solution can be to add logic in nanotechnology (FET logic for signal restoration) or some dedicated CMOS logic/cells (for inverter functionality).

Nanoscale technology could also be utilized for interconnects only to speed-up communication that can be problematic in deep submicron technology. NanoMadeo must handle both of these extremes in order to be useful as a prototyping tool for new nanotechnology designs.

The computational model specifies the role of the nano or CMOS segment in computation and interconnect. This division of labor is a new requirement with hybrid fabrics, which all early nanoscale computation devices are likely to be.

Architectural Model

The architectural model contains information about the building components and topological structure of the fabric. These components correspond to nanoscale or CMOS elements necessary to build the architecture on the fabric. These can be classified into basic devices, pre-composed blocks and wires as shown in figure 2.

The architectural model also contains information about the types of tiles specific to fabric: nanoBlocks for NanoPLA [START_REF] Dehon | Nanowire-based programmable architectures[END_REF], tiles of basic cells for CMOL [START_REF] Strukov | CMOL FPGA: a reconfigurable architecture for hybrid digital circuits with two-terminal nanodevices[END_REF], hypercells for FPNI [START_REF] Snider | Nano/CMOS architectures using a field-programmable nanowire interconnect[END_REF] and tiles for NASIC [START_REF] Moritz | Fault-tolerant nanoscale processors on semiconductor nanowire grids[END_REF]. The model describes the topological organization of the nano and micro components, including their hierarchical structure in tiles.

Figure 2. Building components used in architectural model

Technological Model

The technological model contains more information on the physical constraints based on the underlying technology and useful for the place-and-route routines. Nanoscale systems often do not allow arbitrary routing and placement, complicating their design as compared to CMOS designs. For example, a placement constraint related to the fabric might be the doping constraints in the NASIC fabric that limits each type of transistor to one dimension: horizontal or vertical.

Constraints on routing are particularly important in the case of reconfigurable fabrics where connections are limited to certain routes. The costs for these routes also give guidance to the routing procedures for choosing the best routes. Another constraint may be defects present in a particular chip in the case of a reconfigurable fabric. These present additional routing and placement constraints in configuring around the defects [START_REF] He | Defect-Aware High-Level Synthesis Targeted at Reconfigurable Nanofabrics[END_REF].

Fault Model

As nanoscale computational fabrics are commonly based on bottom-up manufacturing processes, reliability of this new kind of circuit is imperfect. Information on the expected faults is provided through the fault model, including what types of faults are expected, their distribution, and their probability.

Fault types include: permanent defects due to the manufacturing process such as stuck-on or off transistors or broken nanowires; transient faults due to internal noise, particle impacts, or electromagnetic interference; and process variation, including doping, channel length, wire thickness, and others. For each possible fault in a given technology, the rate and distribution (uniform/clustering [START_REF] He | Defect-Aware High-Level Synthesis Targeted at Reconfigurable Nanofabrics[END_REF]) is included in the fault model.

Example: NASIC Fabric Description

The models described above are illustrated through some emerging nanoscale fabrics in table I. Special focus is given on NASIC fabric for deeper explanations as case study.

NASIC [19][20][21] is a hybrid system based around tiles of nanowires and FETs with CMOS providing support and some control circuitry. The tiles are made up of crossed nanowires with FETs at the intersections, forming cascaded PLA-like structures. In each tile (or supertile), there is one couple(or several couples) of planes of transistors, one with the channels running horizontally and one with the channels running vertically. Thus, each tile implements two basic logic functions and can implement any logic function using two-level logic.

In the NASIC fabric, each nanotile is surrounded by microwires which provide power and control signals. The control signals implement typically various styles of a dynamic control scheme. This use of dynamic logic puts a synchronization constraint on the synthesis of applications onto NASICs, which NanoMadeo must manage. CMOS also provides support for modular redundancy schemes, encoding/decoding of inputs and outputs for the entire system (not between tiles), and control signal generation. The distribution of role between CMOS and nano layer is driven by the computational model of the NASIC fabric and explicit two main points: one is the computation organization of the nanogrid in two level logic in order to be mapped later into PLA structures (information related to synthesis), the other is related to the control aimed to be mapped at CMOS level. The architectural model of the NASIC fabric points out the building components used (here: FET, nanowire, mircowire) and explicit the structural organization in tiles based on topological rules on building components. Building components may be assembled in a predefined way (for instance for the nano and microwires, if the number of nanotiles are supposed to fixed) or in an adaptive way related to the application (placement of FETs on the PLA structure). In the latter case, these topological rules are active during the place-and-route phase.

TABLE I Main Features of Some Hybrid Nanofabrics Related to Models

Fabrics

The technological model provides the physical constraint of the NASIC fabric essentially due to the doping constraints of the two types of transistors that can be used (N-FET, P-FET). This constraints introduce some complexity in the placement routines inside one tile. The mapping onto different tiles partially replaces the doping constraints by I/O constraints between tiles.

The model takes into account two types of faults: permanent and transient fault. Distribution and rate of these types of faults have an impact on the reliability of the implementation. The fault tolerant transformations have different capabilities in masking errors that can be evaluated using a yield simulator [START_REF] Moritz | Fault-tolerant nanoscale processors on semiconductor nanowire grids[END_REF]. This point is more detailed in section 4.

APPLICATION SPECIFICATION AND BEHAVIORAL TRANSFORMATIONS

The behavioral description of an application is written in an objectoriented language (Smalltalk) that is similar to the traditional description used in Madeo [START_REF] Fabiani | Abstract execution mechanisms in a synthesis framework[END_REF]. The compilation procedure produces Directed Acyclic Graphs (DAGs), which are the intermediate representation (IR) used by NanoMadeo. This model is largely unchanged between architectures, allowing the same behavioral description to be used in comparing designs.

Behavioral Transformations

These transformations include nano/CMOS pre-partitioning taking into account the computational model: computation and interconnect tasks will be assigned to CMOS or nanoscale parts .

Fault-tolerance techniques may be applied at this level and correspond to three kinds of transformations: a) transformation introducing voters like TMR in order to duplicate portion of codes and to vote between copies, b) transformation introducing different data encoding based on redundant codes (RNS codes, Errorcorrecting codes, expressed at this level like data types, c) transformation changing the physical support: the computation can be realized by the CMOS part to be more reliable.

Illustration: Wisp0 application

WISP-0 [START_REF] Wang | Wire-streaming processors on 2-D nanowire fabrics[END_REF] is a stream processor, built on NASIC, that implements a streaming processor architecture with 5-stage pipeline: fetch, decode, register file, execute, and write back. It is a multi-tile design with 5 nanotiles. A key feature is that intermediate values during execution are often stored on the nanowires directly without explicit latches using a three-phase dynamic control. Other key aspects relate to its fault-masking strategy and density optimizations. We give in figure 4 an example of a DAG produced by the compiler from source code defining the ALU and Register File (RF) stages of WISP-0. In this DAG, nodes correspond to function calls or operators that will be synthesized into logic PLA blocks. This description implicitly describes some data synchronization, but this information could be more explicit and could be managed through specific behavioral transformations. No explicit partitioning between CMOS/Nano is done at this point because every functionality is aimed to be implemented on nano parts in the case of NASIC fabric. Nevertheless, if some fault-tolerant parts in CMOS are needed, this information needs to be explicit (for instance, the generation of CMOS voter by transformation for faulttolerance in TMR case). Other transformations for fault-tolerance can be applied by injecting specific data types for the inputs. These types represent future data encodings for the input data; for instance, in the case of NASIC fabric, BCH codes (as error correcting codes ECC) are used to introduce built-in redundancy.

SYNTHESIS, STRUCTURAL TRANSFORMATIONS AND YIELD PROJECTION 4.1 Synthesis

The resulting logic is then synthesized in the appropriate type of logic (PLA, LUT, multi-level logic) with the appropriate building components as defined by the computational model and architectural model. Standard external tools such as SIS are used for this process. This is done on a block-wise basis, with each operation as compiled from the high-level code compiled as a single block. Different levels of operator decomposition can be applied, allowing the complexity of each block to be traded off against the number of blocks.

Structural Transformations

Once the initial structural representation of the application has been generated through synthesis, transformations at the structural level are applied. The synthesis is based only on the type of logic and may not take into account all structural requirements. An example is the signal restoration required by NanoPLA. At this point, logic is synthesized for the combinatorial parts such as decoders and sequential parts such as registers or dynamic logic controls are defined around the synthesized segments as required to support the architecture.

Structural level fault-tolerance related transformations are also done in this step. These include techniques like N-way redundancy to provide additional copies of input/output signals and of some intermediate signals (the logic minterms in a case of PLA structures). Modular redundancy techniques are also possible at this stage -specific structures are selected and voter circuits are provided to implement TMR or similar schemes, but at this level, a more detailed architecture of this kind of circuitry is provided.

Yield Projection

The structural representation of the circuit plus the fault distribution given by the fault model can be used to make yield projections. This is performed by an external yield simulator. A yield simulator for PLA-based structures proposed in [START_REF] Angiolini | Improving the fault tolerance of nanometric PLA designs[END_REF] could be used for different kinds of 2D nanofabrics. Yield estimation can also be done using Monte Carlo simulation [START_REF] He | Defect-Aware High-Level Synthesis Targeted at Reconfigurable Nanofabrics[END_REF].

If the predicted yield is not satisfactory, it is possible to iterate, applying different kinds of fault-tolerant transformations to different portions of the application. These iterations may continue until an acceptable level of yield is reached.

Structural Transformations and Yield Projection for WISP-0

In the case of NASIC fabric, NanoMadeo utilizes the external synthesis tool SIS to perform the two-level logic synthesis of PLAs associated to each node of the DAG. Assembly of synthesized portions is addressed by NanoMadeo to define the complete logical structure of the WISP-0 application. WISP-0 may use some structural fault-tolerance techniques such as TMR and N-way redundancy of signals. The result of synthesis is then transformed here to implement these techniques, when they are in use.

We have developed a yield simulator to evaluate fault tolerance techniques in NASICs. The simulator generates random defect maps for designs based on a defect model and runs logic simulations on them, testing with many different possible sets of input. By measuring what proportion of the generated defect maps result in correct output when simulated, the yield can be estimated. NanoMadeo can automatically call the yield simulator to evaluate defect and fault tolerance techniques. One example of output after several runs of the yield simulator, using different fault rates and different fault-tolerance techniques(TMR, ECC,N-way) is shown graphed in figure 5. This graph provides information on the efficiency of the fault-tolerant techniques related to the fault rate and the types of permanent defects (for instance, if the fault rate is above 6%, the yield is better with ECC techniques considering 10% Stuck-off and 90% Stuck-on).

PHYSICAL DESIGN

Nanofabrics are generally organized into tiles, hypertiles or nanoblocks that correspond to clusters of PLAs, basic cells or hypercells. The partitioning techniques used to define such blocks are based on clustering heuristics for PLA packing, as in PLAmap [START_REF] Chen | Performance-Driven Mapping for CPLD Architectures[END_REF], T-VPACK [START_REF] Betz | Architecture and CAD for Deep-Submicron FPGAs[END_REF] or Singh Algorithm [START_REF] Singh | Efficient circuit clustering for area and power reduction in FPGAs[END_REF].

The parameters for clustering are the number of elementary cells or P-terms of the PLA and the number of inputs and outputs associated with the cluster. The placement problem consists of placing each basic cell inside a cluster, once the clusters are defined. This is achieved using generic optimization heuristics like simulated annealing, using e.g., congestion costs in the case of reconfigurable fabrics.

Routing procedures for nanofabrics can use adaptive maze router algorithms like Pathfinder from VPR, or they can be more specific to the fabric using, for example, custom adaptation of shortest Steiner tree problems or other VLSI algorithms [START_REF] Gerez | Algorithms for VLSI Design Automation[END_REF]. For reconfigurable fabrics, a defect map provides extra constraints for placement and routing to configure around the defects previously detected.

Table II gives an overview of the different algorithms applied in physical layout tools for the NanoPLA, CMOL and FPNI fabrics. Physical tools for nanofabrics use two kinds of algorithms or heuristics: adaptive generic algorithms or custom procedures. Adaptive generic algorithms include general purpose optimization heuristics like simulated annealing or genetic algorithms and algorithms for FPGAs like Pathfinder and PLA clustering as the ones implemented in Madeo [START_REF] Lagadec | Abstraction, modélisation et outils de CAO pour les circuits intégrés reconfigurables[END_REF] or the VPR tool.

TABLE II Physical Tools Published For Specific Nanofabrics

NanoPLA [START_REF] Dehon | Nanowire-based programmable architectures[END_REF] CMOL [START_REF] Strukov | A Reconfigurable architecture for hybrid CMOS/nanodevice circuits[END_REF] FPNI [START_REF] Snider | Nano/CMOS architectures using a field-programmable nanowire interconnect[END_REF] Partitioning PLAMAP [START_REF] Chen | Performance-Driven Mapping for CPLD Architectures[END_REF] T-VPACK [START_REF] Betz | Architecture and CAD for Deep-Submicron FPGAs[END_REF] Singh's greedy algo . CONCLUSION In order to handle next generation hybrid nano-architectures, CAD tools will have to evolve. Highly heterogeneous multi-part fabrics introduce new challenges which must be met to efficiently use those new fabrics in building real applications. In this paper, we have shown that the proposed tool, NanoMadeo, can handle many of these challenges and can be used productively for work on NASIC. Its generic design will make it easy to adapt it for work on other hybrid architectures while using much of the same functionality already implemented.

Figure 3 .

 3 Figure 3. WISP-0 Block DiagramThe specification of WISP0 with NanoMadeo is functional, including :

Figure 4 .

 4 Figure 4. DAG representing ALU and RF

Figure 5 . 5 . 1

 551 Figure 5. Graph of yield simulator output for WISP-0

Figure 6 .

 6 Figure 6. Abstract WISP-0 Layout from NanoMadeo6. CONCLUSIONIn order to handle next generation hybrid nano-architectures, CAD tools will have to evolve. Highly heterogeneous multi-part fabrics introduce new challenges which must be met to efficiently use those new fabrics in building real applications. In this paper, we have shown that the proposed tool, NanoMadeo, can handle many of these challenges and can be used productively for work on NASIC. Its generic design will make it easy to adapt it for work on other hybrid architectures while using much of the same functionality already implemented.

ENS'07Paris, France, 3-4 December 2007 © EDA Publishing/ENS 2007 ISBN :978-2-35500-003-4

© EDA Publishing/ENS 2007 ISBN :978-2-35500-003-4

ISBN :978-2-35500-003-4