JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD MCA 2020 COMPUTER ORGANIZATION Previous Question Paper (October/ November - 2020 - R17)

To simplify the function F(w, x, y, z) = Σ(2, 3, 4, 5, 6, 7, 11, 14, 15) in product-of-sums (POS) form, we first identify the zeros of the function, which are the minterms of the complement F'. The zeros are at indices: 0, 1, 8, 9, 10, 12, 13.

Mapping these onto a 4-variable K-map:

Grouping the zeros (F'):

1. Group 1 (corners): m0, m2, m8, m10 (simplified to y'z')
2. Group 2: m0, m1, m4, m5 (simplified to w'y)
3. Group 3: m8, m9, m12, m13 (simplified to wy')
4. Group 4: m12, m14 (simplified to wxy')

The complement function is F' = y'z' + w'y + wy' + wxy'. Applying De Morgan's theorem to find F in POS form:

(a) The OR-AND logic diagram consists of four OR gates feeding into a single AND gate. The inputs to the OR gates are (y, z), (w, y'), (w', y), and (w', x', y) respectively.

(b) The NOR-NOR logic diagram is constructed by replacing each OR gate with a NOR gate and the final AND gate with a NOR gate, while inverting the inputs to the final NOR gate. This results in a two-level NOR gate structure equivalent to the POS expression.

Cache mapping techniques determine how memory blocks are placed into cache lines. To illustrate these, consider a system with a main memory of 16 blocks (0-15) and a cache of 4 lines (0-3).

1. Direct Mapping: Each memory block maps to a specific cache line using the formula: Cache Line = Block Address mod (Number of Cache Lines). For example, blocks 0, 4, 8, and 12 all map to cache line 0. This is simple and fast but leads to high conflict misses if two frequently used blocks map to the same line.

2. Associative Mapping: Any memory block can be placed in any cache line. The cache controller searches all lines simultaneously using a tag comparison. For our example, block 5 could reside in line 0, 1, 2, or 3. This eliminates conflict misses but requires expensive comparator hardware for every cache line.

3. Set-Associative Mapping: The cache is divided into sets, each containing multiple lines. A block maps to a specific set (using modulo arithmetic) but can reside in any line within that set. In a 2-way set-associative cache, our 4 lines form 2 sets (Set 0: lines 0,1; Set 1: lines 2,3). Block 4 maps to Set 0 (4 mod 2 = 0) and can occupy either line 0 or 1. This provides a balance between the low cost of direct mapping and the flexibility of associative mapping, significantly reducing conflict misses.