Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Fall 2017 > CSCI 223 Midterm 2 > Flashcards

CSCI 223 Midterm 2 Flashcards

1
Q

3 mechanisms in procedures

A
  1. passing control (call, return)
  2. passing data (using either registers or memory)
  3. memory management (stack - allocate/deallocate)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

x86-64 stack grows toward

A

lower memory addresses (down)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

register ? contains address of top of stack

A

%rsp

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

stack operation: pushq Src

A

fetch (read) operand at Src), decrememt %rsp by 8 (or 4 on 32-bit), write operand at address given by %rsp

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

register ? contains address of the frame pointer

A

%rbp

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

stack operation: popq Dest

A

read value at address given by %rsp, increment %rsp by 8 (or 4 on 32-bit machine), store value at Dest (must be register)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

procedure control flow

A

use stack
procedure call: push return address on stack, jump to label
procedure ret: pop address from stack, jump to address

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

return address

A

address of the next instruction right after call

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

return value

A

%rax (64-bit) or %eax (32-bit)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

stack allocated in ?

A

frames (state for single procedure instantiation)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

contents of stack frames

A

return information, local storage (if needed), temporary storage (if needed)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

management of stack frames

A

space allocated when enter procedure (“set-up” code; includes push by call instruction) and deallocated when return (“finish” code; includes pop by ret instruction)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

we create a new stack frame when

A

we enter a new function

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

calling conventions

A

caller saved and callee saved

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

caller saved

A

caller saves temporary values in its frame before the call

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

callee saved

A

callee saves temporary values in its frame before using, then restores them before returning to caller

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

%rax is the ?, ?-saved, and can be modified by ?

A

return value, caller-saved, procedure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

%rdi…%r9 are the ?, ?-saved, and can be modified by ?

A

arguments, caller-saved, procedure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

%r10, %r11 are ?-saved, and can be modified by ?

A

caller-saved, procedure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

%rbx, %r12, %r13, %r14 are ?-saved, and can be modified by ?

A

caller-saved, callee must save and restore

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

%rbp is the ?, ?-saved, and can be modified by ?

A

frame pointer, callee-saved, callee must save and restore

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

%rsp is the ?, ?-saved, and can be modified by ?

A

stack pointer, callee-saved (special form), restored to original value upon exit from procedure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

recursion is handled by ? calling conventions

A

normal (in the use of the stack)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

char/unsigned char

A

1 byte

2^8 (256) numbers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

short/unsigned short

A

2 bytes

2^16 numbers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

int/unsigned int

A

4 bytes

2^32 numbers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

long/unsigned long

A

8 bytes

2^64 numbers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

integer encoding standards: unsigned integers

A

like converting binary to decimal: the sum of the number (0 or 1) times 2^i

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

integer encoding standards: two’s complement for signed integers

A

first bit is a sign bit (0 = non-negative, 1 = negative) in addition to a value, converting the rest is like binary to decimal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

to find the negative version of an integer

A
  1. find bit pattern for positive version
  2. flip all bits
  3. add 1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

for a 16-bit integer, UMax (unsigned)

A

