Computer Organization and Architecture Test 5

Number of Questions: 35 Section Marks: 30

Directions for questions 1 to 35: Select the correct alterna- 6. Perform the following operation in 2’s complement
tive from the given choices. signed representation, and specify the result in 2’s com-
1. The output of the following circuit is: plement signed notation.
(–13)10 + (–28)10 = ?
(A) 10101001 (B) 11010111
A (C) 11010110 (D) 00101001
B
7. Convert the following number to base 9.
(1101222.201121)3
(A) 1358.647 (B) 4172.647
C (C) 4178.153 (D) 1358.153
8. Which of the following is usually regarded as a bottle-
neck to von-Neumann computer Architecture?
(A) AB + BC (B) AB + BC + AC (A) ALU
(C) A + B + C (D) AB + BC (B) Instruction set
2. Match the following: (C) Processor/memory interface
List I (Numbers in Decimal) (D) Control unit
List II (equivalents in signed 2’s complement represen- 9. Which of the following is the largest storage unit in a
tation) usual memory hierarchy?
List-I List-II (A) Cache memory (B) Main memory
P. – 43 1. 01100000 (C) Register (D) Hard disk
Q. – 78 2. 00110110 10. Which type of cache miss does not occur in fully-Asso-
R. + 54 3. 111010101 ciative cache memory?
S. + 96 4. 10110010 (A) Capacity miss (B) Conflict miss
(C) Compulsory miss (D) Cold start miss
(A) P–3, Q–4, R–1, S–2
(B) P–4, Q–3, R–1, S–2 11. Which of the following statement is FALSE?
(C) P–3, Q–4, R–2, S–1 (A) Pipelining does not improve the execution time of
(D) P–4, Q–3, R–1, S–2 a single task.
(B) Pipelining improves the throughput of the total
3. Which one of the following function will satisfy the
work load.
property, “Dual of function = complement of the
(C) Pipeline speed is limited by the slowest pipeline
function”?
stage.
(A) f (A, B, C) = Sm (0, 1, 2, 3)
(D) In pipelining, only one task is processed at a
(B) f (A, B, C) = Sm (4, 5, 6, 7)
time.
(C) f (A, B, C) = Sm (0, 2, 4, 6)
(D) f (A, B, C) = Sm (0, 1, 6, 7) 12. What is the execution time per stage of a pipeline that
has 4 equal stages and a mean overhead of 12 cycles?
4. The number of min terms for the function
(A) 3 cycles (B) 4 cycles
F(a, b, c, d, e) = b + cd is:
(A) 24 (B) 20 (C) 6 cycles (D) 12 cycles
(C) 32 (D) 16 13. How many bits are needed to represent a direct address
5. Which of the following will work like an inverter? on a 64-bit machine?
(A) 6-bits (B) 64-bits
A 0
(P) (Q) (C) 32-bits (D) 264-bits
1 A
14. A program has 5% divide instructions. Any non-divide
instruction takes one cycle. All divide instructions take
0 1
(R) (S) 25 cycles. What percent of CPU time is spent just doing
A A
divides?
(A) P, Q (B) Q, R (A) 100% (B) 95%
(C) R, S (D) P, S (C) 56.82% (D) 28.41%
3.44 | Computer Organization and Architecture Test 5

15. Which of the following is not an advantage of memory (A) 0, 1 (B) 1, 0

