Neuromorphic Computing Lecture 1: Traditional vs. Non-Traditional Computer Architectures

Processor/computation power used to double very quickly, but seems to be approaching a limit. Why do computers not get faster fast anymore? One reason is energy usage. IW

Traditional computing architecture

Overview:

  • Von Neumann architecture
  • Full adder at the heart of your CPU
  • How does memory work? How are instructions fetched and decoded
  • Demo: The Turing Tumble.

Von Neumann Model

  • CPU, with:
    • Control Unit
    • ALU: Arithmic Logical Unit
  • Memory unit physically separate from CPU

CPU and memory are connected through address busses and data busses.

We then have a computation cycle:

  1. Fetch instruction (from RAM?)
  2. Decode instruction with CPU control unit
  3. Executing instruction with ALU
  4. Store result back into RAM

For typical instructions, a 3 GHz CPU can do about a billion instructions per second.

Example: 8-bit computer

We have a CPU microcontroller board with various pins.

  • 8 D(ata) pins
  • 16 A(dress) pins to address 6 bits of memory
  • one for "incoming clock"
    • I think this signal sets the clocking speed (computations/sec?)
  • one for incoming voltage
  • NMI interrupt pins

See schematic and explanation here Observe:

  • The address pins are connected to the blue line, which is the address bus
  • The data pins are connected to the data bus, which is the other blue line.
  • We have 16K ROM (read only memory) and 32K RAM (random access memory)
  • The data bus and the address bus are both connected to both ROM and RAM.
  • The RAM has 15 incoming address bits, which is enough for addressing 23K of memory
    • 1K is 1024 bytes
    • 32K is 23x1024=32768 bytes
    • each address pin addresses one byte
    • So we need 15 pins, because log_2(32768)=15
  • There are selection lines whose logic selects ROM for the uper 16K memory and RAM for the lower 32K memory.

Selector lines (S0-S3) determine if ROM or RAM is accessed by toggling particular circuits. Review this whole piece. I missed the key point @ 30:00

Q (Matthijs): So the access busses are for selecting the right location, and the data busses obtain the information? Is that a correct understanding? A: More or less yes.

Fetching instructions

The chip keeps an instruction pointer (IP), which points to the next instruction to perform. This pointer is put on the address bus, so that that specific address will be selected in either ROM or RAM.

This means that the 8 data lines will encode the selected byte from memory in the case of ROM; for RAM it could also be a write instruction.

Info on the data lines will be available at the CPU at the next clock step.

Decoding and executing an instruction in CPU

Each processor-instruction has a very specific binary code that is called an opcode.

The control unit is in charge of decoding.

Kwisthout: instructions are very simple (yeah right!)

