GTU COA (Computer Organization & Architecture) Summer 2020 Paper Solutions

Download Question Paper : click here

Q.1

(a) Enlist register reference instructions and explain any one of them in detail.

Register reference instructions -

1. CLA
2. CLE
3. CMA
4. CME
5. CIR
6. CIL
7. INC
8. SPA
9. SNA
10. SZA
11. SZE
12. HLT

HLT - The HLT (Halt) instruction is used to stop the execution of a program or processor, bringing it to a halt and indicating the end of its operation. It ensures that the processor does not perform any further instructions until it is reset or another action is taken to resume its operation.

(b) What is combinational circuit? Explain multiplexer in detail. How many NAND gates are needed to implement 4 x 1 MUX?

Combinational circuit - A combinational circuit is a digital circuit that produces an output based only on the current input values, without any internal memory or state. It uses logic gates and Boolean logic functions to compute the output directly from the present input conditions, without considering previous states or feedback.

Multiplexer - A multiplexer, commonly known as a mux, is a combinational circuit that selects and outputs a single data input from multiple input lines based on the control signals. It acts as a data selector, routing the desired input to the output line.

A multiplexer typically has 2^n input lines, where 'n' represents the number of select lines or control signals.

The select lines of a multiplexer control which input line is connected to the output. By changing the combination of select line inputs, different input lines can be selected

The total number of NAND gates required to implement a 4×1 multiplexer is (assuming a NAND gate of any number of inputs is available) 7

(c) Draw the flowchart for instruction cycle and explain.

1. Start (SC = 0): The instruction cycle begins with the sequence counter (SC) set to 0.
2. Fetch Instruction (T0): Copy the program counter (PC) to the address register (AR) and retrieve the instruction from memory.
3. Load Instruction (T1): Load the fetched instruction into the instruction register (IR) and increment the program counter (PC).
4. Decode Instruction (T2): Decode the operation code (OP code) in the instruction register (IR) and extract the address.
5. Check D7 and Addressing Mode: Check D7 bit to determine the instruction type (input/output, register reference, or memory reference).
6. Indirect Addressing (if applicable): If the instruction is a memory reference with indirect addressing, update the address register (AR) with the value stored at the memory location pointed to by AR.
7. Execute Instruction: Perform the operation specified by the instruction.
8. Repeat: Cycle back to T0 and continue with the next instruction.

Q.2

(a) What is RAM and ROM?

RAM (Random Access Memory):

• Volatile and temporary computer memory that loses its contents when power is turned off.
• Serves as the primary storage for actively used data and program instructions.
• Allows for random access, enabling the CPU to directly access any memory location in constant time.

ROM (Read-Only Memory):

• Non-volatile and permanent computer memory that retains its contents even when power is turned off.
• Contains pre-programmed data that is set during manufacturing and cannot be modified or erased by normal operations.
• Often used to store firmware, including low-level software instructions and device settings such as BIOS.

(b) One Hypothetical basic computer has the following specifications

Addressing Mode = 16 Total Instruction Types = 4 (IT1,IT2,IT3,IT4) Each of the instruction type has 16 different instructions. Total General Purpose Register = 8 Size of Memory = 8192 x 8 bits Maximum number of clock cycles required to execute one instruction = 32 Each instruction of the basic computer has one memory operand and one register operand in addition to other required fields. a. Draw the instruction word format and indicate the number of bits in each part. b. Draw the block diagram of control unit

(a) Instruction Word Format

• 16 x 4 = 64
• log₂64 = 6

Total No. of Addressing Modes

• 16
• log₂16=4

Total No. of General Purpose Register

• 8
• log₂8 = 3

Size of Memory

• 8192 bytes
• Address Bits = log₂8192 = 13

(b) Block Diagram of Control Unit

(c) Write an assembly language program to find the Fibonacci series up to the given number

Suppose we want to generate the Fibonacci series up to the 10th number.

