Reconfigurable Computing�(adapted from Bobda‘s Book [1])

Prof. Dr. Vanderlei Bonato

The University of Sao Paulo (USP)

Institute of Mathematical and Computing Sciences (ICMC)

Agenda

1. Early Work

​

• Programmable devices (PLD)
• PAL /PLAs
• CPLDs
• FPGAs

​

• Design Flow

​

​

Early Work

Gerald Estrin Fix-Plus Machine

• Vision of a restructurable computer system

​

Pragmatic problem studies predicts gains in computation

speeds in a variety of computational tasks when executed

on appropriate problem-oriented configurations of the

variable structure computer. The economic feasibility of the

system is based on utilization of essentially the same

hardware in a variety of special purpose structures. This

capability is achieved by programmed or physical

restructuring of a part of the hardware.

​

G. Estrin, B. Bussel, R. Turn, J Bibb (UCLA 1963)

Gerald Estrin Fix-Plus Machine

• Fixed plus Variable structure computer
• Proposed by G. Estrin in 1959
• Consist of three parts

​

• A high speed general purpose computer (the fix part F).

​

• A variable part (V) consisting of various size high speed digital substructures which can be reorganized in a problem oriented special purpose configurations.

​

• The supervisory control (SC) coordinates operations between the fix module and the variable module.

​

Speed gain over IBM7090 (2.5 to 1000)

Gerald Estrin Fix-Plus Machine

• The Fixed Part (F)

Was initially an IBM 7090, but could be any general purpose computer

• The Variable Part (V)

Made upon a set of problem specific optimized functional units in the

basic configuration( trigonometric functions, logarithm, exponentials,

n-th power, roots, complex arithmetic, hyperbolic, matrix operation)

​

• Two types of basic building block
• The first basic element contains four amplifiers and associated input logic for signal inversion, amplification, or high-speed storage
• The second basic block consists of ten diodes and four output drivers and is for combinatoric application

Gerald Estrin Fix-Plus Machine

• The basic modules can be inserted into any of 36 positions on a mother board.
• The connection between the modules is done by wiring harness
• Function Reconfiguration means changing some modules
• Routing Reconfiguration means changing some wiring harness

Gerald Estrin Fix-Plus Machine

Substantial efforts

on Reconfiguration

The Rammig Machine

• Goal

​

Investigation of a system, which, with no manual or

mechanical interference, permits the building changing, processing and destruction of real (not simulated) digital hardware

​

Franz J. Rammig (University of Dortmund 1977)

​

​

The concept resulted in the construction of a

hardware editor. Useful to observe a circuit under

test (Hardware Emulation)

The Rammig Machine

• Implementation
• Outputs of modules connected to Selectors and selectors output connected to module inputs.
• Software controlled modules interconnection
• Two main problems to solve
• Because the circuit is not hard-wired, a distortion of the time behaviour is possible
• The timing is controlled by the circuit instead of being dictated by an observation mechanism.
• A time-controlling must therefore be provided

Programmable Logic

PALs and PLAs

• Pre-fabricated building block of many AND/OR gates (or NOR, NAND)
• "Personalized" by making or breaking connections among the gates

Programmable Array Block Diagram for Sum of Products Form

Inputs

Outputs

PALs and PLAs

Example:

Equations

Personality Matrix

1 = asserted in term

0 = negated in term

- = does not participate

1 = term connected to output

0 = no connection to output

Input Side:

Output Side:

PALs and PLAs

Example Continued - Unprogrammed device

All possible connections are available

before programming

PALs and PLAs

Example Continued -

Programmed part

Unwanted connections are "blown"

Note: some array structures

work by making connections

rather than breaking them

PALs and PLAs

Alternative representation for

high fan-in structures

Short-hand notation

so we don't have to

draw all the wires!

​

X at junction indicates

a connection

Unprogrammed device

Programmed device

PALs and PLAs

Design Example

F1 = A B C

​

F2 = A + B + C

​

F3 = A B C

​

F4 = A + B + C

​

F5 = A ⊕ B ⊕ C

​

F6 = A ⊕ B ⊕ C

Multiple functions of A, B, C

PALs and PLAs

What is difference between Programmable Array Logic (PAL) and�Programmable Logic Array (PLA)?

PAL : AND array is programmable, OR array is fixed at fabrication

A given column of the OR array

has access to only a subset of

the possible product terms

PLA: Both AND and OR arrays are programmable

PALs and PLAs

Design Example: BCD to Gray Code Converter

Truth Table

K-maps

Minimized Functions:

PALs and PLAs

Programmed PAL:

4 product terms per each OR gate

Minimized Functions:

Complex Programmable Logic Devices

• Complex PLDs (CPLD) typically combine PAL combinational logic with Flip Flops
• Organized into logic blocks connected in an interconnect matrix
• Combinational or registered output
• Usually enough logic for simple counters, state machines, decoders, etc.
• CPLDs logic is not enough for complex operation
• FPGAs have much more logic than CPLDs

​

• e.g. Xilinx Coolrunner II, etc.

Complex Programmable Logic Devices

Field-Programmable Gate Arrays (FPGAs)

• Introduced in 1985 by Xilinx
• Roughly seen, an FPGA consist of:
• A set of programmable macro cells
• A programmable interconnection network
• Programmable input/outputs

​

• Subparts of a (complex) function are implemented in macro cells which are then connected to build the complete function
• The IO can be programmed to drive the macro cell's inputs or to be driven by the macro cell's outputs
• Unlike traditional application-specific integrated circuit (ASIC), function is specified by the user after the device is manufactured
• Physical structure and programming method is vendor dependant

FPGA Structure

• Typical organization
1. Symmetrical Array
• 2 D array of processing elements (PE) embedded in an interconnection network
• Interconnection points at the horizontal-vertical intersection
2. Row based
• Rows of Processing elements
• Horizontal routing via horizontal channels
• Channels divided in segments
• Vertical connections via dedicated vertical tracks (not on the graphic)

FPGA Structure

• Typical organization (cont)
3. Sea of gates
• 2 D array of processing elements
• No space left aside the PEs for routing
• Connection is done on a separate layer on top of the cells
4. Hierarchical
• Hierarchically placed Macro cells
• Low-level macro cells are grouped to build the higher-level's PEs

FPGA Programming Technologies

• SRAM (LUT-based)
• An SRAM is used to store all possible values of a function
• Value of a function for a given input is retrieved using the inputs as SRAM-Address
• SRAM implementing a function is called a look-up table (LUT)
• A new function is implemented by writing new values into the LUT
• SRAM-based FPGA can therefore be reprogrammed (configured) on the fly
• Since a LUT is volatile, a LUT configuration is lost when switching off the system

FPGA Programming Technologies

• Anti-fuse
• An anti-fused normally presents a high-impedance state
• can be “fused” into a low-impedance state when programmed by a high voltage.
• The anti-fuse used in each of FPGAs from different company differs in construction

Advantages:

• small area,
• low resistance and parasitic capacitance than transistors
• reduce delays in the routing.

​

Drawback: No reprogrammation possible

FPGA Programming Technologies

• Poly-diffusion Anti-fuse: ACTEL PLICE
• programmable low-impedance circuit element
• Poly-silicon terminal
• Oxide-Nitride-Oxide dielectric
• Melting the dielectric establish connection

​

• Metal Anti-fuse: Q-Logic Vialink
• 2 Metal terminal layers (Titanium-Tungsten)
• Programming points isolated by amorphous Silicon film

FPGA Programming Technologies

• EEPROM (Flash)
• The same technology as that used in
• EPROM and EEPROM memories.
• Advantages:
• EPROMs require re-programmable but do not require external storage.
• EEPROM can be re-programmed in-circuit.
• Drawbacks:
• EPROM's resistors consume static power.
• EEPROM requires more chip area and multiple voltage sources

FPGA Function generators

• LUT
• LUT are used as function generators in SRAM-based FPGA

​

• A k-inputs LUT can implement up to 2 ^k different functions

​

• A k-input LUT has 2 ^k SRAM locations

​

• A function is implemented by writing all possible values that the function can take in the LUT

​

• The inputs values are used to address the LUT and retrieve the value of the function corresponding the the input values

a XOR b

a

b

0 0 0

0 1 1

1 0 1

1 1 0

0

1

1

0

a

b

a Xor b

LUT

FPGA Function generators

a XOR b

a

b

0 0 0

0 1 1

1 0 1

1 1 0

0

1

1

0

a

b

a Xor b

LUT

FPGA Function generators

• LUT Example: Implement the function
• using:

2-input LUTs

3-input LUTs

4-input LUTs

A

B

D

B

C

D

A

B

C

F

A

B

D

B

C

D

A

B

C

C

D

A

B

F

F

FPGA Function generators

• Multiplexers (MUX)
• A 2 ^kx1 MUX can implement up to 2 ^k different functions

​

• A function is implemented by writing all possible values that the function can take as constant at the MUX-Inputs

​

• The selector-values are used to pass the corresponding input to the MUX output

​

• Complex function can be decomposed and implement using many MUXes using the Shannon expansion theorem

Static and dynamic Reconfiguration

• The ways of using a reconfigurable systems can be classified in two big categories:

​

• Static reconfigurable systems.

The computation and reconfiguration is defined once at compile

time.

This category encounters the rapid prototyping systems, the non-

frequently reconfigurable systems as well as some frequently

reconfigurable systems.

​

• Dynamic or run-time reconfigurable systems.�The computation and reconfiguration sequences are not known at compile-time. The system reacts dynamically at run-time to computation and therefore, to reconfiguration requests. Some non-frequently reconfigurable systems as well as most frequently reconfigurable systems belong to this category.

Intel FPGAs

Xilinx FPGAs

Design Flow

Hardware/software partitioning

• The implementation of a reconfigurable system is a Hardware/software co- design process which determines:

​

• The software part, that is the code-segment to be executed on the processor. The development is done in a software language with common tools.
• We will not pay much attention to this part.
• The hardware part, that is the part to be executed on the RD.
• This is the target of this section.
• The interface between software and hardware. This part is not in the scope of this course.

Software

C, C++, Java

etc ...

Hardware

VHDL, Verilog

HandelC, etc..

Interface

Coarse-grained RC

• The implementation of a coarse-grained RD is done with vendor specific language and tools.
• Usually a C-like language with the corresponding behavioral or structural compilers.

​

• For the coarse-grained architectures presented in the previous chapter, the languages and tools are summarised in the table below.

FPGA Design Flow

• The implementation flow of an FPGA designs is shown on the figure aside. It is a modifiedASIC design implementation divided in 5 steps.

​

• The steps (design entry, functional simulation, place and route) are the same for almost all digital circuits.
• Therefore, they will be presented only briefly.

​

• FPGA-synthesis differs from other synthesis process in the technology mapping step
• We will therefore consider some details of FPGA-synthesis, in particular the LUT-technology mapping which is proper to the FPGAs.

FPGA Design Flow - Design entry

• The design entry can be done with
• A schematic editor: �Selection components from a (target device) and graphically connecting them together to build complex modules.
• Finite State machine (FSM) can also be entered by drawing the states and transitions either as graph or as table.

​

• A Hardware Description Language (HDL)
• structural as well as behavioral description of complex circuits.
• Behavioral description: useful for designs containing loops, Bit-vectors, ADT, FSMs.
• Structural description: emphasizes the hierarchy in a given design.

FPGA Design Flow – Functional Simulation

• After the design entry, the functional simulation is
• used to logically test the functionality of the design.
• A testbench provides the design under test with inputs for which the reaction of the design is known.

​

• The outputs of the circuit are observed on a waveform and compared to the expected values.

​

• For simulation purpose, many operations can be used (mod, div, etc...) in the design description.

​

• However only part of the code which is used for simulation can be synthesized later.

​

• The most used HDLs are:
• VHDL (behavioral, structural)
• Verilog (behavioral, structural)
• Some C/C++-like languages (SystemC, HandelC, etc...)

FPGA Design Flow – Synthesis

• The design is compiled and optimized. All non-synthesizable data types and operations must be replace by equivalent synthesizable code.
• The design is first translate into a set of Boolean equations which are then minimized.
• Technology mapping is used to assigned the functional modules to library elements. The technology mapping on FPGAs is called LUT-technology mapping.
• The result of the technology mapping is a netlist which provides a list of components used in the circuit as well as their interconnections.
• There exist many formats to describe a netlist. The most popular is the EDIF (Electronic Design Interchange Format).
• Vendor specific netlist also exists. Example: XNF (Xilinx Netlist Format)

FPGA Design Flow – Place and route

• The Netlist provides only informations about the components and their interconnections in a given design. The place and route must be used to:

​