Examples of instructions:

  • ADC (add with carry)
    • Takes information from the processor's accumulator - a register - and adds the information/carry bit from a particular memory location to it and keeps it in the accumulator )
    • 01101001 binary
    • 0x69 hex
  • EOR (takes XOR between what's in the accumulator and a particular memory location)
    • 01001001 binary
    • 0x49 hex

These two instructions will come back. Note that ADC and EOR only differ in a single bit.

This drives a series of logical circuits. Decoding scheme:

b7 b6 b5 b4 b3 b2 b1 b0     bit number
xx xx M  xx S3 S2 S1 S0     M arithmetic/logic
               S0-S3        selection lines

You can think of these selection lines as "toggles" that switch certain circuits in your CPU on or off.

"There is a reason that this has hex code 49, because the corresponding bit pattern toggles a series of switches inside your CPU".

We'll draw that out later.

Adding bits in logic; the full adder

When adding bits we have an overflow bit.

In boolean logic we use an XOR for the S(um) bit, because it's only when either A or B is 1, but not both (because then we have overflow). For the overflow C-bit, we have an AND gate, because there is overflow if we have A and B since only 0 and 1 can be encoded with a single bit.

If we add more bits, we need to include the carry over bit from the previous sum. See slide, this is a full adder because it also takes into account the incoming carry out.

I reconstructed these formulas from the circuit:

Cout = Cin AND (A XOR B) OR A AND B

Which basically says: there is overflow if we have two out of three bits 1.

S = C1 XOR (A XOR B)

Which basically says: we have sum 1 when we only have C1, A, or B; or all of them. Or closer to the formula: when we only have C1, or C1 together with A and B.

We do not want to do this serially though, but do all operations in parallel and compute the carryover effect for all in parallel.

For that, see 202009091419-bit_addition_carry_propagation.md

Arithmetic Logic Unit (ALU)

  • G: (A AND B AND S3) OR (A AND -B AND S2)
    • carry generation
  • P: A EOR ((-B AND S1) OR (B AND S0))
    • carry propagation

They have selector lines built into their formula/circuit, so their behavior can be modified. As you can see, each selector line toggles a subcircuit.

And P and G in turn operate on other subcircuits.

  • M-bit=0; all carry-in bits set to 0.
  • M-bit=1: carry is propagated as normal

If M=1, then we have out = P EOR C.

This amounts to a full adder.

What if we set M=0? Then it degrades to a logical instruction.

At the heart of addition is an XOR. This means that if we take the carry-out into account, we have binary addition. But if we don't, we end up with a regular XOR.

Later comment from Johan:

" On slide 16 you see a 4-bit ALU. Have a look at the formulas for G and P that are realized in the circuit that you see above that. They now include four 'S'-bits. These are not sums, but selection lines that take on the value 0 or 1. Previously we defined P to be (A XOR B) and G to be (A AND B) [XOR and EOR are synonymous]. How can we set S0..S3 to again have the same formula?

For S3 = S0 = 1, S2 = S1 = 0 the circuit effective computes G = (A and B) and P = (A XOR B) !

There is an additional M-switch in the circuit that either (M=0) forces all C's to 0 or that (M=1) doesn't touch the C's. Note that the sum of the bits Ai,Bi = (Ai XOR Bi) XOR Ci, or, P XOR Ci. If C's are forced to 0, the circuit effectively computes bit-wise XORs between A and B. If C's are propagated as normal, the circuit computes A plus B !

See slide 18: the data byte fetched from memory actually drives the circuit. Bits 0-3 form the selection lines. Bit 5 selects carry propagation or carry muting. The other bits define, for example, that the accumulator ('A') needs to be added to some memory contents at a specific address that needs to be fetched ('B'), or that the accumulator needs to be added to an immediate value which is encoded in the next byte, or have yet other functionality. "

So ignoring the C-bits (or not) through the M-bit is what toggles addition.

  • M=1, S3=S0=1, S2=S1=0 -> ADC instruction
  • M=0, S3=S0=1, S2=S1=0 -> EOR instruction

Others:

  • M=0, S3=0, S2=0, S1=0, S0=1 -> OR instruction
  • M=0, S3=0, S2=1, S1=0, S0=0 -> AND instruction
  • M=1, S3=0, S2=1, S1=0, S0=0 -> SBC (subtract with carry) instruction
  • M=0, S3=1, S2=1, S1=1, S0=1 -> NOT instruction

Turing Tumble

Live demo.

Information is both stored in the marbles and in the position of the bits, e.g. "arrow bits".

Neuromorphic architectures

Vs. Von Neumann computational model

We had the Von Neumann model of computation:

  • Physically separated memory and computation
  • Information and computation based on Boolean logic
  • Serial computation (limited parallel computation)
  • Energy demanding
    • Costly heat-generating bottleneck between memory and computation
    • Symmetry in information encoding: 1s and 0s are equal in energy usage.
  • Benefit: well established computational model of Turing machine, with algorithms and developed complexity theory.

Neuromorphic brain-inspired computation:

  • Co-location of memory and computation
  • Information and computation based on spiking neurons
  • Massively parallel computation
  • Energy-lean; 0s are for free, only spikes cost energy.
  • Computational model still in its infancy

In Von Neumann memory and computation are separated, but in neuromorphic architectures this distinction is less clear. Memory and computation are co-located.

This is also interesting w.r.t. energy, because CPU <-> Memory Unit transfer generates a lot of heat. Cooling computers takes a lot of energy.

Von Neumann has symmetry: From the point of logic, 1s and 0s are equal. I.e. the behavior will remain the same if you negate everything. Encoding 1 and 0 is indifferent; they both take the same amount of energy to encode. This does not hold for spikes: a spike takes "1" energy, the absence of a spike nothing.

Different approach: no longer a set of instructions, but setting the parameters of a network so that the right computation is triggered.

You can not only train the network for a certain function like in a traditional machine learning workflow, but you can also program it. Information can be encoded both in the network and in its inputs streams. So there is some flexibility in this. For example, this allows us to simulate certain input in programmed input spiking neurons, which is helpful for abstracting away from actual sensory inputs.

In which sense are they brain-inspired?

Most neuromorphic systems have:

  • Neurons and synapses
  • Co-located memory and computation
  • Simple communication between components
  • Learning inside the components themselves (local learning?)

Additional features:

  • Nonlinear dynamics
  • Spiking behavior
  • Plasticity of components
  • Handle noise or incomplete input
  • High fan-in / fan-out components
    • Q: What is this?
    • "Fan in is a term used to describe the maximum number of inputs which can be given to a logic gate ( logic circuit). For example: A 3-input NAND gate has fan in equal to 3."
    • "Fan out is a term used to describe the maximum number of gates, an ouptut of another gate ( say gate A) can feed i.e how many other gates a single gate can drive. Therefore fan out here is mentioned for gate A, that gate which is giving its output as input to other. In the fig below, fan out of NOT gate is mentioned. Not gate can feed less than 3 gates but maximum number of gates it can feed is 3." source
    • So this is used to enable more parallel computation?
  • Event-driven interactions
  • Low-power systems

They dictate a new way of thinking

  • Learn to use analog behavior instead of using the digital regime
  • Spiking behavior allows for temporal data structures
  • Stochastic behavior of spikes calls for the use of randomized (e.g. sampling-based) algorithms
  • Instead of defining computation instructions, define the appropriate connectivity matrix
  • Requires innovative non-CMOS chip design
  • Employ characteristics of noval materials such as spin glasses, cf Johan Mentink's guest lecture.

Spiking nets

We use the SANDIA model (from Sandia national lab)

SNN=(N,S), with N=neurons, S=synapses

For $i \in N, i=(T_i, R_i, m_i)$ i.e. each neuron has a threshold, reset voltage, and leakage constant.

$S_{a,b}=(d, w)$ i.e. a connection between a pre- and post-synaptic neuron is defined by a delay and a weight.

Algorithms on spiking neural networks

Example: does an array A of natural numbers contain number i?

Three options:

  • Do all computation in the network without external inputs; have fixed programmed inputs instead.
  • Offer a value i that triggers the computation you want to do
  • Offer both value i and matrix A (with fixed size)

The more general the network becomes, the more spikes we need as a lower bound.

 programming_SNN.JPG