Georges Gielen

Trent Mcconaghy

Tom Eeckelaert

CAFFEINE: Template-Free Symbolic Model Generation of Analog Circuits via Canonical Form Functions and Genetic Programming

Keywords:

HAL is

Introduction

Symbolic models of analog circuits have many applications. Fundamentally, they increase a designer's understanding of a circuit, which leads to better decisionmaking in circuit sizing, layout, verification, and topology design.

Automated approaches to symbolic model generation are therefore of great interest.

In symbolic analysis, models are derived via topology analysis. [START_REF] Gielen | Techniques and Applications of Symbolic Analysis for Analog Integrated Circuits: A Tutorial Overview[END_REF] is a survey. Its main weakness is that it is limited to linear and weakly nonlinear circuits.

Leveraging SPICE simulations in modeling is promising because simulators readily handle nonlinear circuits, as well as environmental effects, manufacturing effects, and different technologies. Simulation data has been used to train neural networks as in [START_REF] Vancorenland | A Layout-aware Synthesis Methodology for RF Circuits[END_REF][START_REF] Liu | Remembrance of Circuits Past: Macromodeling by Data Mining in Large Analog Design Spaces[END_REF][START_REF] Wolfe | Extraction and Use of Neural Network Models in Automated Synthesis of Operational Amplifiers[END_REF]. However, such models provide no insight.

The aim of symbolic modeling is to use simulation data to generate interpretable mathematical expressions that relate the circuit performances to the design variables.

In [START_REF] Daems | An Efficient Optimization-based Technique to Generate Posynomial Performance Models for Analog Integrated Circuits[END_REF][START_REF] Daems | Simulation-based generation of posynomial performance models for the sizing of analog integrated circuits[END_REF], symbolic models are built from a posynomial template. The main problem is that the models are constrained to a template, which restricts the functional form and in doing so also imposes bias. Also, the models have dozens of terms, limiting their interpretability. Finally, the approach assumes posynomials can fit the data; in analog circuits there is no guarantee of this, and one might never know in advance.

The problem we address in this paper is how to generate symbolic models with more open-ended functional forms (i.e. without a pre-defined template), for arbitrary nonlinear circuits, and at the same time ensure that the models are interpretable. A target flow that reflects these goals is shown in Figure 1.

We approach the question by using genetic programming (GP) [START_REF] Koza | Genetic Programming[END_REF] as a starting point. GP generates symbolic expressions without the using a template, but those functions are overly complex. So, we extend GP via a grammar specifically designed to have interpretable symbolic models. We name the approach CAFFEINE: Canonical Functional Form Expressions in Evolution.

Figure 1: Template-free symbolic modeling flow

The contributions of this paper are as follows:

• To the best of our knowledge, a first-ever tool to do template-free symbolic modeling, with the flexibility of SPICE simulations therefore allowing modeling of any nonlinear circuits.

• A means to make the models compact and understandable, yet with arbitrary accuracy; in fact providing a tradeoff between accuracy and complexity. Final models are highly predictive.

• For GP, a specially designed grammar and related operators to ensure that all functions explored follow a canonical form, making them directly interpretable. This paper is organized as follows. Section 2 defines the problem. Section 3 gives background on GP, on which sections 4 and 5 build to describe CAFFEINE and the grammar. Section 6 has results; section 7 concludes.

Problem Formulation

The problem that we address is formulated as follows: Given:

• A set of {x(t),y(t)},t=1..N data samples where x(t) is a d-dimensional design point t and y(t) is a corresponding circuit performance value measured from simulation of that design.

• No model template

Determine:

• A set of symbolic models * f F ∈ that together provide the optimal tradeoff between prediction error and some measure of complexity.

Speed of model building is not considered a goal at this point; that is left to future research.

Background: Genetic Programming

Genetic Programming (GP) [START_REF] Koza | Genetic Programming[END_REF] is an evolutionary algorithm, with the distinguishing characteristic that GP individuals (points in the design space) are trees.

GP has issues to be addressed before it can be useful in symbolic model generation. GP-evolved functions can be notoriously complex and un-interpretable; e.g. [START_REF] Koza | Genetic Programming[END_REF] showed functions so bloated that they take up a full page of dense text. Also, overfitting is a risk because prediction quality does not influence model choice.

The functional form of results from canonical GP is completely unrestricted.

While this sounds great compared to the restrictions of fixed-template regression, it actually goes a little too far. Most importantly, an unrestricted form is almost always difficult to analyze. Also, an unrestricted form can cause undesirable biases in the search, such as tuning too many parameters which may even be redundant, or making it difficult for to add / remove basis functions. The challenge is to find a way to restrict the form enough to overcome these problems, without constraining away any possible forms.

CAFFEINE

CAFFEINE uses GP as a starting point, but extends it in order to properly address template-free symbolic modeling. It attacks the issues of complexity and interpretability in two main ways: a multi-objective approach that provides a tradeoff between error and complexity, and a specially designed grammar to constrain the search to specific functional forms without cutting out good solutions. It also performs special postprocessing to further improve models. In CAFFEINE, the overall expression is a linear sum of weighted basis functions; therefore, each individual is a set of GP trees.

Multi-Objective Approach

CAFFEINE uses a state of the art multi-objective evolutionary algorithm, namely NSGA-II [START_REF] Deb | A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multiobjective Optimization: NSGA-II[END_REF]. NSGA-II returns a set of individuals that, collectively, trade off error and complexity (i.e. a nondominated set).

"Error" is normalized mean-squared error. "Complexity" is dependent on the number of basis functions, the number of nodes in each tree, and the exponents of "variable combos" (VCs, described later):

nvc( ) , 1 1 complexity( ) ( nnodes( ) vccost( )) M j f b k j j k f w j v c = = = + + å å (1)
where w b is a constant to give a minimum cost to each basis function, nnodes(j) is the number of tree nodes of basis function j, nvc(j) is number of VCs of basis function j, and dim 1 vccost(vc) abs(vc(dim))

d vc w = = å .
The approach accomplishes simplification during generation by maintaining evolutionary pressure towards lower complexity. The user avoids an a priori decision on error or complexity because the algorithm generates a set of models that provide tradeoffs of alternatives.

Grammar and Operators

In GP, a means of constraining search is via a grammar, as in [START_REF] Whigham | Grammatically-based Genetic Programming[END_REF]. Evolutionary operators must respect the derivation rules of the grammar, i.e. only subtrees with the same root can be crossed over, and random generation of trees must follow the derivation rules. A basis function is the leaf nodes (terminal symbols) of the tree; internal nodes (nonterminal symbols) reflect the underlying structure; the tree root is the start symbol.

Even though grammars can usefully constrain search, none have yet been carefully designed for functional forms. In designing such a grammar, it is important to allow all functional combinations (even if just in one canonical form). This includes an arbitrary number of products of expressions, and of sums of expressions. Any desired single-input, dual-input, etc should be allowed.

The CAFFEINE grammar maintains functions in a "canonical form" and meets those goals: Terminal symbols are in quotes. Each nonterminal symbol has a set of derivation rules separated by '|'. The start symbol is REVPC; one tree is used for each basis function; basis functions are linearly weighted using leastsquares learning. Basis function operators include: creating a new individual by randomly choosing >0 basis function from each of 2 parents; deleting a random basis function; adding a randomly generated tree as a basis function; copying a subtree from one individual to make a new basis function for another.

The root is a product of variables and/or nonlinear functions (REPVC and REPOP). Within each nonlinear function is a weighted sum of basis functions (REPADD). Each basis function can be, once again, a product of variables and/or nonlinear functions. And so on.

The grammar is context-free, with two exceptions for the sake of enhanced search:

• Weights (W). A real value is stored in the range In this way parameters can take on very small or very large negative or positive values. Zero-mean Cauchy mutation [START_REF] Yao | Evolutionary Programming Made Faster[END_REF] is an operator on the real value.

• Single-basis rational combinations of variables (VC). With each VC a vector is stored, with integer value per design variable as the variable's exponent. An example vector is [1,0,-2,1], which means ( * ) ( ) x x

x . For interpretability, real-valued and fractional-valued exponents are not allowed. VC operators include: one point crossover, and randomly adding or subtracting to an exponent value.

POW(a,b) is a b . Via 2ARGS with MAYBEW, either the base or the exponent (but not both) can be constants.

The designer can turn off any of the rules if they are considered unwanted or unneeded. For example, one could easily restrict the search to polynomials or rationals, or remove potentially difficult-to-interpret functions such as sin and cos. The designer could change or extend the operators or inputs, e.g. include w i , l i , and w i / l i .

CAFFEINE Post-Processing

After the evolutionary run is complete, simplification after generation (SAG) is performed on each of the final set of models in the tradeoff. SAG is accomplished via the Predicted Residual Sums of Squares (PRESS) statistic ( ) ( ) t t ξ - [START_REF] Breiman | Stacked Regression[END_REF] coupled with forward regression [START_REF] Hong | A Robust Nonlinear Identification Algorithm Using PRESS Statistic and Forward Regression[END_REF]. PRESS approximates leave-one-out cross-validation on the linear parameters; forward regression prunes basis functions that harm predictive ability. This gives predictive robustness to the linear parameters.

After that, the tradeoff models are evaluated on test data, and filtered down to only models that are on the tradeoff of testing error and complexity. Such a final step might not be possible with more deterministic approaches having more homogenous results, but the stochastic nature of CAFFEINE, causing more heterogeneous results, makes such filtering possible. Single-input operators allowed were:

x , log e (x), log 10 (x), 1/x, abs(x), x 2 , sin(x), cos(x), tan(x), max(0, x), and min(0,x), 2 x , 10 x , where x is an expression. Doubleinput operators allowed are x 1 +x 2 , x 1 *x 2 , max(x 1 ,x 2 ), min(x 1 ,x 2 ), power(x 1 ,x 2 ), and x 1 /x 2 . Also, lte(testExpr, condExpr, exprIfTestLessThanCond, elseExpr) and lte(testExpr, 0, exprIfTestLessThan0, elseExpr) were used. Any input variable could have an exponent in the range {…,-2, -1, 1, 2, …}. While real-valued exponents could have been used, that would have harmed interpretability.

The circuit being modeled is a high-voltage CMOS OTA as shown in Figure 2. The goal is to discover expressions for low-frequency gain (A LF ), unity-gain frequency (f u ), phase margin (PM), input-referred offset voltage (v offset ), and the positive and negative slew rate (SR p , SR n ). To allow a direct comparison to the posynomial approach [START_REF] Daems | Simulation-based generation of posynomial performance models for the sizing of analog integrated circuits[END_REF], an almost-identical problem setup was used, as well as identical simulation data. The only difference is that because scaling makes the model less interpretable, neither the inputs nor outputs were scaled; the one exception is that f u is log-scaled so that mean-squared error calculations and linear learning are not wrongly biased towards high-magnitude samples of f u .

