Evaluating Placement Algorithms for Run-Time Reconfigurable Systems

Dedra Eatmon and Clay Gloster
NC State University

Please send all correspondence to Clay Gloster 
Clay Gloster, Jr., Ph.D., P.E.
NC State University
Department of Electrical & Computer Engineering
Box 7914
Raleigh, NC 27695-7914
email:     gloster@eos.ncsu.edu
telephone: (919) 515-7348	
fax:       (919) 515-2285
Please note: An Open/Unclassified presentation is desired.

The field programmable gate array (FPGA) has become one of the most utilized 
configurable devices in the area of reconfigurable computing.  FPGAs have a 
large amount of flexibility and provide a high degree of parallel computing 
capability.  Since their introduction in the 1980's, these configurable logic 
devices have experienced a dramatic increase in programming capabilities and 
performance.  Both factors have been significant in the changing roles of 
configurable devices in custom-computing machines.  However, the improvements in 
capability and performance have not eliminated the issues related to efficient 
placement of applications on these devices.  

This paper presents a tool that evaluates placement algorithms for configurable 
logic devices.  Written in Java, the tool is a framework in which various 
placement algorithms can be executed and the performance and quality of each 
placement evaluated using a cost function. Based on devices that support 
relocatable hardware modules (RHMs), the tool places modules with user-specified 
placement algorithms and provides feedback that can be used for a comparative 
analysis.  The framework manages module mappings to the logic device that are 
both independent of each other and do not require pin-to-pin routing 
connections. Such a tool is valuable for the  identification of effective 
placement algorithms for real-time placement of RHMs in run-time reconfigurable 
systems.
 
The Dynamic REsource Allocation and Management (DREAM) framework, has been 
designed and developed to evaluate FPGA placement algorithms/heuristics.  A 
portion of the evaluation is based on a simplistic cost function that calculates 
the amount of contiguous unused space remaining on the device in two dimensions. 
In our experiments, we use an FPGA logic core generator to produce several 
rectangular RHMs. In addition to the rectangular RHMs produced by the logic core 
generation tool, our framework can handle arbitrary circuit profiles. Several 
scenarios consisting of approximately 500 insertions/deletions of both 
rectangular and non-rectangular RHMs are used as test data sets for placement.  
Two placement algorithms are presented to demonstrate the flexibility of the 
framework.  The first algorithm is an adaptation of a traditional best-fit 
algorithm that we call exhaustive search and the second is a random placement 
algorithm. Future work will involve the development of additional placement 
algorithms and the incorporation of placement issues that relate to  requests 
for central reconfigurable computing resources originating from a remote site.

The DREAM framework answers the call for a tool that is sorely needed to 
identify placement algorithms that can be effectively used for real-time 
placement.  In addition to providing results that can be used to benchmark the 
performance of placement algorithms in real-time on a configurable system, this 
tool also allows the end-user methods to store and load placements for future 
optimization. By taking full advantage of the partial and full dynamic 
reconfiguration capabilities of logic devices currently used in run-time 
reconfigurable systems, the goal of DREAM  is to minimize placement time while 
maximizing the utilization of configurable devices.