COMP2300/6300
Computer Organisation and Program Execution
Dr Semester 1, 2022
Copyright By PowCoder代写 加微信 powcoder
Week 12: Revision!
It’s been a journey…
Tour of the topics
A few questions from each major topic
Advice for exams Open Questions
What was this course about again?
Digital Logic
Digital Logic Topics (in short):
Boolean Algebra Combinatorial Logic Functions
Digital Electronics – Logic Gates
Binary Encoding, and 2ʼs-Complement Adders: Half, Full, Arithmetic Logic Unit
Simple CPU Architecture
Logic gates
1. how many bits can be added together? 2. how long does it take?
3. where does the final carry bit go?
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
Whatʼs the di erence between Boolean algebra, combinational logic, and sequential logic?
Why do we need all three of these things to describe computers? Are there parts of the story missing from COMP2300?
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/So ware Interface
Hardware/So ware Interface Topics (in short)
Structure of an instruction Assembly to CPU instructions
CPU Status Flags (NCZV)
ARM v7 instructions (adding, subtracting, moving, rotate/shi , bit-wise ops) loading and storing from memory
branch instructions
Contents of Quick Ref. Card
What is the hardware/so ware interface? Why do we call it this?
why do we need both immediate and register versions of some instructions?
NCZV Flags Negative
Carry Overflow
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 su ix
This status flag is set when the result of an ALU operation is zero
movs r5, 5
movs r6, -5
adds r4, r5, r6
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
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
movs r0, 5
movs r1, 6
subs r2, r0, r1
What flags will be set a er the subs instruction is executed?
Can you think of a use case for each shi and rotation instruction?
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
mov r1, 0x20000000 @ put the address in r1
ldr r0, [r1] @ load the data into r0
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
ldmia
push {Rgstrs}
pop {Rgstrs}
Conditional branch examples
beq
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
A function call
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]!
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
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
cmp r1, #1
beq base_case
@ recursive case
sub r1, #1
bl fact @ get fact(n-1)
mul r0, r0, r1 @ calc fact(n-1) * n
b continue_code
base_case:
mov r0, #1
continue_code:
Control Structures
Control Structures Main Topics (in short)
Conditional branching
Control Structures in Machine Code:
if while for
CPSR table
ne not equal cs carry set cc carry clear
mi minus/negative
pl plus/positive
vs overflow set
vc overflow clear
hi unsigned higher
ls unsigned lower or same ge signed greater or equal lt signed less
gt signed greater
le signed less or equal
flags Z=1 Z=0 C=1 C=0
C=1 ∧ Z=0 C=0 ∨ Z=1 N=V
Z=0 ∧ N=V Z=1 ∨ N≠V
while loop components
control structures gallery – practice these!
Which control structures were useful for your assignments?
Is there anything you can do in assembly that goes beyond “typical control structures”?
Make up a loop or if-then-else block in Python or Java.
How quickly can you translate it into ARM assembly? How do you know you answer is correct?
Data Structures
Data Structures Main Topics (in short) Arrays
Alignment Addressing Iterators Copying
How do we know how big an array is in memory?
Is it possible to write outside the bounds of the array?
Can you make an array where the size can be changed? (mutable array?)
How do we address a particular element in an array?
Add up the numbers in an array
ldr r0, =array @ base address
mov r1, 0 @ from_index
mov r2, 7 @ to_index
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
cmp r1, r2
ble array_sum
@ update accumulator
@ increment index
@ keep looping?
Whatʼs the di erence between an array and a record?
Imagine you are creating a Point-of-Sale system (cash register) using a microbit. What data structures might be required?
Asynchronism, Interrupts, and Concurrency
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)
Whatʼs an interrupt? Why are they necessary?
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!
Whatʼs problems can occur when running concurrent programs? What are the possible solutions?
How does the “too much milk” problem help us understand this issue?
Race Conditions and Mutual Exclusion
When the sequence or timing of threads of execution has an e ect 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
Semaphores
A semaphore (Dijkstra, 1968) is a generalisation of our lock to handle common resources more generally.
We define a semaphore variable (S), and two operations: Wait(S): if S > 0, then S := S – 1 and continue, else wait Signal(S): S := S + 1, tell someone waiting to try again
So S could start at 1 (binary) or a higher number.
Implementing a semaphore
Whatʼs a race condition? What can we do about it?
Whatʼs mutual exclusion?
Can this be achieved on a microbit? How would you do it?
Networks Main Topics (in short)
Transmission mediums Communications protocols
Packet switched/circuit switched Simplex/duplex
Parallel/Serial
Timing and Synchronisation OSI reference model (7-layers!)
How many transmission mediums can you name?
If you were stuck on a desert island what transmission media could you use to send a message for help?
What is a communications protocol?
Why would it be needed? Explain your answer.
topology is the way that the nodes are connected to one another (both physically and logically)
there are several di erent ways to connect the nodes together, each with pros and cons
Serial vs parallel
serial parallel
data is sent one-bit-at-a-time multiple bits sent simultaneously (e.g. multiple wires) fewer bits sent per signal, but simpler need to keep all the connections in sync
Synchronous vs Asynchronous
synchronous asynchronous
transitions on a clock line (independent) timers at each end
no clock skew issues, but requires an no extra connections required, but more vulnerable to
extra connection synchronisation issues
How does the P2300 protocol fit into the OSI layer diagram?
Operating Systems
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
virtual machine
provides friendly & safe environment memory management
hardware abstraction process management inter-process comms (IPC)
resource manager
coordinates access to resources processors
mass storage
communications channels
devices (timers, GPUs, DSPs, peripherals…)
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
Why are kernels and (user) programs separate?
How are they di erent? Arenʼt they both programs?
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
Architecture Main Topics (in short)
History of computing architectures Harvard vs von Neumann architecture
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
What are the main components of a CPU? What do they do? Are any components unnecessary?
Simple Pipeline
What is a CPU instruction pipeline and why would it be used? Explain how it is possible to construct one.
Vector/SIMD vs hyper-threading vs multi-core
what is the di erence between Vector/SIMD, hyperthreading, and multi-core architectures? What workloads benefit from each one?
Virtual Memory
Is virtual memory an architecture (hardware) topic or an OS (so ware) topic? Explain reasons for both points of view.
Parallax Propeller
What are the benefits of having many physical CPU cores? What problems could arise in practice?
Alternative Architectures
What alternative architectures are possible for computing?
Finally done. That was epic, thanks for coming with me everybody!
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com