Nicolas Brunie

Florent De Dinechin

Matei Istoan

Guillaume Sergent

Kinga Illyes

Bogdan Popa

Kalray Lip

ARITHMETIC CORE GENERATION USING BIT HEAPS

A bit heap is a data structure that holds the unevaluated sum of an arbitrary number of bits, each weighted by some power of two. Most advanced arithmetic cores can be viewed as involving one or several bit heaps. We claim here that this point of view leads to better global optimization at the algebraic level, at the circuit level, and in terms of software engineering.

To demonstrate it, a generic software framework is introduced for the definition and optimization of bit heaps. This framework, targeting DSP-enabled FPGAs, is developed within the opensource FloPoCo arithmetic core generator. Its versatility is demonstrated on several examples: multipliers, complex multipliers, polynomials, and discrete cosine transform.

I. INTRODUCTION AND MOTIVATION

In binary digital arithmetic, a positive integer or fixed-point variable X is represented as follows:

X = imax i=imin 2 i x i (1)
In all this paper we will call weight a power of two such as the 2 i in the above equation: X is represented as a sum of weighted bits. The indices i min and i max are the minimum and maximum weights of X.

The product of X by Y can similarly be expressed as a sum of weighted terms:

XY = ( imax i=imin 2 i x i ) × ( jmax j=jmin 2 j y j ) = i,j 2 i+j x i y j (2)
In all the sequel we use the term bit heap to denote a sum of weighted bits such as [START_REF] Wallace | A suggestion for a fast multiplier[END_REF] above. There, each weighted bit on the heap is actually a term x i y j . However, most of this work will focus on the final summation: How each weighted bit was produced (e.g. as an AND of two input bits here) is mostly irrelevant -it will be addressed only when needed.

We will classically [START_REF] Ercegovac | Digital Arithmetic[END_REF] represent bit heaps as 2D dot diagrams such as Fig. 1(c) and following. There, the horizontal axis represents the weights (most significant bits left as usual), and each dot represents one weighted bit participating to the final sum. Here also, how each bit was computed is not shown.

Bit heaps capture bit-level parallelism

Addition within a sum of weighted bits is associative and commutative. For instance, in a dot diagram, the order of the bits in a column (same weight) is irrelevant. Therefore, a representation like i,j 2 i+j x i y j captures all the intrinsinc bit-level parallelism present in this sum. Exploiting this, a fast multiplier may be built as a tree (often called a compressor tree) of bit-level adders [START_REF] Wallace | A suggestion for a fast multiplier[END_REF], [START_REF] Dadda | Some schemes for parallel multipliers[END_REF], [START_REF] Oklobdzija | A method for speed optimized partial product reduction and generation of fast parallel multipliers using an algorithmic approach[END_REF], [START_REF] Stelling | Optimal circuits for parallel multipliers[END_REF], [START_REF] Ercegovac | Digital Arithmetic[END_REF]. More details will be given in Section IV in the context of FPGAs. In general, the sum of a bit heap can be computed by an architecture operating in space linear with the size of the heap (its total number of bits), and time logarithmic in its maximum height (the maximum number of bits of same weight) [START_REF] Ercegovac | Digital Arithmetic[END_REF].

Bit heaps are versatile

Bit heaps are not limited to computing multiplication. It is easy to show that the sum or product of a bit heap are themselves bit heaps (they can be developed as a single big sum). By induction, any multivariate polynomials of fixedpoint inputs may be expressed as a single sum of weighted bits. This includes addition and multiplication on complex numbers, sums of products and sums of squares (for linear algebra operators or signal processing transforms), polynomials used to approximate elementary functions, etc. Besides, the bits may come from table lookup or other arbitrary components, which further enlarges the class of functions where a bit heap is relevant.

Expressing such a function as a monolithic bit heap (a single sum), rather than as a composition of adders and multipliers, enables a global optimization instead of several independent local ones. This has been shown to lead to more efficient bitlevel implementations [START_REF] Swartzlander | Merged arithmetic[END_REF], [START_REF] Verma | Data-flow transformations to maximize the use of carry-save representation in arithmetic circuits[END_REF], [START_REF] Parendeh-Afshar | Compressor tree synthesis on commercial high-performance FPGAs[END_REF]. However, there has been so far no attempt to capture this generality in a universal tool. This is the main goal of the present work.

Due to this versatility, this article will demonstrate bit heaps with a variety of shapes. This is why we prefer the phrase bit heap over the phrase "bit array" used in the multiplier literature (where bit heaps are indeed lozenges). It also emphasizes that the order is irrelevant in the sum.

Bit heaps enable bit-level algebraic optimizations

The bit heap is also a pertinent tool to assess and improve the bit-level complexity of computing such multivariate polynomials. An enlightening example (to our knowledge unpublished) is a third-order Taylor formula for the sine: sin(X) ≈ X -X 3 /6, which we use in [START_REF] De Dinechin | Fixed-point trigonometric functions on FPGAs[END_REF]. This formula can be evaluated using two standard multiplications (to compute X 3 ), a multiplication by the constant 1/6, and a subtraction. However, it can also be expressed directly as a single bit heap as follows. From (1), we may write

X 3 = imax i=imin 2 3i x 3 i + imin≤i<j≤imax 3 • 2 i+2j x i x 2 j + imin≤i<j<k≤imax 6 • 2 i+j+k x i x j x k (3)
Here we have a first set of algebraic simplifications to apply, for instance x k i = x i or 2•2 w a = 2 w+1 a. The multiplication by 3 can be obtained by duplicating bits in the bit heap: 3•2 w a = 2 w+1 a + 2 w a. At this point the computation of X 3 already requires about one third of the bit-level operations that would be present in two multipliers. However, as we are interested in X 3 /6, we may optimize further and rewrite (3) as:

X -X 3 /6 = imax i=imin 2 i x i -1/3 imax i=imin 2 3i-1 x i -imin≤i<j≤imax •2 i+2j-1 x i x j -imin≤i<j<k≤imax •2 i+j+k x i x j x k
(4) Now we only have only i max -i min bits of the bit heap to actually divide by 3. We target some output accuracy, typically matching the input precision p = i max -i min + 1. One option is to replace 1/3 with its binary representation 0.1010101..., suitably truncated. Then the second line adds about as many bits to the bit heap as the third one. We use another option, with a variation of the divider by 3 from [START_REF] De Dinechin | Table-based division by small integer constants[END_REF] that adds 3p bits to the bit heap, albeit after a delay.

Table I shows properly truncated bit heaps in the context of a sine/cosine implementation [START_REF] De Dinechin | Fixed-point trigonometric functions on FPGAs[END_REF], and gives the corresponding synthesis results (for smaller input sizes, the whole of X 3 /6 is simply tabulated).

A versatile bit heap implementation simplifies core generation

Finally, bit heaps are convenient from a software development point of view. The purpose of the FloPoCo project 1 is to generate an infinite set of application-specific operators for FPGA-based computing [START_REF] De Dinechin | Designing custom arithmetic data paths with FloPoCo[END_REF]. The long-term development of such a core generator is challenging for several reasons. Firstly, the operators we want to develop are increasingly complex (currently including filters, elementary functions, etc). Secondly, FloPoCo has the ambition of optimizing all its operators for a wide range of FPGAs from the main vendors. The sheer combinatorics of operators (each heavily parameterized) and targets make this task less and less tractable.

However, most of the advanced operators include products, sums of several terms read from tables or computed as products, etc. A solution to the above issue is therefore to express as much as possible of the operators as bit heaps. We may then delegate their implementation (the actual code generation) to a [START_REF] De Dinechin | Fixed-point trigonometric functions on FPGAs[END_REF] single, centralized, versatile bit heap framework. When a new FPGA appears, all we need is to update this one piece of code.

This can be viewed as an elegant way to separate 1/ optimizations that are of mathematical nature (the construction of the bit heap), and 2/ optimizations that depend on the target technology and target performance (its compression).

The remainder of this article introduces such a universal bit heap manipulation tool. As a bit heap is a data structure, not an arithmetic operator in the usual sense, we embed this notion in the FloPoCo architecture generator. To obtain an architecture, one first throws bits (now VHDL signals) from various components on a bit heap, then calls a routine that will build the compressor tree.

Outline

As FPGAs offer more and more DSP computing resources, we first need to include these resources in a bit-heap-centric view in Section II. This will actually expose additional optimizations opportunities.

Section III describes in details the data structures used for bit heap manipulation, with a focus on timing issuesin coarser operators such as DSP-based multipliers or our X -X 3 /6 example, bits may arrive on the bit heap from various sources and at different times. Another focus is on signed bit heaps handling two's complement numbers: we generalize classical tricks to show that signed numbers entail very low overhead.

Section IV studies the construction of the compression tree. It shows that the best elementary compressors are based on ternary adders on FPGA architectures that support them, such as the recent Altera circuits.

The interested reader will find in the FloPoCo source code (starting with version 2.4.0) all the details omitted here due to space constraints.

II. BIT HEAPS IN DSP-ENABLED FPGAS

One initial motivation of this work was to improve the implementation of large multipliers using DSP blocks in FloPoCo. This section first reviews the state of the art, points to sub-optimal design choices, and shows how a DSP-aware bit heap view can solve them.

A. FPGA multiplication capabilities

