| Department
of Information Systems |
Development of Formal Methods for FPGA-based Array Processor Design
(Research Project funded by National Research Funds (OTKA) No. T-022115,
1997-99)
Persons involved: István
Vassányi
Introduction to FPGAs and Cellular Architectures
The increasing demands on signal and image processing performance require
application-specific hardware solutions, which in turn limit the flexibility
of the signal processing subsystem. A relatively new technology, Field
Programmable Gate Arrays (FPGAs) offer a solution to this problem by
providing a completely reprogrammable hardware component which can act
as a co-processor or accelerator board in a microcomputer environment.
SRAM-based FPGAs can be reprogrammed in run-time in some (tens of) milliseconds
an in-circuit, thereby combining the performance of custom hardware and
the flexibility and ease-of-use of general purpose microprocessors. FPGA
chips contain a homogenous matrix of configurable logic blocks that can
be interconnected by a hierarchy of programmable routing resources.
Due to their array structure, FPGAs serve an ideal environment for
systolic/cellular arrays, known as an alternative to the Neumann architecture,
but not often actually applied due to the traditional lack of proper hardware
support. Fine grain cellular arrays are made up by a regular SIMD network
of simple identical processors, and they exploit massive (pipelined) data
parallelism. As such, they can be applied to problems involving simple
repetitive operations on large volumes of data, most notably image and
signal processing applications.
Project Overview
The project investigates the feasibility of FPGA-based 2-dimesional, fine
grain processor arrays with an emphasis on image processing applications.
Since the theory of systolic arrays is a well studied area, and methods/tools
are available for extracting parallelism from problems and for designing
the best abstract processor array, the project focuses on the implementation
problems of such arrays on SRAM-based, matrix structured FPGAs.
Two chief components of the project are the application of tiling theory
for this field and the adaptation of existing FPGA CAD methods to the special
features of systolic arrays (like array topology and communication symmetry).
Results Achieved
I have achieved the following results so far:
-
I have shown that the currently available state-of-art FPGA chips can hold
reasonably sized systolic arrays for such problems as binary morphology
and histogram computation;
-
With the application of geometric tiling theory I have shown that only
a quite limited set of array types can be efficiently implemented on matrix
structured FPGAs;
-
I have designed and implemented a placement-routing tool for FPGA layout
design that uses a parameterized fine-granularity FPGA model and produces
layouts for the feasible array types (see figure).
The output of the Array Mapper (ARM) tool in the Cell Array Viewer
for a simple Processing Element
Facilities
The Department has a PC-based XC3000 development system and single-FPGA
demo cards (from Xilinx Inc.). I have access to an XC4000-based Spectrum
G800 co-processor board and development system (from Giga Operations Inc.)
at the KFKI Research Institute for Measurement and Computing Techniques,
and to an XC6200-based H.O.T. development system (from Virtual Computer
Co.) at the Technical University of Budapest.
Co-operation with other Institutions
Publications
(See the publications of the project coordinator,
István
Vassányi)