Tero Rissa

Adam Donlin

Wayne Luk

Evaluation of SystemC Modelling of Reconfigurable Embedded Systems

This paper evaluates the use of pin and cycle accurate SystemC models for embedded system design exploration and early software development. The target system is Mi-croBlaze VanillaNet Platform running MicroBlaze uClinux operating system. The paper compares Register Transfer Level (RTL) Hardware Description Language (HDL) simulation speed to the simulation speed of several different SystemC models. It is shown that simulation speed of pin and cycle accurate models can go up to 150 kHz, compared to 100 Hz range of HDL simulation. Furthermore, utilising techniques that temporarily compromise cycle accuracy, effective simulation speed of up to 500 kHz can be obtained.

Introduction

Introduction of embedded processors into Field Programmable Gate Arrays (FPGAs) exposes mainstream designers to a new field of CAD: hardware and software development of application specific embedded systems. This creates a conflict between two verification worlds. Software developers are accustomed to high-speed Instruction Set Simulators (ISS) with full visibility and controllability to the system, whereas hardware engineers use Hardware Description Language (HDL) simulators. Currently the latter is the only option provided for complete system simulation, which is clearly too time consuming as illustrated later in this paper.

This paper examines the usefulness of SystemC modelling to alleviate the gap between embedded software and hardware verification methods. Previous related work include, amongst others, SystemC modelling of an IP forwarding chip [START_REF] Kogel | Virtual architecture mapping: A SystemC based methodology for architectural exploration of system-on-chip designs[END_REF], AMBA bus architecture [START_REF] Caldari | Transaction-level models for AMBA bus architecture using SystemC 2.0[END_REF], multiprocessor SoC platforms [START_REF] Wieferink | A system level processor/communication co-exploration methodology for multi-processor system-on-chip platforms[END_REF], and virtual in-circuit emulation [START_REF] Benini | Virtual in-circuit emulation for timing accurate system prototyping[END_REF]. This paper presents several different SystemC models of a complex embedded system executing uClinux operating system. It is shown that there can be 8-fold differ-ence in the simulation time depending on the used SystemC model.

The rest of the paper is organised as follows. Section 2 introduces the target system and the used SystemC tools. Section 3 briefly looks in to the HDL RTL simulation of the system. Sections 4 and 5 presents the cycle and noncycle accurate SystemC models and simulation speed results. Section 6 highlights some of the drawbacks and future improvement possibilities with SystemC modelling. Finally section 7 concludes the paper.

Target System

The target system is uClinux [START_REF]UClinux Embedded Linux Microcontroller Project[END_REF] running on MicroBlaze VanillaNet [START_REF]MBVanilla Net Platform V6.20a[END_REF] platform depicted in Fig. 1. Both the hardware version of the platform and the Linux port are created by John Williams [START_REF] Bergmann | A flexible platform for real-time reconfigurable systems on chip[END_REF][START_REF] Williams | Embedded linux as a platform for dynamically self-reconfiguring systems-on-chip[END_REF]. Publicly available third party platform and application was chosen to facilitate comparisons with our models. uClinux is a derivative of Linux 2.0 kernel intended for microcontrollers without Memory Management Units (MMUs). The MB VanillaNet platform is targeted to Insight/Memec V2MB1000 Virtex2 evaluation board and the range of peripherals reflects this.

All the simulations are carried out using IBM IntelliStation Z Pro with 3.06 GHz Intel Xeon processor with 2.5 GB RAM memory, running Red Hat 8 operating system with Linux 2.4.18-14 kernel. Each SystemC simulation result is an average of 50 data points: 10 different phases over 5 executions of the Linux boot sequence. From obvious reasons the RTL HDL simulation results are not from Linux boot sequence, but from a simpler program execution.

SystemC Tools

All the SystemC development tools used within this project are Free Open Source Software (FOSS). SystemC class library, including the source code is free and available to the public via SystemC portal [START_REF]Open SystemC Iniative OSCI, SystemC documentation[END_REF]. In addition to standard Linux C++ development and shell tools, GTKWave waveform viewer and Data Display Debugger (DDD) were used.

RTL HDL Simulation

The RTL HDL simulation is carried out in Mentor Graphics ModelSim SE 6.0 without any trace waveform. The used HDL model is generated by Xilinx Embedded Development Kit (EDK). As seen from Fig. 2, which contains the results from all the presented models, the HDL simulation can be run with the speed of 167 Hz. With this simulation speed, it would take 1 month and 15 days to complete uClinux boot sequence.

Pin and Cycle Accurate Models

The SystemC models presented in this section are pin and cycle accurate models of the target system components; peripherals, buses and the MicroBlaze. This means that the all the signals between the components that are present in the RTL HDL model are also present in the SystemC models. Furthermore, the waveforms of these signals in these models are identical. The difference is that pin and cycle accurate model does not model all the signals and register transfers inside the components. For example, multi cycle operation can be carried out in zero simulation time and then the result delayed for required amount of cycles. In general this means that the components' internal description can be done using standard C++, whilst SystemC is used for the component interface. Naturally, SystemC must be used also for concurrent elements to maintain the cycle accuracy within the interface. A notably large component is the Xilinx MicroBlaze ISS, which is standard C++ implementation wrapped in SystemC module.

The UART models connects to the pseudo terminal (PTY) interface on the underlying Linux operating system. By using this interface, it is possible to connect to the model using standard terminal software, such as minicom. The SystemC model of Ethernet MAC is a proxy that implements only the OPB interface and peripheral control registers.

Initial SystemC Model

In the initial SystemC model, sc [in|out] rv ports are used in all the system components and sc signal rv signals are used to connect the ports. Within modules, native C++ types are used, whenever possible. The main reason of using resolved signal and port types is to enable HDL co-simulation in ModelSim. It is well known that these data types are slower to simulate than unresolved ones. However, the simulation speed of this type of model is already 61 kHz -360 times faster than RTL HDL simulation.

Native C++ Data Types

The fist optimised model utilises native C++ data types for signals between system components. When using these data types, HDL co-simulation is no longer possible. In addition, multiple drivers of a same signal are no longer detected. The use of this optimisation is facilitated by signal declaration and manipulation macros and inline functions. These constructs makes is possible to turn the optimisation on and off during compilation time without changes to the source code of the models.

As it can be seen from Fig. 2 this optimisation provides 132% speed improvement compared to the previous model, yielding simulation speed of 141.7 kHz.

Threads vs. Methods

SC THREAD is a SystemC process that can have multicycle behaviour. When multicycle behaviour is not required, more lightweight process -SC METHOD -can be used. Methods are faster to simulate than threads due to reduced scheduling complexity. In this model, 3 out of 17 processes in total are changed from threads to methods. It can be seen that this yields modest 2% speed improvement.

Reduced Port Reading

In SystemC, ports are implemented as C++ objects. Every port operation, e.g., read and write, will inflict a chain of function calls due to request-update nature of the concurrency kernel. Listing 1 illustrates how port reading can be reduced, when port value is required several times within single process execution. The first code snippet uses the value of input X two times if the value is not 2. By utilising local variable to store the input value, only one reading of the port is required. Naturally, this technique can only be utilised, when reading of the port is not blocking operation and does not consume port item, as can be the case for example with sc fifo.

In this model, 6 input port reads occurring every cycle were reduced to 3. This yields 2.5% speed improvement. As in this model there are about 70 port read operations ev-

Listing 1. Reduced port reading / / M u l t i p l e p o r t r e a d s v o i d i n p u t m e t h o d ( ) {

i f ( i n p u t x . r e a d ( ) != 2 ) { z = i n p u t x . r e a d ( ) + i n p u t y . r e a d ( ) ; } }

/ / Reduced p o r t r e a d s v o i d i n p u t m e t h o d ( ) {

unsigned i n t l o c a l X = i n p u t x . r e a d ( ) ; i f ( l o c a l X != 2) { z = l o c a l X + i n p u t y . r e a d ( ) ; } } ery cycle, slightly depending on phase of execution, reducing port reading has potential for notable speed improvement. Especially, it can be noted that hardware description style to check of reset condition on every cycle is not the most efficient way of writing SystemC code. Instead, the variables should be initialised for example in the constructors, or global variable, not a port, used for reset detection.

Listing 2. Reduced port reading

/ / S e p a r a t e t h r e a d s f o r o p e r a t i o n s v o i d t h r e a d 1 ( ) {

w h i l e ( 1 ) { z = x+y ; w a i t ( ) ; } } v o i d t h r e a d 2 ( ) { w h i l e ( 1 ) { answer = z + 4 2 ; w a i t ( ) ; } }

/ / S e p a r a t e f u n c t i o n s f o r o p e r a t i o n s v o i d c o m b i n e d t h r e a d ( ) {

w h i l e ( 1 )

{ d o f u n c t i o n 2 ( ) ; d o f u n c t i o n 1 ( ) ; w a i t ( ) ; } } v o i d d o f u n c t i o n 1 ( ) { z = x+y ; } v o i d d o f u n c t i o n 2 ( ) {
answer = z + 4 2 ; }

Reduced Scheduling

In pin and cycle accurate modelling vast majority of Sys-temC processes, i.e., threads and methods, are scheduled every clock cycle. The models presented in this section reduces scheduling with two techniques explained in sections 4.5.1 and 4.5.2. These techniques has potential to yield speed improvement through two factors: 1) reduce the computation in SystemC scheduling engine and 2) reduce the overall computation of a process. The first factor is present in both techniques, the second one only in the latter.

Combination of Concurrent Elements

In RTL HDL description it is common practise to declare separate process for every state of processing in order to make the code more understandable and modular. In Sys-temC, although separate processes -methods or threadshave identical sensitivity, every process is scheduled sepa-rately. As SystemC is based on C++ it is natural to perform the computation in functions that are called from processes instead of performing the computation inside process directly. The difference is that the functions can be called from a single process without compromising the readability and modularity of the code. As these models are not targeted for hardware implementation, synthesisability of the function calls is not an issue, unlike in RTL HDL models.

Listing 2 demonstrates this optimisation in practice. The upper code snippet has two separate processes, in this case threads, for computation. In the lower snippet, the computation is done inside functions that are called from combined thread(). It is good to note the order of function calls. do function2() must be called before do function1() in order to achieve identical behaviour regardless of whether SystemC signals or native C++ data types were used for variables. The computation is usually rather more complicated than in this example and identifying the correct sequence of operations becomes increasingly difficult as complexity increases. This limits the applicability of the optimisation.

In this model, 3 synchronous single cycle threads are combined to a single thread. As can be seen from Fig. 2 this yields 3% speed improvement. This illustrates that the scheduling in SystemC kernel is notable part of the execution. In addition, asynchronous processes that are potentially scheduled several times within a single clock cycle, should be avoided whenever possible.

Multicycle Sleep of Processes