The logic fabric of FPGAs is based on small look-up tables (LUTs). A k-inputs look-up table (LUTk) may implement any boolean function of up to k inputs (k = 4, 5, or 6 in current FPGAs). For instance, an AND of up to k bits consumes one LUTk, so each bit of the bit heap for a degreek polynomial will cost one LUT to compute. Tightly coupled carry propagation logic enables fast carry-ripple additions at the cost of one LUT per addition bit. This logic is designed so that array multipliers can be built at the cost of n 2 LUTs for an n × n-bit multiplier.

In recent years, the number k of inputs to the LUT has increased from 4 to 6. A 3x3-bit multiplication may now be implemented by tabulating it in 6 LUT6, instead of accumulating it in 9 LUT6. This is not only smaller, but also as fast as it gets (one LUT delay).

Back to the bit heap, this is also an efficient way of generating partial products for a logic-based multiplier. We are not aware of this idea in the literature. The smaller squares on figures such as Fig. 2 represent such 3x3 LUT-based multipliers.

Recent FPGAs also include small "hard" multipliers. Altera chips offer 36x36-bit multipliers fracturable into a variety of combinations of 18x18, 12x12 and 9x9 ones, and various relevant sum-of-product configurations. Recent Xilinx chips offer 18x25 signed multipliers followed by 40-bit adders. Starting with Virtex-6, there are also adders on the inputs. Exploiting this variety is the current main challenge of portable arithmetic design in FloPoCo.

B. Building large multipliers as bit heaps

A large multiplication must be decomposed in smaller ones that fit hardware resources. This decomposition is a sum: it can be managed as a bit heap. To illustrate this, consider the following 4-DSP implementation of a 41x41 multiplier on Virtex-5 [START_REF] Banescu | Multipliers for floating-point double precision and beyond on FPGAs[END_REF].

XY = (X 0:16 Y 0:23 + 2
In [START_REF] Banescu | Multipliers for floating-point double precision and beyond on FPGAs[END_REF], the process of discovering ( 5) is called tiling. A multiplier board must be tiled with tiles corresponding to hard multipliers. Smaller, leftover tiles may be implemented as logic, as shown on on Fig. 1.

Furthermore, the adders included in DSP blocks may be used to sum the results of several multipliers. A sequence of multipliers chained by adders without needing any LUT logic is called a supertile in [START_REF] Banescu | Multipliers for floating-point double precision and beyond on FPGAs[END_REF]. For instance, the two parentheses of (5) correspond to two supertiles for Xilinx Virtex 5 or later. Altera devices have square multipliers and different supertiling capabilities, but the same concepts apply -see [START_REF] Pasca | Correctly rounded floating-point division for DSP-enabled FPGAs[END_REF] for recent examples. This tiling approach is very versatile. To illustrate it, Fig. 2 shows the tiling of a 53x53-bit truncated multiplier outputting a faithful result on 53 bits. On this figure, we have one potential supertile of size 3, and one of size 1. Fig. 3, inspired by [START_REF] Pasca | Correctly rounded floating-point division for DSP-enabled FPGAs[END_REF], shows the same multiplier implemented for a Stratix IV device. It consists of one 36x36 multiplier, and two 18x18 ones that form a supertile. Also note that the tiling algorithm has a threshold parameter t (set to 0.5 for all our figures). It defines the percentage of multiplier that must be useful to the large multiplication for a DSP block to be used. Set to zero, only logic will be generated. Set to 1, only DSP blocks will be used.

D(0)(0) D(1)(0) D(0)(1) D(0)(0) (a) Tiling view D(0)(0) D(1)(0) D(0)(1) D(0)(0) (b) Weight-aligned view (c) bit heap view

C. Bit heap versus components

In [START_REF] Banescu | Multipliers for floating-point double precision and beyond on FPGAs[END_REF], a large multiplier is not based on a bit heap, but implemented as a combination of three types of components: DSP multipliers, logic multipliers, and multi-input adders. This entails several inefficiencies in a pipelined design:

1/ artificial synchronization of the bits of intermediate sums, whereas the lower bits could typically be forwarded earlier than the upper bits;

2/ several instance of bit heap compression (one for each logic-based multiplier, plus one for the final multi-addition); These inefficiencies are aggravated if the multiplier is itself part of a larger component that could be expressed as a single bit heap. An important case is a sum of products, the simplest example being the complex product depicted on Fig. 4. In this case, additional optimizations opportunities arise.

The first is that supertiles can be built out of tiles coming from different multipliers, as long as they contribute to the same bit heap. Fig. 4 consists of two bit heap, each adding two products. Altera DSP blocks are designed to implement such operations (a × b ± c × d) efficiently for precisions of 18 bits. Our key observation is that even for larger sizes (where each multiplier is decomposed in several DSP blocks), we can pair in a DSP corresponding sub-products from the two multipliers in a supertile computing a × b ± c × d.

The second optimization is to exploit the adders within the DSP blocks to consume bits from the bit heap (without consideration of where they come from). In the simple multiplier examples, the first DSP adder of a supertile is unused. If we can feed it bits from another source (e.g. bits from the logicbased multiplier, possibly already partly compressed), it will remove them from the bit heap for free. Xilinx DSP adders can input such an external addend. Note that Altera ones cannot, unless otherwise unused multipliers are used as pass-through.

D. Summing up

The good way to manage DSP blocks in a bit heap is therefore to

• consider DSP blocks as unevaluated multiplications in a bit heap, and • consider supertiling as a step of the compression process. With this point of view, a multiplier contributes to a bit heap, but may not be alone in doing so. It may contribute bits from logic-based tiles, or DSP-sized tiles. The chaining of such tiles into a supertile is part of the compression process, and it may even consume other bits of the bit heap. The result of a supertile will be itself sent back to the bit heap for further compression.

In the proposed framework, a multiplier is not necessarily a component itself (an entity in VHDL terms). In the complex multiplier, it is a virtual component that throws bits to the bit heap of a larger component. In terms of architecture generation, the (simplified) code of a sum of product will be addBitsToBitHeapForMult(...); addBitsToBitHeapForMult(...); compressBitHeap();

An adder or subtractor is not necessarily a component, either. The adder and subtractor of Fig. 4 have no corresponding VHDL entities, they are part of the compression.

Conversely, an operator may involve several distinct bit heaps (two on Fig. 4). This will be the general case.

The complex multiplier example also shows that we must be able to add the opposite of a product to the bit heap. An efficient implementation of this, exploiting the fact that DSP blocks include signed multipliers, will be shown in Section III-C.

III. THE UNIVERSAL BIT HEAP

Let us first stress that the bit heap is a dynamical data structure during the circuit generation process: First, several sub-operators may add bits to the bit heap. Eventually, in the construction of the compressor tree, bits will be removed from the bit heap, and new bits will be added, until only the final sum remains.

There are two aspects of time here: operator-generation time (as the generator program runs), and circuit time (using notions such as critical path or, for pipelined designs, cycles). The generator must be able to evaluate the circuit time, for instance as in [START_REF] De Dinechin | Designing custom arithmetic data paths with FloPoCo[END_REF].

A. The data structure

A weighted bit is a data structure consisting essentially of its signal name, its weight, and its instant. A column of the bit heap is represented as a list of weighted bits, ordered by their arrival time (in the circuit time). The complete bit heap data structure essentially consists of a maximum weight, and an array of columns indexed by the weights.

Figures 1(c), 2(c), 3(c), 4(b) or 4(c) represent such data structures, with the weights as horizontal axis, least significant bits to the right, as in standard binary numeration. Different arrival times are indicated by different colors. These figures are actually Scalable Vector Graphics files that can be opened in a browser, in which case hovering the mouse over one bit shows its signal name and its arrival instant in circuit time.

B. Managing constant weighted bits

Some of the bits added to a bit heap are constant bits, e.g. coming from

• rounding truncated products added to the bit heap,

• rounding the final result of the bit heap,

• managing two's complement signed numbers, as explained below in III-C.

It would be wasteful to dedicate hardware to compressing such constant bits, as their sum is known in advance. Therefore, the bit heap data structure also includes a multiple-precision integer which gathers all the constant bits. The actual value of the sum of all the constant bits is added to the bit heap just before compression. This is an old trick, widely used in the design of Baugh-Wooley signed multipliers [START_REF] Baugh | A two's complement parallel array multiplication algorithm[END_REF] and multi-input adders [START_REF] Ercegovac | Digital Arithmetic[END_REF]. However the addition of the constant bits was usually computed by hand, which for complex bit heaps soon becomes error-prone. Here it is performed by the generator, which is simpler, safer and more flexible.

As a side effect, note that fixed-point rounding computations can often be merged in the global compression for free.

C. Managing signed numbers

Signed numbers are classically represented using two's complement notation [START_REF] Ercegovac | Digital Arithmetic[END_REF]. It is possible to design bit heaps operating directly on positive and negative bits [START_REF] Jaberipur | An efficient universal addition scheme for all hybrid-redundant representations with weighted bit-set encoding[END_REF], but this section shows that managing two's complement signed numbers in a bit heap costs very little, as most of the overhead can be hidden in the constant bit vector.

1) Sign extension using the constant vector: Most numbers added to the bit heap do not extend to its full range of weights. When such a number is signed, it must be sign-extended: its MSB must be replicated all the way up to the MSB of the bit heap [START_REF] Ercegovac | Digital Arithmetic[END_REF]. Done naively, this could add many bits to the bit heap, some of them with large fanout. We may use here a classical trick from two's complement multipliers: to replicate bit s from weight p to weight q, we add the complement of s at weight p. Then we add 2 q -2 p to the constant bit vector (this correspond to a string of 1s stretching from bit p to bit q). The reader may check that this performs the necessary sign extension both when s = 0 and s = 1.

