Anna Bernasconi
email: anna.bernasconi@unipi.it

Antonio Boffa

Fabrizio Luccio
email: fabrizio.luccio@unipi.it

Linda Pagli
email: linda.pagli@unipi.it

The Connection Layout in a Lattice of Four-Terminal Switches

A non classical approach to the logic synthesis of Boolean functions based on switching lattices is considered, for which deriving a feasible layout has not been previously studied. All switches controlled by the same literal must be connected together and to an input lead of the chip, and the layout of such connections must be realized in superimposed layers. Inter-layer connections are realized with vias, with the overall goal of minimizing the number of layers needed. The problem shows new interesting combinatorial and algorithmic aspects. Since the specific lattice cell where each switch is placed can be decided with a certain amount of freedom, and one literal among several may be assigned for controlling a switch, we first study a lattice rearrangement (Problem 1) and a literal assignment (Problem 2), to place in adjacent cells as many switches controlled by the same literal as possible. Then we study how to build a feasible layout of connections onto different layers using a minimum number of such layers (Problem 3). We prove that Problem 2 is NP-hard, and Problems 1 and 3 appear also intractable. Therefore we propose heuristic algorithms for the three phases that show an encouraging performance on a set of standard benchmarks.

Introduction

The logic synthesis of a Boolean function is the procedure for implementing the function into an electronic circuit. The literature on this subject is extremely vast and large part of it is devoted to two-level logic synthesis, where the function is implemented in a NAND or NOR circuit of maximal depth 2 [?]. In this paper, we focus on a different synthesis method based on a switching lattice, that is a two-dimensional array of four-terminal switches implemented in its cells. Each switch is linked to the four neighbors and is connected with them when the switch is ON, or is disconnected when the switch is OFF.

The idea of using regular two-dimensional arrays of switches to implement Boolean functions dates back to a seminal paper by Akers in 1972 [?]. Recently, with the advent of a variety of emerging nanoscale technologies based on regular arrays of switches, synthesis methods targeting lattices of multi-terminal switches have found a renewed interest [?,?,?]. A Boolean function can be implemented in a lattice with the following rules:

each switch is controlled by a Boolean literal, i.e. by one of the input variables or by its complement;

(a)

x 1

x 1

x 2

x 3

x 2

x 3

x 3

x if a literal takes the value 1 all corresponding switches are connected to their four neighbors, else they are not connected; the function evaluates to 1 for any input assignment that produces a connected path between two opposing edges of the lattice, e.g., the top and the bottom edges; the function evaluates to 0 for any input assignment that does not produce such a path.

For instance, the 3 × 3 lattice of switches and corresponding literals in Figure 1-a implements the function f = x 1 x 2 x 3 +x 1 x 3 +x 2 x 3 . If we assign the values 1, 0, 0 to the variables x 1 , x 2 , x 3 , respectively, we obtain paths of 1's connecting the top and the bottom edges of the lattices (Figure 1-b), and f evaluates to 1. On the contrary, the assignment x 1 = 1, x 2 = 0, x 3 = 1, on which f evaluates to 0, does not produce any path from the top to the bottom edge (Figure 1-c). All the other input assignments can be similarly checked.

The synthesis of a function f on a lattice consists of finding an assignment of input literals to the switches, such that the top-bottom paths in the lattice implement f and the number of switches in the lattice is reduced as much as possible. Recalling that the dual f D of a function f is such that f D (x 1 , . . . , x n ) = f (x 1 , . . . , x n ), in [?,?] Altun and Riedel developed a synthesis method where the implicants (products) of the minimal irredundant SOP forms of the function f and of its dual f D are respectively associated, in any order, to the columns and to the rows of the lattice. The literal assigned to a switch is chosen from the necessarily non-void intersection of the two subsets of literals appearing in the implicants corresponding to the intersecting column and row of the lattice. If several literals appear in the intersection anyone of them can be chosen. As an elementary example consider the function f = x 1 x 3 x 4 + x 1 x 2 + x 1 x 3 x 4 and its dual f D = x 1 x 3 + x 1 x 4 + x 2 x 3 + x 1 x 2 x 4 . Figure 2-a shows the lattice for f where just one multiple assignment x 1 , x 3 occurs.

Starting from the lattice obtained by the Altun-Riedel method we consider three problems related to the physical implementation of the circuit, that must be solved obeying the following assumptions.

(a)

x 1 x 1 x 2

x 3

x 4

x 1

x 3

x 3

x 1 x 3

x 2 x 1 x 4 (b)

x 1 x 1 x 2 x 3 x 1 x 3 x 1 x 2 x 4 x 4 x 3 x 3 x 1 (c) x 1 x 1 x 2 x 3 x 1 x 3 x 1 x 2 x 4 x 4 x 3 x 3 x 1 Fig. 2. A lattice implementing the function x1x3x4 + x1x2 + x1x3x4 (a)
, where a choice between x1 and x3 must be performed in the first cell. The lattice after column permutation (b), and then row permutation (c), obtained with our method.

1. Equal literals must be connected together, and to an external terminal on one side (e.g. the top edge) of the lattice. This may require using different layers, and vias to connect cells of adjacent layers. 2. Connections can be laid out horizontally or vertically (but not diagonally) between adjacent cells. 3. Each cell can be occupied by a switch, or by a portion of a connecting wire, or by a via. No two such elements can share a cell on the same layer. In particular the connections cannot cross on the same layer. 4. The overall target is designing a layout with the minimum number of layers.

Since the problem is computationally-hard, it will be relaxed to finding a reasonable layout by heuristic techniques.

The circuit will be built starting from the original N × M lattice (level 0), and superimposing to it a certain number H of layers (levels 1 to H), to give rise to a three-dimensional grid of size N × M × (H + 1). Note that the switches associated with the same literal cannot be generally connected all together on the same layer, so one or more subsets of these switches will be connected on a layer and then made available through vias on the next layers to be connected to other subsets.

Two degrees of freedom remain after the function has been synthesized, to be used to reduce the number of layers in the layout. One is the possibility of permuting lattice columns and rows arbitrarily, as exploited in the following Problem 1. The other is the possibility of selecting any literal from a multiple choice for each switch, as exploited in the following Problem 2. Problems 1 and 2 apply at level 0, preparing the lattice for the actual layout design which takes place in the next layers 1 to H, where the inputs of the switches associated with the same literal are connected together and to the corresponding external lead, as treated in the following Problem 3.

Problems 1, 2, and 3 are solved one after the other, each producing the input for the next one. Since all of them are computationally-hard, we solve them heuristically, then show experimentally that our solutions are efficient for standard benchmarks where the size of the lattice and the number of variables are reasonable. A preliminary version of this study limited to Problem 2 (without a proof on NP-hardness) and to Problem 3 has been presented in [?].

Rearranging the lattice

In principle a lattice can be seen as an array A[N × M ], or as a non-directed graph G = (V, E) whose vertices correspond to the lattice cells (then |V | = N M ) and whose edges correspond to the horizontal and vertical connections between adjacent cells (then

|E| = 2N M -N -M ). We shall refer indifferently to a lattice cell A[i, j], 1 ≤ i ≤ N, 1 ≤ j ≤ M , or to graph vertex v k , 1 ≤ k ≤ N M .
Obviously the vertices have degree 2, 3, or 4 if they respectively correspond to corner, border, or internal cells of the lattice.

Let x 1 , x 2 , . . . , x n be the variables of the function and L be the set of all literals, |L| = 2n. After the Altun-Rieder synthesis is completed, each cell A[i, j] is associated with a non-void subset L i,j ∈ L, from which one literal has to be eventually assigned to the corresponding graph vertex. We pose: Definition 1. If a single variable is associated to each vertex, an mc-area is a maximal connected subgraph S of G in which all variables hold the same literal. Equivalently an mc-area is the portion of the lattice corresponding to S.

Note that if two mc-areas A 1 , A 2 hold the same literal, no two cells c 1 ∈ A 1 , c 2 ∈ A 2 may be adjacent since A 1 and A 2 are maximal.

A basic task is minimizing the number of mc-areas, or equivalently make them as large as possible, since this will imply reducing the number of layers. As shown below the core of this problem is NP-hard, so we study how to solve it heuristically. As already said we proceed in two consecutive phases. The first phase is aimed at permuting columns and rows in order to increase the number of adjacent cells holding common literals, even though subsets of two or more literals may still be associated to each cell. The second phase consists of the selection of one literal in each of the multiple assignments at the cells, so the mc-areas can be built according to Definition 1. To implement the first phase we pose: Definition 2. The weight of a pair of cells A[r, s], A [u, v] is given by: w

u,v r,s = |L r,s ∩ L u,v |/(|L r,s | • |L u,v |). For example for L r,s = {a, b, c}, L u,v = {b, c, d, e} we have L r,s ∩ L u,v = {b, c}, then: w u,v
r,s = 2/(3 • 4) = 1/6. Note that w u,v r,s is the probability for A[r, s], A[u, v] to share the same literal if one literal is randomly chosen from L r,s and L u,v .

The weight is relevant in our case for pairs of adjacent cells. As we are interested in building large mc-areas, we pose: Problem 1. Find a column permutation and a row permutation of A, to maximize the sum of weights of the pairs of adjacent cells.

Once Problem 1 has been solved, one literal must be selected in each subset L i,j as stated in the following: Problem 2. Find a literal assignment for each cell A[i, j] that minimizes the number of mc-areas.

Solving Problem 1

To ease the task of Problem 1, an elementary observation is in order:

Observation 1 Two cells can be made adjacent by column or row permutation if and only if they lay on the same row or on the same column, respectively.

By Observation 1, column and row permutations can be independently performed since the result of one does not affect the result of the other. In fact the problem will be solved by a column permutation followed by a row permutation. We pose: Definition 3. The weight C s,v of a pair of columns s, v of the lattice is the sum of weights of all the pairs of cells lying in the columns s, v and in the same row, that is:

C s,v = N i=1 w i,v i,s .
And, simmetrically:

Definition 4. The weight R r,u of a pair of rows r, u of the lattice is the sum of weights of all the pairs of cells lying in the rows r, u and in the same column, that is: R r,u = M j=1 w u,j r,j .

For building large mc-areas we are interested in bringing adjacent pairs of columns and rows with higher weights, via permutations. To this end we adopt the following heuristic on the columns, then on the rows.