The technology is 0.7 Nm CMOS. The supply voltage is 5V. V th,nom is 0.76V and -0.75V for NMOS and PMOS devices, respectively. The load capacitance is 10 pF.

Good training data is essential to the methodology. The choice of design variables and sampling methodology determines the extent to which the designer can make inferences about the physical basis, and what regions of design space the model is valid in. We used an operating-point driven formulation [START_REF] Leyn | An Efficient Dc Root Solving Algorithm with Guaranteed Convergence for Analog Integrated CMOS Circuits[END_REF], where currents and transistor drive voltages comprise design variables (13 variables in our case). Device sizings could have been used instead; it all depends on designer preference. Full orthogonal-hypercube Design-Of-Experiments (DOE) sampling of design points was used, with scaled dx=0.1 (the simpler problem of dx=0.01 is ignored in this paper) to have 243 samples with three simulations each, some of which did not converge. Simulation time for one sample was about 1 s, or 4 min for all samples; this is fully dependent on the circuit, analyses, and experimental design being used. These samples, otherwise unfiltered, were used as training data inputs. Testing data inputs were also sampled with full orthogonal-hypercube DOE and 243 samples, but with dx=0.03. Thus, in this experiment we are creating a somewhat localized model; one could just as readily model a broader design space.

The run settings were: maximum number of basis functions = 15, population size 200, 5000 generations, maximum tree depth 8, and parameter range . All operators had equal probability, except parameter mutation was 5x more likely. Complexity measure settings were w b = 10, w vc = 0.25. Just one run was done for each performance goal, for 6 runs total. (The aim was proof-of-concept, not efficiency.) Each run took about 12 hours on a 3 GHz Pentium IV Linux workstation. After each run, SAG (section 5.1) was done, taking about 10 min. We use normalized mean-squared error on the training data and separate testing data, which are standard measurements in regression literature. Testing error is ultimately the more important measure. These measures are identical to two of the three posynomial "quality of fit" measures [START_REF] Daems | Simulation-based generation of posynomial performance models for the sizing of analog integrated circuits[END_REF]: q wc is training error, and q tc is testing error. (q wc and q tc are identical as long as the constant 'c' in the denominator is zero, which [START_REF] Daems | Simulation-based generation of posynomial performance models for the sizing of analog integrated circuits[END_REF] did.) We ignore q oc , which measured the error at just one training point.

Results and Discussion

Let us first see if CAFFEINE generates tradeoffs between training error (q wc ) and complexity, as expected. As expected, the number of basis functions usually rises with the complexity. This is not always the case, however, as larger trees increase complexity too; the plateaus and dips in the basis function curves show that this does indeed occur. In every case, CAFFEINE used the maximum allowed number of basis functions (15) to achieve the lowest error. Undoubtedly, error could have been reduced further, but models with 15 basis function models are already at the edge of interpretability.

The testing error (q tc ) is also shown in Figure 3. We see that unlike training error, it is not monotonically decreasing as complexity rises. This means that some less complex models are more predictive than more complex ones. However, if we prune the models down to the ones that give a tradeoff between testing error and complexity, we get the rightmost column of Figure 3. These 5-10 models for each performance goal are of the most interest.

It is notable that the testing error is lower than the training error in almost all cases. This sounds promising, but such behavior is rare in the regression literature, and made us question what was happening. It turns out there is a valid reason: recall that the training data is from extreme points of the sampling hypercube (scaled dx=0.10), and the testing data is internal to the hypercube (dx=0.03). This testing data tests interpolation ability. Thus, models that really are predictive should be able to interpolate well, even at the cost of a perfect fit to the extreme points. In any case, to validly have testing error lower than training error demonstrates the strength of the CAFFEINE approach.

Let us now examine the actual symbolic models generated by CAFFEINE. We ask: "what are all the symbolic models that provide less than 10% error in both training and testing data?" Table I shows those functions (f u has been converted to its true form by putting the generated function to the power of 10). We see that each form has up to 4 basis functions, not including the constant. For v offset , a constant was sufficient to keep the error within 10%. We see that a rational functional form was favored heavily; at these target errors only one nonlinear function, ln( ), appears (for A LF ).

That expression effectively says that the order of magnitude of some input variables is useful.

One can examine the equations in more detail to gain an understanding of how design variables in the topology affect performance. For example, A LF is inversely proportional to i d1 , the current at the OTA's differential pair. Or, SR p is solely dependent on i d1 and i d2 and the ratio i d1 / i d2 . Or, within the design region sampled, the nonlinear coupling among the design variables is quite weak, typically only as ratios for variables of the same transistor. Or that each expression only contains a (sometimes small) subset of design variables. Or, that transistor pairs M1 and M2 are the only devices affecting five of the six performances (within 10%).

  REPVC => 'VC' | REPVC '*' REPOP | REPOP REPOP => REPOP '*' REPOP | 1OP '(' 'W' '+' REPADD ')' | 2OP '(' 2ARGS ')' | ... 3OP, 4OP etc 2ARGS => 'W' '+' REPADD ',' MAYBEW | MAYBEW ',' 'W' '+' REPADD MAYBEW => 'W' | 'W' '+' REPADD REPADD => 'W' '*' REPVC | REPADD '+' REPADD 2OP => 'DIVIDE' | 'POW' | 'MAX' | ... 1OP => 'INV' | 'LOG10' | ...

  user-set, e.g. 10.

Figure 2 : 6 . 1

 261 Figure 2: Schematic of high-speed CMOS OTA 6 Experiments

Figure 3

 3 Figure 3 illustrates tradeoff results. In each instance, CAFFEINE generates a tradeoff of about 50 different models. As expected, a zero-complexity model (i.e. just a constant) has the highest training error of 10-25%; the highest complexities have the lowest training error, of 1-3%. Since only one run was done for each performance characteristic, the reliability of the algorithm is promising.

Figure 3 :

 3 Figure 3: The two leftmost columns show generated models' training error (qwc), testing error (qtc), and number of bases vs. complexity for each performance goal; all models in the tradeoff of training error vs. complexity are shown. The rightmost column shows only models that are on the tradeoff of testing error vs. complexity too.

Table I : CAFFEINE-generated symbolic models which have less than 10% training and testing error

 I

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

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

By only putting the relevant variables into a model, the approach demonstrates the potential to provide expressions for circuits with significantly more variables.

One may improve understanding in another fashion: by examining expressions of varying complexity for a single performance characteristic.

Low-complexity models will show the macro-effects; alterations to get improved error point show how the model is refined to handle second-order effects. Table II shows models generated for PM in decreasing training and testing error. A constant of 90.2, while giving 15 % training error, had only 4% test error. For better prediction, CAFFEINE injected two more basis functions; one basis being the current into the differential pair i d1 , the other basis, i d2 / v ds2 , the ratio of current to drain-source voltage at M2. The next model turns the input current term into a ratio i d1 / v sg1 . Interestingly, and reassuringly, almost all ratios use the same transistor in the numerator and denominator.

Such analyses achieve the aim of this tool: to improve understanding of the topology. We also compared CAFFEINE to the posynomial approach using the numbers in [START_REF] Daems | An Efficient Optimization-based Technique to Generate Posynomial Performance Models for Analog Integrated Circuits[END_REF]. We first compare the test and training errors. To pick a model from a CAFFEINE-generated tradeoff for comparison, we fixed the training error to what the posynomial achieved, then compared testing errors. Results are in Figure 4. In one case, v offset , CAFFEINE did not meet the posynomial training error (0.4%), so it probably could have for more basis functions; we instead picked an expression which very nearly matched the posynomial approach's testing error of 0.8%. What we saw in previous data, and we see again here, is that CAFFEINE has lower testing error than training error, which provides great confidence to the models.

In contrast, in all cases but v offset , the posynomials had higher testing error than training error, even on this interpolative data set. CAFFEINE models' testing errors were 2x to 5x lower than the posynomial models. The exception is v offset , where the posynomial achieves 0.8% testing error compared to 0.95% for CAFFEINE. With posynomials having weak prediction ability even in interpolation, in comparison to more compact models, one might question the trustworthiness of constraining models of analog circuits to posynomials.

Conclusion

This paper presented CAFFEINE, a tool which for the first time can generate interpretable, template-free symbolic models of nonlinear analog circuit performance characteristics.

CAFFEINE is built upon genetic programming, but its key is a grammar that restricts symbolic models to a canonical functional form.

CAFFEINE generates a set of models that collectively trade off between error and complexity. Visual inspection of the models demonstrates that the models are interpretable. These models were also shown to be significantly better than posynomials in predicting unseen data.


Nicolo Manaresi

Gianni Medoro

Melanie Abonnenc

Vincent Auger

Paul Vulto

Aldo Romani

Luigi Altomare

Marco Tartagni

Roberto Guerrieri

Nicolò Manaresi

New Perspectives and Opportunities From the Wild West of Microelectronic Biochips

come

Background

The trend of miniaturization for bioanalysis is an emerging field, which is perceived to be very promising due to its potential of bringing the "cheaper, better, faster" motto to analytical practices in many application domains, such as diagnostics, biotechnology, environmental protection. Many of the early developments in this field have been based on photolithography and microfabrication of glass or plastic devices with processes borrowed from microelectronic technology. More recently, there has been a growing use of true CMOS chips for the implementation of Lab-on-a-chip [1].

In our group we pioneered the development of biochips for single-cell manipulation and detection based on CMOS [2]. An array of more than 100,000 electrodes is programmed to create electric fields in a drop of liquid (~4µl) on top of the chip, thus creating tens of thousands dielectrophoretic (DEP) cages which can trap cells in levitation [START_REF] Manaresi | A CMOS Chip for Individual Cell Manipulation and Detection[END_REF]. Changing the pattern of voltages applied to the electrodes, the DEP cages can be shifted, thus dragging along the trapped particles. To each electrode an optical or capacitive sensor [START_REF] Romani | Capacitive Sensor Array for Localization of Bioparticles in CMOS Lab-on[END_REF] can be associated, to detect particle presence.

Taking the development of these chips as a case study we can make some general considerations which apply also to other applications, and give an idea of opportunities and challenges lying ahead in this exciting brave new world of lab-on-a-chip.

Electronic design perspective: different constraints same design-flow