All these constant bits are compressed into the constant vector: The overhead of a bit heap accepting signed numbers, with respect to an unsigned bit heap, is at most one line of bits.

Relatedly, subtracting a number to the bit heap resumes to adding the bitwise complement (with sign extension), and a constant 1 to the LSB of the subtrahend.

2) Adding or subtracting a product of signed numbers: Suppose we now have a bit heap whose result will be a two's complement numbers, and we want to either add or subtract the product XY , with X and Y being two's complement numbers on p and q bits respectively:

X = -2 p-1 x p-1 + p-2 i=0 2 i x i Y = -2 q-1 y q-1 + q-2 j=0 2 j y j
The product will be written

XY = 2 p+q-2 x p-1 y q-1 -2 p-1 x p q-2 j=0 2 j y i -2 q-1 y q p-2 i=0 2 i x i +( p-2 i=0 2 i x i ) × ( q-2 j=0 2 j y j ) (6)
This product is a p + q-bit number with the sign bit at position p + q -1. This weight doesn't appear in the above equation but appears as a carry out of the sum.

Adding this product to a bit heap can be performed by adding separately these four addends. The last line is a standard product of unsigned numbers, and can be added to the bit heap as is. The same holds for the first line -weight p + q -2 is not the sign bit. The two intermediate lines must be subtracted from the bit heap, which can be done by complementation and sign extension as described above.

Subtracting a product from the bit heap (as needed on the real side of the complex multiplier) is similar, and is "left as an exercise to the reader". There is one trap: the negated product of two unsigned terms is not always negative, it may be zero, which has a positive sign.

We now want to exploit DSP blocks which are able to compute signed multiplications. A generalization of the previous technique consists in decomposing a p-bit input X = -2 p-1 x p-1 + p-2 i=0 2 i x i as X = 2 p-k X h + X l where • X h is formed of the k leading bits (including the sign bit), and may be considered as a k-bit signed number, • X l is formed of the p -k least significant bits, and is an unsigned number. We may similarly split Y = 2 q-k Y h + Y l . Here k and k must be understood as the size of a signed product: (k, k ) = (18, 25) on Xilinx, (k, k ) = (18, 18) on Altera. The product XY now becomes

XY = 2 p+q-k-k X h Y h (signed × signed) +2 p-k X h Y l (signed × unsigned) +2 q-k X l Y h (unsigned × signed) +X l Y l (unsigned × unsigned)
With this rewriting we may now use, for the lines involving a signed number, signed multipliers offered by DSP blocks. Adding -XY to a bit heap is similar.

IV. TIMING-DRIVEN BIT HEAP COMPRESSION

This section deliberately focuses on the various tradeoffs involved, as the algorithmic details may be found in the (still evolving) FloPoCo source code. It will be illustrated by Fig. 5, which describes the timing-driven compression of the bit heap of Fig. 2.

A. Basics

Bit heap compression is based on a set of elementary compressors. An elementary compressor inputs a few bits from the bit heap, and replaces them with their sum, on fewer bits. The simplest example is the full adder: It computes the sum of three bits of weight w, and rewrites this sum as two bits of weights w + 1 and w. It is also called (3:2) compressor. On Fig. 5, we have highlighted two (6:3) compressors that rewrite the sum of 6 bits as a 3-bit number.

The compression of a bit heap therefore consists of several stages. In each stage, the bit heap is paved with as many compressors as possible that compress it in parallel (we hae highlighted only two of them on Fig. 5). The outputs of these compressors, plus possibly bits that have not been compressed in previous stages, plus possibly new bits arrived on the bit heap in between, form a new bit heap ready for the next stage.

There are therefore two broad issues to address: the choice of an elementary compressor library, and the algorithm that assembles them to form a full compression tree.

On FPGAs, the state of the art, concerning the first issue, is [START_REF] Parendeh-Afshar | Compressor tree synthesis on commercial high-performance FPGAs[END_REF] (also see references therein). Their main contribution is to show that large elementary compressors can be built efficiently using the fast-carry logic.

With respect to the second issue, there are many technological parameters to take into account (starting with the compressor library and the performance of its various elements). In additions, there are several possible objective function: one may want to optimize for delay, or for area for instance. Most suggested solutions are somehow greedy: try to exploit the most efficient elementary compressors first, try to compress as much as possible in one stage. The algorithm in [START_REF] Parendeh-Afshar | Compressor tree synthesis on commercial high-performance FPGAs[END_REF] works along these lines, as does the one we have implemented.

B. Elementary compressors for FPGAs

We use the notation of [START_REF] Ercegovac | Digital Arithmetic[END_REF] and [START_REF] Parendeh-Afshar | Compressor tree synthesis on commercial high-performance FPGAs[END_REF] to describe elementary compressors called generalized parallel counters in [START_REF] Parendeh-Afshar | Compressor tree synthesis on commercial high-performance FPGAs[END_REF]. The full adder is denoted GPC(3:2). A GPC(k 1 , k 0 : r) inputs k 0 bits of weight 0 and k 1 bits of weight 1 and rewrites their sum on r bits. This notation can be generalized to more input columns but there is a diminushing return, and [START_REF] Parendeh-Afshar | Compressor tree synthesis on commercial high-performance FPGAs[END_REF] only considers two columns.

Table II analyses the theoretical costs of some elementary compressors, including the best from [START_REF] Parendeh-Afshar | Compressor tree synthesis on commercial high-performance FPGAs[END_REF], on an FPGA model that matches modern FPGAs from both Xilinx and Altera: the elementary cell is a LUT6 which may be used as two independent LUT5, combined with some dedicated fast carry propagation. More accurate, low-level synthesis results for both Altera and Xilinx may be found in [START_REF] Parendeh-Afshar | Compressor tree synthesis on commercial high-performance FPGAs[END_REF]. In this table, we report

• the compression factor γ = number of input bits number of output bits . A higher γ means fewer stages.

• the number of bits removed from the heap by a compressor. For instance the GPC(3:2) removes only one bit, while the GPC(6:3) removes 3 bits; • the cost in LUT6 of the compressor. For instance, the GPC(3:2) uses a LUT6 as two independent LUT3, one for FOR THE ACTUAL COSTS ON STRATIX III AND VIRTEX5, SEE [START_REF] Parendeh-Afshar | Compressor tree synthesis on commercial high-performance FPGAs[END_REF].

each of its output bits: it costs one LUT6. The GPC(6:3) needs one LUT6 for each of its output bits; • the cost per removed bit, which is the relevant measure of area-efficiency of a compressor; • the delays, expressed in terms of τ L , the combined delay of a LUT and the local routing surrounding it, and τ cp , the delay of a carry propagation of one bit. It should be noted that τ cp << τ L , typically τ L ≈ 30τ cp . For instance, the 3 LUT6 of a GPC(6:3) operate in parallel, and thus have a delay of 1τ L . Conversly, the arithmetic compressors from [START_REF] Parendeh-Afshar | Compressor tree synthesis on commercial high-performance FPGAs[END_REF] involve a chain of two or three LUT6 connected by the global routing.

The main use of this ratio of bits removed per LUT6. Delay-wise, we want to minimize the number of stages (higher γ) and the delay of one stage (lower delay). For instance, for the same bit/LUT ratio, it is preferable to use GPC(6:3) than GPC(3:2), as it will lead to fewer stages.

Our contribution is to observe that the ternary adder, when supported (e.g. on recent Altera FPGAs) is a serious contender. It has, for sizes between 5 and 30, the best ratio of compressed bits per LUTs, the best compression factor γ, and a delay between τ L and 2τ L thanks to τ L ≈ 30τ cp . This is consistently better than the arithmetic compressors of [START_REF] Parendeh-Afshar | Compressor tree synthesis on commercial high-performance FPGAs[END_REF]. Table III shows that the area gain over parallel counters may be close to 50% for the same delay. This is not in contradiction with the main conclusion of [START_REF] Parendeh-Afshar | Compressor tree synthesis on commercial high-performance FPGAs[END_REF], which was that GPCs are more efficient than ternary adder trees: they consider the implementation of a bit heap compressor as a single tree of large ternary adders. There, many of the inputs to these adders must be padded with zeroes, which reduces the area efficiency. What we advocate here is the use of small ternary adders, whose size is chosen to pave the bit heap efficiently (without padding) while keeping the delay small.

A final advantage of the ternary adder is that it easy to express in a portable way (a+b+c in Verilog or VHDL).

With all these considerations, our current implementation mostly ignores [START_REF] Parendeh-Afshar | Compressor tree synthesis on commercial high-performance FPGAs[END_REF], and considers only the naive LUT6-based elementary compressors GPC(3:2), GPC(6:3), GPC(1,5:3), and small binary and ternary adders, the latter only on recent Altera targets.

C. Supertiling (DSP compression)

To compress a bit heap including multiplier tiles (possibly from several multipliers as described in Section II), the first step is to attempt to chain these into supertiles, using DSP adders.