1. compute the weights C s,v of all pairs of columns; 2. build a stack S whose elements contain the pairs (s, v) with non-zero weights, ordered for decreasing value of such weights; 3. start with M subsets of adjacent columns, each containing exactly one of them; 4. pop one by one the pairs (s, v) from S: for the pair currently extracted decide a column re-arrangement (without actually performing it), merging two subsets of adjacent columns, one containing column s and the other containing column v, if the two columns can be made adjacent without breaking the subsets already built. The columns in each subset are kept ordered for increasing value of their index. This step 4 is performed according to the scheme COLUMN-PERM shown below; 5. once the stack S is empty, permute the groups of columns as indicated in the corresponding subsets previously determined. These groups can then be arranged in the lattice in any order.

COLUMN-PERMUTE 1. define a vector P of M elements, whose values are: P [j] = 1 if column j forms a subset of one column; P [j] = 2 if column j is the first one in a subset of more than one column; P [j] = 3 if column j is the last one in a subset of more than one column; P [j] = 4 if column j is neither the first one nor the last one in a subset of more than two columns;

2. initialize P as P [j] = 1 for 1 ≤ j ≤ M ; // all the initial subsets of columns contain one element: // recall that S is a stack of pairs of columns;

3. while S is not empty pop a pair (s, v) from S; 4. the process ends with one or more subsets each corresponding to the permutation of a group of columns.

if (P [s] = 4 OR P [v] = 4) discard (s, v)
After column permutation, the rows are permuted with a procedure perfectly symmetrical to the one given for columns, using row weights R r,u .

In the lattice of Figure 2 (a), the pairs of columns in S with non-zero weights, ordered for decreasing values of the corresponding weights are:

(1,2) C 1,2 = 3/2, (1,3) C 1,3 = 3/2
producing the subsets of adjacent columns {1, 2}, {3} and then {3, 1, 2}, from which the column permutation of Figure 2 (b) is built. The ordered pairs of rows in S with non-zero weights are:

(1,2) R 1,2 = 3/2, (1,3) R 1,3 = 3/2, (3,4) R 3,4 = 1
producing the subsets of adjacent rows {1, 2}, {3}, {4}, {3, 1, 2}, {4}, and then {4, 3, 1, 2}, from which the final row permutation of Figure 2 (c) is built.

A global measure W of the amount of adjacent equal variables in the whole lattice, called the lattice weight, is naturally given by the sum of weights of all pairs of adjacent cells, or equivalently by the sum of weights of all the pairs of adjacent columns and rows, namely:

W = M -1 j=1 C j,j+1 + N -1 i=1 R i,i+1 .
In fact an increase of the value of W can be seen as an indicator of the advantage deriving from a column-row permutation. In the example of Figure 2 the lattice weight increases from W = 4 (part (a)) to W = 7 (part (c) after column and row permutation). In the simulations discussed in the last section such value roughly doubles on the average after the heuristic for Problem 1 is applied.

Implemented with standard data structures, the time required by the above heuristic is O(N M 2 n + M N 2 n) versus O(N M n) of the input size (recall that n is the number of variables).

Hardness of Problem 1

Although our heuristic for Problem 1 shows an encouraging experimental value, a weakness derives from the decision of not restructuring a subset of columns/rows after it is built, aside from possibly inverting the order of its elements. Merging two subsets in a strictly optimal way would lead to an exponential explosion of the time needed with a possibly minor improvement of the result. Up to now we have not been able to decide the time complexity of the problem, although we believe that is NP-hard. We simply pose the question of its precise hardness as a challenging open problem.

Solving Problem 2

Problem 2 is of high computational interest for two reasons. The first is that the number of prime implicants in f and f D strongly increases with the number of variables of the function, so that the elementary examples that we have given so far do not show the real entity of the phenomenon. In particular the possibility of having multiple assignments of many literals in the lattice cells is substantially high, making Problem 2 a crucial part of lattice rearrangement. The second reason is that Problem 2 is NP-hard as we will prove in the next subsection, so a clever heuristic must be devised for its solution. To this end a preliminary exam of the lattice is performed by applying the following Rule 1, with the attempt of reducing the number of literals contained in the subsets associated to the vertices.

Rule 1. Let v j be a vertex; v 1 , v 2 , v 3 , v 4 be the four vertices adjacent to v j (if any); L j , L 1 , L 2 , L 3 , L 4 be the relative subsets of literals. Apply in sequence the following steps:

Step 1. Let |L j | > 1. If a literal x ∈ L j does not appear in any of the sets L i , for 1 ≤ i ≤ 4, cancel x from L j and repeat the step until at least one element remains in L j .

Step 2. Let |L j | > 1, and let L k ⊂ L j with k ∈ {1, 2, 3, 4}. If a literal x ∈ L j appears in exactly one set L h with h ∈ {1, 2, 3, 4} and h = k, then cancel x from L j and repeat the step until at least the literals of L k remain in L j .

We have: Proposition 1. The application of Rule 1 does not prevent finding a literal assignment that minimizes the number of mc-areas.

Proof. Assume that a literal x canceled from v j by Step 1 or Step 2 of the rule would instead be assigned to v j in the final assignment.

Step 1. An mc-area containing only v j with literal x would result. If, in a minimal solution, a different literal y is assigned to v j and is not assigned to v 1 , v 2 , v 3 , or v 4 , the number of mc-areas remains the same. If instead y is assigned to one or more of these vertices the number of mc-areas decreases.

Step 2. If x is not assigned to v h an mc-area containing only v j with literal x would result, otherwise an mc-area containing v j , v h , and possibly other vertices with literal x would result. Since one of the literals y ∈ L k must be assigned to v k in any minimal assignment, and L k ⊂ L j , then y could be assigned to v j instead of x and the number of mc-areas would remain the same, or would decrease if y is assigned also to other neighbors of v j .

2

An example of application of step 2 of Rule 1 is shown in Figure 3. A literal cancelation from L j may induce a further cancelation in an adjacent cell. In the example of Figure 3, if all the cells adjacent to v h except for v j do not contain the literal c, the cancelation of c from L j induces the cancelation of c from L h if step 1 of Rule 1 is subsequently applied to v h . Before running an algorithm for solving Problem 2, the sets L i may be reduced using Rule 1 through a scanning of the lattice. This is a simple task, although a clever data structure must be devised for reducing the time required. Moreover several successive lattice scans may be applied for further reduction until no change occurs in a whole scan, although this is likely to produce much less cancelations than the first scan. These operations constitutes the first phase of any algorithm. Then, as the problem is computationally intractable, a heuristic must be applied. The following algorithm MC-AREAS proposed here, and already experimented in [?], builds each mc-area as a BFS tree, looking for a subset of adjacent vertices that share a same literal and assigning that literal to them. The lattice is treated as a tree.

MC-AREAS

start from a vertex vi and reduce the associated set of literals

Li to just one of its elements li chosen at random; vi will be the root of a tree Ti under construction for the current mc-area;

2. traverse the lattice from vi in BFS form: forany vertex vj encountered such that vj does not belong to a BFS tree already built: if (li ∈ Lj) assign li to vj and insert vj into Ti else insert vj into a queue Q; continue the traversal for Ti;

3. if (Q is not empy) extract a new vertex vi from Q
and repeat steps 1 and 2 to build a new tree;

The experimental results discussed in the last section are derived following this approach. Better results would be possibly obtained with more skilled heuristics at the cost of a greater running time.

Hardness of Problem 2

To prove that Problem 2 is NP-hard we formulate it in graph form as done in [?] where the proof appeared. Let G = (V, E) be an undirected graph and let C be a set of k colors such that each vertex v i ∈ V is associated to (or "contains") a non-void subset C i of C. The graph problem equivalent to ours, indicated as MPA for minimal partition (color) assignment, is the one of assigning to each vertex v i of G a single color from among the ones in C i such that the number σ of maximal connected subgraphs of G 1 , . . . , G σ of G whose vertices have the same color is minimal. Dealing with a lattice, as required in our Problem 2, it is sufficient to start with PMPA, that is the MPA problem where G is planar. We have:

Proposition 2. The PMPA Problem is NP-hard.

Proof. Reduction from planar graph 3-coloring. Let H be an arbitrary planar graph to be 3-colored with colors 1, 2, 3, and let G be a corresponding planar graph whose MPA must be built. The set of colors of G is {1, 2, 3, 4, 5, 6, 7, 8, 9}. For each edge e = (u, v) of H there are nine vertices u, e, v, x 1 , x 2 , x 3 , y 1 , y 2 , y 3 in G connected as shown in Figure 4, with subsets of colors:

C u = {1, 2, 3}, C v = {1, 2, 3}, C e = {4, 5, 6, 7, 8, 9}, C x1 = {1, 6, 7, 8, 9}, C x2 = {2, 4, 5, 8, 9}, C x3 {3, 4, 5, 6, 7}, C y1 = {1, 4, 5, 6, 9}, C y2 = {2, 5, 6, 7, 8}, C y3 {3, 4, 7, 8, 9}.
Consider a minimal collection of monochromatic connected subgraphs G 1 , . . . , G σ of G. We have: (1) the vertices u, v must belong to two distinct subgraphs G i , G j and the vertex e cannot belong to

G i or to G j because C e ∩ C u = ∅ and C e ∩ C v = ∅;
(2) at most one of the vertices x 1 , x 2 , x 3 may belong to G i and at most one of the vertices y 1 , y 2 , y 3 may belong to G j due to their colors; (3) at most two of the vertices x 1 , x 2 , x 3 and at most two of the vertices y 1 , y 2 , y 3 may belong to the same subgraph of e implying that the colors assigned to u and v must be different due to the colors of all the vertices involved. Letting G = (V, E), from the points 1, 2, and 3 we have Starting from Theorem 2 we now prove that the result holds true even for planar grid-graphs GMPA as in the case of our lattice.

Proposition 3. The GMPA Problem is NP-hard.

Proof. We proceed in two steps. First we prove the result holds true for planar graphs of bounded vertex degree d ≥ 3 by reduction from PMPA. Then we pass from bounded degree planar graphs to GMPA. for embedding the edges of G as non intersecting sequences of cells in i, j directions. In [?] was then shown that one such embedding can be built where all edges are just straight line segments. 3. Build the embedding on Γ , and extend the grid to a new grid Γ as follows.

If two horizontal sequences of cells representing two edges of G lie in two rows i, i + 1 and part of these sequences share the same columns (i.e. the two sequences are partly adjacent), insert a new empty row between i and i + 1, using its cells where needed to fix vertical sequences possibly interrupted by the new row. Repeat the operation for any pair of partly adjacent sequences.

Repeat the process on the columns, inserting new columns until no vertical sequences are partly adjacent. Note that the construction of Γ has been done in time and space polynomial in n. Discard the subsets of cells with color c, and in any other subset take only the cells corresponding to original vertices of G. These subsets constitute a solution for a bounded degree PMPA. 2

3 Solving Problem 3

After Problem 2 is solved, we have to choose how to connect the different mcareas associated with the same literal and then connect them to the external input leads. To this end different layers are needed to attain all non-crossing connections. Formally we pose the following problem:

Problem 3: Find a minimum number of layers allowing to connect together all the mc-areas with the same literal, and to connect them to the input leads, obeying the assumptions 1 to 4 of Section 1.

The solution has to be constructive, that is, the actual layout must be shown.

In order to better understand the problem let us discuss an example. We start from a lattice of N × M cells each associated to one of the 2n input literals. Figure 5 shows a 5 × 6 lattice with 7 literals indicated for simplicity with the numbers 1 to 7. In practical applications we usually have 2n < N × M , hence there are cells assigned to the same literal that must be connected together to be reached in parallel from outside. Recall that these literals may be grouped in the mc-areas deriving from the previous lattice rearrangement. The starting lattice constitutes layer 0 of the layout, above which the connections are to be built in successive layers.

Suppose that the input leads to the circuit are in the top edge of the lattice. In layer 1 the only connections we can lay out are those of the mc-areas, and the mc-areas with cells in the top row may also be connected outside, see Figure 6 (a). Note that in layer 1 there is no room for other connections, hence a new layer 2 must be added. For each of the mc-areas connected in layer 1 and holding a literal that appears also in other mc-areas, or not yet connected to the outside, a single cell is connected through a via to the next layer. The final number of layers may be affected by the specific selection of these cells, however, in our heuristic we do not consider this point and choose the positions of the vias arbitrarily. In the layers of Figure 6 the underlined literals indicate where the corresponding vias start.

A possible implementation of the second layer is shown in Figure 6 (b). Each surviving mc-area is now represented by the arrival of a via. Recall that connections cannot cross, hence in general not all areas can be connected. Note that areas already connected to the top edge don't need to be connected to the this edge again, even though they are not completely connected among each other. This is the case of the area associated with literal 1, while areas associated with literals 3, 6, and 7 have still to be connected to the top edge. Note also that all literals with label 4 can be connected in a single area and outside, therefore there is no need to connect this area to the next layer.

The next layer 3 is depicted in Figure 6 (c) where one on the two areas of literal 3 can be connected to the top edge, but these two areas are still to be connected to one another. In this layer the connections for literals 2 and 5 are completed, while vias for literals 3, 6, and 7 are arbitrarily chosen. In the last layer 4 the layout is completed as shown in Figure 6 (d).

Impossible instances

To address Problem 3 formally we must start with a crucial observation, namely not all instances of it are solvable no matter how many layers are used. As an introduction consider the lattice of Figure 7 where each row contains a cyclic shift of the literals in the previous row and all these shift are different. It is easy to see that no cells with the same literal can be connected together independently of any column/row permutation. We now show that the vast majority of problem instances are theoretically solvable, although some may require an exceedingly high number of layers to be practically solved. We have: Proposition 4. A problem instance cannot be solved if and only if in the initial literal assignment no two adjacent cells share a same literal after any column/row (a) permutation (Problem 1) and, no matter how the multiple assignments are resolved (Problem 2), each cell in row zero contains a literal that occurs also in another cell.

Proof. If part. Assume that no two adjacent cells share a same literal after any solution of Problems 1 and 2. Although the cells of row zero can be connected to the output, there will be no way to connect them to the other cells with the same literal since all cells will be occupied by a via in all layers.

Only-if part. If at least one of the conditions stated in the proposition does not hold, at least one cell in layer 2 is made available (or "free") for routing due to an area built in layer 1, or to a connection to the output in that layer. Once a free 1 2 3 2 3 1 3 1 2 Fig. 7. A non solvable instance.

cell arises, it can be "moved" to any cell of the array by consecutive movements of adjacent literals as in the well known 15-slide game, and any literal adjacent to the free cell can similarly be moved around to be brought adjacent to a cell with the same literal. Proceeding with this strategy all cells with a same literal can be linked together and brought to the output. 2

Note that the strategy indicated in the only-if part of the above proof may require a very large number of layers if only a small number ν of free cells exists in a layer, as only ν movements can be done in that layer. In particular, if only a few cells are made free by the solution of Problems 1 and 2, i.e. if layer 1 contains a large number of small mc-areas, the routing mechanism could require so many layers not to apply in practice. A decision on building or not such a layout must be taken after the simulation on significant examples.

Hardness of Problem 3

In the solution of Problem 3, the cells containing the same literal in any layer are connected, in the best case, as trees (and not as general subgraphs) to minimize the occupation of free cells, see next Subsection 3.3. The problem of minimizing the number of layers is related to the one of building the maximum number of such trees in any layer whose edges do not intersect. If a 15-slide movement of free cells is required the problem is NP-hard [?]. If such movements are not required the problem has strong similarities with other known NP-hard problems dealing with grid embedding of graphs, as for example determining the Steiner tree among k vertices on a grid [?], or determining the rectilinear crossing number of a graph [?], etc.

We have not been able to prove that Problem 3 is NP-hard, and leave it as a challenging open problem. For its solution we rely on a heuristic algorithm that produces satisfying results on a large class of benchmark instances as shown in the last section. If no tree can be directly built in a layer, as discussed in the previous subsection, the heuristic stops declaring that routing is impossible. Otherwise we have: Proposition 5. Let α be the number of mc-areas generated by Problems 1 and 2, h be the number of literals involved in the lattice, and k be the number of literals appearing in the cells of the top edge. An upper and a lower bound to the number H of layers are given by α + (h -k)/M and h/M , respectively.

Proof. Upper bound. First note that in layer 1 all the cells of any mc-area are connected together, and in each of the successive layers at least one pair of cells having a via from the previous layer, and holding the same literal, are connected. Then at most α layers are needed to connect all the cells holding the same literal. In addition all the h literals must be connected to the corresponding inputs leads on the top edge of the lattice. For the k literals already in this edge the connections can take place in layer 1. The remaining h -k literals, in the worst case, may be brought to a further layer α + 1 by vias and connected to the input leads in (h -k)/M layers.

Lower bound. Observe that h external leads must be displayed on the top edge of the lattice, possibly in different layers, and this edge contains M cells. 2

In the example of Figure 6 we have α = 15 (there are 15 mc-areas in layer 0), h = 7, k = 3, and M = 6. The proposed layout with H = 4 layers is far from approaching the upper bound 15 + 4/6 = 16, while is closer to the lower bound 7/6 = 2.

Heuristics for Problem 3

Let us now discuss possible greedy heuristics to solve Problem 3 in a reasonable amount of time.

Independently of the lattices that cannot be solved according to the conditions stated in Proposition 4, other cases may require an exceedingly large number of layers if the "15-slide game" moves are required, as indicated in the proof the same Proposition 4. We do not accept such moves, treating a lattice requiring them as unsolvable. This limitation shows a minor importance in practice since our algorithms failed very rarely to find a layout for a theoretically solvable lattice, out of a very large number of cases, see Section 4.

The general structure of our heuristics consists of the following two main steps:

1. Starting with layer 0 resulting from a re-arrangement of the lattice done in Problems 1 and 2, build the connecting trees for all mc-areas in layer 1, and connect the literals of the top side to the external leads. 2. While there are trees with the same literals still to be connected between them and/or to the outside: (a) place a via on a cell chosen at random of each such a tree; (b) add a new layer to receive the vias; (c) try to connect together as many vias as possible, associated to the same literal; (d) try to connect each group of cells containing a literal to the corresponding external lead, if not already done.

Step 1 can be implemented in a standard way, in a lattice traversal. Note that this initial step is optimal, i.e., no algorithm for the minimization of the number of layers can do better on the first layer.

To implement the second and main step of the heuristics we introduce the concept of free area where a connection between cells with the same literal can be displayed, namely: Definition 5. In the layers from 2 on, a free cell is one not containing a via; a free area is a maximal connected subset of free cells; the boundary cells of a free area are the ones surrounding it. Proposition 6. In any given layer from 2 on, cells holding the same literal can be connected together through free cells if and only if they are boundary cells of the same free area.

Proof. If part. Any subset of cells holding the same literal and bounding the same free area can be connected by a tree of connections laid out inside the area.

Only if part. Cells not bounding any free area are completely surrounded by vias holding different literals and cannot be connected to any other cell in that layer. For cells holding the same literal but not bounding the same area, any connecting path would inevitably meet another via. 2 Some considerations are in order. If a set of cells holding the same literal and facing the same free area are connected using free cells inside the area, other boundary cells of the same area can be connected only if the required connections do not cross those already laid out on that area. If two cells holding the same literal bound different areas they can still be connected in the layer through a path that meets only vias with their same literal, if any. If these conditions are not met, the cells must be connected in a next layer.

In the example of Figure 8 four free areas can be used to connect the two 1's in cells (1,2), (2,4); the two 5's in cells (1,4), (2,5); the two 7's in cells (3,6), (5,6); and the two 4's in cells (2,2), (4,4), the latter also connected to the external lead, as already shown in Figure 6 (b). The two 5's in cells (1,4) and (5,1) cannot be connected in this layer since they do not bound the same free area. However, if literal 2 in cell (3,3) were a 5, that connection would have been possible passing through cell (3,3), thus merging connections laid out in two different free areas. The still missing connections among different 5's, 2's, 6's, and 3's, will be done in the free areas of layers 3 and 4 as shown in Figure 6.

On these grounds we execute the crucial points c, d in step 2 of our heuristic first computing all the free areas in the layer, then trying to connect all boundary cells assigned to the same literal and facing the same free area. A relevant feature of this process is that free areas are mutually disjoint, then the searches for connections can be performed in parallel creating a thread for each free area.

The only portion of the layer shared by multiple threads are the boundary cells facing different free areas, that can be managed through lock variables that force the threads to access those cells in mutual exclusion.

The cells to be connected are treated pairwise, however, a subset of more than two cells holding the same literal may bound a free area and as many as possible of them must be connected in tree form. Therefore as soon as two of them are connected, the couple is treated as a single cell identified as the central cell of the connecting path holding the literal of the two, and the process continues looking for other cells to be connected to them.

Clearly a connecting path cuts the free area in two parts and other cells facing this same area may become unreachable from one another. We could solve this issue by recomputing the free areas after a new connection is done, but this approach is computationally very heavy. Therefore, we compute free areas only once in each layer, and then apply a proper non-exhaustive search algorithm to limit the search for non-existing connections, still guaranteeing that mutually reachable cells will be connected with high probability.

