Flashcards

CS219 - Midterm 2

lisel v Computer Science English 131 cards

Cards in this deck (131)

1What will be the output voltage if we apply A = Vcc and B = 0 (ground)?
2Which of the following is a sequential circuit? (Decoder, Multiplexer, Full adder, SR Latch)SR Latch
3What will be the output if we apply 0 to the input?
4When will this NAND gate have an output of 0?
5When will this NOR gate have an output of 1?
6What is the name of the logic gate shown?D flip-flop
7In a full adder, what is the value of S and Cout when A=1, B=1, and Cin = 1?01 + 01 + 01 = 11 (3)
8Which of the following is an INCORRECT description of 32-bit MIPS ISA? a. Its design follows principles of RISC architecture b. It is a performance metric for 32-bit processors c. All instructions are fixed-size (32-bit) d. It has 32 32-bit integer registersa. Its design follows principles of RISC architecture
9Which of the following MIPS instructions is encoded differently than the others? a. beq r8, r10, addr b. lw r4, 128(r0) c. slll r6, r8, 17 d. subi r10, r2, 32c. sll r6, r8, 32
This instruction is an r-type instruction. All other instructions are i-type.
10Which of the following CANNOT be a real MIPS instruction? a. addi r2, r4, 100 b. add r4, 100(r8) c. lw r5, 100(r3) d. sw r2, 128(r0)b. add r4, 100(r8)
This is an r-type instruction, and for add there should be 3 arguments (dest = src + src)
11What encoding type does the following instruction belong to? ADD r14, r10, r20r-type
12What encoding type does the following instruction belong to? BEQ r3, r4, g0i-type
13What encoding type does the following instruction belong to? SW r6, 200[r7]i-type
14A CPU has critical path of 40 FO4 (fan-out of 4) between pipeline stages. On a 28nm process technology, F)4 latency is given 10 ps (picosecond = 10^-12 second). What is the maximum possible clock frequency of the design on the 28 nm technology?2.5 * 10^9 Hz
40 * 10 = 1/400 ps = 0.0025 ps
Given that 1 ps = 1 Thz (10^12 Hz), 0.0025ps = 2.5 GHz = 2.5 * 10^9 Hz
15What is a multiplexer? (MUX)has n number of inputs, and 2^n selectors
one of the 2^n selectors will be sent to the input based on the combination of n inputs (in binary)
16What is a decoder?Based on n inputs, there are 2^n outputs (due to the binary combination of the n inputs)
17What is the I/O table of a half adder?
18What is the difference between a combinational and sequential circuit?Combinational output is only determined by the current inputs.
Sequential output is based on past values (has memory).
19What sequential circuit is this?SR Latch
20What is the truth table for an SR latch?
21Are latches level-triggered or edge-triggered?Level-triggered: if the input changes at any time while the clock is high, then the output of Q changes
22What is the difference between a normal and clocked SR latch?Clocked SR latches only set and reset when the clock is high. Otherwise, if the clock is not high, then S and R inputs do not affect Q at all.
23What sequential circuit is this?Clocked D-latch
24What does the clocked D latch do?Prevents the S=R=1 condition
D is only sampled and stored when the clock is 1 (high)
level-triggered
25Are flip-flops edge or level-triggered?Edge-triggered, so the sampling on happens on a rising or falling edge of the clock.
Rising edge means it is positive edge-triggered, falling edge means it is negative edge-triggered
26How are edge-triggered mechanisms developed in a D flip-flop?An inverted adds gate delay on purpose.
27How many bits of data can a D flip-flop store?1 bit
28How long can a D flip-flop "delay" bit propagation?By 1 clock
29Describe all 4 latches.a) level-high active D-latch (loads state from D when clock is 1)
b) level-low active D-latch (loads state from D when clock is 0)
c) positive edge-triggered flip-flop
d) negative edge triggered flip-flop
30What is the difference between a shift register and a parallel register?A shift register uses the output Q as the input (D) for the next register.
A parallel register does not use the current output Q as the next input D.
31How can we better utilize hardware for pipelining?Latch intermediate results in internal stages
32The maximum clock is bound bythe CPU circuit's longest path for signal to arrive at the next pipeline stage
(pipeline cannot move until the stage is finished)
33What is Fan Out of 4?The process-independent unit used to describe the required latency between clock cycles
34A design has a critical path of 20 FO4 between pipeline stages. It is a 90nm process that has 20ps for FO4. What is the minimum cycle time? What is the maximum frequency?Minimum cycle time: 400ps (20 FO4 * 20ps)
Maximum frequency = 2.5GHZ (1/400 ps)
35What are the sizes for each of these data types? Byte Halfword Word DoublewordByte: 8-bit
Halfword: 16-bit
Word: 32-bit
Doubleword: 64-bit
36What is alignment restriction?Data has to be naturally aligned, so it must start at addresses that are a multiple of 4
37Is MIPs bi-endian?Yes, but in class we assume little-endian (least significant value in the sequence is stored first)
38How many general purpose registers are there in MIPs and how many bits do we need to refer to a register?32 GPR
5 bits to refer
39What are the three addressing modes in MIPs?Immediate (addi)
Displacement (register-based such as lw)
Displacement (PC-relative) (beq)
40What can you use to allow absolute addressing?$zero
41What are the three types according to the encoding of the instruction?R-type: has register operands (add or jr $rs)
I-type: instructions with immediate fields. Includes load/stores, and branches (addi, lw, beq, etc.)
J-Type: instructions that jump to a 26-bit offset field (j offset)
42What is the instruction format for R-type instructions?|op|rs|rt|rd|shamt|funct
Where op and funct are 6 bits
43What is the instruction format for I-type instructions?|op|rs|rt|address/immediate|
Where address/imm is 16 bits
44What is the instruction format for J-type instructions?|op|target address <26-bit>|
45When is zero set in an ALU?when a - b == 0
46How does a register file work?It is a collection of parallel registers that specifies (in binary) which register to read from / write to
47What are the 5 Stages in the MIPs single cycle implementationIF, ID, EX, MEM, WB
48What happens during instruction fetch?the PC is updated by 4
49What happens during the instruction decode?decodes the instruction and reads selected registers from the register file
if it is a branch, get the target address
50What happens during the execution stage?If ALU, perform the ALU operation
If the instruction is load/store, get the effective address by adding the base register + the offset
51What happens during the memory access stage?If it is a load instruction, read from memory.
If it it a store instruction, write to memory.
52What happens during the write back stage?If the instruction uses the ALU or is a load instruction, write the result back to the register file.
53What is the MIPs single cycle implementation for: add $rd, $rs, $rtIF: update PC by 4
ID: decode instructions and read $rs, $rt, $rd, registers from the register file
EX: If ALU, do the operation. If load/store, get the effective address by adding offset & address.
WB: Writeback the result of the ALU to the write register.
54What is the MIPs single cycle implementation for addi $rt, $rs, immediate?IF: update PC by 4
ID: get register from register file, and then use a MUX for rt/rd to select which one to use
EX: execution & effective address - sign extend the immediate, and use a MUX between the sign-extended immediate and the 32 data. The sign extended immediate will be added with the R1 data using the ALU.
WB: writeback the result into the write-back data
55What is the MIPs single cycle implementation for lw $rt, offset($rs)IF: update the PC counter by 4
ID: use a MUX between $rt and $rd to select which register will be written to (will be rt in this case)
EX: for load, calculate the effective address by adding offset + $rs
4) read from memory using the mem to register MUX
5) write back the result of the MUX to the register
56What is the MIPs single cycle implementation for sw $rt, offset($rs)?IF: update PC by 4
ID: decode the instructions and read registers from the register file. use a MUX betwen $rt and $rd to select which register the result will be written to
EX: for store, get the effective address by adding immediate offset
MEM: write the value in $rt to the register offset in mem
57What is the MIPs single cycle implementation for beq $rt, $rs, offset?IF: update PC + offset >> 2 IF the branch is true
ID: read register files
EX: instruction execute, if the logic for the condition is true then the branch is taken
58The register file participates in what to cycle stages?ID & WB (read registers at ID, write to registers at WB)
59Can instructions be overlapped perfectly in pipelining?No
60What are pipeline hazards?Conditions where you have internal conflict in which you have to stall the pipeline.
61Give an example of a RAW data hazard.add $s0, $t0, $t1
sub $t2, $s0, $t3
sub requires the result of add, but when sub reads $s0 at ID stage, the result has not been written to $s0 yet for the first instruction (Read After Write hazard)
62What are the three ways to resolve hazards?1. Don't solve the hazard - break the instruction semantics.
2. Stall the pipeline.
3. Forwarding
63How do you break the instruction semnatics?The software should know how broken the hardware is. In this case, it is up the application program to issue instructions in such a way that hazards can be avoided.
64How do you stall the pipeline?Stop younger instructions in the pipeline when a conflict has been detected. There should be hardware control that can detect the hazard condition.
Insert a pipeline bubble, which can be done whenever. Current instructions become "nop" and instructions in earlier stages are repeated. This has a negative performance impact.
65What is forwarding?When you forward necessary information between pipeline stages. This can get rid of most conflict, but not always.
66What are the three types of pipeline hazards?Structural hazard, data hazard, control hazard
67What is a structural hazard?When two or more instructions in the pipeline need the same resource
68How are instructions executed in a structural hazard?Executed in serial rather than in parallel for part of the pipeline
69A structural hazard is also known as aresource hazard
70Give an example of a structural hazard.The main memory has a single port (no separate instruction for instruction memory and data memory). Therefore, load/store cannot be performed in parallel with IF. The IF stage must stall for one cycle when a load/store instruction hits the MEM stage.
71Give another example of a structural hazard/In superscalar architecture, when multiple instructions are ready to enter the EX phase and there is only one ALU.
Solution: Stall OR increase available resources (with multiple main memory ports or multiple ALUs)
72What are the three types of data hazards?Read after write (RAW) / true dependency
Write after read (WAR) / anti dependency
Write after write (WAW) / output dependency
73What data type hazard is most common in MIPs?RAW
74What are the 4 additional techniques for reducing branch penalties?1. Prefetching the branch target
2. Multiple streams
3. Delayed branch
4. Branch prediction
75What happens at prefetch branch target?The instructions at the branch taken path are prefetched, in addition to the instruction at the branch untaken path.
The prefetched instructions are kept until the branch decision. If the branch is taken, then the IF can be skipped since instructions have already been fetched.
Utilized by IDM 360/91
76What is the multiple streams method?Two pipelines: one for the branch taken and one for the branch untaken. Use the appropriate pipeline.
Problems: Memory/register contention can lead to delay
77What is the delayed branch method?Allows the instructions directly following a branch instruction to proceed normally.
78What is a branch delay slot?What instructions right after a branch that proceed normally are occupying in a delayed branch
79How many branch delay slots does MIPS ISA have?Original only has 1
80What are the issues with a delayed branch?Only effective in a 5-stage pipeline, had static instruction scheduling which was not very effective
81What are the 5 different branch prediction possibilities?1. "Predict never taken"
2. "Predict always taken"
3. Predict by opcode
4. Taken/not taken switch
5. Branch history table
82Which of the five are static?Predict always taken, predict never taken, and predict by opcode
83Which of the five are dynamic?Taken/not taken switch
Branch history table
84What happens when you predict that a branch is never taken?Assume that the jump will never happen so always fetch the next instruction
85What happens when you predict that a branch is always taken?Always fetch the target instruction and assume that the jump will always happen
86Which is more favorable? Branch is never taken or branch is always taken?Branch is always taken, but there is a higher chance of causing page fault and leading to higher penalty
87How does predicting by opcode work?Some instructions are more likely to jump than others, so make this prediction by looking at the instruction op code
88Up to how successful can prediction by opcode be?75%
89How does a taken / not taken switch work?One or more bits can be associated with each conditional branch instruction. Depending on whether the switch is on taken or not taken, the processor will decide according.
90Where is the state stored in a taken/not taken switch?In fast, temporary memory such as cache or a separated table
91How does a 2-bit branch prediction work?Think of forgiving tit for tat. Four modes: very unlikely, unlikely, likely, and very likely. Depending on the outcome, it will jump between these 4 stages.
92What is the problem with the taken/not taken switch?The branch instruction must always be decoded first in order to get the target instruction address
This is bypassed by using a Branch History Table/Branch Target Buffer
93What is a branch history table?cache memory associated with the instruction fetch stage
each entry contains the address of the branch instruction, a history of bits for the state, and the address of the target instruction
94What is the general sequence of events for the taken/note taken switchDuring prefetch, the lookup table is triggered. It will search for the branch instruction in the lookup table. If there is no match, use the next sequential address. Otherwise, if there is a match follow the table's decision.
When a branch is executed, the state in the table should be updated with either correct/incorrect. If the predicted target address is wrong, update and use the correct one.
If it is a totally new branch instruction, add it into the table.
95How to predict for a history-based logic when there is initially no history?If the branch is backwards (so you jump to past lines in your code) then predict taken.
If the branch is forwards (you jump to future lines in your code) then predict not taken.
Only use static prediction as a fallback, when there is no history or matching entry.
96What are three key features of Reduced Instruction Set Computer (RISC)1. limited and simple instruction set
2. large number of general purpose registers (compiler technology optimizes register use)
3. Emphasis on optimizing the instruction pipeline
97What was the technology landscape like in the early 80s?1.5um lithography for process technology nodes
VLSI was just beginning (only 100ks transistors on chips)
Microprocessors were oddities
Big Irons ruled the market
98Is there a debate between RISC and CISC?No. Most microarch internally run RISC micro-ops, and employ instructions with a translation layer.
99What are the intentions of CISC archicture?easy compiler writing
improved execution efficiency (complex operations can be implemented with less lines of code)
support for HLL (which was C at the time)
100The percentage of operands in CISC at the time were mainlyscalar variables (about 80%)
101Optimization should focus onspeeding up local variable accesses
102What was the depth of nesting in procedure calls?Usually within a narrow window of depth (used less than 6 arguments, or less than 6 local scalar variables)
103What is the conclusion of procedure calls?Operand references in prodecure calls are highly localized (the same values are frequently accessed depending on the memory access pattern)
this was the basis of cache memory
104Is making instruction set architecture closer to HLL effective?No, we hsould be focusing on what is time-consuming when generating programs by HLL compilers
105What are the three suggestions that were implied by the measurements done on CISC?1. There should be a large number of registers so that operand references can be made without having to access memory
2. Careful design of pipelines (common use of branches means that straightforward pipelines are not always the most efficient)
3. Simplified instruction set
106What is superscalar?A technique that allows the execution of multiple instructions at the same time with the use of multiple functional units (which can be done in a single thread of execution)
107When can instructions be executed in parallel?When they are not dependent on each other.
108How does a super pipeline work?It has twice as much internal clock speed than normal, so 2 tasks can be started in one clock cycle
109T/F: Shorter instructions can complete more quickly in superscalar architecture?True
110What is Simultaneous Multi-threading? (SMT)fetch execute instructions from other programs at the same time (threads), this exploits thread-level parallelism
111How is SMT added to superscalar architecture?make the core CPU have two architectural states
112What is an SMT thread?A logical processor that is visible to software, however this shares the physical core so there is a performance issue sometimes
113To find the # of logical processorsMultiple sockets by cores by SMT threads per core
114What are challenges of superscalar architecture?It is limited by the degree at which you can execute the instructions in parallel (Instruction Level Parallelism ILP)
115What hazards limit instruction level parallelism exploitation?Control hazards, output dependencies (WAW), and antidependencies (WAR)
116What are the features of modern microarchitecture?Can put out more than one instruction at a cycle, can execute instructions out of order, speculative execution, register renaming, and multiple functional units
117Why do control hazards exist in modern architecture?Instructions after a branch cannot be executed in parallel with instructions before a branch (this can happen with out of order execution)
118What can alleviate problems with control hazards?Speculative execution (branch execution on steroids)
119What is a reorder buffer? (ROB)An instruction retirement mechanism that makes sure instructions are committed in order. Allows a safe backout when a wrong prediction is made.
120How does out of order execution work?In order to make the pipeline more efficient (to avoid as many stalls as possible) the instructions can be issued and executed out of order aslong as the same result is produced.
121What is the problem with out of order completion?WAW (output dependency)
Writes to a register at the wrong time (usually too early or too late)
can be avoided with a stall on the instruction that may accidentally get the result of the older instruction
happens usually when the destination for two instructions are the same
122How does out of order instruction issuing work?get future instructions and begin issuing them if there is no conflict, fully utilizes ILP
123What is the problem with out of order instruction issuing?processor stops decoding when there is a dependency or a conflict
the processor cannot issue subsequent instructions even though they are independent of the instructions already in the pipeline
124How can you decode future instructions in advance? (Because instructions cannot be issued until they have been decoded)need an intermediate buffer which leads to an 'instruction window' that contains decoded instructions
125How do we issue instructions out of order?Fetch and decode instructions while the instruction window is not full
Whenever a functional unit is available, any instruction from the IW can be executed if:
1. It needs the current available functional unit
2. There are not conflicts or dependencies
126What is the hazard with out of order issues?WAR hazard (Antidependency)
to avoid this hazard, the instructions using old data should be completed before the instruction that overwrites the data executes
127Why are WAW and WAR hazards created from out of order instruction completions and out of order instruction issues?fake dependencies are created by using the same register names (such as using R3. although it is the same register, it is technically different bc it is expected to have a different value )
128What happens when using the same registers?multiple instruction compete to use them and that competition worsens when register optimization techniques are used
129What are logical register names?Software visible, architectural register names
130What are hardware register names?hidden, internal register names (we will denote them with subscripts)
131What is a prime example of modern microarchitecture?Intel Haswell