In some cases, processes (methods and threads) do not need to be invoked every clock cycle in order to achieve the desired functionality. For example in the target system, the underlying PTY interface of the UART model is capable of receiving characters much faster than our model is able to fill the transmission buffer. Therefore, instead of scheduling the transmission process to execute every cycle, the process can sleep for several cycles between executions. In SystemC, this can be done using wait(time, sc time unit) and next trigger(time, sc time unit) methods for threads and methods, respectively. This optimisation can be applied in relatively rare occasions and the benefit greatly depends on amount of computation done in each time the process is scheduled. In the case of UART interface module, the transmission will cause system calls, that have relatively long and host system load dependent execution times. In order to reduce system calls, and thus speed distortion of the results, this optimisation is utilised in all of the presented models.

Summary of Pin and Cycle Accurate Models

Unoptimised pin and cycle accurate SystemC model provided simulation speed of 61 kHz, which already provides around 360 times speedup compared to RTL HDL simulation. Mainly by utilising native C++ data types instead of multi-valued SystemC data types, 152.5 kHz simulation speed was obtained. The last three optimisation techniques had relatively small impact, 7.6% altogether, to the overall simulation speed. On the other hand, utilisation of these optimisations is simple and the tradeoffs are minor. Therefore, these techniques should be considered more as good modelling style guidelines than optimisation methods.

Non-Cycle Accurate Models

The models presented in this section uses optimisation techniques that does not preserve cycle accuracy. All the optimisation can be turned on and off during run time of the simulation. This makes it possible to quickly simulate section of the execution that is already known to work properly to a section that requires cycle accuracy. In general, it is possible to miss some errors in the system, when these optimisations are utilised.

Instruction Memory Activity Suppression

Vast majority of the OPB bus activity is MicroBlaze instruction fetches from SDDR RAM. In this model, the instruction fetches are suppressed by a new module called memory dispatcher. This module can directly access the memory models inside the peripherals. The benefit of providing the instructions via memory dispatcher are twofold: there are no longer arbitration conflicts between MicroBlaze data and instruction side OPB and even more importantly, it takes only one cycle to fetch the instruction instead of the minimum of three. As can be seen from Fig 2, the improvement in CPI is around 35%, whereas the execution time goes down 64% -from 1 hour 9 minutes to 24 minutes.

Clearly, this model compromises cycle accuracy in several ways. However, the operation of the memory dispatcher can be turned on and off at run-time.

Main Memory Activity Suppression

With this model, the whole main memory peripheral -SDDR RAM -is handled by the memory dispatcher. Again, the speedup is due to two factors. As in previous model, the number of cycles required for memory operation is reduced. Furthermore, as the memory peripheral is completely handled by the memory dispatcher, is no longer necessary to schedule the memory peripheral. Therefore, when the memory dispatcher is enabled, memory peripheral's attachment to the OPB can be removed.

Further Reduction of Scheduling

In the two previous models, the main speedup was due to simplification of frequently occurring peripheral transactions. In the target system, the uClinux has very small number of transaction with FLASH memory, GPIO, and Ethernet MAC peripherals. However, these peripherals' address decode unit is scheduled every clock cycle. This unnecessary scheduling and address decoding activity can be suppressed by explicitly accessing the peripheral only when the address is within the correct range.

As can be seen from Figure 2 this optimisation reduces the boot time to 12 minutes, providing additional 15% speedup. The danger of this optimisation is that it is no longer possible to detect some corner case bugs in the system, as for example peripheral taking over the bus when not allowed.

Interception of Kernel Functions

Final model utilises interception of two low level Clibrary functions. The Linux boot execution spends 52% on two functions: memset and memcpy. The former sets a memory region to a certain byte-value and the latter performs byte-wise copy of non-overlapping memory region to another.

The interception of the function is carried out by the Sys-temC MicroBlaze ISS wrapper. First, the wrapper detects jump to either function and reads function parameters from the MicroBlaze registers. Then the function is executed in native C++ on the host computer in zero simulation time. Finally, the wrapper modifies the ISS registers to have the same values than after normal function execution. In both of the cases only one instruction -the loop check branchis different compared to the normal execution.

With this optimisation, the CPI is actually lower, as illustrated by Fig 2, because of extra computation required to perform the captures. As roughly half of the instructions are executed in zero time, it is not surprising that the boot-up execution time is also halved from 12 minutes to 6 minutes. Effectively this boot time corresponds to simulation speed of 578 kHz. This optimisation is very application specific and does not only compromise cycle accuracy, but also the ISS execution statistics will be distorted.

Summary of Non-Cycle Accurate Models

The optimisation techniques yielding non-cycle accurate models provide up to 10 000 times speedup compared to RTL HDL simulation. All the techniques considered within this study can be turned on and off during the simulation. This makes it possible to quickly simulate portions of the code that are already known to function correctly and then return to cycle-accurate model for portions that require more detailed examination. However, it must be noted that although the optimisation can be turned on and off, the system will not be in exactly identical state compared to fully cycle accurate simulation. For example, interrupts will occur in different phase of the execution, resulting different program counter traces. In general, this is a problem only in most pathological cases as for example interrupts should function correctly regardless of the phase of execution.

SystemC Drawbacks and Solutions

This section outlines some of the drawbacks of SystemC modelling experienced within this project.

The major drawback for software development is that standard software development tools are debugging the software of the model, not the software running on the model. For example, the code that is being traced is SystemC source code, not the source code of uClinux. One possible solution to this problem would be to provide debugger interface, for example to GDB, from the SystemC model.

There is no linter available for SystemC. In other words, the SystemC semantics that is build on top of C++ syntax, is not checked within the compilation process. The effect of this is that illegal semantics that are syntactically correct will not produce compiler errors or warnings. In these occasions, the programs will cause a run-time error, which are usually harder to locate than compile-time errors. In addition, standard C++ compiler will produce undecipherable error messages, when the illegal use of SystemC semantics yields and syntactical error within the SystemC library.

Interaction with other software environments and native C/C++ and SystemC can be troublesome. This is due to two reasons. 1) main() function of the SystemC executable of within the SystemC kernel and thus not easily modifiable by the programmer. This implies that SystemC kernel is the top-level entity in the system and all the functionality must be executed within SystemC components. 2) There is no standard way of creating SystemC events from non-SystemC sources. Significance of this is that SystemC processes cannot be made sensitive to anything that is not implemented with SystemC channel types. For example in the case presented in the paper, it would have been useful to be able to be sensitive to the MicroBlaze ISS output variables, which are implemented in native C++.

Conclusion

Pin and cycle accurate SystemC modelling provides high-speed alternative to RTL HDL simulation of reconfigurable embedded systems. This paper demonstrated the usability and speed of SystemC model simulation by booting up uClinux on SystemC model of MicroBlaze VanillaNet platform. The speed of cycle accurate SystemC models range from 60 kHz to 150 kHz. Models that have capability of turning cycle accuracy on and off during the simulation can achieve simulation speed of up to 280 kHz. However, due to techniques used, the effective simulation speed can be up to 578 kHz. The speedup compared to RTL HDL simulation ranges from 360x to 10 000x, depending on the used SystemC model. Due to higher simulation speed, SystemC modelling facilitates early embedded software development and enables rapid and easy architectural exploration.

Figure 2 .

 2 Figure 2. Results. Bars for simulation speed (CPS/[kHz]) with values on the left and line plot for simulation time [min] with values on the right.

Target platform: MicroBlaze VanillaNet The

  availability of full set of FOSS development tools to carry out project with this magnitude indicates that the financial threshold for adaptation of SystemC form the tool cost point of view is negligible.

	32Mb SDDR RAM	4Mb SRAM 32Mb FLASH	MicroBlaze Soft Processor Core	L M B	8Kb BRAM
		32-bit CoreConnect On-Chip Pheripheral Bus (OPB)
	Console UART	Debug UART	Interrupt Controller	Timer/Counter	Ethernet MAC	General Purpose I/O
		Figure 1.

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)


Christophe Alias

FIFO Recovery by Depth-Partitioning is Complete on Data-aware Process Networks

Keywords: High-level synthesis, automatic parallelization, polyhedral model, synchronization Synthèse de circuit haut-niveau, parallélisation automatique, modèle polyédrique, synchronisation

Computing performances are bounded by power consumption. The trend is to offload greedy computations on hardware accelerators as GPU, Xeon Phi or FPGA. FPGA chips combine both flexibility of programmable chips and energy-efficiency of specialized hardware and appear as a natural solution. Hardware compilers from high-level languages (High-level synthesis, HLS) are required to exploit all the capabilities of FPGA while satisfying tight time-to-market constraints. Compiler optimizations for parallelism and data locality restructure deeply the execution order of the processes, hence the read/write patterns in communication channels. This breaks most FIFO channels, which have to be implemented with addressable buffers. Expensive hardware is required to enforce synchronizations, which often results in dramatic performance loss. In this paper, we build on our algorithm to partition the communications so that most FIFO channels can be recovered after a loop tiling, a key optimization for parallelism and data locality. We describe a class of process networks where the algorithm can recover all the FIFO channels. We point out the limitations of the algorithm outside of that class. Experimental results confirm the completeness of the algorithm on the class and reveal good performance outside of the class.

Introduction

Since the end of Dennard scaling, the performance of embedded systems is bounded by power consumption. The trend is to trade genericity (processors) for energy efficiency (hardware accelerators) by offloading critical tasks to specialized hardware. FPGA chips combine both flexibility of programmable chips and energy-efficiency of specialized hardware and appear as a natural solution. High-level synthesis (HLS) techniques are required to exploit all the capabilities of FPGA, while satisfying tight time-to-market constraints. Parallelization techniques from high-performance compilers are progressively migrating to HLS, particularly the models and algorithms from the polyhedral model [START_REF] Bondhugula | A practical automatic polyhedral parallelizer and locality optimizer[END_REF], a powerful framework to design compiler optimizations. Additional constraints must be fulfilled before plugging a compiler optimization into an HLS tool. Unlike software, the hardware size is bounded by the available silicon surface. The bigger a parallel unit is, the less it can be duplicated, thereby limiting the overall performance. Particularly, tricky program optimizations are likely to spoil the performances if the circuit is not post-optimized carefully [START_REF] Alias | Optimizing Affine Control with Semantic Factorizations[END_REF]. We believe that source-level optimizations (directly on the source program) should be avoided in HLS, and moved to middle-end level, on an intermediate representation closed to the final circuit. Process networks are such a natural and convenient intermediate representation for HLS [START_REF] Alias | Data-aware Process Networks[END_REF][START_REF] Rijpkema | Deriving process networks from nested loop algorithms[END_REF][START_REF] Turjan | Compiling nested loop programs to process networks[END_REF][START_REF] Verdoolaege | Polyhedral Process Networks[END_REF]. A sequential program is translated to a process network by partitioning computations into processes and flow dependences into channels. Then, the processes and buffers are factorized and mapped to hardware.