Let us now briefly discuss the possible implementations of this search within each free area. The main point is considering a boundary cell c 1 that must be connected to a target cell c 2 through a path of distinct free cells in a free area. This can be formalized as a state space search, where the state space is of size O(4 N ×M ) as the number of cells in the area is O(N × M ) and there are at most four possible moves from each cell. As a search in this space would be prohibitively expensive, we use heuristics to find solutions of high quality as quickly as possible. We have tested several heuristics proposed in the literature, while for space reasons the results reported in Section 4 are limited to Bestfirst and Greedy-beam (see [?,?]) that select the next cell to visit according to an estimate of the Manhattan distance from the target cell. The first heuristic provides better results but its time complexity O(4 N ×M ) is very high and can be applied only to small size lattices. The time complexity of Greedy-beam is instead linear in the lattice size, but produce worse quality results. In fact it may fail in connecting some mutually reachable cells on a given layer, so the final layout may contain a high number of layers. Depending on the lattice size and on the specific application, we can therefore select one of the two heuristics (or, for that matter, other known ones), trading quality of results vs. scalability.

Experimental Results

In this section we report the experimental results related to the physical implementation of switching lattices N × M according to the assumptions 1 to 4 reported in Section 1. The physical implementation of a lattice is a 3-dimensional grid N × M × (H + 1), where H is the number of layers needed to route all the connections among switches controlled by the same input literal. The aim of our experimentation is to determine whether the proposed implementation can be considered technologically feasible. To this ends we have considered the lattices obtained applying the Altun-Riedel method to the benchmark functions taken from LGSynth93 [?], where each output has been treated as a separate Boolean function. For space reasons, in the following Table 1 we report only a significant subset of these functions as representative indicators of our experiments.1 . The experiments have been run on a IntelCore i7-4710HQ 2.50GHz CPU with 8 GB of main memory, running Linux Ubuntu 17.10. The algorithms have been implemented in C according to the lines indicated in the paper for the solution of Problems 1, 2, and 3.

Table 1 is organized as follows. The first column reports the name and the number of the separate output functions of the benchmark circuit. The following two columns report the number of different literals occurring in the lattice and its dimension N × M . The last four columns report the number H of layers computed with the Best-first and the Greedy-beam heuristics, together with the corresponding running time. The last row reports the sum of the values of the corresponding column. The cases where the algorithm failed in finding a layout (see Subsection 3.3) are marked with a hyphen.

As expected, we have obtained layouts with a smaller number of layers using the Best-first heuristic at the expense of a higher computation time. However we note that the increase in the number of layers computed with the faster Greedy-beam heuristic appears quite limited.

Finally, these simulations have shown the effectiveness of the heuristic for Problem 1: indeed, the number of layers computed applying only the heuristics for Problems 2 and 3, without first permuting rows and columns, increases on average of about 35% using Best-first, and of about 43% using Greedy-beam. Moreover, running both the heuristic for Problem 1 and the algorithm MC-AREAS for Problem 2, we have obtained a considerable reduction of the number of layers, when compared with the results published in [?].

Concluding remarks

We have presented the first study on connection layout for two-dimensional switching lattices referring to the network implementation proposed by Altun and Riedel [?]. We have shown how to build a stack of consecutive layers where the connections between switches driven by the same variable can be laid without crossings, with the aim of minimizing the number H of layers. Since the problem is computationally intractable we have designed a family of heuristics for finding satisfactory solutions, then applied to a very large set of standard Boolean functions to validate our approach. For space reasons we have presented only the results obtained with the fastest and the slowest heuristics, and only for a subset of the functions analyzed taken as representative of the work done.

The overall design consists of three main phases, studied as Problems 1, 2, and 3. The first two are aimed at rearranging the switch positions and their literal assignment of the starting lattice, in order to place in adjacent cells as many switches controlled by the same literal as possible. The third phase then builds the actual connections on the different layers of the chip.

Countless improvements are open. While the NP-hardness of Problem 2 has been proved, for theoretical completeness also the NP-hardness of Problems 1 and 3 has to be proved to fully justify the use of heuristics. Better algorithms could be studied, and tested on larger data samples. The layout for other switching lattices should be considered. The layout rules should possibly be changed, in particular allowing more than one wire traversing a switch area in the higher layers. We are presently working on all these issues.

Fig. 1 .

 1 Fig. 1. A network of four terminal switches implementing the function f = x1x2x3 + x1x3 + x2x3 (a); the lattice evaluated on the assignments 1,0,0 (b) and 1, 0, 1 (c), with 1's and 0's representing ON and OFF switches, respectively.

  else according to the values P [s], P [v] the subsets of s and v are merged bringing s adjacent to v and the values of P [s], P [v] are updated accordingly; // nine combinations of values P [s], P [v] are possible: // for P [s] = P [v] = 2 and P [s] = P [v] = 3 the order // of the columns in one of the subsets must be inverted;

Fig. 3 .

 3 Fig. 3. Canceling a literal from a multiple choice using step 2 of Rule 1. Literals are denoted by a, b, c, d, e, f, g. Literal c in cells vj, v h is canceled from vj.

Fig. 4 .

 4 Fig. 4. Portion of graph G corresponding to the edge e = (u, v) of graph H.

  1. Reduction from PMPA, by insertion of new vertices to reduce all vertex degrees to at most 3. If edges (a, b), (a, c), (a, d), (a, e) and possibly other edges (a, x) exist, i.e. deg(a) > 3, insert a new vertex z with C z = C a ∪C b ∪C c , delete edges (a, b), (a, c), and insert new edges (a, z), (z, b), (z, c). Note that the degree of a decreases by 1, the degrees of b, c are unchanged, and z has degree 3. Continue until each vertex has degree ≤ 3. The solution for the new graph, i.e. the connected mono-colored subgraphs, coincides with a solution for PMPA if the new vertices z are deleted and the original edges are restored. Note that the graph resulting after the transformation is planar. 2. A result of Leslie G. Valiant (Theorem 2 of [?]), states that a planar graph G of n vertices with degree at most four admits a planar embedding in an O(n × n) grid Γ . Of the O(n 2 ) cells of Γ , obviously only n are used in the embedding for the vertices of G, while many of the others are used

  4. If two adjacent vertices a, b of G are embedded in two non adjacent cells of Γ , assign the set of colors C a ∩ C b to the cells of the sequence representing the edge (a, b). Repeat for all pairs of adjacent vertices. Assign a new color c ∈ C to all the grid cells not corresponding to the vertices and to the edges of G. 5. Solve GMPA on Γ considering all the cells as vertices of a new larger graph.

Fig. 5 .

 5 Fig. 5. Example of starting lattice.

Fig. 6 .

 6 Fig. 6. (a) Layer 1 with the first connections. (b) Layer 2. (c) Layer 3. (d) Layer 4. Arrows indicate the connections to the input leads on the top edge. Underlined literals indicate the starting cells of the vias.

ForFig. 8 .

 8 Fig. 8. Layer 2 of Figure 6 (b) with the seven free areas shown in grey.

Table 1 .

 1 Number of layers for the lattice layout of a subset of standard benchmark circuits, built along the lines indicated in Problems 1,2, and 3.

				Best-first Greedy Beam
	Bench	lit	N×M	H Time(s) H Time(s)
	add6(5)	24 156×156	7 733.21 8	0.43
	adr4(1)	16 36×36	6	0.19 8	0.02
	alu2(2)	16 10×11	4	0.01 4	0.01
	alu2(5)	20 13×14	4	0.01 4	0.01
	alu3(0)	8	4×5	3	0.01 3	0.01
	alu3(1)	12	7×8	4	0.01 4	0.01
	b12(0)	7	6×4	4	0.01 4	0.01
	b12(1)	9	5×7	4	0.01 4	0.01
	b12(2)	10	6×7	3	0.01 3	0.01
	bcc(5)	28 27×9	10	0.02 9	0.01
	bcc(7)	29 31×11	10	0.03 11	0.01
	bcc(8)	29 31×12	10	0.04 9	0.01
	bcc(27)	28 39×19	10	0.13 12	0.02
	bcc(43)	28 20×10	6	0.02 6	0.01
	bench1(2)	18 45×24	10	0.26 11	0.04
	bench1(3)	18 31×16	8	0.03 9	0.01
	bench1(5)	18 50×27	9	0.31 9	0.04
	bench1(6)	18 35×21	9	0.09 12	0.03
	bench1(7)	18 43×21	9	0.12 12	0.02
	bench1(8)	18 44×24	9	0.19 10	0.04
	bench(6)	10	8×4	5	0.01 5	0.01
	br2(4)	18 18×8	6	0.01 6	0.01
	br2(5)	19 14×4	6	0.01 6	0.01
	br2(6)	19 16×5	6	0.01 6	0.01
	clpl(3)	11	6×6	3	0.01 3	0.01
	clpl(4)	9	5×5	3	0.01 3	0.01
	co14(0)	28 92×14	11	0.29 12	0.04
	dc1(4)	7	5×4	-	0.01 -	0.01
	dc2(4)	11 10×9	5	0.01 5	0.01
	dc2(5)	9	6×6	4	0.01 4	0.01
	dk17(1)	10	8×2	6	0.01 6	0.01
	dk17(3)	11 11×3	-	0.01 -	0.01
	dk17(4)	12	9×3	5	0.01 5	0.01
	ex1010(0)	20 91×46	11	8.42 13	0.24
	ex4(4)	13 17×6	7	0.01 7	0.01
	ex4(5)	27 35×45	7	0.51 8	0.02
	ex5(32)	14 4×10	3	0.01 3	0.01
	ex5(36)	11	2×8	2	0.01 2	0.01
	ex5(38)	13	4×9	3	0.01 3	0.01
	ex5(40)	15 6×12	5	0.01 5	0.01
	ex5(43)	15 8×14	6	0.01 6	0.01
	exam(5)	13 11×6	4	0.01 4	0.01
	exam(9)	20 59×30	9	0.75 12	0.04
	max128(5)	14 14×17	6	0.01 6	0.01
	max128(8)	13 5×10	5	0.01 5	0.01
	max128(17) 14 26×25	7	0.06 8	0.01
	max1024(5) 20 117×122 10 191.33 14	0.89
	mp2d(6)	14 10×6	5	0.01 5	0.01
	mp2d(9)	14	6×8	3	0.01 3	0.01
	mp2d(10)	10	6×3	4	0.01 4	0.01
	sym10(0)	20 130 × 210 9 1571.93 10	2.14
	tial(5)	28 181×181 10 1491.45 12	1.19
	z4(0)	7 15×15	5	0.01 6	0.01
	z4(1)	14 28×28	7	0.08 7	0.01
	Z5xp1(2)	14 12×11	4	0.01 4	0.01
	Z5xp1(3)	14 18×18	5	0.01 7	0.01
				336 3999,8 367	5,61

Experimental results on a much larger set of benchmark functions may be requested to the present authors


Valentino Peluso
email: valentino.peluso@polito.it

Andrea Calimera
email: andrea.calimera@polito.it

