Admin Time

It's been a journey...

Digital Logic Topics (in short):

• Boolean Algebra
• Combinatorial Logic Functions
• Digital Electronics - Logic Gates
• Binary Encoding, and 2’s-Complement
• Adders: Half, Full, Ripple Carry
• Arithmetic Logic Unit
• Simple CPU Architecture

Logic gates

All gates can be represented by NAND or NOR.

Twos complement representation

The basic idea: define (binary) negative numbers so the adder works.

How do we make a number negative? Invert bits and add one! Why does that work?

Flip-flops

CPU Architecture

What are the main components of a CPU?

Can you explain what each of these components do?

We come back to this later…

Hardware/Software Interface Topics (in short)

• Structure of an instruction
• Assembly to CPU instructions
• CPU Status Flags (NCZV)
• ARM v7 instructions (adding, subtracting, moving, rotate/shift, bit-wise ops)
• loading and storing from memory
• branch instructions
• Contents of Quick Ref. Card

NCZV Flags

• Negative
• Zero
• Carry
• Overflow

Negative

This status flag is set when the result of an ALU operation is negative if interpreted as a twos complement signed integer

movs r0, 5
movs r1, 6
subs r2, r0, r1

don’t forget the s suffix

Zero

This status flag is set when the result of an ALU operation is zero

movs r5, 5
movs r6, -5
adds r4, r5, r6

Carry

This status flag is set when the result of an ALU operation requires a “carry out” if interpreted as an unsigned 32-bit integer (i.e. it requires 33 or more bits to represent)

movs r2, 0xFF000000
movs r3, 0xFF000000
adds r5, r2, r3

Overflow

This status flag is set when the result of an ALU operation would overflow the min/max value if interpreted as a twos complement signed integer

movs r0, 0x7FFFFFFF @ largest signed integer
adds r0, 1

movs r0, 0x80000000 @ smallest signed integer
subs r0, 1

ARM is a load-store architecture

Instructions are either:

• ALU operations which take inputs and save results to registers, or,
• memory access operations which just save and load from memory

What does this mean for the programmer?

Loading and Storing

Load:

mov r1, 0x20000000 @ put the address in r1
ldr r0, [r1]       @ load the data into r0

Store:

mov r0, 42
mov r1, 0x20000000
str r0, [r1]

Extra Operations

Load less than 32 bits

ldrb @ load byte from register
ldrh @ load halfword from register
strb @ store byte to register
strh @ store halfword to register

Negative Stack

stmdb <Rs>!, {Rgstrs} @ store multiple decrement before
ldmia <Rs>!, {Rgstrs} @ load multiple increment after
push {Rgstrs}
pop {Rgstrs}

Conditional branch examples

beq <label> @ branch if Z = 1
bne <label> @ branch if Z = 0
bcs <label> @ branch if C = 0
bcc <label> @ branch if C = 1
bmi <label> @ branch if N = 1
bpl <label> @ branch if N = 0
bvs <label> @ branch if V = 1
bvc <label> @ branch if V = 0

Functions Main Topics (in short)

• There and back again, bl, bx, and lr
• The stack
• Calling conventions
• Functions calling functions
• Functions calling themselves! (a.k.a. recursive functions)
• Local variables, and the stack frame (incl. sp and fp)
• Relative addressing
• Passing values: by copy and by reference

there, and back again

AAPCS

The ARMv7 Architecture Procedure Call Standard is the convention we’ll (try to) adhere to in programming our microbits

The full standard is quite detailed, but the general summary is:

• r0-r3 are the parameter and scratch registers
• r0-r1 are also the result registers
• r4-r11 are callee-save registers
• r12-r15 are special registers (ip, sp, lr, pc)

Store and Load to the stack

@ Push the value in r2 onto the stack
str r2, [sp, -4]
sub sp, sp, 4

@ Different one-liners for Push
str r2, [sp, -4]!
push {r2}
stmdb sp!, {r2}

@ Pop the value from the "top" of the stack into r3
ldr r3, [sp]
add sp, sp, 4

@ One-liners for Pop
ldr r3, [sp], 4
pop {r3}
ldmia sp!, {r2}

Push and Pop; illustrated

<– Push

Pop –>

Passing by Copy or Reference

Function stack frame

