Solutions
A
We are given an array of unique uint32_t
that represent nodes in a directed graph. We say there is an edge between A and B if A < B
and the Hamming distance between A and B is exactly 1
. A Hamming distance of 1
means that the bits differ in 1
(and only 1) place. As an example, if the array were {0b0000, 0b0001, 0b0010, 0b0011, 0b1000, 0b1010}
, we would have the edges shown as following:
See also: LeetCode 461. Hamming Distance
Construct an edgelist_t
(specified below) that contains all of the edges in this graph.
Our solution used every line provided, but if you need more lines, just write them to the right of the line they are supposed to go after and put semicolons between
them. All of the necessary #include
statements are omitted for brevity; do not worry about checking for malloc
, calloc
, or realloc
returning NULL
. Make sure L->edges
has no unused space when L
is eventually returned.
- A01 = ?
nodes[i] ^ nodes[j]
XOR can differentiate the differenet bit from two numbers. Take
111
and110
for example,b111 ^ b110 = b001
.
- A02 = ?
tmp & (tmp - 1)
To check the hamming distance is 1, the XOR result must contain only 1 1 bit in the number.
if
tmp & (tmp-1)
is 0 then there is only 1 1 bit in the number, and if the result is not 0, then there is multiple 1 bit in the number.Another approach is
__builtin_popcount(tmp) == 1
.
- A03 = ?
L->edges[L->len].A = nodes[i]
- A04 = ?
L->edges[L->len].B = nodes[j]
Since the direct graph edge is from the shorter one to the longer one and line 10
nodes[i] < nodes[j]
, edgeA isnodes[i]
and edgeB isnodes[j]
.
B
Consider the following circuit:
You are given the following information:
Clk
has a frequency of 50 MHzX
changes 10ns after the rising edge of Clk
Reg1
and Reg2
have a clock-to-Q delay of 2 nsThe clock period is . This means that if X
changes, it changes 10 ns after the clock positive edge.
B01 = ?
4 ns
Reg1 longest possible setup time: the path is output of Reg1 -> NOT -> OR, with a delay of 2 ns + 4 ns + 10 ns = 16 ns. So 20 - 16 = 4 ns.
Reg2 longest possible setup time: the path is X changes -> AND, with a delay of 10 ns + 2 ns = 12 ns. So 20 - 12 = 8 ns.
So longest setup time: min(4ns, 8ns) = 4nsSince during the propagation delay, the X value is garbage, we can not count as stable value, and we do not consider the combinational logic delay(like D-to-Q delay), so
Tclk - propagation delay > setup time
.For Reg1
Clock period =
propagation delay: 2+4+10=16
Setup time = 20-16=4nsFor Reg2
Clock period =
propagation delay: 10+2=12ns
Setup time = 20-12=8nsHence, considering the
Tclk - propagation delay > setup time
, we would choose the minimum one, 4ns.
B02 = ?
8 ns
Reg 1 longest possible hold time: the path is output of Reg2 -> OR, with a delay of 2 ns + 10 ns = 12 ns.
Reg2 longest possible hold time: the path is output of
Reg2 -> NOT -> AND, with a delay of 2 ns + 4 ns + 2 ns = 8 ns.
So longest hold time: min(12ns, 8ns) = 8nsWe should consider the propagation delay followed with register.
Thold < Tprop
.For Reg1
Condisering the output Q, it would have to wait for the OR gate and Reg2, and hence the longest hold time is 2+10=12nsFor Reg2
It would have to wait for NOT->AND->Reg2. so the longest hold time is 8ns.Considering the rule
Thold < Tprop
, The longest hold time is min(8, 12)
01
means Reg1 = 0
and Reg2 = 1
). We did one transition already.
- B03 = ?
10
For state 00 to B03
For Reg1: 0|1=1
For Reg2: 0&1=0
Hence the answer is10
- B04 = ?
01
For state 10 to B04
For reg1: 0|0=0
For reg2: 1&1=1
Hence the anwer is01
C
What is the FULLY SIMPLIFIED (fewest primitive gates) circuit for the equation below? You may use the following primitive gates: AND, NAND, OR, NOR, XOR, XNOR, and NOT.
- C01 = ?
或 \overline C 或 NOT C
D
Consider the following RISC-V assembly code.
Recall that immediate values are generated from instructions with the following table:
We will refer to the number produced after this process is completed as the "immediate value."
What are the fields for the machine code generated for beq s1, x0, End
(line 4)?
Immediate value
- D01 = ?
24
Each line is 4 byte, so immediate values is
funct3
- D02 = ?
0x0
According to the risc-v mannual
Hence, answer is000
.
opcode
- D03 = ?
0x63
rs1
- D04 = ?
9
rs2
- D05 = ?
0
x0 is always 0.
E
Consider the following pipelined circuit. Assume all registers have their clock inputs correctly connected to a global clock signal and that logic gates have the following parameters:
When shopping for registers, we find two different models and want to determine which would be best for our circuit.
Register Type
Register Type
- E01 = ?
420 ps
2 * (30ps + 80ps + 60ps + 40ps) = 420ps
Critical Path = CLK_Q + XOR + AND + SETUP
Because this passes through 2 registers, our latency is 2 clock cycles.
just 1 critical path because it considers the latency to be just the top path A takes to B.Tlatency = Tsetup + Tprop + Tclk_q
Since the circuit is seperate in to two parts, so it must pass two clocks from A to B.
- E02 = ?
460 ps
2 * (80ps + 80ps + 60ps + 10ps) = 460ps
It also counts an extra clock to q to give A
its value or propagate through the last register to B.
F
Consider the following RISC-V code:
bltu
instruction?
- F01 = ?
-8
Two instructions away =
-8
bytes
Each instruction is byte, so to go back to Loop, it needs to minus bytes.
7
bits). This justifies taking out the funct3
field from the R, I, S, and SB instructions, allowing you to allocate bits to other instruction fields except the opcode field. Assume register s0 = 0x1000 0000
, s1 = 0x4000 0000
, PC = 0xA000 0000
. Let's analyze the instruction: jalr s0, s1, MAX_POS_IMM
where MAX_POS_IMM
is the maximum possible positive immediate for jalr
. After the instruction executes, what are the values in the following registers? (Answer in HEX)
s0
= F02s1
= F03PC
= F04
- F02 = ?
0xA000 0004
- F03 = ?
0x4000 0000
- F04 = ?
0x4000 0FFF
We know that rd and rs1 fields are now 6 bits.
jalr
is an I-type instruction, so we take out thefunct3
bits but we give each of rd and rs1 fields 1 bit, meaning we have 1 bit leftover to give to the immediate field. Thus, we now have a 13-bit immediate. Thus, the maximum possible immediate ajalr
instruction can hold is halfwords away, which is represented as 0b0 1111 1111 1111, which is0x0FFF
.
s0
is the linking register – itss value is PC + 4
s1
does not get written into so it stays the same.
PC = R[s1] + 0x0FFF
G
Consider the following circuit:
Assume input A and input B come from registers. Assume all 2-input logical gates have a 10 ns propagation delay. The NOT
gate has a 5 ns delay. All registers have a clk-to-q of 15 ns and setup time of 20 ns.
- G01 = ?
75 ns
We have the following paths:
- Input A (clock-to-q) -> NOT -> Register (setup) = 15 ns + 5 ns + 20 ns = 40 ns
- Input A (clock-to-q) -> NOT -> AND -> NOR -> AND -> Register (setup) = 15 ns + 5 ns + 10 ns + 10 ns + 10 ns + 20 ns = 70 ns
- Input B (clock-to-q) -> NAND -> AND -> NOR -> AND -> Register (setup) = 15 ns + 10 ns + 10 ns + 10 ns + 10 ns + 20 ns = 75 ns
- Register (clock-to-q) -> NOT -> NOR -> AND -> Register (setup) = 15 ns + 5 ns + 10 ns + 10 ns + 20 ns = 60 ns
So we need the max of them which would be 75 ns.
Find the longest delay.
- G02 = ?
20 ns
For the maximum hold time, we need to look at the same paths to see what would be the shortest path to get to the register:
- Input A (clock-to-q) -> NOT -> Register (NO setup) = 15 ns + 5 ns = 20 ns
- Input A (clock-to-q) -> NOT -> AND -> NOR -> AND -> Register (NO setup) = 15 ns + 5 ns + 10 ns + 10 ns + 10 ns = 50 ns
- Input B (clock-to-q) -> NAND -> AND -> NOR -> AND -> Register (NO setup) = 15 ns + 10 ns + 10 ns + 10 ns + 10 ns = 55 ns
- Register (clock-to-q) -> NOT -> NOR -> AND -> Register (NO setup) = 15 ns + 5 ns + 10 ns + 10 ns = 40 ns
For this one, when we get to the register, we do NOT want to include the setup time as we want to see what is the shortest time to get to a register. This means we take a min of the above paths (which does NOT include the setup) which would be 20 ns.
Find the minimum delay.
H
We wish to implement a function, reverse
, that will take in a pointer to a string, its length, and reverse it. Assume that the argument registers, a0
and a1
, hold the pointer to and length of the string, respectively. Complete the following code skeleton to implement this function.
- H01 = ?
addi t3, t3, -1
t1+t4+1 = s1
t4 = s1-t1-1 = s1-t0-1 = s1-(t3)
we assume t1 as the index number of the string.
- H02 = ?
sb t5, 0(t1)
Switch the and value.
- H03 = ?
srli s8, s1, 1
Since reverse only need to iterate the half of the string time, t0 just need to iterate to
- H04 = ?
bne t0, s8, Loop
Check wheter the iterate value and are same, if it is the same ;then the loop is ended otherwise it goes back to label Loop.
J
Take a look at the following circuit:
We have a register clk-to-Q time of 5ps, a hold time of 2ps, and a setup time of 3ps. AND and NAND gates have a delay of 5ps, OR and XOR gates have a delay of 6ps, and
NOT gates have a delay of 1ps. Assume that our inputs A, B, C, and D arrive on the rising edge of the clock.
- J01 = ?
XOR AND OR OR
- J02 = ?
31 ps
Reg2
and Reg3
. Assume that the clock period (rising edge to rising edge) is 100 ps, registers have a clk-to-Q delay of 25ps and a setup and hold time of 20ps, and all gates have a delay of 5ps. Choose the waveform with the correct outputs for Reg2
and Reg3
.Notation: For reference, in the diagram below, the first region indicates an "undefined" signal, the second region indicates a signal of "high" or 1, and the third region indicates a signal of "low" or 0.
J03 = ?
B
K
Consider the following program that computes the Fibonacci sequence recursively. The C code is shown on the left, and its translation to RISC-V assembly is provided on the right. You are told that the execution has been halted just prior to executing the ret instruction. The SP label on the stack frame (part 3) shows where the stack pointer is pointing to when execution halted.
ble
instruction to make the assembly implementation match the C code.
- K01 = ?
a0, a7, done
a0 is n in C code.
a7 is1
in C code.
done is ready to return in C code.
fib
is called?
- K02 = ?
3
Please fill in the values for the blank locations in the stack trace below. Please express the values in HEX.
Notation | address |
---|---|
Smaller address | 0x280 |
0x1 | |
K03 | |
SP | K04 |
K05 | |
0x0 | |
0x280 | |
0x3 | |
0x0 | |
0x2108 | |
0x4 | |
0x6 | |
Larger address | 0x1 |
- K03 = ?
0x0- K04 = ?
0x280- K05 = ?
0x2
Initialn
is 0x3, and the after the inst.sum: addi a0, a0, -1
the k05 becomes 0x3-1=0x2.
K04 = ra = 0x280
s0 is to store the temporary value to addfib(n - 1) + fib(n - 2)
together equal to instadd a0, s0, t0
.
What is the hex address of the done
label? (Answer in HEX)
- K06 = ?
0x298
There have 6 instructions between the firstcall fib
and done label. Therefore the address is 0x280+6*4=0x298
What was the address of the original function call to fib
? (Answer in HEX)
- K07 = ?
0x2104
Since call would store the next instruction's address so the first ra minus 4 is the answer, which is 0x2108.
L
Suppose we want to create a system that decides if the concatenation of its previous 2 single-bit inputs is a power of 2 (where the MSB is the input from 2 cycles ago and the LSB is from 1 cycle ago). If the previous 2 bits (prior to the current input) are a power-of-two the system outputs a 1, otherwise it outputs 0. Before any input is sent, assume the initial previous 2 bits are 2'b00.
A partial finite state machine diagram of this circuit is shown below:
Before receiving any inputs the FSM is in state A.
- L01 = ?
A
Considering the route A->B->D, the previous two bits are 10, when the input is 0 then the previos two bits would become 00 which means the next state would go to A.
- L02 = ?
B
Considering the route A->B->D, the previous two bits are 10, when the input is 1 then the previos two bits would become 01 which means the next state would go to B.
- L03 = ?
1