Reconfigurable computing

Reconfigurable computing is a computer architecture combining some of the flexibility of software with the high performance of hardware by processing with very flexible high speed computing fabrics like field-programmable gate arrays (FPGAs). The principal difference when compared to using ordinary microprocessors is the ability to make substantial changes to the datapath itself in addition to the control flow. On the other hand, the main difference with custom hardware, i.e. application-specific integrated circuits (ASICs) is the possibility to adapt the hardware during runtime by "loading" a new circuit on the reconfigurable fabric.

History and properties

The concept of reconfigurable computing has existed since the 1960s, when Gerald Estrin's landmark paper proposed the concept of a computer made of a standard processor and an array of "reconfigurable" hardware.^[1][2] The main processor would control the behavior of the reconfigurable hardware. The latter would then be tailored to perform a specific task, such as image processing or pattern matching, as quickly as a dedicated piece of hardware. Once the task was done, the hardware could be adjusted to do some other task. This resulted in a hybrid computer structure combining the flexibility of software with the speed of hardware; unfortunately this idea was far ahead of its time in needed electronic technology.

In the 1980s and 1990s there was a renaissance in this area of research with many proposed reconfigurable architectures developed in industry and academia,^[3] such as: COPACOBANA, Matrix, Garp,^[4] Elixent, PACT XPP, Silicon Hive, Montium, Pleiades, Morphosys, PiCoGA.^[5] Such designs were feasible due to the constant progress of silicon technology that let complex designs be implemented on one chip. The world's first commercial reconfigurable computer, the Algotronix CHS2X4, was completed in 1991. It was not a commercial success, but was promising enough that Xilinx (the inventor of the Field-Programmable Gate Array, FPGA) bought the technology and hired the Algotronix staff.^[6]

Reconfigurable computing as a paradigm shift: using the Anti Machine

Computer scientist Reiner Hartenstein describes reconfigurable computing in terms of an anti machine that, according to him, represents a fundamental paradigm shift away from the more conventional von Neumann machine. ^[7] Hartenstein calls it Reconfigurable Computing Paradox, that software-to-configware migration (software-to-FPGA migration) results in reported speed-up factors of up to more than four orders of magnitude, as well as a reduction in electricity consumption by up to almost four orders of magnitude—although the technological parameters of FPGAs are behind the Gordon Moore curve by about four orders of magnitude, and the clock frequency is substantially lower than that of microprocessors. This paradox is due to a paradigm shift, and is also partly explained by the Von Neumann syndrome.

The fundamental model of the reconfigurable computing machine paradigm, the data-stream-based anti machine is well illustrated by the differences to other machine paradigms that were introduced earlier, as shown by Nick Tredennick's following classification scheme of computing paradigms (see "Table 1: Nick Tredennick’s Paradigm Classification Scheme"). ^[8]

The fundamental model of a Reconfigurable Computing Machine, the data-stream-based anti machine (also called Xputer), is the counterpart of the instruction-stream-based von Neumann machine paradigm. This is illustrated by a simple reconfigurable system (not dynamically reconfigurable), which has no instruction fetch at run time. The reconfiguration (before run time) can be considered as a kind of super instruction fetch. An anti machine does not have a program counter. The anti machine has data counters instead, since it is data-stream-driven. Here the definition of the term data streams is adopted from the systolic array scene, which defines, at which time which data item has to enter or leave which port, here of the reconfigurable system, which may be fine-grained (e. g. using FPGAs) or coarse-grained, or a mixture of both.

The systolic array scene, originally (early 1980s) mainly mathematicians, only defined one half of the anti machine: the data path: the systolic array (also see Super systolic array). But they did not define nor model the data sequencer methodology, considering that this is not their job to take care where the data streams come from or end up. The data sequencing part of the anti machine is modeled as distributed memory, preferably on chip, which consists of auto-sequencing memory (ASM) blocks. Each ASM block has a sequencer including a data counter. An example is the Generic Address Generator (GAG), which is a generalization of the DMA.

Example of a streaming model of computation

Problem: We are given 2 character arrays of length 256: A[] and B[]. We need to compute the array C[] such that C[i]=B[B[B[B[B[B[B[B[A[i]]]]]]]]]. Though this problem is hypothetical, similar problems exist which have some applications.

Consider a software solution (C code) for the above problem:

for(int i=0;i<256;i++){ char a=A[i]; for(int j=0;j<8;j++) a=B[a]; C[i]=a;}

This program will take about 256*10*CPI cycles for the CPU, where CPI is the number of cycles per instruction.