Fig. 1 shows a sketch of typical design flow related to integrated circuits design. High cost of prototypes, long turnaround time for fabrication, availability of accurate models favour the choice of this approach. The same is still convenient for the design of electronic part of biochips, although many constraints must be revised in light of the application. As an example, in our case, cell size is specified by biology, so there is no need to make an array with electrode pitch much smaller than that. Even more important is the fact that latest generation technologies have a reduced supply voltage while actuation (DEP force dependent on voltage square) and sensing (signal dynamic range) benefit from a larger supply voltage. This lead to a first consideration: older generation technologies may best fit your purpose.

Further, cells move, in response to DEP forces, at a typical rate of 10-100 microns per second, which means that we have plenty of time (from an electronic point of view) to program the actuator array, scan sensor output etc. This is an opportunity not only to achieve design goals with an older technology but also to trade time of execution for quality of the results, e.g. averaging sensors output for thermal noise reduction. Thus we can make a second consideration: typical speeds related to transfer of mass (or heat) are quite slow compared to electronic timescale. There is room to exploit this creatively.

Fluidic and packaging design

A very important aspect of a biochip is represented by the microfluidic and packaging implementation which represents a significant part of the design effort and of the final device cost. By fluidic, we would include here not only aspects related to the flow of liquid samples, but also, in a wider sense, the management of the sample itself for the analysis (thus including design aspects related to DEP in our example). Packaging is functional to the implementation of the desired fluidic structure, electrical connection etc. and is a key issue deeply connected with the fluidic aspects.

In this realm, although Computational Fluid Dynamics and multi-physics simulation tools are making big progresses, modeling of all relevant effect in the operation of a biochip is still a very complex task. Surface properties and wettability, heating and evaporation, electro-thermal flow, AC electro-osmosis, electric field and dielectrophoresis, modelling of cells, are all aspects requiring not only a wide knowledge of the physics behind those phenomena, but also demand -to have meaningful simulations-a lot of input parameters which are uncertain or completely unknown, thus making simulation pretty much a research topic in itself.

On the other hand, fluidic circuits can often be implemented with photolithographic processes with a moderate resolution, since minimum feature size are typically in the order of hundred microns (especially when dealing with cells which may measure 20-30µm). Moreover, fluidic design typically requires a simple mask layout (one or two layers), and fabrication can thus be achieved with a corresponding short turnaround. As a consequence it is often faster to build and test a prototype than to simulate it. This suggests a new approach, sketched in Fig. 2. In this perspective, simulation is not a substitute to the realization and testing of a prototype, but still has a role in helping the designer with better understanding of test results and design optimization.

In the perspective of this new design work-flow for fluidic packaging of hybrid chips we developed some special techniques [START_REF] Vulto | Microfluidic channel fabrication in dry film resist for production and prototyping of hybrid chips[END_REF] to achieve fast turnaround time (two-three days from design to device) and very low cost both for the masks (few euros) and overall set-up for fabrication (tens of thousands euros).

Fig. 1 -

 1 Fig. 1 -Electronic design flow. Simulation is used for verification, and further contribute to performance optimization through design centering (dashed line). After meeting specifications in simulation, one resort to fabrication and testing, with the objective to avoid lengthy and expensive further iterations (dotted line).

Fig. 2 :

 2 Fig. 2: Fluidic packaging design-flow. Fabrication and testing is an integral part of the design cycle. Simulation contributes with insights and interpretation of experimental data from tests, and is also useful (dashed line) to optimize the design.

Fig. 3 :

 3 Fig. 3: CMOS biosensor/actuator for cell-analysis. The fluidic microchamber packaging is implemented double bonding the ito-coated glass, patterned with dry-resist film, to a CMOS chip.

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


M J Absar

F Catthoor
email: francky.catthoor@imec.be

Compiler-Based Approach for Exploiting Scratch-Pad in Presence of Irregular Array Access

Scratch-pad memory is becoming an important fixture in embedded multimedia systems. It is significantly more efficient than the cache, in performance and power, and has the added advantage of better timing-predictability. Current techniques for the management of the scratch-pad are quite mature in the case of arrays accessed in a regular fashion, i.e. inside nested-loop by index expressions which are affine functions of the loop-iterators. Many multimedia codes, however, also use arrays as subscripted variables in the index expression of other arrays, thereby making the access pattern irregular. Existing techniques fail in such cases, bringing down the performance. In this paper, we extend the framework that exists today, to the case of irregular access. We provide a clear and precise compiler-based technique for analyzing irregular array-access, and efficiently mapping such arrays to the scratch-pad. On the average, 20% reduction in energy consumption, for a set of realistic applications, was achieved using our methods 1 .

Introduction

Multimedia and signal processing embedded systems access large amounts of data, abstracted as multi-dimensional arrays, inside multilevel nested-loop. Such software include audio, video, image processing, encryption-decryption and network software, among others. Optimization of the memory access, therefore, forms an important step in the power-reduction and performance-enhancement of such applications [START_REF] Catthoor | Custom Memory Management Methodology: Exploration of Memory Organization for Embedded Multimedia System Design[END_REF].

Scratch-pad memory (SPM), a relatively small (2-4 KB) onchip data-memory, is becoming popular these days. Being a memory without any control hardware, it operates at a much lower cost compared to the cache.

In the cache, decisions such as which data-set should continue to reside in the cache, and which ones must be evicted to make room for new ones, are made by the hardware. On the other hand, data-movement to and from the SPM happens under program control. This implies that the compiler or the software developer must identify which arrays, and which section therein, should be mapped to the SPM at any point.

Today, in the industry, this optimization is largely done manually. This makes it difficult to keep track of global trade-offs, and requires significant effort for exploration and verification.

In the past, investigation has been done [START_REF] Kandemir | A compiler-based approach for dynamically managing scratch-pad memories in embedded systems[END_REF] [START_REF] Issenin | Data reuse analysis technique for software-controlled memory hierarchie[END_REF] of techniques for SPM-management of arrays indexed using affine functions of the loop-iterators. We identify this type of array-access as direct-indexing. Direct-indexing is also sometimes referred to as regular-access in the current literature. Many multimedia codes, however, also index arrays using other arrays. Current techniques map these indirectly-indexed arrays either, as a whole [START_REF] Panda | Efficient utilization of scratch-pad memory in embedded processor applications[END_REF] onto the SPM or, reject it altogether if it does not fit completely in the SPM. Not incorporating the flexibility of moving only the relevant parts of the indirectly-indexed multidimensional-arrays onto the SPM, implies a sub-optimal solution. The space in the SPM is limited and one array occupies it at the expense of others.

In this paper, we identify, for indirectly-indexed arrays, the critical portions that need to be on the SPM at different instances of time. We propose a new framework for representing indirectly-indexed arrays. This framework builds upon the existing ones [START_REF] Kandemir | Improving cache locality by a combination of loop and data transformation[END_REF] [START_REF] Wolf | A data locality optimizing algorithm[END_REF] for directly-indexed arrays, by an important extension. Using a cost-model, we perform a trade-off exploration between the size of the array that must be moved to the SPM, and the resulting benefit from any increased reuse of that data. The right loop level, for a multilevel loop, at which the transfer-code should be inserted is analyzed to maximize reuse. To our best knowledge, this is the first work that investigates dynamic-management of SPM for arrays that are indirectly-indexed.

Motivating Examples

for( i = 0 ; i < N ; i++) for( j = 0; j < M ; j++ ) for( k = 0 ; k < 16 ; k++ ) for( l = 0 ; l < 16 ; l++ ) .

..= image[ 16*i + x[i][j] + k ] [ 16*j + y[i][j] + l ];
The code above is from QSDPCM [START_REF] Stobach | A new technique in scene adpative coding[END_REF], an inter-frame image compression algorithm. In the code, three arrays -'x', 'y', and 'image' -are referenced. These three, therefore, form potential candidates for mapping to the SPM. Arrays 'x' and 'y' (motion-vectors) are relatively small in size (N*M). So they can be migrated completely to the SPM. Also, since they are indexed in a regular manner (only via iterators), we know precisely, at compile-time, the row-number of each of them that would be accessed for a given value of 'i'. Therefore, it is also possible to map only a single row of 'x' and 'y', for a given value of 'i'. As the computation moves to the next value of 'i', the next row of 'x' and 'y' can be moved to the SPM, overwriting the previous one. This is one way of mapping regularly accessed arrays using data-space tiling [START_REF] Kandemir | A compiler-based approach for dynamically managing scratch-pad memories in embedded systems[END_REF].

Next, consider the mapping of 'image' to the SPM. Since it is indirectly-indexed, current techniques would try to map it as a whole. But that may not be always possible (e.g. a 256 × 256 image would need 64KB of SPM). Observe that for a given value of 'i' and 'j', the 16×16 block in the 'image' that is accessed is actually precisely known at (and only at) run-time. Therefore, one possible mapping of 'image' to SPM is by copying the 16 × 16 block inside the loop of 'i' and 'j', as shown in the code below: for( l = 0 ; l < 16 ; l++ ) ...= spm_image[k][l];} In the above code, the symbol dest <src means that the specified set of elements are moved from the external memory (src) to the SPM (dest). This can be done efficiently using a DMA (Direct-Memory Access) controller. Fig. 1 (left-side) shows pictorially this selection process. The SPM-mapping of 'image', as described so far, exploits only spatial reuse. In practice, however, the values that the elements of 'x' hold, is much smaller than the dimensions of 'image'. This information enables our algorithm to do a much better mapping, with potentially high temporal reuse. Assume that the range of values in 'x' is limited to [L, U ]. Fig. 1 (right-side) shows for a given 'i', the region of 'image' that should be mapped to the SPM. All access to 'image' for that value of 'i' would, therefore, always result in hit to the SPM. Temporal reuse resulting from overlapping blocks are then well exploited. Simplified code for the transfer is shown below:

...= spm_image[ -L + x[i][j] + k ]

[ 16*j + y[i][j] + l ];} We now show some general cases where spatial and temporal reuse can (or cannot) be identified at compile-time. We show four different access patterns of the same array A[20][30]. Array A is accessed inside a two-level nested-loop: for(i = 1...5)for(j = 1...5)..

. = A[• • •][• • •]. In Fig 2.i, A is referenced as A[E[i][j]][F [i][j]].
The rectangle in Fig. 2.i represents the 2-D data-space of A. The pair of numbers (i, j) beside each black dot (element of A) shows points in the iteration-space at which that particular element of A is accessed. Fig 2 .i has low compile-time detectable reuse, because for each value of i and j, a potentially different row of A (via array E) and a different column of A (via array F ) can be selected. In Fig. 2.ii, A is referenced as