Energy-Accuracy Scalable Deep Convolutional Neural Networks: A Pareto Analysis

Keywords: Facial Expression Recognition, show adaptive ConvNets reach better energy-accuracy trade-off w, r, t, conventional static fixed-point quantization methods

This work deals with the optimization of Deep Convolutional Neural Networks (ConvNets). It elaborates on the concept of Adaptive Energy-Accuracy Scaling through multi-precision arithmetic, a solution that allows ConvNets to be adapted at run-time and meet different energy budgets and accuracy constraints. The strategy is particularly suited for embedded applications made run at the "edge" on resourceconstrained platforms. After the very basics that distinguish the proposed adaptive strategy, the paper recalls the software-to-hardware vertical implementation of precision scalable arithmetic for ConvNets, then it focuses on the energy-driven per-layer precision assignment problem describing a meta-heuristic that searches for the most suited representation of both weights and activations of the neural network. The same heuristic is then used to explore the optimal trade-off providing the Pareto points in the energy-accuracy space. Experiments conducted on three different ConvNets deployed in real-life applications, i.e. Image Classification, Keyword Spotting, and

Introduction

Deep Neural Networks (DNNs) are computational models that emulate the activity of the human brain during pattern recognition. They consist of deep chains of neural layers that apply non-linear transformations on the input data [START_REF] Lecun | Deep learning[END_REF]. The projection on the new feature-space enables a more efficient classification, achieving accuracies that are close, and in some cases even above, those scored by the human brain. Convolutional Neural Networks [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] (ConvNets hereafter) are the first example of DNNs applied to problems of human-level complexity. They have brought about breakthroughs in computer vision [START_REF] Russakovsky | Imagenet large scale visual recognition challenge[END_REF] and voice recognition [START_REF] Hinton | Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups[END_REF], improving the state-of-the-art in many application domains. From a practical viewpoint, the forward pass through a ConvNet is nothing more than matrix multiplications between pre-trained parameters (the synaptic weights of the hidden neurons) and the input data. The most common use-case for ConvNets is image classification where a multichannel image (e.g. RGB) is processed producing as output the probability that the subject depicted in the picture belongs to a specific class of objects or concepts (e.g. car, dog, airplane, etc.). One can see this end-to-end inference process as a kind of data compression: high-volume raw-data (the pixels of the image) are compressed into a highly informative tag (the resulting class). In this regard, the adoption on the Internet-of-Things (IoT) is disruptive: distributed smart-objects with embedded ConvNets may implement data-analytics at the edge, near the source of data [START_REF] Xu | Scaling for edge inference of deep neural networks[END_REF], with advantages in terms of predictability of the service response time, energy efficiency, privacy and, in general, scalability of the IoT infrastructure.

The design of embedded ConvNets encompasses a training stage during which the synaptic weights of the hidden neurons are learned using a back-propagation algorithm (e.g. the Stochastic Gradient Descent [START_REF] Bottou | Large-scale machine learning with stochastic gradient descent[END_REF]). The learning is supervised and accuracy-driven, namely, it adjusts the weights such that an accuracy loss function evaluated over a set of labeled samples is minimized. Once trained, the ConvNet can be flashed on the smart-object and deployed at the edge, where it runs inference on never occurred samples. To notice that ConvNets presented in the literature show different depth (number of layers) and size (number of neurons per layer); also the topology may change due to optional layers used to reduce the cardinality of the intermediate activations, e.g., local pooling layers, or their sparsity, e.g. Rectified Linear Units (ReLU). Regardless of the internal structure, ConvNets show a common characteristic, complexity. Even the most simple model, e.g. AlexNet [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] or the more compact MobileNets [START_REF] Howard | Mobilenets: Efficient convolutional neural networks for mobile vision applications[END_REF], show millions of synaptic weights to be stored and tens of thousands of matrix convolutions to be run [START_REF] Xu | Scaling for edge inference of deep neural networks[END_REF]. This prevents their use on low-power embedded platforms which offer low storage capacity, low compute power, and limited energy budget. How to design ConvNets that fit the stringent resource constraints while preserving classification accuracy is the new challenge indeed.

Recent works introduced several optimization strategies, both at the software level and hardware level [START_REF] Sze | Efficient processing of deep neural networks: A tutorial and survey[END_REF]. They mainly exploit the intrinsic redundancy of ConvNets in order to reduce (i) the number of weights/neurons (the so-called pruning methods) or (ii) the arithmetic precision (quantization methods) or (iii) both [START_REF] Grimaldi | Layer-wise compressive training for convolutional neural networks[END_REF]. Precision scaling is of practical interest due to its simplicity and the solid theories developed in the past for DSP applications. It concurrently reduces the memory footprint (the lower the bit-width, the lower the memory footprint) and the execution latency (the lower the bit-width, the faster the execution). The use of fixed-point arithmetic with 16-and 8-bit [START_REF] Szegedy | Going deeper with convolutions[END_REF] instead of the 32-bit floating-point, or even below, e.g. 6 and 4-bit [START_REF] Chen | Eyeriss: An energy-efficient reconfigurable accelerator for deep convolutional neural networks[END_REF], has shown remarkable savings with no, or very marginal accuracy drop. Aggressive binarization [START_REF] Courbariaux | Binaryconnect: Training deep neural networks with binary weights during propagations[END_REF] is an alternative approach provided that large accuracy loss is acceptable. Obviously, the implementation of quantized ConvNets asks for integer units that can process data with reduced representations; recent hardware designs, both from industry and academia, follow this trend [START_REF] Flamand | Gap-8: A risc-v soc for ai at the edge of the iot[END_REF][14] [START_REF] Albericio | Bit-pragmatic deep neural network computing[END_REF].

Most of the existing optimizations, both pruning and quantization, were originally conceived as static methods. Let's consider quantization. For a given ConvNet the numeric precision of the weights is defined at design-time and then kept constant during run-time. Therefore, the design effort is that of finding the proper bit-width such that accuracy losses are minimized [START_REF] Moons | Energy-efficient convnets through approximate computing[END_REF]. Although effective, this approach is very conservative as inference always operates at full speed and hence under maximum resource usage. Adaptive strategies that speculate on the quality of results to reach higher energy efficiency are a more interesting option for portable devices deployed on non-critical missions [START_REF] Shafique | Adaptive and energy-efficient architectures for machine learning: Challenges, opportunities, and research roadmap[END_REF]. There exist applications or use-cases for which the classification accuracy can be relaxed without affecting much the user perception, or, alternatively, conditions under which other extra-functional properties of the system, e.g. energy budget or latency, get higher priority. For such cases, one may use the arithmetic precision as a control knob to manage the resources. This concept of energy-accuracy scaling is a well-established technique for VLSI designs [START_REF] Alioto | Energy-quality scalable integrated circuits and systems: Continuing energy scaling in the twilight of moores law[END_REF], while it represents a less explored option for ConvNets (and DNNs in general). The idea of energy-accuracy scalable ConvNets through dynamic precision scaling was first introduced in [START_REF] Peluso | Weak-mac: Arithmetic relaxation for dynamic energyaccuracy scaling in convnets[END_REF] and then elaborated in [START_REF] Peluso | Energy-driven precision scaling for fixed-point convnets[END_REF] with the introduction of an energy-driven optimization framework. The method applies to softwareprogrammable arithmetic accelerators where precision scaling is achieved through variable-latency Multiply&Accumulate (MAC) instructions. This implementation applies for any general purposes MCUs (e.g. [START_REF] Lai | Enabling deep learning at the iot edge[END_REF]) or application-specific processors with a multi-precision instruction-set (e.g. Google TPU [START_REF] Jouppi | Indatacenter performance analysis of a tensor processing unit[END_REF]); it can also be extended to dedicated architecture (both ASIC or FPGA accelerators [START_REF] Moons | An energy-efficient precision-scalable convnet processor in 40-nm cmos[END_REF]). This chapter further investigates on this strategy introducing a Pareto analysis of the energy-accuracy space. An optimization engine is used to identify the arithmetic precision that minimizes energy and accuracy loss concurrently. The obtained precision settings can be loaded at run-time with minimal overhead thus to allow ConvNets to reach the operating conditions that satisfy the requirements imposed at the system-level. As test-benches we used three real-life applications built upon state-of-the-art ConvNets, i.e. Image Classification [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF], Keyword Spotting [START_REF] Warden | Speech commands: A dataset for limited-vocabulary speech recognition[END_REF], and Facial Expression Recognition [26]. Experimental results suggest the proposed strategy is a practical solution for the development of flexible, yet efficient IoT applications. The remaining sections are organized as follows. Section 2 gives an overview of related works in the field. Section 3 describes the implementation details for the single weight-set multi-precision arithmetic used in scalable ConvNets. Section 4 recalls the optimization engine and the energy-accuracy models adopted. Finally, Section 5 shows the Pareto analysis over the three benchmarks and the performance of the optimization heuristic.

Related Works

With the emerging of the edge-computing paradigm, the reduction of ConvNets complexity has become the new challenge for the IoT segment. The problem is being addressed from different perspectives: with the design of custom hardware that improves the execution of data-intensive loops achieving energy efficiencies of few pico-Joules/operation[27] [START_REF] Chen | Eyeriss: An energy-efficient reconfigurable accelerator for deep convolutional neural networks[END_REF]; with new learning strategies that generate less complex networks [START_REF] Gu | Recent advances in convolutional neural networks[END_REF]; with iso-accuracy compression techniques aimed at squeezing the model complexity. A thorough review is reported in [START_REF] Yang | Designing energy-efficient convolutional neural networks using energy-aware pruning[END_REF]. To notice that while many existing techniques are conceived as static methods, the dynamic management of ConvNets is a less explored field. This work deals with this latter aspect.

Adaptive ConvNets

