cse 3430 final

main components of a computer

memory, processor, input, output

smallest unit of memory

bit

bit string

collection of bits

what is stored as bit strings

everything

how many values encoded by n bits

2^n

how is memory organized in a computer

sequence of words as an array

word of memory

string of bits; usually 32 or 64

are words the same size in every system

no; definition not consistent

byte

8 bits

definition of byte universal?

yes

B2D

method for encoding unsigned integers; similar to decimal system where each spot has a value of 2^n; universal for unsigned integers

range of values with B2D

0 to 2^n - 1

B2S

first bit is sign (1 is negative, 0 is positive) and the rest are the magnitude using normal B2D

B2T

two's complement; to negate (or unnegate a value) flip all the bits and add 1

B2O

one's complement; to negate (or unnegate) flip all the bits

range of values with B2T

-2^(n-1) to 2^(n-1) - 1

adding B2D

add like normal with carries; overflow occurs if the carry flag is 1; first carry always 0

adding B2T

add like normal with carries; overflow occurs if the MSB and second MSB do not match so overflow flag is 1; use first carry of 0

adding B2O

use AND gate on MSBs; if both negative then use first carry of 1; if both positive then use first carry of 0; if one negative and one positive then who knows what to do

overflow flag determination

use XOR gate on MSB and second MSB

subtraction B2T

keep first operand normal, flip second operand, add 1 to first carry (equivalent of just negating the second operand using B2T)

IEEE 754 single precision

32 total bits; 1 bit sign (1 is negative, 0 is positive); 8 bit biased exponent (subtract from 127 to get true exponent); 23 bit mantissa (implied 1 and then what is right of the decimal in binary)

steps to convert IEEE 754 single precision

1. decode
2. calculate true exponent
3. rewrite as exponent from binary
4. calculate decimal value in decimal (binary number divided by 2^(total number of decimal spaces))

value when true exponent is negative

between -1 and 1

trade off when using IEEE 754

precision because must assume that it can be represented by a fraction in binary (denominator is 2^(something))

ASCII encoding

8 bits but first bit always 0, so only 7 bits for the actual encoding; latin alphabet and numbers and symbols; 2^7 total characters

UTF8 encoding

not all characters same number of bytes; each character can be 1 to 4 bytes; not all bits used for encoding, other bits are used to signal how many bytes the character is

parity and MSB in ASCII

because first bit of ASCII always 0, when sending it will be the "parity bit"; changed so that the total number of 1s in the byte is always even; also applied horizontally in multi byte sends; the system will no something was sent wrong if the number of 1s is not even

can hardware (CPU) tell what data is encoded in a bit string just by looking

nope

size of an address

typically 32 bits

word aligned vs unaligned access of data in memory

* word aligned access = only data at "word divisible" addresses can be accessed (i.e. increments of 8 bytes if one word is 8 bytes)
* unaligned access = data at every byte address can be accessed

subparts of the CPU

control flow, ALU, registers

four types of instructions all CPUs can perform

data movement, ALU, control, IO

reads and writes with memory

* read = retrieve content at designated memory address
* write = overwrites content at designated memory address with data given by CPU

which register holds the address of the instruction being executed

program counter PC

which register holds the instruction being executed

instruction register IR

what kind of program converts assembly to machine

assembler

RISC vs CISC

* RISC = reduced instruction; one word instructions; all arithmetic must be performed in registers
* CISC = complex instruction; can have multi-word instructions; can have ALU operands (arithmetic outside of registers)

what are Intels and ARMS

Intels are CISC and ARMS are RISC

which processor architecture is load/store

RISC b/c all memory access must be completed through registers

how many assembly language instructions correspond to a single high-level language statement

4

when can the PC be incremented

after the next instruction is fetched / once the next instruction begins execution

if or else (or loop) statements

use branches / jumps

processor status register PSR

contains flags that depend on the last ALU instruction

fours flags in PSR

* sign flag SF = 1 if negative
* zero flag ZF = 1 if 0
* carry flag CF = 1 if carry
* overflow flag OF = 1 if overflow

labels in assembly language

mark addresses; where data is stored or where a branch / jump destination is located

do labels occupy space in memory

no they are symbolic markers and are replaced by the actual address (bit string) in machine language

built in data structures recognized by CPU