1. We start with two variables, "A" and "B". Initially, "A" is set to 0 and "B" is set to 1. These variables will help us keep track of the current and previous numbers in the series.
2. We also set a limit to 10, which means we want to generate 10 numbers in the series.
3. We store the current number (initially 0) in a temporary variable "E".
4. To calculate the next number in the series, we add the current number (A) to the previous number (B). The sum becomes the new current number.
5. We then update the previous number by assigning the current number (stored in "E") to it.
6. Next, we decrease the limit by 1 to keep track of the remaining numbers to be generated.
7. We check if the limit is zero. If it's not zero, we repeat the steps from 3 to 7 to generate the next number in the series.
8. Once the limit becomes zero, we stop the program.
9. The generated Fibonacci series will be stored in memory.

OR

(c) Write an assembly language program to find average of 15 numbers stored at consecutive location in memory.

ORG 0000H ; Set the starting address

MOV B, 0FH ; Initialize counter B to 15
MOV C, 00H ; Initialize sum C to 0
MOV D, 00H ; Initialize intermediate result D to 0

LOOP:
  MOV A, M ; Load the number from memory
  ADD C ; Add the number to the sum
  MOV C, A ; Update the sum
  INX H ; Increment the memory pointer
  DCR B ; Decrement the counter
  JNZ LOOP ; Jump to LOOP if counter is not zero

MOV A, C ; Move the sum to register A
MOV B, 0FH ; Reset counter B to 15
DIV B ; Divide the sum by 15
MOV E, A ; Move the quotient to register E

HLT ; Halt the program

; Data section
DB 01H, 02H, 03H, 04H, 05H, 06H, 07H, 08H, 09H, 0AH, 0BH, 0CH, 0DH, 0EH, 0FH ; Example numbers

Q.3

(a) Which are different pipeline conflicts. Describe

The three main pipeline conflicts:

1. Resource Conflicts: These occur when multiple instructions need simultaneous access to the same hardware resource. They require techniques like resource sharing or scheduling to prevent contention.
2. Data Dependency Conflicts: These arise due to dependencies between instructions that prevent concurrent execution. They include Read After Write (RAW), Write After Read (WAR), and Write After Write (WAW) hazards. Techniques like forwarding and reordering are used to address these conflicts.
3. Branch Difficulties: Control hazards occur with conditional branches and jumps. They can cause pipeline stalls or incorrect speculation. Techniques like branch prediction help mitigate these difficulties.

(b) What is assembler? Draw the flowchart of second pass of the

assembler

An assembler is a software tool that translates assembly language programs into machine code, which can be executed directly by the computer's processor.

(c) Write a note on arithmetic pipeline

Arithmetic pipeline is a technique used to enhance the performance of arithmetic operations by breaking them down into smaller stages or sub-operations.

Floating point addition using arithmetic pipeline :

The following sub operations are performed in this case:

1. Compare the exponents: In this stage, the exponents of the operands are compared to determine the necessary alignment and scaling for further calculations.
2. Align the mantissas: This stage adjusts the position of the mantissas so that they have the same exponent, allowing for proper addition, subtraction, or other arithmetic operations.
3. Add or subtract the mantissas: The mantissas are added or subtracted based on the desired arithmetic operation, considering any carry or borrow from the previous stage.
4. Normalize the result: The result is normalized by adjusting the exponent and mantissa to ensure proper representation, eliminating any leading or trailing zeros and maintaining accuracy.

Example:

Let us consider two numbers,

X=0.3214*10^3 and Y=0.4500*10^2

Explanation:

First of all the two exponents are subtracted to give 3-2=1. Thus 3 becomes the exponent of result and the smaller exponent is shifted 1 times to the right to give

Y=0.0450*10^3

Finally the two numbers are added to produce

Z=0.3664*10^3

As the result is already normalized the result remains the same.

OR

Q.3

(a) What is address sequencing? Explain

• Address sequencing refers to the process of determining the sequence in which memory addresses are accessed or executed during the execution of a program or instruction.