mapped technique? (C) 1, 1
(i) Simple hardware (D) cannot be determined without initial states
(ii) Simple instruction size 20. The initial state of counter is AB = 01. What is the out-
(iii) All address modes available put (AB) after first clock pulse?
(iv) More memory address space
A B
(A) (i), (iv) only (B) (iv) only
(C) (i), (ii), (iii) only (D) (iii), (iv) only 1 1
J Q T Q
16. How many number of 2-input NAND gates are required Clk
to implement f (A, B, C, D) = Sm (1, 3, 4, 5, 6, 7, 9, 11,
12, 13, 14, 15)? 1 K Q Q
(A) 4 (B) 3
(C) 2 (D) 1
(A) 10 (B) 11
17. The output of the following Multiplexer circuit is: (C) 01 (D) 00
21. A switching circuit has four inputs as shown below. A
x1 l0
and B represent the first and second bits of a binary
number N1, C and D represent the first and second bits
y l1 of a binary number N2.
z l1 s y F(x, y, z) The output is 1 only, if the product N1 × N2 is less than
l0 s or equal to 2.
The minimum POS form of F(A, B, C, D) is
x
y A
z
N1
(A) x1 + yz (B) x1 y + z B Switching F
(C) (x1 + y)z (D) x1 y1 + yz + xy1z C
Circuit
N2
D
18. Initially Qn = 0, Qn = 1, , after clock pulse Qn+1 = 1,
Qn+1 = 0, which of the following correctly specifies
(A) AB + CD + AC + AD + BC
about the inputs a, b, c?
(B) (A + C) (A + B + D) (B + C + D)
a x (C) ( A + D )( A + B + D )( B + C + D )
sum J Q
Full
b Adder (D) ( A + C )( A + B + D )( B + C + D )
K Q
c carry
22. The synchronous counter which follows (Q1 Q0) 00 →
10 → 11 → 01 → 00 by using JK-flip flop and D-flip
Clk flop, has inputs as

(A) two or more inputs should be 1. J1 Q1 D0 Q0

(B) only one input has to be 1, or all inputs should
be 1. K1
(C) c should be zero, a, b, can be either 11 or 00
(D) All inputs should be zero.
Clk
19. The states of Q, Q after a clock pulse are:
(A) J1 = Q1 , K1 = Q0 , D0 = Q0
(B) J1 = Q1 , K1 = Q1 , D0 = Q0
J Q
(C) J1 = Q0 , K1 = Q0 , D0 = Q1
Clk (D) J1 = Q0 , K1 = Q0 , D0 = Q1
K Q
23. The minimum SOP form of:
(A) P + QR (B) P + Q
(C) PQ + R (D) P
 Computer Organization and Architecture Test 5 | 3.45

24. A combinational circuit has 3 inputs A, B, C, and 3 out- 30. Consider a main memory system that consists of Eight
puts X, Y, Z. And the functions f (A, B, C) and g (A, B, C) memory modules attached to the system bus, which is
are generated from the combinational logic circuit as one word wide. When a write request is made the bus
shown here with NAND, AND gates. Find the least in occupied for 100 ns by the data, address and control
possible minterm expression for Y (A, B, C). signals. During the same 100 ns and for 500 ns thereaf-
f (A, B, C) = Sm (1, 3, 4, 5, 7) ter, the addressed memory module executes one cycle
g (A, B, C) = Sm (4, 6) accepting and storing the data. The internal operation
Y (A, B, C) = Sm (?) of different memory modules may overlap in time, but
only one request can be on the bus at any time. What is
f(A, B, C) the maximum number of stores that can be initiated in
A X one second?
(A) 109 (B) 107
5
B Y (C) 10 (D) 102
31. Suppose a bus protocol requires 15 ns for devices to
C Z make requests, 15 ns for arbitration and 20 ns to com-
g(A, B, C) plete each operation. How many operations can be
completed per second?
(A) 107 (B) 2 × 107
(A) Sm (0, 2, 3, 6, 7) (B) Sm (1, 3, 4, 5, 7) (C) 5 × 10 7
(D) 50
(C) Sm (0, 2, 4, 6) (D) Sm (0, 2, 4) 32. A computer truncates the significant to four decimal
25. From the above data, for which input A, B, C. places and gives the results in normalized form. What
The outputs all X, Y, Z will become 111 (i.e., XYZ = 1) is the resultant of (0.2233 × 102) + (0.6688 × 101)?
(A) 010 (B) 101 (A) 0.2901 × 102 (B) 2.9018 × 101
(C) 100 (D) 110 (C) 0.2902 × 10 2
(D) 29.018
26. What is the speed up of the pipeline, which is executing 33. For each of the following cases, specify whether SRAM
10 tasks. Consider the mean overhead of the pipeline as or DRAM would be more appropriate building block
5 and an execution time per stage as 1 cycle. for the memory system?
(A) 4.5 (B) 4 (i) A memory system where performance is the most
(C) 3 (D) 5 important goal.
(ii) A memory system where cost is the most impor-
27. Consider a 32-bit computer that has an on-chip tant goal.
16 Kbyte four-way set-associative cache. Assume that (A) SRAM, SRAM
the cache has a line size of four 32-bit words. Then (B) SRAM, DRAM
what will be Tag, Set and Word fields respectively: (C) DRAM, SRAM
(A) 18, 8, 6 (B) 18, 10, 4 (D) DRAM, DRAM
(C) 20, 8, 4 (D) 20, 10, 2
Linked answer questions 34 and 35:
28. Consider a memory of 64 blocks (labelled 0 through Consider an unpipelined processor. Assume that it has 1 ns
63) and a cache of 8 lines (labelled 0 through 7). Using clock cycle and it uses 3 cycles for ALU operations, 5 cycles
direct mapping, which of the following blocks of mem- for branch instructions and 4 cycles for memory operations.
ory contend for line 2 of the cache? Assume that the relative frequencies of these operations are
(i) Block 10 (ii) Block 15 80%, 10% and 10% respectively. Suppose that due to clock
(iii) Block 20 (iv) Block 55 skew and set up, pipelining the processor adds 0.1 ns of
(v) Block 42 (vi) Block 63 overhead to the clock.
(A) (i), (iii), (v) only (B) (i), (v) only 34. What is the average instruction execution time on a
(C) (i), (ii), (iv) only (D) All the six pipelined processor?
29. Convert the decimal number –30.375 to IEEE 754 (A) 4.3 ns (B) 4.4 ns
Floating-point format. Which of the following cor- (C) 1.1 ns (D) 1 ns
rectly specifies the hexa-decimal equivalent of con- 35. By ignoring latency impact, what is the speedup gain in
verted number? the instruction execution rate using pipeline?
(A) C1F30000 (B) 82830000 (A) 4.3 (B) 3.9
(C) 02830000 (D) 41F30000 (C) 1.1 (D) 1
3.46 | Computer Organization and Architecture Test 5

