05-06-2013, 04:31 PM
Field-programmable gate arrays (FPGAs)
[attachment=54844]
Introduction
Field-programmable gate arrays (FPGAs) are generic, programmable digital devices that
can perform complex logical operations. FPGAs can replace thousands or millions of
logic gates in multilevel structures. Their high density of logic gates and routing
resources, and their fast reconfiguration speed give them the advantage of being
extremely powerful for many applications. FPGAs are widely used because of their rich
resources, configurable abilities and low development risk, making them increasingly
popular.
Since FPGAs offer designers a way to access many millions of gates in a single device,
powerful FPGA design tools with an efficient design methodology are necessary for
dealing with the complexity of large FPGAs. Currently, most of the FPGA design tools
[Men01][Syn03][Syn04] use the following design flow: first, they implement the design
using Hardware Description Language (HDL); second, they simulate the behavior and the
functionality of the design; finally, they synthesize and map the design in the vendor’s
FPGA architecture [Xil00]. When analyzing the typical design flow of an Electronic
Design Automation (EDA) tool, place-and-route is the most time-consuming and
laborious procedure. It’s hard to find an optimum layout in a limit period of time.
Similar to the bin-packing problem, placement is NP-complete [Ger98].
Prior Work
This chapter examines the traditional FPGA design cycle from the contemporary FPGA
design tools reported in the literature. The common features of the design cycle are
analyzed and their shortcomings are evaluated for high-density FPGAs. Incremental
compilation [Sun98], a compiler optimization technique, is examined from the literature
to demonstrate the possibility of improving the traditional FPGA design flow. The
functionality of both the JBits Application Program Interface (APIs) and JBits tools
[Xil01] is investigated to explain their potential to shorten the FPGA design cycle.
FPGA Design Tools
This section reviews the current FPGA design tools, the placement algorithms, and the
traditional FPGA design flow. The characteristics of the design flow are investigated and
their limitations for million-gate FPGA designs are examined.
Incremental Compilation
Incremental compilation is a compiler optimization intended to improve the software
development cycle. It is used to search for the change between the current and the
previous design, recompile only the change, and avoid affecting the remaining optimized
portions. Because the recompilation time will be proportional to the changes in a design,
incremental compilation, if used properly, will significantly reduce the compilation time
if the changes are small.
This technique is broadly used in software engineering to improve software development
cycles. Montana [Kar98], an open and extensible integrated programming environment
provided by IBM and an infrastructure of one of IBM’s production compiler, Visual Age
C++ 4.0 [Nac97], supports incremental compilation and linking. This system uses an
automatic testing tool to test functions that have been changed since the last computation,
which leads to better performance for the tool and the compiler. Venugopal and Srikant
applied incremental compilation to an incremental basic block instruction scheduler
[Ven98]. In this paper, algorithms for incremental construction of the dependency
directed graph and incremental shortest and longest path were investigated and their
performances were evaluated by implementing the system on an IBM RISC System/6000
processor. The testing results showed that the compiling time is reduced significantly by
using the incremental compilation technique.
Garbage Collection
Garbage collection, in the context of free memory management, was originally a software
engineering issue. This technique is generally used in automatic memory and resource
management by automatically reclaiming heap-allocated storage after its last use by a
program [Jon96]. Memory management is a simple and easy task in small-scale
computer programming, but it becomes essential as the complexity of software
programming grows, especially in situations where memory allocation/de-allocation is
not explicitly handled. Improper resource management could downgrade system
performance and distract the concentration of software engineers from the real problems
they are trying to solve. Programmer controlled (explicit) resource management provides
methods for software engineers, especially object-oriented language programmers, to
effectively control the complexity of their program, therefore increasing code efficiency
and resource application.
Several object-oriented languages including Java, C++, and Smalltalk utilize garbage
collection techniques for free memory management, and an enormous number of papers
and books talk about this issue. Richard Jones and Rafael Lins reviewed the development
of memory management, the classical and generational garbage collection algorithms,
and its applications to the C/C++ language in their book [Jon96]. An age-based garbage
collection is discussed in [Ste99].
[attachment=54844]
Introduction
Field-programmable gate arrays (FPGAs) are generic, programmable digital devices that
can perform complex logical operations. FPGAs can replace thousands or millions of
logic gates in multilevel structures. Their high density of logic gates and routing
resources, and their fast reconfiguration speed give them the advantage of being
extremely powerful for many applications. FPGAs are widely used because of their rich
resources, configurable abilities and low development risk, making them increasingly
popular.
Since FPGAs offer designers a way to access many millions of gates in a single device,
powerful FPGA design tools with an efficient design methodology are necessary for
dealing with the complexity of large FPGAs. Currently, most of the FPGA design tools
[Men01][Syn03][Syn04] use the following design flow: first, they implement the design
using Hardware Description Language (HDL); second, they simulate the behavior and the
functionality of the design; finally, they synthesize and map the design in the vendor’s
FPGA architecture [Xil00]. When analyzing the typical design flow of an Electronic
Design Automation (EDA) tool, place-and-route is the most time-consuming and
laborious procedure. It’s hard to find an optimum layout in a limit period of time.
Similar to the bin-packing problem, placement is NP-complete [Ger98].
Prior Work
This chapter examines the traditional FPGA design cycle from the contemporary FPGA
design tools reported in the literature. The common features of the design cycle are
analyzed and their shortcomings are evaluated for high-density FPGAs. Incremental
compilation [Sun98], a compiler optimization technique, is examined from the literature
to demonstrate the possibility of improving the traditional FPGA design flow. The
functionality of both the JBits Application Program Interface (APIs) and JBits tools
[Xil01] is investigated to explain their potential to shorten the FPGA design cycle.
FPGA Design Tools
This section reviews the current FPGA design tools, the placement algorithms, and the
traditional FPGA design flow. The characteristics of the design flow are investigated and
their limitations for million-gate FPGA designs are examined.
Incremental Compilation
Incremental compilation is a compiler optimization intended to improve the software
development cycle. It is used to search for the change between the current and the
previous design, recompile only the change, and avoid affecting the remaining optimized
portions. Because the recompilation time will be proportional to the changes in a design,
incremental compilation, if used properly, will significantly reduce the compilation time
if the changes are small.
This technique is broadly used in software engineering to improve software development
cycles. Montana [Kar98], an open and extensible integrated programming environment
provided by IBM and an infrastructure of one of IBM’s production compiler, Visual Age
C++ 4.0 [Nac97], supports incremental compilation and linking. This system uses an
automatic testing tool to test functions that have been changed since the last computation,
which leads to better performance for the tool and the compiler. Venugopal and Srikant
applied incremental compilation to an incremental basic block instruction scheduler
[Ven98]. In this paper, algorithms for incremental construction of the dependency
directed graph and incremental shortest and longest path were investigated and their
performances were evaluated by implementing the system on an IBM RISC System/6000
processor. The testing results showed that the compiling time is reduced significantly by
using the incremental compilation technique.
Garbage Collection
Garbage collection, in the context of free memory management, was originally a software
engineering issue. This technique is generally used in automatic memory and resource
management by automatically reclaiming heap-allocated storage after its last use by a
program [Jon96]. Memory management is a simple and easy task in small-scale
computer programming, but it becomes essential as the complexity of software
programming grows, especially in situations where memory allocation/de-allocation is
not explicitly handled. Improper resource management could downgrade system
performance and distract the concentration of software engineers from the real problems
they are trying to solve. Programmer controlled (explicit) resource management provides
methods for software engineers, especially object-oriented language programmers, to
effectively control the complexity of their program, therefore increasing code efficiency
and resource application.
Several object-oriented languages including Java, C++, and Smalltalk utilize garbage
collection techniques for free memory management, and an enormous number of papers
and books talk about this issue. Richard Jones and Rafael Lins reviewed the development
of memory management, the classical and generational garbage collection algorithms,
and its applications to the C/C++ language in their book [Jon96]. An age-based garbage
collection is discussed in [Ste99].