A [B[i]] [C[j]].
In this case, as long as i remains constant, the same row of A would be accessed, independent of the contents of C. Therefore, before the start of each j-loop, the entire row A [B[i]] [0 : 29] can be copied to the SPM. Fig. 2.iii shows an instance of temporal reuse. With the reference as

A [B[j]] [C[j]]
, the same set of elements of A are reused over each value of i. Fig. 2.iv, with reference A[B[i]+j][15], shows a case where both temporal and spatial reuse exist. Since the number of access (25) exceeds the distinct number of elements accessed (20), we clearly have reuse (pigeon-hole principle). Fig. 2.iv shows one possible reuse pattern.

Exactly which elements are reused may not be known at compile-time. However, even without that precise information, in many cases, as in the above examples, it is often clear at compile-time, itself, that reuse exists. This is often sufficient to enable a good SPM-mapping.

Related Work

Techniques for improving the performance of hierarchal memories in the case of regular (directly-indexed) array access have been deeply studied. Over a decade ago, Utpal Banerjee [START_REF] Banerjee | Data Dependenies[END_REF] showed that unimodular matrices could be used to represent loop transformations, such as interchange, skewing and reversal, in a mathematically elegant form. Wolf and Lam have shown that using unimodular matrices simplifies datadependence checks [START_REF] Wolf | A data locality optimizing algorithm[END_REF] when a nested-loop undergoes a series of loop-transformations, each instrumented as a unimodular transformation. Lam and others use loop-transformations to take advantage of any data-reuse. That is, loop structure is changed so that all the consumption of the same data is moved closer in time. Though proposed with cache-based system in mind, temporal locality enhancement is a fundamental step in improving code for any hierarchical memory structure, including scratch-pad based systems.

In addition to changing the loop-structure, which affects all arrays inside the loop sometimes in a conflicting way, several researchers, in the recent past, have focused on applying data transformations to improve spatial locality for the cache [7] [11]. Kandemir proposed an efficient compiler-based technique for mapping applications to the scratch-pad [START_REF] Kandemir | A compiler-based approach for dynamically managing scratch-pad memories in embedded systems[END_REF]. His technique, however, applies only to arrays with regular access.

The Chaos Group has studied partitioning and reorganization of data at run-time [START_REF] Das | Communication optimizations for irregular scientific computation on distributed memory architectures[END_REF], in order to balance computational load across processors. They introduce the concept of inspector-executor. The inspector first analyzes the pattern of access, and then the executor changes the loop-structure (computation) and layout to exploit the reuse. The analysis, grouping and loop transformations are all performed at runtime. Using this technique, problems such as ocean simulation, n-body problem and molecular dynamics [START_REF] Ding | Improving cache performance in dynamic applications through data and computation reorganization at run time[END_REF] can be optimized. This technique, however, requires expensive run-time processing to isolate temporal and spatial locality. Run-time analysis is unavoidable in some cases. But based on our observation that multimedia codes, even those with irregular access, can be quite well analyzed at compile time for locality, we take a different approach in this paper. A more thorough analysis is possible in our case, because it is performed at compile-time and not at run-time.

Irregularity over an Iterator

In this section, we describe the concept of regularity and irregularity of an array over an iterator. We use this concept, later, to optimize the SPM-mapping of indirectly-indexed arrays. Our context is a nested-loop represented by an iteration vector, I, which contains the loop iterators from the outermost position to the innermost. The arrays are accessed inside the body of the loop-nest. Each array may contain other arrays in its index expression, in addition to the iterators and constants. We use Example 3 below to explain our representation. EXAMPLE 3 for(i = ...) for(j = ...) for(k = ...)

.

.. = A[ B[ C[k][k+1] + D[j] ] + i ][i+j]

Definition (Indirectly-Indexed Array) 1: An array is defined as indirectly-indexed if its index expression contains one or more arrays. Otherwise, it is termed as directly-indexed.

C = R C I + o C = 0 0 1 0 0 1   i j k   + 0 1
We extend this representation to incorporate indirect-indexing.

We consider an m-dimensional array X, with reference X , as composed of three components:

• S X : an m × 1 vector of array elements that indirectlyindex X. Each element of S X is an affine function of such arrays. • R X I: represents the iterators involved in the directindexing of X. For an m-dimensional array in an n-level nested-loop, R will be an m × n matrix.

• o X : m × 1 vector of constants. The arrays in S X have these three same components, as well, in their reference.

The reference

C[k][k + 1] (directly-indexed) is represented as: C = 0 0 SC + 0 0 1 0 0 1   i j k   RC I + 0 1 oC . Reference B[C[k][k + 1] + D[k]] (indirectly-indexed) is expressed as: B = C C + D D SB + 0 0 0   i j k   RB I + 0 oB
Operator • takes as input a reference (column) vector, and returns the corresponding element. For example,

C k k + 1 translates to element C[k][k + 1].
We now give the generic representation for any directly or indirectly-indexed access. Consider an m-dimensional array X, referenced as X , inside an n-level loop-nest. In the p th dimension of X, the q th indirectly-indexing array is denoted as U p,q . For example:

X[U 11 • + U 12 • . . .][U 21 • . . .].
The reference of U p,q is denoted as Up,q . A generic reference is, therefore, represented as:

X =    q U 1,q U1,q q U 2,q U2,q . . .    + R X I + o X
To keep it simple, we have omitted coefficients for U p,q . Definition (Irregular over an Iterator in a Dimension) 2: An m-dimensional array with reference X is defined as "irregular in the p th dimension, over iterator i", if at least one of the two hold:

1) for some q, i appears in the index expression of U p,q 2) for some q, U p,q is irregular over i in at least one of its dimensions. For example, array C, with reference

C[k][k + 1], is regular over {k} in both its dimension. Array B in B [C[k][k + 1] + D[j] + i], is irregular over {j, k}, but is regular over {i}. Array Y , in Y [Z[i][j] + j] [k]
, is irregular over {i, j}, and regular over {j}, in the first dimension. It is regular over {k} in the second dimension. Technique for computing the regular and irregular sets is given in the Appendix.

Identifying and Exploiting Locality

Here, we describe an algorithm for SPM mapping of indirectly and directly indexed arrays, using the concept of regular and irregular sets developed in the previous section.

A. The Cost Model

Consider a loop-nest with

I = [ i 1 i 2 • • • i n ] T .

B. Search-Space Exploration 1) Illustrating Example:

We explain our algorithm, firstly, with an example. Fig. 3 (left-column) shows a four-level nested-loop with I = [ i 1 i 2 i 3 i 4 ] T . In this loop, array

A[100][200] is referenced as A[ B[i 2 ]+i 3 ][ C[i 1 ]+i 4 ].
We can choose to do transfers of A, to the SPM, at five possible points. For instance, we could make a copy just before the start of loop i 4 . That point is labeled as migration-point m 4 in the figure. At the point m 4 , i 1 , i 2 and i 3 each have a fixed value, temporary albeit. Starting at row B[i 2 ] + i 3 and column C[i 1 ] + 2, the next four locations in that row can be copied to the SPM. These five locations, therefore, form a copy-candidate. The SPM-Mapping (third) column in Fig. 3 shows how much of the SPM gets filled with that copy. The number of times this transfer would happen equals the number If we next try to do the copying at migration-point m 2 , we must copy the entire 100 rows for the column C[i 1 ] + 2 to column C[i 1 ]+6 (inclusive). The transfer will have to be done only 50 times. As pictorially illustrated in the Fig. 3, with a slight increase in copy size we get an enormous reduction in the number of transfers ( from 250, down to 50).

That leaves us with two additional migration points: m 1 , where we attempt to copy the entire array, but it is not possible because of limited SPM size; and m 5 , where it is cheaper to access the external memory directly.

For each of the migration-points above, we can compute the T ransf er Cost. We chose the point that has the least cost. Note that Access Cost is independent of the migration-point.

2) Search-Space Exploration Algorithm: Consider a nestedloop with

I = [ i 1 i 2 • • • i n ] T .
In our algorithm, we will need to describe subsets of the iterators. The set of all iterators is denoted as

I = {i 1 , i 2 , • • • , i n }. We define I k , subset of I, as {i k , i k+1 , • • • , i n }; e.g. I 2 = {i 2 , i 3 , • • • , i n }.
The m-dimensional, indirectly-indexed, array X is accessed inside the loop-nest I described above. The size of

X is D 1 × D 2 × • • • × D m . In C-Language, X could be declared as int X[D 1 ][D 2 ] • • • [D m ]. X is referenced as X[E 1 ][E 2 ] • • • [E m ],
where each E p is a linear expression of iterators and indirectly-indexing arrays (U p,q ). That is, X = q U 1,q U1,q q U 2,q U2,q

• • • T + R X I + o X .
We refer to U p,q 's as the indirectly-indexing arrays at the firstlevel. The iterators over which X is regular (irregular) in the p th dimension is represented as α p (β p ).

The n-level input loop-nest has n! possible permutations. In practice, n is usually small (less than 7). For each permutation, σ, we do the following. Starting from the innermost loop (i n ), we traverse to the outermost loop (i 1 ), computing the T ransf er Cost for each migration-point. The migration point m k is located inner to the loop of iterator i k-1 but outer to loop of i k (e.g. see Fig. 3). Note that, during the execution, each time the program reaches the point m k , the iterators in the set I -I k have a fixed valid value.

Our main data-structure for the algorithm is config. It has three components: 1. An array called range, 2. A number k which specifies the migration-point m k , and 3. The T ransf er Cost for the migration-point m k . The element range[p] contains the lower and upper limits of the p th dimension that must be transferred. As seen in Algorithm 1, the search-space is traversed via two loops. The outer loop, k = n . . . 1, is over the migration-points, starting from m n (inner-most) and moving up to m 1 . The second loop, p = 1 . . . m, is over the dimensions of the array X. For a given m k , and a particular dimension p, our focus is to: find the range of the p th dimension of X that must be transferred to the SPM, assuming that the migration-point has been fixed as m k .

We, first of all, check if any of the iterators in I k are present in the irregular set (β p ). Recall that iterators in β p are those used to indirectly index X in the p th dimension. Also, iterators in the set I k are those not having a definite fixed value at m k . They cover a range. Therefore, if any iterator in I k is also present in β p , we cannot know the exact locations in p th dimension of X that would be accessed. Therefore, if I k ∩ β p = φ (φ is the null-set), we copy the entire range (0 . . . D p -1) to the SPM (see Algo. 1).