1. Control Address Register (CAR) Incrementing: The control address register is responsible for storing the address of the next instruction to be fetched from control memory. During address sequencing, the CAR is incremented to point to the next instruction in the sequence.
2. Branching: Address sequencing involves branching based on certain conditions. This can be an unconditional branch, where the control address register is directly updated to a specific address, or a conditional branch, where the branching is determined by the status bit conditions.
3. Mapping Process: The address sequencing process also includes a mapping process to determine the specific address within the control memory. This mapping is typically done by using specific bits of the instruction address to identify the correct location in control memory where the instruction is stored.
4. Subroutine Return: Address sequencing provides a facility for subroutine return. When a subroutine is called and its execution is complete, the address sequencing mechanism allows for the return to the calling program by updating the control address register with the address to resume execution after the subroutine.

(b) Design a simple arithmetic circuit which should implement the following operations: Assume A and B are 3 bit registers. Add : A+B, Add with Carry: A+B+1, Subtract: A+B’, Subtract with

Borrow: A+B’+1, Increment A: A+1, Decrement A: A-1, Transfer A: A

(c) Explain how addition and subtraction of signed data is performed if a computer system uses signed magnitude representation.

• The two signs A, and B, are compared by an exclusive-OR gate. If the output of the gate is 0 the signs are identical; If it is 1, the signs are different.
• For addition : Identical signs dictate that the magnitudes be added. For Subtraction : Different signs dictate that the magnitudes be added. The magnitudes are added with a microoperation EA ← A + B, where EA is a register that combines E and A. The carry in E after the addition constitutes an overflow if it is equal to 1. The value of E is transferred into the add-overflow flip-flop AVF.
• For Addition : Different signs dictate that the magnitudes be subtracted. For Subtraction : Identical signs dictate that the magnitudes be subtracted. The magnitudes are subtracted by adding A to the 2's complemented B. No overflow can occur if the numbers are subtracted so AVF is cleared to 0.
• 1 in E indicates that A >= B and the number in A is the correct result. If this number is zero, the sign A must be made positive to avoid a negative zero. 0 in E indicates that A < B. For this case it is necessary to take the 2's complement of the value in A. The operation can be done with one microoperation A ← A' +1.
• However, we assume that the A register has circuits for microoperations complement and increment, so the 2's complement is obtained from these two microoperations.
• In other paths of the flowchart, the sign of the result is the same as the sign of A. so no change in A is required. However, when A < B, the sign of the result is the complement of the original sign of A. It is then necessary to complement A, to obtain the correct sign.
• The final result is found in register A and its sign in As. The value in AVF provides an overflow indication. The final value of E is immaterial.

Q.4

(a) Enlist different status bit conditions.

Different status bit conditions, also known as flags, are used to indicate specific conditions or results of operations.

1. Carry Flag (C): The Carry Flag is set if there was a carry out from or borrow into the most significant bit (MSB) during an arithmetic operation, allowing for handling of multi-byte arithmetic and checking for overflow or underflow conditions.
2. Sign Flag (S): The Sign Flag is set if the result of an operation is negative, indicated by the MSB being 1, enabling the detection of negative results for branching and conditional operations.
3. Zero Flag (Z): The Zero Flag is set when the result of an operation is zero, enabling comparisons, equality checks, and conditional branching based on zero/non-zero conditions.
4. Overflow Flag (V): The Overflow Flag is set when an arithmetic operation results in an overflow, indicating that the result is too large or too small to be represented using the available number of bits, enabling proper handling of signed arithmetic operations.

(b) What is addressing mode? Explain direct and indirect addressing mode with example.

Addressing mode refers to the way in which the operand or data is specified in an instruction. It determines how the CPU retrieves or accesses the data for processing.

1. Direct Addressing Mode: In direct addressing mode, the memory address of the operand is directly specified in the instruction. The CPU accesses the data directly from the specified memory location. Example -

   MOV R1,[100]
   
   The CPU accesses the memory location 100 directly to retrieve the data and stores it in register R1. The memory address 100 is explicitly specified in the instruction.