Following the recent literature, the concept of adaptive ConvNets may have multiple interpretations and hence different implementations. On the one hand, there are solutions that adapt to the complexity of the input data. On the other hand, solutions that adapt to external conditions or triggers, regardless of data complexity. The former class is mainly represented by techniques that implement the general principle of coarse-to-fine computation [START_REF] Fleuret | Coarse-to-fine face detection[END_REF]. These methods make use of branches in the internal network topology generating conditional deep neural nets [START_REF] Panda | Conditional deep learning for energyefficient and enhanced pattern recognition[END_REF]. In its most simple implementation, a conditional ConvNet is made up of a chain of two classifiers, a coarse classifier (for "easy" inputs) and a fine classifier (for "hard" inputs) [START_REF] Yan | Hd-cnn: hierarchical deep convolutional neural networks for large scale visual recognition[END_REF]; the coarse classifier is always-on, while the fine classifier is occasionally activated for "hard" inputs (statistically less frequent). As a result, ConvNets can adapt to the complexity of data at run-time. An extension with deeper chains of quantized micro-classifiers is proposed in [START_REF] Neshatpour | Icnn: An iterative implementation of convolutional neural networks to enable energy and computational complexity aware dynamic approximation[END_REF], while in [START_REF] Moons | 14.5 envision: A 0.26to-10tops/w subword-parallel dynamic-voltage-accuracy-frequency-scalable convolutional neural network processor in 28nm fdsoi[END_REF] authors propose the use of Dynamic Voltage Accuracy Frequency Scaling (DVAFS) for the recognition of objects of different complexity. Concerning the second class, that is the main target of this work, adaptivity is achieved by tuning the computational effort of the ConvNet depending on the desired accuracy. The control knob is the arithmetic precision of the convolutional layers. The work described in [START_REF] Peluso | Weak-mac: Arithmetic relaxation for dynamic energyaccuracy scaling in convnets[END_REF] is along this direction as it introduces an HW-SW co-design to implement multi-precision arithmetic at run-time. Depending on the parallelism of the HW integer units (e.g. 16-or 8-bits), weights can be loaded and processed using different bit-widths thus to achieve different degrees of accuracy under different energy budgets. This is the enabler for accuracy-energy scaling adaptive ConvNets. To notice that unlike static quantization methods where different accuracy levels could be achieved using multiple pre-trained weight-sets stored as separate entities, here the precision scaling is achieved using a single set of weights and incomplete arithmetic operations. The same strategy is adopted in this work. Hybrid solutions may jointly exploit the complexity of the input problem with the accuracy imposed at the application level. For instance, the authors of [START_REF] Peluso | Scalable-effort convnets for multilevel classification[END_REF] introduce the concept of multi-level classification where the classification task can be performed at different levels of semantic abstraction: the higher the abstraction, the easier the classification problem. Then, depending on the abstraction level and the desired accuracy, the ConvNet is tuned to achieve the maximum energy efficiency.

Fixed-Point Quantization

Since the multi-precision strategy adopted in this work encompasses the quantization to fixed-point, this subsection gives a brief taxonomy of the existing literature on the subject. Complexity reduction through fixed-point quantization exploits the characteristics of the weight distributions across different convolutional layers in order to find the most efficient data representation [START_REF] Lin | Fixed point quantization of deep convolutional networks[END_REF]. Two main stages are involved: the definition of the bit-width, i.e. the data parallelism, and the radix-point scaling, i.e. the position of the radix point. A common practice is to define the bit-width depending on hardware availability (e.g. 16-, 8-bit for most of the architectures), then find the radix-point position that minimizes the quantization error. The existing techniques, mainly from the DSP theory, differ in the radixpoint scaling scheme. A complete review is out of the scope of this work and the interested reader can refer to [START_REF] Sze | Efficient processing of deep neural networks: A tutorial and survey[END_REF]. It is worth emphasizing that a one-size-fits-all solution does not exist as efficiency is affected by the kind of neural networks under analysis and the characteristics of the adopted hardware. A more relevant discriminant factor is the spatial granularity at which the fixedpoint format is applied, per-net or per-layer. In the former case all the layers share the same representation; in the latter case, each layer has its own representation. Since the weights distribution may substantially differ from layer to layer, a finer, i.e. per-layer, approach achieves lower accuracy loss [START_REF] Lin | Fixed point quantization of deep convolutional networks[END_REF]. Whatever the granularity is, existing works from the machine-learning community, e.g. [START_REF] Lin | Fixed point quantization of deep convolutional networks[END_REF] [37], focused on accuracy-driven optimal precision scaling. Only a few papers take hardware resources into account, which is paramount when dealing with embedded systems. The authors of [START_REF] Moons | Energy-efficient convnets through approximate computing[END_REF] briefly describe a greedy approach where low precision is assigned starting from the first layer of the net (topological order) without considering the complexity of the layer. In [START_REF] Szegedy | Going deeper with convolutions[END_REF] authors describe the design of embedded ConvNets for FPGAs and propose a per-layer precision scaling that is aware of the number of memory accesses. Only very few works, e.g. [START_REF] Yang | Designing energy-efficient convolutional neural networks using energy-aware pruning[END_REF] and [START_REF] Peluso | Energy-driven precision scaling for fixed-point convnets[END_REF], bring energy consumption as a direct variable in the optimization loop.

Energy-Accuracy Scalable Convolution

The proposed adaptive ConvNet strategy leverages precision scalable arithmetic. This section introduces a possible implementation of matrix convolution using software-programmable multi-precision Multiply&Accumulate (MAC) instructions. It first describes the algorithmic details, then it presents a custom processing element that accelerates the variable-latency MAC with minimal design overhead.

SW: Multiprecision Convolution

For a given layer in a ConvNet, the convolution between the M × M input map matrix I and the M × M weight matrix of a kernel W is the dot-product of the

W i × I i * I W M = I i W i I i W i = N=16 K=8 MxM … … I i × H H × H L L H × L L + + + × Half:KxK = 8x8
Mixed:KxN = 8x16 Assuming a N -bit fixed-point representation (N = 16 in this work), I i and W i can be seen as two concatenated halfwords of K = N/2 bits (K=8); the most significant parts I H i and W H i and the least significant parts I L i and W L i . As pictorially described in fig. 1, each single product I i × W i is implemented by means of a four-cycles procedure where the most significant and least significant halfwords are iteratively multiplied, shifted and accumulated. To notice that I H i and W H i are signed integers, I L i and W L i are unsigned. Different precision options can be reached by stopping the execution at earlier cycles: half (K × K) 1 cycle, mixed (K × N ) 2 cycles and full (N × N -bit) 4 cycles; an additional mixed precision option (N × K) is also obtained by swapping the second and the third cycle (2 cycles).

Full:NxN = 16x16 𝑖=0 𝑀 2 -1 𝐼 𝑖 × 𝑊 𝑖 H L H L #1 #2 #3 #4 cycles I W K=8
The same four options can be extended to the dot-product procedure as described in Algorithm 1. At half-precision, both the operands I i and W i are reduced to K bits. The first loop (lines 1-2) operates on the most significant parts I H i , W H i . The result is then returned (line 3). At mixed-precision, only one operand, the input I i (or the weight W i , not shown in the pseudo-code), is reduced to K bits. First, the partial result r is shifted of K-bits (line 4), then the second loop (lines 5-6) iterates on I H i and W L i (I L i and W H i ) and the result is returned (line 7). At fullprecision, both W i and I i are taken as N bit operands. In this case the last two loops (lines 8-12) come into play and they iterate on the least significant parts W L i and I i (both H and L) thus to complete the remaining part of the product. To summarize, with N =16, the available precision options are: half (K × K, i.e. 8 × 8), mixed (N × K, i.e. 16 × 8 or K × N , i.e. 8 × 16), full (N × N , i.e. 16 × 16). Given the regular structure of the algorithm, all them can be implemented on the same K × K MAC unit.

Algorithm 1: Iterative multiply-accumulate algorithm

Input: I, W , precision Output: Dot-Product r 1 for i = 0; i < M ; i = i + 1 do 2 r = r + I H i × W H i 3 if (precision==half ) then return r ; // half:KxK 4 r = r K 5 for i = 0; i < M ; i = i + 1 do 6 r = r + I H i × W L i 7 if (precision==mixed) then return r ; // mixed:KxN 8 for i = 0; i < M ; i = i + 1 do 9 r = r + I L i × W H i 10 r = r K 11 for i = 0; i < M ; i = i + 1 do 12 r = r + I L i × W L i 13 return r ; // full:NxN
This straightforward algorithm offers a simple way to adjust the precision of the results and the resource usage. Firstly, it allows the computational effort, and hence the energy consumption, to scale with the arithmetic precision; secondly, it alleviates the memory bandwidth as less bits need to be moved from/to the memory banks at lower precisions1 .

HW: Variable-latency Processing Element

Figure 2 gives the RTL-view of the proposed processing element (PE) for N =16.

The PE is composed by 9 × 9 multiplier, where the 9 th bit is used for the sign extension of the operands. As described in the previous subsection, the most significant parts (I H i , W H i ) are signed, while the least significant parts (I L i , W L i ) are unsigned. Therefore, the MSB of (I L i , W L i ) belongs to the module, while that of (I H i , W H i ) is the sign. In order to account for this issue we implemented the following mechanism: when (I H i , W H i ) are processed, the sign is extended to the 9 th by concatenating the MSB (i.e. the sign) of I and W ; when (I L i , W L i ) are processed a 0 is concatenated. The selection is done through the control signals signed-I and signed-W driven by the local control unit (omitted in the picture for the sake of space). The same control unit is in charge of feeding the MAC with the right sequence of data (H or L) fetched from a local memory. The accumulator has 16 guard bits and an embedded saturation logic to handle underflow and overflow. The role of the programmable shifter is two-fold. First, to shift the partial results when needed (see Algorithm 1). Second, to implement the dynamic fixed point arithmetic by moving the radix point of the final accumulation result depending on the desired fractional length [START_REF] Courbariaux | Training deep neural networks with low precision multiplications[END_REF]. A range check logic drives bit saturation if the result does not fit the word-length. In order to minimize the dynamic power consumption, a zero-skipping strategy [START_REF] Moons | 14.5 envision: A 0.26to-10tops/w subword-parallel dynamic-voltage-accuracy-frequency-scalable convolutional neural network processor in 28nm fdsoi[END_REF] is implemented by means of latch-based operand isolation and clockgating. If one of the operands is zero, then the latches prevent the propagation of inputs minimizing the switching activity, while the clock-gating cell disables the clock signal thus reducing the equivalent load capacitance of the clock signal.

Hardware Characterization

The proposed SW-HW precision scaling strategy can be implemented using both FPGA and ASIC technologies. In this work we designed and characterized the 8 × 8 MAC unit using a commercial 28 nm UTBB FDSOI technology and the Synopsys Galaxy Platform, versions L-2016.03. The frequency constraint is set to 1 GHz at 0.90 V in a typical process corner (compliant with recent works that used the same technology [START_REF] Desoli | 14.1 a tops/w deep convolutional neural network soc in fd-soi 28nm for intelligent embedded systems[END_REF]). Power consumption is extracted using Synopsys PrimeTime L-2016.06 with SAIF back-annotation. Collected results show a standard cell area of 1443 µm 2 and total average power consumption of 0.95 mW.

Compared to a traditional 8×8 MAC unit, the proposed architecture shows 3.7% area penalty. The shift from floating-point to fixed-point is a well-known problem in the DSP domain. In this sub-section, we review the basic theory and the main aspects involving this work.

A floating-point value V can be represented with a binary word Q of N bits using the following mapping function:

