Clément Foucher
email: clement.foucher@unice.fr

Fabrice Muller
email: fabrice.muller@unice.fr

Alain Giulieri
email: alain.giulieri@unice.fr

Online Codesign on Reconfigurable Platform for Parallel Computing

Keywords: Parallelism, Reconfigurable computing, Hardware virtualization, Online codesign

Reconfigurable hardware offers new ways of accelerating computing by implementing hardware accelerators at run time. In this article, we present an approach allowing a hardware/software codesign of applications in which implementation can be chosen at run time depending on available resources. We propose a platform supporting this flow and describe its different implementations used to prove the feasibility of our approach. This platform allows the underlying hardware to be virtualized in order to have a generic architecture that can be used to run applications. Partial dynamic reconfiguration is used over Xilinx Virtex 5 boards to enhance reconfiguration capabilities.

Introduction

Computing-intensive structures traditionally rely on parallelism. Supercomputers, or High Performance Computers (HPCs), are massive grids of Processing Elements (PEs) linked together to compute distributed applications.

Over the past few years, reconfigurable hardware has been increasingly used as a way to enhance computing power. Indeed, with reconfigurable hardware, we can instantiate hardware accelerators specifically matching the application's needs. Bringing flexibility to previously static structures has removed a major obstacle to using hardware accelerators. But most current reconfigurable architectures introduce hardware as an extension of software applications [START_REF] El-Ghazawi | The promise of High-Performance Reconfigurable Computing[END_REF]. General applications are run on software PEs, which delegate some work to hardware units. Software dominance over hardware is a feature of pratically all systems because static hardware needs to be controlled dynamically depending on the application; a requirement that can only be met using software. But now that hardware is (almost) as flexible as software, we belive that the time has come to change this relationship. This paper describes a way to build applications in a hardware/software online codesign approach. With this approach, an application is split into various application kernels which can either be hardware, software or can even have both implementations. In that case, the implementation choice is made at runtime. Section 2 describes the current state of the art as regards intensive computing through parallelism and reconfigurable hardware. Section 3 goes on the describe our approach. After what, section 4 describes the platforms used to evaluate the validity of this approach. Finally, section 5 looks at future work to be completed.

Increasing computing power -overview of actual methods

Parallelism is a way of increasing computing power by using arrays of PEs instead of a single PE. Applications are split into kernels, which are subelements that can be computed independently. For completely independent kernels, doing so makes it possible to achieve a maximum computing speed gain, which is equal to the number of PEs. But actual application kernels communicate together, dramatically impacting this gain. This is why we have to proceed carefully to fully avail of the powers of a parallel computing platform. Moreover, the gain realized will depend to a great extent on our knowledge of the kernel's communication. For many years, parallelism was used only in the professional world, and with intensive computing applications. But, a few years ago, it began to spread to the personal computing world as a mean to keep increasing computing power. For a certain period, hardware had been used to speed up dedicated tasks. But hardware's static nature meant that it could not always be used since a specific, dedicated, electronic logic was required. Reconfigurable computing, with the ability to change logic circuit at runtime -and thus making it possible to map a hardware accelerator according to the needs of the application -has extended the range of applicable uses for hardware acceleration. Parallel design of applications requires taking into consideration many parameters such as communication between kernels, memory dispatching and resources conflicts. Dealing with such applications requires a rigorous modeling of the application to ensure correct management of these issues. Section 2.1 depicts the currently existing parallel architectures; section 2.2 describes the advances brought to parallel systems by reconfigurable architectures. Finally, section 2.3 presents models used to design these applications and languages used to implement them.

Parallel architectures

Parallel computing ranges from small multicore processors to large HPC grids containing thousands of PEs.

Multicore

Multicore chips, as well as multiprocessors systems, offer various PEs working in the same environment. Such systems are called Symmetric Mul-tiProcessing (SMP) platforms. Figure 1 shows a simple view of such systems, which allows for data to be exchanged between PEs through the shared memory or dedicated channels. Each PE can itself be a Single Instruction Multiple Data (SIMD) unit [START_REF] Cheema | Application-specific SIMD synthesis for reconfigurable architectures[END_REF], in which case the same instruction to be run on several data items at the same time. In the general case, a SIMD unit working on words of 2 n bits can process 2 p words of 2 n-p bits in a single instruction. Multicore chips can be homogeneous or heterogeneous. Homogeneous systems contain a number of implementations of the same PE, while heterogeneous systems contain different kinds of PEs specialized for specific treatments. One of the first commercial multicore chips was the Cell Broadband Engine (Cell BE) by IBM, Sony and Toshiba [START_REF] Hofstee | Power efficient processor architecture and the Cell processor[END_REF], a heterogeneous system. The Cell BE contains a power processor element, which is a 64-bit core, and eight synergistic processor elements, that are 128-bit SIMD units. The power processor element runs the main program and delegates work to the synergistic processor elements.

Manycore

Increasing the number of cores in a single system leads to architecturebased limitations as SMP is not relevant any more when reaching about a dozen cores [START_REF] Asanovic | The landscape of parallel computing research: a view from Berkeley[END_REF]. Indeed, managing concurrent memory accesses and communication between PEs becomes very tricky beyond this point. A new kind of architecture is then used when moving from multicore to what is called manycore [START_REF] Hill | Amdahl's law in the multicore era[END_REF][START_REF] Woo | Extending Amdahl's law for energy-efficient computing in the many-core era[END_REF]. Manycore architectures are built using the network paradigm, each core being an island linked to others through a Network on Chip (NoC) [START_REF] Benini | Networks on Chips: A new SoC paradigm[END_REF]. Interesting prototypes exists such as Intel's Single-chip Cloud Computer [START_REF] Howard | A 48-core IA-32 message-passing processor with DVFS in 45nm CMOS[END_REF][START_REF]SCC External Architecture Specification[END_REF], proposed as a research platform. It includes 24 nodes on the same chip, each node being a dual core IA-32 Pentium processor, and using message-passing to communicate between nodes. A NoC is in charge of internal communication, implementing the message-passing protocol at the hardware level. There are different levels of memory, including a shared one at the top. This is a complete processing system, bearing greater resemblance to a grid (or cloud) of computers than to a multicore processor. Another manycore-like architecture is mppSoC [START_REF] Marquet | Massively parallel processing on a chip[END_REF], reproducing the early HPCs' array topology on a chip. MppSoC uses a theoretical model in which an array control unit controls a 2-D array of PEs able to perform SIMD parallel computing. PEs communicate using two channels. First, MpNoC is a global NoC allowing communication between any two PEs in the design. Second, a local network, X-Net, allows local communication between a PE and its 8 neighbors. The Array Control Unit uses a modified instruction set architecture adding specific instructions for parallelism and communication.

Supercomputers

According to Oyanagi [START_REF] Oyanagi | Future of supercomputing[END_REF], "supercomputers are regarded as the computers which have an order of magnitude higher performance" than traditional computers. Main HPCs architectures gather nodes linked by a network or a bus, each node being a SMP system. Figure 2 presents a classical HPC system. The nodes communicate using message passing, with various protocols to send and receive data and control information. Such a system is said to be globally distributed, locally shared in terms of memory. Hager and Wellein [START_REF] Hager | Architecture and performance characteristics of modern High Performance Computers[END_REF] describe supercomputers architectures for communication and memory. They offer a well-structured analysis by explaining each architectural element and the reason for their presence. As computers evolved, dedicated hardware appeared to help the Central Processing Unit (CPU) with some specific tasks. Of particular note is the graphic card, which can include hardware codecs for widely used video standards. Graphic cards also include a specific execution unit called Graphical Processing Unit (GPU). GPUs are built as arrays of PEs with the ability to process the various elements to be rendered at the same time. While GPUs were designed to process graphical computations, their parallel nature means enhanced computing power for various kinds of applications. The present trend is to talk of Global Purpose GPUs (GPGPUs) to indicate a capacity to be used for a wider range of computations than just graphical. We can illustrate this trend by taking a look at the TOP 500, which ranks the most powerful supercomputers according to the results of the test high performance LINPACK [START_REF] Dongarra | The LINPACK benchmark: past, present and future[END_REF]. In the year 2010, the most powerful HPC was Jaguar, a farm of 37,376 six-core AMD Opteron CPUs. For the current year of 2011 however, the leader is the Tianhe-1A, a cluster of 14,336 six-core Intel Xeon, also including 7,168 nVidia GPGPUs, each one containing 448 CUDA Cores1 . The Open Computing Language (OpenCL) [START_REF]OpenCL official website[END_REF] offers an open development platform for designing GPGPUs solutions. OpenCL is designed by the Khronos Group, a non-profit organization aimed at maintaining open standards, such as the well-know OpenGL graphical application programming interface. OpenCL is a combination of a C-based dedicated language along with an application programming interface allowing computation on various resources such as CPUs and GPGPUs. OpenCL splits the computation kernels from the program management, allowing for the dispatching of various kernels to heterogeneous PEs. The TOP 500 ranking offers interesting insight into the current high levels of supercomputing. An interesting observation is made by Iushchenko [START_REF] Iushchenko | Measuring the performance of parallel computers with distributed memory[END_REF] about studies by Dongarra, which is one of the LINPACK test developer. "On the average, a computer that leads the 'Top-500' list in terms of performance takes the last place in it after 6-8 years. The capacity of a supercomputer that takes the last place in this list is compared with that of a personal computer after 8-10 years". If this observation remains true in the future, we can expect to have 2.57 petaflops (Tianhe-1A score at high performance LINPACK) in our personal computers in about 15-20 years from now.

Reconfigurable parallel architectures

Reconfigurable hardware relies on arrays of programmable logical elements linked by a configurable network. These components, such as Field Programmable Gate Arrays (FPGAs) allow the mapping of various complex logical elements such as digital signal processors, video decoders or processors.

Reconfigurable hardware

With the recent Partial Dynamic Reconfiguration (PDR) technology, one part of a reconfigurable device can be changed without affecting the other part. On a FPGA chip hosting a design containing multiple Intellectual Property blocks (IPs), this means that an IP can be changed while others are running. In this respect, the FPGA can be considered as an array of independent IPs. This new technology adds much more flexibility to FPGAbased hardware components by allowing dynamic IP changes during system life. Reconfigurable hardware allows integrating accelerators in systems easier than using dedicated hardwired resources. Indeed, integrating generic hardware resources can offset the cost of dedicated hardware as various accelerators can be integrated on demand. Moreover, implementing algorithms as hardware circuitry instead of software code can be useful in devices where energy matters. Actually, a slow-clocked hardware implementation of an algorithm can offer the same performance as a higher speed software implementation, with less energy consumption [START_REF] Kwan | FPGAs for improved energy efficiency in processor based systems[END_REF]. Thus, reconfigurable hardware can improve energy efficiency of CPU-and GPU-based systems [START_REF] Kestur | Blas comparison on fpga, cpu and gpu[END_REF].

Reconfiguration also comes at a cost, the overhead of the reconfiguration time, during which it is impossible to use an IP, and the energy cost of the reconfiguration itself. PDR avoids a complete FPGA reconfiguration and acts on smaller bitstreams, bringing an appreciable speed gain. For Birk and Fiksman [START_REF] Birk | Dynamic reconfiguration architectures for multicontext FPGAs[END_REF], the reconfigurable hardware capabilities are close to the software concept of dynamic libraries, with the capacity to be instantiated when needed, and even replicated if needed more than once at a time. Their approach to dynamic reconfiguration entails using multi-context FPGAs. In these architectures, reconfigurable elements contain one active configuration and one or more standby configurations. The standby configuration can be dynamically reconfigured while the active configuration is running. This allows an instant switch between active and standby configurations whenever needed, hiding the reconfiguration overhead. Clearly, this approach is resources-greedy since at any given moment, each reconfigurable element has an idle configuration monopolizing unused resources. Its use then becomes a tradeoff between wasting time and reducing the usable area of a device, depending on application priority. European project AEther [START_REF]AEther project website[END_REF] presented an architecture based upon networked reconfigurable components. Each component can communicate with its neighbors to form Self-Adaptive Network Elements (SANEs) [START_REF] Casas | A novel hardware architecture for self-adaptive systems[END_REF]. The SANEs communicate to form a platform able to run an application. In this structure, computation elements can be of various sizes by using more or less components linked together, making it possible to run kernels with different resources needs. This avoids wasting too many resources by using reconfigurable regions sizes matching the larger element needs. Work has been done on resources scheduling upon SANEs [START_REF] Muhammad | Dynamic and self adaptive resource management: aether operating environment[END_REF] as well as on simulation of the SANEs environment and scheduling strategies impact [START_REF] Khodary | On simulating operating environment decisions in a sane network[END_REF]. In reconfigurable systems, there are more bitstreams to store since a single reconfigurable area can support various IPs over time. Bitstream storage needs to be addressed as embedded systems have limited memory. Crenne presents a bitstream storage architecture similar to a cache stack, with various levels leading to various performances [START_REF] Crenne | End-to-end bitstreams repository hierarchy for FPGA partially reconfigurable systems[END_REF]. Level 1 (L1) is local storage in RAM, while L2 and L3 are stored over a network. L2 contains bitstreams stored over a local area network, while L3 supposes a wireless connection. Bitstreams are directly copied from the content of network packets to the Internal Configuration Access Port (ICAP) [START_REF]Partial Reconfiguration User Guide[END_REF][START_REF]Virtex-5 FPGA Configuration User Guide[END_REF], Xilinx's FPGAs internal reconfiguration IP. This avoids too much local storage while imposing penalties when a needed bitstream is not present in L1. Duhem et al. [START_REF] Duhem | FaRM: Fast reconfiguration manager for reducing reconfiguration time overhead on FPGA[END_REF] presents a superset of Xilinx's ICAP called Fast Reconfiguration Manager (FaRM). FaRM speeds up the reconfiguration process by implementing direct memory accesses to get bitstreams from local memory. This IP also implements bitstream compression in order to reduce needed storage and bitstream transfers overhead. The bitstream is dynamically uncompressed before being sent to the ICAP. The bitstream is temporarily stored in a local Block-RAM (BRAM)-based FIFO, allowing the data transfer to continue transfers while uncompressing the bitstream.

High performance reconfigurable computers

Lately, supercomputers have begun using reconfigurable hardware to accelerate specific kernels. In the past, hardware accelerators were hard-wired circuits to which the software could delegate some special jobs (e.g. graphical cards usually embedded a MPEG2 decoder chip). Due to the static nature of these elements however, it was difficult to use them in HPCs, since different applications have different requirements. Adding generic hardware brings a lot of flexibility by allowing computing-demanding applications to map needed IPs on reconfigurable areas, not requiring a specific hardwired hardware accelerator. An example of HPRC system is the Cray XD1 in which nodes are constituted by a dual AMD Opteron system in which a Xilinx Virtex II Pro or a Virtex 4 FPGA can be added. Communication between CPUs and FPGAs is done through a RapidArray fabric offering a 3.2 GB/s duplex channel. Gothandaraman et al. [START_REF] Gothandaraman | FPGA acceleration of a quantum monte carlo application[END_REF] use the Cray XD1 to identify the possible gain on executing Quantum Monte Carlo application on reconfigurable supercomputers. They compare an application's performances on this integrated platform to results conducted on a platform consisting in a dual Intel Xeon coupled to two Xilinx Virtex II Pro FPGAs using a 66 MHz PCI interface. Their results highlight that the bandwidth between the processors and the reconfigurable devices is a real bottleneck. HPRC systems integrate reconfigurable hardware jointly with software PEs in the nodes, or separated on dedicated nodes depending on the architec-ture [START_REF] El-Ghazawi | The promise of High-Performance Reconfigurable Computing[END_REF]. In both cases, the main application runs on software PEs. When reaching critical sections of codes for which hardware acceleration has been developed, a software PE books a reconfigurable PE, configures it with appropriate bitstream, then launches the run. This leads to the finding that the system is still mainly software, with dynamic hardware resources perceived as coprocessors used to accelerate specific kernels. In current HPRC systems, FPGAs are reconfigured atomically, not implementing PDR. First experimentations involving PDR on HPRCs systems were conducted by El-Araby et al. [START_REF] El-Araby | Exploiting partial runtime reconfiguration for High-Performance Reconfigurable Computing[END_REF] on the Cray XD1 system. They use the concept of Hardware Virtualization, the reconfigurable hardware being mapped to generic hardware like pages of a memory system. Their work shows the gain obtained by reconfiguring parts of the device instead of a monolithic bitstream at once.

Parallelism tools: models and languages

Building parallel applications requires adapted models to describe it and ways to program it. When computer science turned to parallelism, many programming tools already existed for sequential behaviors. Based on that, two approaches were taken: adapt existing tools, like programming languages C and Pascal, or create new tools specifically adapted to parallelism. ADA is one of the first programming language to manage parallelism by nature, dealing with processes, which are entities that can be run in parallel. But most of the applications already written also needed to be adapted to avail of parallel platforms. Most existing parallel applications are thus based on C or Pascal, with a superset layer adding parallelism features. OpenMP's [START_REF] Chandra | Parallel programming in OpenMP[END_REF][START_REF] Hoeflinger | The OpenMP memory model[END_REF] compiler directives allow communication through the shared memory. It is described as compiler pragmas added to a C or Pascal source code to indicate parallelism of applications. The compiler then includes thread creation and deletion in the application, resulting in a fork/join model. On most distributed systems, message-based communication relies on the Message Passing Interface (MPI) [START_REF] Gropp | A high-performance, portable implementation of the MPI message passing interface standard[END_REF][START_REF] Hempel | The emergence of the MPI message passing standard for parallel computing[END_REF], which defines a set of communication routines. MPI is widely used in the industry and seen as a standard. The routines defined by the interface allow various communication calls between two threads of more. The implementation of the different calls can take the underlying hardware into consideration to offer a low-level Quality of Service using resources at their best. Thus, there are various implementations of this interface, including proprietary ones specifically designed for each hardware platform, as well as open-source ones. MPI manages parallelism explicitly, requiring adding specific calls to send and receive functions to manage inter-thread communication. Conversely, OpenMP is implicit as the programmer describes which parts of the application should be run in parallel, the compiler taking care of the inducted communication. MPI is said to be a local view because developers describe the code that must be run on each node to form the application, while OpenMP offers a global view by describing the application that is distributed upon PEs. Figure 3 shows the difference in terms of application description. It describes a simple sum between two arrays, followed by a sum on the resulting array. The local view has to handle communication "manually", while the global view simply indicates that the operation has to be done in parallel. Note that the local view tools, such as MPI, also define reduction operation, so that gathering and then summing data can be done in a single call, unlike this example.

A is array of integers range 1 to 10 B is array of integers range 1 to 10 C is array of integers range 1 to 10 sum is integer Defining the architecture of a parallel application is a delicate operation and must be done carefully, since a single bottleneck can impact the whole system; the entiere application can end up getting blocked because of a resource starvation in a single part of the program. Worse, parallel management adds traps like deadlocks, definitely blocking an application if too few precautions are taken. Before implementing an application, we need to model it in order to gain information about potential constraints, such as data dispatching and communication between threads. Thanks to the model, we can enhance an application's parallel profile to optimize execution time, and prevent it from falling into a parallel pitfall. According to Skillicorn and Talia [START_REF] Skillicorn | Models and languages for parallel computation[END_REF], program-ming languages are models, since they allow applications to be represented no matter what the underlying hardware is. Models such as Unified Modeling Language (UML) [START_REF]Unified Modeling Language website[END_REF] allows for the implementing of an application by using design tools to translate virtual operations into actual languages. In terms of parallel models, UML offers an interesting profile called Modeling and Analysis of Real-time and Embedded systems (MARTE) [START_REF]UML profile for MARTE[END_REF]. MARTE addresses embedded systems containing both hardware and software resources, allowing us to describe their relationship. Architecture Analysis & Design Language (AADL) [1] is another modeling tool. It describes hardware resources such as PEs, devices and buses, as well as software elements that will use these resources, to describe the whole system. AADL has a graphical approach, and can be defined as an UML profile. SystemC [START_REF]SystemC website[END_REF] is also a major modelisation tool, providing us with a number of approaches from low-level cycle-accurate simulation to transaction-level modeling. It implements concurrency between processes, allowing simulation of parallel system natively. It is primarily used to make general high level verification, but many development tends to use it as a HDL description tool.

do parallel C <= A + B end do sum <= C[1] + C[2] + … + C[10] Global view A is integer B is integer local_sum is integer local_sum <= A + B if node number is 1 do C is

Our approach

Increasing computing power can be addressed in different ways. One possibility is to increase the speed and integration of components in the PEs. Another way is to increase the number of PEs. Finally, integrating dedicated hardware is also a possibility to speed up specific kernels.

Background and preliminary observations

In the past, the personal computer experience has been enhanced mainly by increasing integration while professional computing added parallelism to reach the upper echelons in terms of computing power. Recent years however have showed the limits of increasing single-treaded computation speeds, mainly because of leakage current and heat issues. Thus, personal computers turned to parallelism by introducing multicore chips in order to keep on increasing the levels of computing performance. Introducing multiple cores in former purely-sequential architectures exposed inherent flaws in legacy programs: their inability to use multiple PEs, and thus enjoy the full benefits of this rise in performances. Thanks to the use of multitask operating systems, there is still a possible gain on parallel architectures by running independent applications of the different PEs. While personal computing needs to learn from the professional experience in terms of parallelism, a new challenge in the quest to increase computing power has emerged. Reconfigurable computing allows applications to delegate jobs to hardware accelerators specifically matching the application's needs. But introducing this new capability in current architectures leads to the same problems as introducing parallelism in sequential architectures: the applications, and moreover the platforms, are not able to enjoy the benefits that could come from such a tool. There is a need for a new methodology to support reconfigurable hardware natively rather than as a speed-up tool for software codes. With a codesign methodology such as is used in Application-Specific Integrated Circuit (ASIC) design, we can dispatch application kernels upon hardware or software implementation. By considering hardware/software relationships prior to system building, we can optimize the implementation of kernel in the light of factors given as important in the application specifications, such as required performance, minimization of implementation cost, energy efficiency, etc. Such ASIC systems are specific to an application and are static, but even for reconfigurable systems, applying the ASIC methodology is not that simple; for example, if we later decide to change the kernel implementation, this could lead to expensive changes in the whole system if the kernel's communication with the system is specific to its software/hardware nature and has to be changed with it. Moreover, auto-adaptive systems have specific and highly unpredictable needs, changing with their environment. In some specific cases, this situation can lead to the exhaustion of reconfigurable hardware resources and/or processor time. This is why we propose a new approach involving hardware/software online codesign. Online codesign is a notion where some or all of the kernels have both software and hardware implementation, the one we use being chosen at execution time depending on available resources and process criticality.

Execution model

Our approach consists in viewing an application as a gathering of independent kernels communicating with each other. An application description is a list of kernels to run along with their input and outputs. Threads (running instances of kernels) are automatically linked when one's output data is the other's input data. The kernels' hardware or software nature is not considered when building the application. Independently of the application, kernel implementations are defined, possibly re-using existing IPs. More than a hardware/software issue, multiple hardware implementations can be defined for a single kernel, using different hardware resources. Then, executing the application is done by reading the sequence of kernels to run, then choosing an implementation for each kernel depending on available resources. This is a virtualization process in which the application knows the processes to run, but has no idea as to how they will be processed. This virtualization approach is somehow close to the OpenCL methodology. Indeed, OpenCL explicitly manages the software kernels execution on the PEs [START_REF] Thoman | Automatic OpenCL device characterization: Guiding optimized kernel design[END_REF]. Creating an OpenCL application consists of listing the kernels that can benefit from the execution on dedicated PEs present in the system, and explicitly map the kernels on these resources. The program then adopts a system view, managing the software kernels and allocating their execution to the hardware resources. OpenCL can manage any software resources in a system like CPUs, GPUs, or even particular resources like DSPs, Cell BE [START_REF] Ferrer | Optimizing the exploitation of multicore processors and gpus with OpenMP and OpenCL[END_REF], etc. But our flow differs in many points from OpenCL. First, our approach is built to enable the use of dynamic hardware on reconfigurable resources while OpenCL is designed for software PEs management. Another difference is that our methodology is not application-based, but rather kernel-based. OpenCL describes an application that, at some point, makes use of a kernel and maps it on a specific resource. In our approach, the application is only a set of kernels, with no precision on their implementations. Our kernelcentric view allows a kernel to be totally independent from the others, thus from the application itself. Figure 4 presents the general flow used to build an application and run it on a dedicated platform. Stage A presents the application description, starting with an application's specifications (step A.1), that must be split into various independent kernels (step A.2). Dependencies between kernels are identified (step A.3) in order to build the final application's description (step A.4). Stage B presents the implementation of the abstract application kernels (step B.1), which can be implemented for the application purpose or can re-use existing IPs and/or software parts (step B.2). On the hardware side, we use standard material such as FPGAs, on which a virtualization platform is built. This enables us to disregard the actual nature of the underlying hardware from the application point of view. Finally, on stage C, the application is run over the platform, and kernels are dynamically instantiated over hardware and software resources. Achieving independence from the implementation is only possible if access to the kernels is also virtualized. Different implementations of the same kernel require the same data and should provide the same results; it is how input data is furnished to the kernel, and outputs retrieved from the kernel, that changes. This is why each implementation of a kernel has a description of how to get and set data. Data is managed independently of the kernel's implementation, the matching get and set procedures being applied transparently. Finally, independence also requires that starting, stopping and suspending a kernel be automated, as well as a way of knowing if a kernel has finished processing. These automations are defined using action sets, which are sequences of actions to perform in a specific order. An action can be a read/write in a register or on a memory range, or a sequence of FIFO actions on a register. An other way to provide and get data is using pointers to memory. These are handled by booking a memory range and passing on its address and size to the IP using register actions. Specific actions are also defined such as masking and comparing data words; in this way, we can check that an IP has completed its work.

The application is described upon XML files containing the above structure.