Now, consider the hardware implementation shown here, say on an FPGA. Here, one element from the array 'A' is 'streamed' by a microprocessor into the circuit every cycle. The array 'B' is implemented as a ROM, perhaps in the BRAMs of the FPGA. The wire going into the ROMs labelled 'B' are the address lines and the wires out are the values stored in the ROM at that address. The blue boxes are registers used for storing temporary values Clearly, this is a pipeline and will output 1 value (a useful C[i] value) after the 8th cycle. Hence the output is also a 'stream'.

The hardware implementation takes 256+8 cycles. Hence, we can expect a speedup of about 10*CPI over the software implementation. However, the speedup is much less than this value due to the slow clock of the FPGA.

Reconfigurable computing as a hobby

With the advent of affordable FPGA boards, there is an ever increasing number of students' and hobbyists' projects that seek to recreate vintage computers or implement more novel architectures, such as the RISC ^{[9] [10] [11]} .^[12]

• 

  An FPGA board is being used to recreate the Vector-06C computer

• 

  Game being played on the FPGA Vector-06C computer

• 

  The C-One emulating an Amstrad CPC

See also

• High-performance reconfigurable computing
• Reconfigurable computing terminology
• Partial re-configuration
• Sprinter
• 1chipMSX
• PSoC
• Milkymist
• Mitrionics
• PipeRench
• Computing with Memory
• iland project

References

Further reading

• Cardoso, João M. P.; Hübner, Michael (Eds.), Reconfigurable Computing: From FPGAs to Hardware/Software Codesign, Springer, 2011.
• S. Hauck and A. DeHon, Reconfigurable Computing: The Theory and Practice of FPGA-Based Computing, Morgan Kaufmann, 2008.
• J. Henkel, S. Parameswaran (editors): Designing Embedded Processors. A Low Power Perspective; Springer Verlag, March 2007
• J. Teich (editor) et al.: Reconfigurable Computing Systems. Special Topic Issue of Journal it — Information Technology, Oldenbourg Verlag, Munich. Vol. 49(2007) Issue 3
• T.J. Todman, G.A. Constantinides, S.J.E. Wilton, O. Mencer, W. Luk and P.Y.K. Cheung, "Reconfigurable Computing: Architectures and Design Methods", IEEE Proceedings: Computer & Digital Techniques, Vol. 152, No. 2, March 2005, pp. 193–208.
• A. Zomaya (editor): Handbook of Nature-Inspired and Innovative Computing: Integrating Classical Models with Emerging Technologies; Springer Verlag, 2006
• J. M. Arnold and D. A. Buell, "VHDL programming on Splash 2," in More FPGAs, Will Moore and Wayne Luk, editors, Abingdon EE & CS Books, Oxford, England, 1994, pp. 182–191. (Proceedings,International Workshop on Field-Programmable Logic, Oxford, 1993.)
• J. M. Arnold, D. A. Buell, D. Hoang, D. V. Pryor, N. Shirazi, M. R. Thistle, "Splash 2 and its applications, "Proceedings, International Conference on Computer Design, Cambridge, 1993, pp. 482–486.
• D. A. Buell and Kenneth L. Pocek, "Custom computing machines: An introduction," The Journal of Supercomputing, v. 9, 1995, pp. 219–230.

External links

• The Fine-grained Computing Group at Information Sciences Institute
• Reconfigurable computing lectures and tutorials at Brown University
• A Decade of Reconfigurable Computing: a Visionary Retrospective
• Reconfigurable Computing: Coming of Age
• The University of South Carolina Reconfigurable Computing Laboratory
• The Virginia Tech Configurable Computing Laboratory
• Reconfigurable Systems Summer Institute (RSSI)
• IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM)
• International Conference on Field-Programmable Logic and Applications (FPL)
• BYU Configurable Computing Laboratory's FPGA CAD tool set
• The Morphware Forum
• NSF Center for High-Performance Reconfigurable Computing (CHREC)
• The OpenFPGA effort
• RC Education Workshop
• Reconfigurable Architectures Workshop
• The George Washington University High Performance Computing Laboratory
• The University of Florida High-Performance Computing & Simulation Research Laboratory
• The University of Kansas Hybridthreads Project - OS for Hybrid CPU/FPGA chips
• Reconfigurable computing tools and O/S Support from the University of Wisconsin
• Circuits and Systems Group, Imperial College London
• Why we need reconfigurable computing education
• The on-line version of the MEANDER FPGA design framework
• FHPCA: FPGA High Performance Computing Alliance
• Website of the DRESD (Dynamic Reconfigurability in Embedded System Design) research project
• Advanced topics in computer architecture: chip multiprocessors and polymorphic processors (2003)
• UT Austin TRIPS multiprocessor
• UNC Charlotte reconfigurable computing cluster
• XiRisc/PiCoGA project at University of Bologna, Italy
• COPACOBANA Project, Germany