In this paper, we focus on the translation of the buffers to hardware. We propose an algorithm to restructure the buffers so they can be mapped to inexpensive FIFOs. Most often, a direct translation of a regular kernel -without optimization -produces to a process network with FIFO buffers [START_REF] Turjan | Classifying interprocess communication in process network representation of nested-loop programs[END_REF]. Unfortunately, data transfers optimization [START_REF] Alias | Optimizing remote accesses for offloaded kernels: Application to high-level synthesis for FPGA[END_REF] and generally loop tiling reorganizes deeply the computations, hence the read/write order in channels (communication patterns). Consequently, most channels may no longer be implemented by a FIFO. Additional circuitry is required to enforce synchronizations. This results in larger circuits and causes performance penalties [START_REF] Alias | Data-aware Process Networks[END_REF][START_REF] Zissulescu | Solving out of order communication using CAM memory: an implementation[END_REF][START_REF] Turjan | Realizations of the extended linearization model. Domain-specific processors: systems, architectures, modeling, and simulation[END_REF][START_REF] Van Haastregt | Enabling automatic pipeline utilization improvement in polyhedral process network implementations[END_REF]. This a major lock which prevents, so far, to incorporate fine-grain polyhedral loop optimizations on the middle-end of HLS tools. In this paper, we build on our algorithm presented in [START_REF] Alias | Improving communication patterns in polyhedral process networks[END_REF] to reorganize the communications between processes so that more channels can be implemented by a FIFO after a loop tiling. We make the following contributions:

We prove the completeness of our algorithm on Data-aware process networks (DPN) [START_REF] Alias | Data-aware Process Networks[END_REF]: on a DPN, our algorithm can recover all the FIFO after a loop tiling. This feature is a step towards enabling polyhedral optimizations in HLS at middle-end level.

We exhibit a counter-example which prove that our algorithm is no longer complete when the process network does not comply with the DPN process/channel partitioning scheme. Also, we discuss the criteria to be fullfilled by the kernel so all the FIFO can be recovered.

Experimental results on Polybench/C kernels confirm the completeness of the algorithm on DPN. For non-DPN process networks, we show that the algorithm can recover a significant amount of FIFO.

The remainder of this paper is structured as follows. Section 2 introduces polyhedral process network, data-aware process networks and discusses how communication patterns are impacted by loop tiling, Section 3 recalls our algorithm to reorganize channels, prove the completeness of our algorithm on DPN and points-out the limitations of our algorithm on non-DPN process networks. Section 4 presents experimental results. Finally, Section 5 concludes this paper and draws future research directions. 1

RR n°9187

Alias

Preliminaries

This section defines the notions used in the remainder of this paper. Sections 2.1 and 2.2 introduce the basics of compiler optimization in the polyhedral model and defines loop tiling. Section 2.3 defines polyhedral process networks (PPN), shows how loop tiling disables FIFO communication patterns and outlines a solution. Finally Section 2.4 presents data-aware process networks (DPN), the particular kind of PPN on which our algorithm is proven to be complete.

for i := 0 to N + 1 • load(a[0, i]); for t := 1 to T for i := 1 to N • a[t, i] := a[t -1, i -1] + a[t -1, i]+ a[t -1, i + 1]; for i := 1 to N • store(a[T, i]);

Polyhedral Model at a Glance

Translating a program to a process network requires to split the computation into processes and flow dependences into channels. The polyhedral model focuses on kernels whose computation and flow dependences can be predicted, represented and explored at compile-time. The control must be predictable: only for loops and if with conditions on loop counters are allowed. Data structures are bounded to arrays, pointers are not allowed. Also, loop bounds, conditions and array accesses must be affine functions of surrounding loop counters and structure parameters (typically the array size). This way, the computation may be represented with Presburger sets (typically approximated with convex polyhedra, hence the name). This makes possible to reason geometrically about the computation and to produce precise compiler analysis thanks to integer linear programming: flow dependence analysis [START_REF] Feautrier | Dataflow analysis of array and scalar references[END_REF], scheduling [START_REF] Bondhugula | A practical automatic polyhedral parallelizer and locality optimizer[END_REF] or code generation [START_REF] Bastoul | Efficient code generation for automatic parallelization and optimization[END_REF][START_REF] Quilleré | Generation of efficient nested loops from polyhedra[END_REF] to quote a few. Most compute-intensive kernels from linear algebra and image processing fit in this category. In some cases, kernels with dynamic control can even fit in the polyhedral model after a proper abstraction [START_REF] Alias | Multi-dimensional rankings, program termination, and complexity bounds of flowchart programs[END_REF]. Figure 1.(a) depicts a polyhedral kernel and (b) depicts the geometric representation of the computation for each assignment (• for assignment load, • for assignment compute and • for assignment store). The vector i = (i 1 , . . . , i n ) of loop counters surrounding an assignment S is called an iteration of S. The execution of S at iteration i is denoted by S, i . The set D S of iterations of S is called iteration domain of S. The original execution of the iterations of S follows the lexicographic order over D S . For instance, on the statement C: (t, i) (t , i ) iff t < t or (t = t and i < i ). The lexicographic order over Z d is naturally partitioned by depth:

Inria = 1 . . . d where (u 1 . . . u d ) k (v 1 , . . . , v d ) iff ∧ k-1 i=1 u i = v i ∧ u k < v k
. This property will be exploited by the partitioning algorithm. We now explain how producer/consumer relations are extracted from a polyhedral kernel and represented.

Dataflow Analysis On Figure 1.(b), red arrows depict several flow dependences (read after write) between executions instances. We are interested in flow dependences relating the production of a value to its consumption -not only a write followed by a read to the same location. These flow dependences are called direct dependences. Direct dependences represent the communication of values between two computations and drive communications and synchronizations in the final process network. They are crucial to build the process network. Direct dependences can be computed exactly in the polyhedral model [START_REF] Feautrier | Dataflow analysis of array and scalar references[END_REF]. The result is a relation → relating each producer P, i to one or more consumers C, j . Technically, → is a Presburger relation between vectors (P, i) and vectors (C, j) where assignments P and C are encoded as integers. For example, dependence 5 is summed up with the Presburger relation:

{(•, t -1, i) → (•, t, i), 0 < t ≤ T ∧ 0 ≤ i ≤ N }.
Presburger relations are computable and efficient libraries allow to manipulate them [START_REF] Verdoolaege | ISL: An integer set library for the polyhedral model[END_REF][START_REF] Kelly | The omega calculator and library, version 1.1. 0[END_REF]. In the remainder, direct dependence will be referred as flow dependence or dependence to simplify the presentation.

Scheduling and Loop Tiling

Compiler optimizations change the execution order to fulfill multiple goals such as increasing the parallelism degree or minimizing the communications. The new execution order is specified by a schedule. A schedule θ S maps each execution S, i to a timestamp θ S ( i) = (t 1 , . . . , t d ) ∈ Z d , the timestamps being ordered by the lexicographic order . In a way, a schedule dispatches each execution instance S, i into a new loop nest, θ S ( i) = (t 1 , . . . , t d ) being the new iteration vector of S, i . A schedule θ induces a new execution order ≺ θ such that S, i ≺ θ T, j iff θ S ( i) θ T ( j). Also, S, i θ T, j means that either S, i ≺ θ T, j or θ S ( i) = θ T ( j). When a schedule is injective, it is said to be sequential: each execution is scheduled at a different time. Hence everything is executed in sequence. In the polyhedral model, schedules are affine functions. They can be derived automatically from flow dependences [START_REF] Bondhugula | A practical automatic polyhedral parallelizer and locality optimizer[END_REF]. On Figure 1, the original execution order is specified by the schedule θ load (i) = (0, i), θ C (t, i) = (1, t, i) and θ store (i) = (2, i), where C denotes the compute statement. The lexicographic order ensures the execution of all the load instances (0), then all the compute instances (1) and finally all the store instances (2). Then, for each statement, the loops are executed in the specified order.

Loop tiling is a transformation which partitions the computation in tiles, each tile being executed atomically. Communication minimization [START_REF] Alias | Optimizing remote accesses for offloaded kernels: Application to high-level synthesis for FPGA[END_REF] typically relies on loop tiling to tune the ratio computation/communication of the program beyond the ratio peak performance/communication bandwidth of the target architecture. Figure 2.(a) depicts the iteration domain of compute and the new execution order after tiling loops t and i. For presentation reasons, we depict a domain bigger than in Figure 1.(b) (with bigger N and M ) and we depict only a part of the domain. In the polyhedral model, a loop tiling is specified by hyperplanes with linearly independent normal vectors τ 1 , . . . , τ d where d is the number of nested loops (here τ 1 = (0, 1) for the vertical hyperplanes and τ 2 = (1, 1) for the diagonal hyperplanes). Roughly, hyperplanes along each normal vector τ i are placed at regular intervals b i (here b 1 = b 2 = 4) to cut the iteration domain in tiles. Then, each tile is identified by an iteration vector (φ 1 , . . . , φ d ), φ k being the slice number of an iteration i along normal vector τ k :

φ k = τ k • i ÷ b k . The result is a Presburger iteration domain, here DC = {(φ 1 , φ 2 , t, i), 4φ 1 ≤ t < 4(φ 1 + 1) ∧ 4φ 2 ≤ t + i < 4(φ 2 + 1
)}: the polyhedral model is closed under loop tiling. In particular, the tiled domain can be scheduled. For instance, θC (φ 1 , φ 2 , t, i) = (φ 1 , φ 2 , t, i) specifies the execution order depicted in Figure 2.(a)): tile with point (4,4) is executed, then tile with point (4,8), then tile with point [START_REF] Alias | Data-aware Process Networks[END_REF][START_REF] Rijpkema | Deriving process networks from nested loop algorithms[END_REF], and so on. For each tile, the iterations are executed for each t, then for each i.

Polyhedral Process Networks

We derive a polyhedral process network by partitioning iterations domains into processes and the flow dependence relation into channels. Figure 1.(c) depicts a possible PPN from the Jacobi 1D kernel given on Figure 1.(a). For this example, we choose a canonical partition of the computation (one process per statement) and a partition of flow dependences such that there is single channel per couple producer/read reference, as motivated later. More formally, a polyhedral process network is a couple (P, C) such that:

Each process P ∈ P is specified by an iteration domain D P and a sequential schedule θ P inducing an execution order ≺ P over D P . Each iteration i ∈ D P realizes the execution instance µ P ( i) in the program. The processes partition the execution instances in the program: {µ P (D P ) for each process P } is a partition of the program computation.