• Assign locations to the components.
• Provide communication paths to the interconnections.

​

• The place and route steps are optimization problems for which some cost must be minimized.
• The most important factors are:
• The clock frequency.
• The signal latency.
• The routing congestion.
• Etc...

FPGA Design Flow – Configuration bitstream

• The Last step in the design process is the generation of the configuration stream also known as bitstream. A Bitstream describes:

​

• The value of each LUT, that is the set of bits used to configure the function of a LUT.

​

• The interconnections configuration describes:
• The inputs and outputs of the LUTs
• The value of the multiplexers
• how the switches should be set in the interconnection matrix

​

• All informations regarding the functionality of LUTs, multiplexers and switches are available after the place and route step

FPGA Design Flow – Example

• Implements a Modulo 10-counter on a symetrical array FPGA with a 2x2 Logic Block (LB) .

​

• The structure of the LBs is given in the picture aside. It consists of:
• 2 2-inputs LUT.
• 2 edge triggered T-Flipflop.

​

• Your result should minimize
• The area
• The latency

FPGA Design Flow – Example

• Truth table of the modulo 10 counter The z describe the states while the T describe the inputs of the T-FFs

Karnaugh-minimization of the

functions T₁, T₂, T₃, and T₄

FPGA Design Flow – Example

FPGA Design Flow – Example

Exemplo de produtos com

hardware reconfigurável

*

50

Microsoft Research: Project Catapult

• Project Catapult is a Microsoft venture that investigates the use of field-programmable gate arrays (FPGAs) to improve performance, reduce power consumption, and provide new capabilities in the datacenter (large-scale datacenters);

​

• Video
• http://research.microsoft.com/apps/video/default.aspx?id=219486

Microsoft Research: Project Catapult

​

• Paper
• A Reconfigurable Fabric for Accelerating Large-Scale Datacenter Services (ISCA2014)
• Under high load, the large- scale reconfigurable fabric improves the ranking throughput of each server by a factor of 95% for a fixed latency distribution

​

• Accelerating Deep Convolutional Neural Networks Using Specialized Hardware (Microsoft Research)
• We show that the throughput/watt is significantly higher than for a GPU, and project the performance when ported to an Arria 10 FPGA.

Amazon EC2 F1 Instances

• Amazon Web Services (AWS)
• Amazon EC2 F1 is a compute instance with field programmable gate arrays (FPGAs) that you can program to create custom hardware accelerations for your application
• Amazon EC2 F1 instances offered in two different instance sizes that include up to eight FPGAs per instance.
• F1 instances include 16 nm Xilinx UltraScale Plus FPGA.

Maxeler Technologies

• High-performance dataflow platforms for a wide range of application domains”
• MaxCompiler allows an application to be split into three parts:
• Kernel(s), which implement the computational components of the application in hardware.
• Manager configuration, which connects Kernels to the CPU, engine RAM, other Kernels and other dataflow engines via MaxRing.
• CPU application, which interacts with the dataflow engines to read and write data to the Kernels and engine RAM.

​

Other examples

• Stretch Technology - Stretch Inc
• Stretch is a fabless semiconductor company providing software configurable processors for compute-intensive applications.
• Flex Logix
• utilizes a new breakthrough interconnect architecture: less than half the silicon area of traditional mesh interconnect, fewer metal layers, higher utilization and higher performance.
• Algo-Logic Company
• designs, verifies, and deploys the lowest latency algorithms for processing network data using FPGA logic.
• Celoxica
• Provides accelerated Market Data Feed Handlers for the main Equity, Options, Futures, Fixed Income and FX Markets in both the US and Europe.

​

​

References

• [1] CHRISOPHE BOBDA – “Introductions to Reconfigurable Computing – Architecture, algorithms and applications”- Springer, 2007, 359pg.
• [2] Xilinx. FPGA vs. ASIC [https://www.xilinx.com/fpga/asic.htm]
• [3] Maxeler Technologies. https://www.maxeler.com/products/software/maxcompiler/
• [4] Strech. http://www.stretchinc.com/
• [5] Dini Group. http://www.dinigroup.com/web/index.php
• [6] Flex Logix. http://www.flex-logix.com/fpga-tutorial/
• [7] Algo-Logic. http://algo-logic.com/about
• [8] Celoxica. http://www.celoxica.com/

​