Answer Keys
1. C 2. C 3. D 4. B 5. A 6. B 7. A 8. C 9. D 10. B
11. D 12. B 13. B 14. C 15. B 16. B 17. B 18. B 19. B 20. B
21. D 22. C 23. A 24. C 25. D 26. B 27. C 28. B 29. A 30. B
31. B 32. A 33. B 34. C 35. B

Hints and Explanations

1. In the circuit NAND – NOR structure can be redrawn 5. P is 1 ⊕ A = A ⋅ 1 + A ⋅ 1 = A
as AND – AND Structure. Q is A Q 0 = A ⋅ 1 + A ⋅ 0 = A
R is 0 ⊕ A = A ⋅ 0 + A ⋅ 0 = A
AB S is 1 Q A = 1 ⋅ A + 0 ⋅ A = A
A
So P, Q work like inverter. Choice (A)
6. (–13)10 + (–28)10 = (–41)10
B The operation in 2’s complement signed representation
also given the same answer.
BC (–41)10 is signed 2’s complement representation is
C 11010111 ( +41 = 00101001) Choice (B)
7. Base 9 and base 3 are related (32 = 91). 2 digits of base 3
is equal to base 9.

A ⋅ ABC ⋅ C = ABC = A + B + C Choice (C) Base-3 Base-9

01 1
2. Positive numbers will be represented in their original
binary magnitude but sign bit will be zero (0) to make 02 2
it as positive number. 10 3
Negative Numbers are represented as 2’s complement 11 4
of their positive number representation in 2’s comple- 12 5
ment signed number. 20 6
+ 43 = 00101011
21 7
– 43 = 11010101 (By taking 2’s complement)
22 8
+ 78 = 01001110
– 78 = 10110010 (By taking 2’s complement) 100 10
+ 54 = 00110110 Given number in base 3 is
+ 96 = 01100000 Choice (C) 01 10 12 22 ⋅ 20 11 21
3. Dual of function can be obtained by making min terms 1 3 5 8⋅ 6 4 7
to max terms, i.e., 0 to 1, 1 to 0. = (1358 ⋅ 647)9 Choice (A)
Dual of 8. In Von-Neumann computer architecture, most of
000 ↔ 111 the time is used for transferring data or instructions
001 ↔ 110 from memory to CPU. This is the bottleneck of Von-
010 ↔ 101 Neumann computer. Choice (C)
011 ↔ 100 9. Choice (D)
f = Sm (0, 1, 6, 7) 10. In full-Associative cache, we can place any block of
Dual is f D = p m (7, 6, 1, 0) main memory at any line of cache. So there will be no
= p m (0, 1, 6, 7) conflict miss. Choice (B)
= S m (2, 3, 4, 5)
11. In pipelining, several tasks are processed simultane-
Which is equal to f (complement of f ). Choice (D) ously. Choice (D)
4. F = b + cd 12. If there are k stages and each stage take T cycles then
The term ‘b’ = - b - - - will have 16 min terms, the term (k – 1) T = Pipeline mean overhead
cd = - - cd - will have 8 min terms out of those 4 min ⇒ (4 – 1) × T = 12
terms, have ‘b’. ⇒ T = 4 cycles. Choice (B)
So remaining are 8 – 4 = 4 13. 64
A 64-bit machine has 2 locations. To address these
So total min terms = 16 + 4 = 20 Choice (B) locations, we require 64-bits. Choice (B)
 Computer Organization and Architecture Test 5 | 3.47