V = Q • 2 -F L (1)
F L indicates the fraction length, i.e. the position of the radix-point in Q. Given a set of real values, the choice of N and F L affects the information loss due to quantization. Since the bit-width N is usually given as a design constraint (e.g. 16-bit in this work), the problem reduces to searching the optimal F L (the integer length IL is then given by N -IL). The choice of F L affects the maximum representable value |V max | and the minimum quantization error Q step .

Concerning |V max |, the relationship is described in the following equation:

F L = log 2 2 BW -1 -1 |V max | (2)
A trade-off does exit: the lower the F L the lower the V max ; the larger the F L the lower the Q step . The decision of which constraint to guard more (|V max | or Q step ) mainly depends on the distribution of the original floating-point weights and their importance in the neural model under quantization.

A dynamic fixed-point scheme is implemented where the fraction length is defined layer-by-layer. The F L opt that minimizes the L2 distance between the original 32-bit floating point values and the quantized values is searched among N -1 possible values. The search is done over a calibration set built by randomly picking 100 samples from the training set. To be noted that our problem formulation applies a symmetric linear quantization using a binary radix-point scaling.

As an additional piece of information, it is important to underline that quantization is not followed by retraining, a very time-consuming procedure even for small ConvNets.

Multiprecision Fixed-Point ConvNets

Problem Formulation For a ConvNet of L layers, the classification accuracy can be scaled to different values by optimally selecting the arithmetic precision of each layer. The choice of such optimal precision should be done for the input map (I) and the weight (W) matrices of each layer each layer i, and for the output map matrix (O) of the last layer2 .

Assuming the availability of the four accuracy options described in Section 3, i.e. full (16 × 16), mixed (16 × 8 or 8 × 16), half (8 × 8), the precision for I and W of each layer, and that of O for last layer, can be assigned to 8-bit or 16-bit. We encode the unknown of the problem as a vector X of (2×L+1) Boolean variables x i , where the variable x 2×L+1 refers to O. The encoding map is: x=0→8-bit, x=1→16-bit. The optimal assignment is the one that minimizes the total energy consumption E(X) while ensuring an accuracy loss λ(X) lower than a user-defined constraint λ max .

Energy-Driven Precision Assignment