Each channel c ∈ C is specified by a producer process P c ∈ P, a consumer process C c ∈ P and a dataflow relation → c relating each production of a value by P c to its consumption by C c : if i → c j, then execution i of P c produces a value read by execution j of C c . → c is a subset of the flow dependences from P c to C c and the collection of → c for each channel c between two given processes P and C, {→ c , (P c , C c ) = (P, C)}, is a partition of flow dependences from P to C.

The goal of this paper is to find out a partition of flow dependences for each producer/consumer couple (P, C), such that most channels from P to C can be realized by a FIFO.

On Figure 1.(c), each execution S, i is mapped to process P S and executed at process iteration i: µ P S ( i) = S, i . For presentation reason the compute process is depicted as C. Dependences depicted as k on the dependence graph in (b) are solved by channel k. To read the input values in parallel, we use a different channel per couple producer/read reference, hence this partitioning. We assume that, locally, each process executes instructions in the same order than in the original program: θ load (i) = i, θ compute (t, i) = (t, i) and θ store (i) = i. Remark that the leading constant (0 for load, 1 for compute, 2 for store) has disappeared: the timestamps only define an order local to their process: ≺ load , ≺ compute and ≺ store . The global execution order is driven by the dataflow semantics: the next process operation is executed as soon as its operands are available. The next step is to detect communication patterns to figure out how to implement channels.

Communication Patterns A channel c ∈ C might be implemented by a FIFO iff the consumer C c reads the values from c in the same order than the producer P c writes them to c (in-order) and each value is read exactly once (unicity) [START_REF] Turjan | Compiling nested loop programs to process networks[END_REF][START_REF] Turjan | Classifying interprocess communication in process network representation of nested-loop programs[END_REF]. The in-order constraint can be written:

in-order(→ c , ≺ P , ≺ C ) := ∀x → c x , ∀y → c y : x ≺ C y ⇒ x P y
The unicity constraints can be written:

unicity(→ c ) := ∀x → c x , ∀y → c y : x = y ⇒ x = y
Notice that unicity depends only on the dataflow relation → c , it is independent from the execution order of the producer process ≺ P and the consumer process ≺ C . Furthermore, ¬in-order(→ c Inria , ≺ P , ≺ C ) and ¬unicity(→ c ) amount to check the emptiness of a convex polyhedron, which can be done by most LP solvers. Finally, a channel may be implemented by a FIFO iff it verifies both in-order and unicity constraints:

fifo(→ c , ≺ P , ≺ C ) := in-order(→ c , ≺ P , ≺ C ) ∧ unicity(→ c )
When the consumer reads the data in the same order than they are produced but a datum may be read several times: in-order(→ c , ≺ P , ≺ C ) ∧ ¬unicity(→ c ), the communication pattern is said to be in-order with multiplicity: the channel may be implemented with a FIFO and a register keeping the last read value for multiple reads. However, additional circuitry is required to trigger the write of a new datum in the register [START_REF] Turjan | Compiling nested loop programs to process networks[END_REF]: this implementation is more expensive than a single FIFO. Finally, when we have neither in-order nor unicity: ¬in-order(→ c , ≺ P , ≺ C )∧¬unicity(→ c ), the communication pattern is said to be out-of-order with multiplicity: significant hardware resources are required to enforce flow-and anti-dependences between producer and consumer and additional latencies may limit the overall throughput of the circuit [START_REF] Alias | Data-aware Process Networks[END_REF][START_REF] Zissulescu | Solving out of order communication using CAM memory: an implementation[END_REF][START_REF] Turjan | Realizations of the extended linearization model. Domain-specific processors: systems, architectures, modeling, and simulation[END_REF][START_REF] Van Haastregt | Enabling automatic pipeline utilization improvement in polyhedral process network implementations[END_REF]. Consider Figure 1.(c), channel 5, implementing dependence 5 (depicted on (b)) from

•, t-1, i (write a[t, i]) to •, t, i (read a[t -1, i]).
With the original sequential schedule, the data are produced ( •, t -1, i ) and read ( •, t -1, i ) in the same order, and only once: the channel may be implemented as a FIFO. Now, assume that process compute follows the tiled execution order depicted in Figure 2.(a). The execution order now executes tile with point (4,4), then tile with point (4,8), then tile with point [START_REF] Alias | Data-aware Process Networks[END_REF][START_REF] Rijpkema | Deriving process networks from nested loop algorithms[END_REF], and so on. In each tile, the iterations are executed for each t, then for each i. Consider iterations depicted in red as 1, 2, 3, 4 in Figure 2.(b). With the new execution order, we execute successively 1,2,4,3, whereas an in-order pattern would have required 1,2,3,4. Consequently, channel 5 is no longer a FIFO. The same hold for channel 4 and 6. Now, the point is to partition dependence 5 and others so FIFO communication pattern hold. Alias hyperplane φ 1 (direction t), blue dependences crossing tiling hyperplane φ 2 (direction t + i) and green dependences inside a tile. Since the execution order in a tile is the same as the original execution order (actually a subset of the original execution order), green dependences will verify the same FIFO communication pattern as in the non-tiled version. As concerns blue and red dependences, source and target are executed in the same order because the execution order is the same for each tile and dependence 5 happens to be short enough. In practice, this partitioning is effective to reveal FIFO channels. In the next section, we recall our algorithm to find such a partitioning. The next subsection presents the Data-aware process networks, the particular kind of PPN on which the algorithm is complete.

Data-aware Process Networks

There are as many polyhedral process networks as possible partitions of the computations (processes) and dependences (channels) of the input kernel. A data-aware process network [START_REF] Alias | Data-aware Process Networks[END_REF] is a process/channel partition template which allows, given a relevant loop tiling, to control the data transfers volume and the parallelism degree at the same time. Figure 3 gives a possible DPN partition (b) from a loop tiling (a) on the motivating example. Given a loop tiling D S → DS for each statement S, we consider the execution order induced by the schedule θS (φ 1 , . . . , φ n , i) = (φ 1 , . . . , φ n , i): for each (φ 1 , . . . , φ n-1 ), we execute the sequence of tiles (φ n , i) such that (φ 1 , . . . , φ n , i) ∈ DS . The set of executions S, i given (φ 1 , . . . , φ n-1 ) is called a band and written B(φ 1 , . . . , φ n-1 ). On Figure 3.(a), B(1) is the set of tiles surrounded by thick red lines. First, band B(0) (with 0 ≤ t < 4) is executed tile by tile, then band B( 1) is executed tile by tile, and so on. On DPN, a band acts as a reuse unit. This means that incoming dependences (here 1,2,3) are loaded and outcoming dependences (here 13,14,15) are stored to an external storage unit. Dependences inside a band are resolved through channels (here 4 to 12). Inside a band, the computations may be split in parallel process thanks to surrounding hyperplanes ( τ 1 , . . . , τ n-1 ). On Figure 3 We distinguish between i/o dependences, (→ i/o source or target outside of the band e.g. 1, 2, 3 or 13, 14, 15), local dependences to each parallel process (→ local , source and target on the same parallel process e.g. [START_REF] Alias | Data-aware Process Networks[END_REF][START_REF] Alias | Optimizing Affine Control with Semantic Factorizations[END_REF][START_REF] Bastoul | Efficient code generation for automatic parallelization and optimization[END_REF] and synchronization dependences between parallel process (→ synchro , source and target on different parallel process e.g. 7, 8, 9). For each array a loaded/stored through → i/o , a load (resp. store) process Load a (resp. Store a ) is created. For each i/o dependence (P , φ 1 , . . . , φ n , i) → i/o , φ 1 , . . . , φ n , j), assuming the data written by P is a[u( i)] and the data read by C is a[v( j)], the dependence is removed and replaced by a dependence flowing to Store a : (P , φ 1 , . . . , φ n , i) → i/o (Store a , φ 1 , . . . , φ n , u( i)), and by a dependence flowing from Load a : (Load a , φ 1 , . . . , φ n , v( j)) → i/o (C , φ 1 , . . . , φ n , j) (on Figure (b), these processes are simply named Load/Store). Dependence → i/o and processes Load a and Store b can be further optimized to improve data reuse through the band [START_REF] Alias | Data-aware Process Networks[END_REF]. Finally each channel c of the original PPN is partitioned in such a way that each new channel c connects a single producer process and consumer process (here original PPN channel 4 is split into DPN channels 4, 7, 10). We keep track of the original PPN channel with the mapping µ: µ(c ) := c (here µ(4) = µ(7) = µ(10) = 4).

Inria

The DPN partitioning will be denoted by (L, P , S, C ) where L is the set of Load process, P is the set of parallel processes, S is the set of store processes Store and C is the set of channels. 3: Data-aware process network (DPN) for the Jacobi-1D kernel. (a) computations are executed per band (between red thick lines), tile per tile. Incoming dependences (1,2,3) are loaded, outcoming dependences [START_REF] Turjan | Compiling nested loop programs to process networks[END_REF][START_REF] Turjan | Realizations of the extended linearization model. Domain-specific processors: systems, architectures, modeling, and simulation[END_REF][START_REF] Turjan | Classifying interprocess communication in process network representation of nested-loop programs[END_REF] are stored, internal dependences (4 to 12) are solved through local channels depicted in (b). Parallelization is derived by splitting a band with tiling hyperplanes (here the dotted line). With this scheme, arithmetic intensity and parallelism can be tuned easily.

The Partitioning Algorithm

In this section, we recall our algorithm presented in [START_REF] Alias | Improving communication patterns in polyhedral process networks[END_REF] to restructure the channels so FIFO channels can be recovered after a loop tiling. Then, we present the contributions of this paper. Section 3.1 proves that the algorithm is complete on DPN. Then, Section 3.2 points out the limits of the algorithm on general PPN without the DPN partitioning.

Figure 4 depicts the algorithm for partitioning channels given a polyhedral process network (P, C) (line 5). For each channel c from a producer P = P c to a consumer C = C c , the channel is partitioned by depth along the lines described in the previous section (line 7). D P and D C are assumed to be tiled with the same number of hyperplanes. P and C are assumed to share a schedule with the shape: θ(φ 1 , . . . , φ n , i) = (φ 1 , . . . , φ n , i). In other words, the execution of a tile follow the order as in the original program. This case arises frequently with tiling schemes for I/O optimization [START_REF] Alias | Data-aware Process Networks[END_REF]. If not, the next channel → c is considered (line 6). The split is realized by procedure split (lines 1-4). A new partition is built starting from the empty set. For each depth (hyperplane) of the tiling, the dependences crossing that hyperplane are filtered and added to the partition (line 3): this gives dependences → 1 c , . . . , → n c . Finally, dependences lying in a tile (source and target in the same tile) are added to the partition (line 4): this gives → n+1 c . θ P (x) ≈ n θ C (y) means that the n first dimensions of θ P (x) and θ C (y) (tiling coordinates (φ 1 , . . . , φ n )) are the same: x and y belong to the same tile. Consider the PPN depicted in Figure 1.(c) with the tiling and schedule discussed above: process compute is tiled as depicted in Figure 2.(c) with the schedule θ compute (φ 1 , φ 2 , t, i) = (φ 1 , φ 2 , t, i). Since processes load and store are not tiled, the only channels processed by the algorithm are 4,5 and 6. split is applied on the associated dataflow relations → 4 , → 5 and → 6 . Each dataflow relation is split in three parts as depicted in Figure 2.(c). For → 5 : → 1 5 crosses hyperplane t (red), → 2 5 crosses hyperplane t + i (blue) and → 3 5 stays in a tile (green). Each of these new dataflow relations → 1 5 , → 2 5 ,→ 3 5 exhibit a FIFO communication pattern w.r.t. θ. The total space occupied by these new FIFO is almost the same as the original channel plus a small overhead as discussed in [START_REF] Alias | Improving communication patterns in polyhedral process networks[END_REF].