Recursive Functions: Factorial

fact: @ assume input is in r1
  push {lr}
  cmp r1, #1
  beq base_case
  @ recursive case
  push {r1}
  sub r1, #1 
  bl fact @ get fact(n-1)
  pop {r1}
  mul r0, r0, r1 @ calc fact(n-1) * n
  b continue_code

  base_case:
  mov r0, #1
  continue_code:
  pop {lr}
  bx lr

Control Structures Main Topics (in short)

• Conditional branching
• Control Structures in Machine Code:
• if
• while
• for

CPSR table

while loop components

control structures gallery - practice these!

Data Structures Main Topics (in short)

• Arrays
• Structure
• Alignment
• Addressing
• Iterators
• Copying

Add up the numbers in an array

  ldr r0, =array @ base address
  mov r1, 0      @ from_index
  mov r2, 7      @ to_index
@ setup
  mov r3, 0 @ "accumulator" register
  mov r4, 4 @ element size

array_sum:
  mul r5, r1, r4   @ calculate offset
  ldr r6, [r0, r5] @ load from offset
  add r3, r6       @ update accumulator
  add r1, 1        @ increment index
  cmp r1, r2       @ keep looping?
  ble array_sum

Records

Async Main Topics (in short)

• Interrupts & Exceptions: When and Why?
• What happens during an interrupt?
• How is this related to parallel computing?
• Concurrency and Synchronisation
• Race Conditions
• Mutual Exclusion
• Synchronisation (Locks and Semaphores)

Interrupts

One or multiple lines wired directly to the sequencer.

Interrupts: Enables pre-emptive scheduling, timer driven actions, transient hardware interactions, etc…

BUT: A little bit more work to set up, requires external hardware (“interrupt controller”) to encode external requests.

Interrupt Handler

A “normal function”, called when an interrupt is triggered.

The CPU saves the “caller-save” context on the stack, loads lr with special value.

Handler saves “callee-save” context, then runs I/O or time-critical code.

Context Switch

Switch out a program (during an interrupt) without it even noticing!

Race Conditions and Mutual Exclusion

When the sequence or timing of threads of execution has an effect on the outcome.

Can result in bugs! (e.g., in Assignment 3!) What is the value at Count in this code?

Critical Section

What does ARMv7-M give us?

Using a “lock” variable

Networks Main Topics (in short)

• Transmission mediums
• Communications protocols
• Packet switched/circuit switched
• Simplex/duplex
• Topology
• Parallel/Serial
• Timing and Synchronisation
• OSI reference model (7-layers!)

Topology

topology is the way that the nodes are connected to one another (both physically and logically)

there are several different ways to connect the nodes together, each with pros and cons

Serial vs parallel

Synchronous vs Asynchronous

OS Main Topics (in short)

• Operating Systems: Concept
• OS Categories
• OS Architectures
• Processes - what are processes anyway?
• How do OSs handle processes?
• Scheduling

Why do we need operating systems anyway?

What’s an OS? …two main roles

Kernel: definition

the kernel is the program (functions, data structures in memory, etc.) which performs the core role(s) of the OS

access to the CPU, memory, peripherals all happens through the kernel through a system call

Monolithic OS - Modular - μKernels

Process: definition

• a running program
• includes the code (instructions) for the program, and the current state/context:
• registers/flags
• memory (stack and heap)
• permissions/privileges
• other resources (e.g. global variables, open files & network connections, address space mappings)

Mapping processes to CPUs

Architecture Main Topics (in short)

• History of computing architectures
• Harvard vs von Neumann architecture
• Pipelines
• Out-of-order execution
• Vector/SIMD instructions
• Hyper-threading
• Multi-core computing
• Virtual Memory
• Alternative architectures (Parallax Propeller)

A simple CPU

• decoder/sequencer converts instructions into CPU control signals
• arithmetic logic unit (ALU) performs maths & logic operations
• registers provide small, fast storage to the CPU
• flags indicate the states of the latest calculations
• code/data management for loading/storing, caching
• memory

Are any of these components unneccessary?

Simple Pipeline

What can go wrong in a pipeline?

Vector/SIMD vs hyper-threading vs multi-core

What are the differences?

Virtual Memory

Is virtual memory an architecture (hardware) topic or an OS (software) topic?