The job descriptor lists the kernels to run and their data dependency. A kernel descriptor is needed for each kernel, listing the implementations and their related files. Related files are obviously the kernels binaries and/or bitstreams, but also parameters descriptors and thread access descriptors that are specific to each implementation. A parameter descriptor contains the action sets needed to provide and retrieve data to/from the kernel. A thread access descriptor contains the action sets needed to interact with a thread. By virtualizing the management of kernels, we can use the same input and output data format without needing to concern ourselves about the implementation of the end application, thus enhancing what we call online codesign.

Thanks to virtualization, an application described for our flow could work on any system containing reconfigurable resources if the kernels bitstreams and binaries are synthesized/compiled accordingly. To illustrate this, we proceeded by building supporting this flow. The purpose of these platforms is to prove the feasibility of our system by showing a working implementation.

Platforms

We called our general platform the Simple Parallel platfOrm for Reconfigurable Environment (SPORE). This platform adapts a simple HPC topology, with nodes composed of computing PEs and a communicationdedicated element, as in figure 5. Using our virtualization flow, the underlying hardware does not need to be taken into consideration, thus the nodes could be heterogeneous, plugging various kind of device together. SPORE is a theoretical platform, from which we developed two implementations. The first one, Software HPC Platform (SHP), is intended to evaluate the general architecture and check if HPC hierarchy can be applied to FPGAs boards. The second one, Hardware Stream Dynamic Platform (HSDP) will demonstrate that our method of hardware virtualization is actually applicable. This section describes these two platforms and their characteristics.

Software HPC Platform

Before introducing reconfigurable hardware and other elements of our approach, we first needed to make a basic test: was the HPC architecture easily implementable on our test material? This architecture was first presented in [START_REF] Foucher | Exploring FPGAs capability to host a HPC design[END_REF].

Overview

The worker PEs are called computing cells while the communication component is called a host cell. Intra-node communication is done through the shared memory while the host cell is responsible for handling inter-node communication through the Ethernet access. Computing cells do not need an OS since they will process a single task at once. We only need a small runtime program able to launch the process and to send results when finished. Figure 6 presents the implemented design from a software point of view, including the intra-node communication elements. We decided to use MPI for inter-node communication, as this is the standard communication tool in current architectures. Implementing OpenMP for intra-node use on that platform would have required re-writing a complete compiler, due to the fact that computing cells do not have an OS. Since this was not a viable solution for us, we preferred to use MPI for both inter-and intra-node communication, adding a proxy layer for intra-node communication. Calls between host cell and computing cells are handled by a generic interface which is called by the application-dependant proxy. A server is plugged to the network along with the nodes and is simply an entry point for launching the MPI application on the nodes. Xilinx ml507 development boards [49] contain a Virtex 5 fx70t FPGA [START_REF]Xilinx Virtex 5 family[END_REF], the system implemented upon this board. With this set of components, we can build a complete, nonvolatile system by using a CompactFlash card to host the filesystem. The PowerPC 440 is used as the core of the host cell, supporting a Linux kernel, while the computing cells been built using Xilinx's MicroBlazes softcore processors [START_REF]Microblaze processor reference guide[END_REF]. Enabling data and/or instruction cache requires two direct accesses to memory, while disabling both means that we can use a single access through the bus. On figure 7, the right-most computing cell is cached, while the other two are uncached. The Multi-Port Memory Controller (MPMC) allows up to eight accesses. One being used for the host cell, this allows three cached cells or seven uncached cells on the same board. While data communication between host cell and computing cells is made through the memory, the Mailbox components allow control communication. Mailboxes are composed of two FIFOs allowing bidirectional transfers between two buses. Table 1 presents the resources used by this implementation. The computing cells with cache use BRAMs as cache storage resources, doubling the total BRAM count. Moreover, the number of LUTs is increased by 15% as the cache management uses logic to be implemented. The host cell seems to be lighter that the computing cells, but the real resource cost is hidden by the use of the hardwired PowerPC. On the software side, we use a Linux implementation built on the kernel provided by Xilinx for use with its boards [START_REF]Xilinx open source resources[END_REF]. The filesystem is created using Buildroot [START_REF]Buildroot project website[END_REF], a simple tool providing the base libraries required to run the system. As said previously, MPI has open-source implementations. We chose the MPI CHameleon 2 (MPICH2) [START_REF]MPICH2 website[END_REF], which is a free implementation of the MPI2 protocol.

Platform evaluation