Some of the bits produced along a supertile are reversed to the bit heap, tagged with the instant at which they are available. For instance, when we use two chained DSPs to compute (a× b) + 2 s (c × d) where s is a constant shift (17 on Xilinx, 18 on Altera), the lower bits of the sum are those of a × b and are sent to the bit heap, while only the upper bits are sent to the DSP adder.

Conversely, in the beginning of a supertile, we look for bits available in the bit heap at the instant when the first DSP multiplication finishes. These bits will be registered and added for free using the adder of the first DSP of the supertile.

The exact supertiling algorithm depends on the target. On Xilinx, the DSP blocks are independent and can be chained only using 17-bit shifts. On Altera, the DSP block granularity is larger: a unit actually includes four 18x18 multipliers and an adder tree that has several possible configurations, the flexibility being limited by the number of physical output bit of the unit (around 72 bits). One useful configuration is the 36x36 multiplier, and we generate this as a single tile (see Fig. 3(a)). Another is the "complex multiplier" configuration, with two parallel sums of (independent) 18x18 products. The supertiling opportunities for the 9x9 and 12x12 configurations are unclear at this point.

To sum up, this step of the compression (in generation time) adds bits to the bit heap, and may remove some, too. We are then left with a classical (but timed) bit heap.

D. Bit-level compression

After supertiling, we have a main loop that advances a global (circuit) time. At each iteration, we look for sets of bits ready for compression in the bit heap. We tile such bits with the best possible compressors (more on their choice below). Applying a compressor means generating the corresponding hardware and removing its inputs bits from the bit heap. Output bits are sent to the bit heap where they arrive at a later circuit time (the max of the times of the inputs, plus the delay of the compressor). In a pipelined compressor, this may entail a change of cycle, or not. The output bits of one stage are not allowed to be processed in the same stage, to prevent the construction of carry propagation in one stage.

There is a heuristic decision to take to apply sub-optimal (area-wise) compressors. In the beginning of the loop, we prefer not to do it, hoping that the later arrival of more bits will enable the use of the most efficient compressors. In the last stages, however, sub-optimal compressors should be used, otherwise the delay will increase. A good strategy, inspired by Dadda [START_REF] Dadda | Some schemes for parallel multipliers[END_REF], is to first evaluate the optimum delay, and then use the fewest possible sub-optimal compressors to reach this optimal delay.

The loop is stopped when no column holds more than 3 bits. There are several options for the final addition of these bits, depending on the target hardware and target frequency:

• it may use a ripple-carry ternary adder. This is the best option if the target FPGA supports it, and if the bit heap width is small enough for this addition to fit in one cycle. • otherwise we may use one row of GPC(3:2) compressors, then any high-speed adder from [START_REF] Nguyen | FPGA-specific arithmetic optimizations of short-latency adders[END_REF]. In both case, this final addition is started as early as possible: if the final addition of the LSB bits can overlap the compression of the MSBs, we do it.

E. Results

Table I showed results for a truncated X -X 3 /6, Table IV shows some synthesis results for the complex product, and Table V shows results for LUT-based discrete cosine transforms. These examples stress all the aspects of the framework. Performance does not yet always match expectations, but the complex product demonstrates the cost saving of a single bit

Fig. 1 . 5 D

 15 Fig. 1. A possible implementation of a 41 × 41 multiplier on Virtex-5

  Fig. 3. 53x53-bit faithful multiplier for Stratix IV.

Fig. 1

 1 Fig. 1 is generated by FloPoCo. Its bit heap (Fig. 1(c)) receives the results of two supertiles, plus the bits of the central logic-based multiplier decomposed into 3 × 3 multipliers.This tiling approach is very versatile. To illustrate it, Fig.2shows the tiling of a 53x53-bit truncated multiplier outputting a faithful result on 53 bits. On this figure, we have one potential supertile of size 3, and one of size 1. Fig.3, inspired by[START_REF] Pasca | Correctly rounded floating-point division for DSP-enabled FPGAs[END_REF], shows the same multiplier implemented for a Stratix IV device. It consists of one 36x36 multiplier, and two 18x18 ones that form a supertile. Also note that the tiling algorithm has a threshold parameter t (set to 0.5 for all our figures). It defines the percentage of multiplier that must be useful to the large multiplication for a DSP block to be used. Set to zero, only logic will be generated. Set to 1, only DSP blocks will be used.

  (a) Arithmetic view (b) The two bit heaps for 12-bit faithful results.(c) The two bit heaps for 32-bit faithful results, using one DSP block for each multiplication.

Fig. 4 .

 4 Fig. 4. Complex multiplication as two bit heaps. Different colors in the bit heap indicate bits arriving at different instants.

TABLE I X

 I -X 3 /6 ON VIRTEX-5 FOR THE FAITHFUL SINCOS OPERATOR OF

  17 X 17:40 Y 0:16 ) + 2 23 (X 0:23 Y 24:40 + 2 17 X 24:40 Y 17:40 ) + 2 34 X 17:23 Y 17:23

  Fig. 5. Timed view of the compression of the bit heap of Fig. 2 for 400MHz. Horizontal lines separate compression stages, bold lines separate clock cycles. On the right, the numbers indicate the clock cycle and the delay within a cycle.

	The operation of two GPC(6:3)
	compressors is highligted.
	All the compressors
	operate in parallel.
					before first compression
					0	1.113 ns
					0	1.644 ns
	The results from DSP blocks
	arrive on the bit heap		1	1.061 ns
	at cycle 2 only
					1	1.158 ns
					2	1.061 ns
					2	1.158 ns
					2	1.273 ns
					before 3-bit height additions
					before final addition
	name	γ	δ bits	LUT6	δ bits /LUT6	delay
	Naive LUT-based compressors
	GPC(3:2)	1.5	1	1	1	τ L
	GPC(6:3)	2	3	3	1	τ L
	GPC(1,5:3)	2	3	3	1	τ L
	Arithmetic-based compressors from [8]
	GPC(1,5:3)	2	3	2	1.5	2τ L + 2τcp
	GPC(7:3)	2.33	4	3	1.33	3τ L + 2τcp
	GPC(3,5:4)	2	4	3	1.33	3τ L + 2τcp
	Adders as compressors
	adder(n)	2	n	n	1	τ L + nτcp
	adder3(n)	3 n n+2	2n -2 n + 2	2n-2 n+2	τ L + nτcp
	adder3(16)	2.66	30	18	1.66	1.5τ L

TABLE II THEORETICAL

 II COMPARISON OF SEVERAL ELEMENTARY COMPRESSORS.

  table is to help us decide which is the best compressor at each stage of the compression process. Area-wise, we want to use the compressors with the highest

		cost of	cost of compression
		partial products (parallel counters) (ternary adders)
	24x24	384	505	283
	32x32 trunc.	510	379	287
		TABLE III
	ALM COSTS FOR LOGIC-BASED MULTIPLIERS (PARALLEL COUNTER
	VERSUS TERNARY ADDERS) ON ALTERA STRATIX IV

heap over the instantiation of several adder and multiplier components, all other things being equal (in particular each multiplier using the compression code of the fused bit heap).

All these operators are faithful, i.e. their error with respect to an infinitely accurate computation is strictly smaller than the LSB of the result. This focus on accuracy is a distinct feature of FloPoCo, and the bit heap approach also makes the needed error analysis easy, but space is missing to detail this.

V. CONCLUSION

This article suggests to place the notion of bit heap at the center of arithmetic design, especially for coarse operators. The benefit is to expose, at different levels (from algebraic to circuit), a global optimization instead of several local optimizations. A versatile tool for manipulating and implementing such bit heaps is discussed. It also makes for shorter, more robust and better organized code in the open-source FloPoCo arithmetic generator.

This approach is directed toward arithmetic designers. An alternative approach is to use bit heaps in high-level design tools: Compilers optimizations that transform arithmetic circuits to maximize the benefit of carry-save notation [START_REF] Verma | Data-flow transformations to maximize the use of carry-save representation in arithmetic circuits[END_REF] could be used to build bit heaps automatically, in which case the proposed framework would serve as a back-end.

Short-term future work includes refinements to this bit heap framework, in particular the supertiling and compression heuristics. This will improve the absolute performance of the generated architectures. We are also working on relevant interfaces to the various trade-offs involved.

A promising direction is to work on the approximation of a function directly by a bit heap. In this context, we intend to automate algebraic optimizations such as those developed for X -X 3 /6. There are also many opportunities to pre-compress, in small tables [START_REF] Hassler | Function evaluation by table look-up and addition[END_REF] that would fit LUTs, sums of terms sharing the same inputs.

Looking further, bit heaps could be a pertinent tool to address open bit-level complexity questions such as: How many bits does one need to flip to compute a faithful 16-bit sine function?


Yike Hu

Ming Ruan

Zelei Guo

Rui Dong

James Palmer

John Hankinson

Claire Berger

Walt A De Heer

Structured epitaxial graphene: growth and properties

Graphene is generally considered to be a strong candidate to succeed silicon as an electronic material. However, to date, it actually has not yet demonstrated capabilities that exceed standard semiconducting materials. Currently demonstrated viable graphene devices are essentially limited to micron size ultrahigh frequency analog field effect transistors and quantum Hall effect devices for metrology. Nanoscopically patterned graphene tends to have disordered edges which severely reduce mobilities thereby obviating its advantage over other materials. Here we show that graphene grown on structured silicon carbide surfaces overcomes the edge roughness and promises to provide an inroad into nanoscale patterning of graphene. We show that high quality ribbons and rings can be made using this technique. We also report on progress towards high mobility graphene monolayers on silicon carbide for device applications.