14. Total time required to execute the given program

= (0.95) * 1 + (0.05) * 25 = 0.95 + 1.25 = 2.2 Q connected to rising edge means this is an UP coun-
Time taken for Divide Operations = 0.05 * 25 = 1.25 ter A is LSB, B is MSB.
\ Percentage of CPU time spent on divides QA connected to rising edge.
1.25 i.e., for every falling edge of QA, B will change so
= * 100 = 56.82%. Choice (C)
2.2 AB = 11
15. Using memory mapped technique, the memory address
space will be reduced. Choice (B) Clk
16. f (A, B, C, D) = Sm (1, 3, 4, 5, 6, 7, 9, 11, 12, 13, 14, 15)
CD 1
00 01 11 10 1
AB
A 0 0 0
00 1 1

01 1 1 1 1
B1 1 1
11 1 1 1 1 0 0

10 1 1

Clk BA
F=B+D
0 10
B
= B 1 11
D
2 00
3 01
4 10

QA connected to rising edge.

D
i.e., for every falling edge of QA, B will change so
AB = 11 Choice (B)
F = B + D. So 3, 2–input NAND gates are required to 21.
implement F(A, B, C, D)
N2 0 1 3 2
Choice (B) N1 CD
17. The first multiplexer output is AB 00 01 11 10
y = I 0 s + I1s 0 00 1 1 1 1
= x1 ⋅ x1 + zx = x1 + zx = x1 + z
1 01
F = ( x1 + z ) y + z ⋅ y1 = x1y + yz + y1z 1 1 1

= x1 y + (y + y1)z = x1 y + z Choice (B) 3 11 1

18. Qn = 0, Qn+1 = 1
i.e., the state gets toggled i.e., when J = 1, K = 1 2 10 1 1
or the next state is set, Qn+1 = 1 i.e., when J = 1, K = 0
so J = 1, k = x (either zero or 1) The max terms will be (for POS form)
so sum should be one, carry either zero or one.
CD
So a, b, c should have only one 1 (sum = 1, carry = 0) 00 01 11 10
AB
All inputs a, b, c can be 1 so that sum = 1, carry = 1.
00
Choice (B)
19. J = Qn ⊕ Qn ( EXOR of Q, Q ) = 1 01 0

K = Qn Q Qn ( EXNOR of Q, Q ) = 0 11 0 0 0
When J = 1, K = 0, next clock pulse will give
10 0 0
Q = 1, Q = 0 Choice (B)
20. Given circuit is an Asynchronous counter, as clock is So F = ( A + C )( B + C + D )( A + B + D ) Choice (D)
connected to rising edge.
3.48 | Computer Organization and Architecture Test 5

22. 26. Pipeline mean overhead = 5