In order to evaluate the system, we needed an evaluation program representative of a HPC application. We chose a benchmark developed by NASA Advanced Supercomputing (NAS), the NAS Parallel Benchmark (NPB) Integer Sort (IS). NPB [START_REF] Bailey | The NAS Parallel Benchmarks[END_REF] is a set of tests used to benchmark parallel archi-tectures, and NPB IS is a simple bucket-based integer sort algorithm. The general performance of the benchmark is not the matter since MicroBlazes are small processors that are not computing-intensive. Nevertheless, running this application using different configurations highlights the impact of the various factors. NPB benches can be run using various classes, each class representing a different amount of data to match different HPC sizes. The possible classes for the IS bench are, in ascending order, S, W, A, B, C and D. We chose class A as a tradeoff between a minimum size correctly representing HPC applications and a maximum size that was reasonable given our limited number of boards. The computing cells can be configured to enable or disable the instruction cache, while the data cache is always disabled. Indeed, activating cache over data results in a general slowdown when executing this bench over our platform. This is due to the frequent accesses to different arrays, forcing frequent cache line flushes and loads. Note that this is specific to this configuration, and different sizes of cache, or running different applications on this platform, could result in a speedup when data cache is activated. But due to the limited amount of BRAM, cache size cannot be increased. BRAM resources use is already almost at maximum level: cached systems use 84.5% of the BRAMs with one host and three computing cells. Some techniques can be used to optimize memory access. At the software level, a method is to optimize memory access patterns in order to enhance cache usage [START_REF] Kjeldsberg | Guidance of loop ordering for reduced memory usage in signal processing applications[END_REF][START_REF] Catthoor | How to solve the current memory access and data transfer bottlenecks: at the processor architecture or at the compiler level[END_REF]. This technique implies to change the code taking in consideration the underlying memory and cache layout. On the hardware side, cache coherency can be maintained between the various processors, avoiding flush operations. As this first platform is only intended to be a general behavior evaluation, we did not integrate such advanced tricks. The evaluation was conducted upon a dozen ml507 boards linked by an Ethernet network, and using different configurations of the application distribution. Not all configurations were however allowed since some required too many boards or too much memory. The application running time was measured, with details of time spent on computation and on communication between MPI jobs. The criteria were: instruction cache enabled or not; total number of jobs; number of jobs per board. We presented some representative results concerning computation and communication times on figures 8 to 10. Figure 8 shows a dramatic increase of communication time when we put more jobs on the same board. This is because of the shared memory, a single access at once. Since the application is single program multiple data, all processes on the same boards need to access the memory at the same time, leading to congestion. Figure 9 shows the correct general behavior, namely computation time drops according to the total number of jobs on each board. On this figure, we see that the number of jobs per board only has little impact on computation time, curves for 1 and 2 jobs per board being quite layered. Nevertheless, passing to 4 jobs per board begins to have a sensitive impact due to concurrent memory accesses. stable, the number of jobs per board leads to an increase of total time. Memory is thus a bottleneck issue, obliging us to reconsider the SMP characteristic of our platform. Nevertheless, the other characteristics of our platform would not seem to be a problem as we were able to reproduce a HPC-like behavior with multiple nodes. These results allowed us to continue our investigations by building a second platform, even if the memory model needs to be reexamined.

Hardware Stream Dynamic Platform

The second platform focuses on the hardware virtualization flow, thus it integrates dynamic reconfiguration.

Overview

In order to simplify implementation, we only use hardware computing cells in that implementation. As a consequence, and since IPs used to evaluate the platform do not make use of MPI, this platform does not need to implement it. Nevertheless, MPI will be present in the final version of the SPORE platform. HSDP is thus not HPC-oriented; rather it is datafloworiented. Figure 11 presents the HSDP design. To handle dynamic hardware, we use a software reconfiguration manager able to send orders to a FaRM IP through a Linux driver. Bitstreams are stored, along with other application elements, on the data server. The storage manager transfers it to the local storage when needed, in order to make it accessible by FaRM. SHP's MPI server is replaced by a scheduler dispatching work amongst nodes, where a local scheduler dispatches work amongst cells. To replace the shared memory-only communication used in SHP, we allow communication to be done directly through a bus. Implementation is done, as for SHP, on Xilinx's ml507 development boards. Computing cells are split in two parts: a static one and a dynamic one. The dynamic part, called kernel host, is configured using partial bitstreams. The static part, namely the kernel controller, is responsible for isolating the bus from the kernel host during the reconfiguration process. It also manages the reset signal for threads. In any other case, it is invisible to the bus, giving direct access to the IPs' registers. The local scheduler is the entry point of the virtualization process for each node. It receives a job descriptor which will be parsed, extracting information about kernels. Then, the local scheduler advises the storage manager to grab needed files such as kernel descriptors, bitstreams, etc. The storage manager is in charge of the "cache" management for bitstreams. Since the bitstream repository has a limited storage capacity, a least recently used policy is deployed when there is a need to store a new bitstream. Resources occupation for node components is given in table 2. Note that the kernel host's resources are always monopolized, even if there is no IP mapped on, or if the IP has a smaller actual occupation.

Platform evaluation

As this implementation is dataflow-oriented, we chose a test application in which a kernel's output is another kernel's input, rather than a communication-oriented evaluation program such as NPB IS. The flow was evaluated using an AES encoding/decoding chain. The application has two parallel branches, each one encoding an input file, then decoding it. We write a job descriptor containing this application. IP behavior is controlled by writing a thread access descriptor, and the characteristics of each IP are given using a kernel descriptor. All these files are written in XML using a specific syntax. As an example, the listing in figure 12 details the thread access descriptor containing the action sets used to access both encoder and decoder IPs. Some actions are constant writes to IP registers, while the cypher key is a reference to an input file. This makes it possible to change this key without changing the thread access descriptor, which is supposed to depend only on the kernel implementation.