2. Indirect Addressing Mode: In indirect addressing mode, the instruction specifies a memory address that holds the actual address of the operand. The CPU retrieves the operand by first accessing the memory location that contains the address and then accessing the data from the address stored in that location. Example -

   MOV R1, 200
   MOV R2, [R1]
   
   In the instruction "MOV R1, 200", the value 200 is loaded into register R1. Then, in the instruction "MOV R2, [R1]", the indirect addressing mode is used. The CPU accesses the memory location specified by the value stored in register R1 (200) to retrieve the data and stores it in register R2. The actual operand is indirectly specified through the address stored in register R1.

(c) What is cache memory address mapping? Which are the different memory mapping techniques? Explain any one of them in detail.

Cache is a fast small capacity memory that should hold those information which are most likely to be accessed.

Cache memory address mapping refers to the process of mapping main memory addresses to cache memory addresses. It determines how cache blocks are assigned to specific locations in the cache.

There are three commonly used memory mapping techniques:

1. Direct Mapping
2. Associative Mapping
3. Set-Associative Mapping

Direct Mapping -

Direct mapping is a memory mapping technique used in cache systems where each block of main memory is mapped to a specific block in the cache. The mapping is determined based on the index bits of the memory address.

Working -

1. Cache Structure: The cache memory is divided into a set of fixed-size blocks, each capable of storing a fixed number of bytes. Each block has a unique identifier called a cache index.
2. Main Memory Blocks: The main memory is also divided into blocks of the same size as the cache blocks.
3. Mapping: Each main memory block is mapped to a specific cache block based on the index bits of the memory address. The number of index bits determines the number of cache blocks and the size of the cache.
4. Address Structure: A memory address consists of three components: the tag, the index, and the offset. The tag bits uniquely identify the memory block, the index bits determine the cache block, and the offset bits specify the location within the cache block.
5. Accessing Data: When a memory address is requested, the cache controller uses the index bits to identify the cache block associated with that memory address.
6. Cache Hit: If the requested memory block is present in the cache block identified by the index bits and the tag bits match, it is a cache hit. The data is retrieved from the cache, satisfying the memory request without accessing the main memory.
7. Cache Miss: If the requested memory block is not present in the cache block identified by the index bits or the tag bits do not match, it is a cache miss. In such cases, the data needs to be fetched from the main memory and stored in the cache block associated with the memory address.

Advantages of Direct Mapping:

• Simplicity: Direct mapping is easy to implement and understand due to its straightforward mapping scheme.
• Deterministic: The location of each memory block in the cache is fixed, allowing for predictable cache behavior.

Disadvantages of Direct Mapping:

• Cache Conflicts: Certain memory access patterns may result in cache conflicts, where multiple memory blocks map to the same cache block, leading to higher cache miss rates.
• Limited Flexibility: Direct mapping has limited flexibility in accommodating different memory access patterns compared to other mapping techniques.

OR

Q.4

(a) Differentiate isolated I/O and memory mapped I/O.

(b) Compare and contrast RISC and CISC.

RISC (Reduced Instruction Set Computer):

• RISC is a type of computer architecture that emphasizes simplicity and a small set of simple instructions.
• Has a limited number of addressing modes, which are ways to access data in memory.
• Instructions have a fixed length, making the processor easier to design and execute instructions quickly.
• RISC architectures are generally easier for compilers to optimize, resulting in efficient code execution.

CISC (Complex Instruction Set Computer):

• CISC is a type of computer architecture that emphasizes a rich and diverse instruction set.
• Offers a wide range of addressing modes to provide more flexibility in accessing data.
• Instructions can vary in length, which can make decoding and executing them more complex.
• CISC architectures can be more challenging for compilers to optimize, potentially leading to less efficient code execution.

(c) Explain booth’s multiplication algorithm with example.

Booth algorithm gives a procedure for multiplying binary integers in signed- 2’s complement representation