Present state Next state Inputs Let there are k stages.
Q1 Q0 Q1 Q0 J1 K1 D0 Given each stage take 1 cycle.
(k – 1)T = Pipeline overhead
0 0 1 0 1 X 0
1 0 1 1 X 0 1 ⇒ (k – 1) × 1 = 5
1 1 0 1 X 1 1 ⇒ k=6
0 1 0 0 0 X 0 nonpipeline execution time
Speed up =
From the above table, pipeline execution time
Writing the inputs interms of present state 10 × 6 60
= = =4 Choice (B)
D0 = Q1, J1 = Q0 , K1 = Q0 Choice (C) (10 + 6 − 1) 15
23. Given function is in standard POS Form 27.
F(P, Q, R) = pM (5, 6, 4) = Sm (0, 1, 2, 3, 7) Tag Set Word
20 8 4
QR
P 00 01 11 10
32-bits
0 1 1 1 1 32-bits
Cache capacity = 16 KB = 214 bytes
1 Line size = 4 × 32-bit words
1
= 4 × 4 Bytes = 16 Bytes = 24B
214 10
Number of lines in cache = 4 = 2
F (P, Q, R) = P + QR Choice (A) 2
4 × Number of sets = 210
24. When we consider two min terms product, ⇒ Number of sets = 28
mi, mj = 0 if i ≠ j \ Set size = 8
e.x., ABC ⋅ ABC = 0 mi, mj ≠ 0 if i = j Tag = 32 – (8 + 4) = 20. Choice (C)
e.x., ABC ABC = ABC 28. Main memory has 64-blocks (0 – 63).
Cache has 8 lines (0 – 7).
If two functions ANDed with min terms, then resultant
To place a particular block of main memory in a line of
is common min terms of the two functions.
cache, use the following formula:
Example:
Cache line number = Block number % number of cache
If f1 (a, b, c) = m1 + m2 + m3
lines.
f2 (a, b, c) = m3 + m4
In cache line number 2, at a time any one of the blocks
f1 ⋅ f2 = (m1 + m2 + m3) (m3 + m4) 2, 10, 18, 26, 34, ..., 58 can be placed. Choice (B)
= m1 ⋅ m3 + m1 ⋅ m4 + m2 ⋅ m3 + m2 m4 + m3 ⋅ m3 + m3 ⋅ m4
29. –30.375 = –11110.011 = –1.1110011 × 2 4
= m3 (all other terms will be zero)
Sign = 1
In the given problem f (A, B, C) = X ⋅ Y
Mantissa = 11100110000000000000000
= Sm(1, 3, 4, 5, 7)
Exponent = 4
So X, Y = Sm (0, 2, 6) (the remaining min terms)
Biased exponent = 127 + 4 = 131 = 10000011
g(A, B, C) = Y ⋅ Z = Sm (4, 6) \ –30.375 in IEEE standard is
X and Y are having (0, 2, 6) min terms in common, 1100 0001 1 111 0011 0000 0 000 0 000 0 000
i.e., Y will have all these 3 min terms. C 1 F 3 0 0 0 0
Similarly Y and Z have (4, 6) min terms in common, = (C1F30000)16. Choice (A)
So Y will have these 2 min terms also.
30. First write operation requires 600 ns. (100 ns for bus,
So Y = Sm (0, 2, 4, 6) Choice (C)
500 ns for store)
25. From the above solution During the store operation of first write another request
f (A, B, C) = XY = Sm (1, 3, 4, 5, 7) may be given to bus.
X ⋅ Y = Sm (0, 2, 6) So we can start a write operation after every 100 ns.
g (A, B, C) = Y Z = Sm(4, 6) \ Maximum number of stores that can be initiated in
The min terms common to X Y and Y Z are 1 109
one second = = 2 = 107 Choice (B)
XY ⋅ YZ = XYZ = Sm (6) 100 ns 10
i.e., The output X = 1, Y = 1, Z = 1 only for
31. Total time taken for one operation = 15 + 15 + 20
the min term 6, i.e., ABC = 110. Choice (D)
= 50 ns
 Computer Organization and Architecture Test 5 | 3.49

One operation requires 50 × 10–9 sec The resultant must have four decimal places (by trunca-
In one second, number of operations completed tion)
1 \ Sum is 0.2901 × 102. Choice (A)
= = 2 × 107. Choice (B)
50 × 10 −9 33. For high performance use SRAM and for low cost use
DRAM. Choice (B)
32. 0.2233 × 102
+0.6688 × 101 34. Average instruction time on a pipelined processor
? = 1 ns + 0.1 ns = 1.1 ns. Choice (C)
__________
First equate the exponents 35. Average instruction time on a non-pipelined processor
0.6688 × 101 = 0.06688 × 102 = 1 + ((3 × 0.8) + (5 × 0.1) + (4 × 0.1)) = 4.3 ns
0.22330 × 102 Speed up =
4.3
= 3.9 Choice (B)
0.06688 × 102 1.1
0.29018 × 102