<Thread_access_descriptor ID="12" Name="AES encoder and decoder thread access descriptor"> <Context> <Restore> <!--Connect IP--> <Action Type="Register" Direction="Write" Data_constant="01" Offset="0" Size="4"/> <!--Enable reset--> <Action Type="Register" Direction="Write" Data_constant="03" Offset="0" Size="4"/> <!--Diable reset--> <Action Type="Register" Direction="Write" Data_constant="01" Offset="0" Size="4"/> <!--Cypher key--> <Action Type="Memory" Direction="Write" Data_reference="0" Offset="36" Size="4" Count="4"/> <!--Disable premption--> <Action Type="Register" Direction="Write" Data_constant="00" Offset="4" Size="4"/> </Restore> </Context> <Behavior> <Start> <Action Type="Register" Direction="Write" Data_constant="01" Offset="20" Size="4"/> </Start> </Behavior> </Thread_access_descriptor> Implementing the AES encoder involves using 2430 LUTs (63.3% of the kernel host capacity), while the AES decoder uses 2975 LUTs (77.5%). The architecture layout can be seen on figure 13, with two computing cells and the PowerPC being the host cell base. Computing cell 0 is shown implementing an AES encoder while computing cell 1 hosts an AES decoder. Chain output data is recovered, as well as intermediate data at the encoder output, in order to check the accuracy of the process. The test has been conducted using a dual-cell and a single-cell platform, leading to different congestions in reconfiguration. On the dual-cell platform, both branches of the program can run independently. On the single-cell platform, only one thread can run at once, the second branch being in a waiting state until cell is clear. General results reveal that our design flow is correct since the obtained results are in line with expectations. The application has been tested using compressed and uncompressed bitstreams, and the reconfiguration times have been measured and are given in table 3. HSDP implementation of SPORE is still being evaluated, using longer chains which are more representative of actual applications, in order to identify potential flaws. Time measures concerning IP run time and reconfiguration overhead will also be conducted. A third implementation of SPORE is planned in order to implement the complete flow, namely integrating both the reconfigurable behavior and the MPI capability. Given that it would be final platform, all elements of our theory should be present, including the hybrid nature of cells and kernel implementations, which can either be hardware or software. This platform would then gather the features of the previous two platforms, but with improvements to resolve the shortcomings revealed by these versions. This platform, whose current name is Hybrid HPRC & Stream Platform (HHSP), will adopt the manycore topology, managing communication through a NoC in order to overcome the SMP issues.

Conclusion

In this paper, we explained the notion of hardware/software online codesign. With online codesign, we no longer need to consider the actual implementation of the kernels when at the design stage. Moreover, with this approach, we handle hardware and software implementation in one single movement. Thus, some or all of the kernels can have both implementations, the final one being chosen at run time. This paper also presented a virtualization mechanism used to manage these kernels automatically in relation with their actual implementation, which may not be known before running. This mechanism defines ways to deal with a kernel implementation such as starting, setting parameters, etc. using lists of actions to be carried out sequentially on the kernel. Finally, we presented the SPORE platform and its various implementations, intended to be a demonstrator for our implementation flow. The various current and future SPORE implementations give us an opportunity to improve design flow with a real implementation highlighting potential issues we didn't seen at design time. This global flow allows execution of auto-adaptive applications, in which the used and unused resources are unpredictable and depends on the environment. This behavior, where hardware or software nature of an application kernels can be decided at runtime, allows more flexibility than the offline codesign used in most of the current platforms. As an example, a HPRC application, where hardware routines are statically defined, can run on only one kind of platform, and would need to be adjusted before it could be run on another platform. In this case, our virtualization flow, thanks to which we can disregard the underlying structure when designing the application, would allow us to run a given application on any platform able to implement this flow.

Bibliography

Figure 1 :

 1 Figure 1: SMP platform.

Figure 2 :

 2 Figure 2: HPC nodal architecture.

Figure 3 :

 3 Figure 3: Global view versus local view in application description.

Figure 4 :

 4 Figure 4: General flow used to build an application.

Figure 5 :

 5 Figure 5: View of the system distributed upon various nodes.

Figure 6 :

 6 Figure 6: Software stack.

Figure 7 :

 7 Figure 7: Implementation of SHP upon Xilinx ml507 board.

Figure 8 :

 8 Figure 8: Communication time versus number of jobs on each board.

Figure 10 Figure 9 :

 109 Figure 9: Computing time versus the total number of boards.

Figure 10 :

 10 Figure 10: Total time versus number of jobs per board.

Figure 11 :

 11 Figure 11: View of HSDP system.

Figure 12 :

 12 Figure 12: Thread access descriptor for AES IPs.

Figure 13 :

 13 Figure 13: Virtex 5 fx70t layout of HSDP implementation.

Table 1 :

 1 Resources used by the SHP components (percentages expressed on Virtex 5 fx70t global resources).

	Resource	Uncached	Cached	Host cell
	occupation computing cell computing cell
	LUTs	3,870 (8.6%)	4,441 (9.9%)	2,559 (5.7%)
	BRAMs	17 (11.5%)	34 (23.0%)	23 (15.5%)
	DSP48Es	6 (4.7%)	6 (4.7%)	0 (0.0%)

Table 2 :

 2 Resources used by the HSDP components (percentages expressed on Virtex 5 fx70t global resources).

	Resource	Host cell	Kernel	Kernel host
	occupation		controller
	LUTs	12,477 (27.9%) 290 (0.6%) 3,840 (8.6%)
	BRAMs	42 (28.4%)	0 (0.0%)	0 (0.0%)
	DSP48Es	13 (10.0%)	0 (0.0%)	0 (0.0%)

Table 3 :

 3 Reconfiguration times expressed in clock cycles.

	Compression Encoder Decoder
	Enabled	79,633	91,232
	Disabled	103,295 103,287

The Compute Unified Device Architecture (CUDA)[START_REF] Nickolls | Scalable parallel programming with CUDA[END_REF] is a GPGPU architecture developped by nVidia. CUDA Cores is the name of the parallel PEs in this architecture.