none

subroutine (function) in assembly

block of instructions that may be called, sometimes multiple times

subroutine call different from branch

branch doesn't need a return address

how can the return address be saved

link register or on the stack

link register limitation

only "one deep" subroutine calling because the return address will be overwritten

what other data gets put onto the stack for a subroutine call

parameters (last to first), return address, local variables of subroutine, starting address of caller's stack frame

interrupt subroutine

interrupt service routine ISR code in the OS

UART

universal asynchronous receiver transmitter

UART registers

* RValue = contains the value from the outside world
* RStatus = contains 1 if there is a new/unread value in RValue

without interrupt UART programming

makes CPU sit in a wait loop just constantly checking RStatus for any updates

raising an interrupt

interrupt signal sent (from disk drive, UART, ...), interrupt controller notifies CPU, CPU saves the PC and all other registers, CPU transfers control to ISR

when does the CPU check for interrupts

at the end of each instruction execution, but a part of the instruction still

how does ISR know where to return

CPU saves PC (return address) to memory before transferring control

how does OS make sure ISR isn't interrupted

bit flag in PSR to disable interrupts; they will "buffer" until CPU can process them

assembly instructions per machine instruction

1

does every CPU use the same assembly language

no

what real CPU is Y86 based on

Intel X86-64

instruction set architecture ISA

the programmer visible machine interface; part of the hardware the programmer can "see"

how many Y86 registers

15; omit %r15

conditions codes in Y86

3 condition codes (flags); SF, ZF, OF

kinds of operands in Y86

only signed; that's why no CF

size of operands in Y86

64 bits

size of addresses in Y86

64 bits

big endian vs little endian

* big endian = stores MSB at lowest address and LSB at highest address
* little endian = stores MSB at highest address and LSB at lowest address

what endian is Y86 and Intel

little endian

four data movements in Y86

* rrmoveq = register to register
* irmoveq = immediate to register
* mrmoveq = memory to register
* rmmoveq = register to memory

source operand read, written in Y86?

only read

destination operand read, written in Y86?

* for ALU: read and written
* for data movement: only written

immediate operand in Y86

constant

address expressions for memory operands in Y86

DISP(BASE) where BASE is a register containing an address in memory and DISP is how much to decrement or increment BASE address by to get to the address wanted

four ALU in Y86

* addq = first + second into second
* subq = second - first into second
* andq = first AND second into second (bit by bit)
* xorq = first XOR second into second (bit by bit)

unconditional jump instruction in Y86

PC will have address of the destination

what two things does the call instruction in Y86 do

1. push return address on the stack
2. write address of Dest label to PC

what two things does the ret instruction in Y86 do

1. pop the return address from the stack
2. write it to the PC

portion of stack for each subroutine

called a frame; goes from rbp base pointer to rsp stack pointer

why does each subroutine save calling rbp before sets its own base/frame pointer

so it may reset the rbp and return to the caller's stack frame once the subroutine is complete

how does the stack grow

downward in memory; towards lower number addresses

push and pop instructions in Y86

* pushq = puts value onto stack by decrementing rsp and then writing the value to rsp
* popq = takes value off the stack by reading the value in rsp and then incrementing rsp

how are parameters passed on the stack in Y86

last to first before the function is called (so they are above the subroutine's base pointer)

last thing pushed on the stack when a subroutine is called

return address

two inputs and two outputs of half adder

* two inputs = x and y
* two outputs = sum and carry

three inputs and two outputs of full adder

* inputs = x, y, and carry-in
* outputs = sum and carry-out

what is a decoder used for

used to select a memory word, given the address

decoder has n inputs, how many outputs

2^n

how many output lines of a decoder can have the value 1

only one

what is a multiplexor used to do

reverse of a decoder; selects one output from the inputs depending on the control lines

how many control lines for a multiplexor with n inputs

log_2(n)

combinational circuit vs sequential circuit

* combinational = only relies on current inputs, has no memory
* sequential = relies on current inputs and past, has memory

what circuit is used to implement memory

combinational

what circuit are full adders, multiplexors, and decoders

combinational

what circuit uses a clock input

sequential

what combination of SR must be prevented

1-1 because makes the circuit unstable (output is unknown)

SR to D gate

S is D and R is ~D (not S)