1. Booth's algorithm reduces the number of partial products, resulting in fewer additions or subtractions.
2. It utilizes shifting operations for quick multiplication by powers of 2 and aligning partial products.
3. The algorithm is particularly efficient when the multiplier has consecutive zero bits, minimizing required operations.

It works on the string bits 0's in the multiplier that requires no additional bit only shift the right-most string bits and a string of 1's in a multiplier bit weight 2ᵏ to weight 2ᵐ that can be considered as 2ᵏ⁺¹ - 2ᵐ

Example - Let’s multiply the two numbers 7 and 3 by using the Booth's multiplication algorithm.

Here we have two numbers, 7 and 3. First of all, we need to convert 7 and 3 into binary numbers like 7 = (0111) and 3 = (0011). Now set 7 (in binary 0111) as multiplicand (M) and 3 (in binary 0011) as a multiplier (Q). And SC (Sequence Count) represents the number of bits, and here we have 4 bits, so set the SC = 4. Also, it shows the number of iteration cycles of the booth's algorithms and then cycles run SC = SC - 1 time.

The numerical example of the Booth's Multiplication Algorithm is 7 x 3 = 21 and the binary representation of 21 is 10101. Here, we get the resultant in binary 00010101. Now we convert it into decimal, as (000010101) = 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21

Q.5

(a) What is associative memory? Explain.

1. Associative memory, or content-addressable memory (CAM), enables data retrieval based on content rather than memory addresses.
2. It uses parallel comparison to search and retrieve data by comparing it with stored content across all memory locations simultaneously.
3. Associative memory is commonly used in applications such as pattern recognition, database searching, and cache memory.
4. It offers fast and efficient search operations, but can be more expensive and complex to implement compared to traditional memory.

(b) Differentiate between paging and segmentation techniques used in virtual memory.

(c) Write a note on asynchronous data transfer.

Asynchronous data transfer refers to the process of transferring data between two independent units or devices where the internal timing of each unit is independent of the other.

There are two ways of achieving it -

Strobe control and Handshaking

Strobe control -

This method employs a single control line to time each transfer. This control line is also known as a strobe, and it may be achieved either by source or destination, depending on which initiate the transfer.

Source-initiated strobe for data transfer

• In the source-initiated strobe method, the source unit activates a strobe pulse to indicate that valid data is available on the data bus.
• The destination unit responds to the strobe signal and retrieves the data from the bus, typically during the active duration of the strobe signal.

Destination-initiated strobe for data transfer

• In the destination-initiated strobe method, the destination unit activates a strobe pulse to request data transfer from the source unit.
• Upon receiving the strobe signal, the source unit places the requested data onto the data bus.
• The destination unit retrieves the data from the bus during the active duration of the strobe signal.

Handshaking -

The handshake method solves the problem of Strobe method by introducing a second control signal that provides a reply to the unit that initiates the transfer.

Source-initiated transfer using handshaking

• In source-initiated transfer using handshaking, the source unit controls the timing of data transfer by initiating the handshaking signals, while the destination unit responds to the signals to indicate its readiness to receive the data.

Destination-initiated transfer using handshaking

• In destination-initiated transfer using handshaking, the destination unit initiates the data transfer by requesting data from the source unit using handshaking signals, and the source unit responds to indicate its readiness to transmit the data.

OR

Q.5

(a) Write about Time-shared common bus interconnection structure.

1. Shared Bus: Multiple devices or modules in the system share a single common bus for communication.
2. Time Division: The bus is divided into time slots, with each device assigned a specific slot for transmitting data.
3. Centralized Control: A central controller or arbiter manages bus access, coordinating the timing and sequencing of data transfers.
4. Scalability: The structure allows for system expansion by adding or removing devices without major changes to the bus architecture.

(b) Explain the working of Direct Memory Access (DMA).

DMA (Direct Memory Access) is a technique used in computer systems to allow certain devices to transfer data directly to and from the memory without involving the CPU.

