B.

Tech(CSE) – Computer Architecture and Organization – CSE2001 – Fall 2016

Problem Set

1. Perform the division of (117) ÷ (-9) using Restoring and Non restoring division algorithm.

2. Show the contents of registers E, A, Q and SC during the process of multiplication of two
binary numbers, 11111 (multiplicand) and 10101 (multiplier) using Booths Algorithm.
3. Show step by step process of modified booth multiplication algorithm with the flowchart
for 15 x -13.
4. Give examples for the following four different cases (i) carry, overflow (ii) no carry,
overflow (iii) carry, no overflow (iv)no carry, no overflow.
5. Give the algorithm for Non restoring division and perform the same on (27) ÷ (-6)
6. How do you determine the overflow in each of the representations? (i) signed magnitude
addition and subtraction (ii) two's complement addition and subtraction (iii) unsigned
addition and subtraction? Illustrate each case with an example.
7. Give the algorithm for 2’s complement addition and subtraction and perform the same on
1011111 + 0101101.
8. Compare and contrast Booth with modified booth multiplication Algorithm.
9. Represent -35 and 75 in a) Sign magnitude b) ones complement c) twos complement
format.
10. State and prove the Bit pair recording table of modified Booths Algorithm.
11. Represent +12.456 in single precision IEEE 754 format.
12. Represent – 23.543 in double precision IEEE 754 format.
13. Determine the value of 1 10101011 11100101000000000000000 in decimal.
14. Determine the value of
0 11101011010 1110101010000000000000000000000000000000000000000000
15. For the hexadecimal main memory addresses 111111, 666666,BBBBBB, show the
following information, in hexadecimal format:
a. Tag, Line, and Word values for a direct-mapped cache, where tag – 8bits, line
– 14 bits, word – 2 bits
b. Tag and Word values for an associative cache, where tag – 22 bits, word – 2
bits

Dr. Saritha V, Associate Professor, Scope, VIT University page. 1

B.Tech(CSE) – Computer Architecture and Organization – CSE2001 – Fall 2016

c. Tag, Set, and Word values for a two-way set-associative cache, where tag – 9
bits, set – 13 bits, word – 2 bits

16. List the following values:

d. For the direct cache from the below Fig: address length, number of
addressable units, block size, number of blocks in main memory, number of
lines in cache, size of tag

e. For the associative cache from below Figure: address length, number of
addressable units, block size, number of blocks in main memory, number of
lines in cache, size of tag

f. For the two-way set-associative cache example of Figure 4.15: address length,
number of addressable units, block size, number of blocks in main memory,
number of lines in set, number of sets, number of lines in cache, size of tag

17. Consider a 32-bit microprocessor that has an on-chip 16-KByte four-way set-
associative cache. Assume that the cache has a line size of four 32-bit words. Draw a
block diagram of this cache showing its organization and how the different address
fields are used to determine a cache hit/miss. Where in the cache is the word from
memory location ABCDE8F8 mapped?

18. Consider a machine with a byte addressable main memory of 216 bytes and block
size of 8 bytes. Assume that a direct mapped cache consisting of 32 lines is used with
this machine.
g. How is a 16-bit memory address divided into tag, line number, and byte
number?
h. Into what line would bytes with each of the following addresses be stored?

0001 0001 0001 1011

1100 0011 0011 0100
1101 0000 0001 1101
1010 1010 1010 1010

i. Suppose the byte with address 0001 1010 0001 1010 is stored in the cache.
What are the addresses of the other bytes stored along with it?
j. How many total bytes of memory can be stored in the cache?
k. Why the tag is also stored in the cache?

Dr. Saritha V, Associate Professor, Scope, VIT University page. 2

B.Tech(CSE) – Computer Architecture and Organization – CSE2001 – Fall 2016

19. A set-associative cache has a block size of four 16-bit words and a set size of 2.
The cache can accommodate a total of 4096 words. The main memory size that is
cacheable is 64K × 32 bits. Show how the processor’s addresses are interpreted?

20. Consider a memory system that uses a 32-bit address to address at the byte level,
plus a cache that uses a 64-byte line size.
l. Assume a direct mapped cache with a tag field in the address of 20 bits. Show
the address format and determine the following parameters: number of
addressable units, number of blocks in main memory, number of lines in
cache, size of tag.
m. Assume an associative cache. Show the address format and determine the
following parameters: number of addressable units, number of blocks in main
memory, number of lines in cache, size of tag.
n. Assume a four-way set-associative cache with a tag field in the address of 9
bits. Show the address format and determine the following parameters:
number of addressable units, number of blocks in main memory, number of
lines in set, number of sets in cache, number of lines in cache, size of tag.

21. Consider a computer with the following characteristics: total of 1Mbyte of main
memory; word size of 1 byte; block size of 16 bytes; and cache size of 64 Kbytes.
o. For the main memory addresses of F0010, 01234, and CABBE, give the
corresponding tag, cache line address, and word offsets for a direct-mapped
cache.
p. Give any two main memory addresses with different tags that map to the same
cache slot for a direct-mapped cache.
q. For the main memory addresses of F0010 and CABBE, give the corresponding
tag and offset values for a fully-associative cache.
r. For the main memory addresses of F0010 and CABBE, give the corresponding
tag, cache set, and offset values for a two-way set-associative cache.

22. Consider the following code:

for (i = 0; i < 20; i++)
for ( j = 0; j < 10; j++)
a[i] = a[i] * j
a. Give one example of the spatial locality in the code.
b. Give one example of the temporal locality in the code.

23. Consider a memory system with the following parameters:

Tc = 100ns; Tm = 1200ns
If the effective access time is 10% greater than the cache access time, what is the hit
ratio H for look through cache?

24. Consider a look through cache with an access time of 1 ns and a hit ratio of H
0.95. Suppose that we can change the cache design (size of cache, cache organization)
such that we increase H to 0.97, but increase access time to 1.5 ns. What conditions
must be met for this change to result in improved performance?

25. A computer employs RAM chips of 128 x 8 and ROM chips of 512 x 8. The
computer system needs 256 *16 of RAM, 1024 x 16 of ROM, and two interface units
with 256 registers each.

Dr. Saritha V, Associate Professor, Scope, VIT University page. 3

B.Tech(CSE) – Computer Architecture and Organization – CSE2001 – Fall 2016

Show the chip layout for the given specifications.

26. A computer employs RAM chips of 128 x 8 and ROM chips of 512 x 8. The
computer system needs 512 *8 of RAM, 512 x 16 of ROM, and two interface units
with 256 registers each.
Show the chip layout for the given specifications.

27. If the received data is 101110011001. Determine whether single bit error or more
than one bit error occurs. If there is an error in single bit, perform error correction.

28. If the received data is 001101100111. Determine whether single bit error or more
than one bit error occurs. If there is an error in single bit, perform error correction.

29. Calculate the check bits for the data bits 101100110101.

30. Compare the performance of FIFO, LRU and optimal page replacement
algorithms in terms of hit ratio considering three pages to be in memory at a time for
the following sequence.
2 3 2 1 5 2 4 5 3 2 5 2

Dr. Saritha V, Associate Professor, Scope, VIT University page. 4