Consider the DPN depicted in Figure 3. This DPN is derived from the PPN in Figure 1.(c), with the tiling described above. The dependences are pre-split into channels to fit with the DPN execution model: load/store dependences (red and black), intra-process dependences for each parallel process C 1 and C 2 (blue for C 1 , yellow for C 2 ) and communication between parallel processes (green dependences). Dependence 4 and 5 lead to the same faulty communication pattern as in Figure 2.(b). Our algorithm will split them between dependence instances crossing the t + i hyperplane (as on the figure) and dependence instances with source and target inside the same tile. Here, each split gives a FIFO. Similarly, the same splitting occurs for process C 2 . Communication dependences [START_REF] Bondhugula | A practical automatic polyhedral parallelizer and locality optimizer[END_REF][START_REF] Feautrier | Dataflow analysis of array and scalar references[END_REF][START_REF] Kelly | The omega calculator and library, version 1.1. 0[END_REF], green) can be implemented directly by a FIFO: no split is required on this example. Finally, all the compute-to-compute channels (4 to 12) can be turned to FIFO. Load/Store dependences are not considered for splitting because load and store buffers are usually not FIFOs. Indeed, each loaded data will usually be read several times as DPN are tuned for a maximal data reuse. Also, the store process will read the data to prepare burst data transfers. Hence, the store read order is generally not the write order of the producer process (here process C 2 ).

Completeness on DPN partitioning

The algorithm always succeeds to recover all the FIFO on PPN with the DPN execution schema: if a PPN channel c is a FIFO before tiling, then, after tiling and turning the PPN into a DPN, the algorithm can split each DPN channel c created from the PPN channel c (c = µ(c)) in such a way that we get FIFOs. We say that the splitting algorithm is complete over DPN. This is an important enabling property for DPN: essentially, it means that DPN allow to implement the Inria tiling transformation while keeping FIFO channels, which is necessary (though not sufficient) to map it to hardware. In the next section, we will show that general PPN (without DPN partitioning) are not complete. This shows that DPN is an important subset of PPN.

We start by a fundamental lemma, asserting that if a dependence relation → can be implemented with a FIFO w.r.t. a given schedule then any subset of → with the same schedule can also be implemented by a FIFO: Proof: Any counter example → ⊂→ c such that ¬fifo(→ , θ Pc , θ Cc ) would imply that ¬fifo(→ c , θ Pc , θ Cc ): if ¬in-order(→ , θ Pc , θ Cc )) then ¬in-order(→ c , θ Pc , θ Cc )), also: if ¬unicity(→ ) then ¬unicity(→ c ). This contradicts the hypothesis. q.e.d.

With this lemma, we can prove the completeness of the algorithm on any DPN partitioning: Proof: Since we only consider channels between compute processes of P , we can exclude the case → c ⊂→ i/o (load source or store target). Hence we have to consider the remaining cases → c ⊂→ local and → c ⊂→ synchros . Assume → c ⊂→ local . This is the case for dependences 4, 5, 6 and 10, 11, 12. First, remark that dependences of → local can only cross the last tiling hyperplane ( τ 2 on figure 3.(a)). Indeed, the dependences crossing the remaining hyperplanes are all gathered in → i/o by construction. Also, dependences between parallel processes are all gathered in → synchro by construction. If the last tiling hyperplane does not break the fifo communication pattern, no splitting is required. Else, the splitting ends-up with a new dependence (and channel) partition:

→ c =→ last c → tile c . → last c
being the dependence instances crossing the last tiling hyperplane and → tile c being the dependence instances lying inside a tile. Since in a tile, the schedule induces the same execution order as in the original DPN, → tile c ⊂→ c , and c is a FIFO with the original execution order, then → tile c gives a FIFO channel (lemma 3.1). Similarly, → last c links iterations from a producer tile (tile in the example) to the next consumer tile (tile on the example). Since → last c ⊂→ c and fifo(→ c , θ Pc , θ Cc ), then fifo(→ last c , θ Pc , θ Cc ) by lemma 3.1. To conclude that → last c gives a FIFO in the DPN, we need to check that the execution order on the producer side of → last c is a subset of ≺ θ Pc and that the execution order on the consumer side of → last c is a subset of ≺ θ Cc . Provided the tile size is big enough, we can assume that starting from a given tile, the targets of → last c belong the same tile (typically the next tile in the execution). By hypothesis, the execution order on a tile is a subset of the original execution order ( θS (φ 1 , . . . , φ n , i) = (φ 1 , . . . , φ n , i) for each statement S). In particular, the execution order of the producers (resp. consumers) of → last c is a subset of ≺ θ Pc (resp. ≺ θ Cc ). Hence the splitting ends-up with FIFO channels. This is a general apparatus which will be used to prove the next case.

Assume → c ⊂→ synchro . On the example, this happens for dependences 7, 8, 9. Remark that → c hold dependences from a producer tile (here tile 3) to tiles mapped to the same consumer process (here 4 and 6) by construction. Data sent to several consumer processes cannot flow through the same channel. Hence the only hyperplane which can separate consumer iteration is again the last tiling hyperplane. Either all the consumer iterations belong to the same tile (here 9), and we directly have a FIFO by lemma 3.1. Either consumer iterations are split by the last tiling hyperplane: → c =→ last c → tile c (here 7,8). The same reasoning as in the previous paragraph allow to conclude that both cases can be implemented by a FIFO. Hence the splitting ends-up with FIFO channels.

This shows the completeness of the algorithm on DPN partitioning schema. q.e.d.

RR n°9187

Limitations on general PPN

When the PPN does not follow the DPN partitioning, there is no guarantee that the algorithm will always succeed to recover FIFO. Figure 5 gives a counter example. We modify the kernel given on Figure 1.(a) to observe a single dependence (t, i) → (t + 2, i -1) on the compute domain (•) and we keep the same loop tiling. The resulting PPN is almost like in (c) but with a single compute buffer (4 is kept to solve the dependence, 5, 6 are removed). The algorithm will split the dependence in three parts: the dependences crossing the t hyperplane (partially depicted, in green), the dependences crossing the t + i hyperplane (not depicted) and the dependence totally inside a tile (not depicted). In tile 2, iteration [START_REF] Alias | Data-aware Process Networks[END_REF][START_REF] Quilleré | Generation of efficient nested loops from polyhedra[END_REF] is executed before iteration (5, 7): (4, 11) ≺ θ (5, 7). But the dependence target of iterations [START_REF] Alias | Data-aware Process Networks[END_REF][START_REF] Quilleré | Generation of efficient nested loops from polyhedra[END_REF] and [START_REF] Alias | Optimizing Affine Control with Semantic Factorizations[END_REF][START_REF] Bondhugula | A practical automatic polyhedral parallelizer and locality optimizer[END_REF] are not executed in the same order because (5, 7) targets tile 5 and (4, 11) targets tile 6 (the next tile in the execution order). Hence the in-order property is not verified and the channel cannot be realized by a FIFO.

We observe that the algorithm works pretty well for short uniform dependences. However, when dependences are longer, the target operations reproduce the tile execution pattern, which prevents to find a FIFO. The same happens when the tile hyperplanes are "too skewed". Indeed, skewed hyperplanes can be viewed as orthogonal hyperplanes modulo a change of basis. When the hyperplanes are too skewed, the change of basis enlarge the dependence size which produce the same effect as in the counter-example. To summarize, the dependences must be uniform i → i + d and reasonably short (small d ). This means that tiling hyperplanes should not be too skewed. Indeed, skewed hyperplanes can always be viewed as orthogonal hyperplanes modulo a change of basis in the iteration space. The more skewed the hyperplanes are, the longer the dependence will be after the change of basis, thereby causing the same issue than on the counter example. The next section will, in particular, assess the capabilities of our algorithm to recover FIFO on general PPN.

Inria 4 Experimental Evaluation

This section presents the experimental results obtained on the benchmarks of the polyhedral community. We check the completeness of the algorithm on DPN process networks. Then, we assess the performances of the algorithm on PPN without DPN partitioning scheme. Finally, we show how much additional storage is produced by the algorithm.

Experimental Setup

We have run the algorithm on the kernels of PolyBench/C v3.2 [START_REF] Pouchet | Polybench: The polyhedral benchmark suite[END_REF]. We have checked the completeness of the algorithm on PPN with DPN partitioning (Table 1), study the behavior of the algorithm on general PPN, without DPN partitioning (Table 2). Each kernel is tiled to reduce I/O while exposing parallelism [START_REF] Alias | Data-aware Process Networks[END_REF] and translated both to a PPN and a DPN using our research compiler, Dcc (DPN C Compiler). On the DPN, the process are parallelized with a degree of p = 2 on each band dimension: for a kernel with a loop tiling of dimension n, each compute process is split in 2 n-1 parallel processes.

Completeness on DPN Table 1 checks the completeness of our algorithm on PPN with DPN partitioning. For each kernel, column #buffers gives the total number of channels after applying our algorithm, column #fifos gives the total number of FIFO among these channels, the next columns provide the total size of FIFO channels and the total size of channels (unit: datum). Then, the next column assess the completeness of the algorithm. To do so, we recall the number of FIFO c in the original PPN before DPN partitioning and without tiling (#fifo basic). After tiling and DPN partitioning, each FIFO c is partitioned into several buffers c (µ(c ) = c). Column #fifo passed gives the number of original FIFO c such that all target buffers c are directly FIFO: #{c | ∀c : µ(c ) = c ⇒ c is a FIFO}. No splitting is required for these buffers c . Column #fifo fail gives the number of original FIFO c such that at least one target buffer c is not a FIFO: #{c | ∃c : µ(c ) = c ∧ c is not a FIFO}. If all the failing buffers c can be split into FIFO by the algorithm, we say that c has been restored. The column #fifo restored count the restored FIFO c. Since the algorithm is complete, we expect to have always #fifo fail = #fifo restored. The last column gives the proportion of FIFO c not restored. We expect it to be always 0. As predicted, the results confirm the completeness of the algorithm on DPN partitioning: all the FIFO are restored.