Introduction

Whether graphene will or will not become an important electronic material critically hinges on our ability produce high quality graphene and to pattern it at the nanoscale. Currently the predominant paradigm for producing graphene devices of any kind, is to start with an extended graphene sheet, that may be produced by a variety of methods [START_REF] Berger | Ultrathin epitaxial graphite: 2D electron gas properties and a route toward graphene-based nanoelectronics[END_REF][START_REF] Park | chemical methods for the production of graphenes[END_REF][START_REF] Li | Large-Area Synthesis of High-Quality and Uniform Graphene Films on Copper Foils[END_REF] , and subsequently to pattern the sheet using standard microelectronics lithography methods [START_REF] Berger | Electronic confinement and coherence in patterned epitaxial graphene[END_REF][START_REF] Han | Energy Band-Gap Engineering of Graphene Nanoribbons[END_REF][START_REF] Oostinga | Magnetotransport through graphene nanoribbons[END_REF][START_REF] Stampfer | Energy Gaps in Etched Graphene Nanoribbons[END_REF][START_REF] Gallagher | Disorder-induced gap behavior in graphene nanoribbons[END_REF] . Typically lithography is performed by coating the graphene sheet with a resist material which is subsequently exposed to light or and electron beam, producing an image on the resist, that is subsequently developed to expose the graphene surface. The exposed graphene is then cut, typically using an oxygen plasma that removes the exposed graphene resulting in a patterned graphene layer. However if patterned graphene is seen as a macro molecule, then this "top down" method of producing it is very different from the method that is usually used to produce large molecules, either in the laboratory or in nature. In fact, the chemical approach would be to produce large molecules by assembling them from smaller ones, i.e. a "bottom up" approach [START_REF] Palma | Blueprinting macromolecular electronics[END_REF] .

While lithographically patterned structures are adequate for large devices, that rely primarily on the two-dimensional electronic properties of graphene, in fact, graphene's promise for electronics, as well as for new fundamental physics, relies primarily on its lower dimensional properties (i.e. nanoribbons and quantum dots). That is, graphene is most interesting when feature sizes are of the order of its Fermi wavelength so that quantum confinement effects manifest themselves. The carbon nanotube, with its well-known size and helicity dependent electronic properties is the archetype for quantum confined graphitic structures. In fact considerations of nanotube properties were the primary motivation for graphitic electronics research [START_REF] Berger | Ultrathin epitaxial graphite: 2D electron gas properties and a route toward graphene-based nanoelectronics[END_REF] .

Graphene is a zero bandgap semiconductor (i.e. a semimetal). Modern digital microelectronics relies on the bandgap of the semiconductor so that field effect transistors can be produced with large on to off switching ratios in order to minimize leakage currents when the transistor is in the "off" state. However, this off condition cannot be reached with 2 dimensional graphene, not even at extremely low temperatures.

While devices based on two-dimensional graphene (i.e. devices with feature sizes greater than a 100 nm) are not considered to be useful for digital electronics, this material is useful for ultrahigh high frequency analog electronics [START_REF] Schwierz | Graphene transistors[END_REF] . Fast graphene transistors have been produced using 2 dimensional graphene. Even though these devices have very small on to off ratios (of the order of 10) they nevertheless have above unity gain at frequencies exceeding 200 GHz [START_REF] Liao | High-speed graphene transistors with a self-aligned nanowire gate[END_REF][START_REF] Lin | Enhanced performance in epitaxial graphene FETs with optimized channel morphology[END_REF] , which brings them in the range of state of the art semiconducting devices [START_REF] Krithivasan | Half-terahertz operation of SiGeHBTs[END_REF] . In order to push these limits ever closer to the THz ranges will require further significant improvements of the graphene performance (as well as reductions in contact resistances and higher quality dielectrics). It should be mentioned that 2 dimensional graphene Hall bars patterned on epitaxial graphene are considered to be important in metrology as quantum Hall based resistance standards [START_REF] Janssen | Anomalously strong pinning of the filling factor ν = 2 in epitaxial graphene[END_REF] .

It was theoretically known that quantum confined structures like graphene ribbons, could have band gaps under certain conditions [START_REF] Nakada | Edge state in graphene ribbons: Nanometer size effect and edge shape dependence[END_REF][START_REF] Wakabayashi | Electronic and magnetic properties of nanographite ribbons[END_REF] . The size of the bandgap Eg is predicted to be of the order of Eg= 1 eV/W where W is the width of the ribbon. Consequently, theoretically, very narrow ribbons can have significant band gaps. There are however caveats. The size of the bandgap depends on the condition of the edge. In fact, theoretically, only graphene ribbons with armchair edges are semiconductors, and for them, only those where the width is an integer multiple of three hexagons [START_REF] Nakada | Edge state in graphene ribbons: Nanometer size effect and edge shape dependence[END_REF][START_REF] Wakabayashi | Electronic and magnetic properties of nanographite ribbons[END_REF] . All other graphene ribbons, including those with zigzag edges and chiral ribbons that are intermediate between zigzag and armchair are all expected to be metallic (in general) [START_REF] Wakabayashi | Edge effect on electronic transport properties of graphene nanoribbons and presence of perfectly conducting channel[END_REF] . Note, however, that theory does predict that bandgaps may open under certain circumstances [START_REF] Son | Energy gaps in graphene nanoribbons[END_REF] .

It should therefore considered to be surprising that several recent papers report that lithographically patterned graphene nanoribbons from exfoliated graphene deposited on SiO2 are all semiconducting with band gaps that are of the order of 1eV/Eg [START_REF] Han | Energy Band-Gap Engineering of Graphene Nanoribbons[END_REF][START_REF] Oostinga | Magnetotransport through graphene nanoribbons[END_REF][START_REF] Stampfer | Energy Gaps in Etched Graphene Nanoribbons[END_REF][START_REF] Gallagher | Disorder-induced gap behavior in graphene nanoribbons[END_REF][START_REF] Han | Electron Transport in Disordered Graphene Nanoribbons[END_REF] . The band gap was established by adjusting the charge density of the patterned graphene ribbon by applying a potential to a Si back gate in the usual way. It was noted that with decreasing charge density the conductance dramatically decreases (by several orders of magnitude) similar to the conductance decrease that is observed in a semiconductor, from which the band gap was determined.

However, it was later determined [START_REF] Oostinga | Magnetotransport through graphene nanoribbons[END_REF][START_REF] Stampfer | Energy Gaps in Etched Graphene Nanoribbons[END_REF][START_REF] Gallagher | Disorder-induced gap behavior in graphene nanoribbons[END_REF][START_REF] Han | Electron Transport in Disordered Graphene Nanoribbons[END_REF] that (in most cases) the band gap was actually a mobility gap. That is, the edges of these patterned ribbons is disordered causing scattering. The rough edges caused the graphene ribbon to resemble a series of "quantum dots" causing strong localization of the charge carriers and a large reduction in the mobility at low charge densities. While an interesting phenomenon in itself, materials that rely on such mobility gaps are not considered to be suitable for high-speed digital electronics.

In order to reduce edge scattering in narrow ribbons requires that edge roughness is reduced. This suggests significant modifications in the patterning method itself. Here we show examples of quality nano-structures produced directly on tailored silicon carbide surfaces without post-growth lithography processing. Progress towards high mobility epitaxial graphene monolayers for device applications is also reported.

Structured monolayer graphene growth on silicon carbide

Epitaxial graphene on silicon carbide ranks among the most promising candidates for large-scale graphene electronics. Epitaxial graphene grown on silicon carbide has several advantages over epitaxial graphene grown on metal substrates. One advantage is, that the material does not need to be transferred from the metal to another dielectric substrate. The SiC substrate is a large band-gap semiconductor widely used in the industry 20 and schemes are developed for integration with Silicon [START_REF] Fukidome | Epitaxial Growth Processes of Graphene on Silicon Substrates[END_REF] . The interface between epitaxial graphene and the silicon carbide substrate is reasonably well understood on the atomic scale [START_REF] Hass | Interface structure of epitaxial graphene grown on 4H-SiC[END_REF] . One of the most important advantages of epitaxially grown graphene sheets, is that here are no trapped impurities under the graphene (although interface can be modified by passivation and intercallation), and it can be readily patterned. Large-area graphene (on both polar faces of SiC) has been grown by several groups [START_REF] Berger | Ultrathin epitaxial graphite: 2D electron gas properties and a route toward graphene-based nanoelectronics[END_REF][START_REF] Lin | Enhanced performance in epitaxial graphene FETs with optimized channel morphology[END_REF][START_REF] Janssen | Anomalously strong pinning of the filling factor ν = 2 in epitaxial graphene[END_REF][START_REF] Fukidome | Epitaxial Growth Processes of Graphene on Silicon Substrates[END_REF][START_REF] De Heer | Large area and structured epitaxial graphene produced by confinement controlled sublimation of silicon carbide[END_REF][START_REF] Emtsev | Towards wafer-size graphene layers by atmospheric pressure graphitization of silicon carbide[END_REF][START_REF] Ohta | Role of carbon surface diffusion on the growth of epitaxial graphene on SiC[END_REF][START_REF] Röhrl | Raman spectra of epitaxial graphene on SiC[END_REF][START_REF] Tiberj | Multiscale investigation of graphene layers on 6H-SiC(000-1)[END_REF][START_REF] Robinson | Epitaxial Graphene Materials Integration: Effects of Dielectric Overlayers on Structural and Electronic Properties[END_REF][START_REF] Waldmann | Bottom-gated epitaxial graphene[END_REF] . There are still progress to be made, however, before large area graphene layers with uniform properties are produced.