If I k ∩ β p = φ, then we check the regular set, α p , which represents iterators generating regular access in the indexexpression E p . Iterators in I -I k have a fixed value at m k . Therefore, the free-iterators in E p -those representing not one particular value at m k , but a range -is the set α p ∩ I k . These iterators in E p are analyzed to determine the range of the p th dimension of X that should be to the SPM. We use the Omega Library to do symbolic range computation [START_REF] Kelly | The omega library: Framework and algorithm for analysis and transformation of scientific programs[END_REF]. If I k ∩ α p = φ, then only a single point in this dimension is to be transferred.

For each m k , a conf ig k is generated. It contains the range information and associated T ransf er Cost. If the sizes in range amount to more than the allocated SPM-size, the cost is set to infinity (not shown in Algo. 1). We choose the optimal config as one with the minimum cost. This is compared with the No SPM-Mapping, i.e. direct access from external memory.

The data-layout of X should be changed so that the dimension that has the largest range is the fastest changing dimension [START_REF] Kandemir | Improving cache locality by a combination of loop and data transformation[END_REF]. This data-layout will result in the least number of DMA-transfers. In other words, based on the dimensions of the hyper-cuboid that must be transferred, the layout must be such that the longest edge is stored contiguous in memory. Now we consider the case when the range of values assumed by the elements of (at least some) indirectly-indexing arrays are provided to the algorithm. In real embedded application, this is usually possible because, even for data-dependent parameters, the designers typically apply some bounds. With that information, in Algo. 1, for the case I k ∩β p = φ, we do not automatically extend the range to full-length (0 . . . D P -1). Instead, arrays, such as U p,1 , U p,2 , . . ., which indirectly index X at the first-level in the p th dimension, are treated as variables that can assume any value in the specified range. Also, iterators in E p belonging to the set I k ∩ α p , i.e. those iterators whose value is not fixed at m k , are also treated as variables. Treating the rest of the iterators in E p as constants, the total range is computed. Note: only those indirectlyindexing arrays that are regular or irregular, in any dimension, over the set I k , are treated as variables with a range. The rest of the first-level arrays are to be treated as constants, because they will compute to a fixed value at the point m k .

Experiments and Results

We have implemented our algorithm on top of an in-house optimizing compiler framework. For these experiments we ran our algorithm with the following parameters: C (constant factor in DMA-Transfer)= 15, t (cost per element, for the transfer) = 1, m E (cost for data in external memory) = 5, and m S (cost for data in SPM) = 1. These are typical values also used by other researchers [START_REF] Kandemir | A compiler-based approach for dynamically managing scratch-pad memories in embedded systems[END_REF].

We evaluated the resulting codes on an ARM (Advanced Risc Machine) Simulator. The simulator contains an ARM processor with a 4KB on-chip scratch-pad and a 4KB twoway associative data-cache. A DMA is available to transfer data between SPM and external memory. All components have an incorporated timing and power models. We present performance results on four realistic applications kernels, with relatively large code and many data arrays: (also known as Dolby-Digital) [START_REF] Absar | Development of ac-3 digital audio encoder[END_REF]. The bit-allocation part has several two level array-indexing. For each application, Fig. 4 has a group of three columns. The first col. shows the execution time for the original program. No SPM mapping (Non-Opt) was done but the arrays were accessed through the cache. The second col. shows the execution-time when all the arrays with only regular access (directly-indexed) were mapped to the SPM, in the best possible way (Opt-Reg). Arrays not mapped to the SPM were put in the cacheable-section of the external memory. The third col. shows the execution time when both regularly and irregularly accessed arrays were allowed to be mapped to the SPM, using our technique (Opt-Irreg). Fig. 5, similarly, shows the energy values. Clearly, banishing large, indirectly-indexed, arrays from the SPM can result in significant penalties.

Conclusion

Arrays indexed through both iterators and other arrays, occur commonly in many programs. In this paper, we showed, using several examples, that the access pattern of many indirectly-indexed arrays can be quite well analyzed at compile-time for spatial and temporal locality. The analysis was used to efficiently map such arrays to the SPM. We see our main contribution as extending the current framework, and providing an unambigious compiler-based technique for handling irregular arrays access.

Generating Irregular and Regular Sets

For a reference X = S X + R X I + o X , in a loop-nest with iterators I = {i 1 , i 2 , • • • , i n }, we define some operators:

Operator θ 1 , when applied to a m×n matrix, R X , returns a m×1 column vector θ 1 (R X ) = [d 1 d 2 . . . d m ] T , such that:

d p = {i k | i k ∈ I ∧ r p,k = 0 ∧ r p,k ∈ R X } Therefore, each component of θ 1 (R X
) is a subset of I. For a vector a = [a 1 a 2 . . . a m ] T , where each element a i is a subset of I, we define a = ∪ k a k . That is, a forms a set union of all the iterators present in a. θ 2 ( S X ) = θ 2       q U 1,q U 1,q q U 2,q U 2,q . . .

  

   =    q Θ U 1,q q Θ U 2,q . . .

  

Finally: Θ( X ) = θ 2 ( S X ) ∪ θ 1 (R X ). The reference X , of m-dimensional array X, is with respect to its p th dimension:

• Regular over the set of iterators in p th row of θ 1 (R X ).

• Irregular over the set of iterators in the p th row of the columnvector θ 2 ( S X ). • Independent over the iterators which do not appear in the above two.

Fig. 1 .

 1 Fig. 1. Migrating the relevant section of an, indirectlyindexed, image-data onto SPM.

  for( i = 0 ; i < N ; i++) for( j = 0; j < M ; j++ ) { spm_image[0:15][0:15] <image[ 16*i + x[i][j] + (0:15)] [ 16*j + y[i][j] + (0:15)]; for( k = 0 ; k < 16 ; k++ )

Fig. 2 .

 2 Fig. 2. Examples of compile-time discernible spatial and temporal reuse in indirectly-indexed arrays.

  In the reference B [C[k][k + 1] + D[j]], the arrays C and D are directly-indexed, while array B is indirectly-indexed. In the current literature [7], a directly-indexed array such as C[k][k+ 1], is represented as:

  Suppose the iterator i k assumes the values 1, 2 • • • , I k . An array X referenced inside the body of such a loop-nest will be accessed I 1 × I 2 × . . . × I n times. We have two scenarios:• Array X not mapped to SPM: In this case, the access is always directly to the external-memory. If m E is the cost per access for a word in the external memory, thenT otal Cost = I 1 × I 2 × • • • × I n × m E . • Array Xmapped to SPM: In this case, T otal Cost = T ransf er Cost + Access Cost. T ransf er Cost is the cost of all the transfers of X to the SPM. Access Cost is the cost of all the access to X on the SPM. T ransf er Cost: Suppose the transfers to SPM, of the relevant portion of array X, is done at loop-level k, i.e. inner to loop-nest [i 1 , i 2 , • • • , i k ] but outer to the loop-nest [i k+1 , i k+2 , • • • , i n ]. Therefore, there will be in total I 1 × I 2 ו • •×I k number of transfers. We model each of those transfers as composed of N number of sub-transfers. For each sub-transfer, the DMA is programmed to move Q contiguous elements to the SPM from the external memory. A DMA-transfer incurs a fixed startup cost, C, and a cost that is proportional to number of elements, , that are transfered [8], i.e. DM A transf er cost = C + t. Therefore, each sub-transfer has a cost C + Qt. And so, T ransf er Cost = (C + Qt) × N × I 1 × I 2 × • • • × I k . Access Cost: Let m S be the cost per access for a word in the SPM. Thus: Access Cost = I 1 ×I 2 ו • •×I n ×m S .

Fig. 3 .

 3 Fig. 3. Trade-off between number of transfers and the size of each transfer. of times the program comes to migration-point m 4 . That is, 50 × 50 × 80 = 200000 times. The T otal Cost at m 4 is: T otal Cost = (C + 5t) × 200000 T ransf er Cost

Fig. 4 . 2 .Fig. 5 .

 425 Fig. 4. Total execution-time for-1. Non-Opt, 2. Opt-Reg, 3. Opt-Irreg.

Algorithm 1

 1 Scratch-Pad Mapping Technique. function Find conf ig opt for a given permutation σ for k = n . . . 1 do for p = 1 . . . m do if I k ∩ β p = φ then range[p] ← (0 . . . D p -1) else if I k ∩ α p = φ then range[p] ← compute range based on iteratorvariables I k ∩ α p in E p , treating rest as con-

	stants
	else
	range[p] ← (0 . . . 0)
	end if
	end if
	end for
	s ← size(range), c ← transf er cost(range)
	conf ig k ← range, k, c
	end for
	conf ig opt ← conf ig k with the minimum cost
	end function

This work was partly funded by STMicroelectronics, Asia Pacific Pte Ltd, under PhD. Fellowship Program.

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

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


Romain Aubry
email: romain@cimne.upc.edu

Eugenio Oñate
email: onate@cimne.upc.edu

Rodolfo -Sergio
email: sergio@ceride.gov.ar

Idelsohn

Del Pin
email: fdelpin@cimne.upc.edu

Particle finite element method applied to mould filling

ABSTRACT. The Particle Finite Element Method (PFEM) is applied to the solution of three dimensional casting processes with solidification problems for a viscous incompressible fluid. One of the most salient features of the method is to treat the classical Navier-Stokes equations in a fully non-linear Lagrangian description, including the large deformations of the fluid during the filling process. The stabilisation of the convective term is then completely bypassed. A modified fractional step is presented to ensure mass conservation. A fully thermally coupled flow and the solidification strategy are also introduced.

RÉSUMÉ. La méthode des éléments finis particulaires (PFEM) est utilisée pour la résolution des procédés de mise en forme modélisés par des fluides visqueux incompressibles. L'utilisation de la formulation Lagrangienne appliquée aux équations de Navier-Stokes permet d'éviter la classique difficulté numérique due au terme convectif inclus dans la dérivée temporale totale. Un schéma de pas fractionnaire modifié est présenté pour assurer la conservation de la masse. Le couplage thermique au travers de l'approximation de Boussinesq et le processus de solidification sont également présentés. KEYWORDS: Lagrangian description, free surface problem, incompressibility, solidification, mass conservation. MOTS-CLÉS : Description Lagrangienne, surface libre, incompressibilité, solidification, conservation de la masse.

Introduction

In casting processes, one of the biggest difficulties to be solved is created by the appearance of the free surface during the mould filling process, which has to be located. Various methods have already been studied with fixed grid like VOF, level set and pseudo-concentration. They all use a hyperbolic-like transport equation to solve the movement of the free surface as well as the Navier-Stokes equations. Various strategies have also been presented to track and smooth the free surface. Here, we take the choice to follow the free surface during its motion by following the movement of the particles in a Lagrangian manner, which implicitly gives the position and the evolution of the free surface. Furthermore, using the Lagrangian description allows to use total temporal derivatives and to circumvent the wellknown difficulty of the stabilization of the convective term. However, due to the large motion of the fluid, which only produces deviatoric stresses through deformation rates, a complete remeshing has to be performed at each time step. Furthermore, the non linearity of the convective term is now present in all the spatial derivatives of the Navier-Stokes equation.

The Particle Finite Element Method (PFEM) [START_REF] Idelsohn | The Particle Finite Element Method: a powerful tool to solve incompressible flows with free-surfaces and breaking waves[END_REF], Oñate et al., 2004) is a powerful method to solve free surfaces problems and is extended here to discontinuous pressure approximations and solidifications problems.