Limits on PPN without DPN partitioning Table 2 shows how the algorithm can recover FIFO on a tiled PPN without the DPN partitioning. The columns have the same meaning as the table 1: columns #buffers and #fifos gives the total number of buffers (resp. fifos) after applying the algorithm. Column #fifo basic give the number of FIFO in the original untiled PPN: we basically want to recover all these fifos. Among these FIFO buffers: column #fifo passed gives the number of buffers which are still a FIFO after tiling and column #fifo fail gives the number of FIFO buffer broken by the tiling. These are the FIFO which need to be recovered by our algorithm. Among these broken FIFO: column #fifo restored gives the number of FIFO restored by the algorithm and column % fail gives the ratio of broken FIFO not restored by the algorithm. Since our algorithm is not complete on general PPN, we expect to find non-restored buffers. This happens for kernels 3mm, 2mm, covariance, correlation, fdtd-2d, jacobi-2d, seidel-2d and heat-3d. For kernels 3mm, 2mm, covariance and correlation, failures are due to the execution order into a tile, which did not reproduce the original execution order. This is inherently due to the way we derive the loop tiling. It could be fixed by imposing the intra tile execution order as prerequisite for the tiling algorithm. But then, other criteria (buffer size, throughput, etc) could be harmed: a trade-off needs to be found. For the remaining kernels: fdtd-2d, jacobi-2d, seidel-2d and heat-3d, failures are due to tiling hyperplanes which are too skewed. This fall into the counter-example described in Section 3.2, it is an inherent limitation of the algorithm, and it cannot be fixed by playing on the schedule. The algorithm succeed to recover the all FIFO channels on a significant number of kernels (14 among 22): it happens that these kernels fulfill the conditions expected by the algorithm (short dependence, tiling hyperplanes not too skewed). Even on the "failing" kernels, the number of FIFO recovered is significant as well, though the algorithm is not complete: the only exception is the heat-3d kernel.

Conclusion

In this paper, we have studied an algorithm to reorganize the channels of a polyhedral process network to reveal more FIFO communication patterns. Specifically, the algorithm operates channels whose producer and consumer iteration domain has been partitioned by a loop tiling.

We have proven the completeness of the algorithm on the DPN partitioning scheme. Also, we pointed out limitations of the algorithm on general PPN. Experimental results confirms the completeness of the algorithm on DPN as well as the limitations on general PPN. Even in that case, in a significant number of cases, the algorithm allows to recover the FIFO disabled by loop tiling with almost the same storage requirement. This means that our algorithm enables DPN as an intermediate representation for middle-end level polyhedral optimizations.

In the future, we plan to design a channel reorganization algorithm provably complete on general PPN with tiling, in the meaning that a FIFO channel will be recovered whatever the dependence size and the tiling used. Finally, we observed that FIFO failures can be avoided by playing with the intra-tile schedule. This may hinder other criteria (buffer size, throughput). We plan to study the trade-offs involved and to investigate how to constrain the scheduling algorithm while keeping acceptable trade-offs.

Figure 1 :

 1 Figure 1: Motivating example: Jacobi-1D kernel. (a) depicts a polyhedral kernel, (b) gives the polyhedral representation of loop iterations (•: load, •: compute, •: store) and flow dependences (red arrows), then (c) gives a possible implementation as a polyhedral process network: each assignement (load, compute, store) is mapped to a different process and flow dependences (1 to 7) are solved through channels.

Figure 2 :

 2 Figure 2: Impact of loop tiling on the communication patterns. (a) gives the execution order of the Jacobi-1D main loop after a loop tiling, (b) shows how loop tiling disables the FIFO communication pattern, then (c) shows how to split the dependences into new channels so FIFO can be recovered. Consider Figure 2.(c). Dependence 5 is partitioned in 3 parts: red dependences crossing tiling

  .(a), each band is split in two sub-bands separated by a dotted line, thanks to hyperplane τ 1 = (1, 0). Each sub-band is implemented by a separate process on Figure 3.(b): C 1 for the left sub-band, C 2 for the right sub-band. The DPN partitioning allows to tune the arithmetic intensity (A.I.) by playing on the band width b (here A.I. = 2 × bN/2N = b) and to select the parallelism independently Each parallel process is identified by its coordinate = ( 1 , . . . , n-1 ) along surrounding hyperplanes. Assuming p parallel instances along each surrounding hyperplanes we have 0 ≤ k < p. The parallel instance of C of coordinate , for 0 ≤ k < p is written C (here we have parallel instances C 0 and C 1 ).