Another advantage is, that graphene growth can be directed. That is, by proper tailoring of the substrate, graphene can be grown only where it is desired as shown in detail below. This method of graphene growth circumvents the damaging lithographic patterning step that causes the large mobility drops in the patterned graphene ribbons mentioned above. Moreover, surprisingly, all graphene ribbons produced by this method are found to be metallic. There is no evidence for a band gap, in contrast to lithographically patterned graphenes that show evidence of band gaps or mobility gaps. These observation indicate that scattering at the edges is suppressed compared with ribbons produced using standard lithography methods.

Structured graphene growth is pursued along two distinct tracts: large area graphene growth on the carbon terminated surface, and sidewall graphene structured growth [START_REF] Sprinkle | Scalable templated growth of graphene nanoribbons on SiC[END_REF] on the silicon terminated surfaces. Both of these approaches are treated in detail below.

Structured Cface graphene growth

It is well known that the mobilities of graphene monolayers grown on the (000-1) face (the C-face) are significantly greater (typically by a factor of 3-10) than those graphene on the (0001) face (the Si-face). For this reason considerable effort has expended to control the graphene growth on the C-face, in particular for the 2dimensional mono graphene devices mentioned above. High quality graphene mono-and multilayers have are grown on the C-face of hexagonal silicon carbide (either 6H or 4H) using the confinement controlled sublimation method (CCS) [START_REF] De Heer | Large area and structured epitaxial graphene produced by confinement controlled sublimation of silicon carbide[END_REF] . Briefly, in this method, a silicon carbide chip is heated in vacuum, inside a graphite capsule, that is supplied with a small leak. One or more graphene layers form at temperatures between 1500-1600 C. Uniform monolayer graphene growth is difficult to achieve over the entire 4 x 5 mm SiC chip surface. In particular, while large area growth has been accomplished consisting of a continuous graphene layer covering the entire surface, below this layer (which over most of the area is a monolayer) there are occasionally patches with additional graphene layers. Even though the top-most layer is continuous, these patches affect the transport properties, and ideally they should be eliminated. This sub-layer partial growth is more critical on the Si-face because A-B stacked bilayers don't have the same electronic structure as mono layers. On the C-face the monolayer electronic structure is preserved for multilayers due to the orientational stacking (see below) 31,[START_REF] Faugeras | Few-layer graphene on SiC, pyrolitic graphite, and graphene: A Raman scattering study[END_REF] For quantum-Hall effect-based metrology applications it is important that the graphene is uniform and continuous on predetermined locations, that can then be patterned. While high quality continuous and uniform multilayer epitaxial graphene films are relatively easy to produce [START_REF] De Heer | Large area and structured epitaxial graphene produced by confinement controlled sublimation of silicon carbide[END_REF] , uniform monolayers are still challenging. Progress is described below.

Graphene growth on the C-face nucleates primarily at natural substrate steps [START_REF] Ohta | Role of carbon surface diffusion on the growth of epitaxial graphene on SiC[END_REF] (caused by step bunching), etched steps, and defects like screw dislocations (Figure 1). The monolayer growth patches at steps (Fig. 1a) are uniformly distributed over the silicon carbide chip surface. However, growth at screw dislocations (Fig. 1b) is not controlled and typically results in rather deep cervices covered with mulilayer graphene. It is clear that screw dislocations are an impediment to uniform growth.

Raman spectroscopy is a powerful characterization tool for graphene deposited on silicon oxide and it has been extensively treated in the literature [START_REF] Ferrari | Raman spectrum of graphene and graphene layers[END_REF] . Raman spectra for epitaxial graphene is basically similar however with some significant and important differences [START_REF] Röhrl | Raman spectra of epitaxial graphene on SiC[END_REF][START_REF] Faugeras | Few-layer graphene on SiC, pyrolitic graphite, and graphene: A Raman scattering study[END_REF] . Most importantly, the Raman spectrum of the silicon carbide substrate itself is superimposed on the graphene spectrum with intense features in the range 1500 to 2000 cm -1 (Fig. 2a, red curve). The other characteristic bands (D, G and 2D) are used for diagnostic purposes. For Bernal stacked multilayer graphene, the 2D band evolves as a superposition of peaks due to the evolution of the electronic structure with increasing number of layers that converges to the graphite bandstructure [START_REF] Ferrari | Raman spectrum of graphene and graphene layers[END_REF] . However the evolution in C-face graphene is subtler since each layers has the same electronic structure as that of a single layer . Consequently, the Raman spectra of thick C-face graphene multilayers are essentially identical to that of a monolayer [START_REF] Faugeras | Few-layer graphene on SiC, pyrolitic graphite, and graphene: A Raman scattering study[END_REF] . However, the 2D band does broaden for the first few layers. This broadening is (most likely) primarily caused by the charge density variations from one layer to the next : the bottom most layer is negatively charged (n~5 10 -12 cm -2 ) due to the SiC substrate, while the others are essentially neutral. Shifts in the 2D band due to change in the Fermi level have been discussed in ref [START_REF] Das | Monitoring dopants by Raman scattering in an electrochemically top-gated graphene transistor[END_REF] . Moreover, the top-most layer is (often) p doped due to environmental effects. In any case, as for exfoliated graphene on silicon carbide, monolayer graphene on SiC can be identified by its signature 2D band.

The positions of the G band and the 2D band as a function of charge density for monolayer graphene (on the C-face) are shown in Fig. 2. The charge densities have been determined from the Hall resistance. Note that the charge on a graphene monolayer is the sum of the interface charge and the environmentally induced charge. An epitaxial graphene monolayer is intrinsically negatively charged but it gradually becomes positively charged after exposure to the ambient. Heating in vacuum restores its virgin condition. An increase in the energies of these two Raman bands with increasing charge density (either positive or negative) is also observed in exfoliated graphene. While the increase in the G band agrees quantitatively with that observed for electrostatically gated exfoliated graphene, the shift in the 2D band is significantly larger than that observed in exfoliated graphene. We further note that in contrast to exfoliated graphene, the ratio of the 2D peak intensity and the G band intensity is not a reliable indicator for monolayer graphene as it is found vary from 2 to 9. However, we have found that ratio of the intensity of the G band and the SiC bands is a reliable indicator of the graphene layer thickness, that is particularly accurate in identifying graphene monolayers on the C face. The D band is typically very small in C face graphene indicating low defect densities in the material.

In Figure 3 we present a more detailed analysis of a C-face monolayer including both topographic AFM data and scanning Raman spectroscopy data. Usually a epitaxial graphene on the C-face can be recognized by the pleats as shown in Fig. 3a, however, occasionally an anomalous pleat-free region is observed within a monolayer patch. A micro Raman map of this patch (Fig. 3 b-c) shows that the areas with pleats have a normal Raman spectrum with a peak 2D intensity at 2680 cm -1 , while the Raman spectrum in the anomalous region has its 2D peak intensity at 2760 cm -1 . This shift in the Raman band indicates that this region is probably stressed and more strongly coupled to the substrate than normal.

Attempts to structure silicon carbide, by etching mesas or pits, in order to direct graphene growth on the C face have had good success (Fig. 4). It appears that graphene growth initiates at specific corners of the hexagonal pit etched in C-face SiC. Further work will reveal if this can lead to a process. In the mean time, very high quality monolayer graphene patches that spontaneously form on the SiC surface are optically identified with AFM, ellipsometry, optical transmission or Raman spectroscopy and then patterned using conventional methods.

Electronic transport and devices on the Cface

The enhanced mobilities of C-face graphene is an important consideration for micron scale graphene devices including Hall-bars for metrology as well as high frequency transistors. These larger patterned structures do not rely on quantum confinement but rather exploit the intrinsic two dimensional graphene properties. Hall bar resistance standards are based on the quantum Hall effect that requires high mobility graphene that will exhibit well-developed quantum Hall plateaus at relatively high temperatures (i.e. above cryogenic temperatures 31 ) and relatively low magnetic fields (a few Tesla). Terahertz transistors require graphene that has a high mobility at high charge densities (see below). These transistors (envisioned for telecommunications) will be used for amplifiers and oscillators. They need to have significant gain at high frequencies, but large on to off ratios (that are essential for digital applications) are not required.

Figure 5 presents progress on monolayer epitaxial graphene Hall bars on the C-face that show the characteristic half-integer quantum Hall effect as in ref [START_REF] Wu | Half integer quantum Hall effect in high mobility single layer epitaxial graphene[END_REF] : (a) low charge density allows for QHE plateaus at moderate magnetic field, (b) step free non patterned monolayer flake, (g-f) top-gated single layer. The high mobility graphene (µ~18,000 cm 2 V -1 s -1 at a charge density n~ 10 12 cm -2 ) is typical for the C-face.

