An iterative method for algorithms implementation on a limited dynamically reconfigurable hardware

Journal of Computer Science, May, 2006 by Abdellatif. Mtibaa, Abdessalem. Ben Abdelali, Lotfi. Boussaid, Elbey. Bourennane

Abstract: In this study we propose a framework and a combined temporal partitioning and design space exploration method for run time reconfigurable processors. Our objective is to help designers to implement an algorithm in limited FPGA area resources while respecting the execution time constraint. The algorithm to be implemented is represented by a task graph with different implementation alternatives (design points) for each task. We study the effect of hardware resources limitation in the choice of the algorithm implementation design point. The proposed method is based on an heuristic technique which consists on combining temporal partitioning and task design points selection to obtain solutions that satisfy the imposed constraints.

Key words: Reconfigurable hardware, run time reconfiguration, time partitioning, design points

INTRODUCTION

With today's deep sub-micron technology, the state-of-the-art FPGA have exceeded 10 million system gates, allowing for multimillion gates FPGAs operating at speeds surpassing 400 MHz. Many designs, which previously could only achieve speed and cost of density goals in ASICs, are converting to much more flexible and productive reprogrammable solutions. The major developments in FPGA logic density, speed, packaging etc. have made implementing a system of processor/s, IP blocks, and user logic in an FPGA (System On a Programmable Chip: SOPC) a possibility. This technology is currently being used for the acceleration of a wide variety of applications on a large number of systems. It has evolved so much that the real-time aspect is not the only objective of the designer [1]. It has allowed the association of the flexibility and the specificity. Several applications can be realized by specialized architectures by simply configuring the FPGAs each time the FPGA-based board is supplied.

With the advent of new device architectures and new software tools, the interest in Run-Time Reconfiguration (RTR) or dynamically reconfiguration logic has increased. This concept has introduced several advantages. It helps the designer to optimize his implementation by increasing the functional density of the FPGA coprocessor. It offers the possibility of sharing in time the available resources in the FPGA between the different tasks of an application. This can be accomplished by using either total or partial dynamic reconfiguration. This later allows the configuration of a part of an FPGA design to change while the circuit is running. The AT40K40 FPGA family of ATMEL allows the reconfiguration of any area of the component by modifying the SRAM configuration contents [1]. Actually, Xilinx offers this technology for his more recent families such as the Virtex-II Pro FPGAs [2-4].

In this study we propose a method for efficient management of a given FPGA area resources for a particular algorithm by exploiting the dynamic reconfiguration for possible use in SOPC. The proposed method consists in combining temporal partitioning techniques and design points selection of the different tasks constituting the algorithm. We aim to resolve the temporal partitioning problem for a given application while considering the characteristic of multi design point of each algorithm task. This can be very useful for possibly variable resources available on the FPGA when adding a new service or an update [5]. By using different alternatives for the algorithm tasks we increase the chance to meet the application constraints. In fact choosing the best design point for each task may not necessarily result in the best overall design. This depends on the architectural constraints and the dependency constraints among the tasks [6].

State of the ART in the dynamic reconfiguration domain: In literature a lot of interest was given to the dynamic reconfiguration and the opportunities given by the new FPGA technologies. Works in this field aim To reduce the difficulty in managing the dynamically reconfigured application and to provide a reliable implementation by developing a set of tools and associated methodologies addressing many issues related to the Dynamic Reconfiguration such as: Automatic partitioning of a conventional design, Specification of the dynamic constraints, Verification of the dynamic implementation through dynamic simulations, Automatic generation of the configuration controller, etc.

In [7-9] the FSS (FPGA Support System) environment which is developed at Manchester University is represented. It facilitates the execution of hardware-based tasks on a dynamically reconfigurable FPGA. It supports the placement, execution and removal of blocks on the FPGA. A framework for the Design and Implementation of Dynamically and Partially Reconfigurable Systems "PaDReH" is proposed in [10,11]. It is presented with a design flow including partitioning, scheduling and validation. Papers [12,13] are related to the integrated design system called SPARCS (Synthesis and Partitioning for Adaptive Reconfigurable Computing Systems) which is developed in the ECECS Department at Cincinnati University. It aims to automatically partitioning and synthesizing designs for reconfigurable boards with multiple field-programmable devices (FPGA). The system contains a temporal partitioning tool, a spatial partitioning tool, and a high-level synthesis tool. In [14] a run-time reconfiguration system for FPGA computing resources is proposed; System behaviour and architecture are represented as a problem graph, and an architecture graph, respectively. The Model-Integrated Development Environment for Adaptive Computing (MIDE) project of Vanderbilt University [15] has as goal to develop high-level system design tools for implementing dynamically reconfigurable systems using adaptive computing technology. It is aimed at embedded systems of weapons like missile guiding systems. It uses DSP processors coupled to Virtex Xilinx FPGAs. The Berkeley Reconfigurable Architectures, Software, and Systems (BRASS) project of Berkeley University has proposed SCORE (Stream Computations for Reconfigurable Execution) [16], a computation model based on the organization of reconfigurable systems around the virtualization of three main hardware concepts: paged reconfigurable hardware, page communication through the use of streams, and storage. The Dynamically Reconfigurable Hardware Research at Bournemouth University [17,18] has proposed the DYNASTY tool, which is a generic CAD framework for research in the area of reconfigurable system design techniques and methodologies.