1 6 for each channel c 7 {→ 1 c 9 removeFigure 4 :

 67194 Figure4: Our algorithm for partitioning channels[START_REF] Alias | Improving communication patterns in polyhedral process networks[END_REF]. The algorithm split produces the dependence partition described on Figure2.(c), for each depth k of the producer schedule θ P and the consumer schedule θ C . The dependence partition is kept if each set of the dependence partition has a FIFO pattern.

Lemma 3 . 1

 31 Consider a PPN (P, C) and a channel c ∈ C. If → ⊂→ c and fifo(→ c , θ Pc , θ Cc ) then: fifo(→ , θ Pc , θ Cc ).

Property 3 . 2

 32 Consider a PPN (P, C) and a DPN partitioning (L, P , S, C ) w.r.t. a tiled schedule. Then, for each channel c ∈ C of the DPN: if the original channel in the PPN c = µ(c ) is a FIFO, then the split of c will be a FIFO as well.

Figure 5 :

 5 Figure 5: Counter example on general PPN. When dependences are too long, target iterations reproduce the tiling pattern ; hence breaking the FIFO pattern.

2 . 2 8 3 3 . 1

 22831 Model at a Glance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Scheduling and Loop Tiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 Polyhedral Process Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.4 Data-aware Process Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The Partitioning Algorithm 9 Completeness on DPN partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2 Limitations on general PPN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Inovallée 655 avenue de l'Europe Montbonnot 38334 Saint Ismier Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Table 1 :

 1 Detailed results on PPN with DPN execution scheme. The algorithm is complete on DPN: all the FIFO were recovered (%fail = 0)

	Kernel #buffers #fifos total fifo size total size #fifo basic #fifo passed #fifo fail #fifo restored %fail
	trmm 12	12	516	516	2	1	1	1	0
	gemm 12	12	352	352	2	1	1	1	0
	syrk 12	12	8200	8200	2	1	1	1	0
	symm 30	30	1644	1644	6	5	1	1	0
	gemver 15	13	4180	4196	4	3	1	1	0
	gesummv 12	12	96	96	6	6	0	0	0
	syr2k 12	12	8200	8200	2	1	1	1	0
	lu 45	22	540	1284	3	0	3	3	0
	trisolv 12	9	23	47	4	3	1	1	0
	cholesky 44	31	801	1129	6	4	2	2	0
	doitgen 32	32	12296	12296	3	2	1	1	0
	bicg 12	12	536	536	4	2	2	2	0
	mvt 8	8	36	36	2	0	2	2	0
	3mm 53	43	5024	5664	6	3	3	3	0
	2mm 34	28	1108	1492	4	2	2	2	0
	covariance 45	24	542	1662	7	4	3	3	0
	correlation 71	38	822	2038	13	9	4	4	0
	fdtd-2d 120	120	45696	45696	12	5	7	7	0
	jacobi-2d 123	123	10328	10328	10	2	8	8	0
	seidel-2d 102	102	60564	60564	9	2	7	7	0
	jacobi-1d 23	23	1358	1358	6	2	4	4	0
	heat-3d 95	95	184864	184864	20	2	18	18	0

  InriaKernel #buffers #fifos total fifo size total size #fifo basic #fifo passed #fifo fail #fifo restored %fail

	trmm 3	3	513	513	2	1	1	1	0
	gemm 3	3	304	304	2	1	1	1	0
	syrk 3	3	8194	8194	2	1	1	1	0
	symm 9	9	821	821	6	3	3	3	0
	gemver 8	7	4147	4163	4	2	2	2	0
	gesummv 6	6	96	96	6	6	0	0	0
	syr2k 3	3	8194	8194	2	1	1	1	0
	lu 11	6	531	1091	3	0	3	3	0
	trisolv 6	5	20	36	4	3	1	1	0
	cholesky 12	9	789	1077	6	3	3	3
	doitgen 4	4	12289	12289	3	2	1	1	0
	bicg 6	6	532	532	4	2	2	2	0
	mvt 4	4	34	34	2	0	2	2	0
	3mm 10	6	1056	2848	6	2	4	2	50%
	2mm 6	4	784	1296	4	2	2	1	50%
	covariance 12	8	533	1317	7	4	3	2	33%
	correlation 22	15	810	1642	13	9	4	3	25%
	fdtd-2d 20	14	10054	36166	12	0	12	6	50%
	jacobi-2d 12	4	1153	8385	10	0	10	2	80%
	seidel-2d 12	6	803	49955	9	0	9	3	66%
	jacobi-1d 13	13	1178	1178	6	1	5	5	0
	heat-3d 20	0	0	148608	20	0	20	0	100%

Table 2 :

 2 Detailed results on PPN. The algorithm is not complete on general PPN: some FIFO were not recovered (for some kernels, %fail = 0).

RR n°9187


Michael Ullmann
email: ullmann@itiv.uni-karlsruhe.de

Wansheng Jin
email: jin@itiv.uni-karlsruhe.de

Jürgen Becker
email: becker@itiv.uni-karlsruhe.de

Hardware Support for QoS-based Function Allocation in Reconfigurable Systems

Keywords: CBR, Algorithm, Resource Management

This contribution presents a new approach for allocating suitable function-implementation variants depending on given quality-of-service functionrequirements for run-time reconfigurable multi-device systems. Our approach adapts methodologies from the domain of knowledge-based systems which can be used for doing run-time hardware/software resource usage optimizations.

Introduction

During the last four years FPGAs have become the favorite prototyping devices in many application areas of computer sciences and electrical engineering. Since modern FPGAs have a higher integration density offering features like partial run-time reconfiguration (e.g. on Xilinx Virtex II FPGAs) they have become attractive for a variety of embedded applications and scientific approaches exploiting theses features. Partial run-time reconfiguration enables for a new class of embedded applications utilizing FPGA resources at run-time as flexible and adaptive hardware-accelerated coprocessors [START_REF] Griese | Hardware Support for Dynamic Reconfiguration in Reconfigurable SoC Architectures[END_REF]. Furthermore there already exist first academic approaches implementing a complete reconfigurable system-on-chip supporting run-time reconfiguration of dedicated functions and their management at run-time [START_REF] Ullmann | On-Demand FPGA Run-Time System for Dynamical Reconfiguration with Adaptive Priorities[END_REF] [START_REF] Walder | A Runtime Environment for Reconfigurable Hardware Operating Systems[END_REF]. Other researchers already have implemented low budget embedded operating systems running on soft-core or hard-wired on-chip processors on FPGA (e.g. uClinux on a Xilinx MicroBlaze [9]). Combining these approaches using one or several low-cost reconfigurable devices plus dedicated hardware like ASICs or DSPs will create flexible and highly adaptive multi-purpose systems which can be applied in a variety of application domains (e.g. automotive infotainment, multimedia, control-oriented applications etc.). The development and proof of such a versatile system concept is a main research topic of our research group. Our previous work consisted in the development and implementation of a first run-time reconfigurable system-on-chip, supporting flexible ondemand hardware-task switching and a sophisticated runtime reconfiguration and task management mechanisms on Xilinx Virtex II FPGAs [START_REF] Ullmann | On-Demand FPGA Run-Time System for Dynamical Reconfiguration with Adaptive Priorities[END_REF][10]. Although the tested application domain in our previous work targets at automotive control applications with soft time and security constraints we intend to extend our approach for other fields of application as already mentioned above. Common embedded systems usually have a set of subfunction realizations targeting only one type of hardware for their execution (e.g. as slow software or hardware accelerated functionality only). Additionally the location for execution is normally pre-defined at design time. We address this weak points, since we believe that run-time reconfigurable systems in combination with dedicated hardware resources will have benefits compared to ordinary embedded application approaches which cannot flexibly adapt to changing needs of users. Furthermore by applying intelligent management mechanisms we conceive to gain increases of system-performance and energy/power-efficiency.

CPU

As shown in figure 1 our previous approach can be reused as multiple entity at the lower reconfigurable hardware layer of our conceived system approach. Additionally dedicated hardware can be added in parallel. The system is logically divided into different layers. At the application level different applications are executed depending on the location and the mode of operation (as parallel hardware or sequential software tasks). Most applications are conceived to have major parts in software and some dedicated parts accelerated in reconfigurable hardware or DSP. The application level is separated from the lower system levels by an Application-API which offers services for communication, sub-function calls and quality of service (QoS) negotiation. A further system level below is responsible for the proper allocation of functions. Depending on the QoS demands, given by the application's function call an appropriate implementation of the desired function must be found from a run-time function repository. So this layer needs informations about the available functions, their different implementations and QoS features. Additionally it will need informations about the current system load and power consumption status, which are procured by the HW-Layer API one level below. The HW-Layer API is the interface for all hardware relevant aspects like resource consumption, low-level communication and reconfiguration of system parts. It connects the high level components with the local system controllers, which may be located on different devices (e.g. standard CPU, FPGA (soft-core CPU) or DSP). These controllers are responsible for the control of local run-time reconfiguration and other sub-tasks like local task/ resource management and communication issues.

This paper will focus on some aspects of a QoS-aware function allocation so that details on the other system levels as they were not published yet will be presented in future papers. Our contribution is structured as follows: In section 2 we give a motivation for QoS-aware function allocation and how it can be solved by means of a simplified case-based-reasoning approach. Section 3 describes a short application example for our case-basedreasoning approach whereas section 4 describes the hardware/ software implementation and synthesis results of the algorithm. The paper closes with a summary and gives an outlook on our future work.

QoS-aware Function Allocation

In some cases, especially in multimedia applications it is not sufficient to do a simple function call if a dedicated function is needed which has to comply with additional constraints like data/frame-rates, processing modes, response deadlines etc. We conceive that the system offers for one requested function type different implementations which can be run as software or as reconfigurable accelerated hardware having different features. So there emerges the problem to identify a set of most appropriate implementation variants which match best to the given constraints from request. The found set of implementation variants can be used for checking the current system load and resource consumption state concerning the feasibility of a best matching implementation out of it which can be inserted on FPGA or as software-task on a processor. It is possible that the best matching implementation is not currently feasible without preempting other active (hardware) tasks so an alternative implementation can be offered to the calling application which has to decide on it. The details on this QoS negotiation mechanism as they are not presented here will be in the scope of future papers. At this point it is primarily here of interest how a best matching implementation by given constraints can be found. Before we introduce our approach we want to give an overview on case-based reasoning and how parts of this approach can be applied for solving that problem.

Case-based Reasoning Background

Case-based reasoning (CBR) is an approach for developing knowledge-based systems that are able to retrieve and reuse solutions that have worked for similar situations in the past. CBR traces its roots to the work of Roger Schank, Janet Kolodner and Michael Lebowitz in the early 1980s [START_REF] Bartsch-Spörl | Case-Based Reasoning --Survey and Future Directions[END_REF][5] [START_REF] Schank | Dynamic Memory: A Theory of Learning in Computers and People[END_REF]. Since the beginning of the 1990s CBR approaches are extensively applied in helpdesk applications and diagnostic expert systems for customer support. In CBR systems expertise is embodied in a library of past cases, rather than being encoded in classical rules. Each case typically contains a description of the problem, plus a solution and/or the outcome.

The knowledge and reasoning process used by an expert to solve the problem is not recorded, but is implicit in the solution. To solve a current problem: the problem is matched against the cases in the case base, and similar cases are retrieved. The retrieved cases are used to suggest a solution which is reused and tested for success. If necessary, the solution is then revised. Finally the current problem and the final solution are retained as part of a new case. The complete CBR-cycle is shown in figure 2.

Case-base Representation and Similarity

Problem cases may have different representations. These can be object-oriented, trees & graphs or sets of simple pairs of attributes and their values. We have found the latter representation appears to be best suited for our purposes, since attributes of some type may describe comparable features of different implementations. The attributes' values depend on their type and given value range and can be of integer/real type, even discrete ordered sets of symbols are possible if they can be mapped onto integers. Typical types can be data-rates, discrete processing modes (float/integer), power consumption, code/bitstream-sizes, response times, frame sizes, max. bit-error-rates etc. A local similarity measure is needed for comparing attributes of same type between different implementations. Such a measure is often based on a transformation function which calculates from the Euclidian or Manhattan distance of two given attributes a similarity value in the range [0 ... 1], where 1 means that both attribute values are identical and 0 means that both values have a maximum distance (no similarity).

.

A B i A B A B i j d x ,x s x ,x = 1- ; d x ,x 0 1+ max d x ,x
(1) f An example function is given in equ. (1) where x A , x B are attribute values of same type from a request A and an implementation case B. The function d(x i , x j ) calculates the distance / absolute difference between both values where max(d(x i , x j )) represents the maximum possible distance which can be determined at design time from all attributes of same type given by the implementation library. Since the request and implementation descriptions may contain several attributes it is not sufficient to calculate for every attribute pair (A Req_i , A Impl_i ) a local similarity s i . All local similarities s i have to be combined into a global similarity which enables for comparing all implementation variants of same basic function type with the attribute description set of a given function request. Such a needed function S global is denoted as amalgamation function which transforms an input vector located inside an n-dimensional cube [0 ... 1] n back into a scalar range of [0 ... 1]. A convenient function is the weighted sum of all local similarities as shown in equ. [START_REF] Bartsch-Spörl | Case-Based Reasoning --Survey and Future Directions[END_REF]. It is monotonous in every argument and S global (0, ...,0)=0; S global (1, ...,1)=1. , , ; 1 .

n n n i i i i i global S s s w s w (2) f
At this point it should be noted that other approaches for similarity calculations are possible as well. A well known method comes from statistical decision theory and determines the Mahalanobis distance by calculating the co-variance matrix of the whole set of function attributes. This method is very effective concerning the results but the computational efforts would be too large so we decided to apply Manhattan distance metrics.

Confirmed Solution

Application Example for Retrieval

Following short application example will give an impression how a retrieval and similarity comparison can be done. As shown in figure 3 an application requires an FIR-equalizer functionality for audio DSP purposes. Each offered type of basic-functionality has a global function-ID which is used for finding the proper type entry inside the function implementation tree. The nodes of this tree are ordered in a hierarchy, where the nodes in the upper level represent all function types whereas their successor nodes at lower levels contain informations about their related implementations like the implementation-ID which can have a unique system-global or a local ID value and a set of attributes, separable again by unique type IDs, which contain details on each implementation's features like processing bitwidth, processing mode (integer/float), output mode and sampling rate. Other attributes like power consumption, response deadlines etc. are conceivable. It should be noted here that such metrics which characterize a functionality on QoS-aspects have to be pre-defined by the designer as a set of attributes whose values are derived from simulations and tests of the function's model. Depending on the application's needs the request's attribute composition may vary. As first step all function type entries have to be checked for finding the required type (ID Type ). It should not happen that the desired type is not found since the application's functional requirements should already be known at design time, otherwise the function can not be served. In the given example case the desired function-ID Type = 1 is found and three possible implementations for different execution targets (FPGA, DSP, General Purpose Proc.) have to be checked. Figure 3 shows that the request's attribute-set does not have to be completely specified; incomplete subsets are possible as well which is a nice property of case-based retrieval. As next step all corresponding attributes are retrieved from each implementation attribute sub-table and for every implementation k a similarity value S global (k) is calculated by applying equ. ( 1) and (2) as shown in table 1. If a corresponding implementation attribute is not found, its local similarity s i can be set to 0 because a missing attribute can be seen as unsatisfiable requirement.

The d max values as used in table 1 were taken from an extra table (not shown here) which was generated at design time containing supplemental data on the attributes' design-global upper/lower value bounds (see also figure 4 (right -maxrange -1 )).

As the results show from table 1 the DSP-based function-implementation matches best to the given requirements. The FPGA-implementation produces the second-best similarity whereas the standard software implementation has a rather low similarity which would not satisfy the demands if the attributes were inspected manually. It's conceivable to reject all results below a given threshold similarity. In the given example the allocation manager would check now for each acceptable solution its feasibility concerning the system load and would suggest the remaining implementation-variants to the calling application. Since every available function realization has a unique identifier it will be possible to retrieve the function's corresponding configuration data (CPU opcode/ FPGA bitstream) from a global function repository for reconfiguration. It is still possible that no matching feasible variant was found so that the application has to repeat its request with rather relaxed constraints giving a chance to the third low performance implementation (ID Impl =3). Otherwise the application can not call the function. If a function was allocated and instantiated on hardware it is not necessary to repeat the retrieval procedure at repeated function calls. The allocation manager could create a kind of bypasstoken containing data one the previous selection which can be reused at repeated function calls so that only an availability check on the function and its allocated resources has to be done.

Hardware/Software Implementation

The function allocation manager's retrieval functionality can be implemented in software or as hardware mapped algorithm. Although case-based retrieval is a rather control oriented algorithm we have been able to model, simulate and synthesize an accelerated retrieval unit on FPGA.

Data Structures

As first step the needed data structures for request and implementation-tree were defined. We decided to use linear lists which can be connected by reference pointers for creating complex tree structures. Each list contains several entries like IDs, values, pointers and is terminated by a dedicated NULL-entry. These lists can be easily mapped on linear organized RAM-blocks if all list elements use the same word length per entry (e.g. 16 or 32 bits). Figure 4 (left) shows the structure of a list containing the request description including the desired function type, attributes and weighting factors w i to be used. The internal order of entries is predefined so that an attribute's ID is always followed by its value and weight. Additionally the attribute-blocks have to be pre-sorted by their ID in ascending order. This measure is applied in all other list-structures as well (see figure 5) and aims at improving the retrieval efficiency of the algorithm. Because each attribute has to be searched by its ID in each implementation's attribute-list it is possible to avoid a repeated search from the top of each list. Since the next requested attribute has a larger ID value than its predecessor it is possible to continue searching from the current position instead of doing a repeated search from the top of the local list. As a consequence the effort for searching becomes linear.

Another auxiliary list which is used for similarity calculation is shown in figure 4 (right). The entries are grouped again in blocks and they are pre-sorted by attribute IDs for the same reasons as mentioned before. The fourth entry of each attribute block (maxrange -1 ) contains a pre-calculated reciprocal value of d max +1.

Since it is a constant we do not need to implement an expensive hardware divider saving resources. By using the reciprocal value we can do a rather fast multiplication with the attributes' absolute difference instead of doing a slow division (see also equ. (1)). Figure 5 shows the implementation-tree structure which is a hierarchical tree of three levels. Similar to figure 3 it contains a top level list including implementation-IDs and reference pointers to the corresponding implementation lists. Each implementation list contains blocks sorted by implementation ID with pointers referencing to lists of attribute/value pairs of each implementation. All partial lists are generated at design time creating one big block of linear concatenated lists.

Hardware Implementation

The hardware implementation of the retrieval unit was done by modeling its behavior in Matlab Stateflow at first. We developed some tools in Matlab for creating and exporting all needed data structures (implementation-tree, request list etc.) so that they can be easily used for testing purposes in Stateflow, VHDL and C. After testing and verifying of our Stateflow model we converted the behavioral model into synthesizable VHDL code by using a special conversion tool JVHDLgen [3]. This tool is still in beta state of development but it proved to work fine although we had to do some minor restrictions to our Stateflow model since not all features of Stateflow are currently supported. Additionally some manual code modifications were necessary for synthesizing the model onto Xilinx Virtex II 3000 FPGA using Xilinx ISE 6.2. Figure 6 gives an overview on the main parts of the implemented algorithm. The shown version is able to find the most similar implementation. The delivered results will be the ID and similarity value of the best matching implementation. The main components of the retrieval unit's data path are depicted in figure 7. It should be noted that this data path's schematic was derived from the Stateflow model as the generated VHDL code is less suitable for extracting control-and data path information. The processing bitwidth of all attribute values was defined at 16 bit. Our tests showed that this bitwidth is sufficient even for fixed point calculations without seriously losing accuracy. We have been able to show that we get the same retrieval results in high precision floating point Matlab simulation as we get from VDHL simulation using ModelSim. The hardware design takes 441 CLB slices, two 2x18bit hardware multipliers and can be operated at 75 MHz (see also table 2). A small amount of additional memory of about 4.5 kB is needed for storing the implementation-tree giving space for a full set of 15 function types containing 10 implementations * 10 attributes each, using 16 bit words for each entry (see table 3, reference pointers are included). Apart from the hardware implementation we also mapped the retrieval algorithm into a C program running on a Xilinx MicroBlaze soft-processor at 66 MHz. The software version which takes only 1984 bytes of opcode and 1208 bytes for variables proved to produce identical retrieval and similarity results for a selected set of test cases where we created different implementation-trees and requests. The same test cases were applied to the hardware implementation and we compared the performance results of both implementations. As result we have found that our hardware version is at 66 MHz about 8.5 times faster than the software solution.

Figure 6. Most similar retrieval algorithm

Table 3. Case-base memory consumption

Conclusions and Outlook

We have proved the feasibility of a hardware accelerated function-retrieval on QoS requirements based on methodologies from case-based reasoning theory. Although we adopted the CBR-retrieval and similarity determination steps for our purposes some might argue that the presented approach does not implement a complete CBR-cycle as shown in figure 2. Actually many practical CBR-implementations restrict to the retrieval step only and re-use the found solution without adaptation and assessment step, since a reasonable adaptation of the found solution is a very complex and time consuming process, which is not necessary in a retrieval of static implementations. Although the implementation-tree is currently a static structure we conceive dynamic update mechanisms of Case-Base-data structures and function repositories at run-time enabling for a self-learning system as new aspects of our future work. Our next step will be an extension for getting n most similar solutions from retrieval which offers the possibility for checking out the feasibility of different matching variants. Additionally we think about optimizations of the used implementation-tree structure and retrieval finite state automaton for getting a better speed-up. Furthermore a rather compacted attribute block representation could be used for loading IDs and values as blocks within one step speeding everything up at least by factor 2.

Figure 1

 1 Figure 1. Reconfigurable HW/SW System

Figure 2 .

 2 Figure 2. Case-based reasoning-cycle [1]

Figure

  Figure 3. Function r quest at case-base

Figure 4 .

 4 Figure 4. Request list and attribute list

Figure 5

 5 Figure 5. Implementation-tree structure

Figure 7 .

 7 Figure 7. Data-path -Most similar retrieval

Solved Case Suggested Solution Knowledge Solved Case Suggested Solution Knowledge Solved Case Suggested Solution Knowledge Case Base Case Base Learned Case Learned Case

		Problem Problem
	R e t a in	New Case New Case	R e t r ie v e	New
	Learned Case	Case Base	Retrieved Retrieved Case Case	Case
	Tested/ Repaired Case Confirmed Solution Confirmed Solution R is e Knowledge Solved Case Tested/ Repaired Tested/ Repaired Case Case	R e u s e
		Suggested
		Solution

Table 1 . Retrieval -similarity example

 1

	i	A Req_i	A CB_i	d( A Req_i , A CB_i ) d( A	d max d max	s i s i
	1 1	16 16	16 16	0 0	16-8=8 16-8=8	1 1
	3 3	1 1	2 2	1 1	2-0=2 2-0=2	0.66 0.66
	4 4	40 40	44 44	4 4	44-8=36 44-8=36	0.89 0.89
		Impl. ID= 1 : FPGA Impl. ID= 1 : FPGA	w j =1/3 w j =1/3	S global S global	0.85 0.85

Req_i , A CB_i ) A CB_i A Req_i i S global 44-8=36 2-0=2 16-8=8 d max 0.96 w j =1/3 Impl. ID= 2 : DSP 0.89 4 44 40 4 1 0 1 1 3 1 0 16 16 1 s i d( A Req_i , A CB_i ) A CB_i A Req_i i S global 44-8=36 2-0=2 16-8=8 d max 0.96 w j =1/3 Impl. ID= 2 : DSP 0.89 4 44 40 4 1 0 1 1 3 1 0 16 16 1 s i d( A Req_i , A CB_i ) A CB_i A Req_i i S global 44-8=36 2-0=2 16-8=8 d max

	1	16	8	8	0.11
	3	1	0	1	0.66
	4	40	22	18	0.51
	Impl. ID= 3 : GP-Proc	w j =1/3	0.43

s i d( A Req_i , A CB_i ) A CB_i A Req_i i S global 44-8=36 2-0=2 16-8=8 d max

	1	16	8	8	0.11
	3	1	0	1	0.66
	4	40	22	18	0.51
	Impl. ID= 3 GP-Proc	w j =1/3	0.43

s i d( A Req_i , A CB_i ) A CB_i A Req_i i best

Funktionstyp ID Attribut ID Attribut Wert Attribut Gewicht Listen Ende Attribut Gewicht w Attribut Wert Attribut ID Functiontype ID Attribute ID Attribute Value •End of List Attribute Weight w i Attribute Value Attribute ID Function Requirements Description -Pointer Attribute Weight w i List entries presorted by ID Funktionstyp ID Attribut ID Attribut Wert Attribut Gewicht Listen Ende Attribut Gewicht w Attribut Wert Attribut ID Functiontype ID Attribute ID Attribute Value •End of List Attribute Weight w i Attribute Value Attribute ID Function Requirements Description -Pointer Attribute Weight w i Funktionstyp ID Attribut ID Attribut Wert Attribut Gewicht Listen Ende Attribut Gewicht w Attribut Wert Attribut ID Functiontype ID Attribute ID Attribute Value •End of List Attribute Weight w i Attribute Value Attribute ID Function Requirements Description -Pointer Attribute Weight w i List entries presorted by ID List entries presorted by ID Attribut ID Lower Bound Upper Bound Attribut Max Lower Bound Upper Bound Listen Ende Attribut Max-Bereich Attribut ID Attribute ID Lower Bound Upper Bound Attribute Max Range -1 Lower Bound Upper Bound •End of List Attribute Max Range -1 Attribute ID Attributes Supplemental-Data Pointer List entries presorted by ID Attribut ID Lower Bound Upper Bound Attribut Max Lower Bound Upper Bound Listen Ende Attribut Max-Bereich Attribut ID Attribute ID Lower Bound Upper Bound Attribute Max Range -1 Lower Bound Upper Bound •End of List Attribute Max Range -1 Attribute ID Attributes Supplemental-Data Pointer List entries presorted by ID List entries presorted by ID Request list structure Attribute list structure

Extract function basic-type from request and look in case-base for corresponding entry Selection of next function implementation from sub-list, store ID of corresponding implementation from case-base Determine type and value of next attribute from request, get range constant d max from attribute-supplemental list Look in attribute list of implementation for a matching attribute entry and get its value

	attribute found		attribute not found
	i S	1	_ i C B max , i i d A A 1 d A		0 S 0 i i S
			i S S S w i S S S w	i i
					no
			Last attribute from
			request processed ?
				yes
			S > S Best ?
			Keep S and implementation ID
			Last implementation	no
			in list ?
				yes /
			deliver most similar
			implementation ID
	Resources: Xilinx Virtex II 3000
	CLB-Slices:			441 of 14336	3 %
	MULT18X18s:		2 of 96	2 %
	BRAMS(18Kbit):	2 of 96	2 %
	Max. Clock:				MHz

Table 2 . Synthesis results on XC2V3000 77 Max. Clock: BRAMS(18Kbit): MULT18X18s: CLB-Slices: Resources: Xilinx Virtex II 3000

 2

	441 of 14336	3 %
	2 of 96	2 %
	2 of 96	2 %
	77	MHz

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)