More precisely, the negative charge nS~5x 10 12 cm -2 at the interface with SiC, can be partially compensated by exposition to the environment, and tuned from n to p. In Fig 5a, the C-face single layer was coated with PMMA, rinsed in hot acetone and hot water to remove resist residues. The process was repeated several times until the charge density was adjusted to a value well below nS<1x10 12 cm -2 . It is interesting that even at this low density (n-doping nS= 0.19x 10 12 cm -2 ) the resistivity ρxx=800Ω remains low, yielding a Hall mobility µ=1/(nSeρxx)=39,800 cm 2 /Vs. The Hall resistance ρxy is linear at low field (away from the QHE plateaus) and does not present the kink or rounding previously associated with the contribution of multilayers 31 . A higher field, the Hall resistance ρxy shows two very well defined quantum Hall plateaus and the onset of the third one at ρxy=(h/νe 2 ), with the filling factor ν=2, 6 and 10 (ν=4n+2; n=0, 1, 2) expected from single layer graphene. As already observed on both C-and Si-faces [START_REF] Janssen | Anomalously strong pinning of the filling factor ν = 2 in epitaxial graphene[END_REF]31 the ν=2 plateau extends in a large field region, over 4.5 Tesla and up to the highest field, 7 Tesla in this experiment. The resistivity ρxx remains vanishingly small in the plateau region. All these observations corroborate that this is a high mobility low n-doped single layer. Low doping density and high mobility can be finely tuned by environment exposure both for p-and ndoping. This demonstrates that epitaxial graphene can be used as QHE resistance standards even in moderate magnetic field. Similar results are consistently found on all the monolayer epitaxial graphene devices measured, for instance another Hall bar on the same chip gives ρxx=690Ω and µ=12,600 cm 2 /Vs at charge density ns= 0.7 x 10 12 cm -2 . Another example is given on Fig. 5b for a non patterned monolayer (ρxx=320 Ω, µ=21,100 cm 2 /Vs at charge density nS= 0.92 x 10 12 cm -2 ). Here also the ν=2, 6, 10 plateaus are well observed concomitant with zero resistivity at high field. Note also the absence of a sizable localization peak at low field in all devices.

Applying top gate electrodes for individual device switching significantly decreases the mobilities, as already reported [START_REF] Robinson | Epitaxial Graphene Materials Integration: Effects of Dielectric Overlayers on Structural and Electronic Properties[END_REF] . Nevertheless, useful devices can still be made with significantly large mobilities to demonstrate the quantum Hall effect as shown in Fig. 5 d-f. Note that alternative back-gating strategies, which work in a certain temperature range, are useful for global gating in a reduced temperature range [START_REF] Waldmann | Bottom-gated epitaxial graphene[END_REF] . A top gate was deposited on another single layer by evaporating aluminum metal at a slow rate (0.1 A/s) in low vacuum, allowing aluminum to oxidize during deposition.

A subsequent deposition at higher rate (0.9 A/s) covers the alumina with an Aluminum metallic gate. Results for a Hall bar (width 1µm, length 4.3 µm) are presented in Fig. 5d-f. The resistivity as a function of gate voltage at 4K undergoes a maximum for Vg~0.3V, clearly showing the conductance modulation by the electrostatic field on both sides of the Dirac point (Fig. 5f) with a high to low resistivity ratio R(Vg=3V)/Rmax=Ioff/Ion=13. This value is common for 2D single layer graphene. The gate efficiency to change the charge density ns can be directly measured by the linear Hall resistance ρxy for different gate voltages at low field. The gate voltage Vg=0.3V at the Dirac point gives a charge density nS=6.2x10 11 cm -2 induced by the gate to compensate for the natural sample doping. This very close to the doping nS=5.6x10 11 cm -2 measured from ρxy at zero gate voltage.

A gate voltage sweep at 9 Tesla shown in Fig. 5d reveals fully developed quantum hall plateaus at σxy= νe 2 /h for ν=2, 6, 10, 14 (σxy is the transverse conductivity). The plateaus corresponding to resistivity ρxx minima and a vanishing resistivity for the ν=2 plateau clearly demonstrates that this is a single layer. Field sweep at zero gate voltage (in the p-doped region, charge density ns=5.6x10 11 cm -2 , mobility µ=8,500cm 2 /Vs) and at Vg=0.4V, i.e. at a comparable charge density but in the ndoped region (ns=5x10 11 cm -2 , mobility µ=7,200cm 2 /Vs) shows a well resolved ν=2 plateaus, that extends in a large field region. In particular this shows the QHE effect can be switched from p to n using the top gate. Note that the mobility for n doping is significantly lower than for p doping, nevertheless the quantum Hall effect is observed for both polarities. As for other single layer graphene of high mobility a very small and narrow weak localization is observed at zero field.

Finally the reciprocal relation between the resistivity and the charge density nS = 1/(eρxy) is depicted in Fig. 5c for micron size C-face single layer graphene Hall bars. As expected for single layer graphene ρxx increases at low charge density, but it is interesting to note that ρxx is quite low compared to results reported for exfoliated graphene, where ρxx≈(4-6e 2 /h) -1 = 4-6 kΩ [START_REF] Chen | Chargedimpurity scattering in graphene[END_REF] . The resistivity saturates at high charge density to a value remarkably close to the 1/(80 e 2 /h)=320 Ω that was estimated by Orlita et al. [START_REF] Orlita | Approaching the Dirac point in high mobility multi-layer epitaxial graphene[END_REF] from their observation of a scattering time inversely proportional to the energy (  /τ = 0.026E ) in IR spectroscopy measurements for the screened inner layers of multilayered epitaxial graphene. The charge inhomogeneity δnS can be estimated [START_REF] Farmer | Utilization of a Buffered Dielectric to Achieve High Field-Effect Carrier Mobility in Graphene Transistors[END_REF] from the width of ρxx(Vg), for top gated samples. From ρxx=ρs+(eµ n S 2 + δn S 2 ) -1 we find δnS = 2x10 11 cm -2 , ρs = 130 Ω and µ = 8500 cm 2 /Vs (pdoped side) (µ=6200 cm 2 /Vs, n-doped side) for the sample in Fig. 5f, in very good agreement with the Hall mobility values. The δnS values found for the top gated single layers are of the same order as single layer on SiO2. It appears therefore that charge inhomogeneity alone cannot account for the low ρxx values.

The basic structure and characteristics of a high frequency graphene field effect transistor is shown in Fig. 6. The device has elongated source, drain and gate structures (typically of the order of several microns) in order to ensure high current operation. The other dimensions are optimized for high frequency performance. In particular the channel is ideally short and the contact resistances are ideally low [START_REF] Schwierz | Graphene transistors[END_REF][START_REF] Krithivasan | Half-terahertz operation of SiGeHBTs[END_REF] . Parasitic capacitances between the various components are designed to be as small as possible. While the highest frequency operation of graphene based transistors has slowing been inching up, the current goal of THz operation has not yet been achieved. However the problems appear to be primarily technical and surmountable [START_REF] Liao | Sub-100 nm Channel Length Graphene Transistors[END_REF] . While epitaxial graphene as a viable channel material for THz applications has been established, there are still considerable problems in providing low resistance leads, which determine the access resistance. This may be surprising since from Fig. 5c, the conductivity of (doped) graphene (≈10µΩcm) is comparable to that of copper at room temperature. Nevertheless, the minimum resistance of a graphene lead (the so called access resistance) is of the order of a few hundred Ω per square so that for example, the source lead with a length to width aspect ratio of 10 to 1 has a resistance of several kΩ. This can be reduced by cladding the graphene with a metal, however the metal to graphene resistance is also large. Currently the minimum access resistance reported is about 350 Ω per micron of channel width [START_REF] Lin | Enhanced performance in epitaxial graphene FETs with optimized channel morphology[END_REF] . This is still too large for THz applications.

Structured growth on the Si face.

Graphene is known to nucleate at step edges and growth rates are known to depend on the crystal face. Growth is considerably slower on the Si face than on the C face. These facts are advantageously used in the structured growth method (also called the templated growth method [START_REF] Sprinkle | Scalable templated growth of graphene nanoribbons on SiC[END_REF] ) where the silicon carbide surface is first etched to produce steps. During the high temperature annealing using the CCS method, the etched steps crystallize and a graphene film forms on them. The growth times and temperatures are adjusted so that a monolayer graphene film forms only on the step edges and not (or minimally) on the (0001) surfaces.

High temperature annealing causes vertically etched steps (on the order of 10 nm deep) to produce (1-10n) facets with a normal that has an angle of 23 deg with respect to the {0001} direction.

Cross sectional, high resolution transmission electron microscopy by Norimatsu et al. [START_REF] Norimatsu | Formation process of graphene on SiC[END_REF] of the graphene on steps on SiC have shown that the graphene terminates perpendicular to the silicon carbide surface both on the bottom of the step or on the steps themselves. This effect has also been observed using scanning tunneling microscopy on small graphene islands on (0001) SiC [START_REF] Tiberj | Multiscale investigation of graphene layers on 6H-SiC(000-1)[END_REF] . Moreover, these atomic resolution studies further show, that the graphene edges are along the zigzag direction, indicating that the graphene sidewall ribbons are zigzag ribbons. This is very important since the edge structure determines the electronic properties of the ribbons. In particular, zigzag ribbons are always metallic [START_REF] Wakabayashi | Edge effect on electronic transport properties of graphene nanoribbons and presence of perfectly conducting channel[END_REF] .

