Please enable JavaScript.
Coggle requires JavaScript to display documents.
old 334 notes (up to lecture - 9, all assembly stuff is using pep/9 not…
old 334 notes (up to lecture - 9, all assembly stuff is using pep/9 not mips)
c++ in assembly(compilation)
variable
at ISA level
is a label for a memory location
at ASL level
live in memory
at HOL level
are defined here
4 types
global
available to everyone and remember things across contexts, global memory is used to hold its value
local
available to current context then lost(live on the stack)
a variable in a function that only exists when that function is being executed
static
available to current context and then remembered
other
available to lower context then lost
named places in memory( single location)
class
block of contiguous memory locations that has addresses of functions inside it
functions
group of statements given a name that is called at some point in the program and then returned from
function call
push actual function parameters(may be 0), push return address(where we go at end of function), push storage for local variables
if an array is a parameter, all elements are pushed consecutively in order starting with 0th element at the top
value passing
pass by value
pass by value of local variable
caller puts them on the stack, callee pops them off the stack(and potentially changes their local name)
pass by value of global variable
function return
usually return 1
returning values
push space for return value, push actual function parameters(may be 0), push return address(where we go at end of function), push storage for local variables
parameters
formal parameters
ones used in function declaration, ex: int sum (int p, int q)
actual parameters
params used in function call ex: sum(a, b)
boolean types
0 = false, anything else = true
arrays
start of many locations of the same type
2 types
global
treated the same as global local variables, global memory is set asside to hold the array elements
local
like local variables, live on the stack, elements stored consecutively starting with 0th element at the top of the stack followed by rest
2 types of memory allocation
dynamic
allocated by application(handled by operating system) released by application(consolidated by operating system)
released dynamic memory can be fragmented/unusable, must be cleaned using garbage collection
static
allocated by compiler, fixed amount allocated prior to execution
pointers
2 types
global
points to a global memory location, requires asterisk to access value at that location (indirect addressing)
local
live on the stack, point to locations in the stack
linked lists
in c++
3 esential components
sequential collection of elements, each with a pointer to another element
last element's pointer set to NULL
a pointer to the first element
translating to assembly
create a struct with pointers to next struct and current struct
create a struct for current element, then update that struct's pointers, enter a value, and store it using the base mem location of the struct + offset, repeat for next elements
structs
group of data elements sharing a common name
data elements can be different types and sizes
2 steps to translating struct to assembly
inputting data
load offset into INDEX register
INPUT a character into the base memory location + offset in INDEX register
outputting data
load offset into INDEX, output base mem location + offset in INDEX reg
cs170
software
program that controls the computer
easier to change than hardware
Implements an algorithm to solve a problem
two kinds:
Application Software
software dealing with user data
makes the computer system accessible to the end user at Level App7
System Software
software dealing with access to limited computer resources
makes the computer accessible to the applications designers
ex:
operating system
responsible for 3 things:
File management
Memory management
OS ensures CPU has access to the correct parts of memory when needed. Even when that memory is not in RAM.
3 different kinds of memory the OS manages
3 more items...
Processor management
manages the CPU's limited resources(registers, cores, i/o paths) to meet user needs and stay productive
common OSs
Unix-based: Mac OS/X, Linux, iOS
Linux-based: Android
Other: Windows
all software
takes inputs, process them, and produce outputs
software analysis
input and processing are known,
output is unknown
software design
input and output are known,
processing is unknown
4 General problem-solving guidelines
› Understand the problem, break into subproblems.
› Outline a solution.
› Solve each part of your outlined problem.
› Test your solution on the computer.
three common components of a computer
Central Processing Unit (CPU)
3 steps in execution
step 1 retrieves data and instructions from main memory
step 2 executes instructions
based on processing
directives that are “hard
coded” into its silicone.
step 3 puts (writes) results to
main memory.
if stored in a file,
it must be loaded from disk to main memory
fetches data/instructions from
CPU memory
16-64 CPU registers
dozens of mem cells
all cpus have 3 things
cache memory
aka
SRAM
two of which define the actual processor
controls
datapaths
aka
processor
types of processors
multicore microprocessors
microprocessor with multiple processors in a single integrated circuit
microprocessors
Main memory
one part of memory in von Neumann architecture
holds 4 things
output data
persistent storage, display, buffers. etc.
pixel
a picture element, which is a single dot on the display, each with its own brightness and color setting, which are configured to from an image on a panel/paper
number of bits required for a display
memory =
numberOfPixels ∗ numberOfComponents ∗
(log numberOfShades/ log 2)
generally expressed in bytes
input data
keyboard, mouse, pens, etc.)
memory-mapped I/O
locations in main memory reserved for input connections and output connections
ex: how the OS manages memory when pressing a key on a keyboard
since keyboards are mapped to main memory, they send info about the key pressed to the input connection in main memory, then the keyboard sends a signal to the CPU telling it a key was pressed. The CPU then fetches the info from the input connection initially sent by the keyboard to main memory. This transfer occurs through the system bus.
I/O modules
special purpose processors
ex:
used to compute color values for individual pixels on a display, instead of the CPU doing it, the CPU sends a signal to the output connections of main memory, which then go to the I/O modules
data
instructions.
volatile
aka
primary memory
two parts
RAM
meaning
Random access memory
ROM
biillions of mem cells
secondary memory
reads/writes directly to main memory using DMAC
DMA
direct memory access
managed by
DMAC
specialled processing units in persistent memory
direct memory access controller
allows input/output directly to/from memory
any means of storing data after PC is powered off
can mean
ROM
hard disk drive
random access, persistent
disk
a single disk can be used with different operating systems and have incompatble file systems (ex: unix and windows)
disk memory
nonvolatile
trillions of memory cells
solid disk drive
100x faster than HDD, 1000x slower than main memory, fully electronic, no mechanical parts
random access, persistent
aka
nonvolatile
no direct communication
between PM & CPU
why?
disk is 100x-1000x slower than CPU
file
collection of bits
file system
handled by
can contain 3 kinds of info
program
algorithm written for execution on a computer, cant be written in English, only in one of the seven languages
program execution time
time = instructions * (cycles/instruction) * (time/cycle)
# of instructions x number of clock cycles to complete an instruction x amount of time in one clock cycle
execution time of a task within a program
The system performance equation
timeToCompleteProgram = numberOfISA3instructions x averageNumberOfMc2instructionsToCompleteOneISA3Instruction x timeToCompleteOneCycle(T=1f, the GHz rating)
where T = period, number of seconds per cycle
f = frequency rating of the CPU
result measured in time per program
ex
1 Suppose your CPU is rated at 2.5 GHz and you execute a program task on your app that requires the execution of 16 million ISA3 instructions. If each ISA3 instruction executes an average of 3.7 Mc2 instructions, what is the execution time of the program task?
[16x10^6]x3.7x[1/(2.5x10^9)]
=23.7ms == 0.024 seconds
data
document
bus
system bus
allows transfer of data to/from cpu, Main memory, persistent memory
collection of wires that allows communication between computer components or between computers
algorithm
set of instructionss that, when carried out in the proper sequence, solves a problem in a finite amount of time, not necessarily made for a computer, can be written in English
ex: a recipe
the two components of time in a computer system
cpu time
cpu clocking
clock frequency
aka
clock rate
measured in
GHz
billion cycles / 1 second
unit of frequency
1 more item...
\(10^9 HZ \)
MHz
\(10^6 HZ \)
\( \frac{1}{\text{(clock period)}} \)
clock period
\( \frac{1}{\text{(clock frequency)}} \)
operation of digital hardware
clock cycles
\(\text{(instruction count)} * \text{(cycles per instruction)} \)
cpu time
time it takes to process something
four formulas
\( \frac{\text{(cpu clock cycles})}{\text{(clock rate)}} \)
\(\text{(cpu clock cycles)} * \text{(cpu cycle time)} \)
\(\text{(instruction count)} * \text{(clocks per instruction)} * \text{(cpu cycle time)} \)
\(\frac{\text{(instruction count)} * \text{(clocks per instruction)} } {\text{(clock rate )} } \)
bandwidth
number of tasks completed per unit of time
bandwidth equation
bandwidth of the channel x transmission time
results measured in bits per second or bytes per second
MB/s != mb/s
ex
A typist is entering some text on a computer keyboard at the rate of 35 words per
minute. How large must the bandwidth of the channel be to accommodate the information flow
between the typist and the computer system? Assume that each word is followed by one space
character, on average.
bandwidth = 3 Gigabits/s
400 Megabytes = 3200 megabits = 3.2 gigabits
3.2 Gb = 3 Gb / 1s * t
t = 3.2Gb/3Gb/1s == 3.2Gb * 1s / 3Gb
t = 1.066 s
A typist is entering some text on a computer keyboard at the rate of 35 words per
bandwidth= information/time
i = b * t
8bits/char * 36 char / (1 min * 60 sec/min)
288bits / 60 seconds
4.8 bits / second
minute. How large must the bandwidth of the channel be to accommodate the information flow
between the typist and the computer system? Assume that each word is followed by one space
character, on average.
Including one space character after each word, the typist enters 36 characters per minute.
bandwidth
high bandwidth == more information transferred per unit of time
low bandwidth == less info transferred per unit of time
component of space in a computer system
computers store/process information
as electrical signals, which are voltage levels inside the electronic circuits, where each signal is either at high voltage level == 1 or low voltage level == 0
bit
smallest unit of digital information
digital meaning
signal stored in memory can have only a fixed number of values
each bit in a computer system occupies space in the circuit comprised of the electronic components that maintain its value
sequence of bits
aka
cell
larger # of bits == wider range of numeric/character values
The number of values stored by a sequence of n bits
2^n
2 more items...
3 common cell sizes
Nibble - collection of 4 bits
Byte - collection of 8 bits
3 more items...
Word - collection greater than a byte
2 more items...
4 types of binary operations
arithmetic
3 more items...
4 Logical binary operations
4 more items...
Rotations
3 more items...
arBITrary collection of sequnetial bits, not the same throughout the computer system
symbol: b
binary digit, as it can only be one of two digits: 0 or 1
have no inherent meaning
code(information storage)
The representation scheme used to store information in memory
4 special CPU bits
NZVC
carry bit
use in signed/unsigned addition when a sum wont fit in the same number of cells as the two binary numbers being added
N = 1 if result is negative, just a copy of sign bit
Z = 1 if result is all zeros
V = 1 if signed integer
overflow, if you add two negs and get a pos, V =1, if you add two pos and get a neg, V=1, same if a dec value is outside the signed range(-8 to 7)
C = 1 if unsigned integer
overflow, if adding two unsigned numbers results in a bin with more cells than the two being added, C =1, same if dec is out of range for those cells
all computers have 5 types of hardware
input device
output device
central processing unit
6 pieces and their symbols
status bits
NZVC
accumulator
A
contains results
index register
X
accesses elements of an array
program counter
PC
location of next instruction
stack pointer
SP
location of free memory
where we are in the program/what values are currently being looked at/stored/popped in memory
instruction register
IR
holds current instruction, determines what the CPU will do
memory
main memory
a consecutive sequence of individually addressble 8 bit cells
lowest memory location
0000
highest memory location
FFFF
bus
set of parallel wires all components connect to
5 steps of data flow
input device puts data on the bus when told
output device takes data off bus when told
cpu puts data onto the bus and takes data from the bus, while controling the bus
memory gets data from the bus and puts data onto the bus when told by cpu
bus transports data
4 base systems in cs
hexadecimal(hex)
decimal to hexadecimal
divide by 16, track dividends and remainders, convert to dividends and remainders to their hex equivalents, then place remainers in order from last to first, youre done when you reach a value with a hex equivalent, the last one is converted to its hex equivalent
ex: 46 to hex
46/16 = 2 remainder 14 E
2 base 16 = 2
46 = 2E
place in order from
last->first
0-F
0 0 0000
1 1 0001
2 2 0010
3 3 0011
4 4 0100
5 5 0101
6 6 0110
7 7 0111
8 8 1000
9 9 1001
A 10 1010
B 11 1011
C 12 1100
D 13 1101
E 14 1110
F 15 1111
hex to bin
convert each hex char into its 4 bit equivalent
ex
5F
=
0101 1111
hex to decimal
convert each letter into its decimal equivalent, then do \(16^{position} * \) position value
ex
8BE7
= 8(11)(14)7
= 16^3 * 8
+16^2 *11
+16^1 * 14
+ 16^0 * 7
35,815
decimal(dec)
decimal to binary
binary(bin)
0-1
bin to dec
\(2^{position} *\) position value
ex: 101101
2^0 * 1
+2^1 * 0
+2^2 * 1
+2^3 * 1
+2^4 * 0
+2^5 * 1
1+
0+
4+
8+
0+
32
=
45
bin to floating point number
\(2^{position - numberOfPositionsRightOfDecimal } *\) position value
mantissa
everything right of the decimal point
ex:
for two kinds of numbers
integer to binary
divide by 2, track dividends & remainders, place remainders in order from last to first, youre done when you reach a value with a binary equivalent, the last one is converted to its binary equivalent
ex: 22
5/2 = 2, Remainder: 1
2/2 = 1, Remainder: 0
1/2 = 0, Remainder: 1
= 10110
double check:
0x2^0 + 1x2^1 + 1x2^2 + 0x2^3 + 1x2^4 + 0x2^5
2+4+16=22
11/2= 5, Remainder: 1
22/2 = 11, Remainder: 0
floating point to binary
same as integer, but binary positions right of decimal point = \(1/(2^{positionRightOfDecimal}) \)
ex:
5.375
5 = 101
0.375 < 1/2(0.5), = 0
0.375 > 1/4 (.25) = 1
0.375 - 0.25 = 0.125
0.125 = 1/8 (.125) = 1
101.011
0-9
octal(oct)
0-7
decimal to octal
ex: 46
46/8 = 5 remainder 6
46 base 8 = 56
double check
\(8^1 * 5 = 40\)
\(8^0 * 6 = 6\)
40+6 = 46
RTL
10(really 5) symbols
OR \( \vee \)
AND \( \wedge \)
XOR \(\oplus \)
NOT \(\neg \)
Implies \(\Rightarrow \)
Transfer \(\leftarrow\)
Bit Index \( \langle \rangle \)
Informal description { }
sequential separator \(;\)
concurrent separator \(,\)
syntax
bit places:
c most significant bit
0 = second to most significant bit
least significant bit = higher index number
C 0 1 2 3 4 5
only left arrows
bit index \(\langle\) lowest (most significant/leftmost) \(..\) highest(least significant/rightmost) \(\rangle\)
ex: 6 bit ROL
\(c \leftarrow r \langle 0 \rangle \) , \(r \langle 0..4 \rangle \leftarrow r \langle 1..5 \rangle ,c \leftarrow r \langle 5 \rangle\)
ex: ROR
\( r \langle 5 \rangle \leftarrow c \), \(r \langle 1..5 \rangle \leftarrow r \langle 0..4 \rangle c \leftarrow r \langle 0 \rangle\)
register transfer language
instructions
two dominant computer systems
reduced instruction set computer
ARM
meaning
advanced risc machine
aka
RISC
complex instruction set computer
x86
made by 2 companies
Intel
AMD
advanced micro devices
aka
CISC
2 types of instructions
unary
1 part
instruction specifier
ex
STOP
non unary
2 parts
instruction specifier
operand
which is
data used by the instruction, a memory location
does something with the contents of the memory location used as an operand
ex
LOAD, STORE, ADD, SUBTRACT, AND, OR< INVERT, NEGATE, LOAD BYTE, STORE BYTE, CHARACTER INPUT, CHARACTER OUTPUT
instruction execution order
not wired into the CPU, determined by a program written in machine language
machine code instructions hard wired into cpu chip
cpu chip
aka
integrated circuit
device that combines dozens to millions of transistors
types of chips
4 common types of character encoding
ascii
7 bit
american standard for computer information exchange
extended ascii
8 bit
unicode
16 bit
unicode 2.0
24 bit
3 kinds of binary number representation
binary coded decimal
each decimal digit gets its own nibble
gray code
adjacent values are separated by exactly one bit
non zero return
bits only change state if the original bits change
von neumann execution cycle
6 steps
2 initialize cpu
meaning
initialize program counter and stack pointer
3 fetch next instruction
4 decode instruction specifier
5 find address of next instruction
meaning
increment PC
execute instruction, return to step 3 unless STOP
initialize memory
benefits
drawbacks
translator
3 types
compiler
a program that does one of 2 things
converts HOL into assembly level code for another program to translate into machine code
aka
high order language level to assembly level
converts high order language directly into machine code
aka
high order language level to instruction set architecture level
requires
ABI
two parts
operating system interfaces used by application programmers
user portion of instruction set
defines how compiler translates source to machine code
assembler
converts assembly code to machine code
interpreter
converts each source code directly to machine code one line at a time
aka
language processors
any type of program that converts code from one language to another
random access
types of memory
sequential access
to get information at the other end of the disk, you must traverse all the data between the beginning and the end
sequential access memory
SAM
ex:
magnetic tape
to get information from any location in ram does not require you to traverse the information held between each location
pn\(\mu\)m kMGTB
conversions
+/- ^3
+/- 1024
+/-
scientific notation
normal form to binary
sign | coefficient | exponent | base
coefficient
aka
mantissa
significand
decimal is always in same location, no bit is used to store it
most significant bit is always 1, therefore never stored
convert
aka normal form
IEEE 754 floating point standard
two sizes
single precision
1 sign bit | 8 exponent bits | 23 mantissa bits
32 bit
\(2^{-149}\)
double precision
1 sign bit | 11 exponent bits | 52 mantissa bits
64 bit
\(2^{-1074}\)
special values
negative infinity
1 11111111 0....
sign bit 1 exponent bits all 1s coeffiicient bits all zeros
positive infinity
0 11111111 0...
sign bit 0 exponent bits all 1s coeffiicient bits all zeros
not a number
aka NaN
0/1 11111111 not all zeros
exponent bits all 1s coefficient bits anything but all zeros,
c++ variable sizes
int
2's complement integer
char
8 bit ascii character
von neumann architecture
3 components
machine composed of memory
memory composed of bits
program instructions and data share memory
5 aspects
data and instructions are indistinguishable
programs can modify themselves
programs can recreate themselves
programs can completely disappear
not limited to computers
Assembly Addressing modes
8 types
Direct -
the OprndSpec points to a memory location that contains the Oprnd
001 | d | MEM [oprndspec]
iNdirect -
the OprndSpec is an index to an index based on a memory location that
contains the Oprnd
010 | n | Mem [mem [oprndspec] ]
Stack-relative
the OprndSpec is located relative to the current SP memory location
011 | s | Mem[SP + oprndspec]
Stack-relative-deFerred
similar to indirect but using the SP
indirect[[SP+]]
100 | sf | Mem[Mem[SP + oprndspec]]
IndeXed
OprndSpec is offset from another location in memory that contains the Oprnd
101 | x | Mem[oprndspec + X]
Immediate
the Oprnd is the OprndSpec
000 | i | [oprndspec]
Stack-indeXed -
similar to stack-relative, but
based on a value already on the stack
stack relative [... + X]
011 | sx | Mem[SP + oprndspec + X]
Stack-indexed-deferred
similar to indirect
but using the previous stack-relative to start
indirect [ [ ]+X ]
111 | sxf | Mem[Mem[SP + oprndspec] + X]
assembly mnemonic
2 parts
the mnemonic itself
operand specifier
aka
oprndspec
optional
ex
ABI
two parts
user portion of instruction set
operating system interfaces used by application programmers
defines how compiler translates source to machine code
types of storage
volatile
only retains data if it is currenlty receiving power
non-volatile
retains data even when its not receiving power
7 levels of abstractions for a computer system
7 Application Level
6 High-order language level
5 Assembly level
4 operating system level
3 instruction set architecture level
2 microcode level
1 logic gate level
and their corresponding languages
Level 7 (App7): Language dependent on applications program
Level 6 (HOL6): Machine-independent programming language
languages
Java
general-purpose and web applications
Python
scripting language for web applications
C++
general applications
C
programming operating systems
added object-oriented features
HOL 6 example statement
i = j + k
Level 5 (Asmb5): Assembly language
Level 4 (OS4): Operating system calls
Level 3 (ISA3): Machine language
one instruction
equivalent to several Mc2 level instructions
programs are downloaded as sets of instructions at this level
Level 2 (Mc2): Microinstructions and register transfer
one instruction
requires one cycle to execute
Level 1 (LG1): Boolean algebra and truth tables
3(7) levels of program code
high-order language level
assembly level
machine level
operating system level
instruction set architecture level
microcode level
logic gate level
systems and software quality requirements and evaluation (SquaRE) products model
6 -y's of code
maintainability
how hard to modify
functional suitability
does it satisfy our needs
compatibility
does it work with other code
usability
is it easy to use
reliablity
can it perform for a while
portability
is it easy to host elsewhere
