How do computers do math?

This is part 9 in a continuation on the quest to answer the question “How do computers do math?”. It should how to build logic circuits using programmable logic.

Programmable logic

Complexity – CAD – Simulation ….

Logic devices can be classified into two broad categories

  • Fixed devices, where the circuits are permanent. Their function cannot be changed. Examples are:
    • gates (NAND, NOR, XOR),
    • binary counters,
    • multiplexers, and
    • adders.
  • Application-Specific Integrated Circuit (ASIC)
    • The manufacturer defines a integrated circuit containing transistors, but does not connect them together.
    • The user specifies the metal mask that connects the transistors.
    • The manufacturer uses this mask to finish the ASIC.
    • Introduced by Fairchild in 1967. Have since grown to contain over 100 million gates.

Programmable logic devices

Programmable logic devices (PLD), can be changed at any time to perform any number of functions. Prominent flavors of PLDs are:


(c) Copyright 2014 Coert Vonk
Programmable array logic
  • Programmable array logic (PAL)
    • based on sum-of-products, with programmable “fuses”,
    • used for simple combinational logic (a few 100′s gates),
    • introduced by MMI (Birkner and Chua, 1978).
    • The figure on the right shows an example of an AND function with programmable fuses.
  • Complex programmable logic device (CPLD)
    • based on sum-of-products,
    • for medium size combinational logic (10,000′s gates).
  • Field-programmable gate array (FPGA)
    • based on blocks containing a look-up tables, full adder and d flip-flop,
    • used for complex combinational or sequential logic such as state machines (1,000,000′s gates),
    • introduced by Xilinx (Freeman, Vonderschmitt) in 1985.

A CPLD would be sufficient to implement the combinational circuits discussed so far, however our ultimate goal is to create a modest microprocessor circuit. As we will see later, a microprocessor circuit requires a state machine for which we need a FPGA. As a result the remainder of this text will focus on a FPGAs implementation.

Interconnected cells

The core of FPGAs contains a vast array of interconnected logic cells.

The exact logic cell architecture depends on the vendor. (refer to FPGA logic cells for typical cell architectures.)

The main vendors are:

  • Xilinx for leading edge products, and
  • Altera for lean and efficient devices.

Each logic cell consists of:

  • a look-up table (LUT), to implement any 4-input Boolean function,
  • a full adder with an additional AND gate, to implement multiplication.
  • a D flip-flop, to implement sequential logic, and
  • a 2-to-1 multiplexer, to bypass the flip-flop if desired

(c) Copyright 2014 Coert Vonk
Example logic cell

Each IO cell consists of:

  • a D flip-flop, to implement sequential logic, and
  • a 2-to-1 multiplexer, to bypass the flip-flop if desired

(c) Copyright 2014 Coert Vonk
Example IO cell

Programmable interconnects

  • Reconfigurable interconnects allow the logic cells to be “wired together”.
  • The functionality of an FPGA can be changed by downloading a different configuration.
  • The circuits are often much faster as with discrete components, because the signals stay within the silicon die of the FPGA.

(c) Copyright 2014 Coert Vonk
Example programmable interconnect

The figure below shows a typical matrix organization of the logic cells that are interconnected using programmable interconnects.


(c) Copyright 2014 Coert Vonk
Example FPGA

Lab environment (thanks Dylon)

  • Altera (now Intel), much better tools.
  • Boards
    • Xilinx, development boards are easy to find. E.g. Spartan6 ($89 at Avnet) that has a USB-to-UART chip on it so you can plug it right into your computer to download new FPGA code as well as use it as a UART.
    • Alternatively, the Xilinx Spartan3E development board is an old standby that works well.
  • Simulator
    • icarus verilog (free simulator, yum install iverilog) and GTKWave (free waveform viewer, yum install gtkwave) work great. They are just as good as most of the bundled simulators that you’ll find with the tools.
    • a web copy of ModelSim bundled with Xilinx or Altera that wouldn’t be bad either.
  • Cliff Cummings posted papers about verilog, and book recommendations.
  • OpenCores has lots of verilog and VHDL code for most any kind of core you can imagine.
  • Scripts SimShop and Tizzy for simulation and state machines! SimShop provides an easy scriptable way to set up a simulation environment, and Tizzy allows you to write state machines in .dot and will do a conversion to verilog for you.

xx

The typical workflow:

  • The desired logic is specified using traditional schematics or a hardware description language.
  • The logic function is compiled into a binary file that can be downloaded into the FPGA.
  • Test vectors and output verification.
  • The binary file is download the FPGA.

The application-specific integrated circuit (ASIC), is similar to the FPGA, except that it is not reprogrammable. The advantage is higher speed and smaller footprint.

Hardware description language (HDL)

  1. Verilog/VHDL
  2. netlist
  3. synthesis optimizes the functions
  4. mapping to hardware

Build-in components are called macros (counters, RAM, multiplexers, adders, LUT)

  1. See “Introduction to Verilog
  2. In order the obtain reasonable speeds (wires are not ideal), the utilization is typically limited to about 50%.

Lab work

FPGA tools for design entry, simulation, synthesis and uploading is available from: (see also comparison)

Build an 8-bit adder

What’s next?

The logic next step is the Arithmetic Logical Unit that forms the heart of today’s computers.

Arithmetic Logical Unit (ALU)

  1. Arithmetic Logical Unit (ALU)
    • http://ecen3233.okstate.edu/Fall%202009/labs/Lab05.pdf
    • soft cores for Xilinx, http://www.1-core.com/library/digital/soft-cpu-cores/
  2. Add Simple picture showing different functions feeding into a multiplexor where the operation is the selector.

Now let us build something with Gate-Level Verilog!

The inquiry “How do microprocessors work?” picks up from here.

Embedded software developer
Passionately curious and stubbornly persistent. Enjoys to inspire and consult with others to exchange the poetry of logical ideas.

2 Replies to “How do computers do math?”

  1. Coert, I have tried to make a square root in excel but it would be work. The multiply and divide work in excel and the CSM works. I can not send you a picture of my work in this system. Can you help me?
    Ronald lokker from the Netherlands

  2. Thanks. I think the sqrt schematic might use the q* instead of the q to build the new subtrahend.
    [in parallel to email conversation]

Leave a Reply

Your email address will not be published. Required fields are marked *

 

This site uses Akismet to reduce spam. Learn how your comment data is processed.