As noted by Kusunoki et al [START_REF] Kusunoki | Selective synthesis of zigzag-type aligned carbon nanotubes on SiC (0 0 0 )1) wafers[END_REF] , the zigzag nature of the graphene edges is further confirmed in electron diffraction images of carbon nanotubes grown on SiC, which always are of the zigzag variety, which indicates that they terminate with a zigzag edge on the silicon carbide surface. This very important observation, that sidewall graphene ribbons have zigzag edges that terminate in the silicon carbide has profound implications for graphene nano-electronics. For one thing, it implies that the edges are passivated and well defined, that is, they are not subject to the chemical reactivity and the structural disorder of lithographically patterned graphene structures.

The procedure to produce sidewall graphene structures is outlined next (see also Fig. 7). The Si face of 4H (or 6H) SiC is lithographically patterned in using standard lithography methods to produce an etch mask (using, for example, a lithographic resist such as PMMA) on the surface. The masked surface is then subjected to a plasma etched (typically with SF6) to etch the desired pattern to a predetermined depth into the surface. This procedure can be repeated several times to produce structures with varying depths. Alternatively, wide ribbons can be produced by fusing narrower ribbons as shown in Fig. 7b. The resulting structure is then annealed using the CCS method [START_REF] De Heer | Large area and structured epitaxial graphene produced by confinement controlled sublimation of silicon carbide[END_REF] at a temperature of about 1550 C for about 10 minutes, which anneals the steps (typically producing on facets where n ranges from 1 for shallow trenches to about 10 for deep ones) with typically a monolayer of graphene on the steps. Next, if desired, gate structures can be patterned on top of the sidewall ribbons in the usual way. It is occasionally desirable to etch away spurious graphene ribbons that have formed on the sidewalls of steps on the substrate that are inevitably present due to the slight miscut of the original crystal (Fig. 7a). However, judicious choice of the orientation of the patterned structure with respect to the miscut, minimizes this problem.

Figure 7 shows several examples of several sidewall graphene structures produced by this method, to demonstrate its effectiveness. Atomic force microscopy (AFM) images present the topography, while electrostatic force images (EFM) provide a characteristic contrast that distinguishes graphene from silicon carbide (Fig. 7).

Narrow graphene ribbons are particularly important for graphene based nanoelectronics. As mentioned above, sidewall ribbons are expected to have zigzag edges, which we find are (always) metallic. It should be noted that, on the contrary, all graphene ribbons produced to date using standard lithography methods are found to be semiconducting, i.e. have a transport gap a low temperature or close to the charge neutrality point. This is actually not expected since graphene ribbons are generally expected to be metallic [START_REF] Wakabayashi | Edge effect on electronic transport properties of graphene nanoribbons and presence of perfectly conducting channel[END_REF] (the only exception being specific graphene ribbons with armchair edges mentioned above). It is now generally accepted that the bandgaps observed in narrow graphene ribbons produced by standard lithography methods are in fact mobility gaps caused by the rough edges [START_REF] Oostinga | Magnetotransport through graphene nanoribbons[END_REF][START_REF] Stampfer | Energy Gaps in Etched Graphene Nanoribbons[END_REF][START_REF] Gallagher | Disorder-induced gap behavior in graphene nanoribbons[END_REF][START_REF] Han | Electron Transport in Disordered Graphene Nanoribbons[END_REF] . In contrast all of the gated sidewall graphene ribbons produced by the methods outlined here are metallic, consistent with expectations. Moreover, we have observed that a majority of these sidewall ribbons show evidence of (quasi) ballistic transport involving a single conducting channel with mean free paths on the order of 1 µm, which is significantly greater than the typical mean free path in 2D graphene. The narrow graphene ribbons produced for these studies are produced as follows (see Fig. 8).

Two opposing deep (>100 nm) U shaped trenches are first etched. Subsequently a narrow (~10 nm) trench is etched, connecting the U trenches (Fig 8 a). After CCS thermal annealing, the sidewalls of the U trenches form the broad graphene leads for the two narrow graphene sidewall ribbons between the U's. Metal contacts provided to the graphene leads allow for 4-point transport measurements of the graphene ribbon. Figure 8 provides some details of the production and characterization methods used. Specifically, as shown, the EFM resolution of is 30 nm, which is considerably greater than that of Raman (with about 1µm resolution) for detecting graphene nanostructures. Moreover the EFM method can be improved, by modeling the tip to graphene interaction, to provide a resolution of 10 nm.

While structured graphene is most suited for graphene nanostructures, it can also be used for Hall bars and other micron sized devices. An example is shown in Fig. 9 where a graphene ribbon that is about one micron wide and several microns long is connected to 6 leads in the Hall bar configuration for transport measurements. For this sample, a distinct anomalous diode like effect is observed in this ribbon when the resistance is measured between two opposing electrodes as shown in Fig. 9c. Ideally, the resistance (in the absence of a magnetic field) is expected to be zero, however a significant resistance is obtained. This normally indicates a misalignment of the voltage contacts. However the diode-like behavior signifies that nonlinear effects are playing a role. Note that at 4 K, the resistance even changes sign. Similar non-linear properties are seen in nanoscopic phase coherent ballistic junctions and it is expected that coherent transport plays a role in this case as well. This interpretation is fortified by the observation that the anomalous behavior vanishes at room temperature, which is consistent with expected reduction in the phase coherence length (to < 20 nm) at room temperatures.

Conclusion

We have presented recent results on a variety of patterned graphene structures, on the carbon terminated faces of hexagonal silicon carbide. We have demonstrated that structured graphene growth is a powerful and flexible method to control the shapes of the graphene structures and that a wide variety of structures can be produced both for fundamental studies as well as for applications. It presents an important step towards the realization of high mobility quasi one dimensional graphene structures that do not suffer from the strong localization effects observed in conventionally patterned graphene structures, that all but obviate graphene's advantages at the nanoscale.

FIG 1 .

 1 FIG 1.AFM and optical images of graphene the 000-1 face of 4H-SiC . (a) AFM image of monolayer graphene on a stepped 000-1 surface, the graphene layer exhibits pleats (bright lines) and is confined to the central patch. Note the molted appearance of the areas not covered by graphene. Bright spots are due to postproduction contamination; (b) AFM image of a monolayer graphene patch draped over the distinct central stepped region of the image that extends to the top. (c) Optical image of monolayer graphene growth around etched trenches in the SiC surface (that resulted from random cracks in the polymer etch mask). The graphene stands out as slightly brighter patches decorating the dark trenches. (d) Mulilayer graphene growth at a screw dislocation.

FIG 2 .FIG 3 .FIG 4 .

 234 FIG 2. (a) Typical examples of micro Raman spectra used to identify monolayer graphene, black trace: graphene, red trace, bare SiC substrate (Raman laser wavelength λ =532nm, spectral resolution Δ =0.3cm -1 ). Note the G band at 1585 cm -1 and the prominent 2D band at 2685 cm -1 that can be fit with a single Lorentzian (with a typical width of 30 cm -1 ). (b) peak position of the G band; (c) peak position of the 2D band as a function of charge density.

FIG 5 .

 5 FIG 5. The quantum Hall effect in epitaxial graphene C-face for micron wide Hall samples. (a) C-face Hall bar (µ=39,800 cm 2 V -1 s -1 , n= 0.19x10 12 cm -2 ) ; (b) C-face monolayer Hall bar (µ=21,100 cm 2 V -1 s -1 , n= 0.92x10 12 cm -2 ) ; (c) Plot of resistivity versus charge density for micrometer size single layer C-face Hall bars. The dotted line correspond to ρ=(80e 2 /h) -1 from ref. 42 ; (d-f) top gated C-face Hall bar (1µmx 4.3µm). (d) Resistivity ρxx (black) and Hall conductance σxy (red) versus gate voltage at 4K and 9 T, showing plateaus in the n-and p-doped regimes; (e) Hall resistance ρxy, measured at two gate voltages and sweeping the magnetic field. The mobility for n doping is 6200 cm V -1 s -1 and for p doping it is 8500 cm V -1 s -1 . A significant reduction in the mobility (compared with bare samples above) is caused by the application of the top gate; (f) Resistivity ρxx as a function of gate voltage at 4K and zero magnetic field; Inset: the measured Hall bar.

FIG 8 .FIG 9 .

 89 FIG 8. Examples of structured graphene nanoribbon and connection for 4-probe measurement (a) AFM image of U-shped deep trenches connecting a shallow trench overlapped with EFM of a Hall bar structure. (b-d) zoom on the shallow trench (b) AFM image after SiC patterning, (c) AFM image after subsequent graphitization, showing the rounding of the trench due to SiC step flow at high temperature (d) EFM image of (c) showing two nanoribbons grown on the side wall of the trench. From ref 30 .

Sidewall graphene growth along patterned SiC surface that was etched to a depth of 15 nm. Note the serpentine sidewall that was etched to provide for a wide lead (after annealing) for the narrow, straight ribbon segments, demonstrating the flexibility of the method. (c) Graphene ring supplied with leads. The original patterned SiC structure consisted of a circular SiC mesa connected to radial SiC walls. Graphene grown on the sidewall of the mesa produced the graphene ring and graphene grown on the walls produced the leads. HSQ was used as etching mask. (d) Array of graphene nanoribbons. Narrow parallel groves were patterned covering the entire SiC chip. More than 30% of the surface is covered with graphene ribbons. The SiC etching depth was 150nm and photolithography was used to produce the Ni etching mask.