PCC-CSEAI210-T · 4th Semester · CSE

(AI&ML)

Digital Logic &

Computer Design
Complete Unit-wise Notes · All Topics Covered ·
Exam-Ready

Unit I — Digital Logic Unit II — CPU Org

Unit III — ISA & Control

Unit IV — Parallelism & Memory

Basic Principles of Digital

Logic
 Boolean Algebra · Number Systems ·

I Combinational Logic · Sequential Logic

1.1 Boolean Algebra & Logic Gates

WHAT IS BOOLEAN ALGEBRA?

Boolean Algebra is a mathematical system that

deals with variables which can take only two
values: 0 (False) and 1 (True). It forms the
theoretical foundation for all digital circuit
design.

BASIC LAWS & THEOREMS

AND
Law / Theorem OR Form
Form

Identity A·1=A A+0=A

Null A·0=0 A+1=1

Idempotent A·A=A A+A=A

 Complement A · A' = 0 A + A' = 1

Double (A')' = A
Complement

Commutative A·B=B· A+B=B+A

A

Associative (A·B)·C = (A+B)+C = A+

A·(B·C) (B+C)

Distributive A·(B+C) = A+(B·C) =

AB+AC (A+B)·(A+C)

Absorption A·(A+B) = A + A·B = A

A

De Morgan's (A·B)' = A' (A+B)' = A' · B'

+ B'

🎯 E X A M FA V O U R I T E

De Morgan's Theorem is asked almost every

year. Remember: to negate, flip the operator
(AND↔OR) and complement each variable.

BASIC LOGIC GATES

 Truth
Symbol / Key
Gate Table
Expression Property
(A,B → Y)

AND Y=A·B 0,0→0 | Output 1

0,1→0 | only if
1,0→0 | ALL
1,1→1 inputs
are 1

OR Y=A+B 0,0→0 | Output 1

0,1→1 | if ANY
1,0→1 | input is 1
1,1→1

NOT Y = A' 0→1 | Inverts

1→0 input (1
input
only)

NAND Y = (A·B)' 0,0→1 | Universal

0,1→1 | gate –
1,0→1 | can build
1,1→0 any
circuit

NOR Y = (A+B)' 0,0→1 | Universal

0,1→0 | gate
 1,0→0 |
1,1→0

XOR Y=A⊕B 0,0→0 | Output 1

0,1→1 | if inputs
1,0→1 | are
1,1→0 different

XNOR Y = (A⊕B)' 0,0→1 | Output 1

0,1→0 | if inputs
1,0→0 | are same
1,1→1 (equality)

KEY CONCEPT

NAND and NOR are universal gates — every

Boolean function can be implemented using

only NAND gates (or only NOR gates). This is
critical for IC manufacturing economics.

1.2 Number Representations & Computer

Arithmetic

NUMBER SYSTEMS SUMMARY

 Digits
System Base Example
Used

Binary 2 0, 1 (1011)2 =
11

Octal 8 0–7 (13)8 =

11

Decimal 10 0–9 (11)10

Hexadecimal 16 0–9, (B)16 =

A–F 11

SIGNED NUMBER REPRESENTATIONS

Sign-Magnitude: MSB = sign bit (0=+, 1=−).

For +5 in 4-bit: 0101 . For −5: 1101 . Two
representations of zero (+0, −0).

1's Complement: Negate by flipping all bits.

−5 = flip(0101) = 1010 . Still two zeros.

2's Complement: Negate by flipping all bits

and adding 1. −5 = 1010+1 = 1011 . Only
one zero. Used in all modern computers.

SHORTCUT – 2'S COMPLEMENT

 Start from the right. Copy bits up to and
including the first '1'. Flip all remaining bits to
the left.
Example: 0110100 → copy "100" → flip rest →
1001100

FIXED-POINT REPRESENTATION

The binary point is assumed to be at a fixed

position. Integer part to the left, fractional part
to the right. Limited range but simple
arithmetic.

Value = Σ (bit_i × 2^i) where i

can be negative for fractional
bits

FLOATING-POINT REPRESENTATION (IEEE

754)

Format: Sign | Exponent | Mantissa (Fraction)

Total
Precision Sign Exponent Man
Bits

Single 32 1 8 23
(32-bit)
 Double 64 1 11 52
(64-bit)

Value = (−1)^S × [Link] ×

2^(Exponent − Bias)

E X A M E X A M P L E ( F R O M M - 2 3 PA P E R )

Represent (+46.5)10 as 24-bit floating point

(16-bit mantissa, 8-bit exponent):

Step 1: 46 = 1011102, 0.5 = .12 → 46.5 =

101110.12

Step 2: Normalize → 1.011101 × 25

Step 3: Bias (if bias=127): Exponent stored =
5+127 = 132 = 100001002
Step 4: Sign = 0, Mantissa =
01110100000000000 (16 bits, drop leading 1)

BINARY ARITHMETIC

Operation Rules / Notes

Addition 0+0=0, 0+1=1, 1+0=1, 1+1=10

(carry). Use full adder chains.
 Subtraction A−B = A + (2's complement of
B). Discard final carry-out.

Multiplication Shift-and-add method. Multiply

by each bit of multiplier, shift
left, add.

Division Restoring or non-restoring

division algorithms.

GRAY CODE

Adjacent code words differ in only one bit. Used

in rotary encoders and analog-to-digital
converters to reduce errors during transitions.

BINARY ↔ G R AY C O N V E R S I O N

Binary to Gray: MSB of Gray = MSB of Binary.

Each subsequent Gray bit = XOR of current
and previous Binary bit.
Gray to Binary: MSB of Binary = MSB of Gray.

Each subsequent Binary bit = XOR of current

Gray bit and previous Binary bit.
 1.3 Combinational Logic: SOP, POS, K-Map,
Minterms & Maxterms

MINTERM AND MAXTERM

Minterm (mi): A product (AND) term where

each variable appears exactly once

(complemented or uncomplemented). Row
where output = 1 in truth table.

Maxterm (Mi): A sum (OR) term where each

variable appears exactly once. Row where

output = 0 in truth table.

K E Y R E L AT I O N S H I P

For any Boolean function with n variables: F =

Σm (sum of minterms) = ΠM (product of
maxterms)
The set of minterms + set of maxterms = all

2n combinations.

SOP AND POS FORMS

SOP (Sum of Products): OR of AND terms. F

= AB' + A'C + BC
 POS (Product of Sums): AND of OR terms. F
= (A+B)(A'+C)

Canonical SOP: Every term is a minterm (all

variables present)

Canonical POS: Every term is a maxterm

KARNAUGH MAP (K-MAP) — STEP-BY-STEP

A visual method for minimizing Boolean

functions. Cells are arranged so adjacent cells
differ by exactly one variable (Gray code
ordering).

2-variable K-Map (2×2):

B=0 B=1
A=0 | 00 | 01 |
A=1 | 10 | 11 |

4-variable K-Map (4×4), grouping rules:

Group 1s (for SOP) or 0s (for POS) in groups

of 1, 2, 4, 8, 16...

Groups must be rectangular (including wrap-

around at edges)
 Larger groups give simpler expressions —
always make groups as large as possible

Every 1 must be covered by at least one

group

Each group eliminates one variable per

doubling of size

DON'T CARE CONDITIONS

Some input combinations never occur (e.g.,

BCD digits 10–15). These are marked 'd' or 'X' in
the K-Map. You can choose them to be 0 or 1,
whichever helps create larger groups and
simpler expressions.

🎯 EXAM QUESTION (M-23, Q2B)

Minimize F(A,B,C,D) = π(0,3,4,7,8,10,12,14) +

d(2,6) using K-Map

This is a POS form (π = product of maxterms).

Place 0s at positions 0,3,4,7,8,10,12,14 and X
at 2,6 in the 4-variable K-map, then group 0s
for POS minimization.
 1.4 Combinational Circuits: Adders, MUX,
DEMUX, Encoders, Decoders

HALF ADDER

Adds two single bits. No carry-in.

Sum = A ⊕ B Carry = A · B

FULL ADDER

Adds three bits: two inputs (A, B) and one Carry-

in (Cin).

Sum = A ⊕ B ⊕ Cin

Carryout = AB + BCin + ACin

I M P L E M E N TAT I O N T I P

A full adder can be built from two half adders

+ one OR gate.

HALF SUBTRACTOR & FULL SUBTRACTOR

 Half Subtractor: Difference = A
⊕ B, Borrow = A'B
Full Subtractor: Difference = A
⊕ B ⊕ Bin, Borrowout = A'B +

B·Bin + A'Bin

MULTIPLEXER (MUX)

A data selector. Selects one of N inputs and

routes it to the output based on select lines. A
2n:1 MUX needs n select lines.

2:1 MUX: Y = S'·I0 + S·I1

4:1 MUX: 2 select lines, 4 inputs

Key Use: Any Boolean function can be

implemented using a MUX

DEMULTIPLEXER (DEMUX)

A data distributor. Routes a single input to one

of N outputs based on select lines. Opposite of
MUX.

ENCODER
Converts 2n inputs to n-bit binary output. Only
one input active at a time.

Priority Encoder: Handles multiple

simultaneous inputs by giving priority to the
highest-numbered active input.

8-to-3 Encoder: 8 inputs → 3-bit binary code

DECODER

Converts n-bit binary input to 2n outputs.

Exactly one output is active for each
combination.

2-to-4 Decoder: 2 inputs → 4 outputs

Key Use: Memory address decoding, seven-

segment display drivers

Inputs →
Component Function
Outputs

MUX (4:1) 4 data + 2 Select one of

select → 1 many inputs

DEMUX 1 data + 2 Route one input

(1:4) select → 4 to many
 Encoder 4→2 Binary
(4:2) encoding

Decoder 2→4 Binary

(2:4) decoding /
address select

1.5 Sequential Logic: Latches, Flip-Flops,

Registers & Counters

LATCH VS FLIP-FLOP

Feature Latch Flip-Flop

Triggering Level- Edge-triggered

sensitive (responds on
(responds clock edge
while enable only)
is active)

Clock Not Requires a

necessarily clock signal
clocked
 Stability Less More stable;
predictable; synchronized
prone to
glitches

Use Simple Registers,

storage, counters,
async circuits synchronous
circuits

SR LATCH (SET-RESET)

S=1, R=0 → Q=1 (Set)

S=0, R=1 → Q=0 (Reset)

S=0, R=0 → Q unchanged (Hold)

S=1, R=1 → Forbidden / Indeterminate state

FLIP-FLOP TYPES

Flip- Characteristic
Inputs Operation
Flop Equation

SR S, R Set / Q+ = S + R'Q
FF Reset. (with SR=0)
SR=11 is
invalid.
 D FF D Data/Delay. Q+ = D
Q+ = D
regardless
of current
state.

JK J, K Like SR but Q+ = JQ' + K'Q

FF JK=11
toggles. No
invalid
state.

T FF T Toggle Q+ = T ⊕ Q
when T=1;
hold when
T=0.

RACE-AROUND CONDITION (JK FF)

When J=K=1 and the clock pulse width is long,

the output toggles multiple times during one
clock cycle (races around). Solution: Use
Master-Slave JK Flip-Flop — the master
captures input on the rising edge and transfers
to slave on the falling edge, ensuring only one
transition per clock cycle.

SHIFT REGISTERS
A chain of D flip-flops where the output of one
connects to the input of the next. Used for
serial-to-parallel and parallel-to-serial
conversion, data delay.

SISO: Serial In, Serial Out

SIPO: Serial In, Parallel Out

PISO: Parallel In, Serial Out

PIPO: Parallel In, Parallel Out (universal shift

register)

COUNTERS

Clock
Type Speed
Connection

Asynchronous Each FF Slower

(Ripple) clocked by (propagation
Q of delay)
previous

Synchronous All FFs Faster

share (simultaneous)
same clock

Mod-N Counter: Counts from 0 to N−1, then

resets. Needs ⌈log2N⌉ flip-flops.
Up Counter, Down Counter, Up-Down
Counter

Ring Counter: Circular shift register. Only

one bit is '1' at any time.

Johnson Counter: Inverted output feeds

back to input. Counts in Gray code
sequence.

🎯 E X A M FA V O U R I T E

Design a counter for sequence 0,4,5,3,1,6,2,7

using JK flip-flops:
1) Create a state transition table. 2) Find next
states. 3) Use J-K excitation table to find J and
K for each FF. 4) Minimize using K-maps. 5)
Draw logic diagram.

CPU Architecture &

Computer Organization
II Flynn's Classification · Performance
Metrics · Von Neumann Architecture ·
 Instruction Cycle

2.1 Flynn's Classification of Computers

Flynn (1966) classified computer architectures

based on the number of concurrent instruction
streams and data streams.

D
Architecture Full Form Instructions
St

SISD Single 1 1
Instruction,
Single
Data

SIMD Single 1 M
Instruction,
Multiple
Data
 MISD Multiple Multiple 1
Instruction,
Single
Data

MIMD Multiple Multiple M

Instruction,
Multiple
Data

WHICH IS USED IN VECTOR PROCESSORS?

SIMD — A single instruction applies the same

operation to multiple data elements

simultaneously. Perfect for graphics, scientific
computation, and AI inference.

MIMD SUB-TYPES

Shared Memory (SMP): All processors share

a single global memory space. Easy to
program, but memory becomes a
bottleneck.
 Distributed Memory: Each processor has its
own local memory. Communicates via
message passing. Scales better.

2.2 Performance Metrics: MIPS & MFLOPS

MIPS — MILLIONS OF INSTRUCTIONS PER

SECOND

Measures the rate of instruction execution.

Higher = faster CPU for integer operations.

MIPS = Clock Frequency (MHz) /

CPI

Or: MIPS = Instruction Count /

(Execution Time × 10⁶)

L I M I TAT I O N O F M I P S

MIPS is misleading because different ISAs

execute different numbers of instructions for
the same task. A RISC CPU might have higher
 MIPS but do the same work with more
instructions than a CISC CPU.

MFLOPS — MILLIONS OF FLOATING-POINT

OPERATIONS PER SECOND

Measures floating-point computation speed.

Used for scientific and engineering
applications.

MFLOPS = Number of Floating-

Point Operations / (Execution
Time × 10⁶)

CPI — CYCLES PER INSTRUCTION

CPI = Total Clock Cycles /

Total Instructions

Effective CPI = Σ (CPI_i ×

Instruction_fraction_i)

CPU PERFORMANCE EQUATION

 Execution Time = Instruction
Count × CPI × Clock Cycle Time
= Instruction Count × CPI /
Clock Frequency

🎯 E X A M C A L C U L AT I O N ( M - 2 4 , Q 4 A )

40 MHz processor, instruction mix:

Integer Arith: 45000, CPI=1 | Data transfer:
32000, CPI=2 | Float: 15000, CPI=2 | Control:
8000, CPI=2

Total cycles = (45000×1) + (32000×2) +

(15000×2) + (8000×2) = 45000 + 64000 +
30000 + 16000 = 155,000
Total instructions = 100,000
Effective CPI = 155,000 / 100,000 = 1.55
MIPS = 40 / 1.55 = 25.8 MIPS
Execution time = 155,000 / 40,000,000 = 3.875
ms

2.3 CPU Architecture Types: Accumulator,

Register, Stack, Memory
CPU architectures differ in where operands are
stored and how operations are performed.

Operand A=B
Architecture Chara
Source +C

Accumulator Implicit LOAD Simp

accumulator B hardw
register ADD C (man
STORE instru
A early

Stack Top of stack PUSH No ne

B speci
PUSH regist
C postfi
ADD evalu
POP A JVM

GPR General ADD Most

(Register) purpose R1, R2, mode
registers R3 use t

Memory-to- Main ADD Comp

Memory memory A, B, C instru
fewer
instru
 neede
style

MODERN CPUS

Modern processors use General Purpose

Register (GPR) architecture. They have many
registers (e.g., 32 in RISC-V, 16 in x86-64) to
minimize memory accesses.

2.4 Von Neumann Architecture & Stored

Program Concept

STORED PROGRAM CONCEPT

Proposed by John von Neumann (1945). Key

idea: programs (instructions) and data are
stored in the same memory and can be treated
as data. This allows programs to be loaded and
modified dynamically.

COMPONENTS OF VON NEUMANN

ARCHITECTURE
 CPU (Central Processing Unit): Contains
ALU (arithmetic/logic unit) and Control Unit
(CU)

Memory Unit (RAM): Stores both

instructions and data

Input/Output Unit: Interfaces with the

outside world

Bus: Data bus, Address bus, Control bus —

the communication paths

KEY REGISTERS IN A BASIC COMPUTER

Register Full Name Function

PC Program Holds address

Counter of next
instruction to
fetch

MAR Memory Holds address

Address for memory
Register read/write

MBR/MDR Memory Holds data

Buffer/Data being read
Register from or
 written to
memory

IR Instruction Holds the

Register instruction
currently
being
executed

AC Accumulator Holds results

of ALU
operations

DR Data Register Temporary

storage during
ALU
operations

TR Temporary Internal ALU

Register use

INSTRUCTION CYCLE (FETCH-DECODE-

EXECUTE)

1. Fetch: MAR ← PC; Read memory → MBR; IR

← MBR; PC ← PC+1

2. Decode: Control unit decodes opcode in IR

3. Execute: Perform the operation (could
involve memory access, ALU op, etc.)

TYPES OF INSTRUCTIONS

Type Description Examples

Memory Involve reading/writing LOAD,

Reference memory STORE, A
[addr], BS
(Branch a
Save
Address)

Register Operate on the CLA (Clea

Reference accumulator/registers. AC), CMA
No memory address (Complem
needed. AC), INC,
SPA, SNA

I/O Input/Output INP (Inpu

Reference operations AC), OUT
(Output fr
AC), ION,

ACCUMULATOR LOGIC

In Mano's basic computer, the ALU always uses

the Accumulator (AC) as one operand. The
sequence for ADD operation: DR ← M[EA]; AC
← AC + DR; SC ← 0 (clear sequence counter).

ISA, Control Unit &

Addressing Modes
III Microprogrammed Control · RISC vs
CISC · Instruction Formats ·
Interrupts

3.1 Control Memory & Microprogrammed

Control

HARDWIRED VS MICROPROGRAMMED

CONTROL

Hardwired Microprogramm
Feature
Control Control
 Implementation Logic Control memory
gates and (ROM) storing
flip-flops microinstruction

Speed Faster Slower (memory

access overhea

Flexibility Rigid; hard Flexible; update

to modify by changing
microprogram

Complexity Complex Handles comple

for ISAs easily
complex
ISAs

Used in RISC CISC processor

processors (x86)

CONTROL MEMORY

A special high-speed ROM (or sometimes RAM)

that stores microinstructions. Each
microinstruction specifies the control signals
for one clock cycle.

MICROINSTRUCTION FORMAT

A microinstruction typically contains:

 Operations field: ALU operation, register
transfers to perform

Condition field (CD): Which condition to test

for branching

Branch field (BR): Type of branch

(unconditional, conditional, call, return)

Address field: Next microinstruction

address (if branching)

ADDRESS SEQUENCING IN

MICROPROGRAMMED CONTROL

How does control move from one

microinstruction to the next?

1. Incrementing: CAR (Control Address

Register) is incremented by 1 for sequential
execution

2. Unconditional Branch: Load CAR with

branch address from current
microinstruction

3. Conditional Branch: If condition (from CD

field) is true, branch; else increment

4. Mapping: Map opcode of machine

instruction to starting address of its
 microprogram routine

5. Subroutine: Save current address in SBR

(Subroutine Branch Register), jump to
subroutine microprogram

MICROPROGRAM SEQUENCER

The control unit that determines the next

address for the CAR. It uses the BR field, CD
field (condition flags from status register), and
current CAR value to compute the next
microinstruction address.

🎯 EXAM QUESTION (M-23, Q7B)

Discuss the role of Condition Field (CD),

Branch Field (BR), and Input Logic in
Microprogrammed Control:
• CD field: Selects which status bit (carry, zero,
sign, overflow) to test
• BR field: Determines branching action
(JMP=unconditional branch, CALL=subroutine
call, RET=return, MAP=opcode mapping)
• Input Logic: Multiplexer that selects
condition bit based on CD, fed into sequencer
 WHY MICROPROGRAMMED CONTROL IS NOT

S U I TA B L E F O R R I S C

RISC philosophy: instructions must execute in

one clock cycle (or very few).
Microprogrammed control adds latency from
control memory access. RISC uses hardwired
control for maximum speed.

3.2 RISC vs CISC Architectures

Feature RISC CISC

Instructions Simple, fixed- Complex, variable

length length

Execution 1 clock cycle Multiple clock

per cycles
instruction

Memory Only Instructions can

access LOAD/STORE access memory
instructions directly
Registers Many (32+) Fewer

Addressing Few (simple) Many (complex)

modes

Control unit Hardwired Microprogramme

Compiler Complex Simpler compiler

compiler
needed

Code size Larger (more Smaller (fewer,

instructions) powerful instr.)

Examples ARM, MIPS, Intel x86, x86-64,

RISC-V, VAX
SPARC

MODERN REALITY

Modern x86 CPUs (Intel, AMD) have a CISC

ISA externally but internally translate
instructions to RISC-like micro-ops for
execution. So the best of both worlds.
 3.3 Stack Organization & Instruction
Formats

STACK ORGANIZATION

A stack is a LIFO (Last In First Out) data

structure with two operations: PUSH (add to
top) and POP (remove from top). The Stack
Pointer (SP) always points to the top of the
stack.

Register Stack: Stack stored in CPU

registers (limited size, fast)

Memory Stack: Stack in main memory, SP

tracks current position

INSTRUCTION FORMATS: 0, 1, 2, 3-

ADDRESS

For A =
Format Structure Not
(B+C)×(D+E)

3- OP dest, ADD T1,B,C Sho

address src1, src2 ADD T2,D,E prog
MUL larg
A,T1,T2
 inst
wor

2- OP dst, src MOV T1,B; Mos

address (dst = dst OP ADD T1,C com
src) MOV A,D; (x86
ADD A,E
MUL A,T1

1- OP addr LOAD B; Acc

address (uses ADD C; bas
accumulator) STORE T1
LOAD D;
ADD E; MUL
T1; STORE
A

0- OP (stack- PUSH B; Stac

address based) PUSH C; mac
ADD JVM
PUSH D;
PUSH E;
ADD; MUL
POP A
 3.4 Addressing Modes

An addressing mode specifies how the operand

(or its address) is determined from the
instruction.

Effective
Mode Address / Example U
Operand

Immediate Operand ADD R1, C

is in the #5 → n
instruction operand = a
itself 5 n

Direct EA = LOAD 500 G

(Absolute) address → fetch v
field of M[500]
instruction

Indirect EA = LOAD P
M[address @500 → fl
field] fetch
(pointer) M[M[500]]

Register Operand ADD R1, F

is in a R2 → use m
 register R2 a

Register EA = LOAD A
Indirect contents (R1) → a
of register fetch p
M[R1]

Relative EA = PC + Branch +5 B
offset → EA = p
PC+5 in
c

Indexed EA = base LOAD A

address + 100(XR) tr
index → EA =
register 100+XR

Autoincrement EA = R; LOAD S
then R ← (R1)+ a
R+1

Autodecrement R ← R−1; LOAD − S

then EA = (R1) o
R

🎯 EXAM EXAMPLE (M-23, Q6B) — GIVEN

PC=200, R1=400, XR=100, M[399]=999,

M[400]=1000
 Immediate: Operand = 500 (the address

field itself is the operand)

Direct: EA = 500, Operand = M[500]

Indirect: EA = M[500], Operand = M[M[500]]

Relative: EA = PC + 500 = 200 + 500 = 700

Indexed: EA = 500 + XR = 500 + 100 = 600

Register: EA = R1, Operand = R1 = 400

Register Indirect: EA = M[R1] = M[400] =

1000

Autoincrement: EA = R1 = 400; R1
becomes 401

Autodecrement: R1 decremented to 399;

EA = M[399] = 999

WHY ARE ADDRESSING MODES NEEDED?

Provide programming flexibility (arrays,

pointers, stacks)

Reduce instruction count

Enable efficient access to different data

structures
 Support both local and global variable
access efficiently

3.5 Interrupts — Definition, Handling & Types

WHAT IS AN INTERRUPT?

An interrupt is a signal to the CPU indicating

that an event needs immediate attention. The
CPU suspends its current program, saves its
state, and executes an Interrupt Service
Routine (ISR), then resumes the original

program.

STEPS IN INTERRUPT HANDLING

1. Device sends interrupt request (IRQ) to CPU

2. CPU completes current instruction

3. CPU saves PC, flags, and registers (context

save) to stack

4. CPU loads address of ISR from interrupt

vector table

5. ISR executes to handle the event

6. CPU restores saved context (registers, PC,
flags)

7. Resumes interrupted program

TYPES OF INTERRUPTS

Type Source Examples

Hardware External Keyboard

Interrupt devices press, mouse
click, network
packet arrival

Software Program System calls,

Interrupt instruction INT 21h in DOS
(INT n)

Maskable Can be I/O device

Interrupt disabled by requests (can
CPU be postponed)

Non- Cannot be Power failure,

Maskable disabled hardware error,
Interrupt memory parity
(NMI) error
 Vectored Device PIC-based
Interrupt provides systems
ISR address

Non- CPU polls to Polled interrupt

Vectored find source systems

Exception / Internal Division by

Trap CPU events zero, invalid
opcode, page
fault

INSTRUCTION SET OPERATIONS

Category Operations

Arithmetic & ADD, SUB, MUL, DIV, AND, OR,

Logical NOT, XOR, SHL, SHR

Data Transfer LOAD, STORE, MOVE, PUSH,

POP, EXCHANGE

Control Flow JUMP, BRANCH (conditional),

CALL, RETURN, HALT

I/O IN, OUT

 Parallelism, Memory

IV Hierarchy & I/O

Amdahl's Law · Pipelining · Cache
Memory · DMA · I/O Techniques

4.1 Introduction to Parallelism & Amdahl's

Law

GOALS OF PARALLELISM

Reduce execution time for large

computations

Increase throughput (more tasks per unit

time)

Handle large-scale problems that don't fit in

one machine

Improve reliability through redundancy

AMDAHL'S LAW
The speedup of a program using multiple
processors is limited by the sequential (non-
parallelizable) fraction.

Speedup = 1 / [(1 − P) + P/N]

Where:
P = fraction of program that
can be parallelized (0 to 1)
N = number of processors
(1−P) = sequential fraction

Maximum Speedup (N → ∞) = 1 /
(1 − P)

🎯 E X A M C A L C U L AT I O N ( M - 2 3 , Q 9 A )

90% of a program can be parallelized (P = 0.9),

using 10 processors:

Speedup = 1 / [(1 − 0.9) + 0.9/10] = 1 / [0.1 +

0.09] = 1 / 0.19 = 5.26×

Maximum possible speedup (unlimited

processors) = 1 / (1 − 0.9) = 1/0.1 = 10×
 KEY INSIGHT

Even with 10 processors and 90% parallelism,

speedup is only 5.26× not 10×. The 10%
sequential portion is the bottleneck. This is
why eliminating sequential sections matters
most.

4.2 Instruction-Level Parallelism: Pipelining

WHAT IS PIPELINING?

Pipelining is an implementation technique

where multiple instructions are overlapped in
execution, similar to an assembly line. Each
stage of the pipeline processes a different
instruction simultaneously.

CLASSIC 5-STAGE RISC PIPELINE

IF ID EX MEM
Instruction Instruction Execute Memory
Fetch Decode Access
PIPELINE PERFORMANCE

Without pipeline: Time = n × k

cycles (n=instructions,
k=stages)

With pipeline: Time = (k + n −

1) × clock_cycle

Speedup = (n × k) / (k + n − 1)
≈ k (when n >> k)

🎯 E X A M C A L C U L AT I O N ( M - 2 4 , Q 8 A )

Non-pipeline: 50 ns per task. Pipeline: 6

stages, 10 ns/clock. For 100 tasks:

Non-pipeline time = 100 × 50 = 5000 ns

Pipeline time = (6 + 100 − 1) × 10 = 105 × 10 =
1050 ns
Speedup = 5000 / 1050 = 4.76×
Maximum speedup = k = 6× (when n → ∞)

PIPELINE HAZARDS
Situations that prevent the next instruction from
executing in its designated clock cycle:

Hazard
Cause Solutions
Type

Structural Two Resource duplicat

Hazard instructions stalling
need the same
hardware
resource
simultaneously

Data Instruction Forwarding/Bypa

Hazard depends on NOPs; Out-of-orde
result of a execution
previous
instruction not
yet complete

Control Branch Branch prediction

Hazard instruction delayed branching
changes PC; branch target buff
fetched
instructions
may be wrong

DATA HAZARD TYPES

 RAW (Read After Write): Instruction 2 reads
a register before Instruction 1 writes it. Most
common. Also called true dependency.

WAR (Write After Read): Instruction 2 writes

before Instruction 1 reads the value. Anti-
dependency.

WAW (Write After Write): Two instructions

write the same register; order must be
preserved. Output dependency.

4.3 Memory Hierarchy

THE NEED FOR MEMORY HIERARCHY

A fundamental trade-off exists: faster memory

= more expensive per bit. We can't afford to

make all memory as fast as CPU registers. The

hierarchy exploits locality of reference.

PRINCIPLE OF LOCALITY OF REFERENCE

Temporal Locality: A recently accessed

location is likely to be accessed again soon.
 (Loop variables, frequently called functions)

Spatial Locality: If a location is accessed,

nearby locations are likely to be accessed

soon. (Arrays, sequential code)

MEMORY HIERARCHY (FASTEST TO

SLOWEST)

Access
Level Type Size Cos
Time

1 CPU ~1 ns Bytes Hig

Registers (32–
256)

2 L1 Cache ~2–4 32– Ver

ns 64 Hig
KB

3 L2 Cache ~5–10 256 Hig

ns KB–4
MB

4 L3 Cache ~20– 4–32 Me

40 ns MB Hig

5 Main ~60– GBs Me

Memory 100 ns
 (DRAM)

6 Auxiliary ms TBs Low

Memory range
(SSD/HDD)

MEMORY PARAMETERS

Access Time: Time from request to data

available

Cycle Time: Minimum time between

successive accesses (access time +
recovery)

Bandwidth: Amount of data transferred per

unit time

Cost per bit: Price divided by capacity

TYPES OF MEMORY

Type Full Name Characteristics

SRAM Static RAM Uses flip-flops;

no refresh
needed; faster;
expensive; used
in cache
 DRAM Dynamic RAM Uses
capacitors;
needs periodic
refresh; slower;
cheaper; used
in main
memory

ROM Read-Only Non-volatile;

Memory holds
firmware/BIOS

PROM Programmable Write once,

ROM then read-only

EPROM Erasable Erasable with

PROM UV light

EEPROM Electrically Electrically

Erasable erasable, byte-
PROM level

Flash Flash Memory Block-level

erase; SSDs,
USB drives

ASSOCIATIVE MEMORY (CONTENT-

ADDRESSABLE MEMORY)
Memory accessed by content, not address. You
provide a key (pattern), and hardware
simultaneously searches all locations for a
match. Used in TLBs (Translation Lookaside
Buffers) and cache tag comparison.

4.4 Cache Memory — Direct Mapped &

Associative

CACHE CONCEPTS

Cache Hit: Requested data found in cache

Cache Miss: Data not in cache; must fetch

from main memory

Hit Rate (h): Fraction of accesses that are

cache hits

Miss Penalty: Extra time to fetch from main

memory on a miss

Average Access Time = h ×

T_cache + (1−h) × T_main
(Simultaneous access
 organization)

Or: T_avg = T_cache + (1−h) ×

T_main
(Sequential / Hierarchical
access)

🎯 E X A M C A L C U L AT I O N ( M - 2 4 , Q 9 B ) — C A C H E
H I T R AT E = 8 0 % , T _ C A C H E = 5 N S , T _ M A I N =

100 NS

Simultaneous: T_avg = 0.8×5 + 0.2×100 = 4 +

20 = 24 ns
Hierarchical: T_avg = 5 + 0.2×100 = 5 + 20 =

25 ns

DIRECT-MAPPED CACHE

Each main memory block maps to exactly one

cache line. The cache line is determined by:
cache_index = block_number mod
(number_of_cache_lines)

Address Division:

Block Offset bits: log2(block_size) —

identifies byte within block

 Index bits: log2(number_of_cache_lines) —

identifies cache line

Tag bits: Remaining bits — identifies which

main memory block is in this cache line

Tag bits = Total address bits −

Index bits − Offset bits

🎯 E X A M C A L C U L AT I O N ( M - 2 4 , Q 9 A )

Direct-mapped cache: 32 KB, block size = 32

bytes, CPU generates 32-bit addresses

Offset bits = log₂(32) = 5 bits

Number of cache lines = 32 KB / 32 B = 1024
lines
Index bits = log₂(1024) = 10 bits
Tag bits = 32 − 10 − 5 = 17 bits

ASSOCIATIVE CACHE (FULLY ASSOCIATIVE)

A block can be placed in any cache line.

Requires searching all cache lines for a tag
match (uses associative memory / CAM).
Higher hit rate, but more complex hardware.
 No index field — only Tag + Offset

Requires parallel comparison of all tags

SET-ASSOCIATIVE CACHE

Compromise between direct-mapped and fully

associative. Cache is divided into sets, each
with k lines (k-way set-associative). A block
maps to a specific set (using index) but can go
in any of the k lines within that set.

Hardware Miss
Organization Flexibility
Cost Rate

Direct- Low Low Highe

Mapped (fixed
line)

Set- Medium Medium Medi

Associative

Fully High (any Highest Lowe

Associative line)

🎯 E X A M C A L C U L AT I O N ( M - 2 3 , Q 8 B )

8 KB associative cache, block size = 32 bytes,

main memory = 1 GB
 Number of cache blocks = 8×1024 / 32 = 256
blocks

Number of main memory blocks = 1 GB / 32 B

= 2³⁰ / 2⁵ = 2²⁵ blocks
Tag bits = 25 (to identify which main memory
block is in cache)
Number of comparisons for a search = 256
(all cache blocks checked simultaneously in
full associative)

4.5 I/O Interface, Modes of Transfer & DMA

INPUT-OUTPUT INTERFACE

The I/O interface connects peripherals to the

CPU/memory bus. It handles signal level
differences, timing mismatches, and protocol
conversion between CPU and devices.

Components: Data register (holds data being

transferred), Status register (device
ready/busy/error flags), Control register
(commands to device).
MODES OF DATA TRANSFER

How It CPU
Mode
Works Involvement

Programmed CPU 100% —

I/O (Polling) repeatedly CPU stuck
checks in loop
status
register to
see if
device is
ready
(busy-
waiting)

Interrupt- CPU Only at start

Driven I/O initiates I/O, and end
continues
other work,
device
interrupts
when ready
 Direct DMA CPU only at
Memory controller start
Access handles (setup) and
(DMA) data end
transfer (interrupt)
between
device and
memory
directly,
without
CPU
involvement
for each
byte

DMA — DIRECT MEMORY ACCESS

The DMA controller is a specialized chip that

takes over the bus to transfer data between I/O
devices and main memory directly, bypassing
the CPU for each word transferred.

DMA CONTROLLER REGISTERS

Address Register: Starting memory address

for transfer
 Word Count Register: Number of words to
transfer

Control Register: Direction (read/write),

device ID, mode

Status Register: Transfer complete / error

flags

DMA TRANSFER PROCESS

1. CPU programs DMA controller (address,

count, direction)

2. CPU continues executing its program

3. DMA controller requests bus from CPU

(cycle stealing or burst mode)

4. CPU grants bus (releases bus control)

5. DMA transfers data word by word (or in

bursts) between device and memory

6. After completion, DMA interrupts CPU

7. CPU resumes control

CYCLE STEALING VS BURST MODE DMA

Cycle Stealing: DMA steals one bus cycle at a

time from CPU; CPU can still work (slower, but

CPU not blocked).
 Burst Mode: DMA takes full control of bus for

the entire transfer; CPU fully blocked but

transfer is fastest.

PROCESSOR-LEVEL PARALLELISM:
MULTIPROCESSOR OVERVIEW

SMP (Symmetric Multiprocessing): Multiple

CPUs sharing one memory and OS. Same
access time to memory for all CPUs.

NUMA (Non-Uniform Memory Access):

Each processor has local memory; access to
remote memory is slower.

Cluster: Multiple independent computers

connected by high-speed network,

cooperating on tasks.

Digital Logic & Computer Design (PCC-CSEAI210-T) · [Link] CSE

(AI & ML) · 4th Semester
Based on syllabus and past exam papers (M-23, M-24, M-25)