Working of DMA -

1. DMA Controller: A DMA controller is responsible for managing the data transfer process. It coordinates communication between the device, memory, and CPU.
2. Device Request: When a device wants to transfer data, it sends a request to the DMA controller, specifying the source and destination addresses in memory.
3. CPU Authorization: The DMA controller seeks authorization from the CPU to access the system bus and perform the data transfer.
4. CPU Handoff: Once authorized, the CPU relinquishes control of the bus to the DMA controller, allowing it to directly transfer data between the device and memory.
5. Data Transfer: The DMA controller carries out the data transfer autonomously, using high-speed bus access to quickly move data blocks without CPU intervention.
6. Completion Interrupt: Once the data transfer is complete, the DMA controller can generate an interrupt to notify the CPU. The CPU can then resume control and process the transferred data.

(c) Write a note on interprocess communication and synchronization.

Interprocess Communication (IPC) and synchronization are essential aspects that enable processes to interact and coordinate effectively.

Interprocess Communication (IPC):

1. Purpose: IPC allows processes running on the same system to exchange information, share resources, and collaborate on tasks.
2. Message Passing: Processes can communicate by sending messages to each other, where a message contains data or requests for action.
3. Shared Memory: Processes can share a common memory region, allowing them to read from and write to the same memory locations, facilitating data sharing.
4. Pipes: Pipes provide a unidirectional communication channel between processes, with one process writing to the pipe and the other reading from it.
5. Sockets: Sockets enable communication between processes running on different systems connected over a network, allowing distributed IPC.

Synchronization:

1. Purpose: Synchronization ensures orderly and coordinated execution of processes to prevent conflicts and data inconsistencies.
2. Mutual Exclusion: Techniques like locks, semaphores, and mutexes are used to control access to shared resources, ensuring only one process can access them at a time.
3. Critical Sections: Critical sections are code segments that should be executed by only one process at a time to avoid race conditions.
4. Deadlock Avoidance: Strategies like deadlock detection and avoidance algorithms help prevent situations where processes are stuck waiting for resources indefinitely.
5. Synchronization Primitives: Tools like barriers and condition variables facilitate synchronization by allowing processes to wait for specific conditions or reach synchronization points.

ORG 0000H ; Set the starting address

MOV B, 0FH ; Initialize counter B to 15 MOV C, 00H ; Initialize sum C to 0 MOV D, 00H ; Initialize intermediate result D to 0

LOOP: MOV A, M ; Load the number from memory ADD C ; Add the number to the sum MOV C, A ; Update the sum INX H ; Increment the memory pointer DCR B ; Decrement the counter JNZ LOOP ; Jump to LOOP if counter is not zero

MOV A, C ; Move the sum to register A MOV B, 0FH ; Reset counter B to 15 DIV B ; Divide the sum by 15 MOV E, A ; Move the quotient to register E

HLT ; Halt the program

; Data section DB 01H, 02H, 03H, 04H, 05H, 06H, 07H, 08H, 09H, 0AH, 0BH, 0CH, 0DH, 0EH, 0FH ; Example numbers

ORG 0000H ; Set the starting address

MOV B, 0FH ; Initialize counter B to 15 MOV C, 00H ; Initialize sum C to 0 MOV D, 00H ; Initialize intermediate result D to 0

LOOP: MOV A, M ; Load the number from memory ADD C ; Add the number to the sum MOV C, A ; Update the sum INX H ; Increment the memory pointer DCR B ; Decrement the counter JNZ LOOP ; Jump to LOOP if counter is not zero

MOV A, C ; Move the sum to register A MOV B, 0FH ; Reset counter B to 15 DIV B ; Divide the sum by 15 MOV E, A ; Move the quotient to register E

HLT ; Halt the program

; Data section DB 01H, 02H, 03H, 04H, 05H, 06H, 07H, 08H, 09H, 0AH, 0BH, 0CH, 0DH, 0EH, 0FH ; Example numbers