Numerical model of the fluid equations

The Navier-Stokes equations in a Lagrangien framework

We recall quickly the Lagrangian equations of motion for a Newtonian incompressible fluid flow and we refer to (Aubry et al., 2004) for a complete presentation. The momentum conservation reads:

) ( 2 ) ( 0 T X T X DF div F div V - - + - = J Jp dt d µ ρ [1] ) (x grad F X = [2] F det = J [3]
where F is the transformation gradient, J is the Jacobian of the transformation, D the symmetric part of the strain rate, p the pressure, 0 ρ the density and µ the dynamic viscosity of the fluid. Incompressibility is expressed through the mass conservation as:

1 = J or [4] 0 ) ( = -1 X F : V grad
We will see that this equation is particularly important for our application. Furthermore, as F is a function of x we see that the right hand side of [4] is highly non-linear respect to the displacement, which is the main unknown in a Lagrangian approach. Equations [1] and [4] must be completed with appropriate boundary and initial conditions.

Space discretization

Applying the finite element Galerkin method to equations [1] and [4], we obtain:

F P U B V U K V M = + + ) ( ) ( dt d [5] 0 ) ( = V U B
where V and U are the velocity and displacement vectors, and the matrix follow the classical notations for the finite element solution of the Navier-Stokes equations. Once more the non linear dependence of the displacement of all the matrices has been emphasized. Furthermore, it should be noted that the incompressibility condition [4] has been changed for: 0 ) ( = -V div x [START_REF] Bibliographie Aubry | Particle finite element method in fluid mechanics including thermal convection-diffusion[END_REF] which is the time derivative of [4]. Evidently, [4] and [START_REF] Bibliographie Aubry | Particle finite element method in fluid mechanics including thermal convection-diffusion[END_REF] are equivalent at the continuum level. We will see that the time integration of [START_REF] Bibliographie Aubry | Particle finite element method in fluid mechanics including thermal convection-diffusion[END_REF] will play a major role in the mass conservation.

Fractional step, preconditioned Uzawa method and mixed elements

The time discretization is performed with a θ -scheme and through a classical fractional step, designed at the algebraic level following [START_REF] Codina | Pressure Stability in Fractional Step Finite Element Methods for Incompressible Flows[END_REF]. After the introduction of an auxiliary velocity variable and a few algebraic manipulations, the scheme reads:

θ n n θ n θ n θ n n 1 n F P U G V U K V V M + + + + + = + + - ) ( ) ( ) ( γ dt 1 n θ n n 1 n θ n 1 V U D P P U G DM + + + + - = - ) ( ) )( ( γ dt 0 P P U G V V M n 1 n θ n 1 n 1 n = - + - + + + + ) )( ( ) ( γ dt
where is the time increment and dt γ is a numerical parameter varying from 0 to 1. As noted in [START_REF] Codina | Pressure Stability in Fractional Step Finite Element Methods for Incompressible Flows[END_REF], the two pairs of interesting values for ( γ ,θ ) are (0,1) which is first order in time, and (1,1/2), which is second order in time. At this point, a classical approximation is usually made:

L G DM 1 ≈ - [7]
where L is the Laplace operator for continuous pressure. Writing the previous fractional step in terms of V n+1 , a natural stabilization term of the form dt(DM -1 G-L)(P n+1 -γP n ) then appears. This term is efficient only for first order schemes and other strategies have to be designed for second order in time and equal order interpolation (Codina, Idelsohn et al., Oñate et al.). Furthermore, this induces a wrong boundary condition for the pressure and produces a non-discrete divergence free end-of-step velocity.

Instead of using the precedent approximation, we replace the velocity mass matrix in by its lumped mass matrix version in the fractional step so that the same boundary conditions as the monolithic approach are applied, and an exactly discrete divergence-free solution is obtained by also replacing the consistent velocity mass matrix by its lumped counterpart in the projection step of the fractional step. Furthermore, discontinuous approximations of the pressure are now available as well as a second order in time for a mixed finite element satisfying the inf-sup condition.

G DM 1 -

Mass conservation

A classical difficulty of free surface problems is the conservation of mass during the computation. Incompressibility is enforced only weakly through the pressure acting as the Lagrangian multiplier of this condition. A valuable property of discontinuous pressure elements is the enforcement of mass conservation at the element level. In solid mechanics with incompressible media, condition [4] is usually weakly enforced and linearized through a Newton-like method. In fluid mechanics, equation [START_REF] Bibliographie Aubry | Particle finite element method in fluid mechanics including thermal convection-diffusion[END_REF] is usually preferred due to its Eulerian form. So we see that for a Lagrangian fluid, mass conservation will depend crucially of two factors, namely a good approximation of the incompressibility and a good integration of the velocity in time, which is confirmed through numerical results. We therefore use a second order fractional step with a P1++/P1 element with discontinuous linear pressure satisfying the inf-sup condition. With the discontinuous pressure, a better mass conservation is obtained, but more than else allows using a second order scheme which provides a much better integration of condition [START_REF] Bibliographie Aubry | Particle finite element method in fluid mechanics including thermal convection-diffusion[END_REF].

The thermal problem

The energy conservation

In a Lagrangian description, the energy conservation and its weak form read:

)

) ( ( 0 T J dt dT C X T 1 X grad F F div - - = κ ρ [8] 0 ) ( ) ( = + - + + + θ θ n n n dt T U K T T M θ n T T [9]
where C is the heat capacity and κ the conductivity of the media considered. The non linearity is also reflected in the spatial operators of the right hand side.

Thermo-mechanical coupling

The equations of motion of the fluid are coupled with the heat equation through the Boussinesq approximation by introducing a dependence on the density of the temperature in the gravity forces. On the other side, the temperature is implicitly coupled with the displacement as the spatial operators related to the temperature equation are function of the displacement. The system is then fully coupled.

Solidification

We introduce solidification effects through the latent heat release and the solid fraction function. The mushy zone is modelled as a variable viscosity zone until the solid fraction of the zone becomes 1.

Meshing and boundary recognition

Remeshing

As previously mentioned, the large deformations of the fluid produce severe distortion in the mesh so that a remeshing is performed every time step. This remeshing, due to its frequency must be fast and robust, particularly in a threedimensional context. There we have chosen to use the revisited Delaunay based mesh generator, as described in [START_REF] Frey | applications aux elements finis[END_REF]. It allows eliminating slivers during the generation process. Furthermore, as the Delaunay kernel connects points, the cloud of nodes of the last time step could be used to create the new mesh, which minimizes the interpolation error.

Boundary recognition

The α -shape method (Edelsbrünner et al, 1994) is used to determine the free surface, whereas the solid surfaces are explicitly known. Mainly, the α -shape method tries to reconstruct the shape of a cloud of points by relying on a distance argument. In practice, it determines if a given tetrahedral must be taken as a fluid element if its radio is not larger than a local value corresponding to a given size map. The α -shape can be used in a constrained isotropic context, and tests are currently being performed in an anisotropic context.

Conclusions

An efficient and robust solution is presented for the incompressible Navier-Stokes equations coupled with thermal effects and solidification. The Lagrangian description provides a natural framework to treat free surface problems appearing in casting processes. The modified fractional step allows uncoupling the velocity and the pressure computation, the use of discontinuous pressure elements and second order time discretization. This appears to be of utmost importance in the mass conservation process in a moving grid strategy.

Nom de la revue. Volume X -n° X/2001


Stergios Stergiou

Federico Angiolini

Salvatore Carta

Luigi Raffo

Davide Bertozzi

Giovanni De Micheli

xpipes Lite: A Synthesis Oriented Design Library For Networks on Chips

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Increasing transistor density and system interconnect scalability limitations necessitate the introduction of Networks On Chip (NoCs) as a viable, scalable packet-switched micro-network interconnect scheme, alternative to bus architectures. Many NoC architectures have recently been proposed [START_REF] Rijpkema | Trade-offs in the design of a router with both guaranteed and best-effort services for networks on chip[END_REF][START_REF] Karim | On-chip communication architecture for OC-768 network processors[END_REF][START_REF] Saastamoinen | Interconnect IP node for future system-on-chip designs[END_REF][START_REF] Dall | ×pipes: a Latency Insensitive Parameterized Network-on-chip Architecture For Multi-Processor SoCs[END_REF]. A NoC is depicted in Figure 1.

Topology selection is an integral part of a NoC design flow. Regular (such as mesh or fat tree) topologies have been adopted for interconnecting homogeneous cores [START_REF] Dally | VLSI Architecture: Past, Present and Future[END_REF][START_REF] Kumar | A network on chip architecture and design methodology[END_REF][START_REF] Guerrier | A generic architecture for on-chip packet switched interconnections[END_REF][START_REF] Liang | aSOC: A Scalable, Single-Chip communications Architecture[END_REF] in the first generation of NoC approaches. For a heterogeneous system however, such as [START_REF] Yamauchi | A 0.8 W HDTV video processor with simultaneous decoding of two MPEG2 MP@HL streams and capable of 30 frames/s reverse playback[END_REF], a regular topology selection may lead to overdesigning and is therefore not favorable in most current NoCs [START_REF] Murali | Bandwidth Constrained Mapping of Cores onto NoC Architectures[END_REF]. For this reason, several researchers are currently focusing their efforts on developing complete application-specific NoC synthesis flows, where topology and network bulding blocks are customized at instantiation time [START_REF] Murali | SUNMAP: A Tool for Automatic Topology Selection and Generation for NoCs[END_REF][START_REF] Saastamoinen | Interconnect IP node for future system-on-chip designs[END_REF].

The performance advantage of application-specific NoCs has been convincingly demonstrated at the architectural level [START_REF] Murali | SUNMAP: A Tool for Automatic Topology Selection and Generation for NoCs[END_REF][START_REF] Pinto | Efficient Synthesis of Networks On Chip[END_REF][START_REF] Ho | A Methodology for Designing Efficient On-Chip Interconnects on Well-Behaved Communication Patterns[END_REF]. It is a well-known fact, however, that instantiation-time flexibility through automatic synthesis has a price in terms of silicon efficiency [START_REF] Chinnery | Closing the Gap Between ASIC & Custom: Tools and Techniques for High-Performance ASIC Design[END_REF]. Hence, a key issue for NoC synthesis approaches is to demonstrate that the architectural headroom of synthesized NoCs with respect to less flexible, homogeneous NoCs is maintained throughout the logic and physical synthesis steps.

Our work addresses precisely this issue. It details a complete NoC design flow based on ×pipes Lite, a new, synthesis-oriented flow for the ×pipes library. This new version maintains most of the architectural advantages of the original proposed library [START_REF] Dall | ×pipes: a Latency Insensitive Parameterized Network-on-chip Architecture For Multi-Processor SoCs[END_REF], such as latency insensitive design, packet-switched communication with source routing and wormhole flow-control, and interface support for error control. However, ×pipes Lite was re-designed from scratch to be low-latency and synthesis-friendly. The contribution of this work is two-fold: first, it discusses architectural optimizations and specification tuning steps that have been developed to achieve high synthesis efficiency; second, it provides extensive post-synthesis implementation analysis to bound the design space that can be spanned by our flexible building blocks.

The outline of this work is as follows: Section 2 surveys related work. Section 3 analyzes the ×pipes Lite architecture and introduces the proposed design flow. Section 4 provides a comparison between the proposed and the original ×pipes architecture. Section 5 provides an insight on the issues addressed by utilizing SystemC as a synthesis frontend language. Section 6 details the synthesis experimental results. Section 7 concludes the paper.

Related Work

The most advanced SoC communication architectures used in industry today represent evolutionary solutions with respect to shared busses. For instance, the Sonics MicroNetwork [START_REF] Wingard | MicroNetwork-Based Integration for SoCs[END_REF] is a TDMA-based bus which can easily adapt to the data-word width, burst attributes, interrupt schemes and other critical parameters of the integrated cores, while providing very high bandwidth utilization. Another example is the STBus interconnect [START_REF] Strano | OCP STBUS Plug-in Methodology[END_REF], a high-performance communi- Early works in [START_REF] Benini | Networks on Chips: A New SoC Paradigm[END_REF][START_REF] Dally | Route Packets, not Wires: On-Chip Interconnection Networks[END_REF] pointed out the need for more scalable architectures for on-chip communication, and therefore to progressively replace shared busses with on-chip networks. Many NoC architectures have been proposed in the literature, but in most cases the design methodologies and tools are still in the early stage.

Most early NoC proposals are packet switched and exhibit regular structure. The NOSTRUM network [START_REF] Kumar | A network on chip architecture and design methodology[END_REF] adopts a mesh based approach. The Scalable Programmable Integrated Network (SPIN) [START_REF] Guerrier | A generic architecture for on-chip packet switched interconnections[END_REF] is another regular, fat-tree-based network architecture. The Linkoeping SoCBUS [START_REF] Wiklund | SoCBUS: switched network on chip for hard real time embedded systems[END_REF] is a two-dimensional mesh network which uses a packet connected circuit to set up routes through the network. In [START_REF] Karim | On-chip communication architecture for OC-768 network processors[END_REF] the use of the octagon communication topology for network processors is presented. Moreover, the implementation of a star-connected on-chip network supporting plesiochronous communication among system components is described in [START_REF] Lee | An 800MHz Star-Connected On-Chip Network for Application to Systems on a Chip[END_REF]. These NoCs provide scalable network fabrics for homogeneous system (e.g. symmetric chip-multiprocessors), but they do not allow arbitrary heterogeneous topology instantiation.

Significant steps in the direction of instantiation-time flexibility have been taken in the Aethereal NoC design framework, presented in [START_REF] Rijpkema | Trade-offs in the design of a router with both guaranteed and best-effort services for networks on chip[END_REF], which aims at providing a complete infrastructure for developing heterogeneous NoCs with end-to-end quality of service guarantees. The network supports guaranteed throughput (GT) for real time applications and best effort (BE) traffic for timing unconstrained applications. Aethereal's NI is highly configurable (it supports several session-layer standards, a variable number of ports, etc.), but the switch architecture is quite rigid. Furthermore, from the implementation viewpoint, both the NI and the switch make use of custom hard-macro FIFO buffers. These structures are not synthesizeable and they must be manually re-tuned when migrating to new technologies.

Support for heterogeneous architectures requires highly configurable network building blocks, customizable at instantiation time for a specific application domain. For instance, the Proteo NoC [START_REF] Saastamoinen | Interconnect IP node for future system-on-chip designs[END_REF] consists of a small library of predefined, parameterized components that allow the implementation of a large range of different topologies, protocols and configurations. ×pipes NoCs [START_REF] Dall | ×pipes: a Latency Insensitive Parameterized Network-on-chip Architecture For Multi-Processor SoCs[END_REF] push this approach to the limit, by instantiating an application specific NoC from a library of synthesizeable soft macros (Network Interface -NI, switch and link). The components are highly parameterizable and provide reliable and latency insensitive operation. The main drawbacks with the first ×pipes architecture are the high complexity of its basic building blocks, and the lack of a complete synthesis path to silicon implementation (NoC cost is only estimated using high level models [START_REF] Wang | Orion: A Power-Performance Simulator for Interconnection Networks[END_REF]). Both issues are fully addressed in this work.

×pipes Lite Architecture and Synthesis Flow

×pipes Lite is a SystemC library of highly parameterizable, synthesizeable NoC Network Interface, switch and link modules, optimized for low-latency and highfrequency operation. Communication is packet switched, with source routing (based upon street-sign encoding) and wormhole flow control.

×pipes utilizes OCP 2.0 [START_REF]Open Core Protocol[END_REF] as a means to interface with the SoC cores. Adhering to OCP's master/slave semantics, two NI interfaces are implemented for a peer-to-peer communication between two cores. Network communication is transparent to the application. Transferred packets are fragmented into units of fixed size, called flits.

NI Architecture

The ×pipes NI is designed as a bridge between an OCP interface and the NoC switching fabric. Its purposes are the synchronization between OCP and ×pipes timings, the packeting of OCP transactions into ×pipes flits and vice versa, the computation of routing information, and the buffering of flits to improve performance.

The ×pipes NI is designed to comply with version 2.0 of the OCP specifications. In addition to the core OCP signals, support includes for example the ability to perform both non-posted or posted writes (i.e. writes with or without response) and various types of burst transactions, including reads with single request and multiple responses. This allows for thorough exploration of bandwidth/latency tradeoffs in the design of a system.

To provide complete deployment flexibility, the NI is parameterizable in both the width of OCP fields and of ×pipes flits. Depending on the ratio between these parameters, a variable amount of flits is needed to encode an OCP transaction. For any given transaction, some fields (such as the OCP MAddr wires, specific control signals, routing information) can be transmitted just once; in contrast, other fields (such as the OCP MData or SData wires) need to be transmitted repeatedly, for example during a burst transaction. Thus, the NI is built around two registers; one holds the transaction header, while the second one holds the transaction payload. The first register samples OCP signals once per transaction, while the second is refreshed on every burst beat.

A set of flits encodes the header register; subsequently, multiple sets of flits are sent towards the fabric, each encoding a snapshot of the payload register subsequent to a new burst beat. Sets of payload flits are pushed out until transaction completion. Header and payload content is never allowed to mix in the same flit, thus simplifying the required logic. Routing information is attached to the header flit of a packet by checking the transaction address against a Look-Up Table (

LUT).

As shown in Figure 3, two NIs are implemented in ×pipes, named "initiator" (attached to system masters) and "target" (attached to system slaves). A master-slave device will need two NIs, an initiator and a target, for operation. Each NI is additionally split in two submodules, one for the request and one for the response channel. These submodules are loosely coupled: whenever a transaction requiring a response is processed by the request channel, the response channel is notified; whenever the response is received, the request channel is unblocked. The mechanism is currently supporting only one outstanding non-posted transaction, but can be extended should any attached core need this feature.

The ×pipes interface of the NI is bidirectional; for example, the initiator NI has an output port for the request channel and one input port for the response channel (the target NI is dual). The output stage of the NI is identical to that of the ×pipes switches, for increased performance. The input stage is implemented as a simple dual-flit buffer with minimal area occupation, but still makes use of the same flow control used by the switches.

Switch Architecture

The ×pipes switch models the basic building block of the NoC switching fabric. It implements a 2-cycle-latency, output-queued router that supports fixed and round robin priority arbitration on the input lines, and a flow control protocol with ACK/nACK, Go-Back-N semantics.

Allocation of inputs towards specific output lines is handled at the Allocator module. Multiple Allocators exist in a switch, each driving one of its output ports (O i ).

Assuming that one input is currently owning access to O i , it is maintained in its state until a tail flit arrives. Arbitration is subsequently performed upon receipt of a header flit

Out [0] Allocator [0]
Allocator [START_REF] Benini | Networks on Chips: A New SoC Paradigm[END_REF] Allocator [START_REF] Guerrier | A generic architecture for on-chip packet switched interconnections[END_REF] Flow Control In [START_REF] Benini | Networks on Chips: A New SoC Paradigm[END_REF] In [START_REF] Guerrier | A generic architecture for on-chip packet switched interconnections[END_REF] In [START_REF] Kumar | A network on chip architecture and design methodology[END_REF] In An input flit can be rejected, and therefore nACKed, due to one or more of the following reasons:

[0] Out [1] Out [2] Out [0]
• The output line is occupied by a previous transmitting packet. • The buffering space for output O i is already filled.

• Another header flit requesting the same output is concurrently appearing on another input port, and arbitration is won by the latter. If a flit A is dropped, then all subsequent incoming flits are dropped as well, until flit A reappears at the input, adhering to a Go-Back-N flow control mechanism.

After a packet has won the arbitration, its header flit is properly adjusted in order to prepare for the next switch along the routed path to the slave. More specifically, routing information pertaining the current switch is rotated away; this allows positioning of the per-hop routing bits at a fixed offset within the flits.

The switch is parameterizable in the number of its inputs and outputs, its arbitration policy (fixed priority or roundrobin,) as well as in the size of the buffering at the outputs. A 4x3 instantiation is depicted in Figure 4.

Link Architecture

A solution to overcome the interconnect-delay problem consists of pipelining links. The link data introduction rate is decoupled from link delay by trading it with latency. The NoC NI and Switch modules are designed in such a way that their behavior does not depend on the latency of the communication channels (latency insensitive operation) [START_REF] Carloni | Theory of Latency-Insensitive Design[END_REF]. Pipelining has been used both for data and control lines.

Design Flow

The design flow is shown in Figure 2. The ×pipes compiler instantiates the desired NoC by means of configuration scripts that are either automatically generated in a previous step, or manually specified [START_REF] Murali | SUNMAP: A Tool for Automatic Topology Selection and Generation for NoCs[END_REF].

Configuration scripts detail general, core (NI), switch, and link specific parameters. General parameters comprise flit size, and core address space. Core (NI) parameters include type (master/slave/both), address on the NoC and the switch connection endpoint. Switch parameters include the number of inputs and outputs, along with the output buffering capacity. Finally, link parameters comprise the switch endpoints that they connect to, along with the number of their pipeline stages.

×pipes Lite Design Revision

The original ×pipes design is essentially a full-featured NoC specification, addressing all aspects of a NoC design flow, including error control at the switch level, with parameterization pushed to the extreme. ×pipes Lite has instead been designed from the ground up to be a library of fully synthesizeable, low-latency, high-frequency NoC modules. In this context, architectural changes have been performed onto the original ×pipes library [START_REF] Dall | ×pipes: a Latency Insensitive Parameterized Network-on-chip Architecture For Multi-Processor SoCs[END_REF].

One key observation driving the development of ×pipes Lite is that NoCs typically provide abundant and scalable bandwidth, but they lack in providing low-latency services. In order to address this limitation, one of the most noticeable differences between ×pipes Lite and the first version of ×pipes is the dramatic reduction in pipeline depth, with no compromises on the frequency target. Switches, for example, now incur in a latency of just two cycles, against seven in the previous design. Network interfaces underwent a similar redesign, with four fewer pipeline stages in output channels and one less in input channels. This significant improvement was achieved by removing the logic related to virtual channel management and to error detection, even though the switch protocol still supports retransmissions. A side benefit of the shortening of ×pipes pipelines is greatly reduced buffering requirements, which drastically reduces synthesized area and increases achievable frequency.

Additional area savings, again compounded with latency improvements, were achieved by slightly constraining the ×pipes packet format. In contrast with the original specification, which aimed at maximum packing of information within the flits, a format with fixed field offsets and an immediate forwarding policy was chosen as more effective area-and latency-wise. Unnecessary bloat of synthesized hardware was also avoided by assuming routing information to fit in the first flit of a packet, by enforcing a fixed worst-case width, and by preventing header and payload content to mix within the same flit.

From the point of view of the core interface, OCP support was updated from version 1.0 to 2.0 of the specifica- tions, significantly improving the support for burst transactions in the process. Single request, multiple responses burst reads are now possible, and write commands can be either with or without response, trading speed for reliability.

Synthesis and Simulation Back-ends

While the original ×pipes library was mostly targeted to functional simulation, the structure and design choices of the ×pipes Lite NoC modules were heavily influenced by the target goals of high-speed, low-latency soft core synthesizeability. Still, simulation functionality was kept as a design objective, with the issue of instantiation-time parameterizability in the foreground. For this reason, we chose to keep a single codebase for the ×pipes Lite library, conditionally adding simulation-or synthesis-specific code when appropriate.

One of the main issues in keeping the simulation and synthesis flows consistent was the need for different configurations of individual instances of the same module. For example, two switches with different numbers of I/O ports or amounts of buffering may coexist in a ×pipes Lite design. While such configuration is easily achieved in a simulation environment, simply by building a generic SystemC class and by passing appropriate parameters to the constructor of every instance at runtime, the issue is more serious if the module needs to be synthesized, because synthesis tools require static code. Our approach was to use a single configurable class for simulation, and adding preprocessor directives when needed to automatically but statically differentiate every instance to be synthesized. For example, the single class switch() used for simulation would be renamed class switch 4 4() and class switch 7 2(), and then appropriately configured, when synthesizing a 4x4 and a 7x2 switch simultaneously.

For increased flexibility, switch I/O ports are instantiated differently during simulation. Code like IN = new sc in<sc bv<FLIT WIDTH> > [SWITCH INPUTS] is utilized, while synthesis resorts to static definitions and multiple class naming. In a dual manner, signal widths which are defined by means of templates in SystemC, can be accurately tuned for synthesis (e.g. sc bv<LOG INPUTS> mux sel), and are set to upper limit values for simulation.

Various non synthesizeable syntactical alternatives were adopted for simulation, in order to improve performance. For example, missing synthesis support for range selection (sc uint<>.range(a, b)) on non-constant a, b led to a code fork, where simulation used the above syntax, while synthesis resorted to a bit-by-bit assignment.

One more complex issue arose with synthesis of NI routing LUTs. Our choice was to integrate the LUT generation and the related code changes within the ×pipes compiler tool. This tool, leveraging on the codebase hooks described above and on its own topology view, generates the customized code base for both simulation and synthesis along with the suitable Design Compiler synthesis scripts, as specified on the provided input script file.

Experimental Results

The feasibility of automatic generation of NoC topologies from parameterizable SystemC source code was thoroughly verified by performing extensive synthesis experiments in 0.13µm technology with Synopsys Design Compiler for all modules. Results were obtained for worst case commercial conditions under an average switching pattern for power.

Configuration parameters for the NIs comprise the flit width and the size of the output buffers. For a variety of NI configurations, total cell power and area results are depicted in Tables 1 and2. A frequency of 1 GHz was achieved for all variations, and is therefore not reported in the tables.

Switches are also parameterizable in terms of flit width and size of the output buffers. In order to study the effect of the number of input and output ports, three switch instances were analyzed, namely 4x4, 4x6 and 6x4. The resulting area and frequency results are depicted in Table 3; a frequency of 1 GHz was achieved for all the 4x4 switch variations. Total cell power results are reported in Table 4.

An exploration of the area/frequency tradeoff was performed on 32-bit 5x5 switches. By varying the target synthesis clock, different area results were reported (see Figure 6). The maximum operating frequency achieved for the 5x5 switch module was 925 MHz. As expected, area re- quirements are almost constant until a certain frequency (800 MHz in this case), after which synthesis efforts to achieve higher operating frequencies result in a steep area increase.

An example illustrating the importance of the estimation of the area and clock frequency of a NoC can be shown by referring to Figure 6 and Figure 5. The diagram in Figure 5 features two alternative topologies for the same system, comprising four processors, four privately accessible memories, and three shared slave devices. Topology (a) leverages upon a single 11x11 switch in a crossbar-like fashion, while topology (b) creates three clusters with 5x5 switches. We integrated these ×pipes topologies within a complete cycle-true simulation environment ( [START_REF] Loghi | Analyzing on-chip communication in a MPSoC environment[END_REF]), and ran an operating system-based benchmark on them, thus stressing the platforms with functional traffic. To complete a benchmark involving interprocessor communication, topology (a) required, as expected, less clock cycles, with about a 10% advantage due to lower access latency towards shared devices.

However, 11x11 ×pipes switches have a maximum working frequency of approximately 780 MHz, while 5x5 switches can reach 925 MHz (a 19% gain). Area-wise, one 11x11 switch requires 0.48 mm 2 , while three 5x5 switches (synthesized for maximum frequency) take 0.51 mm 2 overall. The net result is that the designer can choose the topology with 5x5 switches at maximum frequency, achieving 10% overall faster performance than the "crossbar" topology despite a comparable area footprint. Alternatively, the designer can clock the 5x5 switches about 10% higher than the 11x11 one (850 MHz), achieving roughly similar performance with a total area of 0.42 mm 2 , a saving of 14%. A third alternative is synthesizing 5x5 switches with a frequency constraint of 800 MHz, about the same as the 11x11 one, thus achieving about 10% lower performance but with an overall area of just 0.38 mm 2 -a 34% saving over the 11x11 solution.

Finally, we performed place&route tests on a 5x5 ×pipes switch instance. The layout analysis shows that the area reported by the synthesis tools was an underestimate by less than 10%.

Conclusion

We have presented xpipes Lite, a design flow for the generation of synthesizeable and simulateable models for application-specific Networks on Chip. Synthesis results with commercial tools prove the value and competitiveness of automatic NoC generation. Whereas higher performance can be achieved by custom layout of NoCs, xpipes Lite benefits designers by reducing their effort and allowing them to explore the design space spanned by various NoC topologies and parameters.

Figure 1 .

 1 Figure 1. NoC Architecture block diagram

Figure 2 .

 2 Figure 2. NoC synthesis flow

Figure 3 .

 3 Figure 3. ×pipes Network Interfaces

Figure 4 .

 4 Figure 4. ×pipes 4x3 Switch

Figure 5 .Figure 6 .

 56 Figure 5. Test ×pipes topologies

Table 1 . Cell power (mW) for initiator and tar- get NIs.

 1

	Flit	Output Buffer Stages
	Width (bits)	4	16	64
		Initiator NIs
	16	22.7	30.4	59.6
	32	33.5	47.7	104.8
	64	49.3	77.1	194.8
	128	87.8 144.5 379.3
		Target NIs
	16	27.5	34.8	62.6
	32	36.9	51.1	106.9
	64	55.4	82.0	194.3
	128	93.3 151.1 382.5

Table 2 . Area (mm 2 ) for initiator and target NIs.

 2

	Flit	Output Buffer Stages
	Width (bits)	4	16	64
		Initiator NIs
	16	0.025 0.037 0.093
	32	0.036 0.061 0.179
	64	0.051 0.111 0.361
	128	0.092 0.186 0.724
		Target NIs
	16	0.035 0.053 0.110
	32	0.045 0.078 0.193
	64	0.063 0.114 0.352
	128	0.117 0.230 0.701

Table 3 . Area (mm 2 ) and timing for 4x4, 4x6, 6x4 switches.

 3

Table 4 . Cell power (mW) for 4x4, 4x6, 6x4 switches.

 4

	Flit	Output Buffer Stages
	Width (bits)	4	16
	4x4 Switches
	16	31.1	62.7
	32	55.5	116.9
	64	104.4	219.3
	128	199.1	430.5
	4x6 Switches
	16	42.8	90.1
	32	79.7	170.8
	64	148.2	334.4
	128	283.2	617.3
	6x4 Switches
	16	35.9	69.1
	32	62.9	123.2
	64	117.2	237.6
	128	223.4	453.5

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

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

Acknowledgement

This research is supported by MARCO Gigascale Systems Research Center (GSRC) and NSF, under contract CCR-0305718 and a grant by STMicroelectronics for DEIS.