Partial Rearrangements of Spaceshared FPGAs


  Partial Rearrangements of Space.pdf (Size: 118.16 KB / Downloads: 0)


Introduction

Dynamically recongurable eldprogrammable gate arrays FPGAs
are com
posed of uncommitted logic cells and routing resources whose functions and
interconnections are determined by userdened conguration data stored in
static RAM This memory can be modied at runtime thereby allowing the
conguration for some part of the chip to be altered while other circuits operate
normally
The ability to recongure parts of a chip while it is operating allows func
tional components
tasks to be swapped in and out of the chip as needed thereby
reducing required chip area at the cost of some reconguration overhead control
and memory Embedded applications that have successfully exploited this fea
ture to conserve hardware include an image processing system a recongurable
crossbar switch and a postscript driver Successful designs for cryptographic
applications video communications and neural computing attest to the suit
ability of the architecture for high performance arraybased computations


The techniques

Partial rearrangement proceeds in two steps The rst step identies a rear
rangement of the tasks executing on the FPGA that frees sucient space for the
waiting task and the second schedules the movements of tasks so as to minimize
the delays to executing tasks The schedule for each feasible rearrangement is
evaluated for the maximum delay to the executing tasks and the time needed
to complete the schedule The problem of identifying the best rearrangement is
thus linked by feedback to the problem of scheduling the rearrangement
The following assumptions are made Tasks are assumed to be independent
and to be contained within orthogonally aligned nonoverlapping rectangular
subarrays of the FPGA Interdependent subtasks are assumed to be conned
to the tasks bounding box The time to load or congure a task is assumed to
be proportional to its area


Identifying feasible rearrangements

The problem of deciding whether or not a waiting task can be accommodated
on an FPGA is NPcomplete  Heuristic solutions are therefore sought In the
following two solutions which we call local repacking and ordered compaction
are presented


Scheduling task rearrangements

Since the time to reload an individual task is proportional to its area the choice
of tasks to move xes the time needed to complete the rearrangement We as
sume a task may continue executing until it is suspended prior to moving The
task is then resumed as soon as it has been reloaded If its destination is not free
when it is moved the tasks initially occupying the destination are immediately
suspended and removed In this work we distinguish between the minimumpos
sible cost of moving a task and the actual cost of moving it The minimum cost
is the time needed to save and reload the task which is unavoidable


Performance assessment
For an FPGA of width W and height H with m  maxfWHg and n exe
cuting tasks the local repacking heuristic requires O mnlog n
time to check
for the existence of a feasible rearrangement Ordered compaction on the other
hand needs
time Local repacking requires logn
time to produce a
schedule whereas an ordered compaction can be scheduled in O n
time