The optimal precision assignment to each layer is carried out using a custom meta-heuristic based on Simulated Annealing (SA). Algorithm 2 shows the pseudo-code of the SA. It gets as inputs the parameters listed in table 2. In all the experiments, the starting solution X 0 is the full-precision (16-bit) to all the L layers (both I and W, and O. The estimation of the accuracy drop is done on a subset of images randomly picked from the training set, referred to as the calibration set. Its size is defined by the cal set parameter. At each iteration, the next state is generated as a random perturbation of the current state (line 6). For those states that satisfy the accuracy constraint (line 7), the energy cost function E is evaluated (line 8) through the function energy. If ∆E (line 9) reduces (line 10), the new state is accepted (lines 11-12). If not, the new state is accepted following a Boltzmann probability function (lines 10-12); the acceptance ratio gets smaller as T reduces. States that show minimum energy are iteratively saved as best solutions (lines [START_REF] Flamand | Gap-8: A risc-v soc for ai at the edge of the iot[END_REF][START_REF] Moons | A 0.3-2.6 tops/w precision-scalable processor for realtime large-scale convnets[END_REF][START_REF] Albericio | Bit-pragmatic deep neural network computing[END_REF]. Once the total number of iterations is reached (line 5), the temperature T is cooled down (line 17). The process iterates till the minimum temperature T f is reached (line 4). The bottleneck of the algorithm is the call to the function accuracy drop. For this reason, the algorithm takes trace of already processed states; this information is fed to the accuracy drop function which can eventually by-pass accuracy estimation (line 16). Energy The system-level architecture depicted in Figure 3 serves as a general template to describe Application-Specific Processors for ConvNets computing, e.g. [START_REF] Chen | Eyeriss: An energy-efficient reconfigurable accelerator for deep convolutional neural networks[END_REF]. It consists of a planar array of processing elements (PE), in our case the MAC units described in Section 3, a set of SRAM buffers for storing temporal data (Input Buffer, Weight Buffer, and Output Buffer), an off-chip memory (DRAM) and its DMA, a control unit (RISC) that schedules the operations. The total energy consumption E is the sum of two main contributions: E = E comp + E mem . E comp is the energy consumed by the PE array, E mem is the energy consumed due to data movement through the memory hierarchy.

9 ∆E = (E next-E current) / (Emax -Emin) 10 if (dE < 0) or (exp[-∆E/K b •T] > random(0,
The first term is defined as:

E comp = L i=1 E MAC • N cycles (xi) • N MAC i + E zero • N zero i (3)
L is the number of layers of the ConvNet. E MAC is the energy consumption of the half-precision MAC (row 8×8 in table 1). N cycles is the latency of a single MAC operation of the i-th layer; it is given as multiple of the latency of the half-precision MAC (row 8×8 in Table 1) and it is function of the precision x i .

N MAC i
is the number of non-zero MAC operations of the i-th layer. E zero i is the energy consumed under zero-skipping (mostly due to leakage). N zero i is the number of zero MAC. The second term is defined as:

E mem = 2•L+1 i=1 E MAC • [αi(xi) + βi(xi) + γi(xi)] (4)
E MAC is the same as in Equation 3, while α i , β i and γ i are three parameters that describe the energy consumed by the i-th layer due to reading/writing the input map (α i ), the weights (β i ), the output map (γ i ). More specifically they represent the ratio between the energy consumption of the memory and the energy consumption of the PE array; here again, the energy unit is the halfprecision MAC (row 8×8 in table 1) [START_REF] Chen | Eyeriss: An energy-efficient reconfigurable accelerator for deep convolutional neural networks[END_REF]. Obviously, α and β do not contribute for the final output layer: α L+1 =0 and β L+1 =0.

All the three parameters are function of the layer precision x i : both fetch and write-back operations depend on (i) the accuracy of the MAC algorithm, and (ii) the number of zero-multiplications (switching activity to/from memory may change substantially). Moreover α i , β i , γ i change depending on the ConvNet model: number and size of weights/channels per layer, stride and padding. Finally, they also differ depending on the size of the hardware components (PE array, and global buffers). Since the target of this work is not the energy model per se, not even the evaluation of different architectural solutions, α i , β i , γ i are extracted for the architecture proposed in [START_REF] Chen | Eyeriss: An energy-efficient reconfigurable accelerator for deep convolutional neural networks[END_REF] and then scaled to our precision reduction strategy. The same E mem model applies to different architectures by proper tuning of the three parameters.

Accuracy Drop

The accuracy drop is computed as the ratio between the number of miss-classified images and the total number of images in the calibration set (cal set), hence its estimation implies the execution of S feed-forward inferences using the quantized fixed-point model (S as the cardinality of cal set).

Unfortunately, common GPUs do not have integer units. To address this issue we implemented the fake quantization proposed in [START_REF] Shan | A Dynamic Multi-precision Fixed-Point Data Quantization Strategy for Convolutional Neural Network[END_REF]. It is a SW strategy that emulates the loss of information due to fixed-point arithmetic still using floatingpoint data-type. Each layer is wrapped with a software module that converts its input data and weights (32-bit floating-point) into a fake integer, namely, still a 32-bit floating-point number subtracted of an amount equal to the error that the fixed-point representation would have brought. The advantage is that all the fixed-point operations are physically run by the high-performance FP units.

Results

Experimental Set-up

The objective of this work is to provide a Pareto analysis of adaptive ConvNets implemented with the proposed energy-accuracy scaling strategy. As benchmarks we adopted three different applications which are reaching widespread use in several domains: Image Classification (IC), Keyword Spotting (KWS), Facial Expression Recognition (FER). Additional details provided in the next subsection.

The exploration in the energy-accuracy space is conducted using the SA engine introduced in Section 4. More specifically, the algorithm is made run under different accuracy loss constraints, from 1% to 15% with step 1%, and collecting the energy consumption reached by the optimal precision settings. Table 3 summarizes the SA parameters used in the experiments. For all the networks we selected the same hyper-parameters, except for the number of iterations iter at a given temperature T . As described in the next sub-section, the three ConvNets have different number of layers, hence different complexity; as the cardinality of the search space increases, more iterations are needed to explore the cost function.

Benchmarks

The three benchmarks under analysis serve very different purposes; their functionality and main characteristics, as well as their training set, are described separately therefore.

Image Classification (IC): the typical image recognition on the popular CIFAR-10 dataset. The dataset collects 60000 32 × 32 RGB images [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF] evenly split in 10 classes, with 50000 and 10000 samples for the train-set and testset respectively. The adopted ConvNet is taken from the Caffe framework [START_REF] Jia | Caffe: Convolutional architecture for fast feature embedding[END_REF], which consists of three convolutional layers interleaved with max-pooling and one fully-connected layer.

Facial Expression Recognition (FER): it is about inferring the emotional state of people from their facial expression. Quite popular in the field of vision reasoning, this task is very challenging as many face images might convey multiple emotions. The reference dataset is the Fer2013 dataset given by the Kaggle competition [26]. It collects 32297 48 × 48 gray-scale facial images split into 7 categories, i.e. "Angry", "Disgust", "Fear", "Happy", "Sad", "Surprise", "Neutral".

Results

Table 5 shows the top-1 prediction accuracy achieved with a coarse per-net precision scaling scheme in which all the layers share the same precision. A viable option to improve performance is to reduce the granularity at which the SA explores the parameters space. This can be achieved by constraining the number of iterations for each explored temperature T (parameter iter in Table 2). A quantitative comparison is given in Fig. 5, whose plot shows the Pareto curves obtained with iter =1000 (the original value), 500 and 250 for the FER benchmark. The execution time reduces linearly, i.e. (66m, 18s) with iter =1000, (33m, 35s) with iter =500, (16m, 36s) with iter =250, while the quality of results reveal more interesting trends. Whereas it is generally true that a larger iter leads to better absolute numbers, the gain practically fades when considering the relative distance between the obtained curves. With iter =1000 the average savings across the Pareto points (39.3%) is just 5% larger than that obtained using iter =500 (34.6%) and iter =250 (34.4%); both iter =1000 and iter =500 collects the same number of Pareto points, 7 overall; only with iter =250 the number of Pareto points reduces from 7 to 5. This analysis suggests that for larger ConvNets there's a margin for tuning the SA to reasonable execution time w/o degrading much the quality.

-7% -6% -5% -4% -3% -2% -1% Top-1 Accuracy Drop 20% 30% 40% 50% Savings (%) 250 500 1000

Fig. 5: Pareto analysis for FER benchmark using different number of iterations during the SA evolution: 1000, 500, 250.

Conclusions

The evolution of ConvNets has been driven by accuracy improvement. High accuracy reflected on large-scale network topologies which turned the inference into a too expensive task for low-power, energy-constrained embedded systems. ConvNets compression is therefore an urgent need for the growth of neural computing at the edge. While most of the existing techniques mainly focus on static optimizations, dynamic resource management represents a viable option to further improve energy efficiency. This chapter introduced a practical implementation of adaptive ConvNets. The proposed strategy allows ConvNets to relax their computational effort, and hence their energy consumption, leveraging the accuracy margin typical of non-critical applications. The technique is built upon a low overhead implementation of dynamic multi-precision arithmetic. The resulting ConvNets are free to move in the energy-accuracy space achieving better trade-offs. A Pareto analysis conducted on three representative applications (Image Recognition, Keyword Spotting, Facial Expression Recognition) quantified the energy savings suggesting potential improvement for the Simulated Annealing (SA) optimization engine. Future works will bring this adaptive strategy to larger ConvNets deployed on real HW implementations.

Fig. 1 :

 1 Fig. 1: Iterative multiply-accumulate algorithm.

Fig. 2 :

 2 Fig. 2: 8 × 8 HW unit for multi-precision MAC.

Algorithm 2 : 8 E

 28 Simulated AnnealingInput: T0, T f , X0, cooling, K b , iter, λtextrmmax, cal set Output: X 1 T = T0 2 E = energy(X0) 3 Emax = energy (ones (2L + 1)); Emin = energy (zeros (2L + 1)) 4 while (T ≥ T f ) do 5 for i = 0; i < iter; i = i+1 do 6 next state = move (current state) 7 if accuracy drop(next state, cal set, tested) < λmax then next = energy (next state)

  Av. Drop refer to the accuracy drop averaged over the Pareto points; column Av. Savings does the same for the energy savings. For all the three benchmarks the energy-accuracy scaling operated with an optimal per-layer multi-precision assignment ensures optimality and usability on several context scenarios. Table 6 also shows the average execution time taken by the SA engine to draw a Pareto point, column Av. Exec. Time. Results are collected on a workstation powered by an Intel i7-8700K CPU and an NVIDIA GTX-1080 GPU with CUDA 9.0. As expected, time gets larger with network complexity. For the largest benchmark (FER) the tool consumes 66 min and 18 s.

Table 1

 1 shows the latency (N cycles ) and the energy consumption per MAC operation (E MAC ) for the four precisions available. As one can see, each row in the table corresponds to a different implementation point in the precision-energy space. If one of the two operands is zero, energy E zero reduces substantially due to the zero-skipping logic: E zero = 0.103E MAC .

Table 1 :

 1 Energy/MAC vs Precision

	Precision (I × W ) N cycles E MAC (pJ)
	16 × 16	4	3.80
	16 × 8	2	1.90
	8 × 16	2	1.90
	8 × 8	1	0.95

Table 2 :

 2 Simulated Annealing Hyper-parameters T 0 Initial temperature T f Final temperature X 0 Starting solution cooling Temperature derating factor (geometric in our case) K b Normalization factor of the acceptance probability iter Number of iterations for each temperature T λ max User-defined accuracy drop (percentage) cal set Calibration set size

  1)) then

	11	current state = next state
	12	E current = E new
	13	if E current < E best then
	14	E best = E current
	15	best state = current state
	16	update(tested)

17

T = T • cooling 18 return best state

DRAM DMA RISC Control + IMEM Input Buffer Weight Buffer Output Buffer 2D SIMD Array

	PE	PE	PE	PE
	PE	PE	PE	PE
	PE	PE	PE	PE
	PE	PE	PE	PE
	Fig. 3: Architectural template of ConvNet accelerators.

Table 3 :

 3 Simulated Annealing Hyper-parameters values

		IC KWS FER
	T 0		512
	T f		2.5
	K b		1e-2
	cooling		2.5
	iter	10	10 2	10 3
	λ max 1% -15%, step 1%
	cal set		2000

  The training set counts of 28708 examples, while the remaining 3589 are in the test set. The adopted ConvNet 4 consists of nine convolutional layers evenly spaced by three max-polling layers, and one fully-connected layer. Each benchmark is powered by a different model whose topology is described in Table4. Within the same table we also collected additional information: the top-1 classification accuracy achieved with the original 32-bit floating-point model (Top-1 Acc.) training w/o any optimization; the overall number of MAC instructions for one inference run using 32-bit floating-point representations (#MAC); the number of possible precision configurations, namely the number of possible operating points in the parameters space (#Op. Points). Concerning the Top-1 accuracy reported in Table4, the results are consistent with the state-of-the-art. They were obtained with a dedicated training and testing framework integrated into PyTorch, version 0.4.1, with the following settings: 150 training epochs using the Adam algorithm[START_REF] Kingma | Adam: A method for stochastic optimization[END_REF]; learning rate 1e-3; linear decay 0.1 every 50 epochs; batch size of 128 samples randomly picked from the training set; non-overlapping testing set and training set.

Table 5 :

 5 Per-Net Precision Scaling: Top-1 Accuracy Operating points. Accuracy drop normalized w.r.t. full precision(16 × 16).fine-tuned model. What we propose instead is the use of a unique set of weights trained at full-precision (i.e. 16-bit for both weights and activations), then, at run-time, data are fetched and processed with the right precision. This is the key advantage of the proposed multi-precision scheme and the main enabler for adaptive ConvNets. As reported in the table, the full-precision fixed-point ConvNets (column 16×16 Fix) keeps almost the same accuracy of the original floating-point model (the maximum relative drop is 0.02% for KWS). The results are in line with previous works and motivate the choice of 16×16 as the baseline for comparison. Concerning the mixed-precision options, 8×16 assigns 8-bit to input maps (I) and 16-bit to the weights (W ); 16×8 does the opposite. The 8×16 option is by far more accurate than 16×8: minimum drop of 0.93% for IC; maximum drop of 2.07% for FER. The half-precision (column 8×8) shows larger loss: minimum drop of 4.90% for KWS; maximum drop 10.97% for IC. These numbers suggest the per-net granularity is too weak for effective deployment of adaptive ConvNets. Among the four available precision options, a very small set per se, only three are of practical use, i.e. 16×16, 8×16, 16×8. Indeed, when precision is reduced to 8 × 8 all the three benchmarks show a dramatic quality degradation. For instance, when shifted from 8 × 16 to 8 × 8, the IC shows a 10× drop (from 0.93% to 10.97%). This calls for a finer precision assignment policy, which is the technique proposed in this work. A detailed analysis of the results is provided by means of a Pareto analysis, Fig.4. The plots show the possible operating points in the energy-accuracy space achieved with a per-net precision scaling (blue ×) and the proposed per-layer precision scaling (red •). Each point comes with a different precision setting. The accuracy drop and the energy savings are normalized with respect to fullprecision (rightmost × marker with 0% accuracy drop). The dotted lines connect the points at the Pareto frontier. As aforementioned, with the per-net granularity only three among four points are Pareto. Moreover, the shift from one operating point to another is very coarse with substantial accuracy drop. The advantage of the per-layer is twofold. First, the Pareto curve is more dense and hence it gives more options for a finer control; this aspect is evident in larger ConvNets

			full	mixed	mixed	half
		32-bit FP 16×16 Fix 8×16 Fix 16×8 Fix 8×8 Fix
	IC	83.04%	83.04%	82.27% 73.07% 73.93%
	KWS 80.94%	80.92%	79.99% 77.26% 76.97%
	FER 65.67%	65.70%	64.31% 62.78% 59.04%
	The table collects the results for the original 32-bit floating-point model and
	the four fixed-point precision options made available with the multi-precision
	arithmetic described in Section 3. To notice that we do not run any retraining
	after quantization. This allows storing a single set of weights for any desired
	precision. Previous works suggest a re-training stage to recover the loss due to
	quantization and this would imply that each precision is coupled with a different

Table 6 :

 6 Comparison between the Per-Net Precision scaling and the Per-Layer Precision Scaling with the proposed SA optimization: the collected statistics refer to the Pareto curves of the two solutions (full-precision excluded). FER). Second, the Pareto curve is dominating the per-net solutions, thus enabling larger (or comparable) average energy savings. Table 6 reports some statistics over the subset of Pareto points, both per-net and per-layer. The column #Op. Points gives the number of Pareto Points; column

		Optimization # Op. Points Av. Drop Av. Savings Av. Exec. Time
	IC	Per-Net SA	2 4	-5.95 -4.84	42.56 42.83	-8 s
	KWS	Per-Net SA	2 4	-3.52 -2.93	40.09 44.95	-13 s
	FER	Per-Net SA	2 8	-6.13 -4.60	41.41 39.83	-66 min 18 s
	(e.g.

We assume the availability of memories that support both word (N -bit) and halfword (K-bit) accesses[START_REF] Jahnke | Micro-controller direct memory access (dma) operation with adjustable word size transfers and address alignment/incrementing[END_REF].

The precision of O does not impact computation as it only affects the number of memory accesses.

https://www.tensorflow.org/tutorials/sequences/audio_recognition

Inspired by https://github.com/JostineHo/mememoji

Table 4: Benchmarks overview. Considering that each convolutional layer with shape (ch, k h , kw), fully-connected with shape (ch), and max-pooling layer with shape (k h , kw). Where k h and kw are respectively the kernel height and width, while ch denotes the number of output channels. Keyword Spotting (KWS): a standard problem in the field of speech recognition. We considered a simplified version of the problem 3 . The reference dataset is the Speech Commands Dataset [START_REF] Warden | Speech commands: A dataset for limited-vocabulary speech recognition[END_REF]; it counts of 65k 1 s-long audio samples collected during the repetition of 30 different words by thousands of different people. The goal is to recognize 10 specific keywords, i.e. "Yes", "No", "Up", "Down","Left", "Right", "On", "Off", "Stop", "Go", out of the 30 available words; samples that do not fall in these 10 categories are labeled as "unknown". There is also an additional "silence" class made up of background noise samples (pink noise, white noise, and human-made sounds). The training set and test set collect 56196 and 7518, respectively. The adopted ConvNet is the cnn-one-fstride4 described in [START_REF] Sainath | Convolutional, long short-term memory, fully connected deep neural networks[END_REF]; it has two convolutional layers, one max-pooling layer and four fully-connected layers. The ConvNet is fed with the spectrogram of the recorded signal which is obtained through the pre-processing pipeline introduced in [START_REF] Sainath | Convolutional, long short-term memory, fully connected deep neural networks[END_REF] (extraction of time × f requency = 32 × 40 inputs w/o any data augmentation).

Application