0xFFFF = 2^16-1 (need to know context to know difference between -1 and 2^16-1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

for a 16-bit integer, TMax (signed)

A

0x7FFF = 2^15-1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

for a 16-bit integer, TMin (signed)

A

0x8000 = -2^15

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

for a 16-bit integer, -1

A

0xFFFF = -1 (need to know context to know difference between -1 and 2^16-1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

for a 16-bit integer, 0

A

0x0000 = 0 (always all zeroes for signed and unsigned)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

the size of TMin is equal to

A

TMax + 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

the size of UMax is equal to

A

2*TMax + 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

equivalence of unsigned/signed numeric values

A

same encodings for nonnegative values

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

uniqueness of unsigned/signed numeric values

A

every bit pattern represents a unique integer value; each representable integer has a unique bit encoding

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

constants by default are considered to be ? integers unless

A

signed; U as suffix

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

sign extension

A

given w-bit signed integer x, convert it to w+k bit integer with same value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

rule for sign extension

A

make k copies of sign bit

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

floating point numbers

A

encode rational numbers of the form v = x*2^y

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

standard for representing floating point numbers (but not all)

A

IEEE 754

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

single-precision for IEEE 754

A

32-bit

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

double precision for IEEE 754

A

64-bit

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

IEEE 754 sign bit is

A

MSB

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

IEEE 754 next set of bits

A

exp

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

IEEE 754 last set of bits

A

frac

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
50
Q

IEEE 754 formula

A

(-1)^s (1.frac) 2^(exp - bias)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
51
Q

divide by two by shifting

A

right

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
52
Q

multiply by two by shifting

A

left

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q

IEEE 754 single precision bit allocation

A

sign bit = 1 bit
exp = 8 bits
frac = 23 bits

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
54
Q

IEEE 754 double precision bit allocation

A

sign bit = 1 bit
exp = 11 bits
frac = 52 bits

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
55
Q

normalized values for IEEE 754

A

when exp =/= 000…0 or 111…1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
56
Q

bias for exp

A

2^(k-1) - 1

57
Q

bias for exp for 32 bit, 64 bit

A

127, 1023

58
Q

denormalized values for IEEE 754

A

exp = 000…0

cases:
frac = 000…0 represents zero value (+0, -0 depending on sign bit)
frac =/= 000…0 represents numbers very close to 0.0

59
Q

special values for IEEE 754

A

exp = 111…1

cases:
frac = 000…0 represents infinity (both positive and negative depending on sign bit)
frac =/= 000…0 represents Not-a-Number (NaN; when no numeric value can be determined)

60
Q

IEEE 754 zero

A 
exp = 00...00
frac = 00...00
61
Q

IEEE 754 smallest positive denormalized

A 
exp = 00...00
frac = 00...01
62
Q

IEEE 754 largest denormalized

A 
exp = 00...00
frac = 11...11
63
Q

IEEE 754 smallest positive normalized

A 
exp = 00...01
frac = 00...00
64
Q

IEEE 754 one

A 
exp = 01...11
frac = 00...00
65
Q

IEEE 754 largest normalized

A 
exp = 11...10
frac = 11...11
66
Q

floating point zero is (the same/different from) the integer zero

A

the same

67
Q

rounding modes

A

towards zero, round down (towards -inf), round up (towards +inf), nearest even (default)

68
Q

int to double conversion

A

exact conversion, as long as int has <= 53 bit word size

69
Q

int to float conversion

A

will round according to rounding mode

70
Q

double/float to int conversion

A

truncates fractional part, like rounding toward zero; not definite when out of range or NaN

71
Q

key features of RAM

A

traditionally packaged as a chip, basic storage unit is normally a cell (one bit per cell)

72
Q

RAM stands for

A

Random-Access Memory

73
Q

static RAM (SRAM)

A

used for cache; each cell stores a bit with a four or six-transistor circuit; retains value indefinitely, as long as it is kept powered; relatively insensitive to electrical noise (EMI), radiation, etc.; faster and more expensive than DRAM

74
Q

dynamic RAM (DRAM)

A

used for main memory; each cell stores bit with capacitor; one transistor per bit; value must be refreshed every 10-100ms; more sensitive to disturbances than SRAM; slower and cheaper than SRAM

75
Q

DRAM and SRAM are ? memories

A

volatile (lose info if powered off)

76
Q

nonvolatile memories + examples

A

retain value even if powered off (ROM, PROM, EPROM, EEPROM, flash memory)

77
Q

ROM

A

read-only memory; programmed during production

78
Q

PROM

A

programmable ROM; can be programmed once after manufacturing

79
Q

EPROM

A

erasable PROM; can be bulk erased (UV, XRay)

80
Q

EEPROM

A

electronically erasable PROM; on our system; electronic erase capability

81
Q

flash memory

A

EEPROMs with partial (sector) erase capability; wears out after about 100,000 erasings

82
Q

uses for nonvolatile memories

A

firmware programs stored in ROM, solid state disks, disk caches

83
Q

bus

A

a collection of parallel wires that carry address, data, and control signals; typically shared by multiple devices

84
Q

memory read transaction

A

movl A, %eax
CPU places address A on the memory bus
main memory reads A from the memory bus, retrieves word x, and places it on the bus
CPU reads word x from the bus and copies it into register %eax

85
Q

memory write transaction (more complicated)

A

movl %eax, A
CPU places address A on bus; memory reads it and waits for the corresponding word to arrive
CPU places data word y on the bus
main memory reads data word y from the bus and stores it at address A

86
Q

explain the power wall

A

CPU clock rates increase up to 2003, then drop because the number of cores was increased in exchange for lower speed to save power

87
Q

the CPU-memory performance gap

A

widens between DRAM, disk, and CPU speeds; the key to bridging this gap is locality

88
Q

locality

A

programs tend to use data and instructions with addresses near or equal to those they have used recently

89
Q

temporal locality

A

recently referenced items are likely to be referenced again in the near future

90
Q

spatial locality

A

items with nearby addresses tend to be referenced close together in time

91
Q

referencing array elements in succession is an example of ? locality

A

spatial

92
Q

referencing the variable “sum” in each iteration is an example of ? locality

A

temporal

93
Q

referencing instructions in sequence is an example of ? locality

A

spatial

94
Q

cycling through a loop repeatedly is an example of ? locality

A

temporal

95
Q

stride

A

the distance between two consecutively accessed addresses (e.g. stride-N, stride-1)

96
Q

CPU registers hold ? retrieved from ?

A

words; L1 cache

97
Q

L1/L2 cache holds ? retrieved from ?

A

cache lines; main memory

98
Q

main memory holds ? retrieved from ?

A

disk blocks/”page” local disks

99
Q

local disks hold ? retrieved from ?

A

files; disks on remote network servers

100
Q

memory hierarchy

A

registers, L1 cache, L2 cache, main memory, local secondary storage, remote secondary storage

101
Q

cache

A

a smaller, faster storage device that acts as a staging area for a subset of the data in a larger, slower device

102
Q

fundamental idea of memory hierarchy

A

for each k, the faster, smaller device at level k serves as a cache for the larger, slower device at level k+1

103
Q

why do memory hierarchies work?

A

because of locality, programs tend to access the data at level k more often than they access the data at level k+1. thus, the storage at level k+1 can be slower, and thus larger and cheaper per bit

104
Q

big idea of memory hierarchy

A

creates an illusion of a large pool of storage that costs as much as the cheap storage near the bottom, but that serves data to programs at the rate of the fast storage near the top

105
Q

cache hit

A

data block b is needed and found in the cache

106
Q

cache miss

A

data block b is needed, not found in the cache, fetched from memory, then stored in cache

107
Q

types of cache misses

A

cold (compulsory), conflict, capacity

108
Q

cold/compulsory cache miss

A

occurs because the cache is empty

109
Q

conflict cache miss

A

occur when the level k cache is large enough, but multiple data objects all map to the same level k block

110
Q

capacity cache miss

A

occurs when the set of active cache blocks (working set) is larger than the cache

111
Q

cache memories

A

small, fast SRAM-based memories managed automatically in hardware that hold frequently accessed blocks of main memory

112
Q

cache configurations

A

direct-mapped, e-way associative, fully associated

113
Q

general cache organization

A 
S, E, B
S = 2^s sets
E = 2^e lines per set
B = 2^b bytes per cache block
cache size = C = SxExB data bytes
114
Q

direct-mapped cache

A

1 line per set
number of lines = number of sets
fastest

115
Q

E-way associative cache

A

E = # lines per set

116
Q

fully associated cache

A

one set with all cache lines

117
Q

cache read

A

locate set, check if any line in set has matching tag, yes + line valid: hit, locate data starting at offset

118
Q

cache block mapping: direct-mapped

A

block will always go to the same location (address % number of blocks)

119
Q

cache block mapping: fully associative

A

block can go anywhere

120
Q

cache block mapping: E-way associative

A

block has E options in one set

121
Q

what to do on a write hit

A

write-through (write immediately to memory) or write-back (defer write to memory until replacement of line; need a dirty bit to determine if the line is different from memory or not)

122
Q

what to do on a write miss

A

write-allocate (load into cache, update line in cache) or no-write-allocate (writes immediately to memory)

123
Q

typical selection for write hit/write miss

A

write-back + write-allocate

124
Q

intel core i7 hierarchy has ? cores, each with ?

A

4; Registers, L1 d-cache, L1 i-cache, and L2 unified cache

125
Q

the intel core i7 processor package holds

A

the 4 cores and the L3 unified cache (shared by all cores)

126
Q

intel core i7 L1 i-cache and d-cache

A

32 KB, 8-way, access: 4 cycles

127
Q

intel core i7 L2 unified cache

A

256 KB, 8-way, access: 11 cycles

128
Q

intel core i7 L3 unified cache

A

8MB, 16-way, access: 30-40 cycles

129
Q

intel core i7 block size

A

64 bytes for all caches

130
Q

cache miss rate

A

fraction of memory references not found in cache; misses/accesses = 1 - hit rate

131
Q

hit time

A

time to deliver a line in the cache to the processor (includes time to determine whether the line is in the cache)

132
Q

miss penalty

A

additional time required because of a miss

133
Q

average memory access time

A

AMAT = hit time + (miss rate * miss penalty)

134
Q

99% hits is ? times as good as 97% hits

A

two

135
Q

three primary strategies for cache block replacement policy

A
  1. random (or psuedo-random)
  2. least recently used (LRU)
  3. first in, first out (FIFO - oldest block is replaced)
136
Q

cache optimization

A
  1. reduce miss rate
  2. reduce miss penalty
  3. reduce hit time
137
Q

six basic cache optimizations

A
  1. larger block size to reduce miss rate
  2. larger cache to reduce miss rate
  3. higher associativity to reduce miss rate
  4. multilevel caches to reduce miss penalty
  5. give priority to read misses over writes to reduce miss penalty
  6. avoid address translation to reduce hit time
138
Q

2:1 cache rule of thumb

A

a direct-mapped cache of size N has about the same miss rate as a 2-way set associative cache of size N/2. This held in three C’s figures for cache sizes less than 128 KB

Fall 2017 (24 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions