Coa Notes Aktu
Coa Notes Aktu
QUANTUM SERIES
For
B.Tech Students of Second Year
of All Engineering Colleges Affiliated to
Dr. A.P.J. Abdul Kalam Technical University,
Uttar Pradesh, Lucknow
(Formerly Uttar Pradesh Technical University)
Aditya Kumar
TM
1 Introduction
CONTENTS
Part-1 : Introduction : Functional .......................... 1–2B to 1–5B
Units of Digital System
and their Interconnection
Main/Internal
Que 1.1. Draw a block diagram of a computer’s CPU showing all Main/Internal
Memory
the basic building blocks such as program counter, accumulator,
address and data registers, instruction register, control unit etc., Fig. 1.1.2.
and describe how such an arrangement can work as a computer, if
connected properly to memory, input/output etc. a. Input unit : This unit is used for entering data and programs into the
computer system by the user for processing.
AKTU 2016-17, Marks 7.5
b. Storage unit : The storage unit is used for storing data and instructions
Answer before and after processing.
Block diagram of computer’s CPU : c. Output unit : The output unit is used for storing the result as output
produced by the computer after processing.
RAM
d. Processing unit : The task of performing operations like arithmetic
Memory ADDRESS BUS Memory data and logical operations is called processing.
address MAR DATA BUS MDR register
register The Central Processing Unit (CPU) takes data and instructions from the
CPU BUS storage unit and makes all sorts of calculations based on the instructions
given and the type of data provided. It is then sent back to the storage unit.
Accumulator
Instruction Que 1.2. Explain the functional units of digital system and their
IR PC ACC (work register)
register interconnections.
Answer
Program counter Control ALU Arithmetic
logic unit The main functional units of a digital computer are shown in Fig. 1.2.1.
Control lines Clock
1. Central Processing Unit (CPU) :
Fig. 1.1.1. a. The CPU is the brain of a computer system.
A computer performs five major operations. These are : b. This unit takes the data from the input devices and processes it
according to the set of instructions called program.
1. It accepts data or instructions as input.
c. The output of processing of the data is directed to the output devices
2. It stores data and instruction.
for use in the outside world.
3. It processes data as per the instructions.
d. CPU has two major parts called ALU and Control Unit.
4. It controls all operations inside a computer.
5. It gives results in the form of output.
1–4 B (CS/IT-Sem-3) Introduction Computer Organization & Architecture 1–5 B (CS/IT-Sem-3)
b. The CPU sends signals on the control bus to enable the outputs
of addressed memory device or port device. Que 1.5. Discuss the bus arbitration.
OR
Que 1.4. Describe the architecture of bus. Write a short note on bus arbitration.
AKTU 2014-15, Marks 05
Answer
1. The computer bus consists of two parts, the address bus and a data bus. Answer
The data bus transfers actual data, whereas the address bus transfers
1. Bus arbitration is a mechanism which decides the selection of current
address or memory location of where the data should go.
master to access bus.
2. The bus provides physical links and the means of controlling the 2. Among several masters and slave units that are connected to a shared
communication exchange of signals over the bus. Fig. 1.4.1 depicts the bus, it may happen that more than one master or slave units will request
organization of a single shared bus. access to the bus at the same time.
3. In such situation, bus access is given to the master having highest
Control priority.
4. Three different mechanisms are commonly used for this :
System i. Daisy chaining :
Address
bus
a. Daisy chaining method is cheaper and simple method.
Data b. All master make use of the same line for bus request.
c. The bus grant signal serially propagates through each master
until it encounters the first one that is requesting.
Main I/O I/O ii. Parallel arbitration : The parallel arbitration consists of priority
CPU
memory device 1 device n encoder and a decoder. In this mechanism, each bus arbiter has a
bus request output line and input line.
Fig. 1.4.1. Architecture of a single shared bus.
iii. Independent priority : In this each master has separate pair of
bus request and bus grant lines and each pair has a priority
3. The principle use of the system bus is high-speed data transfer between assigned to it.
the CPU and memory.
4. Most I/O devices are slower than the CPU or the memory. The I/O Que 1.6. Discuss the advantages and disadvantages of polling
devices are attached to the system bus through external interfaces. and daisy chaining bus arbitration schemes.
5. The Input/Output (I/O) ports are used to connect various devices to the
AKTU 2015-16, Marks 10
computer and hence, enable communication between the device and
the computer. OR
Explain dais y changing method. Write its advantages and
disadvantages.
PART-3
Answer
Bus Arbitration.
Daisy chaining :
1. In this, all masters make use of the same line for bus request.
Questions-Answers 2. The bus grant signal serially propagates through each master until it
encounters the first one that is requesting access to the bus.
Long Answer Type and Medium Answer Type Questions 3. This master blocks the propagation of the bus grant signal, activates the
busy line and gains control of the bus.
4. Therefore any other requesting module will not receive the grant signal
and hence cannot get the bus access.
1–8 B (CS/IT-Sem-3) Introduction Computer Organization & Architecture 1–9 B (CS/IT-Sem-3)
Output Y = A if C = 1 2. It allows compatibility and provides ease of operation and high bandwidth.
Normal input A
High if C = 0 Disadvantages of single shared bus are :
1. The main disadvantage of the shared bus is that its throughput limits
Control input C
Fig. 1.8.1. the performance boundary for the entire multiprocessor system. This is
because at any time only one memory access is granted, likely causing
8. The control input determines the output state.
some processors to remain idle. To increase performance by reducing
9. When the control input is equal to 1, the output is enabled and the gate the memory access traffic, a cache memory is often assigned to each
behaves like any conventional buffer, with the output equal to the processor.
normal input.
2. Another disadvantage of the shared bus design is that, if the bus fails,
10. When the control input is 0, the output is disabled and the gate goes to catastrophic failure results. The entire system will stop functioning since
a high state, regardless of the value in the normal input. no processor will be able to access memory.
11. A large number of three state gate outputs can be connected with wires
to form a common bus line without endangering loading effects. Que 1.10. What is the benefit of using multiple bus architecture
Bus line for bit 0 compared to a single bus architecture ?
A0
B0 Answer
Following are the benefits of using multiple bus architecture compared to
C0
single bus architecture :
D0
S1 1. Single bus have long control sequence because only the data item can be
Select 0
transferred over the bus in a clock cycle.
S0 2 × 4 1
decoder 2 2. To reduce the number of steps needed, most commercial processor
Enable E 3 provides multiple internal paths using multiple buses.
Fig. 1.8.2. 3. The introduction of incrementer unit eliminates the need to add port to
12. The outputs of four buffers are connected together to form a single the PC using the main ALU.
bus line. 4. By providing more paths for data transfer, a significant reduction in the
13. The control inputs to the buffers determine which of the four normal number of clock cycles needed to execute an instruction is achieved.
inputs will communicate with the bus line.
14. Not more than one buffer may be in the active state at any given time. PART-5
15. To construct a common bus for four registers of n bits each using three
Processor Organization, General Register Organization.
state buffers, we need n circuits with four buffers in each.
16. Each group of four buffers receives one significant bit from the four
registers.
Questions-Answers
17. Only one decoder is necessary to select between the four registers.
Que 1.9. Explain why the single shared bus is so widely used as Long Answer Type and Medium Answer Type Questions
an interconnection medium in both sequential and parallel
computers. What are its main disadvantages ?
Que 1.11. Explain general-purpose register based organization.
Answer
Single shared bus is so widely used as an interconnection medium in both Answer
sequential and parallel computer because of following reasons :
1. In this organization, the registers communicate with each other not
1. The shared bus is the simplest and least expensive way of connecting
only for direct data transfers, but also while performing various micro-
several processors to a set of memory modules.
operations.
1–12 B (CS/IT-Sem-3) Introduction Computer Organization & Architecture 1–13 B (CS/IT-Sem-3)
4. The buses A and B are used to form the inputs to the common arithmetic EMPTY FULL
logic unit (ALU).
EMPTY = 1
5. The operation to be performed is selected in the ALU and is determined when stack is empty
by the arithmetic or logic micro-operation by using function select lines
PQR 3
(OPR). Stack pointer (SP) XYZ 2
(consists of 6 bits)
6. The result of the micro-operation is available as output data and also ABCD 1
goes into the inputs of all the registers. 0
Holds the data to be pushed Data
7. Any one of the destination register receives the information from the onto stack or that is popped Register
output bus which is selected by a decoder. off from the stack (DR)
Comparison between register stack and memory stack : 4. Accumulator (ACC) : This block acts as the default temporary storage
register location for all mathematical operations in ALU.
S. No. Register stack Memory stack
5. Instruction Register IR and Decoder : After instruction is fetched
1. Register stacks are momentary Memory stacks are a series of from the memory its stored in Instruction Register. The instruction is
spaces for internal processes memory spaces that is used in then decode by the decoder.
that are being done by the the processes that is done by 6. Stack pointer (SP) : Stack pointer is involved in managing the stack
processor. processor and are temporarily transfers during and program execution.
stored in registers. 7. Timing and control unit : This block manages the sequencing of
events on a timeline between various components of a CPU. All the
2. Register stack is generally on Memory stack is on RAM.
blocks are controlled in a manner to optimize the computational power
(CPU).
of the unit by minimizing the failures.
3. Access to register stack is faster. Access to memory stack is 8. Flags : Flags are also registers or bits inside registers which are set or
slower. cleared for a particular condition on an arithmetic operation. Some of
4. It is limited in size. It is large in size. the most common flags are :
i. Sign : Is used to identify the set/reset of most significant bit of the
Que 1.15. Explain an accumulator based central processing unit result.
ii. Carry : Is used to identify, a carry during addition, or borrow
organization with block diagram. during subtraction/comparison.
iii. Parity : Set if the parity is even. Refer parity from here.
Answer
iv. Zero : To identify when the result is equal to zero.
Internal bus 9. Bus sub-system : All the data transfers in-between memory and CPU
registers including instruction fetches are carried over bus.
Flags General purpose Que 1.16. Explain various types of processor organization.
ALU
registers
AKTU 2015-16, Marks 10
IR
R1
Answer
Decoder R2
Types of processor organizations :
R3
1. General-purpose register based : Refer Q. 1.11, Page 1–11B, Unit-1.
2. Stack based : Refer Q. 1.12, Page 1–13B, Unit-1.
ACC PC 3. Accumulator based : Refer Q. 1.15, Page 1–16B, Unit-1.
SP
PART-7
Timing and control unit
Addressing Modes.
Fig. 1.15.1. Block diagram of accumulator based CPU organization.
1. ALU : A most generic computer system is composed of a unit to do
arithmetic, shift and logical micro-operations commonly known as ALU Questions-Answers
of CPU.
2. Program Counter (PC) : This keeps track of the instruction address Long Answer Type and Medium Answer Type Questions
in memory from where the next instruction needs to be fetched. The
instructions are stored in memory in an order decided by programmer.
3. General purpose registers (R1, R2, R3) : It suggests that the registers
are involved in operations like load inputs, store intermediate results of Que 1.17.
3.17. Write short note on relative addressing mode and
arithmetic, logical and shift micro-operations. The initial inputs are loaded indirect addressing mode.
into registers from memory and final results are later moved into memory. OR
1–18 B (CS/IT-Sem-3) Introduction Computer Organization & Architecture 1–19 B (CS/IT-Sem-3)
Explain the following addressing modes with the help of an example iii. Relative addressing :
each : 1. Relative addressing means that the next instruction to be carried
i. Direct ii. Register indirect out is an offset number of locations away, relative to the address of
iii. Implied iv. Immediate the current instruction.
2. Consider this bit of pseudo-code
v. Indexed AKTU 2014-15, Marks 10
Jump + 3 if accumulator = = 2
Code executed if accumulator is NOT = 2
Answer Jump + 5 (unconditional relative jump to avoid the next line of code)
i. Direct : acc : (code executed if accumulator is = 2)
1. A very simple form of addressing is direct addressing, in which the 3. In the code, the first line of code is checking to see if the accumulator
address field contain the effective address of the operand : EA = A has the value of 2 then the next instruction is 3 lines away.
where, EA = Actual (effective) address of the location 4. This is called a conditional jump and it is making use of relative
containing the referenced operand. addressing.
A = Contents of the address field in the instruction. iv. Register indirect mode :
Instruction 1. Register indirect mode is similar to indirect addressing.
2. The only difference is whether the address field refers to a memory
Memory location or a register.
3. Thus, for register indirect address, EA = (R)
Operand Instruction
R
Memory
Fig. 1.17.1. Direct.
2. A direct address in instruction needs two reference to memory :
a. Read instruction b. Read operand Operand
ii. Displacement addressing : Registers
1. A very powerful mode of addressing combines the capabilities of
direct addressing and register indirect addressing. Fig. 1.17.3. Register indirect.
2. It is known by a variety of names depending upon the content of v. Implied mode :
its use but the basic mechanism is the same. 1. In this mode, the operands are specified implicitly in the definition
3. Displacement addressing requires that the instruction have two of the instruction.
address fields, at least one of which is explicit. 2. All register reference instructions that use an accumulator are
4. The value contained in one address field (value = A) is used directly. implied mode instructions.
5. The other address field or an implicit reference based on opcode, 3. Zero address instructions in a stack-organized computer are implied
refers to a register whose contents are added to A to produce the mode instruction since the operands are implied to be on top of the
effective address. stack. It is also known as stack addressing mode.
Instruction Instruction
R A Implicit
Memory
Instruction
Addressing Effective Content
Operand Mode Address of AC
Fig. 1.17.5. Immediate mode. Direct address 500 800
vii. Indexed :
1. The effective address of the operand is generated by adding a Immediate operand 201 500
constant value to the contents of a register.
Indirect address 800 300
2. The register used may be either a special register for this purpose
or more commonly, it may be any one of a set of general purpose Indexed address 600 900
registers in the CPU.
3. It is referred to as an index register. We indicate the index mode Implied – 400
symbolically as, X(R) Register indirect 400 700
where X denotes a constant and R is the name of register involved.
4. The effective address of the operand is given by, EA = X + [R]
5. In the process of generating the effective address, the contents of Que 1.18. What is difference between implied and immediate
the index register are not changed.
Instruction
addressing modes ? Explain with an example.
R A
Memory Answer
Here the contents of R2 are first used as an EA then these are incremented. Q. 4. Explain the operation of three state bus buffers and show
Auto decrement mode : its use in design of common bus.
1. In this mode the contents of a register specified in the instruction are Ans. Refer Q. 1.8.
decremented.
2. These contents are then used as the effective address of the operand. Q. 5. What is stack ? Give the organization of register stack
Example : Add – (R2), R0 with all necessary elements and explain the working of
Here the contents of R2 are first decremented and then used as an EA for push and pop operations.
the operand which is added to the content of R0. Ans. Refer Q. 1.12.
Que 1.20. How addressing mode is significant for referring Q. 6. What is a memory stack ? Explain its role in managing
memory ? List and explain different types of addressing modes. subroutines with the help of neat diagrams.
Ans. Refer Q. 1.13.
AKTU 2016-17, Marks 15
Q. 7. Explain various types of processor organization.
Answer Ans. Refer Q. 1.16.
1. The addressing mode is significant for referring memory as it is a code
that tells the control unit how to obtain the Effective Address (EA) Q. 8. Explain the following addressing modes with the help of an
from the displacement. example each :
2. Addressing mode is a rule of calculation, or a function that use i. Direct ii. Register indirect
displacement as its main argument and other hardware component as iii. Implied iv. Immediate
(such as PC, registers and memory locations) as secondary arguments v. Indexed
and produce the EA as a result. Ans. Refer Q. 1.17.
Types of addressing modes : Refer Q. 1.17, Page 1–17B, Unit-1.
Q. 9. How addressing mode is significant for referring memory ?
List and explain different types of addressing modes.
VERY IMPORTANT QUESTIONS Ans. Refer Q. 1.20.
2
PART-1
Arithmetic and Logic Unit : Look Ahead Carries Adders.
Answer
Part-1 : Arithmetic and Logic Unit : ...................... 2–2B to 2–4B 1. By combining arithmetic and logic circuits with the help of multiplexer,
Look Ahead Carries Adders we can get the arithmetic and logic units.
Cin Cout
Part-2 : Multiplication : Signed ............................. 2–4B to 2–11B Ai
Operand Multiplication, Booth’s
Bi Arithmetic
Algorithm and Array Multiplier
S0 circuit
Part-3 : Division and Logic Operations ............. 2–11B to 2–16B S1
S2 MUX Yi
Part-4 : Floating Point Arithmetic ...................... 2–16B to 2–21B Logic
Operations, Arithmetic & Logic circuit
Unit Design Select line
Fig. 2.1.1. Block diagram of ALU.
Part-5 : IEEE Standard for .................................. 2–21B to 2–24B 2. When the mode select line S2 = 0, this ALU acts as an arithmetic circuit,
Floating Point Numbers
so the output of arithmetic circuit is transferred as final output.
3. Otherwise (S2 = 1) the output of the logic circuit is transferred as final output.
4. Based on the mode select S2 and input carry Cin, we increase or decrease
the number of arithmetic and logic operations.
5. When S2 = 0, the ALU performs arithmetic operation and when
S2 =1, with Cin = 0, the ALU performs logic operations.
6. We know that the carry input is not required in the logic circuits.
7. When logic operation is selected (S2 = 1), the carry input must be zero.
8. This given us the output sum in full adder circuit as
Yi = Ai Bi Ci ( Ci = 0)
Yi = Ai Bi
Answer
1. A Carry Look Ahead adder (CLA) or fast adder is a type of adder used in
digital logic.
Computer Organization & Architecture 2–3 B (CS/IT-Sem-3) 2–4 B (CS/IT-Sem-3) Arithmetic and Logic Unit
Questions-Answers
Pi Ci+ Gi
Ci Ci + 1
Long Answer Type and Medium Answer Type Questions
Fig. 2.2.1.
9. Consider the circuit of the full adder shown in Fig. 2.2.1. If we define two
new binary variables, Que 2.3. Explain the Booth’s algorithm in depth with the help of
Pi = Ai Bi , Gi = AiBi flowchart. Give an example for multiplication using Booth’s
10. The output sum and carry can respectively be expressed as algorithm. AKTU 2016-17, Marks 15
Si = Pi Ci , Ci+1 = Gi + PiCi OR
11. Gi is called a carry generate, and it produces a carry of 1 when both Ai Discuss the Booth’s algorithm for 2’s complement number. Also
and Bi are 1, regardless of the input carry Ci. Pi is called a carry propagate, illustrate it with the some example.
because it determines whether a carry into stage i will propagate into OR
stage i + 1. Explain Booth’s multiplication algorithm in detail.
C0 = input carry
AKTU 2017-18, Marks 07
C1 = G0 + P0C0
C2 = G1 + P1C1 = G1 + P1(G0 + P0C0) Answer
= G1 + P1G0 + P0P1C0
The algorithm for 2’s complement multiplication is as follows :
C3 = G2 + P2C2 = G2 + P2G1 + P2P1G0 + P2P1P0C0
Computer Organization & Architecture 2–5 B (CS/IT-Sem-3) 2–6 B (CS/IT-Sem-3) Arithmetic and Logic Unit
10 Is LS 01
bit of Q and Add/Sub
A=A–B A=A+B Cin Control
Qn + 1 are n-bit adder
logic
Enable
00
n n
Perform 1-bit arithmetic right Shift right
shift A, Q n and Q n + 1
then decrement CR by 1
An–1 An–2 .......... A1 A0 Qn–1 Qn–2 .......... Q1 Q0 Q–1
no is 1 bit
CR = 0 register
? Fig. 2.4.1. Hardware implementation of signed
yes binary multiplication for Booth’s algorithm.
Final result in A and Q
4. Multiplier and multiplicand are loaded into register Q and register B
Fig. 2.3.1. 2’s Complement multiplication. respectively.
Example : Both negative (– 5 × – 4) 5. Register A and Q–1 and initially set to 0.
6. The n-bit adder performs addition, input of adders comes from
Multiplicand (B) 1 0 1 1 (– 5) Multiplier (Q) 1 1 0 0 (– 4) multiplicand and content of register A.
A Qn Qn + 1 Operation CR 7. In case of addition, Add / Sub line is 0, therefore, Cin = 0 and multiplicand
is directly applied as a second input to the n-bit adder.
0000 1100 0 Initial 4
0000 0110 0 Shift right 3 8. In case of subtraction, Add / Sub line is 1, therefore Cin = 1 and
multiplicand is complemented and then applied to the n-bit adder. As a
0000 0011 0 Shift right 2 result, the 2’s complement of the multiplicand is added to the content
0101 0011 0 AA–B 1 of register A.
9. The control logic scans bit Q0 and Q–1 one at a time and generates the
0010 1001 1 Shift right control signals to perform the corresponding function.
0001 0100 1 Shift right 0 10. If the two bits are same (1 – 1 or 0 – 0), then all the bits of A, Q and
Q– 1 register are shifted to right 1 bit without addition or subtraction
Result : 0001 0100 = + 20 (Add/Subtract Enable = 0).
Computer Organization & Architecture 2–7 B (CS/IT-Sem-3) 2–8 B (CS/IT-Sem-3) Arithmetic and Logic Unit
11. If the two bits differ, then the multiplicand is added to or subtracted
from the A register, depending on the status of bits. Que 2.6. Show step by step the multiplication process using
12. After addition or subtraction right shift occurs such that the left most Booth’s algorithm when (+ 15) and (– 13) numbers are multiplied.
bit of A (An – 1) is not only shifted into An – 2, but also remains in An – 1. Assume 5-bit registers that hold signed numbers.
13. This is required to preserve the sign of the number in A and Q.
AKTU 2014-15, Marks 10
Que 2.5. Draw the data path of 2’s compliment multiplier. Give
Answer
the Robertson multiplication algorithm for 2’s compliment fractions.
Also illustrate the algorithm for 2’s compliment fraction by a suitable 15 = 0 1 1 1 1
– 13 = 2’s complement of 13 = 1 0 0 1 1
example. AKTU 2017-18, Marks 07 Multiplicand (M) = 0 1 1 1 1, Multiplier = 1 0 0 1 1
A Qn Qn+1 Operation SC
Answer
00000 10011 0 101 (5)
Datapath of 2’s compliment multiplier : Refer Q. 2.3, Page 2–4B,
Unit-2. 10001 10011 0 AA – M
Robertson algorithm : 11000 11001 1 Shift 100 (4)
1. A 0, B Multiplicand Q Multiplier and count n. 11100 01100 1 Shift 011 (3)
2. If Q0 = 1 then perform A A + B. 01011 01100 1 AA + M
3. Shift right register F.A.Q by 1 bit F B [n – 1] AND Q[0] OR F and
00101 10110 0 Shift 010 (2)
count count – 1.
4. If count > 1 Repeat steps 2 and 3, otherwise if Q0 = 1 then perform 00010 11011 0 Shift 001 (1)
A A – B and set Q [0] = 0. 10011 11011 0 AA – M
For example : We perform the multiplication of fraction as : 11001 11101 1 Shift 000 (0)
Multiplicand = 0.625 Result = (11001 11101) = – 195(2’s complement of +195)
Multiplier = 0.5
Equivalent binary representation 0.625 = 0101 Que 2.7. Show the contents of the registers E, A, Q, SC during the
2’s complement representation – 0.625 = 1010 + 1 (– 0.625) = 1011
process of multiplication of two binary numbers 11111 (multiplicand)
Equivalent binary representation + 0.5 = 0100
10101 (multiplier). The signs are not included.
2 complement representation – 0.5 = 1011 + 1 – 0.5 = 1100
B AKTU 2016-17, Marks 10
0 1 0 1
F A Q Answer
Steps 0 0 0 0 0 0 1 0 0 Comments
Multiplicand B = 11111 E A Q SC
Step 1 0 0 0 0 0 0 1 0 0 Q0 = 0, No need addition 0 00000 10101 101
0 0 0 0 0 0 0 1 0 1 bit right shift Qn = 1 ; add B 00000
Step 2 0 0 0 0 0 0 0 1 0 Q0 = 0, No need addition 11111
11111
0 0 0 0 0 0 0 0 1 1 bit right shift
Shift right EAQ 0 01111 11010 100
Step 3 0 0 1 0 1 0 0 0 1 Q0 = 1, A A + B Qn = 1 ; add B 01111
0 0 0 1 0 1 0 0 0 1 bit right shift 11111
00000
Step 4 0 0 0 1 0 1 0 0 0 Q0 = 0, No need addition
Shift right EAQ 0 00000 01101 011
Final
Final product Qn = 0 ; shift right EAQ 0 00000 00110 010
0.625 × 0.5 = 0.3125
Qn = 0 ; shift right EAQ 0 00000 00011 001
0101 × 0100 = 00101000
Qn = 0 ; shift right EAQ 0 00000 00001 000
Computer Organization & Architecture 2–9 B (CS/IT-Sem-3) 2–10 B (CS/IT-Sem-3) Arithmetic and Logic Unit
Que 2.8. Show the multiplication proces s us ing Booth’s A Qn Qn+1 B = 1001 SC
algorithm for (– 7) × (+ 3). AKTU 2018-19, Marks 07 A3B0 A2B0 A1B0 A0B0 PP0
A3B1 A2B1 A1B1 A0B1 PP1
Answer A3B2 A2B2 A1B2 A0B2 PP2
A3B3 A2B3 A1B3 A0B3 PP3
Flowchart of Booth’s algorithm for multiplication : Refer Q. 2.3,
Page 2–4B, Unit-2. P7 P6 P5 P4 P3 P2 P1 P0 PP4
Multiplication : Multiply (– 7) × (+ 3)
Convert (–7) into 2’s complement form : Fig. 2.10.1. Manual multiplication process.
+7 = 0111 3. Each shifted multiplicand which is multiplied by either 0 or 1 depending
1’s complement of (+7) = 1000 on the corresponding multiplier bit is called Partial Product (PP).
adding 1 +1 4. Each partial product consists of four product components.
—————
2’s complement of (+ 7) = 1001 P0 = A0B0
––––––––— P1 = A1B0 + A0B1
(+3) = 0011
Computer Organization & Architecture 2–11 B (CS/IT-Sem-3) 2–12 B (CS/IT-Sem-3) Arithmetic and Logic Unit
r
lie
PP2 P1
tip
division operation.
ul
A2
0 M
PP3
P2 Answer
A3 Flowchart for restoring division operation is shown in Fig. 2.12.1.
0
Start
PP4 = P7P6P5P4 ... P0
P7 P6 P5 P4 P3
Bit of incoming partial product A 0
B Divisor
Fig. 2.10.2. Block diagram of combinational multiplier.
D Dividend
7. The full adder block is represented by square block. The carries in each partial Count n
product row of full adders are connected to make 4-bit ripple adder.
8. Thus, the first 4-bit ripple adder adds the first two rows of product Shift left AQ
components to produce the first partial product.
9. The carry output generated is propagated to the most significant product A A–B
component used to produce the next partial product.
10. The subsequent adders add each partial product with the next product No Yes
A<0
component.
Q0 1 Q0 0
A A+B
PART-3 Count Count – 1
Division and Logic Operations.
No
Count = 0
Count Count – 1 Algorithm for non-restoring division : Refer Q. 2.11, Page 2–12B,
Unit-2.
For example, consider 4-bit dividend and 2-bit divisor :
Dividend = 1010, Divisor = 0011
No Count = 0 A Register Q Register
Initially 0 0 0 0 0 1 0 1 0 Dividend
Shift 0 0 0 0 1 0 1 0
Subtract 1 1 1 0 1
First Cycle
Yes set Q0 1 1 1 1 0 0 1 0 0
A<0
A A+B
Shift 1 1 1 0 0 1 0 0
Add 0 0 0 1 1
Quotient in Q Second Cycle
End Remainder in A set Q0 1 1 1 1 1 1 0 0 0
Remainder Quotient
Fig. 2.13.2. A non-restoring division example.
Computer Organization & Architecture 2–15 B (CS/IT-Sem-3) 2–16 B (CS/IT-Sem-3) Arithmetic and Logic Unit
In given example after 4 cycles register A is positive and hence step 3 is not ii. Exponent overflow : Exponent overflow refers to floating point
required. representations and refers to a positive exponent that exceeds the
maximum possible exponent value.
Que 2.14. Perform the division process of 00001111 by 0011 (use a iii. Significand overflow : Significand overflow occurs when the
addition of two significant number of the same sign results in a
dividend of 8 bits). AKTU 2018-19, Marks 07 carry out of the most significant bit.
Overflow detection : An overflow can be detected by observing the carry
Answer into the sign bit position. If these two carries are not equal, an overflow
condition is produced.
B = 0011 B + 1 = 1101
For example :
Operation E A Q SC 35 0 100011 35 1 011101
Dividend in Q, A = 0 0000 1111 40 0 101000 40 1 011000
shl EAQ 0 0001 1110 100
75 1 001011 75 10 110101
add B + 1 1101
Two carries are explicitly shown. If the two carries are applied to an
E = 0, leave Qn = 0 0 1110 1110 exclusive OR gate, an overflow would be detected when the output of
add B 0011 the gate is 1.
restore partial remainder 1 0001 011
shl EAQ 0 0011 1100
add B + 1 1101 PART-4
E = 1, set Qn to 1 1 0000 1101 Floating Point Arithmetic Operations, Arithmetic and Logic
shl EAQ 0 0001 1010 010 Unit Design.
add B + 1 1101
-
E = 0, leave Qn = 0 0 1110 1010
add B 0011 001 Questions-Answers
restore partial remainder 1 0001
Long Answer Type and Medium Answer Type Questions
shl EAQ 0 0011 0100
add B+1 1101 000
E = 1, set Qn to 1 1 0000 0101 Que 2.16. Explain the basic format used to represent floating
Remainder Quontient
point numbers.
Que 2.15. What do you mean by overflow ? Describe the overflow
Answer
detection. The floating point representation has three fields :
1. The sign bit : The sign bit determines whether the number is negative
Answer
or positive. 0 denotes a positive number and 1 denotes a negative
Overflow : number.
1. Overflow is a condition when two numbers with n digits are added and 2. The exponent : The exponent field needs to represent both positive
the sum is a number occupying n + 1 digit. and negative exponents. To do this, a bias is added to the actual
2. Overflow is a problem in digital computer because the number of bits exponent in order to get the stored exponent. For IEEE single precision
cannot be accommodated by an n-bit word. the exponent field is of 8 bits and has a bias value of 127. For double
3. There are following three types of overflow : precision, the exponent field is of 11 bits, and has a bias of 1023.
i. Positive overflow : Positive o verflow refers to integer 3. The mantissa : The mantissa, also known as the significand,
representations and refers to a number that is larger than that can represents the precision bits of the number. It is composed of an implicit
be represented in a given number of bits. leading bit and the fraction bits.
Computer Organization & Architecture 2–17 B (CS/IT-Sem-3) 2–18 B (CS/IT-Sem-3) Arithmetic and Logic Unit
The general structure of floating point number is Table : 2.18.1. Truth table of EXOR Gate.
Answer Answer
AS = BS AS BS AS BS AS = BS
31 30 23 22 0
S E M
EA A + B + 1 EA A + B
AVF 0 8-bit signed 23-bit mantissa fraction
Sign of number
+ Signifies 0 exponent
=0 =1 AVF E – Signifies 1
E
A<B Fig. 2.22.1. Single precision.
A>B
ii. 32-bit floating point number in single precision is represented
A A 0 =0 as + 1M × 2E.
A
iii. The relationship between E and E in single precision is given
A A+1 as E = E + 127.
As As As 0
iv. The 8-bit assigned for exponent E (Modified exponent) is in
the range 0 < E < 255 for normal values. Thus the actual
exponent is in the range – 127 E 127.
END v. The values 0 and 255 are used to indicates the floating points
(result is in A and As) values of exact 0 and infinite respectively.
b. Double precision :
Fig. 2.21.1. i. The floating number in 64-bit are double precision. Fig. 2.22.2
show the double precision format of IEEE standard form.
PART-5 ii. The double precision format has increased, exponent and
mantissa ranges.
IEEE Standard for Floating Point Numbers. iii. The 11 bit assigned for exponent E has range 0 < E < 2047 for
normal values. Thus the actual exponent E is in the range –
1022 E 1023. The relationship between E and E in double
Questions-Answers pricision is given as E = E + 1023.
iv. The 52 bit is assigned for mantissa, provides a precision
Long Answer Type and Medium Answer Type Questions equivalent to about 16 decimal digits.
v. 64-bit floating point number in double precision is represented
as ± 1.M × 2E.
Que 2.22. Explain IEEE standard for floating point numbers. 64 bits
OR
S E M
How floating point numbers are represented in computer, also give
IEEE 754 standard 32-bit floating point number format. 11-bit 52-bit mantissa fraction
Sign
AKTU 2017-18, Marks 3.5 Fig. 2.22.2. Double precision.
Computer Organization & Architecture 2–23 B (CS/IT-Sem-3) 2–24 B (CS/IT-Sem-3) Arithmetic and Logic Unit
Answer
0 10001001 0110110100001.........0
Step 1 : Convert the decimal number in binary format.
For integer, Double precision :
For a given number,
2 1460 0 1.0110110100001 × 210
S = 0, E = 10, M = 0110110100001
2 730 0 Bias (or) modified exponent for double precision
2 365 1 E = E + 1023
= 10 + 1023
2 182 0
(1460)10 = (10110110100) 2 = (1033)10 = (10000001001)2
2 91 1
S E M
2 45 1 1 bit 11 52 bits
bits
2 22 0
0 10000001001 0110110100001.....0
2 11 1
2 5 1
2 2 0
VERY IMPORTANT QUESTIONS
1
Following questions are very important. These questions
For fraction,
may be asked in your SESSIONALS as well as
0.125 × 2 = 0.250 0
UNIVERSITY EXAMINATION.
0.250 × 2 = 0.500 0
0.500 × 2 = 1.000 1
(0.125)10 = (0.001)2
(1460.125)10 = (10110110100.001)2 Q. 1. Describe sequential Arithmetic and Logic Unit (ALU) using
proper diagram.
Step 2 : Normalize the number. Ans. Refer Q. 2.1.
10110110100.001 = 1.0110110100001 × 210
Single precision : Q. 2. Explain Booth’s multiplication algorithm in detail.
For a given floating point number, Ans. Refer Q. 2.3.
1.0110110100001 × 210
S= 0 Q. 3. Draw the data path of 2’s compliment multiplier. Give the
E = 10 Robertson multiplication algorithm for 2’s compliment
M = 0110110100001 fractions. Also illustrate the algorithm for 2’s compliment
Bais (or) modified exponent for single precision fraction by a suitable example.
E = 127 + E Ans. Refer Q. 2.5.
= 127 + 10 = 13710
= 100010012 Q. 4. Show step by step the multiplication process using Booth’s
Number is single precision format algorithm when (+ 15) and (– 13) numbers are multiplied.
Assume 5-bit registers that hold signed numbers.
Ans. Refer Q. 2.6.
Computer Organization & Architecture 2–25 B (CS/IT-Sem-3) Computer Organization & Architecture 3–1 B (CS/IT-Sem-3)
3
process of multiplication of two binary numbers 11111
(multiplicand) 10101 (multiplier). The signs are not included.
Ans. Refer Q. 2.7.
Q. 8. Draw the data path of sequential n-bit binary divider. Give CONTENTS
the non-restoring division algorithm for unsigned integers.
Also illustrate algorithm for unsigned integer with a Part-1 : Control Unit : Instruction ......................... 3–2B to 3–4B
suitable example. Types, Formats
Ans. Refer Q. 2.13.
Part-2 : Instruction Cycle ......................................... 3–4B to 3–9B
Q. 9. Perform the division process of 00001111 by 0011 (use a and Sub Cycle
dividend of 8 bits). (Fetch and Execute etc.)
Ans. Refer Q. 2.14.
Part-3 : Micro-operations, Execution .................. 3–9B to 3–10B
Q. 10. Add – 35 and – 31 in binary using 8-bit registers, in signed 1’s of Complete Instruction
complement and signed 2’s complement.
Part-4 : Program Control, Reduced .................. 3–16B to 3–18B
Ans. Refer Q. 2.19. Instruction Set Computer
Q. 11. Draw the block diagram of control unit of basic computer. Part-5 : Pipelining .................................................. 3–18B to 3–22B
Explain in detail with control timing diagrams.
Ans. Refer Q. 2.20. Part-6 : Hardwired and Micro- ............................ 3–23B to 3–30B
programmed Control :
Q. 12. Draw a flowchart for adding and subtracting two fixed point Micro-programme
binary numbers where negative numbers are signed 1’s Sequencing
complement presentation.
Ans. Refer Q. 2.21. Part-7 : Concept of Horizontal and .................... 3–30B to 3–35B
Vertical Micro-programming
Q. 13. How floating point numbers are represented in computer,
also give IEEE 754 standard 32-bit floating point number
format.
Ans. Refer Q. 2.22.
3–2 B (CS/IT-Sem-3) Control Unit Computer Organization & Architecture 3–3 B (CS/IT-Sem-3)
This instruction will multiply two operand A and B and result is stored
PART-1 in A.
Instruction Types, Formats, Instruction Cycles and Sub Cycles Que 3.2. Describe the types of instructions on the basis of address
(Fetch, Execute etc), Micro-Operation. fields used in the instruction with example.
Answer
Questions-Answers
Four types of instructions are available on the basis of referenced address
fields :
Long Answer Type and Medium Answer Type Questions
Now, Let us evaluate the following arithmetic expression, using all
instruction types.
X = (A + B) * (C + D)
Que 3.1. What is an instruction in the context of computer
1. Three address instruction : Computers with three address
organization ? Explain the purpose of the various elements of an instruction formats can use each address fields to specify either a
instruction with the help of a sample instruction format. processor register or a memory operand. The program in assembly
language to evaluate arithmetic expression is shown as :
AKTU 2014-15, Marks 10
ADD R1, A, B R1 M [ A ] + M [ B ]
ADD R2, C, D R2 M [ C ] + M [ D ]
Answer
MUL X, R1, R2 M [ X ] R1 R2
Instruction :
2. Two address instruction : In this format each address field can
1. Instruction is a command to the processor to perform a given task on specify either a processor register or a memory word. The assembly
specified data. language program to evaluate arithmetic expression is as follows :
2. An instruction is a designed binary pattern which is based on the MOV R1, A R1 M [A]
architecture of CPU to perform a specific function. The entire group of ADD R1, B R1 R1 + M [B]
instructions is called the instruction set. MOV R2, C R2 M [C]
Instruction format : ADD R2, D R2 R2 + M [D]
Opcode Operand MUL R1, R2 R1 R1 R2
Fig. 3.1.1. MOV X, R1 M [X] R1
3. One address instruction : One address instruction uses an implied
Instruction has two parts opcode and operand,
accumulator (AC) register for all data manipulation. The program is as
1. Task to be performed, called the operation code (Opcode), and the data
follows :
to be operated upon, called the operand. LOAD A AC M [A]
2. The operands include the input data of the operation and the results ADD B AC AC + M [B]
that are produced. STORE T M [T] AC
3. A computer must have instructions capable of performing four types LOAD C AC M [C]
of operations : ADD D AC AC + M [D]
a. Data transfers between the memory and the CPU registers. MUL T AC AC M [T]
b. Arithmetic and logic operations on data.
STORE X M [X] AC
c. Program sequencing and control.
All operations are done between the AC register and a memory operand.
d. I/O transfers. 4. Zero address instruction : A stack organized computer does not use
4. The purpose of an instruction is to specify both an operation to be an address field for the instructions ADD and MUL. The PUSH and
carried out by a CPU or also process the set of operands or data to be POP instructions need an address field to specify the operand that
used in the operation. communicates with the stack. The program is as follows :
Example : PUSH A TOS A
MUL A, B PUSH B TOS B
ADD TOS (A + B)
Opcode Operand PUSH C TOS C
3–4 B (CS/IT-Sem-3) Control Unit Computer Organization & Architecture 3–5 B (CS/IT-Sem-3)
PUSH D TOS D OR
ADD TOS (C + D) Explain the different cycles of an instruction execution.
MUL TOS (C + D) (A + B) OR
POP X M [X] TOS Explain all the phases of instruction cycle.
where TOS is TOP of the stack. AKTU 2018-19, Marks 3.5
Que 3.3. Evaluate the arithmetic statement X = (A + B)*(C + D)
Answer
using a general register computer with three address, two address
and one address instruction format a program to evaluate the Instruction cycle :
1. Instruction cycle is a complete process of instruction execution.
expression. AKTU 2018-19, Marks 07 2. It is a basic operational process of a computer.
3. It is the process by which a computer retrieves a program instruction
Answer from its memory, determines what actions the instruction dictates,
Three address instruction : and carries out those actions.
ADD R1, A, B R1 M[A] + M[B] The instruction cycle is divided into three sub cycles :
ADD R2, C, D R2 M[C] + M[D] Fetch cycle Decode cycle Execute cycle
MUL X, R1, R2 M[X] R1 * R2
Fetch Decode Execute
Two address instruction : START HALT
instruction instruction instruction
MOV R1, A R1 M[A]
ADD R1, B R1 R1 + M[B] Fig. 3.4.1.
MOV R2, C R2 M[C] 1. Fetch cycle : To fetch an opcode from a memory location following
ADD R2, D R2 R2 + M[D] steps are performed :
MUL R1, R2 R1 R1 * R2 i. The program counter places the address of the memory location
MOV X, R1 M[X] R1 in which the opcode is stored, on the address bus.
One address instruction : ii. The CPU sends the required memory control signals so as to
LOAD A AC M[A] enable the memory to send the opcode.
ADD B AC A[C] + M[B] iii. The opcode stored in the memory location is placed on the data
STORE T M[T] AC bus and transferred to the CPU.
LOAD C AC M[C] 2. Decode cycle :
ADD D AC AC + M[D] i. The opcode which is fetched from the memory is placed first of all
MUL T AC AC * M[T] in the Data Register (DR) (data/address buffer in case of Intel
STORE X M[X] AC 8085). Thereafter it goes to the Instruction Register (IR).
ii. From the instruction register it goes to the decoder circuitry, which
PART-2 is within the CPU.
iii. The decoder circuitry decodes the opcode.
Instruction Cycle and Sub Cycle (Fetch and Execute etc.). iv. After the opcode is decoded the CPU comes to know what operation
is to be performed, and then execution begins.
3. Execute cycle :
Questions-Answers i. In this cycle, function of the instruction is performed.
ii. If the instruction involves arithmetic or logic, ALU is utilized.
Long Answer Type and Medium Answer Type Questions
Que 3.5. Write the steps in fetching a word from memory.
Differentiate between a branch instruction and call subroutine
Que 3.4. Define instruction cycle and divide instruction cycle
instruction. AKTU 2014-15, Marks 10
into sub cycles with the help of diagram, explain the sequence in
which sub cycles are executed.
3–6 B (CS/IT-Sem-3) Control Unit Computer Organization & Architecture 3–7 B (CS/IT-Sem-3)
AC AC
Questions-Answers
(b) Direct address (c) Indirect address
Fig. 3.7.1. Long Answer Type and Medium Answer Type Questions
Instruction will be decoded and executed by this control unit :
Instruction Register (IR)
15 14 13 12 11 – 0 Que 3.8. Describe micro-operation and enlist its types.
Other inputs
3 × 8 Decoder Answer
7 6 5 4 3 21 0 D0 Control
D7 Control outputs 1. A micro-operation is a simple operation that can be performed during
1
Logic one clock period.
T15
Gates 2. The result of this operation may replace the previous binary information
T0
of register or the result may be transferred to another register.
15 14 ............ 2 1 0 3. Examples of micro-operations are shift, move, count, add and load etc.
4 × 16 4. The micro-operations most often encountered in digital computers are
Decoder classified into four categories :
i. Register transfer micro-operations : It transfer binary
4-bit Increment (INR) information from one register to another.
Sequence Counter Clear (CLR) ii. Arithmetic micro-operations : It perform arithmetic operation
(SC) Clock on numeric data stored in registers.
iii. Logic micro-operations : It perform bit manipulation operations
Fig. 3.7.2. Block diagram of control unit of a computer.
on non-numeric data stored in registers.
1. Control unit consists of : iv. Shift micro-operations : It perform shift operations on data stored
i. Instruction register in registers.
ii. Number of control logic gates
iii. Two decoders Que 3.9. Write a short note on register transfer micro-operation.
iv. 4-bit sequence counter
2. An instruction read from memory is placed in the Instruction Register Answer
(IR). 1. Register transfer is defined as information transfer from one register to
3. The instruction register is divided into three parts : the I bit, operation another and is designated in symbolic form by means of a replacement
code, and address part. operator.
3–10 B (CS/IT-Sem-3) Control Unit Computer Organization & Architecture 3–11 B (CS/IT-Sem-3)
3. The use of variable length instructions does not remove the desirability
PART-4 of making all of the instruction lengths integrally related to the word
length.
Program Control, Reduced Instruction Set Computer. 4. It is more efficient.
5. It is more compact with a combination of register memory addressing
modes.
Questions-Answers Disadvantages of using a variable length instruction format :
1. The main disadvantage of variable length instructions is increase in
Long Answer Type and Medium Answer Type Questions the complexity of the processor.
2. It does not remove desirability of instruction length which is integrally
related to word length.
Que 3.15. What is CISC ? Explain its characteristics.
Que 3.17.
3.27. Write a short note on RISC.
AKTU 2015-16, Marks 05
AKTU 2014-15, Marks 05
Answer OR
What is RISC ? Explain its various characteristics.
1. The term “CISC” (Complex Instruction Set Computer or Computing)
refers to computers designed with a full set of computer instructions AKTU 2015-16, Marks 05
that were intended to provide needed capabilities in the most efficient
way. Answer
2. CISC has complex instruction sets variable length encoding of
1. RISC (Reduced Instruction Set Computer) processor instruction has a
instructions and instruction execution takes varying number of clock
fixed length encoding of instruction and each instruction executes in a
cycles.
single clock cycle by hardwired implementation of each instruction.
3. Due to large number of addressing modes for the operations and
2. RISC architecture focus on reducing the number of instructions and
instructions, the CISC computer generally require fewer instructions to
working with simpler instruction set having limited number of
perform the computation.
addressing modes and allowing them to execute more instructions in
4. Programs writing for CISC architectures tend to take less space in
the same amount of time.
memory.
3. Programs written for RISC architectures tend to make more space in
Characteristics of CISC :
memory but RISC processor’s increased clock rate allows it to execute
1. If the frequency of complex operation is high, then the performance of
its program in less time than a CISC processor takes to execute its
the CISC machine is better to implement.
program.
2. CISC tends to have many instruction formats to accommodate more
RISC characteristics :
opcode types and operand addressing method.
1. Simple instructions are used in RISC architecture.
3. CISC has many instruction formats.
2. RISC helps and supports few simple data types and synthesizes complex
4. CISC processor provides direct manipulation of operands residing in
data types.
memory.
3. RISC utilizes simple addressing modes and fixed length instructions
Que 3.16. Discuss the advantages and disadvantages of using a for pipelining.
4. RISC permits any register to use in any context.
variable length instruction format.
Que 3.18. Differentiate between RISC & CISC based
Answer
Advantages of using a variable length instruction format : microprocessor. AKTU 2017-18, Marks 07
1. In variable length instructions format, it is easy to provide a large OR
collection of opcodes with different opcode lengths. Differentiate between complex instruction set computer and reduced
2. Addressing can be more flexible with various combinations of register instruction set computer.
and memory references plus addressing modes. OR
3–18 B (CS/IT-Sem-3) Control Unit Computer Organization & Architecture 3–19 B (CS/IT-Sem-3)
Answer Answer
1. Pipelining is a technique of decomposing a sequential process into
S. No. RISC CISC sub-operations, with each sub-process being executed in a special
1. Multiple register sets, often Single re giste r se t, o fte n dedicated segment that operates concurrently with all other segments.
consisting of more than 256 consisting 6 to 16 registers total. 2. The processor executes a program by fetching and executing
registers. instructions, one after the other.
3. Let Fi and Ei refer to the fetch and execute steps for instruction Ii.
2. Thre e re giste r o pe rands One or two register operands 4. Execution of a program consists of a sequence of fetch and execute
allowed per instruction (for allo we d pe r instructio n (for steps as shows is Fig. 3.19.1.
example, add R1, R2, R3). example, add R1, R2). Instruction Instruction Instruction
3. Parameter passing through Parame te r passing thro ugh I1 I2 I3
efficient o n-chip re gister inefficient off-chip memory.
windows. F1 E1 F2 E2 F3 E3
11. Few addressing modes. Many addressing modes. Fig. 3.19.2. Hardware organization.
9. The computer is controlled by a clock whose period is such that the
fetch and execute steps of any instruction can be completed in one
PART-5 clock cycle.
Pipelining. 10. Operation of the computer proceeds as in Fig. 3.19.3.
Clock cycle instruction 1 2 3 4
I1 F1 E1
Questions-Answers
I2 F2 E2
Long Answer Type and Medium Answer Type Questions I3 F3 E3
Fig. 3.19.3.
Que 3.19. What is pipelining ? How the idea of pipelining used in 11. In the first clock cycle, the fetch unit fetches an instruction I1 (step F1)
a computer ? and stores it in buffer Bi at the end of the clock cycle.
3–20 B (CS/IT-Sem-3) Control Unit Computer Organization & Architecture 3–21 B (CS/IT-Sem-3)
12. In the second clock cycle, the instruction fetch unit proceeds with the M1
fetch operation for instruction I2 (Step F2). Meanwhile, the execution
unit performs the operation specified by the instruction I1, which is
Processor 1 Task 1
available to it in buffer Bi (Step E1). By the end of the second clock
cycle, the execution of instruction I1 is completed and instruction I2 is
M2
available.
13. Instruction I2 is stored in Bi by replacing I1, which is no longer needed. Task 2
Step E2 is performed by the execution unit during the third clock cycle, Processor 2
while instruction I3 is being fetched by the fetch unit. In this manner,
M3
both fetch and execute units are kept busy all the time.
Task 3
Que 3.20. How pipelining is classified ? Processor 3
OR
Write short notes on instruction pipeline.
Fig. 3.20.2. Processor pipelining.
AKTU 2018-19, Marks 3.5 3. Instruction pipelining :
a. The execution of a stream of instructions can be pipelined by
Answer overlapping the execution of the current instruction with the fetch,
Classification of pipeline : decode, and operand fetch of subsequent instructions as shown in
1. Arithmetic pipelining : Fig. 3.20.3.
a. The arithmetic logic units of a computer can be segmentized for b. This technique is also known as instruction look ahead.
pipeline operations in various data format as shown in Fig. 3.20.1. c. Almost all high-performance computers are now equipped with
b. The four-stage pipeline used in Star-100, the eight-stage pipeline instruction-execution pipelines.
Instructions
used in the TI-ASC, the up to 14 stages pipeline used in the
1
Cray-1 are the example of arithmetic pipeline. Program
Memory
2 data
S1 3
S2 Functional
units
6. A counter may be used to keep the track of the control steps. 2. The sequence of control signals to be generated by the controller can be
7. The required control signals are determined by the following stored in a special Read Only Memory (ROM) also called Control Memory
information : (CM).
a. Contents of the control step counter. 3. Memory control word is written for each micro-operation, and these
b. Contents of the instruction register. control words are stored in a serial ascending memory location.
c. Contents of the condition code flags. 4. The control word is accessed serially (serial access memory) from the
d. External input signals such as MFC and interrupt request. control memory.
Methods to design hardwired control : There are four simplified and 5. Control words are stored in the ROM permanently.
systematic methods for the design of hardwired controllers.
6. The output of the control memory provides the required control signals.
1. State table method or one-hot method.
2. Delay element method.
Control
3. Sequence-counter method. Next To initiate
External Memory Control
4. PLA method. address micro-
inputs Register memory
PLA method : generator operation
(CMR)
1. PLA (Programmable Logic Array) is an important device of digital system.
2. We can implement a large combinational logic circuit or sequential
Next address information
logic circuit in a PLA.
External Control signal Fig. 3.24.1. Block diagram of micro-programmed control unit.
conditional to initiate
input micro-operation 7. If the control memory is sequentially accessed by incrementing control
PLA
memory location, then the sequence of control signals stored in
Sequence
register successive word of ROM can be generated.
8. The storage of control word in a ROM is often referred to as firmware.
Answer Answer
1. Micro-programmed control is a method of control unit design in which Hardwired control : Refer Q. 3.23, Page 3–23B, Unit-3.
the control signal selection and sequencing information is stored in a Micro-programmed control : Refer Q. 3.24, Page 3–24B, Unit-3.
ROM or RAM called a Control Memory (CM).
3–26 B (CS/IT-Sem-3) Control Unit Computer Organization & Architecture 3–27 B (CS/IT-Sem-3)
c. Branches to a given address if a specified status bit is equal to 1. 3. For instance, micro-operation I is executed if the Ith bit is one; it is not
d. Transfer control to a new address as specified by an external executed otherwise.
source (Instruction Register). 4. A micro-code decoder will no longer be required in this case because no
e. Has a facility for subroutine calls and returns. coding is involved.
5. Depending on the current micro-instruction condition flags, and the 5. This scheme will require a total of N bits per micro-instruction (to
contents of the instruction register, a control memory address must be accommodate N different micro-operations).
generated for the next micro-instruction. 6. The advantage with horizontal micro-programming is that several
micro-operations can be executed during each micro-instruction step.
7. In fact, this scheme permits one to execute all the micro-operations
PART-7 provided in the computer in a single micro-instruction.
Concept of Horizontal and Vertical Micro-programming.
Que 3.30. Briefly define the following terms :
i. Micro-operation
Questions-Answers
ii. Micro-instruction
iii. Micro-program
Long Answer Type and Medium Answer Type Questions
iv. Micro-code
v. Control memory AKTU 2015-16, Marks 10
Que 3.29. Explain the concept of vertical and horizontal
multi-programming. Answer
i. Micro-operation :
Answer
1. Micro-operation is a set of operations that the processor unit has
Vertical micro-programming : to perform to execute the major phases of instruction cycle.
1. In the case of vertical micro-programming, e ach line of the 2. The instruction cycle has three major phases of fetch, decode and
micro-program represents a micro-instruction which specifies one or execute.
more micro-operations.
3. The primary function of a CPU is to execute sequence of
2. One micro-instruction gets executed during each step of the control instructions which is in accordance with the instruction cycle.
sequence. One can use a straight binary code to specify each
ii. Micro-instructions :
micro-operation.
1. Micro-instructions are the individual control words in the micro
3. Rather than provide for only one micro-operation per step and use a
routine.
single decoder for the entire micro-instruction field, it is in fact possible
to partition this field into a number of mutually exclusive subfields 2. This contains the control signals for sequencing information.
which can be independently decoded in separate decoder. iii. Micro-program : Micro-program is a micro-code in a particular processor
4. This approach yields a more cost-effective design. If the system design implementation. Writing micro-code is often called micro-programming.
needs in all a total of N different micro-operations one will have to iv. Micro-code :
provide for log2 N bit to specify a micro-operation.
1. Micro-code is a layer of hardware-level instructions and/or data
5. If only one micro-operation per micro-instruction is allowed, then one structures involved in the implementation of higher level machine
would require log2 N bit per micro-instruction. code instructions in many computers and other processors.
Horizontal micro-programming : 2. It helps to separate the machine instructions from the underlying
1. In horizontal micro-programming, one associates each bit of the electronics so that instructions can be designed and altered more
micro-instruction with a specific micro-operation (bit I to represent freely.
micro-operation I). v. Control memory :
2. A specific micro-operation is executed during a micro-instruction step 1. Control memory is a Random Access Memory (RAM) consisting of
only if the corresponding bit is one. addressable storage registers.
3–32 B (CS/IT-Sem-3) Control Unit Computer Organization & Architecture 3–33 B (CS/IT-Sem-3)
No
Following questions are very important. These questions
Yes No may be asked in your SESSIONALS as well as
MRI DEC or HEX UNIVERSITY EXAMINATION.
Get operation Convert
code and Valid operand to
set bits 2-4 non-MRI No binary in Q. 1. What is an ins truction in the context of computer
instruction location organization ? Explain the purpose of the various elements
given of an instruction with the help of a sample instruction
Search address-
by LC format.
symbol table for Yes
binary equivalent Ans. Refer Q. 3.1.
of symbolic address
and set bits 5-16 Store binary Error in Q. 2. Evaluate the arithmetic statement X = (A + B)*(C + D) using
equivalent of line a general register computer with three address, two address
Yes No instruction of code and one address instruction format a program to evaluate
I in location the expression.
given by LC Refer Q. 3.3.
Set Set Ans.
first first
bit to 1 bit to 0 Q. 3. Explain all the phases of instruction cycle.
Ans. Refer Q. 3.4.
Assemble all parts of
binary instruction and store Increment LC Q. 4. Write the s teps in fetching a word from memory.
in location given by LC Differentiate between a branch instruction and call
subroutine instruction.
Fig. 3.34.1. Ans. Refer Q. 3.5.
3–36 B (CS/IT-Sem-3) Control Unit Computer Organization & Architecture 3–37 B (CS/IT-Sem-3)
Q. 5. In an instruction format, there are 16 bits in an instruction Q. 15. Briefly define the following terms :
word. Bit 0 to 11 convey the address of the memory location i.Micro-operation
for memory related ins tructions . For non memory ii.Micro-instruction
instructions these bits convey various register or I/O iii.Micro-program
operations. Bits 12 to 14 show the various basic memory iv. Micro-code
operations such as ADD, AND, LDA etc. Bit 15 shows if the v. Control memory
memory is accessed directly or indirectly. For such an Ans. Refer Q. 3.30.
instruction format draw block diagram of the control unit Q. 16. Write an assembly level program for the following pseudo
of a computer and briefly explain how an instruction will code :
be decoded and executed, by this control unit. SUM = 0
Ans. Refer Q. 3.7. SUM = SUM + A + B
DIF = DIF-C
Q. 6. List and explain different types of shift micro-operation. SUM = SUM + DIF
Ans. Refer Q. 3.12. Ans. Refer Q. 3.31.
Q. 7. What are the different categories of micro-operations that Q. 17. Explain 4-bit incrementer with a necessary diagram.
may be carried out by CPU ? Explain each category of Ans. Refer Q. 3.32.
micro-operations giving one example for each.
Ans. Refer Q. 3.13. Q. 18. Write a program loop using a pointer and a counter to clear
the contents of hex locations 500 to 5FF with 0.
Q. 8. What is CISC ? Explain its characteristics. Ans. Refer Q. 3.33.
Ans. Refer Q. 2.15.
Q. 19. Demonstrate the process of second pass of assembler using
Q. 9. What is RISC ? Explain its various characteristics. a suitable diagram.
Ans. Refer Q. 3.17. Ans. Refer Q. 3.34.
PART-1
4 Memory
Memory : Basic Concept and Hierarchy.
Questions-Answers
Cache
Main memory
Secondary memory
OR
Answer Write s hort note on organization of 2D and 2.5D memory
Data bus DQ1 : DQ 8 AKTU 2014-15, Marks 05
organization.
Timing and Internal 8
•••
refreshing control Answer
control logic signals Data buffer
2D organization :
1. The cells are organized in the form of a two-dimensional array with
rows and columns.
2. Each row refers to word line. For 4-bit per word memory, 4 cells are
interconnected to a word line. Each column in the array refers to a bit
Row 8192 × 1024 × 8 line.
address storage cell array
•••
Bit lines (complement to each other) Memory cells
decoder
A0 D
M A1 E W0 Word line
A C
R A2 O
••• A3 D
E
R
W1 Word line
Column
address decoder
Row Column
address address
buffer W 15
13 10 buffer
R/W Sense/ Sense/ Sense/ Sense/
13 CS write ckt. write ckt. write ckt. write ckt.
RAS CAS WEOE
b3 b2 b1 b0 Data lines
Control lines
Address bus A0 : A 12
Fig. 4.5.1. 2D organization of a memory chip of size 16 × 4.
Fig. 4.4.1. Structure of a commercial 8M × 8-bit DRAM chip.
3. The Memory Address Register (MAR) holds the address of the location
where read/write operation is executed. In Fig. 4.5.1, MAR has 4-bit
PART-3 lines.
2D & 2½ D Memory Organization. 4. The content of MAR is decoded by an address decoder on the chip to
activate each word line.
Questions-Answers 5. The cells in each column are connected to a sense/write circuit by two
bit lines. Two bit lines are complement to each other.
Long Answer Type and Medium Answer Type Questions 6. The sense/write circuits are activated by the Chip Select (CS) lines.
The sense/write circuits are connected to the data lines of the chip.
7. During a read operation, these circuits sense or read the information
1 stored in the cells selected by a word line and transmit this information
Que 4.5. Explain 2D, 2 2 D memory organization.
to the data lines.
Computer Organization & Architecture 4–7 B (CS/IT-Sem-3) 4–8 B (CS/IT-Sem-3) Memory
Answer
MAR
ROM :
x Word b bits b bits b bits
line X 1. The Read Only Memory is a type of semiconductor memory that is
decoder Segment 1 Segment 2 Segment 5 designed to hold data that is either permanent or will not change
frequently. It is also known as non-volatile memory.
6. The × under the address bus lines designate those lines that must be CS1
connected to the address inputs in each chip. CS2
7. The RAM chips have 128 bytes and need seven address lines. CS3
8. The ROM chip has 512 bytes and need 9 address lines. CS4
I0 O0
9. It is now necessary to distinguish between four RAM chips by assigning I1 O1
to each a different address. I2 O2
I3 O3
Que 4.8. A computer uses RAM chips of 1024*1 capacity. ROM
I4 1024 × 8 O4
i. How many chips are needed and how should their address lines I5 O5
be connected to provide a memory capacity of 1024*8 ? I6 O6
ii. How many chips are needed to provide a memory capacity of I7 O7
16 KB ? Explain in words how the chips are to be connected to I8
the address bus. AKTU 2015-16, Marks 10 I9
V(+)
V(–)
Answer
i. Available size of RAM chips = 1024 × 1 Fig. 4.9.1.
Required memory capacity = 1024 bytes Que 4.10. A computer uses a memory unit with 256 K words of
= 1024 × 8
32 bits each. A binary instruction code is stored in one word of
1024 8 memory. The instruction has four parts : an indirect bit, an operation
Number of chips required = = 8 chips
1024 1 code, a register code part to specific one of 64 register and an address
So, 8 chips are needed with address line connected in parallel. part.
ii. To provide a memory capacity of 16K bytes, chips required are i. How many bits are there in the operation code, the register
16 × 8 = 128 chips code part and the address part ?
ii. Draw the instruction word format and indicate the number of
Number of address line for 16 K = 14 (16 K = 214)
bits in each part.
So, 14 lines to specify chip address. iii. How many bits are there in the data and address inputs of the
Que 4.9. A ROM chip of 1024*8 has four select inputs and operates memory ? AKTU 2018-19, Marks 07
from a 5 volt power supply. How many pins are needed for the IC
package ? Draw a block diagram and label all input and output Answer
AKTU 2015-16, Marks 10 a. Address : 28 * 210 = 218 = 18 bits
terminals in the ROM.
Register : 64 registers = 26 = 6 bits
OP code : (Total bit – Indirect bit – Address bit – Register bit)
Answer
= (32 – 1 – 18 – 6) bits = 7 bits
Size of ROM Chip = 1024 × 8
b. I OP Register Address
Number of input = 10 pin [210 = 1024]
31 30 23 170
Number of output = 8 pin
c. Number of bit in address inputs : 18
Number of chip select = 4 pin Number of bit in data inputs : 32
Power = 2 pin
Total 24 pins are required. PART-5
Cache Memories : Concept and Design Issues and Performance.
Computer Organization & Architecture 4–13 B (CS/IT-Sem-3) 4–14 B (CS/IT-Sem-3) Memory
d. As the block size increases from smaller to larger, the hit ratio will
Questions-Answers increase first and on increasing the block size further the hit ratio
began to decrease.
Long Answer Type and Medium Answer Type Questions
iii. Associativity : It is a basic tradeoff between parallel searching versus
constraints on which addresses can be stored.
iv. Write strategy : Its main concern is related to when do we write
Que 4.11. Write short note on cache memory. cache contents to main memory.
No. of set = 8
Main memory Cache memory Total no. of lines = No. of sets × No. of lines/set
Address Data
Tag Data = 8 × 210 = 213
00 000 5670 Index Tag Data
00
Cache size = No. of sets × No. of lines /set × size of line
5670 000 01 1256
= 8 × 213 × 27 bits = 223 bits
00 666 7523
Cache size = 8 MBytes
01 000 1256
00 7523 666 01 5321 Tag Set BO
03 2771 02 6520 8
01 666 5321
51 1560 677 41 2560 35
67 125 7432 Block offset = log2 (line size) = log2 (27) = 7 bits
77 5423 777 66 4423 No. of set = 8
77 777 5423 Physical address (PA) = 35
Tag size = PA – (Block offset + No. of set)
Fig. 4.14.4.
= 35 – (7 + 8)
Tag size = 20 bit
Que 4.15. What do you mean by cache memory ? How does it
Que 4.16. Consider a cache uses a direct mapping scheme. The
affect the performance of the computer system ? An eight-way set
associative cache is used in computer in which the real memory size of main memory is 4 K bytes and word size of cache is 2 bytes.
size 232 bytes. The line size is 16 bytes, and there are 210 lines per set. The size of cache memory is 128 bytes. Find the following :
Calculate the cache size and tag length. i. The size of main memory address (assume each byte of main
memory has an address)
Answer ii. Address of cache block
iii. How many memory location address will be translated to cache
Cache memory : Refer Q. 4.11, Page 4–13B, Unit-4.
address/block/location ?
Cache affect the performance as follows : iv. How can it be determined if the content of specified main
1. The CPU to work at its maximum efficiency, the data transfer from the memory address in cache ? AKTU 2014-15, Marks 10
other hardware must be as fast as its speed. The purpose of a cache is to
ensure this smooth and fast transition of data transfer from the hardware
Answer
to the CPU.
Given, Size of main memory = 4 K bytes
2. As CPU speed increased to the point where the RAM is no longer able to
catch up, the transferring of information again become a serious problem. Size of cache memory = 128 bytes
To solve this issue, a cache, which was effectively a small and extremely Word size of cache = 2 bytes
fast memory, was added to the processor to store immediate instruction i. Size of main memory address :
from the RAM. Since the cache runs at the same speed of the CPU, it
can rapidly provide information to the CPU at the shortest time without Since, size of main memory = 4 K bytes = 212 bytes
any delay. So, the size of main memory address = 12
Numerical : ii. Address of cache block :
Given, Main memory size = 232 bytes = 235 bits Since, size of cache memory = 128 bytes
Line size = Block size = 16 bytes = 27 bits Block size = word size of cache = 2 bytes
Lines/set = 210 128
Since, 8-way set associative so, cache have 8 set Number of lines = = 64
2
Computer Organization & Architecture 4–19 B (CS/IT-Sem-3) 4–20 B (CS/IT-Sem-3) Memory
d. The problem with write back is that portions of main memory are
invalid and hence accesses by I/O modules can be allowed only Questions-Answers
through the cache.
Long Answer Type and Medium Answer Type Questions
Que 4.20. Explain replacement algorithm in brief.
Answer Que 4.21. Explain auxiliary memory. What are the commonly
When a main memory block needs to be brought in while all the cache
used auxiliary memory ?
memory blocks are occupied, one of them has to be replaced. This is known
as block replacement. Answer
The replacement algorithms are given as follows : 1. Auxiliary memory is a higher capacity external memory.
1. Optimal replacement : 2. It is non-volatile memory that is not accessible by the CPU, because it
a. In this policy, replace the block which is no longer needed in the is not accessed via the input / output channels.
future. Types of auxiliary memory :
b. If all blocks currently in cache memory will be used again, replace 1. Magnetic disks :
the one which will not be used in the future for the longest time.
a. A disk is a circular plate constructed of metal or of plastic coated
c. The optimal replacement is obviously the best but is not realistic, with a magnetizable material.
simply because when a block will be needed in the future is usually
b. Data are recorded on and later retrieved from the disk via a
not known ahead of time.
conducting coil, named the head.
2. LRU (Least Recently Used) :
c. During a read and write operation, the head is stationary while
a. In this policy, replace the block in cache memory that has not been the plate rotates beneath it.
used for the longest time, i.e., the least recently used (LRU) block.
2. Magnetic tape :
b. The LRU is sub-optimal based on the temporal locality of reference,
i.e., memory items that are recently referenced are more likely to a. A magnetic tape consists of the electrical, mechanical and electronic
components to provide the parts and control mechanism for a
be referenced soon than those which have not been referenced
for a longer time. magnetic tape unit.
3. FIFO (First in First Out) : b. The tape itself is a strip of plastic coated with a magnetic recording
medium.
a. In this policy, replace the block that has been in cache memory for
c. Bits are recorded as magnetic spots on the tape along several
the longest time.
tracks.
b. FIFO is simplest replacement algorithm than LRU.
d. Usually, seven or nine bits are recorded simultaneously to form a
4. Random selection : character together with a parity bit.
a. In this policy, replace a randomly selected block among all blocks e. Read/write heads are mounted one in each track so that data can
currently in cache memory. be recorded and read as sequence of characters.
b. In random selection, select the block and discard it to make space 3. Flash memory :
when necessary.
a. An electronic non-volatile computer storage device that can be
electrically erased and reprogrammed, and works without any
PART-7 moving parts.
Auxiliary Memories : Magnetic Disk, Magnetic Tape and Optical b. Examples of this are flash drives, memory cards and solid state
Disks, Virtual Memory : Concept Implementation. drives.
4. Optical disk :
a. A storage medium from which data is read and written by lasers.
Computer Organization & Architecture 4–23 B (CS/IT-Sem-3) 4–24 B (CS/IT-Sem-3) Memory
b. Optical disks can store much more data up to 6 gigabytes more 2. Virtual address space is increased using active memory in RAM and
than most portable magnetic media, such as floppies. inactive memory in Hard Disk Drives (HDDs) to form contiguous
c. There are three basic types of optical disks: CD/DVD/BD-ROM addresses that hold both the application and its data.
(read-only), WORM (write-once read-many) & EO (erasable optical 3. A system using virtual memory can load larger programs or multiple
disks). programs running at the same time, allowing each one to operate as if
it has infinite memory and without having to purchase more RAM.
Que 4.22. A moving arm disc storage device has the following 4. Virtual memory is a facility that allows program to address memory
specifications : from local point of view, without regard to the amount of main memory.
Number of Tracks per recording surface = 200 5. A virtual memory system provides a mechanism for translating
Disc rotation speed = 2400 revolution/minute program generated addresses into correct main memory locations.
Track-storage capacity = 62500 bits
6. This is done dynamically, while programs are being executed in the
Estimate the average latency and data transfer rate of this device.
CPU.
AKTU 2017-18, Marks 07
Que 4.24. Explain the following memory schemes discussing why
Answer needed the :
Disk rotation speed = 2400 rpm i. Interleaved memory
Mask register
key
Match
Word organized array Select
ABR DBR ABR DBR ABR DBR Select
of CAM cells circuit
Module Module Module
0 i 2k – 1 Output register
The major characteristics are : b. Level 2 (L2) cache : It is built on current processors on processor
1. This memory is accessed simultaneously and in parallel on the basis of chip. It has capacity from 64 kb to 16 MB.
data content rather than by specific address or location. c. Level 3 (L3) cache : This cache is separate from processor chip on
2. This memory is capable of finding an empty unused location to store the motherboard. Its capacity is up to 8 MB.
the word. 3. Main or primary memory : Refer Q. 4.1, Page, Unit-4.
3. This memory is uniquely suited to do parallel searches by data 4. Secondary memory : Refer Q. 4.1, Page, Unit-4.
association. Que 4.28. What do you mean by locality of reference ? Explain
4. Each cell must have storage capability as well as logic circuits for
matching its content with an external argument. with suitable example. AKTU 2017-18, Marks 07
Que 4.27. Discuss the conceptual organization of a multilevel
Answer
memory system used in computers.
Locality of reference is a term for the phenomenon in which the same values
Answer or related storage locations are frequently accessed, depending on the memory
access pattern.
Conceptual organization of a multilevel memory system consist of basically
Example :
four elements i.e., CPU registers, cache memory, main memory and
1. Take the example of an operating system. Ideally, we would like an
secondary memory.
unlimited amount of main memory, instantly accessible.
2. In practice, we have a limited amount of main memory, and because it is
cheaper, a very large amount of secondary memory.
3. However the trade-off is that secondary memory tends to be several
CPU
Main Secondary
orders of magnitude slower than primary memory.
Register Cache Cache Cache
Level 1 Level 2 Level 3 Memory Memory 4. We can approach the ideal by keeping the more often used data in main
File
memory, and everything else in secondary memory.
5. Because of the principle of Locality of Reference, we can be sure that
most memory references will be to locations already stored in main
memory, thereby improving efficiency and providing a flat memory
Fig. 4.27.1. Conceptual organization of multilevel memories model.
in a computer system.
6. This scheme is used in modern operating systems and is called virtual
memory. Virtual memory gives users the appearance of unlimited
1. CPU registers : primary memory by transparently utilizing secondary memory.
a. The high-speed registers in CPU are used as the temporary storage
for instructions and data.
b. They usually form a general purpose register file for storing data
as it is processed. A capacity of 32 data words is typical for a VERY IMPORTANT QUESTIONS
register file and each register can be accessed within a single
clock cycle that is in a few nano seconds. Following questions are very important. These questions
2. Cache memory : may be asked in your SESSIONALS as well as
a. Cache memory is positioned logically between register files and UNIVERSITY EXAMINATION.
the main memory.
b. Its capacity is less than main memory but access time is much
lesser, that is this types of memories are much faster than the Q. 1. Give the structure of commercial 8M × 8 bit DRAM chip.
main memory. Ans. Refer Q. 4.4.
It operates in three levels :
a. Level 1 (L1) cache : It is built directly into the processor chip. It Q. 2. Write short note on organization of 2D and 2.5D memory
has small capacity from 8 kb to 128 kb. organization.
Ans. Refer Q. 4.5.
Computer Organization & Architecture 4–29 B (CS/IT-Sem-3) 4–30 B (CS/IT-Sem-3) Memory
Q. 3. How main memory is useful in computer system ? Explain Q. 9. A two way set associative cache memory uses blocks of 4
the memory address map of RAM and ROM. words. The cache can accommodate a total of 2048 words
Ans. Refer Q. 4.7. from memory. The main memory size is 128 K × 32.
i. Formulate all pertinent information required to construct
Q. 4. A computer uses RAM chips of 1024*1 capacity. the cache memory.
i. How many chips are needed and how should their address ii. What is the size of the cache memory ?
lines be connected to provide a memory capacity of 1024*8 ? Ans. Refer Q. 4.17.
ii. How many chips are needed to provide a memory capacity
of 16 KB ? Explain in words how the chips are to be connected Q. 10. What is the distinction between spatial locality and
to the address bus. temporal locality ?
Ans. Refer Q. 4.8. Ans. Refer Q. 4.18.
Q. 5. A ROM chip of 1024*8 has four select inputs and operates Q. 11. A moving arm disc storage device has the following
from a 5 volt power supply. How many pins are needed for specifications :
the IC package ? Draw a block diagram and label all input Number of Tracks per recording surface = 200
and output terminals in the ROM. Disc rotation speed = 2400 revolution/minute
Ans. Refer Q. 4.9. Track-storage capacity = 62500 bits
Estimate the average latency and data transfer rate of this
Q. 6. A computer uses a memory unit with 256 K words of device.
32 bits each. A binary instruction code is stored in one word Ans. Refer Q. 4.22.
of memory. The instruction has four parts : an indirect bit,
an operation code, a register code part to specific one of 64 Q. 12. Write a short note on virtual memory.
register and an address part. Ans. Refer Q. 4.23.
i. How many bits are there in the operation code, the register
code part and the address part ? Q. 13. Explain the following memory schemes discussing why
ii. Draw the instruction word format and indicate the number needed the :
of bits in each part. i. Interleaved memory
iii. How many bits are there in the data and address inputs of ii. Associative memory
the memory ? Ans. Refer Q. 4.24.
Ans. Refer Q. 4.10.
Q. 14. What is associative memory ? Explain with the help of a
Q. 7. Discuss the various types of address mapping used in cache block diagram. Also mention the situation in which
memory. associative memory can be effective utilized.
Ans. Refer Q. 4.14. Ans. Refer Q. 4.25.
Q. 8. Consider a cache uses a direct mapping scheme. The size Q. 15. What do you mean by CAM ? Explain its major
of main memory is 4 K bytes and word size of cache is 2 characteristics.
bytes. The size of cache memory is 128 bytes. Find the Ans. Refer Q. 4.26.
following :
i. The size of main memory address (assume each byte of Q. 16. What do you mean by locality of reference ? Explain with
main memory has an address) suitable example.
ii. Address of cache block Ans. Refer Q. 4.28.
iii. How many memory location address will be translated to
cache address/block/location ?
iv. How can it be determined if the content of specified main
memory address in cache ?
Ans. Refer Q. 4.16.
Computer Organization & Architecture 5–1 B (CS/IT-Sem-3) 5–2 B (CS/IT-Sem-3) Input/Output
5
PART-1
Input/Output : Peripheral Devices, I/O Interface, I/O Ports.
Questions-Answers
Input / Output Long Answer Type and Medium Answer Type Questions
CONTENTS Answer
1. Peripheral devices are the computer devices that are connected to the
Part-1 : Input/Output : .............................................. 5–2B to 5–4B computer externally such as printer, scanner, keyboard, mouse, tape
Peripheral Devices, device, microphone and external modem. It can be internal such as
I/O Interface, I/O Ports CD-ROM or internal modem.
2. Peripheral devices can be classified according to their functions :
Part-2 : Interrupts : Interrupt ................................. 5–4B to 5–9B
i. Input : Input devices are the type of computer devices that are
Hardware, Types of
used to provide the control signals to the computer. Keyboard and
Interrupts and Exceptions
mouse are the examples of the input devices.
Part-3 : Modes of Data Transfer : ........................ 5–9B to 5–10B ii. Output : Output devices are the devices that are used to display
Programmed I/O the results. Printer, scanner, speaker and the monitor are the
examples of the output devices.
Part-4 : Interrupt Initiated I/O ........................... 5–10B to 5–15B
iii. Storage : A storage device is a device that is used to store the
and Direct Memory Access,
information such as hard-disk drive, flash drive, floppy disk and
I/O Channels and Processors
the tape drive.
Part-5 : Serial Communication : ......................... 5–15B to 5–20B Que 5.2. Describe I/O interface. Why they are needed ?
Synchronous and Asynchronous
Communication, Standard OR
Communication Interfaces Why input-output interface is required ? Describe in detail.
AKTU 2015-16, Marks 15
Answer
I/O interface provides a method of transferring information between internal
storage and external I/O devices.
The major requirements for an I/O module can be given as :
1. Processor communication : This involves the following tasks :
a. Exchange of data between processor and I/O module.
b. Command decoding : The I/O module for a disk drive may accept
the following commands from the processor : READ SECTOR,
WRITE SECTOR, SEEK track, etc.
Computer Organization & Architecture 5–3 B (CS/IT-Sem-3) 5–4 B (CS/IT-Sem-3) Input/Output
c. Status reporting : The device must be able to report its status to iii. Output data command : It causes the interface to respond by
the processor. For example, disk drive busy, ready etc. transferring data from bus into one of its registers.
d. Status reporting may also involve reporting various errors. iv. Input data command : It is the opposite of data output. The interface
e. Address recognition : Each I/O device has a unique address and receives an item of data from peripheral and places it in its buffer register.
the I/O module must recognize this address.
2. Device communication : The I/O module is able to perform device PART-2
communication such as status reporting. Interrupts : Interrupt Hardware, Types of Interrupts and Exceptions.
3. Control and timing : The I/O module is able to co-ordinate the flow of
data between the internal resources (such as processor, memory) and
external devices. Questions-Answers
4. Data buffering :
a. This is necessary as there is a speed mismatch between speed of Long Answer Type and Medium Answer Type Questions
data transfer between processor and memory and external devices.
b. Data coming from the main memory are sent to an I/O module in a
rapid burst. Que 5.4. Write a short note on interrupts.
c. The data is buffered in the I/O module and then sent to the AKTU 2014-15, Marks 05
peripheral device at its rate.
OR
5. Error detection : Define interrupt. When a device interrupt occurs how does the
a. The I/O module is able to detect errors and report them to the processor determine which device has issued the interrupt ?
processor.
Answer
b. These errors may be mechanical errors (such as paper jam in a
printer), or changes in the bit pattern of transmitted data. A common Interrupt : An interrupt is a signal sent by an I/O interface to the CPU
way of detecting such errors is by using parity bits. when it is ready to send information to the memory or receive information
from the memory.
Que 5.3. Explain I/O bus and I/O command. Identifying the source of an interrupt :
Two methods are available to determine the interrupting device :
Answer a. Polled interrupts :
I/O bus : 1. On receiving an interrupt request the micro-processor will execute
1. The I/O bus consists of data lines, address lines and control lines. a routine causing it to poll each of the devices in turn.
2. It acts as a communication link between processor and several peripheral 2. Devices have a status register containing one or more interrupt
devices. request bits.
3. If a device caused the interrupt, its interrupt flag bit will be set.
3. It comprises of magnetic tape, magnetic disk, printer and terminal.
4. The appropriate service routine will then be selected and the device
4. The I/O bus from processor is attached to all peripheral interfaces. serviced.
I/O command : 5. Polling can be very inefficient if there are many devices capable of
When an address is in the address lines, at the same time, the processor causing an interrupt.
provides a function code in control lines which is referred to as I/O command. 6. This method uses only software methods to identify an interrupting
It is of four types : device.
i. Control command : It is issued to activate the peripheral and to inform b. Vectored interrupts :
it what to do. 1. This is the method used in modern computers.
ii. Status command : It is used to test various status conditions in the 2. It is sometimes referred to as hardware identification since
interface and peripheral. additional hardware is required.
Computer Organization & Architecture 5–5 B (CS/IT-Sem-3) 5–6 B (CS/IT-Sem-3) Input/Output
3. Each vector is identified by an interrupt number from 0 to 255 and 6. Restoration and return :
provides the processor with the means of addressing the a. After the interrupt service routine has completed its processing, it
appropriate interrupt handler. restores all the registers it has changed, and the processor restores
4. A vector address is determined by multiplying its vector number all the registers and flags that were saved at the initiation of the
by 4. interrupt routine.
Que 5.5. Explain the sequence that takes place when an interrupt b. If this is done correctly, the processor should have the same status
as before the interrupt was recognized.
occurs. AKTU 2015-16, Marks 10
Que 5.6. How system resolve the priority of interrupt ?
Answer OR
When an interrupt occurs, sequence of following six steps takes place : Explain polling and daisy chaining method.
1. Interrupt recognition : Answer
a. The interrupt recognition is recognized by the processor of an
There are two methods of system to resolve the priority of interrupt :
interrupt request due to activation of an interrupt request line or
an internal mechanism. a. Polling method :
b. In this step, the processor can determine which device or CPU, 1. When interrupt requests arrive from two or more devices
component made the request. simultaneously, the processor has to decide which request should
2. Status saving : be serviced first and which one should be delayed.
a. The goal of this step is to make the interrupt sequence transparent 2. The processor takes the decision with the help of interrupt
to the interrupted process. priorities. It accepts the request having the highest priority.
b. Therefore, the processor saves the flags and registers that may be 3. In this case polling is used to identify the interrupting device,
changed by the interrupt service routine so that they may be priority is automatically assigned by the order in which devices
restored after the service routine is finished. are polled.
3. Interrupt masking : 4. Therefore, no further arrangement is required to accommodate
a. For the first few steps of the sequence, all interrupts are masked simultaneous interrupt requests. However, the priority of any device
out so that no other interrupt may be processed before the is usually determined by the way the device is connected to the
processor status is saved. processor.
b. The mask is then set to accept interrupts of higher priority. b. Chaining method :
4. Interrupt acknowledgment : 1. Most common way to connect the devices is to form a daisy chain,
as shown in Fig. 5.6.1.
a. At some point, the processor must acknowledge the interrupt
being serviced, so that the interrupting device becomes free to 2. The Interrupt Request line (INTR) is common to all the devices
continue its task. and the Interrupt Acknowledge line (INTA) is connected in a daisy
b. One of the ways is to have an external signal line denoted to chain model.
interrupt acknowledge. 3. In daisy chain fashion the signal is allowed to propagate serially
5. Interrupt service routine : through the devices.
a. At this point, the processor initiates the interrupt service routine. 4. When more than one devices issue an interrupt request, the INTR
line is activated and processor responds by setting the INTA line.
b. The address of the routine can be obtained in several ways,
depending on the system architecture.
c. The simplest is found in the polling method, in which one routine
polls each device to find which one interrupted.
Computer Organization & Architecture 5–7 B (CS/IT-Sem-3) 5–8 B (CS/IT-Sem-3) Input/Output
c. Because NMIs generally signal major or even catastrophic system Read word form I/O CPU
events, a good implementation of this signal tries to ensure that I/O module
the interrupt is valid by verifying that it remains active for a
period of time. Write word CPU Memory
into memory
PART-3 No
Done ?
Modes of Data Transfer : Programmed I/O.
Yes
Next instruction
Questions-Answers
Fig. 5.10.1. Programmed I/O.
Long Answer Type and Medium Answer Type Questions 2. With programmed I/O, the I/O module will perform the requested
action and then set the appropriate bits in the I/O status register.
3. The I/O module takes no further action to alert the CPU.
Que 5.10. Write a short note on programmed I/O. 4. It does not interrupt the CPU.
AKTU 2014-15, Marks 05 5. Thus, it is the responsibility of CPU to periodically check the status of
the I/O module until it finds that the operation is complete.
OR
Discuss the programmed I/O method for controlling input-output
operations. PART-4
Answer Interrupt Initiated I/O and Direct Memory
Access, I/O Channels and Processors.
Programmed I/O :
1. When the CPU is executing a program and executes an instruction
relating to I/O, it executes that instruction by issuing a command to the Questions-Answers
appropriate I/O module.
Long Answer Type and Medium Answer Type Questions
5. For example, a PCI controller and a hard drive controller each have
Answer their own set of DMA channels.
1. Interrupt initiated I/O is a mode of data transfer which removes the Block diagram for DMA :
drawback of the programmed I/O mode.
Address bus, READ/ and WRITE/
2. The CPU issues commands to the I/O module then proceeds with its Micro
normal work until interrupted by I/O device on completion of its work. processor RAM
Data bus
3. For input, the device interrupts the CPU when new data has arrived
and is ready to be retrieved by the system processor.
4. The actual actions to perform depend on whether the device uses I/O BUSREQ BUSACK
ports, memory mapping.
5. For output, the device delivers an interrupt either when it is ready to DMA DMAACK I/O
accept new data or to acknowledge a successful data transfer.
DMAREQ
6. Memory-mapped and DMA-capable devices usually generate interrupts
to tell the system that they are done with the buffer. Fig. 5.12.1.
7. Although interrupt relieves the CPU of having to wait for the devices, Working of DMA controller :
but it is still inefficient in data transfer of large amount because the CPU 1. When the peripheral device sends a DMA request, the DMA controller
has to transfer the data word by word between I/O module and memory. activates the BR line, informing the CPU to relinquish the buses.
Que 5.12. Write short note on DMA. AKTU 2014-15, Marks 05 2. The CPU responds with its BG line, informing the DMA that its buses
are disabled.
OR
Explain the working of DMA controller with the help of suitable Interrupt
Random-access
BG CPU
diagrams. AKTU 2017-18, Marks 07 memory (RAM)
BR
OR
Write a short note on DMA based data transfer. RD WR Address Data RD WR Address Data
AKTU 2018-19, Marks 07 Read control
OR Write control
Give the block diagram of DMA controller. Why are the read and Data bus
write control lines in a DMA controller bidirectional ? Address bus
a. When BG = 0, the RD and WR are input lines allowing the CPU to Advantage of isolated I/O :
communicate with the internal DMA registers. 1. The devices of I/O are treated in a separate domain as compared to
b. When BG = 1, the RD and WR are output lines from the DMA memory.
controller to the random access memory to specify the read or 2. A total of 1MB address space is allowed for memory applications.
write operation for the data.
3. In order to maximize the I/O operations (isolated) separate instructions
5. When the peripheral device receives a DMA acknowledge, it puts a are always provided to perform these operations.
word in the data bus (for write) or receives a word from the data bus (for
read). Disadvantage of isolated I/O :
6. Thus, the DMA controls the read or write operations and supplies the 1. The data transfer only occurs between the I/O port and the registers.
address for the memory. Advantages of memory mapped I/O :
7. The peripheral unit can communicate with memory through the data 1. I/O intensive operation is fast.
bus for direct transfer between the two units while the CPU is 2. The SQLite library needs less RAM.
momentarily disabled.
Disadvantages of memory mapped I/O :
Reason for bidirectional read and write control lines : Read and write
1. If an I/O error on a memory-mapped file cannot be caught by the
control lines in a DMA controller is bidirectional because the microprocessor
application, results in a program crash.
fetch (read) the data from the memory and write data to the memory.
2. Performance is reduced by the use of memory-mapped I/O.
Que 5.13. What is the difference between isolated I/O and memory
mapped I/O ? Explain the advantages and disadvantages of each. Que 5.14. What do you mean by Input-Output (I/O) processor ?
Memory bus
used. Those are IN, OUT, INS, references to memory can be Peripheral devices
OUTS. used. Memory
PD PD PD PD
3. The addresses for isolated I/O Memory mapped I/O devices are unit
devices are called ports. treated as memory locations on
the memory map. Input-Output
4. Efficient I/O operations due to Inefficient I/O operations due to Processor
(IOP) I/O bus
separate bus. single bus fo r data and
addressing.
Fig. 4.14.1. The block diagram of a computer with IOP.
5. Comparatively larger in size. Smaller in size.
3. The memory unit occupies central position and can communicate with
6. Uses complex internal logic. Co mmo n inte rnal lo gic fo r
each processor by means of direct memory access.
memory and I/O devices.
4. The CPU is responsible for processing data. The IOP provides a path
7. Slower operations. Faster operations.
for transfer of data between various peripheral devices and the memory
unit.
Computer Organization & Architecture 5–15 B (CS/IT-Sem-3) 5–16 B (CS/IT-Sem-3) Input/Output
5. The CPU assigns the task of initiating the I/O program. From then on
the IOP operates independent of the CPU and continues to transfer Answer
data from external devices and memory. 1. In serial communication bits are transferred one after the other over a
single communication path.
Que 5.15. Explain I/O channels with its types.
2. Serial communication is a device communication protocol that is standard
on almost every PC.
Answer
3. A given transmission on a communication channel between two
1. A channel is an independent hardware component that co-ordinate all
machines can occur in several different ways.
I/O to a set of controllers. Computer systems that use I/O channel have
special hardware components that handle all I/O operations. Modes of serial communication :
2. Channels use separate, independent and low cost processors for its 1. Simplex connection :
functioning which are called channel processors. a. A simplex connection is a connection in which the data flows in only
3. Channel processors are simple, but contains sufficient memory to handle one direction, from the transmitter to the receiver.
all I/O tasks.
DTE DCTE
4. When I/O transfer is complete or an error is detected, the channel
controller communicates with the CPU using an interrupt, and informs
CPU about the error or the task completion. DTE DCTE
5. Each channel supports one or more controllers or devices. Channel Fig. 5.16.1. Simplex connection.
programs contain list of commands to the channel itself and for various
2. Half-duplex connection :
connected controllers or devices.
a. A half-duplex connection (sometimes called an alternating
Types of I/O Channels :
connection or semi-duplex) is a connection in which the data flows
1. Multiplexer : The Multiplexer channel can be connected to a number in one direction or the other, but not both at the same time.
of slow and medium speed devices. It is capable of operating number of
I/O devices simultaneously. DTE DCTE
2. Selector : This channel can handle only one I/O operation at a time and or
is used to control one high speed device at a time. DTE DCTE
3. Block-Multiplexer : It combines the features of both multiplexer and
Fig. 5.16.2. Half-duplex connection.
selector channels.
b. With this type of connection, each end of the connection transmits
in turn.
PART-5 3. Full-duplex connection :
Serial Communication : Synchronous and Asynchronous a. A full-duplex connection is a connection in which the data flow in
Communication, Standard Communication Interfaces. both directions simultaneously.
b. This can be achieved by means of a four-wire link, with a different
pair of wires dedicated to each direction of transmission.
Questions-Answers
DTE DCTE
Long Answer Type and Medium Answer Type Questions
DTE DCTE
Que 5.16. What do you mean by serial communication ? What are Fig. 5.16.3. Full-duplex connection.
the transmission modes of serial communication ? Que 5.17.
5.47. Explain synchronous communication and
asynchronous communication.
Computer Organization & Architecture 5–17 B (CS/IT-Sem-3) 5–18 B (CS/IT-Sem-3) Input/Output
1
Ans. Refer Q. 5.2.
1.5. What is the relation between bus width and number of bit
transferred ?
Ans. Bus width is directly proportional to the number of bit transferred.
The wider the data bus, then greater will be the number of bits
transferred at one time.
SQ–2 B (CS/IT-Sem-3) 2 Marks Questions Computer Organization & Architecture SQ–3 B (CS/IT-Sem-3)
2
Ans. Memory transfer involves basic operation like fetch (read) or store
(write). The fetch operation transfers a copy of content from
memory location to CPU. The store operation transfers the word
information from CPU to specific memory location.
Arithmetic and
Logic Unit
1.7. Define bus transfer.
Ans. The data transfer between various blocks connected to the common (2 Marks Questions)
bus is called bus transfer. Common bus system is shared by all the
units.
2.1. What is look ahead carry adders ?
1.8. Explain control word. AKTU 2015-16, Marks 02 Ans. A look ahead carry adder is a type of adder which improves the
Ans. Control word is defined as a word whose individual bits represent speed by reducing the amount of time required to determine carry
the various control signals. Therefore each of the control steps in bits.
the control sequence of an instruction defines a unique combination 2.2. What is arithmetic and logic circuit ?
of 0s and 1s.
Ans. Arithmetic circuit : It is a digital circuit which performs only
arithmetic operations such as addition, subtraction etc.
1.9. Compare register stack and memory stack. Logic circuit : It is a digital circuit which perform only logic
Ans. operations such as AND, OR and NOT etc.
S. No. Register stack Memory stack 2.3. Define following terms :
i. RTL ii. Micro-operation
1. A stack can be placed in a The stack is implemented as a
portion of a logical memory standalo ne and also AKTU 2016-17, Marks 02
or can be organized as a implemente d as a rando m
Ans.
co llection o f number o f access memory attached to CPU. i. RTL : Register Transfer Language (RTL) is a convenient tool for
memory words or registers. describing the internal organization of digital computers in concise
2. The stack pointer register The implementation of a stack and precise manner. It can also be used to facilitate the design
(SP) co ntains a binary in the CPU is done by assigning process of digital systems.
number whose value is equal a portion of memory to a stack ii. Micro-operation : The processor unit has to perform a set of
to address of the word that is operation. operations to execute the major phases of instruction cycle these
currently on top of the stack. set of operations called micro-operations.
2.4. What is the main advantage of RTL ?
AKTU 2015-16, Marks 02
Ans. Advantage of RTL are :
i. It uses register’s as a primitive component in the digital system
instead of flip-flops and gates.
ii. It describes the information flow and processing tasks among the
data stored in the registers in a concise and precise manner.
iii. It uses a set of expressions and statements which resemble the
statements used in programming languages.
iv. The presentation of digital functions in register transfer logic is
very user friendly.
2.5. What is the need of having many addressing modes in
machine ?
SQ–4 B (CS/IT-Sem-3) 2 Marks Questions Computer Organization & Architecture SQ–5 B (CS/IT-Sem-3)
3
to following reason :
i. The way of operands are chosen during program execution is
dependent on the addressing mode of the instruction.
ii. The addressing mode specifies a rule for interpreting or modifying
the address field of the instruction before the operand is actually Control Unit
referenced.
2.6. How subtraction operation and other operations can be (2 Marks Questions)
simplified in a digital system ?
Ans. Subtraction operation and other operations can be simplified in a
digital system by using complement method. For each number
system, there are two types of complement :
i. r’s complement ii. (r – 1)’s complement 3.1. Explain one, two and three address instruction.
2.7. How many flip-flops are needed for 4-bit decimal code and AKTU 2016-17, Marks 02
4385 in BCD representations ?
Ans.
Ans. For 4-bit decimal code, there are 4 flip-flops used, each for one bit. i. One address instruction : One address instruction uses an implied
For 4385 in BCD representation, there are 16 flip-flops used. accumulator (AC) register for all data manipulation.
2.8. State the condition for floating-point number to become ii. Two address instruction : In this format each address field can
normalized. specify either a processor register or a memory word.
Ans. A floating-point number is said to be normalized if the most iii. Three address instruction : Three address instruction formats
significant digit of the mantissa is non-zero. can use each address fields to specify either a processor register or
2.9. When exponent overflow and underflow occur ? a memory operand.
Ans. Exponent overflow occurs when a positive exponent exceeds the
maximum possible exponent value. 3.2. What are the various facts related to operation code ?
Exponent underflow occurs when a negative exponent exceeds the Ans. Various facts related to operation code are :
maximum possible exponent value. In such cases, the number is i. The number of bits required for the operation code of an instruction
designed is zero. depends on the total number of operations available in the computer.
ii. The operation code must consist of at least n bits for a given 2n
2.10. Perform the following operation on signed numbers using distinct operations.
2’s compliment method : (56)10 + (– 27)10.
AKTU 2017-18, Marks 02 3.3. Define the necessary factors for instruction sequencing.
Ans. Necessary factors for instruction sequencing are :
Ans. 56 = 111000 (binary form) i. It needs a counter to calculate the address of next instruction after
+ 56 = 0111000 (signed binary form)
execution of current instruction is completed.
– 27 = 011011 (binary form)
ii. It is also necessary to provide a register in the control unit for
100100 (1’s complement)
storing the instruction code.
+1
—————
100101 (2’s complement) 3.4. What operations are included in micro-operations ?
– 27 = 1100101 (signed binary form)
now, (+ 56)10 + (– 27)10 = 0111000 Ans. Micro-operations includes :
i. Transfer a word of data from one CPU register to another or to the
1100101
————— ALU.
1 0011101 ii. Perform the arithmetic or logic operations on the data from the
= (0011101)2 (signed binary number) CPU registers and store the result in a CPU register.
= (29)10 iii. Fetch a word of data from specified memory location and load them
into a CPU register.
SQ–6 B (CS/IT-Sem-3) 2 Marks Questions Computer Organization & Architecture SQ–7 B (CS/IT-Sem-3)
iv. Store a word of data from a CPU register into a specified memory 3.10. What is the problem with simple micro-instruction ?
location. Ans. The micro-program requires several branch micro-instructions.
These instructions perform no useful operation in data path. They
are needed only to determine the address of next micro-instruction.
3.5. Define the following terms : AKTU 2016-17, Marks 02
Thus, they de-tract the operating speed of computer.
i. Effective address
ii. Immediate instruction 3.11. List two important instruction set design issues.
Ans.
i. Effective address : Effective address is the address of the operand AKTU 2015-16, Marks 02
in a computation-type instruction or the target address in a branch- Ans. Two important instruction set design issues are :
type instruction. i. Data types : The various types of data upon which operations are
ii. Immediate instruction : An immediate mode instruction has an performed.
operand field rather than an address field. The operand field contains ii. Registers : Number of CPU registers that can be referenced by
the actual operand to be used in conjunction with the operation instructions and their use.
specified in the instruction.
3.12. Define sequencer. AKTU 2016-17, Marks 02
3.6. What does the processor do when an interrupt is pending ?
Ans. If an interrupt is pending, the processor does the following : Ans. A sequencer generates the addresses used to step through the
micro-program of a control store. It is used as a part of control unit
i. It suspends execution of the current program being executed and
of CPU for address ranges.
saves its context.
ii. It sets the program counter to the starting address of an interrupt 3.13. List the two techniques used for grouping the control
handler routine.
signals. AKTU 2015-16, Marks 02
3.7. Define the goal of CISC architecture. Ans. The two techniques used for grouping the control signal
Ans. The goal of CISC architecture is to provide a single machine are :
instruction for each statement that is written in high-level language. i. Hardwired control unit
ii. Micro-programmed control unit
3.8. Compare horizontal and vertical organization.
Ans. 3.14. List three types of control signals.
1. Long formats. Short formats. Ans. Three types of control signals are :
i. ALU
2. Ability to express a high Limited ability to express parallel ii. Data paths
degree of parallelism. micro-operations. iii. System
3. Little encoding of control Co nside rable encoding o f the
information. control information. 3.15. Draw the block diagram of micro-program sequencer.
4. U se ful when highe r Slower operating speed. AKTU 2015-16, Marks 02
operating speed is desired.
Ans. Ans.
S. No. Horizontal Vertical
External Condition microprogramming microprogramming
IR
inputs codes
1. In horizontal micro- In the case of vertical micro-
programming, one associates programming, each line of the
Micro-instruction sequencer e ach bit of the micro - micro -program represe nts a
(starting and branch address generator) instruction with a specific micro-instruction which specifies
micro-operation (bit I to one or more micro-operations.
represent micro-operation I).
2. A specific micro-operation is One micro -instruction gets
Control Address Register ( PC) executed during a micro- executed during each step of the
instruction step only if the control sequence. One can use a
corresponding bit is one. straight binary code to specify
Control memory each micro-operation.
4
Ans. Auxiliary storage is organized in records or blocks because the seek
time is usually much longer than the transfer time.
Ans. Advantages of erasable optical disk are : 4.15. What do you understand by locality of reference ?
i. Provide high storage capacity about 650 Mbytes of data on 5.25 inch
AKTU 2018-19, Marks 02
disk.
ii. It is portable and can easily be carried from one computer to another. Ans. Locality of reference is a term for the phenomenon in which the
iii. It is highly reliable and has longer life. same values or related storage locations are frequently accessed,
depending on the memory access pattern.
4.12. State the disadvantages of erasable optical disk.
Ans. Disadvantages of erasable optical disk are : 4.16. Write the difference between RAM & ROM.
i. It uses constant angular velocity method, therefore lot of storage AKTU 2017-18, Marks 02
space is wasted in the outer tracks.
ii. Overwriting data on magneto-optic media is slower than for Ans.
magnetic media, since one revolution is required to erase a bit and S. No. RAM ROM
a second is required to write back to that location.
1. A random access memory The read only memory (ROM) is a
4.13. What is memory management unit ? (RAM) device allows data type of semiconductor memory
items to be read or written that is designed to hold data that is
Ans. Memory Management Unit (MMU) is the hardware component in
the computer that handles virtual memory. Any request for data is in almost the same amount either permane nt or will not
sent to the MMU which then determines the location of the of time irrespective of the change frequently. It is also known
information; whether it is in RAM or on a permanent storage drive. physical location of data as non-volatile memory.
The MMU is usually located on our machine’s CPU and holds a inside the memory.
table for matching physical memory addresses to virtual ones. 2. Types of RAM : Types of ROM :
i. Dynamic random i. Programmable read only
4.14. Explain the following terms : access memory memory (PROM)
i. PSW (DRAM)
ii. Delayed load AKTU 2016-17, Marks 02 ii. Static random access ii. Erasable programmable
memory (SRAM) read only memory
Ans. (EPROM)
i. PSW (Program Status Word) :
1. The collection of all status bit conditions in the CPU is sometimes
called a program status word or PSW.
2. The PSW is stored in a separate hardware register and contains
the status information that characterizes the state of the CPU.
3. It includes the status bits from the last ALU operation and it
specifies the interrupts that are allowed to occur and whether the
CPU is operating in a supervisor or user mode.
ii. Delayed load :
1. It is up to the compiler to make sure that the instruction following
the load instruction uses the data fetched from memory.
2. If the compiler cannot find a useful instruction to put after the
load, it inserts a no-op (no-operation) instruction.
3. This is a type of instruction that is fetched from memory but has
no operation, thus wasting a clock cycle.
4. This concept of delaying the use of the data loaded from memory
is referred to as delayed load.
SQ–14 B (CS/IT-Sem-3) 2 Marks Questions Computer Organization & Architecture SQ–15 B (CS/IT-Sem-3)
5
i. The time that the CPU spends testing I/O device status and executing
a number of instructions for I/O data transfer can often be better
spent on other task.
ii. The I/O transfer rate is limited by the speed with which the CPU
Input/Output can test and service a device.
(2 Marks Questions) 5.5. Compare programmed I/O and interrupt driven I/O.
Ans.
S. No. Programmed I/O Interrupt driven I/O
S. No. Memory bus I/O bus 5.7. State the characteristics of I/O channel.
Ans.
1. Memory bus shares entire I/O bus shares only I/O address i. An I/O channel has a special-purpose processor.
address range. range. ii. The I/O instructions are stored in main memory.
iii. The I/O program specifies the devices, the area of memory storage,
2. Memory bus width is greater I/O bus width is smaller than
priority and actions to be taken for certain error conditions.
than I/O bus width. memory bus width.
5.8. Explain the type of I/O channels.
3. Memory bus includes data bus, I/O bus include s data bus, Ans. There are two main types of I/O channels :
address bus and co ntro l address bus and control signals i. Selector channel
signals to access memory. to access I/O. ii. Multiplexer channel
5.4. State the drawbacks of programmed I/O and interrupt 5.9. What are the modes of data transfer ?
driven I/O. AKTU 2016-17, Marks 02
SQ–16 B (CS/IT-Sem-3) 2 Marks Questions Computer Organization & Architecture SQ–17 B (CS/IT-Sem-3)
Ans. Modes of data transfer are : 2. When BG is 1, the CPU has relinquished the buses and the DMA
i. Programmed I/O : Programmed I/O operations are the result of can communicate directly with the memory by specifying an address
I/O instructions written in computer program. in the address bus and activating RD or WR.
ii. Interrupt-driven I/O : This mode avoids the drawbacks of
programmed I/O by using interrupt request. 5.14. What is the use of modem in synchronous communi-
iii. Direct memory access : The interface transfers data onto and
cation ? AKTU 2015-16, Marks 02
out of the memory unit through memory bus.
Ans. A modem converts digital signals into audio tones to be transmitted
5.10. What is an interrupt ? AKTU 2016-17, Marks 02 over telephone lines and also converts audio tones from the line to
digital signals for machine use. The modems used in synchronous
Ans.
1. An interrupt is a signal sent by an I/O interface to the CPU when it transmission have internal clocks that are set to the frequency that
is ready to send information to the memory or receive information bits are being transmitted in the communication line.
from the memory.
2. When a CPU receives an interrupt signal it stops executing current 5.15. Describe cycle stealing in DMA.
normal program. AKTU 2018-19, Marks 02
3. After stopping it saves the state of various registers in stack.
Ans.
4. When this is done CPU executes a subroutine in order to perform
1. In Direct Memory Access (DMA), cycle stealing is a method of
the specific task requested by the interrupt.
allowing I/O controllers to read or write RAM without interfering
5.11. Differentiate between synchronous and asynchronous with the CPU.
2. DMA controllers can operate in cycle stealing mode in which
transmission. AKTU 2016-17, Marks 02 controller take over the bus for each byte of data to be transferred
Ans. and then return control to the CPU.
S. No. Synchronous serial Asynchronous serial
5.16. Write the difference between serial and parallel
communication communication
communication. AKTU 2017-18, Marks 02
1. Transmitter and receivers Transmitter and receivers are not
are synchronized by clock. synchronized by clock. Ans.
2. Data bits are transmitted Data bits are transmitted at Basis for Serial Parallel
with synchronization of constant rate. comparison communication communication
clock.
Meaning Data flows in bi-direction, Multiple lines are used to
3. Data transfer takes place in Data transfe r is character- bit by bit send data i.e., 8 bits or 1
blocks. oriented. byte at a time
5.12. Name the different types of I/O bus. Cost Economical Expensive
Ans. There are four types of I/O bus which are : Bits 1 bit 8 bits or 1 byte
i. Control command ii. Status command
transferred at
iii. Output data command iv. Input data command
1 clock pulse
5.13. Why are read and write control lines in a DMA controller Speed Slow Fast
bidirectional ? AKTU 2015-16, Marks 02 Applications Used for long distance Short distance . Fo r
Ans. Read and write control lines in a DMA controller are bidirectional communication. Fo r example, computer to
so that : example, computer to printer.
1. When a BG input is 0, the CPU can communicate with the DMA computer.
registers through the data bus to read from or write to the DMA
registers.
Computer Organization & Architecture SP–1 B (CS/IT-Sem-3) SP–2 B (CS/IT-Sem-3) Solved Paper (2014-15)
1. Attempt any two parts of the following : (10 × 2 = 20) 4. Attempt any two parts of the following : (10 × 2 = 20)
a. What is a multiplexer and demultiplexer ? Explain how an a. What is the difference between isolated I/O and memory
8 × 1 multiplexer can designed using two 4 × 1 multiplexers. mapped I/O ? Explain the advantages and disadvantages of
each.
b.
i. Simplify the following function using K-map and draw the b. Consider a cache uses a direct mapping scheme. The size of
circuit using AND, OR, NOT gates. main memory is 4K bytes and word size of cache is 2 bytes.
F(A, B, C, D) = s(0, 2, 8, 9, 10, 11, 13, 15) The size of cache memory is 128 bytes. Find the following :
i. The size of main memory address (assume each byte of main
ii. Add – 35 and – 31 in binary using 8-bit registers, in signed memory has an address)
1’s complement and signed 2’s complement. ii. Address of cache block
iii. How many memory location address will be translated to
c. Show step by step the multiplication process using booth’s cache address/block/location ?
algorithm when (+ 15) and (– 13) numbers are multiplied. iv. How can it be determined if the content of specified main
Assume 5 – bit registers that hold signed numbers. memory address in cache.
2. Attempt any two parts of the following : (10 × 2 = 20) c. Explain the following memory schemes discussing why
a. What is an ins truction in the context of computer needed the :
organization ? Explain the purpose of the various elements i. Interleaved memory ii. Associative memory
of an instruction with the help of a sample instruction
format. 5. Write short notes on any four of the following : (5 × 4 = 20)
a. Interrupt b. Bus arbitration
b. Explain the following addressing modes with the help of an c. Virtual memory d. Organization of 2D and 2.5D
example each : e. Programmed I/O f. DMA
i. Direct ii. Register indirect
iii. Implied iv. Immediate
v. Indexed
c. Write the steps in fetching a word from memory.
Differentiate between a branch instruction and call
subroutine instruction.
Computer Organization & Architecture SP–3 B (CS/IT-Sem-3) SP–4 B (CS/IT-Sem-3) Solved Paper (2014-15)
Operand
Operand Registers
Registers
Fig. 6. Indexed.
Fig. 3. Register indirect.
Computer Organization & Architecture SP–7 B (CS/IT-Sem-3) SP–8 B (CS/IT-Sem-3) Solved Paper (2014-15)
5. Fig. 1 shows the block diagram that depicts the transfer from
5. Ability to support Very difficult Easy
R1 to R2. The n outputs of register R1 are connected to the n
operating system
inputs of register R2.
and diagnostic
features P Load
Control circuit R2 Clock
6. Design process Difficult for more Easy
operation n
7. Memory Not used Control memory used R1
(RAM or ROM)
Fig. 8. Block diagram.
8. Chip area efficiency Uses less area Uses more area
6. The letter n will be used to indicate any number of bits for the
9. Used in RISC processor CISC processor
register. It will be replaced by an actual number when the
10. Output generation On the basis of On the basis of control length of the register is known.
input signal line. 7. Register R2 has a load input that is activated by the control
variable P.
Advantage of hardwired control unit : ii. Arithmetic micro-operation :
1. Speed is high. 1. The basic arithme tic micro-operations are additio n,
Disadvantages of hardwired control unit : subtraction, increment and decrement. The arithmetic micro-
1. Expensive to implement. operation defined by the statement, R3 R1 + R2
2. More error prone. which specifies an addition micro-operation.
3. Contain complex logic. 2. It states that the contents of register R1 are added to the
Advantages of micro-programmed control unit : contents of register R2 and the sum is transferred to register
1. Cheaper to implement. R3.
2. Less error prone. 3. Subtraction is implemented through complementation and
3. Contain very simple piece of logic. addition, which is specified in following statement :
Disadvantage of micro-programmed control unit : R3 R1 + R2 + 1
1. Speed is slow.
R2 is the symbol for the 1’s complement of R2. Adding 1 to
b. What are the different categories of micro-operations that the 1’s complement produce the 2’s complement.
may be carried out by CPU ? Explain each category of micro- 4. Adding the contents of R1 to the 2’s complement of R2 is
operations giving one example for each. equivalent to R1 – R2.
Ans. Different categories of micro-operation are :
iii. Logic micro-operation :
i. Register transfer micro-operation : 1. Logic micro-operations specify binary operations for strings of
1. Register transfer is defined as information transfer from one bits stored in registers.
register to another and is designated in symbolic form by means 2. These operations consider each bit of the register separately
of a replacement operator. and treat the contents of two registers R1 and R2 symbolized
by the statement
2. The statement denotes a transfer of the content of register R1
P : R1 R1 R2
into register R2. 3. It specifies a logic micro-operation is to be executed on the
R2 R1
individual bits of the registers provided that the control variable
3. It designates a replacement of the content of R2 by the content P = 1.
of R1. By definition, the content of the source register R1 does
4. For example, the content of R1 is 1010 and content of R2 is
not change after the transfer. 1100. The logic computation :
4. Every statement written in a register transfer notation implies
1010 content of R1
a hardware construction for implementing the transfer. 1100 content of R2
0110 content of R1 after P = 1
Computer Organization & Architecture SP–11 B (CS/IT-Sem-3) SP–12 B (CS/IT-Sem-3) Solved Paper (2014-15)
5. There are 16 different logic operations that can be performed ii. RISC.
with two binary variables. Ans.
iv. Shift micro-operation : 1. RISC (Reduced Instruction Set Computer) processor instruction
1. Shift micro-operations in computer architecture are those has a fixed length encoding of instruction and each instruction
which are used in serial shifting of data present in a register. executes in a single clock cycle by hardwired implementation of
2. Shift micro-operations move or shift data in a register bitwise each instruction.
that is, one bit at a time either left or right from its original 2. RISC architecture focus on reducing the number of instructions
position. and working with simpler instruction set having limited number
List of different types of shift micro-operation : of addressing modes and allowing them to execute more
a. Arithmetic shift micro-operation instructions in the same amount of time.
b. Logical shift micro-operation 3. Programs written for RISC architectures tend to make more space
c. Circular shift micro-operation in memory but RISC processor’s increased clock rate allows it to
execute its program in less time than a CISC processor takes to
c. Write short notes on the following : execute its program.
i. Microprogram sequencer for control memory. RISC characteristics :
Ans. 1. Simple instructions are used in RISC architecture.
1. Micro-program sequencer is a general purpose building block for 2. RISC helps and supports few simple data types and synthesizes
micro-programmed control unit. complex data types.
2. The basic components of a micro-programmed control unit are 3. RISC utilizes simple addressing modes and fixed length instructions
the control memory and the circuit that selects the next address. for pipelining.
3. The address selection part is called micro-program sequencer. 4. RISC permits any register to use in any context.
4. The main purpose of micro-program sequencer is to present an
address to the control memory so that micro-instruction may be 4. Attempt any two parts of the following : (10 × 2 = 20)
read and executed. a. What is the difference between isolated I/O and memory
5. The next address logic of the sequencer determines the specific mapped I/O ? Explain the advantages and disadvantages of
address source to be loaded into the control address register. each.
6. The choice of the address source is guided by the next address Ans. Difference between isolated I/O and memory mapped I/O :
information bits that sequencer receives from the present micro-
instruction. S. No. Isolated I/O Memory mapped I/O
7. All the instructions are loaded in the control memory. 1. Isolated I/O uses separate Memo ry mapped I/O uses
Main storage memory space. memory from the main memory.
Micro-
Control 2. Limited instructions can be Any instructio n which
instruction Data
memory
register path Input-output used. Those are IN, OUT, INS, references to memory can be
devices OUTS. used.
3. The addresses for isolated I/O Memory mapped I/O devices are
Branch address devices are called ports. treated as memory locations on
Next address the memory map.
generation circuit 4. Efficient I/O operations due to Inefficient I/O operations due to
Opcode
(micro-program R separate bus. single bus fo r data and
sequencer) External condition addressing.
5. Comparatively larger in size. Smaller in size.
Fig. 9. Block diagram of micro-programmed control
6. Uses complex internal logic. Co mmo n inte rnal lo gic fo r
with micro-program sequencer.
memory and I/O devices.
8. The present micro-instruction is placed in micro-instruction 7. Slower operations. Faster operations.
register for execution.
Computer Organization & Architecture SP–13 B (CS/IT-Sem-3) SP–14 B (CS/IT-Sem-3) Solved Paper (2014-15)
Advantage of isolated I/O : iv. We can determine the content of specified main memory address in
1. The devices of I/O are treated in a separate domain as compared to cache using this :
memory. i mod 2k
2. A total of 1MB address space is allowed for memory applications. where, i = particular memory address
3. In order to maximize the I/O operations (isolated) separate k = line number
instructions are always provided to perform these operations.
Disadvantage of isolated I/O : c. Explain the following memory schemes discussing why
1. The data transfer only occurs between the I/O port and the needed the :
registers. i. Interleaved memory ii. Associative memory
Advantages of memory mapped I/O : Ans.
1. I/O intensive operation is fast. i. Interleaved memory :
2. The SQLite library needs less RAM. 1. Interleaved memory is a design made to compensate for the
Disadvantages of memory mapped I/O : relatively slow speed of Dynamic Random Access Memory
1. If an I/O error on a memory-mapped file cannot be caught by the (DRAM).
application, results in a program crash. 2. This is done by spreading memory addresses evenly across
2. Performance is reduced by the use of memory-mapped I/O. memory banks.
3. Thus, in contiguous memory, reads and writes are done using
b. Consider a cache uses a direct mapping scheme. The size of each memory bank in turn, resulting in higher memory
main memory is 4K bytes and word size of cache is 2 bytes.
throughputs due to reduced waiting for memory banks to
The size of cache memory is 128 bytes. Find the following : become ready for desired operations.
i. The size of main memory address (assume each byte of main
4. As shown in Fig. 10, the lower order k bits of the address are
memory has an address) used to select the module (Memory bank) and higher order m
ii. Address of cache block
bits give a unique memory location in the memory bank that
iii. How many memory location address will be translated to
is selected by the lower order k bits.
cache address/block/location ? 5. Thus in this way consecutive memory locations are stored on
iv. How can it be determined if the content of specified main
different memory banks.
memory address in cache. 6. Whenever requests to access consecutive memory locations
Ans. Given,Size of main memory = 4 K bytes are being made several memory banks are kept busy at any
Size of cache memory = 128 bytes point in time.
Word size of cache = 2 bytes
7. This results in faster access to a block of data in the memory
i. Size of main memory address : and also results in higher overall utilization of the memory
Since, size of main memory = 4 K bytes = 212 bytes
system as a whole.
So, the size of main memory address = 12
m bits k bits
ii. Address of cache block :
Since, size of cache memory = 128 bytes Address in module Module
Block size = word size of cache = 2 bytes
128
Number of lines = = 64
2
So, address of cache block is from 0 to 63 ABR DBR ABR DBR ABR DBR
iii. Since, size of main memory = 4 K bytes = 4096 bytes
So, number of block in main memory = 4096 Module Module Module
and number of block in cache = 64 0 i 2k – 1
and each block of cache = 2 bytes
Fig. 10.
4096
So, = 32 memory location address will be translated to 8. If k bits are allotted for selecting the bank as shown in the
(64 2) Fig. 10, there have to be total 2k banks. This ensures that
cache address/block/location. there are no gaps of non-existent memory locations.
Computer Organization & Architecture SP–15 B (CS/IT-Sem-3) SP–16 B (CS/IT-Sem-3) Solved Paper (2014-15)
ii. Associative memory : 2. Among several masters and slave units that are connected to
1. Associative memory is a memory in which location is accessed a shared bus, it may happen that more than one master or
by a field of data word stored in the memory rather than by slave units will request access to the bus at the same time.
any address. 3. In such situation, bus access is given to the master having
2. It can be viewed as a random access type memory which in highest priority.
addition to having a physically wired-in addressing mechanism 4. Three different mechanisms are commonly used for this :
also has wired-in logic for bit comparison. i. Daisy chaining :
3. This logic circuit enables comparison of desired bit positions a. Daisy chaining method is cheaper and simple method.
of all the words with a specified input key. b. All master make use of the same line for bus request.
4. This comparison is done simultaneously for all the words. c. The bus grant signal serially propagates through each master
5. This is also called Content Addressable Memory (CAM). until it encounters the first one that is requesting.
ii. Parallel arbitration : The parallel arbitration consists of priority
5. Write short notes on any four of the following : (5 × 4 = 20) encoder and a decoder. In this mechanism, each bus arbiter has a
a. Interrupt b. Bus arbitration bus request output line and input line.
c. Virtual memory d. Organization of 2D and 2.5D iii. Independent priority : In this each master has separate pair of
e. Programmed I/O f. DMA bus request and bus grant lines and each pair has a priority
Ans. assigned to it.
a. Interrupt : c. Virtual memory :
Interrupt : An interrupt is a signal sent by an I/O interface to the 1. Virtual memory is a memory management capability of an
CPU when it is ready to send information to the memory or receive OS that uses hardware and software to allow a computer to
information from the memory. compensate for physical memory shortages by temporarily
Identifying the source of an interrupt : transferring data from Random Access Memory (RAM) to
Two methods are available to determine the interrupting device : disk storage.
i. Polled interrupts : 2. Virtual address space is increased using active memory in RAM
1. On receiving an interrupt request the micro-processor will and inactive memory in Hard Disk Drives (HDDs) to form
execute a routine causing it to poll each of the devices in turn. contiguous addresses that hold both the application and its
2. Devices have a status register containing one or more data.
interrupt request bits. 3. A system using virtual memory can load larger programs or
3. If a device caused the interrupt, its interrupt flag bit will be multiple programs running at the same time, allowing each
set. one to operate as if it has infinite memory and without having
4. The appropriate service routine will then be selected and the to purchase more RAM.
device serviced. 4. Virtual memory is a facility that allows program to address
5. Polling can be very inefficient if there are many devices capable memory from local point of view, without regard to the amount
of causing an interrupt. of main memory.
6. This method uses only software methods to identify an 5. A virtual me mory system provides a mechanism for
interrupting device. translating program generated addresses into correct main
ii. Vectored interrupts : memory locations.
1. This is the method used in modern computers. 6. This is done dynamically, while programs are being executed
2. It is sometimes referred to as hardware identification since in the CPU.
additional hardware is required. d. Organization of 2D and 2.5D :
3. Each vector is identified by an interrupt number from 0 to 2D organization :
255 and provides the processor with the means of addressing 1. The cells are organized in the form of a two-dimensional
the appropriate interrupt handler. array with rows and columns.
4. A vector address is determined by multiplying its vector 2. Each row refers to word line. For 4-bit per word memory, 4
number by 4. cells are interconnected to a word line. Each column in the
array refers to a bit line.
b. Bus arbitration : 3. The Memory Address Register (MAR) holds the address of
1. Bus arbitration is a mechanism which decides the selection of the location where read/write operation is executed. In
current master to access bus. Fig. 11, MAR has 4-bit lines.
Computer Organization & Architecture SP–17 B (CS/IT-Sem-3) SP–18 B (CS/IT-Sem-3) Solved Paper (2014-15)
Bit lines (complement to each other) Memory cells 1. In 2.5D organization there exists a segment.
2. The content of MAR is divided into two parts–x and y number of
bits.
3. The number of segments S is equal to 2y.
A0 D
M A1 E W0 Word line 4. X = 2x drive lines are fed into the cell array and y number of bits
A C decode one bit line out of S lines fed into a segment of the array. In
R A2 O
A3 D total, there are Sb number of bit lines for a b bit per word memory.
E
R 5. Thus for any given address in the MAR, the column decoder decodes
W1 Word line
b out of Sb bit lines by using the y bits of the MAR while a particular
word line is activated by using the x bits.
6. Thus only the b numbers of bits in the array are accessed by enabling
the word line and b number of bit lines simultaneously.
7. Though 2.5D organized memory may need lesser chip decoding
W15
logic, it suffers from one drawback. With high density chips, a
R/W Sense/ Sense/ Sense/ Sense/
simple failure, such as external pin connection opening or a failure
CS write ckt. write ckt. write ckt. write ckt. on one bit can render the entire chip inoperative.
b3 b2 b1 b0 Data lines e. Programmed I/O :
1. When the CPU is executing a program and executes an
Fig. 11. 2D organization of a memory chip of size 16 × 4. instruction relating to I/O, it executes that instruction by
4. The content of MAR is decoded by an address decoder on the issuing a command to the appropriate I/O module.
chip to activate each word line.
5. The cells in each column are connected to a sense/write circuit
by two bit lines. Two bit lines are complement to each other. Issue read command
6. The sense/write circuits are activated by the Chip Select (CS) to I/O module CPU I/O
lines. The sense/write circuits are connected to the data lines
of the chip.
7. During a read operation, these circuits sense or read the Read status I/O CPU
information stored in the cells selected by a word line and of I/O module
transmit this information to the data lines. Not
8. During a write operation, the sense/write circuits receive or ready
write input information from the data lines and store it in the Check Error
status condition
selected cells.
2.5D organization : Ready
Read word form I/O CPU
MAR
I/O module
x Word b bits b bits b bits
line X
decoder Segment 1 Segment 2 Segment 5 Write word CPU Memory
into memory
Column No
decoder Done ?
x+y=n Y
X = 2x Sense/write circuits
Yes
y = 2y Decode 1 out of
S segments Next instruction
b bits Fig. 13. Programmed I/O.
Fig. 12. 2.5D organization.
Computer Organization & Architecture SP–19 B (CS/IT-Sem-3) Computer Organization & Architecture SP–1 B (CS/IT-Sem-3)
2. With programmed I/O, the I/O module will perform the B.Tech.
requested action and then set the appropriate bits in the I/O
status register. (SEM. V) ODD SEMESTER THEORY
3. The I/O module takes no further action to alert the CPU.
4. It does not interrupt the CPU.
EXAMINATION, 2015-16
5. Thus, it is the responsibility of CPU to periodically check the COMPUTER ARCHITECTURE
status of the I/O module until it finds that the operation is
complete. Time : 3 Hours Total Marks : 100
f. DMA :
1. DMA stands for ‘‘Direct Memory Access’’ and is a method of SECTION – A
transferring data from the computer’s RAM to another part
of the computer without processing it using the CPU. Note : Attempt all parts. All parts carry equal marks. Write answer of
2. While most data that is input or output from our computer is each part in short. (2 × 10 = 20)
processed by the CPU, some data does not require processing,
or can be processed by another device. 1. a. What is the main advantage of RTL ?
3. DMA can save processing time and is a more efficient way to
move data from the computer's memory to other devices. b. Define control word.
4. In order for devices to use direct memory access, they must
be assigned to a DMA channel. Each type of port on a computer c. Give block diagram of microprogram sequencer.
has a set of DMA channels that can be assigned to each
connected device. d. Why are read and write control lines in a DMA controller
5. For example, a PCI controller and a hard drive controller bidirectional ?
each have their own set of DMA channels.
Block diagram for DMA : e. List two important instruction set design issues.
Address bus, READ/ and WRITE/
Micro
RAM f. List the two techniques used for grouping the control signals.
processor Data bus
g. Which of L1 and L2 cache is faster ?
BUSREQ BUSACK
h. What is the use of modem in synchronous communication ?
v. Control memory
SOLUTION OF PAPER (2015-16)
4. What do you mean by CAM ? Explain its major
characteristics. SECTION – A
5. Explain various types of processor organization. Note : Attempt all parts. All parts carry equal marks. Write answer of
each part in short. (2 × 10 = 20)
6. Explain the sequence that takes place when an interrupt
occurs. 1. a. What is the main advantage of RTL ?
Ans. Advantage of RTL are :
7. A computer uses RAM chips of 1024*1 capacity. i. It uses register’s as a primitive component in the digital system
i. How many chips are needed and how should their address instead of flip-flops and gates.
lines be connected to provide a memory capacity of 1024*8 ? ii. It describes the information flow and processing tasks among the
ii. How many chips are needed to provide a memory capacity data stored in the registers in a concise and precise manner.
of 16 KB ? Explain in words how the chips are to be connected iii. It uses a set of expressions and statements which resemble the
to the address bus. statements used in programming languages.
iv. The presentation of digital functions in register transfer logic is
8. A ROM chip of 1024*8 has four select inputs and operates very user friendly.
from a 5 volt power supply. How many pins are needed for
the IC package ? Draw a block diagram and label all input b. Define control word.
and output terminals in the ROM. Ans. Control word is defined as a word whose individual bits represent
the various control signals. Therefore each of the control steps in
9. i. What are the differences between hardwired and the control sequence of an instruction defines a unique combination
microprogrammed control unit ? of 0s and 1s.
c. Give block diagram of microprogram sequencer.
ii. What is RISC ? Explain its various characteristics.
Ans.
External Condition
SECTION-C inputs
IR
codes
Note : Attempt any two questions from this section. (15 × 2 = 30) Micro-instruction sequencer
10. i. What is the distinction between spatial locality and (starting and branch address generator)
temporal locality ?
11. Why input output interface is required ? Describe in detail. Control memory
d. Why are read and write control lines in a DMA controller ii. Data paths
bidirectional ? iii. System
Ans. Read and write control lines in a DMA controller are bidirectional
so that : SECTION – B
1. When a BG input is 0, the CPU can communicate with the DMA
registers through the data bus to read from or write to the DMA Note : Attempt any five questions from this section. (10 × 5 = 50)
registers. 2. Discuss the advantages and disadvantages of polling and
2. When BG is 1, the CPU has relinquished the buses and the DMA daisy chaining bus arbitration schemes.
can communicate directly with the memory by specifying an address Ans. Daisy chaining :
in the address bus and activating RD or WR. 1. In this, all masters make use of the same line for bus request.
2. The bus grant signal serially propagates through each master until
e. List two important instruction set design issues. it encounters the first one that is requesting access to the bus.
Ans. Two important instruction set design issues are : 3. This master blocks the propagation of the bus grant signal, activates
1. Number of operations and type of operation to be provided and how the busy line and gains control of the bus.
must complexity they should support. 4. Therefore any other requesting module will not receive the grant
2. Data types of operands upon which operations to be performed. signal and hence cannot get the bus access.
Highest priority Lowest priority
f. List the two techniques used for grouping the control signals.
Master 1 Master 2 Master N
Ans. The two techniques used for grouping the control signal
are :
Bus Bus Bus
i. Hardwired control unit
access access access
ii. Micro-programmed control unit
logic logic logic
g. Which of L1 and L2 cache is faster ?
Ans. Bus Bus grant
1. All processors rely on L1 cache, which is usually located on the grant
processor and is very fast memory and expensive.
2. L2 cache is slower, bigger and cheaper than L1 cache. Bus request
Controller
h. What is the use of modem in synchronous communication ? Bus busy
Ans. A modem converts digital signals into audio tones to be transmitted Fig. 2. Daisy chaining method.
over telephone lines and also converts audio tones from the line to
Advantages of daisy chaining :
digital signals for machine use. The modems used in synchronous
1. It is a simple and cheaper method.
transmission have internal clocks that are set to the frequency that
2. It requires the least number of lines and this number is
bits are being transmitted in the communication line.
independent of the number of masters in the system.
Disadvantages of daisy chaining :
i. What is CAM ?
1. The propagation time delay of bus grant signal is proportional to
Ans. A Content Addressable Memory (CAM) is a circuit that combines
the number of masters in the system. This makes arbitration time
comparison and storage in a single device. Instead of supplying an
slow and hence limits the number of master in the system.
address and reading a word like a RAM, we supply the data and the
2. The priority of the master is fixed by the physical location of master.
CAM looks to see if it has a copy and returns the index of the
3. Failure of any one master causes the whole system to fail.
matching row.
Advantages of polling bus arbitration :
1. If the one module fails entire system does not fail.
j. List three types of control signals.
2. The priority can be changed by altering the polling sequence stored
Ans. Three types of control signals are :
in the controller.
i. ALU
SP–6 B (CS/IT-Sem-3) Solved Paper (2015-16) Computer Organization & Architecture SP–7 B (CS/IT-Sem-3)
Disadvantages of polling bus arbitration : 2. CAM is capable of searching its entire contents in a single clock
1. It requires more bus request and grant signals (2 × n signals for n cycle.
modules). 3. It does that by pairing the SRAM-based memory with additional
2. Polling overhead can consume a lot of CPU time. logic comparison circuitry that is active on every clock cycle.
4. The way CAM functions is almost the opposite of Random Access
3. Briefly define the following terms : Memory (RAM).
i. Micro operation
5. Data stored on CAM, can be accessed by searching for the content
ii. Micro instruction itself, and the memory retrieves the addresses where that content
iii. Micro program
can be found.
iv. Micro code 6. Because of its parallel nature, CAM is much faster than RAM for
v. Control memory
searching.
Ans. The major characteristics are :
i. Micro-operation :
1. This memory is accessed simultaneously and in parallel on the
1. Micro-operation is a set of operations that the processor unit basis of data content rather than by specific address or location.
has to perform to execute the major phases of instruction
2. This memory is capable of finding an empty unused location to
cycle. store the word.
2. The instruction cycle has three major phases of fetch, decode
3. This memory is uniquely suited to do parallel searches by data
and execute. association.
3. The primary function of a CPU is to execute sequence of
4. Each cell must have storage capability as well as logic circuits for
instructions which is in accordance with the instruction cycle. matching its content with an external argument.
ii. Micro-instructions :
1. Micro-instructions are the individual control words in the 5. Explain various types of processor organization.
micro routine.
Ans. Types of processor organizations :
2. This contains the control signals for sequencing information.
iii. Micro-program : Micro-program is a micro-code in a particular a. General-purpose register based :
processor implementation. Writing micro-code is often called micro- 1. In this organization, the registers communicate with each other
programming. not only for direct data transfers, but also while performing
iv. Micro-code : various micro-operations.
1. Micro-code is a layer of hardware-level instructions and/or 2. Seven registers are used for general purpose, the output of
data structures involved in the implementation of higher level each register is connected to two multiplexer (MUXs) inputs.
machine code instructions in many computers and other
processors. 3. Three select lines are used to select any one of the seven
registers and the contents of selected registers are supplied to
2. It helps to separate the machine instructions from the
underlying electronics so that instructions can be designed the inputs of ALU.
and altered more freely. 4. The buses A and B are used to form the inputs to the common
v. Control memory : arithmetic logic unit (ALU).
1. Control memory is a Random Access Memory (RAM) 5. The operation to be performed is selected in the ALU and is
consisting of addressable storage registers. determined by the arithmetic or logic micro-operation by using
2. It is used as a temporary storage for data. function select lines (OPR).
3. Access to control memory data requires less time than to
6. The result of the micro-operation is available as output data
main memory, this speeds up CPU operation.
and also goes into the inputs of all the registers.
4. What do you mean by CAM ? Explain its major 7. Any one of the destination register receives the information
characteristics. from the output bus which is selected by a decoder.
Ans. CAM :
1. Content Addressable Memory (CAM) is computer memory that
operates like a hardware search engine for search-intensive
applications.
SP–8 B (CS/IT-Sem-3) Solved Paper (2015-16) Computer Organization & Architecture SP–9 B (CS/IT-Sem-3)
Address
External input FULL = 1
when stack is full
63
R1 EMPTY FULL
R2
R3 EMPTY = 1
when stack is empty
R4
PQR 3
R5 Stack pointer (SP) 2
XYZ
R6 (consists of 6 bits)
ABCD 1
R7 0
Holds the data to be pushed Data
7 onto stack or that is popped Register
Load SEL SEL off from the stack (DR)
MUX A MUX B
line A B
Bus A Bus B Fig. 4. Block diagram of 64-word stack.
3 to 8
decoder c. Accumulator based :
Arithmetic logic OPR Internal bus
unit (ALU)
SEL D
Output General purpose
Flags ALU
(a) Block diagram registers
3 3 3 4
IR
SEL A SEL B SEL D OPR R1
(b) Control word Decoder R2
Fig. 3. General-purpose register based organization.
R3
4. Accumulator (ACC) : This block acts as the default temporary b. The mask is then set to accept interrupts of higher priority.
storage register location for all mathematical operations in 4. Interrupt acknowledgment :
ALU.
5. Instruction Register IR and Decoder : After instruction is a. At some point, the processor must acknowledge the interrupt
being serviced, so that the interrupting device becomes free
fetched from the memory its stored in Instruction Register.
The instruction is then decode by the decoder. to continue its task.
b. One of the ways is to have an external signal line denoted to
6. Stack pointer (SP) : Stack pointer is involved in managing
the stack transfers during and program execution. interrupt acknowledge.
7. Timing and control unit : This block manages the 5. Interrupt service routine :
sequencing of events o n a timeline betwe en various a. At this point, the processor initiates the interrupt service
components of a CPU. All the blocks are controlled in a manner routine.
to optimize the computational power of the unit by minimizing b. The address of the routine can be obtained in several ways,
the failures. depending on the system architecture.
8. Flags : Flags are also registers or bits inside registers which c. The simplest is found in the polling method, in which one
are set or cleared for a particular condition on an arithmetic routine polls each device to find which one interrupted.
operation. Some of the most common flags are :
6. Restoration and return :
i. Sign : Is used to identify the set/reset of most significant
bit of the result. a. After the interrupt service routine has completed its
ii. Carry : Is used to identify, a carry during addition, or processing, it restores all the registers it has changed, and
borrow during subtraction/comparison. the processor restores all the registers and flags that were
iii. Parity : Set if the parity is even. Refer parity from here. saved at the initiation of the interrupt routine.
iv. Zero : To identify when the result is equal to zero. b. If this is done correctly, the processor should have the same
9. Bus sub-system : All the data transfers in-between memory status as before the interrupt was recognized.
and CPU registers including instruction fetches are carried
over bus. 7. A computer uses RAM chips of 1024*1 capacity.
i. How many chips are needed and how should their address
6. Explain the sequence that takes place when an interrupt lines be connected to provide a memory capacity of 1024*8 ?
occurs. ii. How many chips are needed to provide a memory capacity
Ans. When an interrupt occurs, sequence of following six steps takes of 16 KB ? Explain in words how the chips are to be connected
place : to the address bus.
Ans.
1. Interrupt recognition :
i. Available size of RAM chips = 1024 × 1
a. The interrupt recognition is recognized by the processor of
Required memory capacity = 1024 bytes
an interrupt request due to activation of an interrupt request
= 1024 × 8
line or an internal mechanism.
b. In this step, the processor can determine which device or 1024 8
Number of chips required = = 8 chips
CPU, component made the request. 1024 1
So, 8 chips are needed with address line connected in parallel.
2. Status saving :
ii. To provide a memory capacity of 16K bytes, chips required are
a. The goal of this step is to make the interrupt sequence
16 × 8 = 128 chips
transparent to the interrupted process.
Number of address line for 16 K = 14 (16 K = 214)
b. Therefore, the processor saves the flags and registers that
So, 14 lines to specify chip address.
may be changed by the interrupt service routine so that they
may be restored after the service routine is finished.
8. A ROM chip of 1024*8 has four select inputs and operates
3. Interrupt masking : from a 5 volt power supply. How many pins are needed for
a. For the first few steps of the sequence, all interrupts are the IC package ? Draw a block diagram and label all input
masked out so that no other interrupt may be processed before and output terminals in the ROM.
the processor status is saved.
SP–12 B (CS/IT-Sem-3) Solved Paper (2015-16) Computer Organization & Architecture SP–13 B (CS/IT-Sem-3)
Ans. Size of ROM Chip = 1024 × 8 6. Design process Difficult for more Easy
Number of input = 10 pin [210 = 1024]
operation
Number of output = 8 pin
Number of chip select = 4 pin 7. Memory Not used Control memory used
Power = 2 pin (RAM or ROM)
Total 24 pins are required. 8. Chip area efficiency Uses less area Uses more area
CS1
9. Used in RISC processor CISC processor
CS2
CS3 10. Output generation On the basis of On the basis of control
CS4 input signal line.
I0 O0
I1 O1 ii. What is RISC ? Explain its various characteristics.
I2 O2 Ans.
I3 O3 1. RISC (Reduced Instruction Set Computer) processor instruction
ROM
I4 1024 × 8 O4 has a fixed length encoding of instruction and each instruction
I5 O5 executes in a single clock cycle by hardwired implementation of
I6 O6 each instruction.
I7 O7
2. RISC architecture focus on reducing the number of instructions
I8 and working with simpler instruction set having limited number
I9 of addressing modes and allowing them to execute more
V(+) instructions in the same amount of time.
V(–)
3. Programs written for RISC architectures tend to make more space
Fig. 6. in memory but RISC processor’s increased clock rate allows it to
execute its program in less time than a CISC processor takes to
9. i. What are the differences between hardwired and execute its program.
microprogrammed control unit ? RISC characteristics :
Ans. Comparison between hardwired control and micro- 1. Simple instructions are used in RISC architecture.
programmed control :
2. RISC helps and supports few simple data types and synthesizes
complex data types.
S. No. Characteristics Hardwired Micro-programmed
control control 3. RISC utilizes simple addressing modes and fixed length instructions
for pipelining.
1. Speed Fast Slow
4. RISC permits any register to use in any context.
2. Implementation Hardware Software
SECTION-C
3. Flexibility Not flexible Flexible
4. Ability to handle Somewhat Easier Note : Attempt any two questions from this section. (15 × 2 = 30)
large/ complex difficult 10. i. What is the distinction between spatial locality and
instruction set temporal locality ?
Ans. Difference : 11. Why input output interface is required ? Describe in detail.
Ans.
S. No. Spatial locality Temporal locality
i. I/O interface provides a method of transferring information between
1. Spatial locality refers to the Temporal locality refers to the internal storage and external I/O devices.
tendency of execution to tendency for a processor to access ii. In order to interface peripherals with the CPU, I/O interfaces contain
involve a number of memory memory locations that have been special communication links. These communication links are used
locations that are clustered. used recently. to overcome, the differences between the CPU and peripherals
such as data transfer speed, mode of operation, etc.
2. The spatial locality means The temporal locality means that The major requirements for an I/O module can be given as :
that instructions stored near- a recently executed instruction 1. Processor communication : This involves the following tasks :
by to the recently executed is likely to be executed again very a. Exchange of data between processor and I/O module.
instructions are also likely to soon. b. Command decoding : The I/O module for a disk drive may
be executed soon. accept the following commands from the processor : READ
3. The spatial aspect suggests The te mpo ral aspe ct of the SECTOR, WRITE SECTOR, SEEK track, etc.
that instead of bringing just locality reference suggests that c. Status reporting : The device must be able to report its
o ne item fro m the main whene ve r info rmatio n o f status to the processor. For example, disk drive busy, ready
memory to the cache, it is instruction and data is first etc.
wise to bring several items needed, this information should d. Status reporting may also involve reporting various errors.
that re side at adjace nt be brought into cache where it e. Address recognition : Each I/O device has a unique address
addresses as well. will hopefully remain until it is and the I/O module must recognize this address.
needed again. 2. Device communication : The I/O module is able to perform device
communication such as status reporting.
ii. Show the multiplication process using Booth’s algorithm
3. Control and timing : The I/O module is able to co-ordinate the
when the following numbers are multiplied : (– 13) by (+ 8)
flow of data between the internal resources (such as processor,
Ans. True binary equivalent of + 8 = 01000 memory) and external devices.
True binary equivalent of + 13 = 01101
4. Data buffering :
1’s complement of + 13 = 10010 a. This is necessary as there is a speed mismatch between speed
+1
——— of data transfer between processor and memory and external
2’s complement of + 13 = 10011 (–13) devices.
———
Multiplier = 01000 b. Data coming from the main memory are sent to an I/O module
Multiplicand (B) = 10011 in a rapid burst.
c. The data is buffered in the I/O module and then sent to the
A Qn Qn + 1 Operation SC peripheral device at its rate.
00000 01000 0 100 5. Error detection :
a. The I/O module is able to detect errors and report them to the
00000 00100 0 Ashr AQQn + 1 processor.
00000 00010 0 Ashr AQQn + 1 011 b. These errors may be mechanical errors (such as paper jam in
a printer), or changes in the bit pattern of transmitted data. A
00000 00001 0 Ashr AQQn + 1 010 common way of detecting such errors is by using parity bits.
13. Write a note on subroutines. 3. Explain one, two and three address instruction.
Ans.
14. Draw the block diagram of control unit of basic computer. i. One address instruction : One address instruction uses an
Explain in detail with control timing diagrams. implied accumulator (AC) register for all data manipulation.
ii. Two address instruction : In this format each address field can
15. List and explain different types of shift micro-operation. specify either a processor register or a memory word.
iii. Three address instruction : Three address instruction formats
can use each address fields to specify either a processor register or
a memory operand.
4. Define the following terms :
i. Effective address
ii. Immediate instruction
Ans.
i. Effective address : Effective address is the address of the operand
in a computation-type instruction or the target address in a branch-
type instruction.
ii. Immediate instruction : An immediate mode instruction has an
operand field rather than an address field. The operand field contains
the actual operand to be used in conjunction with the operation
specified in the instruction.
Computer Organization & Architecture SP–5 B (CS/IT-Sem-3) SP–6 B (CS/IT-Sem-3) Solved Paper (2016-17)
5. Explain the following terms : 2. When a CPU receives an interrupt signal it stops executing current
i. PSW ii. Delayed load normal program.
Ans. 3. After stopping it saves the state of various registers in stack.
i. PSW (Program Status Word) : 4. When this is done CPU executes a subroutine in order to perform
1. The collection of all status bit conditions in the CPU is sometimes the specific task requested by the interrupt.
called a program status word or PSW.
2. The PSW is stored in a separate hardware register and contains 9. Differentiate between synchronous and asynchronous
the status information that characterizes the state of the CPU. transmission.
3. It includes the status bits from the last ALU operation and it Ans.
specifies the interrupts that are allowed to occur and whether the
S. No. Synchronous serial Asynchronous serial
CPU is operating in a supervisor or user mode.
ii. Delayed load : communication communication
1. It is up to the compiler to make sure that the instruction following 1. Transmitter and receivers are Transmitter and receivers are
the load instruction uses the data fetched from memory. synchronized by clock. not synchronized by clock.
2. If the compiler cannot find a useful instruction to put after the
2. Data bits are transmitted with Data bits are transmitted at
load, it inserts a no-op (no-operation) instruction.
synchronization of clock. constant rate.
3. This is a type of instruction that is fetched from memory but has
no operation, thus wasting a clock cycle. 3. Data transfer takes place in Data transfer is character-
4. This concept of delaying the use of the data loaded from memory blocks. oriented.
is referred to as delayed load.
10. What is cache memory used for ?
6. Differentiate SIMD and MIMD. Ans.
Ans. 1. Cache memory is used to store frequently used data or instructions.
2. Cache memory is used to improve computer performance by
S. No. SIMD MIMD
reducing its access time.
1. It stands fo r Single It stands for Multiple Instruction 3. A cache holds instructions and data that are likely to be needed for
Instructio n Stre am, Stream, Multiple Data Stream. the CPU’s next operation.
Multiple Data Stream.
2. In this, a paralle l In this, we have N processors, N SECTION – B
computer consists of N streams of instructions and N streams
identical processors. of data. Note : Attempt any five questions : (10 × 5 = 50)
1. Show the contents of the registers E, A, Q, SC during the
7. What are the modes of data transfer ? process of multiplication of two binary numbers 11111
(multiplicand) and 10101 (multiplier). The signs are not
Ans. Modes of data transfer are :
i. Programmed I/O : Programmed I/O operations are the result of included.
I/O instructions written in computer program. Ans.
ii. Interrupt-driven I/O : This mode avoids the drawbacks of Multiplicand B = 11111 E A Q SC
programmed I/O by using interrupt request. 0 00000 10101 101
iii. Direct memory access : The interface transfers data onto and Qn = 1 ; add B 00000
out of the memory unit through memory bus. 11111
11111
8. What is an interrupt ? Shift right EAQ 0 01111 11010 100
Ans. Qn = 1 ; add B 01111
1. An interrupt is a signal sent by an I/O interface to the CPU when it 11111
is ready to send information to the memory or receive information 00000
from the memory. Shift right EAQ 0 00000 01101 011
Computer Organization & Architecture SP–7 B (CS/IT-Sem-3) SP–8 B (CS/IT-Sem-3) Solved Paper (2016-17)
Qn = 0 ; shift right EAQ 0 00000 00110 010 7. The address part is the binary equivalent of 300. The control goes
to address 300 to find the address of the operand.
Qn = 0 ; shift right EAQ 0 00000 00011 001
8. The address of the operand in this case is 1350. The operand found
Qn = 0 ; shift right EAQ 0 00000 00001 000 in address 1350 is then added to the content of AC.
9. The indirect address instruction needs two references to memory
2. In an instruction format, there are 16 bits in an instruction to fetch an operand.
word. Bit 0 to 11 convey the address of the memory location Instruction will be decoded and executed by this control
for memory related ins tructions. For non memory unit :
instructions these bits convey various register or I/O Instruction Register (IR)
operations. Bits 12 to 14 show the various basic memory 15 14 13 12 11 – 0
operations such as ADD, AND, LDA etc. Bit 15 shows if the
Other inputs
memory is accessed directly or indirectly. For such an 3 × 8 Decoder
instruction format draw block diagram of the control unit 7 6 5 4 3 21 0 D0 Control
of a computer and briefly explain how an instruction will 1 D7 Control outputs
be decoded and executed, by this control unit. Logic
T15
Ans. Gates
T0
1. Consider the instruction code format shown in Fig. 1(a). It consists
of a 3-bit operation code, a 12-bit address, and an indirect address 15 14 ............ 2 1 0
mode bit designated by I. 4 × 16
Decoder
2. The mode bit is 0 for a direct address and 1 for an indirect address.
3. A direct address instruction is shown in Fig. 1(b). It is placed in
address 22 in memory. The I bit is 0, so the instruction is recognized 4-bit Increment (INR)
as a direct address instruction. Sequence Counter Clear (CLR)
(SC) Clock
15 14 - 12 11 0
I Opcode Address Fig. 2. Block diagram of control unit of a computer.
(a) Instruction format 1. Control unit consists of :
Memory Memory
i. Instruction register
22 0 ADD 457 35 1 ADD 300
ii. Number of control logic gates
iii. Two decoders
300 1350 iv. 4-bit sequence counter
2. An instruction read from memory is placed in the Instruction
457 Operand Register (IR).
1350 Operand
3. The instruction register is divided into three parts : the I bit,
operation code, and address part.
+ + 4. First 12-bits (0 – 11) are applied to the control logic gates.
5. The operation code bits (12 – 14) are decoded with a 3 × 8 decoder.
AC AC 6. The eight outputs (D0 through D7) from a decoder go to the control
logic gates to perform specific operation.
(b) Direct address (c) Indirect address
7. Last bit 15 is transferred to a I flip-flop designated by symbol I.
Fig. 1. 8. The 4-bit Sequence Counter (SC) can count in binary from 0
4. The opcode specifies an ADD instruction, and the address part is through 15.
the binary equivalent of 457. 9. The counter output is decoded into 16 timing pulses T0 through T15.
5. The control finds the operand in memory at address 457 and adds 10. The sequence counter can be incremented by INR input or clear by
it to the content of AC. CLR input synchronously.
6. The instruction in address 35 shown in Fig. 1(c) has a mode bit
I = 1. Therefore, it is recognized as an indirect address instruction.
Computer Organization & Architecture SP–9 B (CS/IT-Sem-3) SP–10 B (CS/IT-Sem-3) Solved Paper (2016-17)
3. Write an ass embly level program for the following 5. The next address logic of the sequencer determines the specific
pseudocode : address source to be loaded into the control address register.
SUM = 0 6. The choice of the address source is guided by the next address
SUM = SUM + A + B information bits that sequencer receives from the present micro-
DIF = DIF-C instruction.
SUM = SUM + DIF 7. All the instructions are loaded in the control memory.
Ans. 8. The present micro-instruction is placed in micro-instruction
CLA /SUM = 0 register for execution.
STA SUM
LDA SUM /Load current sum 5. Give the detailed comparison between RISC and CISC.
ADD A /Add A to SUM
Ans.
ADD B /Add B to SUM
STA SUM /Save SUM S. No. RISC CISC
LDA C /Load C to AC
CMA /Create 2’s complement 1. Multiple register sets, often Single re giste r se t, o fte n
INC consisting of more than 256 consisting 6 to 16 registers total.
ADD DIF /Subtract C from DIF registers.
STA DIF /Save DIF 2. Thre e re giste r o pe rands One or two register operands
ADD SUM /Add SUM to DIF allowed per instruction (for allo we d pe r instructio n (for
STA SUM /Save SUM example, add R1, R2, R3). example, add R1, R2).
HLT /Halt
3. Parameter passing through Parame te r passing thro ugh
4. Explain microprogram sequencer for a control memory efficient o n-chip re gister inefficient off-chip memory.
using a suitable block diagram. windows.
Ans. 4. Single -cycle instructio ns Multiple-cycle instructions.
1. Micro-program sequencer is a general purpose building block for (except for load and store).
micro-programmed control unit. 5. Hardwired control. Micro-programmed control.
2. The basic components of a micro-programmed control unit are
the control memory and the circuit that selects the next address. 6. Highly pipelined. Less pipelined.
7. Simple instructions are few in The re are many co mple x
Micro- Main storage
Control number. instructions.
instruction Data
memory 8. Fixed length instructions. Variable length instructions.
register path Input-output
devices 9. Complexity in compiler. Complexity in microcode.
10. Only load and store instructions Many instructions can access
Branch address can access memory. memory.
Next address 11. Few addressing modes. Many addressing modes.
generation circuit
Opcode
(micro-program R
sequencer) Section-C
External condition
Note : Attempt any two questions : (15 × 2 = 30)
Fig. 3. Block diagram of micro-programmed control
1. Explain the Booth’s algorithm in depth with the help of
with micro-program sequencer.
flowchart. Give an example for multiplication using Booth’s
3. The address selection part is called micro-program sequencer. algorithm.
4. The main purpose of micro-program sequencer is to present an Ans. The algorithm for 2’s complement multiplication is as follows :
address to the control memory so that micro-instruction may be Step 1 : Load multiplicand in B, multiplier in Q. For negative
read and executed. numbers, 2’s complement format to be used.
Computer Organization & Architecture SP–11 B (CS/IT-Sem-3) SP–12 B (CS/IT-Sem-3) Solved Paper (2016-17)
Step 2 : Initialize the down counter CR by the number of bits 2. How main memory is useful in computer system ? Explain
involved. the memory address map of RAM and ROM.
Step 3 : Clean locations A (n-bits) and Qn + 1 (1-bit). Ans. Main memory is useful in computer system :
Step 4 : Check LS bit of Qn and Qn + 1 jointly. If the pattern is 00 or 1. The main memory occupies a central position in a computer system.
11 then go to Step 5. If 10, then A = A – B. If 01, then A = A + B. 2. It is able to communicate directly with the CPU and with auxiliary
Step 5 : Perform arithmetic right-shift with A, Qn and Qn + 1. LS of memory devices through an I/O processor.
A goes to MS of Qn and LS of Q goes to Qn + 1. Old content of Qn + 3. It is relatively large and fast.
1 is discarded. Memory address map of RAM and ROM :
Step 6 : Decrement CR by one. If CR is not zero then go to Step 4. 1. Memory address map is a pictorial representation of assigned
Step 7 : Final result (or the product) is available in A (higher part) address space for each chip in the system.
and Qn (lower part).
Address bus
CPU
Load multiplicand in B multiplier in Q 16-11 10 9 8 7-1 RD WR Data bus
Initialize CR by no. of bits
Clear A and Qn + 1
Decoder
3 2 1 0
10 Is LS 01 CS1
A=A–B bit of Q and A=A+B CS2
Q n + 1 are 128 × 8
RD Data
RAM 1
WR
00 AD7
Perform 1-bit arithmetic right
CS1
shift A, Qn and Qn + 1
CS2
then decrement CR by 1 128 × 8
RD Data
RAM 2
WR
no is AD7
CR = 0
? CS1
yes CS2
128 × 8
Final result in A and Q RD Data
RAM 3
WR
Fig. 4. 2’s Complement multiplication. AD7
Example : Both negative (– 5 × – 4) CS1
Multiplicand (B) 1 0 1 1 (– 5) Multiplier (Q) 1 1 0 0 (– 4) CS2
128 × 8
RD Data
RAM 4
A Qn Qn + 1 Operation CR WR
AD7
0000 1100 0 Initial 4
0000 0110 0 Shift right 3 CS1
CS2
0000 0011 0 Shift right 2 1-7 128 × 8
8 Data
AD9 ROM
0101 0011 0 AA–B 1 9
0010 1001 1 Shift right
Fig. 5.
0001 0100 1 Shift right 0
2. To demonstrate with a particular example, assume that a computer
Result : 0001 0100 = + 20 system needs 512 bytes of RAM and 512 bytes of ROM.
Computer Organization & Architecture SP–13 B (CS/IT-Sem-3) SP–14 B (CS/IT-Sem-3) Solved Paper (2016-17)
3. The RAM and ROM chips to be used are specified in Fig. 5. The
memory address map for this configuration is shown in Table 1. RAM
4. The component column specifies whether a RAM or a ROM chip is Memory ADDRESS BUS Memory data
used. The hexadecimal address column assigns a range of address MAR DATA BUS MDR register
hexadecimal equivalent addresses for each chip. The address bus register
CPU BUS
lines are listed in the third column.
5. The selection between RAM and ROM is achieved through bus
line 10. The RAMs are selected when the bit in this line is 0, and Accumulator
Instruction IR PC ACC (work register)
the ROM when the bit is 1. register
Table 1 : Memory address map.
Program counter Control ALU Arithmetic
Component Hexadecimal Address
Clock logic unit
Address bus Control lines
10 9 8 7 6 5 4 3 2 1 Fig. 6.
RAM1 0000-007F 0 0 0 × × × × × × × Arrangement of CPU, memory, input/output to work as a
RAM2 0080-00FF 0 0 1 × × × × × × × computer :
RAM3 0100-017F 0 1 0 × × × × × × ×
RAM4 0180-01FF 0 1 1 × × × × × × × Input Central Output
Data Processing Data
ROM 0200-03FF 1 × × × × × × × × × Devices Devices
Unit
6. The × under the address bus lines designate those lines that must
be connected to the address inputs in each chip. Data
7. The RAM chips have 128 bytes and need seven address lines.
8. The ROM chip has 512 bytes and need 9 address lines.
9. It is now necessary to distinguish between four RAM chips by Main/Internal
assigning to each a different address. Main/Internal
Memory
3. a. Draw a block diagram of a computer’s CPU showing all
the basic building blocks such as program counter, Fig. 7.
accumulator, address and data registers, instruction
a. Input unit : This unit is used for entering data and programs into
register, control unit etc., and describe how such an
the computer system by the user for processing.
arrangement can work as a computer, if connected
b. Storage unit : The storage unit is used for storing data and
properly to memory, input / output etc.
instructions before and after processing.
Ans. Block diagram of computer’s CPU :
c. Output unit : The output unit is used for storing the result as
A computer performs five major operations. These are :
output produced by the computer after processing.
1. It accepts data or instructions as input.
d. Processing unit : The task of performing operations like
2. It stores data and instruction.
arithmetic and logical operations is called processing.
3. It processes data as per the instructions.
The Central Processing Unit (CPU) takes data and instructions
4. It controls all operations inside a computer.
from the storage unit and makes all sorts of calculations based on
5. It gives results in the form of output.
the instructions given and the type of data provided. It is then sent
back to the storage unit.
Computer Organization & Architecture SP–15 B (CS/IT-Sem-3) SP–16 B (CS/IT-Sem-3) Solved Paper (2016-17)
4. The circuit receives the four bits from A0 through A3 adds one to it, 2. A table-lookup procedure is a search of table entries to determine
and generates the incremented output in S0 through S3. whether a specific item matches one of the items stored in the
5. The output carry C4 will be 1 only after incrementing binary 1111. table.
This also causes outputs S0 through S3 to go to 0. 3. The assembler uses four tables.
6. This micro-operation is easily implemented with a binary counter. 4. Any symbol that is encountered in the program must be available
A3 A2 A1 A0 1 as an entry in one of these tables; otherwise, the symbol cannot be
interpreted.
Second pass
x y x y x y x y
HA HA HA HA LC 0
C S C S C S C S
6. The entries of the pseudo instruction table are the four symbols 2. A direct address in instruction needs two reference to memory :
ORG, END, DEC, and HEX. a. Read instruction
7. Each entry refers the assembler to a subroutine that processes b. Read operand
the pseudo instruction when encountered in the program. ii. Displacement addressing :
8. The MRI table contains the seven symbols of the memory- 1. A very powerful mode of addressing combines the capabilities of
reference instructions and their 3-bit operation code equivalent. direct addressing and register indirect addressing.
9. The non-MRI table contains the symbols for the 18 register-
2. It is known by a variety of names depending upon the content of
reference and input-output instructions and their 16-bit binary
its use but the basic mechanism is the same.
code equivalent.
10. The assembler searches these tables to find the symbol that it is 3. Displacement addressing requires that the instruction have two
currently processing in order to determine its binary value. address fields, at least one of which is explicit.
4. The value contained in one address field (value = A) is used directly.
8. Explain : 5. The other address field or an implicit reference based on opcode,
i. Vector processing refers to a register whose contents are added to A to produce the
ii. Vector operations effective address.
Explain how matrix multiplication is carried out on a Instruction
computer supporting vector computations. R A
Ans. This question is out of syllabus since session 2018-19. Memory
Instruction Instruction
R R A
Memory
Memory
Operand
Operand Registers
Registers
Fig. 17. Indexed.
Fig. 14. Register indirect.
v. Implied mode : 11. What is a memory stack ? Explain its role in managing
1. In this mode, the operands are specified implicitly in the definition subroutines with the help of neat diagrams.
of the instruction. Ans. Memory stack : Memory stack is a series of memory spaces that
2. All register reference instructions that use an accumulator are is used in the processes that is done by processor and is temporarily
implied mode instructions. stored in registers.
3. Zero address instructions in a stack-organized computer are implied Role in managing subroutines :
mode instruction since the operands are implied to be on top of the 1. The stack supports program execution by maintaining automatic
stack. It is also known as stack addressing mode. process-state data.
Instruction 2. If the main routine of a program, for example, invokes function a
Implicit ( ), which in turn invokes function b ( ), function b ( ) will eventually
return control to function a ( ), which in turn will return control to
the main ( ) function as shown in Fig. 18.
3. To return control to the proper location, the sequence of return
Top of stack register
addresses must be stored.
Fig. 15. Implied mode. 4. A stack is well suited for maintaining this information because it
vi. Immediate mode : is a dynamic data structure that can support any level of nesting
1. In this mode, the operand is specified in the instruction itself. within memory constraints.
2. The operand field contains the actual operand to be used in b ( ) { ... }
conjunction with the operation specified in the instruction. a() {
Instruction b();
Operand }
main ( ) {
Fig. 16. Immediate mode.
a();
vii. Indexed : }
1. The effective address of the operand is generated by adding a Fig. 18. Stack management.
constant value to the contents of a register. 5. When a subroutine is called, the address of the next instruction to
2. The register used may be either a special register for this purpose execute in the calling routine is pushed onto the stack.
or more commonly, it may be any one of a set of general purpose 6. When the subroutine returns, this return address is popped from
registers in the CPU. the stack, and program execution jumps to the specified location
3. It is referred to as an index register. We indicate the index mode as shown in Fig. 19.
symbolically as, X(R)
where X denotes a constant and R is the name of register involved.
4. The effective address of the operand is given by, EA = X + [R]
5. In the process of generating the effective address, the contents of
the index register are not changed.
Computer Organization & Architecture SP–23 B (CS/IT-Sem-3) SP–24 B (CS/IT-Sem-3) Solved Paper (2016-17)
Address
Low memory FULL = 1
when stack is full
63
Unallocated EMPTY FULL
Stack frame
EMPTY = 1
for b ( ) when stack is empty
4. After the subroutine has been executed, a branch is made back to 5. Example of register transfer : T0 : AR PC (Activities in T0 will be,
the main program. Content of PC placed on bus, S2S1S0 = 010, LD of AR is active,
5. A branch can be made to the subroutine from any part of the main transfer occurs at the end of positive transition, T0 is .inactive, T1
program. gets active).
6. Because branching to a subroutine and returning to the main 6. Timing control is generated by 4-bit sequence counter and 4 × 16
program is such a common operation, all computers provide special decoder. The SC can be incremented or cleared. T0, T1, T2, T3, T4,
instructions to facilitate subroutine entry and return. T0, .........
For example :
14. Draw the block diagram of control unit of basic computer. Assume : At time T4, SC is cleared to 0 if decoder output D3 is
Explain in detail with control timing diagrams. active.
Ans. D3T4 : SC 0
1. The control unit consists of 2 decoders, 1 sequence counter, number Timing diagram :
of control logic gates. T 0 T1 T2 T3 T 4 T0
2. The instruction in IR is divide into 3 parts : 15th bit to a flip-flop (FF) Clock
called I, Operation code, and bits 0 to 11. The Op-code is decoded T0
using 3*8 decoder (D0 to D7). Bits 0 to 11 are applied to the control T1
logic gates. The output of a 4-bit sequence counter are decoded into T2
16 timing signals (T0 to T15). T3
3. The SC responds to the positive transition of the clock. Initially
CLR I/ P is active, in 1st positive transition SC = 0, timing signal T0
D3
is active as the output of the decoder. This in turn triggers those
CLR SC
registers whose control inputs are connected to T0. SC is incremented
and the timing signals T0, T1, T2, T3 .... are created. This continues Fig. 22.
unless SC is cleared. We can clear the SC with decoder output D3
active, denoted as : 15. List and explain different types of shift micro-operation.
D3T4 : SC 0 Ans. Shift micro-operation :
Instruction Register (IR) 1. Shift micro-operations in computer architecture are those which
15 14 13 12 11 – 0 are used in serial shifting of data present in a register.
Other inputs 2. Shift micro-operations move or shift data in a register bitwise that
3 × 8 Decoder is, one bit at a time either left or right from its original position.
7 6 5 4 3 21 0 D0 Control List of different types of shift micro-operation :
I D7 Control outputs
a. Arithmetic shift micro-operation :
logic
T15 i. Arithmetic shift operation shifts signed (positive or negative)
gates
T0 binarynumbers either left or right by multiplying or dividing by 2.
ii. For arithmetic shift left micro-operation, the value in the register is
15 14 2 1 0 multiplied by 2 and whereas for arithmetic shift right micro-
4 × 16 operation, the value in the register is divided by 2.
Decoder
iii. In RTL (Register Transfer Language), we can represent this
arithmetic shift micro-operations as
4-bit Increment (INR) R ashl R (arithmetic shift left R (register))
Sequence Counter (SC) Clear (CLR) R ashr R (arithmetic shift right R (register))
Clock iv. Fig. 23 showing arithmetic shift left operation is as follows :
Fig. 21. Block diagram of control unit.
4. Output D3 from the operation decoder becomes active at the end of
T2. When T4 is active, the output of AND gate that implements the
control function D3T4 becomes active. This signal is applied to CLR
input of SC.
Computer Organization & Architecture SP–27 B (CS/IT-Sem-3) SP–28 B (CS/IT-Sem-3) Solved Paper (2016-17)
Fig. 28.
1 0 1 0 0 1 1 1 0 before
0 1 0 0 1 1 1 0 after
Fig. 25.
v. Fig. 26 showing the logical shift right is as follows :
Shift right logical
0 1 0 1 0 0 1 1 1 before
0 1 0 1 0 0 1 1 after
Fig. 26.
Computer Organization & Architecture SP–1 B (CS/IT-Sem-3) SP–2 B (CS/IT-Sem-3) Solved Paper (2017-18)
Time : 3 Hours Max. Marks : 70 e. What do you mean by locality of reference ? Explain with
suitable example.
Note : 1. Attempt all Sections. If require any missing data; then choose
suitably.
SECTION-C
SECTION – A 3. Attempt any one part of the following : (7 × 1 = 7)
a. Differentiate between RISC & CISC based microprocessor.
1. Attempt all questions in brief. (2 × 7 = 14)
a. Draw the circuit diagram of D flip-flop. b. Explain booths multiplication algorithm in detail.
b. Write the difference between RAM & ROM. 4. Attempt any one part of the following : (7 × 1 = 7)
a. Draw the data path of 2’s compliment multiplier. Give the
c. Write short note on pipelining process. Robertson multiplication algorithm for 2’s compliment
fractions. Also illustrate the algorithm for 2’s compliment
d. Write the difference between serial and parallel fraction by a suitable example.
communication.
b. Describe sequential Arithmetic & Logic Unit (ALU) using
e. Perform the following operation on signed numbers using proper diagram.
2’s compliment method : (56)10 + (– 27)10.
5. Attempt any one part of the following : (7 × 1 = 7)
f. Write speed up performance laws. a. Give the structure of commercial 8M × 8 bit DRAM chip.
g. Differentiate between horizontal and vertical b. Explain the working of DMA controller with help of suitable
microprogramming. diagrams.
S E M Double precision
Fig. 2. 1 bit 11 bits 52 bits
Where S is significant (mantissa) digits, E is exponent, B is scaling
b. i. Draw the block diagram for a small accumulator based CPU. factor, which is 2 for binary number, 10 for decimal number.
ii. How floating point numbers are represented in computer,
also give IEEE 754 standard 32-bit floating point number c. Draw the data path of sequential n-bit binary divider. Give
format. the non-restoring division algorithm for unsigned integers.
Computer Organization & Architecture SP–9 B (CS/IT-Sem-3) SP–10 B (CS/IT-Sem-3) Solved Paper (2017-18)
Also illustrate algorithm for unsigned integer with a Dividend = 1010, Divisor = 0011
suitable example. A Register Q Register
Ans. Datapath of sequential n-bit binary divider : Initially 0 0 0 0 0 1 0 1 0 Dividend
A 8 B 8 Shift 0 0 0 0 1 0 1 0
Subtract 1 1 1 0 1
‘0’ 8 First Cycle
reset D set Q0 1 1 1 1 0 0 1 0 0
reset enable_b
reset D Id_shift_b zero zero
enable_a enable_a Isb_b Isb_b
Id_shift_a clock Q
Id_shift_a Shift 1 1 1 0 0 1 0
clock clock Q 0
16 Add 0 0 0 1 1
Second Cycle
enable_b
Id_shift_b 16 set Q0 1 1 1 1 1 1 0 0 0
a b
Psel +
LdP ‘0’
Shift 1 1 1 1 1 0 0 0
16 16 0 0 0 1 1
Psel Add
1 0 Third Cycle
0 0 0 1 0 0 0 0 1
16 set Q0
p_in
reset
IdP Shift 0 0 1 0 0 0 0 1
clock P Subtract 1 1 1 0 1
Fourth Cycle
0 0 0 0 1 0 0 1 1
16 R
Fig. 4. Remainder Quotient
Fig. 5. A non-restoring division example.
Algorithm for non-restoring division :
In given example after 4 cycles register A is positive and hence step
Restoring division operation : 3 is not required.
Step 1 : Shift A and Q left one binary position.
Step 2 : Subtract divisor from A and place answer back in A(A A d. What is micro programmed control unit ? Give the basic
– B). structure of micro programmed control unit. Also discuss
the microinstruction format and the control unit
Step 3 : If the sign bit of A is 1, set Q0 to 0 and add divisor back to A organization for a typical micro programmed controllers
(that is, restore A); otherwise, set Q0 to 1. using suitable diagram.
Step 4 : Repeat steps 1, 2 and 3 upto n times. Ans. Micro-programmed control unit and its structure :
Non-restoring division operation : 1. Micro-programmed control is a method of control unit design in
which the control signal selection and sequencing information is
Step 1 : If the sign of A is 0, shift A and Q left one bit position and
stored in a ROM or RAM called a Control Memory (CM).
subtract divisor from A; otherwise, shift A and Q left and add divisor
2. The sequence of control signals to be generated by the controller
to A.
can be stored in a special Read Only Memory (ROM) also called
Step 2 : If the sign of A is 0, set Q0 to 1; otherwise, set Q0 to 0. Control Memory (CM).
Step 3 : Repeat steps 1 and 2 for n times. 3. Memory control word is written for each micro-operation, and
these control words are stored in a serial ascending memory
Step 4 : If the sign of A is 1, add divisor to A. Step 4 is required to
location.
leave the proper positive remainder in A at the end of n cycles.
4. The control word is accessed serially (serial access memory) from
For example, consider 4-bit dividend and 2-bit divisor : the control memory.
5. Control words are stored in the ROM permanently.
6. The output of the control memory provides the required control
signals.
Computer Organization & Architecture SP–11 B (CS/IT-Sem-3) SP–12 B (CS/IT-Sem-3) Solved Paper (2017-18)
7. When logic operation is selected (S2 = 1), the carry input must be 2. The CPU responds with its BG line, informing the DMA that its
zero. buses are disabled.
8. This given us the output sum in full adder circuit as 3. The DMA then puts the current value of its address register into
Yi = Ai Bi Ci ( Ci = 0) the address bus, initiates the RD or WR signal, and sends a DMA
Yi = Ai Bi acknowledge to the peripheral device.
4. The direction of transfer depends on the status of the BG line.
5. Attempt any one part of the following : (7 × 1 = 7) a. When BG = 0, the RD and WR are input lines allowing the CPU to
a. Give the structure of commercial 8M × 8 bit DRAM chip. communicate with the internal DMA registers.
Ans. b. When BG = 1, the RD and WR are output lines from the DMA
Data bus DQ1 : DQ8 controller to the random access memory to specify the read or
write operation for the data.
Timing and Internal 8
•••
refreshing control
Interrupt
control logic signals Data buffer Random-access
BG CPU
memory (RAM)
BR
Address
select
RD WR Address Data
DMA acknowledgement
••• DS
RS Direct memory I/O
access (DMA) Peripheral
Column BR device
controller DMA request
address decoder BG
Interrupt
Row Column
address address Fig. 13. DMA transfer in a computer system.
buffer buffer
13 10 5. When the peripheral device receives a DMA acknowledge, it puts a
word in the data bus (for write) or receives a word from the data
RAS CAS WEOE 13 bus (for read).
Control lines 6. Thus, the DMA controls the read or write operations and supplies
Address bus A0 : A12 the address for the memory.
Fig. 12. Structure of a commerical 8M × 8-bit DRAM chip. 7. The peripheral unit can communicate with memory through the
data bus for direct transfer between the two units while the CPU is
b. Explain the working of DMA controller with help of suitable momentarily disabled.
diagrams.
Ans. Working of DMA controller : 6. Attempt any one part of the following : (7 × 1 = 7)
1. When the peripheral device sends a DMA request, the DMA a. What is hardwired control ? List various design methods
controller activates the BR line, informing the CPU to relinquish for hardwired control. Discuss in detail using diagram any
the buses. one of the method for designing GCD processor.
Computer Organization & Architecture SP–19 B (CS/IT-Sem-3) SP–20 B (CS/IT-Sem-3) Solved Paper (2017-18)
Ans. Hardwired control and design methods : 4. The algorithm shown in Fig. 15 has five data manipulation
1. It is a controller as a sequential logic circuit or a finite state machine statements in lines 1, 2, 5, 7, and 10.
that generates a sequence of control signals in response to the 5. There are two conditional tests in lines 3 and 4.
externally supplied instructions. 6. We can conclude that the data path requires two 8-bit registers,
2. The control logic is implemented with gates, flip-flops, decoders, one for variable X, and one for variable Y, and a subtractor.
and other digital circuits. 7. The dedicated data path is shown in Fig. 15.
8. In Fig. 16, we have a 2-to-1 mux for the input of each register
CLK Control step
Clock because for each register, we need to initially load it with an input
counter
number, and subsequently load it with the result from the subtractor.
9. The two control signals, In_X and In_Y, select which of the two
Status flags sources are to be loaded into the registers X and Y respectively.
10. The two control signals, load_X and load_Y, load a value into the
Decoder/ respective register.
IR
Encoder Status flags Input X Input_Y_Y
In X
1 0 1 0
In Y
Control signals
Fig. 14. General block diagramof hardwired control.
Methods to design hardwired control : There are four simplified
Dm Load 8-
and systematic methods for the design of hardwired controllers. Load_X Dm Load 8-
bit register
bit register
1. State table method or one-hot method. Clear X Qm Clear Y
Clear
2. Delay element method. Qm
3. Sequence-counter method.
4. PLA method.
clock
FSM based design of GCD processor :
1. First write algorithms for calculation of GCD, after that data paths Xeq Y Comparat
and control unit is designed for GCD processor. or
Xqt Y (X > Y)
2. In this model, both the FSM and the data path circuits are manually (X = Y)
constructed as separate units.
3. The FSM and the data path are connected together in an enclosing 1 0 1 0
unit using the control and status signals. XY
1. Input X Subtractor
2. Input Y Out
3. While (X! = Y)
4. {
5. IF (X > Y) Out
6. THEN X = X – Y Fig. 16. Datapaths of GCD processor.
7. ELSE Y = Y – X
8. END IF b. How pipeline performance can be measured ? Discuss. Give
9. } a space time diagram for visualizing the pipeline behaviour
10. OUTPUT X for a four stage pipeline.
Ans. Pipeline performance :
Fig. 15. Euclid’s algorithm.
There are following terms which are used to measure a pipeline
performance :
Computer Organization & Architecture SP–21 B (CS/IT-Sem-3) SP–22 B (CS/IT-Sem-3) Solved Paper (2017-18)
d. That is why this memory is also called Content Addressable b. A moving arm disc storage device has the following
Memory (CAM). It allows each block of main memory to be stored specifications :
in the cache. Number of Tracks per recording surface = 200
Disc rotation speed = 2400 revolution/minute
CPU Address Data Address Data Track-storage capacity = 62500 bits
14567 3023 14567 3023 Estimate the average latency and data transfer rate of this
CPU address
device.
(15-bits) 23473 2495 23473 2495
Ans. Disk rotation speed = 2400 rpm
56982 2354 56982 2354
Argument 1
As we know that average latency = × Rotation time
register 31567 0256 31567 0256 2
43222 2400 rotation in one minute so the time for one rotation
3452
14566 7654 1 60 3
= * s= s = 12.5 ms
2 2400 240
Associative cache memory 64232 8009
Track storage capacity = 62500 bits
45614 1984 And in one rotation head cover entire track, so, disk transfer rate
98766 3142 2400
= 62500 * s
11132 9823 60
Fig. 20. Main memory (where 2400/60 is number of rotations per second)
3. Set associative mapping : = 2.5 * 106 bps
a. In set associative mapping, each cache location can have more
than one pair of tag + data items.
b. It combines the best of the direct mapping cache and the more
flexible mapping of the fully associative cache.
c. That is more than one pair of tag and data are residing at the same
location of cache memory. If one cache location is holding two pair
of tag + data items, that is called 2-way set associative mapping.
Main memory Cache memory
Address Data
00 000 5670 Tag Data Index Tag Data
00 5670 000 01 1256
00 666 7523
01 000 1256
00 7523 666 01 5321
03 2771 02 6520
01 666 5321
51 1560 677 41 2560
67 125 7432
77 5423 777 66 4423
77 777 5423
Fig. 21.
Computer Organization & Architecture SP–1 B (CS/IT-Sem-3) SP–2 B (CS/IT-Sem-3) Solved Paper (2018-19)
c. What is the difference between RAM and DRAM ? 3. Attempt any one part of the following : (7 × 1 = 7)
a. Write short notes on :
d. What are the difference between horizontal and vertical i. Instruction pipeline
micro codes ? ii. DMA based data transfer
e. Describe cycle stealing in DMA. b. Explain the difference between vectored and non-vectored
interrupt. Explain stating examples of each.
f. List three types of control signals.
4. Attempt any one part of the following : (7 × 1 = 7)
g. Define the role of MIMD in computer architecture. a. Draw the flowchart of Booth’s algorithm for multiplication
and show the multiplication process using Booth’s
SECTION-B algorithm for (– 7) × (+ 3).
d. What is associative memory ? Explain with the help of a i. How many bits are there in the operation code, the register
block diagram. Also mention the situation in which code part and the address part ?
associative memory can be effective utilized. ii. Draw the instruction word format and indicate the number
Ans. Associative memory : of bits in each part.
1. Associative memory is a memory in which location is accessed by a iii. How many bits are there in the data and address inputs of
field of data word stored in the memory rather than by any address. the memory ?
2. It can be viewed as a random access type memory which in addition Ans.
to having a physically wired-in addressing mechanism also has a. Address : 28 * 210 = 218 = 18 bits
wired-in logic for bit comparison. Register : 64 registers = 26 = 6 bits
3. This logic circuit enables comparison of desired bit positions of all OP code : (Total bit – Indirect bit – Address bit – Register bit)
the words with a specified input key.
= (32 – 1 – 18 – 6) bits = 7 bits
4. This comparison is done simultaneously for all the words.
5. This is also called Content Addressable Memory (CAM). I OP Register Address
Working principle of associative memory : b.
31 30 23 17 0
1. The mask register specifies the key field.
c. Number of bit in address inputs : 18
2. Input data is simultaneously compared with the key field of each
Number of bit in data inputs : 32
word.
3. The select circuit implements two functions : SECTION-C
a. It stores the word location (s) for which match has occurred.
3. Attempt any one part of the following : (7 × 1 = 7)
b. It reads out the word(s) in predetermined order for the match
a. Write short notes on :
position (s).
i. Instruction pipeline
4. Thus, a word stored in the associative memory is a pair (key,
Data). Any subfield of the word can be specified as the key. ii. DMA based data transfer
5. The read or write instruction is preceded by the match instruction Ans.
having the format. i. Instruction pipelining :
Match key, Input data a. The execution of a stream of instructions can be pipelined by
6. The read/write operation can next be performed on each of the overlapping the execution of the current instruction with the
words for which match signal is generated. fetch, decode, and operand fetch of subsequent instructions as
shown in Fig. 2.
Input register
b. This technique is also known as instruction look ahead.
c. Almost all high-performance computers are now equipped with
Mask register instruction-execution pipelines.
Instructions
key
Match 1
Program
Word organized array Select Memory
Select 2 data
of CAM cells circuit
3
Output register
Functional
units
Fig. 1. Organization of an associative memory.
Fig. 2. Instruction pipelining.
Associative memory is effectively utilized when doing a large number
of pattern match and lookup. ii. DMA based data transfer :
1. DMA stands for ‘‘Direct Memory Access’’ and is a method of
e. A computer uses a memory unit with 256 K words of 32 bits transferring data from the computer’s RAM to another part
each. A binary instruction code is stored in one word of of the computer without processing it using the CPU.
memory. The instruction has four parts : an indirect bit, an 2. While most data that is input or output from our computer is
operation code, a register code part to specific one of 64 processed by the CPU, some data does not require processing,
register and an address part. or can be processed by another device.
Computer Organization & Architecture SP–9 B (CS/IT-Sem-3) SP–10 B (CS/IT-Sem-3) Solved Paper (2018-19)
3. DMA can save processing time and is a more efficient way to Ans. Flowchart of Booth’s algorithm for multiplication :
move data from the computer's memory to other devices. Load multiplicand in B multiplier in Q
4. In order for devices to use direct memory access, they must Initialize CR by no. of bits
be assigned to a DMA channel. Each type of port on a computer Clear A and Qn + 1
has a set of DMA channels that can be assigned to each
connected device.
5. For example, a PCI controller and a hard drive controller 10 Is LS 01
each have their own set of DMA channels. A=A–B bit of Q and A=A+B
Block diagram for DMA : Q n + 1 are
Address bus, READ/ and WRITE/
Micro 00
processor RAM
Data bus
Perform 1-bit arithmetic right
shift A, Qn and Qn + 1
BUSREQ BUSACK
then decrement CR by 1
DMA DMAACK I/O
DMAREQ
no is
Fig. 3. CR = 0
?
yes
b. Explain the difference between vectored and non-vectored
interrupt. Explain stating examples of each. Final result in A and Q
Ans.
Fig. 4. 2’s Complement multiplication.
S. No. Vectored interrupt Non-vectored interrupt Multiplication : Multiply (– 7) × (+ 3)
1. Vectored interrupt are those Non-vectored interrupt are Convert (–7) into 2’s complement form :
interrupt that generates the those in which vector address is +7 = 0111
interrupt request, identifies not pre-defined. 1’s complement of (+7) = 1000
itself directly to the processor. adding 1 +1
—————
2’s complement of (+ 7) = 1001
2. Vector interrupt have fixed Non-vectored interrupt do not ––––––––—
memory location for transfer have fixed memory location for (+3) = 0011
of control for normal execution. transfer of control for normal A Qn Qn+1 B = 1001 SC
execution.
B + 1 = 0111
3. Vecto re d inte rrupt has A non-vectored interrupt do not 0000 0011 0 initial values 100
memory address. have memory address.
0111 sub B or
4. The vectored interrupt allows When a non-vectored interrupt 0111 add 0111 to A
the CPU to be able to know receive d, it jump into the
what ISR to carry o ut in pro gram counter to fixe d 0011 1001 1 Ashr 011
software. address in hardware. AQn Qn+1
5. Response time is low. Response time is high. 0001 1100 1 Ashr AQn Qn+1 010
F1 E1 F2 E2 F3 E3 Branch address
Next address
Fig. 5. Sequential execution.
generation circuit
Opcode
5. Now consider a computer that has two separate hardware units, (micro-program R
one for fetching instructions and another for executing them, as sequencer) External condition
sho wn in
Fig. 6.
Fig. 7. Block diagram of micro-programmed control
6. The instruction fetched by the fetch unit is deposited in an
with micro-program sequencer.
intermediated storage buffer Bi.
7. The results of execution are deposited in the destination location
specified by the instructions. b. Draw a flowchart for adding and subtracting two fixed point
8. For these purposes, we assume that both the source and binary numbers where negative numbers are signed 1’s
destination of the data operated in by the instructions are inside complement presentation.
the block labelled “Execution unit”.
Storage buffer
Instruction fetch unit Bi Execution unit
Ans. Reason for bidirectional read and write control lines : Read
Subtract operation
Add operation and write control lines in a DMA controller is bidirectional because
the microprocessor fetch (read) the data from the memory and
Minuend in A Augend in A write data to the memory.
Subtrahend in B Addend in B
AS
=0 AS BS
=1 =1
AS BS
=0 b. Explain all the phases of instruction cycle.
Ans. Instruction cycle :
AS BS AS BS AS = BS
AS = BS 1. Instruction cycle is a complete process of instruction execution.
2. It is a basic operational process of a computer.
EA A + B + 1 EA A + B 3. It is the process by which a computer retrieves a program
AVF 0 instruction from its memory, determines what actions the
instruction dictates, and carries out those actions.
=0 =1 AVF E
E The instruction cycle is divided into three sub cycles :
A<B A>B
Fetch cycle Decode cycle Execute cycle
0 =0
A A A Fetch Decode Execute
START HALT
A A+1 instruction instruction instruction
AS AS AS 0
Fig. 10.
END
1. Fetch cycle : To fetch an opcode from a memory location following
(result is in A and AS) steps are performed :
i. The program counter places the address of the memory location
Fig. 8. in which the opcode is stored, on the address bus.
ii. The CPU sends the required memory control signals so as to
enable the memory to send the opcode.
6. Attempt any one part of the following : (7 × 1 = 7)
iii. The opcode stored in the memory location is placed on the data
a. Give the block diagram of DMA controller. Why are the read
bus and transferred to the CPU.
and write control lines in a DMA controller bidirectional ?
2. Decode cycle :
Ans. Block diagram of DMA controller :
i. The opcode which is fetched from the memory is placed first of all
Interrupt
Random-access in the Data Register (DR) (data/address buffer in case of Intel
BG CPU memory (RAM) 8085). Thereafter it goes to the Instruction Register (IR).
BR
ii. From the instruction register it goes to the decoder circuitry, which
RD WR Address Data RD WR Address Data is within the CPU.
Read control iii. The decoder circuitry decodes the opcode.
Write control iv. After the opcode is decoded the CPU comes to know what operation
Data bus is to be performed, and then execution begins.
Address bus
3. Execute cycle :
Address i. In this cycle, function of the instruction is performed.
select ii. If the instruction involves arithmetic or logic, ALU is utilized.
RD WR Address Data
DMA acknowledgement
DS 7. Attempt any one part of the following : (7 × 1 = 7)
I/O
RS Direct memory
Peripheral
a. Explain the basic concept of hardwired and software control
access (DMA)
BR
controller device unit with neat diagrams.
DMA request
BG
Ans. Hardwired control :
Interrupt 1. It is a controller as a sequential logic circuit or a finite state machine
Fig. 9. DMA transfer in a computer system. that generates a sequence of control signals in response to the
externally supplied instructions.
Computer Organization & Architecture SP–15 B (CS/IT-Sem-3) SP–16 B (CS/IT-Sem-3) Solved Paper (2018-19)
b. 1 2 3 4 5 6
Control signals S1 X X
Fig. 11. General block diagram of hardwired control. S2 X X
3. A hardwired control requires changes in the wiring among the
S3 X
various components if the design has to be modified or changed.
4. Its input logic signals are transformed into a set of output logic S4 X
signals are called control signals.
5. Each step in this sequence is completed in one clock cycle. S5 X X
6. A counter may be used to keep the track of the control steps.
7. The required control signals are determined by the following For the following reservation table :
information :
i. Calculate the set of the forbidden latencies and collision
a. Contents of the control step counter. vector.
b. Contents of the instruction register.
ii. Draw a state diagram, showing all possible initial sequences
c. Contents of the condition code flags.
(cycles) without a collision in the pipeline.
d. External input signals such as MFC and interrupt request.
Micro-programmed control : iii. Simple Cycles (SC)
1. Micro-programmed control is a method of control unit design in iv. Greedy cycles among simple cycles
which the control signal selection and sequencing information is
v. MAL (Minimum Average Latency)
stored in a ROM or RAM called a Control Memory (CM).
2. The sequence of control signals to be generated by the controller vi. What is the minimum allowed constant cycles ?
can be stored in a special Read Only Memory (ROM) also called vii. Maximum throughput
Control Memory (CM). viii. Throughput if the minimum constant cycle is used.
3. Memory control word is written for each micro-operation, and
these control words are stored in a serial ascending memory Ans.
location. i. The forbidden latencies are 3, 4, and 5 (S1 : 5 ; S2 : 3 ; S3 : 0 ; S4 : 0
4. The control word is accessed serially (serial access memory) from and S5 : 4), so that the collision vector is Cx = 11100 where the
the control memory. permissible latencies are 1 and 2.
5. Control words are stored in the ROM permanently. ii. State diagram can be obtained by tracing each Cx shift as followed :
6. The output of the control memory provides the required control
signals.
7. If the control memory is sequentially accessed by incrementing
control memory location, then the sequence of control signals
stored in successive word of ROM can be generated.
Computer Organization & Architecture SP–17 B (CS/IT-Sem-3) Computer Organization & Architecture SP–1 B (CS/IT-Sem-3)
SECTION-B
b. Design a 4-bit carry look ahead adder and explain its b. RAM chip 4096 × 8 bits has two enable lines. How many pins
operation with an example. are needed for the integrated circuits package ? Draw a
block diagram and label all input and outputs of the RAM.
c. What is main feature of random access memory ?
i. Draw the timing diagram for a instruction cycle and
explain. 7. Attempt any one part of the following : (10 × 1 = 10)
ii. Give a note on subroutine. a. Write down the difference between isolated I/O and memory
mapped I/O. Also discuss advantages and disadvantages of
d. What do you mean by virtual memory ? Discuss how paging isolated I/O and memory mapped I/O.
helps in implementing virtual memory.
b.
e. What is DMA ? Describe how DMA is used to transfer data i. Discuss the design of a typical input or output interface.
from peripherals. ii. What are interrupts ? How are they handled ?
SECTION-C
3. Attempt any one part of the following : (10 × 1 = 10)
a. Describe in detail the different kinds of addressing modes
with an example.
Secondary
f. What are the types of microinstructions available ?
Program Storage
Input Output
Information Ans. Following types of microinstructions are available :
and Data i. Vertical / horizontal ii. Packed / unpacked
Unit Unit (Results)
Primary iii. Hard / soft microprogramming iv. Direct / indirect encoding
Storage
g. What is SRAM and DRAM ?
Ans. SRAM : Static Random Access Memory is a semiconductor memory
in which, the data does not need to be refreshed dynamically.
Control SRAM is volatile in nature. It consumes more power.
Unit DRAM : Dynamic RAM is a form of random access memory. DRAM
Indicates flow of
instructions and data uses a capacitor to store each bit of data, and the level of charge on
Arithmetic each capacitor determines whether that bit is a logical 1 or 0.
Logic Unit Indicates the control
exercised by the h. What is the difference between 2D and 2 1/2 D memory
control unit organization ?
Central Processing Unit (CPU)
Ans.
Fig. 1. Functional unit of digital computer.
S. No. 2D memory organizations 21/2 D memory organizations
c. Perform the 2’s complement subtraction of smaller number 1. In 2D organization, In 21/2 D organization, hardware
(101011) from larger number (111001). hardware is fixed. changes.
Ans. (111001) – (101011)
Step 1 : 1’s complement of 101011 = 0 1 0 1 0 0 2. 2D organization requires 21/2 D organization requires less
Step 2 : 2’s complement of 101011 = 0 1 0 1 0 0 more number of gates. number of gates.
+1
3. Erro r co rre ctio n is no t In 2 1/2 D organization, error
010101 possible in the 2D correction is easy.
Step 3 : Adding minuend and 2’s complement obtained in Step 2. organization.
111001
+ 010101 i. What is I/O control method ?
Carry Ans. Usually microprocessor controls the process of data transfer
1 001110
between the microprocessor and the peripherals. However,
The sum produce a carry because minuend > subtrahend. So, discard sometimes peripherals also controls the data transfer. During
carry and write the remaining bits. such time I/O control methods are used. The I/O control methods
(1 1 1 0 0 1) – (101011) = 0 0 1 1 1 0
SP–6 B (CS/IT-Sem-3) Solved Paper (2019-20) Computer Organization & Architecture SP–7 B (CS/IT-Sem-3)
A * T3 / F * (G + H) T3 = BT2 +
SECTION-B
A * T3 / F * GH
T4
2. Attempt any three of the following : (10 × 3 = 30)
a. Convert the following arithmetic expressions from infix to A * T3 / F * T4 T4 = GH +
reverse polish notation :
A * T3 F / * T4
i. A*B + C*D + E*F
T5
ii. A*[B + C*CD + E]/F*(G + H)
Ans.
A * T5 * T4 T5 = T3 F/
i. A*B + C*D + E*F A T5 * T4
AB*
+ C*D + E*F
T6
X T6 * T4 T6 = AT5 *
X + C*D + E*F X = AB*
T6 T4 *
X + CD* T7 = T6 T4*
+ E*F T7
Y
T7
X + Y + E*F Y = CD*
on putting value of T7
X + Y + EF*
= T6 T4 *
Z = AT5 * GH + *
XY +Z Z = EF* = A T3 F/ * GH + *
= A BT2 + F / * GH + *
Z
= A BCT1 * + F / * GH + *
XY Z = A BCDE + * + F / GH + *
P = A BCDE + * F / GH + *
P+Z P = XY +
b. Design a 4-bit carry look ahead adder and explain its
PZ Q = PZ +
operation with an example.
Q
Ans.
On putting value 1. A Carry Look Ahead adder (CLA) or fast adder is a type of adder
= PZ + used in digital logic.
= XY + Z + 2. A carry look ahead adder improves speed by reducing the amount
= XY + EF*+ of time required to determine carry bits.
= XCD* + EF * + 3. The carry look ahead adder calculates one or more carry bits before
= AB * CD * + EF * + the sum, which reduces the waiting time to calculate the result of
ii. A * [B + C * CD + E] / F * (G + H) the larger-value bits of the adder.
Assume D + E in the bracket then expression becomes 4. Carry look ahead depends on two things :
A * [B + C * (D + E)] / F * (G + H)
SP–8 B (CS/IT-Sem-3) Solved Paper (2019-20) Computer Organization & Architecture SP–9 B (CS/IT-Sem-3)
Pi Ci+ Gi P0
Ci Ci + 1 G0 S0
Fig. 2.
C0 C0
9. Consider the circuit of the full adder shown in Fig. 3. If we define
two new binary variables,
Fig. 3. A 4-bit look-ahead carry adder.
Pi = Ai Bi , Gi = AiBi
c.
10. The output sum and carry can respectively be expressed as i. Draw the timing diagram for a instruction cycle and
Si = Pi Ci , Ci+1 = Gi + PiCi explain.
11. Gi is called a carry generate, and it produces a carry of 1 when both ii. Give a note on subroutine.
Ai and Bi are 1, regardless of the input carry Ci. Pi is called a carry Ans.
propagate, because it determines whether a carry into stage i will i. Let consider the instruction cycle for instruction STAX rp.
propagate into stage i + 1. This instruction stores the contents of A register in memory whose
address is specified by register pair (BC or DE).
C0 = input carry
It requires the following machine cycles :
i=0 C1 = G0 + P0C0 1. Opcode fetch : Program counter places the memory address on
i=1 C2 = G1 + P1C1 = G1 + P1(G0 + P0C0) low order and high order address bus. This machine cycle is
required for reading the opcode of STAX rp (e.g. 0211 for STAX B)
= G1 + P1G0 + P0P1C0
into the microprocessor and decode it.
i=2 C3 = G2 + P2C2 = G2 + P2G1 + P2P1G0 + P2P1P0C0 2. Memory write : Higher order address is obtained from higher
i=3 C4 = G3 + P3C3 order register and lower address is obtained from lower order
= G3 + P3(G2 + P2G1 + P2P1G0 + P3P2P1P0C0) register of the specified register pair. The contents of the
accumulator are stored into the addressed memory location. Thus
memory write machine cycle is required for writing the data from
the microprocessor (A register) to the addressed memory location.
SP–10 B (CS/IT-Sem-3) Solved Paper (2019-20) Computer Organization & Architecture SP–11 B (CS/IT-Sem-3)
Block diagram for DMA : b. When BG = 1, the RD and WR are output lines from the DMA
Address bus, READ/ and WRITE/ controller to the random access memory to specify the read or
Micro write operation for the data.
processor RAM
Data bus 5. When the peripheral device receives a DMA acknowledge, it puts a
word in the data bus (for write) or receives a word from the data
bus (for read).
BUSREQ BUSACK 6. Thus, the DMA controls the read or write operations and supplies
the address for the memory.
DMA DMAACK I/O 7. The peripheral unit can communicate with memory through the
DMAREQ data bus for direct transfer between the two units while the CPU is
momentarily disabled.
Fig. 5.
SECTION-C
Working of DMA controller :
1. When the peripheral device sends a DMA request, the DMA 3. Attempt any one part of the following : (10 × 1 = 10)
controller activates the BR line, informing the CPU to relinquish a. Describe in detail the different kinds of addressing modes
the buses. with an example.
2. The CPU responds with its BG line, informing the DMA that its Ans.
buses are disabled. i. Direct :
1. A very simple form of addressing is direct addressing, in which
Interrupt
the address field contain the effective address of the operand :
BG CPU
Random-access EA = A
memory (RAM)
BR
where, EA = Actual (effective) address of the location
containing the referenced operand.
RD WR Address Data RD WR Address Data
A = Contents of the address field in the instruction.
Instruction
Read control
Write control Memory
Data bus
Address bus
Operand
Address
select
RD WR Address Data
DMA acknowledgement Fig. 7. Direct.
DS
RS I/O 2. A direct address in instruction needs two reference to
Direct memory
BR access (DMA) Peripheral memory :
device
BG
controller DMA request a. Read instruction
Interrupt b. Read operand
ii. Displacement addressing :
1. A very powerful mode of addressing combines the capabilities
Fig. 6. DMA transfer in a computer system.
of direct addressing and register indirect addressing.
2. It is known by a variety of names depending upon the content
3. The DMA then puts the current value of its address register into of its use but the basic mechanism is the same.
the address bus, initiates the RD or WR signal, and sends a DMA 3. Displacement addressing requires that the instruction have
acknowledge to the peripheral device. two address fields, at least one of which is explicit.
4. The direction of transfer depends on the status of the BG line : 4. The value contained in one address field (value = A) is used
a. When BG = 0, the RD and WR are input lines allowing the directly.
CPU to communicate with the internal DMA registers.
SP–14 B (CS/IT-Sem-3) Solved Paper (2019-20) Computer Organization & Architecture SP–15 B (CS/IT-Sem-3)
5. The other address field or an implicit reference based on 2. All register reference instructions that use an accumulator
opcode, refers to a register whose contents are added to A to are implied mode instructions.
produce the effective address. 3. Zero address instructions in a stack-organized computer are
Instruction implied mode instruction since the operands are implied to be
on top of the stack. It is also known as stack addressing mode.
R A
Memory Instruction
Implicit
Operand
Registers Operand
Registers
Fig. 9. Register indirect.
v. Implied mode :
Fig. 12. Indexed.
1. In this mode, the operands are specified implicitly in the
definition of the instruction.
SP–16 B (CS/IT-Sem-3) Solved Paper (2019-20) Computer Organization & Architecture SP–17 B (CS/IT-Sem-3)
Example : 4. Items may only be added or deleted from the top of the stack.
Address Memory 5. A stack is also known as a pushdown list or a Last-In-First-Out
200
(LIFO) list.
PC = 200 Load to AC Mode
i. Organization of register stack :
201 Address = 500 Consider the organization of a 64-word register stack as illustrated
R1 – 400 202 Next instruction in Fig. 14.
Address
FULL = 1
XR = 100 when stack is full
63
399 450
EMPTY FULL
AC 400 700
EMPTY = 1
500 800 when stack is empty
PQR 3
Stack pointer (SP) XYZ 2
600 900 (consists of 6 bits)
ABCD 1
0
702 325 Holds the data to be pushed Data
onto stack or that is popped Register
off from the stack (DR)
800 300
Fig. 14. Block diagram of 64-word stack.
Fig. 13.
The four separate registers used in the organization are :
1. Stack Pointer register (SP) : It contains a value in binary each
Addressing Effective Content of 6 bits, which is the address of the top of the stack. Here, the
Mode Address of AC stack pointer SP contains 6 bits and SP cannot contain a value
Direct address 500 800 greater than 111111 i.e., value 63.
2. FULL register : It can store 1 bit information. It is set to 1 when
Immediate operand 201 500 the stack is full.
Indirect address 800 300 3. EMPTY register : It can store 1 bit information. It is set to 1
when stack is empty.
Indexed address 600 900 4. Data Register (DR) : It holds the data to be written into or to be
Implied – 400 read from the stack.
ii. Memory stack : Memory stack is a series of memory spaces that
Register indirect 400 700 is used in the processes that is done by processor and is temporarily
stored in registers.
b. Discuss stack organization. Explain the following in Role in managing subroutines :
details : 1. The stack supports program execution by maintaining automatic
i. Register stack process-state data.
ii. Memory stack 2. If the main routine of a program, for example, invokes function a
Ans. ( ), which in turn invokes function b ( ), function b ( ) will eventually
1. A stack is an ordered set of elements in which only one element return control to function a ( ), which in turn will return control to
can be accessed at a time. the main ( ) function as shown in Fig. 15.
2. The point of access is called the top of the stack. 3. To return control to the proper location, the sequence of return
3. The number of elements in the stack or length of the stack is addresses must be stored.
variable.
SP–18 B (CS/IT-Sem-3) Solved Paper (2019-20) Computer Organization & Architecture SP–19 B (CS/IT-Sem-3)
4. Attempt any one part of the following : (10 × 1 = 10) 0 01011101 000001000110............0
a. Represent the following decimal number in IEEE standard
Fig. 17.
floating-point format in a single precision method (32-bit)
representation method :
SP–20 B (CS/IT-Sem-3) Solved Paper (2019-20) Computer Organization & Architecture SP–21 B (CS/IT-Sem-3)
Step 3 : Representing the number in single precision. Result = 00001100 11101111 ( + 33 11)
For a given number
S = 1 (given number is negative number) 5. Attempt any one part of the following : (10 × 1 = 10)
E=8 a. What is parallelism and pipelining in computer
M = 00110011001 architecture ?
Bias of single precision format is = 127
Ans. Parallelism in computer architecture :
E = 127 + E = 127 + 8 1. Executing two or more operations at the same time is known as
= (135)10 parallelism.
= (1000 0111)2 2. The purpose of parallel processing (parallelism) is to speed up the
Number in single precision format computer processing capability i.e., it increases the computational
1 bit 8 bits 23 bits speed.
3. It also increases throughput, i.e., amount of processing that can be
S E M
accomplished during a given interval of time.
4. Improves the performance of the computer for a given clock speed.
0 10000111 00110011001..................0 5. Two or more ALUs in CPU can work concurrently to increase
throughput. The system may have two or more processors operating
concurrently.
b. Using Booth’s algorithm perform the multiplication on the
Pipelining :
following 8-bit unsigned integer 10110011 * 11010101.
1. Pipelining is a technique of decomposing a sequential process into
sub-operations, with each sub-process being executed in a special
dedicated segment that operates concurrently with all other
segments.
SP–22 B (CS/IT-Sem-3) Solved Paper (2019-20) Computer Organization & Architecture SP–23 B (CS/IT-Sem-3)
2. The processor executes a program by fetching and executing 4. The micro-instruction contains a control word that specifies one or
instructions, one after the other. more micro-operations for the data processor. Once these operations
3. Let Fi and Ei refer to the fetch and execute steps for instruction Ii. are executed, the control must determine the next address.
4. Execution of a program consists of a sequence of fetch and execute 5. The location of the next micro-instruction may be the one next in
steps as shows is Fig. 18. sequence, or it may be located somewhere else in the control
Instruction Instruction Instruction memory.
I1 I2 I3 6. While the micro-operations are being executed, the next address is
computed in the next address generator circuit and then transferred
F1 E1 F2 E2 F3 E3 into the control address register to read the next micro-instruction.
7. Thus a micro-instruction contains bits for initiating micro-operations
Fig. 18. Sequential execution. in the data processor part and bits that determine the address
5. Now consider a computer that has two separate hardware units, sequence for the control memory.
one for fetching instructions and another for executing them, as 8. The next address generator is sometimes called a micro-program
sho wn in sequencer, as it determines the address sequence that is read from
Fig. 19. control memory.
6. The instruction fetched by the fetch unit is deposited in an 9. Typical functions of a micro-program sequencer are incrementing
intermediated storage buffer Bi. the control address register by one, loading into the control address
7. The results of execution are deposited in the destination location register an address from control memory, transferring an external
specified by the instructions. address, or loading an initial address to start the control operations.
8. For these purposes, we assume that both the source and 10. The control data register holds the present micro-instruction while
destination of the data operated in by the instructions are inside the next address is computed and read from memory.
the block labelled “Execution unit”. 6. Attempt any one part of the following : (10 × 1 = 10)
Storage buffer a. Discuss the different mapping techniques used in cache
Instruction fetch unit Bi Execution unit memories and their relative merits and demerits.
Ans. Cache mapping :
Fig. 19. Hardware organization. 1. Cache mapping is the method by which the contents of main memory
are brought into the cache and referenced by the CPU. The mapping
9. The computer is controlled by a clock whose period is such that method used directly affects the performance of the entire computer
the fetch and execute steps of any instruction can be completed in
system.
one clock cycle. 2. Mapping is a process to discuss possible methods for specifying
where memory blocks are placed in the cache. Mapping function
b. Explain the organization of microprogrammed control unit dictates how the cache is organized.
in detail.
Types of mapping :
Ans. Organization of micro-programmed control unit : 1. Direct mapping :
1. The general configuration of a micro-programmed control unit is
a. The direct mapping technique is simple and inexpensive to
demonstrated in the block diagram of Fig. 20. implement.
2. The control memory is assumed to be a ROM, within which all 6 bits 9 bits
control information is permanently stored. Tag Index
External Control Control Control Control
input Next-address
address memory data unit
generator
register (ROM) register
00 000 32K × 12 000 512 × 12
Next address information
Octal Octal
Main memory address Cache memory
address
Fig. 20. Micro-programmed control organization.
Address = 15 bits Address = 9 bits
77 777 Data = 12 bits 777 Data = 12 bits
3. The control memory address register specifies the address of the
micro-instruction, and the control data register holds the micro-
Fig. 21. Functional unit of digital computer.
instruction read from memory.
SP–24 B (CS/IT-Sem-3) Solved Paper (2019-20) Computer Organization & Architecture SP–25 B (CS/IT-Sem-3)
00 666 7523 7. Attempt any one part of the following : (10 × 1 = 10)
01 000 1256 a. Write down the difference between isolated I/O and memory
00 7523 666 01 5321
mapped I/O. Also discuss advantages and disadvantages of
03 2771 02 6520 isolated I/O and memory mapped I/O.
01 666 5321
Ans. Difference between isolated I/O and memory mapped I/O :
51 1560 677 41 2560
67 125 7432 S. No. Isolated I/O Memory mapped I/O
77 5423 777 66 4423 1. Isolated I/O uses separate Memo ry mapped I/O uses
77 777 5423 memory space. memory from the main memory.
2. Limited instructions can be Any instructio n which
Fig. 24. used. Those are IN, OUT, INS, references to memory can be
OUTS. used.
3. The addresses for isolated I/O Memory mapped I/O devices are
b. RAM chip 4096 × 8 bits has two enable lines. How many pins devices are called ports. treated as memory locations on
are needed for the integrated circuits package ? Draw a the memory map.
block diagram and label all input and outputs of the RAM. 4. Efficient I/O operations due to Inefficient I/O operations due to
What is main feature of random access memory ? separate bus. single bus fo r data and
Ans. Size of RAM chip = 4096 × 8 addressing.
Number of input = 14 pins (214 = 4096)
5. Comparatively larger in size. Smaller in size.
Number of output = 8 pin
Number of chip select = 2 pin 6. Uses complex internal logic. Co mmo n inte rnal lo gic fo r
Number of power pin = 2 pin memory and I/O devices.
Total pins required = 14 + 8 + 2 + 2 = 26 pins 7. Slower operations. Faster operations.