Q1 (2 pts) Design a 1-bit memory of a full-adder.

The following sequential circuit includes a full-adder (described in the previous question). Inputs are X, Y and carry-in, and outputs are the next state of S and Q.

Implement the sequential circuit in Logisim simulator.

Through the Logisim simulation of this sequential circuit, complete the following truth table for this 1-bit memory of a full-adder: Note that the Carry out signal is output, not the input. The carry in signal is the same as the Q. You can change the Carry-in bit by clicking the D-FF.

X	Y	Carry-in (or Q before clock)	S (before clock)	Carry-out (before clock)	S (after clock)	Carry-out (after clock)
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

For Q1, attach your truth table to your submission. No need to submit .circ file for this 1-bit memory of a full-adder.

Q2. (4 pts) Design a sequential circuit.

A sequential circuit has one D flip-flop and one JK-flip-flop, two inputs x and y, and one output z. A and B are the outputs of each D flip-flop, and JK-flip-flop, respectively. The flip-flop input equations and the circuit output are as follows. Here D_A is the D input of the D-flip flop of A, and J_B, K_B is the J and K input of the JK-flip flop of B.

D_A = ~xy + yB

J_B = ~xB + xy

K_B = yB + ~xA

z = y+x~y

Q2-1. (1pt) Draw the logic diagram of the circuit and test it with Logisim. Please attach the circuit image only, (i.e., capture the circuit image and attach it to your submission file. No need to include .circ.)

Attach the circuit image here.

Q2-2. Construct a state transition table as well as a state diagram of this circuit. Note that you don’t have to simplify states. (1pt)

X	Y	A( t )	B ( t )	A(t + 1)	B(t + 1)	Z
0	0	0	0
0	0	0	1
0	0	1	0
0	0	1	1
0	1	0	0
0	1	0	1
0	1	1	0
0	1	1	1
1	0	0	0
1	0	0	1
1	0	1	0
1	0	1	1
1	1	0	0
1	1	0	1
1	1	1	0
1	1	1	1

Attach a state diagram here. (2pts)

Q3. (14pts) Design a sequential system by simplifying the states.

Q3-1. Draw the corresponding state transition table with 7 states (i.e., S0-S6) and simplify it to the one with 4 states. (Refer to pages 9 and 10 of Lecture Note: 12.SeqCircuit.pptx).

Hint: focus on a pair of S0 and S5; a pair of S1 and S4; and a pair of S2 and S6

The original state transition table

	Input X = 0		Input X = 1
Current State	Next State	Output Z	Next State	Output Z
S0
S1
S2
S3
S4
S5
S6

A simplified state transition table

	Input X = 0		Input X = 1
Current State	Next State	Output Z	Next State	Output Z
S05
S3
S14
S26

Q3-2. Allocate 2 JK flip-flops (A and B) to this simplified state transition diagram as following page 11 of 12.SeqCircuit.pptx.

Q(t)	Q(t+1)	J	K
0	0	0	*
0	1	1	*
1	0	*	1
1	1	*	0

input X=0

input X=1

input X=0

input X=1

input X=0

input X=1

Current State

Next State

Output Z

Next State

Output Z

JK Flip-Flop A

JK Flip-Flop B

AB

AB

Z

AB

Z

Ja

Ka

Ja

Ka

Jb

Kb

Jb

Kb

S05=00

S3 = 01

S14=11

S26=10

Q3-3. Determine and simplify Boolean equations to these two JK flip-flops’ inputs, (i.e., Ja/Ka, and Jb/Kb) using K-maps, as following page 12 of 12.SeqCircuit.pptx.

Ja =

AB X	00	01	11	10
0
1

Ka =

AB X	00	01	11	10
0
1

Jb =

AB X	00	01	11	10
0
1

Kb =

AB X	00	01	11	10
0
1

Q3-4. Determine and simplify a Boolean equation to represent the output Z.

Z =

AB X	00	01	11	10
0
1

Q3-5. Draw the corresponding sequential circuit, using Logisim.

Capture the circuit image to your submission. No .circ file needed.

Attach the circuit image here.

We need to use Easy68K to finish all of the questions

Q1. Cache and Memory mapping (6 points)

Suppose a byte-addressable memory has a total memory capacity of 2M bytes and the cache consists of 64 blocks, where each block contains 32 bytes.

1. Direct Mapping

1) Divide the bits into tag, block and offset bits.

2) What is the tag, line and offset for the address $123A63, in hexadecimal?

tag: 0x__________

line: 0x__________

offset: 0x__________

2. Fully Associative Mapping

1) Divide the bits into tag and offset bits.

2) What is the tag and offset for the address $123A63, in hexadecimal?

tag: 0x__________

offset: 0x__________

3. 4-way set associative mapping

1) Divide the bits into tag, set and offset bits

2) What is the tag, set and offset for the address $123A63, in hexadecimal?

tag: 0x__________

set: 0x__________

offset: 0x__________

Q2. Cache hit and miss (3 points)

Suppose we have a computer that uses a memory with a total memory capacity of 256 bytes. The computer has a 16-byte direct-mapped cache with 4 bytes per block. The computer accesses a number of memory locations throughout the course of running a program. Here is the memory addresses in this exact order: 0x91, 0xA8, 0xA9, 0xAB, 0xAD, 0x93, 0x6E, 0xB9, 0x17, 0xE2, 0x4E, 0x4F, 0x50, and 0xA4. The cache Tag and Block information has been filled out as shown below.

Tag (binary)	Block #	offset 0	offset 1	offset 2	offset 3
1110	0
0001	1
1011	2
0110	3

1. What is the hit ratio for the entire memory reference sequence (given in bold)?

2. What memory blocks will be in the cache after the last address has been assessed? Please fill in the Tag and Block first. Then, fill the actual address value for each offset location in the corresponding cell.

Tag (binary)	Block #	offset 0	offset 1	offset 2	offset 3

Q3. Virtual memory and cache (6 points)

Consider a processor with the following memory hierarchy:

256K virtual address space (byte addressable)

128K physical address space, each page (frame) has 32K bytes (byte addressable)

2Kbyte direct-mapped cache, a block (refill line) has 256 bytes

The machine uses a two entry TLB.

All replacement policies are LRU. There are two LRU stack.

The entry of these stacks are the page number of a virtual memory.

Note that all the values are represented as hexadecimal.

TLB

Virtual page #	Physical page #	Valid
5	3	1
0	2	1

TLB LRU stack

0

5

Page Table

Virtual page #	Physical page #	Valid
0	2	1
1	1	1
2	—	0
3	—	0
4	0	1
5	3	1
6	—	0
7	—	0

Mem LRU stack

0

5

4

1

cache

Line #	Tag	Data block
0	10	*
1	0A	*
2	3C	*
3	14	*
4	28	*
5	04	*
6	37	*
7	1D	*

1. Split the bits of virtual address and physical address.

2. Split the bits in memory address based on the cache.

3. Suppose the processor has requested to access a memory in 0x32764 (which is virtual address)

1) Is it a page fault? Explain.

2) Show the changes of TLB, TLB LRU, page table and Mem LRU

TLB	Virtual page #	Physical page #	Valid

TLB LRU stack

Page Table

Virtual page #	Physical page #	Valid
0
1
2
3
4
5
6
7

Mem LRU stack

3) Show the changes in Cache.

Cache

Line #	Tag	Data
0
1
2
3
4
5
6
7