Dynamic Reconfiguration to Support Concurrent Applications.
AbstractThis paper describes the development of a dynamically reconfigurable system that can support multiple applications running concurrently. A dynamically reconfigurable system allows hardware reconfiguration while part of the reconfigurable hardware is busy computing. An FPGA resource manager (RM) is developed to allocate and de-allocate FPGA resources and to preload FPGA configuration files. For each individual application, different tasks that require FPGA resources are represented as a flow graph which is made available to the RM so as to enable efficient resource management and preloading. The performance of using the RM to support several applications is summarized. The impact of supporting concurrency and preloading in reducing application execution time is demonstrated.
Introduction
Adaptive Computing Systems (ACS) have been shown
to outperform general-purpose systems for some applications
because of their abilities in adapting hardware resources
to the application requirements[1], [8], [9], [13],
[16]. The technology has been demonstrated for a few special
purpose applications which have been tediously hand-
coded. These systems also have tremendous promise for
accelerating more conventional applications such as domain
specific visual development environments (Khoros,
MATLAB, WiT) and web browsers (Netscape, Internet
which dynamically invoke submodules or plug-ins
for image and data processing. Programming a device
to support all of the possible submodules an application
may invoke is not usually feasible due to the large number
of submodules and the finite amount of hardware re-
sources. However, an ACS may support reconfiguration of
some hardware resources while some other programmable
hardware is busy computing. Such a system is referred to
as a dynamically reconfigurable system. A dynamically re-configurable
system can configure the hardware on demand
to support the requirements of interactive programs such
as MATLAB and web browsers.
One way to implement a dynamically reconfigurable ACS
is to incorporate a large number of SRAM-based Field Programmable
Gate Array (FPGA) chips on a co-processing
board which is used in conjunction with a traditional pro-
cessor. However, in such a system there is a need to provide
an operating system like interface for the programmable
hardware to hide the architectural details of the coproces-
sor, to manage reconfiguration of the hardware during application
execution, and to fairly allocate FPGA resources
The authors are with the Department of Computer Science and
Engineering, Wright State University, Dayton, Ohio 45435, U.S.A.
among multiple processes.
Fig. 1. The dynamic reconfiguration system
This paper describes the system software development of
a dynamically reconfigurable system that can support multiple
applications running concurrently. A block diagram
illustrating such a system is shown in Fig. 1 where each application
consists of a program to be executed on the host
machine and a flow graph representing the portion of the
application to be executed on the FPGA resources. The
host program is responsible for starting the execution of
graph nodes through the resource manager (RM). With the
information of multiple flow graphs, one for each applica-
tion, the RM allocates and de-allocates FPGA resources so
that new nodes may be loaded into the system while other
nodes are being executed. In addition, a speculative strategy
is adopted by the RM in the "pre-loading" of FPGA
configuration files to reduce and hide the reconfiguration
overhead and to improve performance. The FPGA architecture
is modular in the sense that the FPGA resources
consist of a number of hardware units and each graph node
uses an integer number of hardware units. Note that multiple
copies of the same application can be executed at the
same time. The system has the following technical advantages

ffl Compared to static reconfiguration schemes, which do
not reconfigure the hardware during the execution of
an application, the system can accommodate more ap-
plications, typically those that require more FPGA
resources than what is available and their usage of
FPGA resources can be satisfied once spread out over
time. This is particularly true when the loading of
some FPGA implementations is based on execution
conditions. The system may also reduce the computation
time for an individual application. Since all of
the required FPGA resources need not be loaded at
once, a larger portion of the application computation
can be mapped to FPGAs.
ffl Compared to other dynamic reconfiguration schemes
that statically determine how to reuse the FPGA resources
[1], [2], the system allocates FPGA resources
at run time via a RM that relieves application developers
from the management of FPGA resources. Due
to use of the RM and its speculative loading policy,
multiple applications may share the FPGA resources
effectively, very much analogous to a virtual memory
system. The RAGE project [3] is similar to our own,
but emphasizes partial reconfiguration. It does not
support pre-loading of configurations.
Section 2 of this paper describes the development environment
of the project. Section 3 shows the design and the
implementation of the RM. Several applications are used
for the testing of the RM. Those applications, the testing
procedure, and the results are summarized in Section 4.
Section 5 compares the system to similar software in an
operating system. Section 6 concludes the paper.
II. Development Environment
A. Hardware Platform
Fig. 2. G900 Architecture
The reconfigurable computing platform used in this
project is a 180 MHz Pentium-pro personal computer hosting
a G900 FPGA board which is a PCI bus based board
manufactured by Giga Operations Corporation (GigaOps).
The board has a modular design, making it suitable for resource
sharing among applications. This design consists
of eight computing modules (XMODs) where each XMOD
contains two XC4020E FPGA chips, 2 MB DRAM, and
Fig. 2). Note that a maximum of sixteen
XMODs can be configured in one G900 board. The
XMODs are connected together by 128 wires, called the
XBUS. Among those 128 wires, 21 of them are used to
support a custom bus protocol, called HBUS, which defines
the pins and timing of signals used for the host (or more
specifically, the PPGA) to FPGA interface. The XBUS
also contains six 16-bit busses that provide inter-XMOD
connectivity.
There are two special purpose onboard FPGAs that are
not part of any XMOD. They are the PPGA and the
CPGA. The PPGA (Xilinx XC4013E-2) controls communication
between the host computer and the XMODS (Fig.
2), by acting as the PCI bus interface to the board. The
CPGA (Xilinx XC5210-5) implements clock generation,
runtime configuration and power up functions. While the
FPGAs can run at clock rates up to 66Mhz, the G900 board
and host interface is currently limited to 16Mhz.
B. Design Environment
The G900 board ships with a developer's kit which includes
XLINK-OS, GOCOLIB, XLINKLIB and XL [11],
[17].
ffl XLINK-OS permits the host program to execute hardware
designs by using standard C function calls and to
map variables that exist in the FPGAs into the host
program's address space (memory mapped variables).
The FPGAs can be reconfigured with the configuration
the host program requires.
ffl Two software libraries, GOCOLIB and XLINKLIB,
are provided in the developer's kit. GOCOLIB provides
low-level routines to interact with the module
FPGAs, monitor CPUs and PPGA etc. XLINKLIB
contains higher level routines for interacting with the
board. Both XLINKLIB and GOCOLIB need to be
linked into every XLINK-OS generated application.
ffl The XL language allows the specification of FPGA operations
and is loosely based on C syntax with many
keywords the same as C. It provides control of the
features available in Xilinx FPGAs. There are the
standard C operators plus a clock operator (:) which
is used in program sequencing. All XL statements
between two clock operators are executed during the
same clock cycle.
Microsoft NT is used as the operating system. The design
process begins with three source files which the user
must create.
1. The source code for the FPGA design written in either
XL or VHDL.
2. A file describing the host to FPGA interface. It declares
memory mapped variables and the functions the
host calls to execute FPGA designs.
3. The application program that resides and executes on
the host computer. It must call functions to initialize,
load and execute user FPGA designs in the XMODs.
The first two files are input into the XL compiler to produce
a Xilinx netlist file. That netlist is used by the Xilinx
tools to automatically map the design into an FPGA .bit
file that contains the FPGA configuration. In addition,
a C header file is generated which can be included in the
host program to control the executions of FPGA designs
on the G900 board. A more detailed description of the
development environment is given in [12].
III. Design and Implementation
To provide the dynamic reconfiguration capability and to
support concurrent applications, an XMOD RM and a set
of library functions have been designed and implemented.
The system is diagrammed in Fig. 3. With the XMOD as
the basic resource unit, the RM allocates and de-allocates
reconfigurable computing resources both on-demand and
speculatively. A set of library functions is provided so that
application developers can pass information from an application
to the RM without worrying about the details of the
inter-process communications or the details of G900 board
control. In this section, the application scenario of the system
is first described. A detailed design is then presented
along with the implementation status. Some discussion of
design issues follows.
Fig. 3. Overview of Resource Manager
A. Application Scenario
In the following paragraphs we describe the scenario for
applications executing with the RM. Both the application
development scenario and the application execution scenario
with the proposed system are given.
Application Development
An application is first analyzed or profiled so to determine
the computations that can be assigned to FPGAs or
XMODs. Those computations are mapped to XMODs by
creating the design.lnk file and going through the development
process described in the previous section to generate
a design.bit file that can be downloaded into the XMODs.
Remaining parts of the application are assigned to the host
program, which also provides data and controls the execution
of computations on the XMOD. The computations
mapped to XMODs are represented as a flow graph which
is passed to the RM when the application starts executing.
An application flow graph is a weighted graph where each
node represents XMOD computation and the weighted
edges represent the control flow of the host program.
The computational granularity of graph nodes may differ
greatly and each node requires either a fixed number
of XMODs or a range of numbers of XMODs. For exam-
ple, a node can be either for a simple integer addition that
requires one XMOD or for a complicated 2-dimensional
discrete cosine transform that can use from one to eight
XMODs depending on the desired performance. An example
edge weighting is shown in Fig. 4. After the execution
of graph node A, the next candidate node can be either
node B, C, or D, depending on a condition evaluated in the
host program. Three weighted edges go out of node A and
the weight of each edge represents the estimated probability
of the destination node being executed given that node
A is being executed. The edge weights are used by the RM
to pre-load FPGA configuration files. Higher weights lead
to a higher chance of pre-loading and zero weight indicates
no need for pre-loading. The edge weights are assumed to
be constants during the application execution in this paper
even though the removing of this assumption may potentially
lead to better performance.
Fig. 4. A flow chart example
The fundamental assumption of the flow graph is that
the computational granularity of graph nodes may differ
greatly and may only require a portion of the available
FPGA resources. It is therefore not efficient to execute a
graph node on an FPGA system one at a time. Instead
multiple nodes, not necessarily from the same application,
should be executed concurrently and new nodes may be
loaded into the system while other nodes are being executed

Application Execution
During the execution of an application, the RM runs as
a background process on the host machine. Each application
provides a flow graph and the corresponding FPGA
configuration files to the RM. The RM loads or pre-loads
FPGA implementations during the host program execu-
tion. The pre-loading implements a speculative strategy
that overlaps XMOD reconfiguration with computation on
other XMODs such that the reconfiguration latency is reduced
or completely hidden. Because the edges in a flow
graph are used only for the pre-loading of FPGA configuration
files, an edge missing in a flow graph does not influence
the correctness of the computation. It does, however, influence
the execution performance.
It is assumed that applications are developed in a way
that executing one graph node at a time is sufficient,
though not necessary, to guarantee the completion of individual
applications. With such applications, the system
will be able to prevent deadlock.
A set of library functions has been developed to simplify
the application development. The library functions
support the passing of a flow graph, the demand loading
request, the node release request, the board release request,
and some XMOD I/O capabilities. When a library function
is called from within an application, some information
is passed to or retrieved from the RM through inter-process
socket communication.
Initially, the application provides the flow graph, along
with the complete pathnames of FPGA configuration files
used for each node, to the RM. The RM speculatively loads
these configuration files, if free XMODs are available; to reduce
and hide the overhead associated with reconfiguration
of FPGAs during run-time. When the application needs
to do the computation mapped to FPGAs, it requests the
RM to load the required bit file in an XMOD. It then waits
till the RM responds with the number of the XMOD that
has been assigned to the application. If the bit file has
been speculatively preloaded then the application does not
have to wait for loading of the configuration file and gets
the XMOD number of the assigned XMOD immediately.
However, if the node has not been pre-loaded or there are
available then the application waits until
an XMOD becomes available and is loaded as requested.
After an XMOD is allocated and loaded, the application
packs the input data for computation into an array
and sends them to the G900 board. Once the input data
has been written to the XMOD, the application initiates
computation. On completion of the computation, the function
mapped to the FPGA should be designed to interrupt
the RM, which in turn will inform the application. Results
are retrieved by the application. If the computation
is complete for the node represented in the flow graph, the
XMOD is released; otherwise the input, execute and result
steps are repeated. When the application is done with
all the computations that have been mapped to FPGAs
then it informs the RM, which will no longer speculate any
nodes from the application's flow graph and will release
any XMODs pre-loaded for the application.
B. Resource Manager Design
The RM is implemented as a multi-threaded applica-
tion. An overview of the design is shown in Fig. 3. The
main thread of RM is the first thread to be created and is
the parent thread for the other threads. It first initializes
the G900 board, then spawns the loader, interrupt handler
and scheduler threads. It also sets up a server socket for
incoming connection requests from applications and waits
for requests. A new application service thread is created for
each requesting application, which then interacts with the
application on behalf of the RM. The main thread loops
back to listen for new requests. Communication among
the different threads of the RM is accomplished through
events, mutexes, shared variables and shared memory.
The application service thread establishes a stream
socket connection with the its client application and services
4its requests. It receives the application flow graph
and puts it into the shared memory and notifies the sched-
uler. Depending on the type of request sent from the appli-
cation, the application service thread responds in different
ways. There are six types of requests that can be sent from
the application.
ffl Load Graph Node: Request the allocation of XMODs
for a flow graph node and load FPGA configuration
files to one or more XMODs. If the XMODs have been
assigned and pre-loaded with the configuration files for
that node then the XMOD numbers are returned to
the application immediately. If, however, no XMODs
have been assigned then the application service thread
places a demand request for the XMODs with the
scheduler. When the XMODs get assigned and loaded
with the required files, it returns the XMOD numbers
to the application.
ffl Input Data: On receiving the input data array, the application
service thread writes the value of each memory
mapped input variable at its specified offset within
the XMOD.
ffl Result Data: The application thread retrieves the result
data from the memory mapped variables on the
XMODs and returns this data to the host program.
ffl Execute Function: The application service thread
starts execution of a specific function on the XMODs.
and waits till the interrupt handler indicates the occurrence
of an interrupt on one or more of the assigned
XMODs. It acknowledges the interrupt(s) and then
informs the client application. The interrupt(s) may
indicate completion of computation or some intermediate
stage. The service thread waits for the next request
from the application which might be reinitiation
of computation or collection of result data.
ffl Release XMOD: The service thread de-allocates all of
the XMODs associated with a specific flow graph node.
ffl Release Flow Graph: The service thread will discard
the application's flow graph, inform the scheduler that
the application flow graph is no longer valid, and then
terminate.
When an application executes an FPGA function, it normally
blocks until the function is completed. The completion
of an FPGA function sends an interrupt from an
XMOD to the interrupt handler thread of the RM. The
thread checks which XMODs have generated an interrupt,
since more than one XMOD could be interrupting at a
time. It then informs the corresponding application service
thread about the interrupt. Once all the interrupts have
been acknowledged by their respective application service
threads, the interrupt handler enables further interrupts
and loops back to wait till another interrupt occurs. For
each graph node, an application developer needs to either
implement an interrupt request circuit in FPGAs or let the
host program wait for a pre-specified amount of time for
the function to complete. The latter approach works only
if the function completion time can be known in advance
or can be determined in a well formulated way.
The scheduler thread which allocates XMODs either on-demand
or speculatively normally sits idle until being "trig-
gered" by three different types of events from an application
service thread: (1) a request for demand loading, (2)
the de-allocation of XMODs due to the release of a graph
node, and (3) the receiving of a new flow graph. Depending
on the type of event, its scheduling parameters and availability
of resources, the scheduler either assigns an XMOD
to the loader thread for loading or loops back to wait for
another event to occur.
The scheduling policy accepts three parameters that can
be specified as arguments to the RM while invoking it.
These parameters determine how aggressively the scheduler
speculatively pre-loads graph nodes. They are defined as
follows.
ffl MAX SPECULATE: Maximum number of immediate
successor nodes from currently executing node in the
flow graph that can be speculatively loaded
ffl THRESHOLD: Minimum edge weight probability for
speculative preloading of the successor node
ffl FREE XMODS: Minimum number of XMODs that
should not be preloaded and should be kept aside for
demand loading requests
The scheduling policy has three sections based on the
events that can trigger the scheduler. Each of these sections
is separately explained below:
I. Demand Loading:
ffl If the node requested for demand loading has been
preloaded or is being preloaded then the number of
the assigned XMOD is returned to the requesting application
service thread.
ffl If the requested node has not been or is not currently
being preloaded then a free XMOD is searched for and
assigned to it for loading. If no free XMOD is available
then any XMOD assigned to the application service
thread for some other node is searched for and
assigned to it. If no XMOD has been assigned to the
application service thread then an XMOD that has
been preloaded or is being speculatively loaded is pre-empted
and assigned.
ffl If all XMODs are executing, then the demand request
is queued up in a demand queue and the requesting
application service thread is suspended. It is woken
up when its demand request is serviced and an XMOD
is assigned.
ffl Once an XMOD has been assigned to the requesting
application service thread, its bit file is scheduled for
loading and the XMOD number is given to the application
service thread which waits till the loading is
completed before passing the XMOD number to the
client application.
ffl Irrespective of the type of event triggering the sched-
uler, if there are any demand loading requests pending
in the demand queue then they are given highest pri-
ority. New demand requests get queued at the end
of the demand queue. Preloading for new or existing
applications is done only if free XMODs are available
after all the demand requests have been serviced.
II. Arrival of New Application Flow
ffl While the number of free XMODs is higher than
FREE XMODS, if a new application flow graph ar-
rives, node 0 of the flow graph is preloaded on a free
XMOD. All new flow graphs are serviced before speculating
existing application flow graphs.
ffl The threshold weight probability for preloading is not
considered while preloading node 0 for a new graph
under the assumption that the application will always
start execution of the flow graph from node 0.
III. Releasing of An XMOD:
ffl While the number of free XMODs is higher than
FREE XMODS, one immediate successor node of the
currently executing node in a flow graph is speculated
till the MAX SPECULATE limit is reached for the
currently executing node in a flow graph. If this limit
has been reached, the flow graph is skipped.
ffl For a node to be speculatively loaded its edge weight
probability, which is calculated as a fraction of combined
edge weights of all out going edges from the
current node, should be higher than THRESHOLD.
ffl If the node to be speculated is detected to have been
executed before on a XMOD, in case of loops, then
it is checked if the configuration file is still loaded on
the XMOD. If yes, it is simply marked as preloaded;
otherwise the node is loaded on a free XMOD, if its
edge weight probability is higher than THRESHOLD.
ffl The speculation of flow graphs is done in a circular
fashion and continues while the scheduler has not come
back to the same application flow graph that it started
with, in the present scheduling cycle.
Scheduling begins from the flow graph following the
last flow graph scheduled in the previous cycle.
Fig. 5. XMOD state diagram
In order to efficiently allocate XMOD resources under
the speculative loading environment, the RM maintains the
state of each XMOD as shown in Fig. 5. If an XMOD
is pre-loaded but not in use yet, it may be de-allocated
when there is another request that cannot be satisfied. If
an XMOD is loaded on-demand, it cannot be de-allocated
until it is released.
Since loading of a configuration bit file is slow and needs
to be done serially on the G900 board, actual loading of bit
files is done by the loader thread. This allows the scheduler
to provide faster response to demand requests and other
scheduling events. The scheduler queues bit files to be
loaded in two queues maintained in the shared memory,
demand queue and speculation queue. The loader thread
serially loads the bit files queued by the scheduler on their
assigned XMODs. Bit files in the demand queue are given
priority over bit files in the speculation queue. On completion
of loading, the application service thread that is
waiting for an XMOD is signaled.
C. More Design Issues
The current design and implementation of the RM supports
multiple concurrent applications with pre-loading.
Several design issues complicate the RM and some have
not yet been addressed. These issues are described as follows

1. Direct XMOD Data Access
The standard mechanism for an application to load data
to XMODs or to unload data from XMODs is to use a library
function that requires the copying of data between
the application and the RM. For applications with frequent
data access or large quantities of Data, a more efficient implementation
that allows individual applications to access
those XMODs directly without going through the RM is
available.
2. Inter-graph-node Constraints
Some resources on the G900 board other than the
XMODs may be shared by different flow graph nodes. For
example the X bus can be used for inter-XMOD commu-
nication. If a graph node uses multiple XMODs and some
wires from the X bus, such resource requirements should
be specified and provided to the RM. Currently none of
the test applications in this paper use the X bus for inter-
XMOD communication and the current RM does not examine
such constraints.
3. Optimal Resource Allocation
For an application flow graph node there is a trade-off
between the resulting performance and the number of
XMODs used. It is expected for most graph nodes that
more XMODs do not lead to linear speedup. Therefore
when a range of XMOD numbers is specified for a node,
the corresponding performance figure for each number of
XMODs can be specified so that the RM may use the information
to optimally allocate resources at run time.
IV. Performance Results
Two main applications were used to test the system op-
eration. They are an MPEG-2 encoder program, and an
application based on an NP-complete satisfiability problem
in which we synthesized a flow graph with four nodes, each
node exhaustively solving the satisfiability problem for a
different logic formula. The two applications are briefly
described below.
1. MPEG-2 Encoder
MPEG-2 is a standard for digital video and audio com-
pression. The MPEG2 encoder that is available from
MPEG Software Simulation Group in source code format
was profiled with the Visual C++ Profiler [4]. Two time-consuming
functions are the full search( ) and the dist1( )
functions that handle the motion estimation of the MPEG-
encoding algorithm. The part of those two functions
that handles forward matching and backward matching
have been mapped to XMODs and implemented. The
resulting flow graph for the application has only one graph
node. That flow graph node can use one to eight XMODs
and all the XMODs use exactly the same FPGA design. A
more detailed description of the design can be found in [5].
The design was first tested without using the RM (i.e.,
with static reconfiguration) and the results show that, even
though more XMODs do improve the performance, the last
few XMODs do not have as much benefits as the first few
XMODs. Although not supported yet, the performance figures
in the future can be provided to the resource manager
to improve resource utilization and overall performance.
2. Satisfiability
The satisfiability problem is the problem of deciding
if a formula in conjunctive normal form is satisfied by
some truth assignment [15]. For example, the following
4-variable formula is in conjunctive normal form and it can
be satisfied when x1=true, x2=false, and x3=false. The
formula contains three clauses that are ANDed together.
Historically the satisfiability problem was the first decision
problem shown to be NP-complete. The satisfiability
problem is convenient for testing the RM as different formulae
can be tested using the same FPGA design by simply
initializing the design with different values. This allows
control over the amount of FPGA computation time. A
simple FPGA design to exhaustively solve the problem is
shown in Fig. 6. Note that the FPGA design was not intended
as an accelerator even though the design was faster
than the Pentium host. FPGA designs that are meant to
accelerate the satisfiability problem can be found in [18]
and [14].
Fig. 6. Satisfiability FPGA design
The FPGA design in Fig. 6 implements a deterministic
solution to the satisfiability problem by checking every
truth assignment. It works as follows. A formula in conjunctive
normal form that contains at most (n+1) clauses
is represented as two matrices of binary values where each
clause is represented as two binary vectors, A1[ ] and A2[
Each A1[ ] bit indicates if a variable is in a clause and
each A2[ ] bit indicates if a variable is negated or not.
Those two matrices are initialized by the host program.
Each truth assignment is represented as a binary vector,
h, stored in an up counter which starts from zero. For
each truth assignment, the formula is evaluated by going
through the clauses one by one. The host is interrupted
when either the formula is satisfied or all the truth assignments
have been exhausted. When the formula is satisfied,
the host can read the truth assignment, i.e., the h value,
that satisfies the formula. This h value is important in the
verification of the system operation. The FPGA design fits
in one FPGA chip and therefore one single XMOD.
Based on the FPGA design, an application was artificially
synthesized. The application, called the multiple-
satisfiability, contains four graph nodes in its flow graph
where each graph node is for the satisfiability evaluation of
a formula. Four formula were pseudo-randomly produced
and used in the application. Because those formula are
fixed and the specific conditions used in the host program
to determine the control flow, it is known which nodes get
evaluated and in what order, if the computation is correct.
The setup was purposely made to test the speculative loading
performance. Note that we pretend that all four graph
nodes use different FPGA configuration files to better represent
real applications even though in reality the same file
is used. Because of this assumption, the execution of a new
graph node requires the re-loading of the configuration file.
A. Simulation Results
The satisfiability problem with different numbers of
nodes and different node granularity and the MPEG encoder
were used for examining system performance. All
readings were taken as an average of three independent
runs. At first, timing for system operations such as G900
board initialization and bit file loading was done to quantify
the overheads of using our development system. It was
found that the board initialization takes about 2.34 seconds
while the loading of a configuration file takes about
seconds.
Each test application was first run without using the RM
and then using the RM to find out the overheads of using
the RM. When an application does not use the RM it needs
to initialize the G900 board and map it into its address
space. As a result applications cannot run concurrently
without using the RM. When the RM is used the board
is initialized only once when it starts. Thus board initialization
time was not counted when the test applications
were run using the RM. Note that when the application is
not using RM it does not have a flow graph but generates
interrupts to indicate end of FPGA computation.
roblem with High
Granularity Nodes
An application with four nodes, each a satisfiability problem
having FPGA computation times in the range of 1.9
sec to 4 sec was developed. These node granularities were
much higher than the FPGA configuration time of 0.35
sec. One, four, eight and twelve copies of the application
were run sequentially without the RM and both sequentially
and concurrently with RM using no speculative pre-
loading. The results obtained are summarized in Fig. 7.
Fig. 7. High granularity satisfiability execution times
For a single application, it took 14.1 sec to complete
without using the RM and 13.5 sec when run through the
Resource Manager. Ideally, since the board initialization
time was not counted in the second case it should have been
2.34 sec less but due to the overheads of packing/unpacking
of data and communicating with Resource Manager it was
only 0.6 sec less. Thus the overhead time of using RM was
1.74 sec for this application.
When the application was run four times sequentially
without Resource Manager it took 56.06 sec to complete
versus 54.27 sec with Resource Manager. But when four
copies of the application were used concurrently using the
RM it took just 14.87 sec to complete, speeding up the execution
by a factor of 3.8 against sequential execution without
RM. Since loading of bit files needs to be done sequentially
even when the applications are running concurrently,
of the 14.87 sec total execution time approximately 5.6 sec
(= 4 \Theta 4 \Theta 0:35) was spent loading the FPGAs. However,
an FPGA on an XMOD in the G900 board can be loaded
while FPGAs on other XMODs are executing. Thus the
PCI bus is shared between FPGA loading and data load-
ing/unloading for other FPGAs, which results in longer
FPGA configuration time depending on the dynamic condition
of the board. The overlap in loading and execution
of FPGAs and concurrent execution on different FPGAs
results in the reduced total time.
When eight copies of the application were run on the
G900 board concurrently through the RM it took 18.17
sec to complete as compared to 111.26 sec for sequential
execution without the RM and 108.87 sec with the RM.
Since one FPGA on all the eight XMODs on the G900
board are used in parallel a speedup by a factor of 6.1 is
achieved over sequential execution without RM, which uses
only one FPGA on an XMOD at a time.
With twelve copies of the application running concurrently
using RM, a speedup by a factor of 8.2 is obtained.
Since the number of applications is more than the number
of FPGA resources, some applications need to wait till
FPGAs become free in the demand queue, before obtaining
FPGA resources for computation.
roblem with Low
Granularity Nodes
The satisfiability problem used in test1 was initialized
with different formulae to get four nodes with computation
times between 8 msec and 26 msec. This was much
lower than 350 msec required for loading an FPGA on G900
board with its bit file. It means that much of the application
execution time would be spent loading the FPGAs
rather than performing computation on FPGAs. The timings
for one, four, eight and twelve copies of the application
were obtained as in test one. The results are shown in Fig.
8.
Fig. 8. Low granularity satisfiability execution times
The speedup obtained by running four copies of the application
concurrently through the RM is just 2.1, with
8 copies it is 2.31 and with 12 copies it is 2.6. The low
speedup factor is because there was less parallelism in the
application execution on FPGAs since most of the time
was spent in sequentially loading the FPGA configurations.
Thus the overhead of communicating with the G900 board
through PCI bus and some hardware constraints on the
G900, which results in high FPGA configuration time, dictate
the minimum node granularity for hiding latency and
obtaining impressive speedup for applications running concurrently

A test similar to tests 1 and 2 was done with two MPEG
encoders. Each MPEG encoder processes 27 frames of images
and uses a single XMOD. The motion estimation part
of the MPEG encoding is performed on the XMOD. It requires
more frequent and larger amounts of data transfer
than the satisfiability problem. For each image frame that
is used as a reference frame, the whole image frame is sent
at once from the host to the XMOD. For the other frames,
an image block of 16 \Theta 16 pixels is sent only after the previous
block has been processed by the XMOD.
Fig. 9. MPEG encoder timings
The timings obtained by running the encoders sequentially
and concurrently are shown in Fig. 9. When a single
encoder was run without using the RM it took 45.35 sec
to process the 27 frames whereas through the RM it took
44.85 sec due to the saving of board initialization time.
When two encoders were run in parallel using the RM they
ran 1.4 times faster than two encoders executing serially
without the RM, which required 91.29 sec to complete the
processing. The speed up is not very high due to the large
amount of data transfer taking place between the FPGA
board and host, but the concurrent use of MPEG encoders
is very useful for image processing applications.
with Speculative P reloading
To verify the effect of speculative pre-loading of FPGAs,
based on the flow graphs given to the RM by the appli-
cations, four copies of the satisfiability problem used in
test 1 running concurrently were re-evaluated. The effect
of varying the different scheduling parameters on the total
execution time of the applications was also obtained. Since
there are eight XMODs on G900 board and preloading is
done on free XMODs, the number of applications used for
testing was limited to four.
Fig. 10. Flow graph for satisfiability with high granularity nodes
The flow graph used for the satisfiability problem in
this test is shown in Fig. 10. The edge weights are arranged
such that node 1 will be preloaded after node 0 then
node 2 and then node 3. This is the actual execution sequence
of the application. The application execution times
were obtained as a function of the scheduling parameters
MAX SPECULATE and FREE XMODS while THRESHOLD
was held constant and as a function of THRESHOLD
and MAX SPECULATE, while FREE XMODS was kept
constant at zero.
Results with THRESHOLD constant
The execution times obtained as a function of
FREE XMODS and MAX SPECULATE are shown in Fig.
11. THRESHOLD was held constant at 0.3 for these re-
sults, which meant that all the nodes in the flow graph
shown in Fig. 10, could get preloaded. It can be concluded
from Fig. 11, that the speculative preloading of FPGA
configurations does help hide the configuration overhead
which results in lower overall execution time. The lowest
execution time is obtained when the number of speculated
nodes is highest. However, as the number of free XMODs
for demand loading increases the overall execution time increases
due to reduced number of speculated nodes.
Fig. 11. Execution times for four satisfiability problems w.r.t.
Results with FREE XMODS constant
For the results in Fig. 12, FREE XMODS was held constant
at zero so that no XMOD was kept aside for demand
loading requests. A THRESHOLD value of 0.5 meant that
only nodes 1 and 2 could be preloaded. With THRESHOLD
equal to 0.6 only node 1 could be preloaded with node
2 and node 3 being demand loaded. From the different values
of execution time in Fig. 12, it is again confirmed that
with reduced number of speculated nodes the overall execution
time increases.
Fig. 12. Execution times for four satisfiability problems w.r.t.
THRESHOLD
Fig. 13. Timing diagram for four high granularity satisfiability
problems (MAX
Fig. 13 shows the timing distribution for a single run of
four copies of High Granularity Satisfiability problems running
concurrently. In the figure, the loading of bit files and
execution of the nodes of the four applications are overlapped
as expected which results in the reduced execution
time.
In summary, for the four High Granularity satisfiability
application, aggressive preloading was advantageous. The
best performance was obtained when THRESHOLD was
0.3, MAX SPECULATE was equal to 2, FREE XMODS
was 0 and was 17% faster than without any speculative
loading of nodes.
roblem with
optimized F low Graph
To study the effect of a flow graph being provided by
the application that did not accurately represent the execution
flow, the flow graph shown in Fig. 10 was modified
to the flow graph shown in Fig. 14. According to
the edge weights, node 2 gets preloaded after node 0 and
then node 1 gets preloaded depending upon THRESHOLD
and MAX SPECULATE values. From node 1, node 3 gets
preloaded before node 2 and even though execution is complete
after node 3 is executed, the flow graph indicates that
node 1 or node 0 may be executed after node 3.
Fig. 14. Incorrect flow graph for satisfiability
Fig. 15. Timing diagram for four high granularity satisfiability
problems (MAX
This incorrect representation of the application execution
in its flow graph, which could also be due to some
condition evaluation differing from the usual case, results
in higher number of preemption of nodes and thus increases
the overall execution time. The timing values obtained as a
function of MAX SPECULATE are shown in Fig. 15. The
THRESHOLD value was kept constant at 0.3, which meant
that all successors from each node could get preloaded if
there were free XMODs. FREE XMODS was zero, thus
allowing as much preloading as possible.
As can be seen in Fig. 15, the gains obtained by speculative
loading are reduced considerably when the flow graph
representation is inaccurate. However, the execution time
is still lower than without any speculation for this test ap-
plication. It is the responsibility of the application developer
to provide as accurate a flow graph as possible unless
the dynamic conditions of the program can not be predicted
accurately. In which case, a lower speedup factor by
using the RM should be acceptable.
V. Comparison to Other Types of Resource
Management
The way that FPGA resources are managed in this paper
in some regard is similar to what is in a virtual memory
system that uses pre-paging with the following two major
differences.
ffl First, while pre-paging can only be used for processes
that were previously swapped out (and not applicable
to new processes), the pre-loading of FPGA configurations
can be applied to new processes because of the
availability of the application flow graphs. Given the
relatively coarse granularity of graph nodes, providing
an application flow graph is arguably very feasible for
an application developer, especially since the FPGA
design process is typically lengthy and tedious.
ffl Second, while a paged virtual memory system is truly
modular in that all the pages are treated the same,
the FPGA resources may not be really modular. For
example, the X bus on G900 can be used to simultaneously
support several groups of inter-XMOD communication
as long as the usage of X bus pins is disjoint
among different groups. The result is that the execution
of one application graph node on XMODs may
prevent the execution of another graph node. The requirement
of such shared resources by each application
graph node should be indicated in the flow graph and
sent to the resource manager. Note that this is not
supported by the current resource manager. As another
example, the FPGA chips on a board may have
different I/O capabilities.
Since the FPGA resources are mainly used for computing
instead of data storage, the RM is in a sense similar
to the processor scheduler in a multi-processing operating
system. However, because of the assumption of data dependency
and conditionals in an application flow graph,
deterministic scheduling techniques as summarized in [6]
cannot be applied to the RM. Instead techniques such as
the one in [7] that is based on the availability of run-time
profile at compile-time are more applicable. Such techniques
can be used to help produce application flow graphs
which were always manually generated in this paper.
VI. Conclusions
A dynamic reconfiguration system that can support concurrent
applications has been designed, implemented, and
tested on a PC with a G900 FPGA board. Compared to
static reconfiguration schemes, the proposed system can accommodate
more applications and potentially reduce computation
9times for individual applications. Compared to
other dynamic reconfiguration schemes, the proposed system
allocates FPGA resources at run time via a resource
manager (RM) that relieves application developers from
the management of FPGA resources. The RM can pre-load
FPGA configurations by utilizing its knowledge of application
flow graphs. Simulation results show that, even though
there is overhead associated with using the resource man-
ager, the concurrency supported by the system can drastically
speedup application execution. As programs such as
MATLAB use libraries of functions to improve programmer
productivity, one advantage of the proposed dynamic
reconfiguration system is that it can support a library of
FPGA functions, say, one for a 2-D convolution, one for a
histogram equalization, and so on. With the system there
is no need to squeeze all of the FPGA functions used by
a program into the hardware resources at the same time.
Such an environment would allow programmers to enjoy
the performance benefits of the adaptive computing technology
without worrying about the FPGA design details
and would accelerate the adoption of the technology.
Future research is necessary to port the RM to other
FPGA boards that may not be as modular as the G900
board. In that case, handling the asymmetry in hardware
resource units is a very challenging problem. Another issue
in dynamic reconfiguration is to design a similar RM for
systems that support partial reconfiguration. The "virtual
hardware manager" as developed in the RAGE project [3]
can probably be integrated with the resource manager in
this paper so that not only concurrent applications are supported
but also the FPGA function density are improved
with partial reconfiguration.
In [10], several models of DPGA program execution are
presented. One of them is "on demand usage" which is
similar to the proposed system. The paper did not pursue
the model but it claimed "Although it may seem a
rather futuristic scenario, there are good reasons for believing
that in the fields of multimedia, communications,
databases and cryptography at least, the characteristics of
the applications themselves are likely to demand this sort
of highly flexible execution environment."

Acknowledgments

This research is supported by DARPA under Air Force
contract number F33615-97-1-1148, an Ohio State investment
fund, and an Ohio State research challenge grant.
Xilinx Inc. donated an FPGA design tool and FPGA chips
on XMODs.



--R

"Run-Time Reconfiguration: A Method for Enhancing the Functional Density of SRAM-based FPGAs,"
"Designing A Partially Re-configured System,"
"A Dynamic Reconfiguration Run-Time System,"
MPEG Software Simulation Group at: http://www.
"Accelerating MPEG-2 Encoder Utilizing Reconfigurable Computing"
"Deterministic Processor Scheduling,"
"Compile-Time Scheduling of Dynamic Constructs in Dataflow Program Graphs,"
"Real-Time Signal Preprocessor Trade-off Study,"
"Using MORRPH in an Industrial Machine Vision System,"
"Reconfigurable Processors,"
"A Resource Manager for Configurable Computing Systems"
"Configurable Computing Solutions for Automatic Target Recognition,"
"Dynamic Circuit Generation for Solving Specific Problem Instances of Boolean Satisfiability,"
"Languages and Machines"
"Sequencing Run-Time Re-configured Hardware with Software,"

"Accelerating Boolean Satisfiability with Configurable Hardware,"
--TR

--CTR
Klaus Danne, Distributed arithmetic FPGA design with online scalable size and performance, Proceedings of the 17th symposium on Integrated circuits and system design, September 07-11, 2004, Pernambuco, Brazil
Ahmed A. El Farag , Hatem M. El-Boghdadi , Samir I. Shaheen, Improving utilization of reconfigurable resources using two-dimensional compaction, The Journal of Supercomputing, v.42 n.2, p.235-250, November  2007
Jack Jean , Xuejun Liang , Brian Drozd , Karen Tomko , Yan Wang, Automatic Target Recognition with Dynamic Reconfiguration, Journal of VLSI Signal Processing Systems, v.25 n.1, p.39-53, May 2000
Christoph Steiger , Herbert Walder , Marco Platzner, Operating Systems for Reconfigurable Embedded Platforms: Online Scheduling of Real-Time Tasks, IEEE Transactions on Computers, v.53 n.11, p.1393-1407, November 2004
Klaus Danne , Marco Platzner, An EDF schedulability test for periodic tasks on reconfigurable hardware devices, ACM SIGPLAN Notices, v.41 n.7, July 2006
David Kearney , Mark Jasiunas, Using simulated partial dynamic run-time reconfiguration to share embedded FPGA compute and power resources across a swarm of unpiloted airborne vehicles, EURASIP Journal on Embedded Systems, v.2007 n.1, p.8-8, January 2007
Katherine Compton , Scott Hauck, Reconfigurable computing: a survey of systems and software, ACM Computing Surveys (CSUR), v.34 n.2, p.171-210, June 2002
reconfiguration;field programmable gate array FPGA;scheduling;resource management;configurable computing