Storage cells

Address Address
0 0
1 1
2 1 0 0 0 1000 2 1 0 0 0 Reading data
Writing data
3 3
4 4
5 5
6 6
n–1 n–1
n n

(a) Write operation (b) Read operation

 Classification of memory

Based on
principle of operation
Read only memory (ROM) Read/write memory (RAM)

Masked PROM EPROM EEPROM Static Dynamic

ROM RAM RAM
Based on physical
characteristics
Erasable Non erasable Volatile Nonvolatile

Based on
mode of access
Sequential Random

Based on
terminology
used for
fabrication
Bipolar MOS
 Secondary storage
devices

Sequential access Random access

devices devices

Magnetic tape
Magnetic Magneto
Optical disk
disk optical disk

Write Once
Floppy Hard Zip CD-ROM Read Many
disk disk disk read-only (WORM) disk
Increasing CPU Increasing Increasing
size speed cost per bit
Primary
cache

Secondary
cache

Main
memory

Magnetic disk, magnetic

tape secondary
memory
 Cache
CPU memory

Main
memory

I/O
processor

Magnetic Magnetic
tapes disks

Auxiliary memory

I : Instruction flow
D : Data flow

I I
Main Secondary
CPU memory memory
D D

M1 M2

(a) Two - level

I
I I - cache I
Main Secondary
CPU memory memory
D D
D D - cache

M2 M3
M1
(b) Three - level

I I I I
Level 1 Level 2 Main Secondary
CPU memory memory
cache cache
D D D D
M1
M2 M3
M4
(c) Four - level
 b b'

T1 T2
X Y

T1
T2
Word line

Bit lines

T1 T2 T1 T2

b b

b

b
 VDD
b b'

T3 T4
T1 T2

(T 3 , T5 ) X Y
(T4 , T6 )
T5 T6

T1
Word line
T2
Bit lines

T1 T2
T1 T2
T1 T2

T1 T2 .
T3
T6 T4 T5
T3 T6 T4 T5

b

Sense line

Storage
capacitor

Control
line
Bit line VCC

Word line

Open : Data stored (logic 1)

T P Close : Data stored (logic 0)
E2

VDD

Address select line

MOSFET
switch
Data line

Fuse
 Output bit
 Quartz window
Ultraviolet light
 ( 200 A
25 V

n-data lines

k-address
lines Memory
unit
k
Read 2 word
n-bit per word
Write

2k 2 10

16  8  128 bits

2 11

2 18  262144
  

D0
D1

D7 D4 D3 D0
I/O3 I/O0 I/O3 I/O0
A0 A0
A9 1K4 A9 1K4

CS WR RD CS WR RD

Chip select

Write

Read

 
 A0
A11

D0
D7

A11 A0 D7 D0 A11 A0 D7 D0 A11 A0 D7 D0 A11 A0 D7 D0

4K8 4K8 4K8 4K8
CS WR RD CS WR RD CS WR RD CS WR RD

RD

WR

A12 0
24 1
Decoder
2
A13
3

Memory cell 8191

Memory cell 8064

63
Data in
62
Line decoder

61

Data
2
6 to 64

out
1

Memory cell 127 Memory cell 0

127 126 125 124 2 1 0

7 to 128 Line decoder

A6 A5 A4 A2 A1 A0
 64  128  8192


b7 b'7 b1 b'1 b0 b'0

W0

FF FF
W1
A0

A1
Address Memory
decoder cells
A2

A3

W15

R/W
Sense/write Sense/write Sense/write
circuit circuit circuit
CS

Data input/output lines: b7 b1 b0

 Word line

ON 0
1
Tunnel Control gate
oxide
Floating gate
Bit line
Source Drain
n+ n+

p - substrate
 SRAM DRAM

Processor Cache Main

memory

Cache
controller

Cache memory system

Number of hits
 100 %
Total number of bus cycles
 1400
 100
1400  100
 
Total wait states 300
Number of memory bus cycles 1500

Cache
M1
Main
CPU memory
Cache Block M2
access replacement

Main-memory
access

System bus
M1

M2
M2 M1
 Cache
M1

Cache Block
access replacement

Main Main
Cache memory
CPU memory
controller M2
controller

Main
memory
access

System bus
 Main Main
memory memory
address

Cache tag memory Cache data memory

1001001111 39 11 10 01 00

1001001110 D4
1001001101 67
1001 0011 39 D4 67 2C
1001001100 2C
1001001011 C3
1001 0001 B2 5A 00 40
1001001010 9A
1001001001 35
1001001000 1A
1001000111 B2
1001000110 5A
1001000101 00 Data
Tag selector
1001000100 40 comparator

Data
5A
OUT
Address in
1001 0001 10
 Main Main
memory memory
address

Cache tag memory Cache data memory

1001001111 39 11 10 01 00

1001001110 D4
1001001101 67
1001 0011 39 D4 67 2C
1001001100 2C
1001001011 C3
1001 0001 B2 E6 00 40
1001001010 9A
1001001001 35
1001001000 1A
1001000111 B2
1001000110 5A
1001000101 00 Data
Tag selector
1001000100 40 comparator

Data
IN E6
Address in
1001 0001 10
 Block 0
Block 1

Block 0

27
 Main memory
Block 0
Block 1
12 bits Cache
memory
Tag
Block 0  
Tag
Block 1 Block i

   
Tag Block 127
Block j

Tag
12
Word
4
 
Main memory address Block 4095
 Main memory
Block 0
Block 1
Block belongs
to set 0 Page 0
  Tag 0

Block 63
Block 64
Block 65
Cache memory Cache memory
Set 0 Tag Tag Page 1

Set 1 Tag
Block 0
Tag
Block 0
  Tag 1
Block 1 Block 1
Block 127
   
Set 62 Tag Tag Block 62  
Set 63 Tag Tag
Block 63 Block 63 Block 4032
Block 4033
Tag Set Word
Page 63

Block belongs
6 6 4
  Tag 63

to set 63
Block 4095
 24

( 2 8  256)

TAG BLOCK WORD

Main memory address = 4 8 4

 2 12

TAG WORD

Main memory address = 12 4

27  128

TAG SET WORD

Main memory address = 5 7 4

  
 

Cache size 1K
Words in each block 4

Tag Block Word

Main memory address = 6 8 2


 

2048
4
512
2

Tag Set Word

Main memory address = 7 8 2

17 bits

log 2 128
Cache size 1K
Words in each block 128

 log 2 8

log 2 64 K log 2 2 16


TAG BLOCK WORD

Main memory address = 6 3 7

16 - bits
2 12

2 10

2 10 2 10  147
 Other bus Other bus
master master Cache
Main
memory

80386 82385 Shared 80386 Cache

memory

Other bus
master

Non-cacheable
80386 Decode
Main
memory Cacheable
Decode

 Reads
 
Program

 Writes 
 Program  Write miss rate  Write miss penalty 
 

Memory accesses
 Miss rate  Miss penalty
Program

Instructions Misses
  Miss penalty
Program Instruction
 CPU time with stalls I  CPI stall  clock cycle
CPU time with perfect cache I  CPI perfect  clock cycle

CPI stall 5.44

CPI perfect 2
5.44
2
 


Address space

Page 0 1 K words

Page 1

Page 2

Page 3 Memory space

Page 4 Block 0 1 K words

Page 5 Block 1

Page 6 Block 2

Page 7 Block 3

13 12
8K=2 4K=2

Words in address space

Words per page
 4 G words
4 K words
Words in memory space 16 M words
Words per page (block) 4 K words

2 24

2 16

Page number Line number

100 0 1 1 1 0 1 0 1 1 0 Virtual address

Table Presence bit

address
000 0 Main memory

001 10 1 Block 0

010 00 1 01 0111010110 Block 1

011 0 Main memory Block 2

address register
100 01 1 Block 3

101 0

110 11 1 MBR

111 0

01 1

Memory page table

 Page 0

Page 1

Page 2

Page 3
Block 0
Page 4
Block 1
Page 5
Block 2
Page 6
Block 3
Page 7
Memory space
12
Address space M=4K=2
13
N=8K=2
 Initial 4 2 0 1 2 6 1 4 0 1 0 2 3 5 7

Least 4 4 4 4 4 0 0 2 6 6 6 4 1 0 2
recently 2 2 2 0 1 2 6 1 4 4 1 0 2 3
used
0 0 1 2 6 1 4 0 1 0 2 3 5
1 2 6 1 4 0 1 0 2 3 5 7

Initial 4 2 0 1 2 6 1 4 0 1 0 2 3 5 7

4 4 4 4 4 2 2 0 0 0 0 1 6 4 2
2 2 2 2 0 0 1 1 1 1 6 4 2 3
0 0 0 1 1 6 6 6 6 4 2 3 5
1 1 6 6 4 4 4 4 2 3 5 7
 Logical address

Segment Page Word

Segment table Page table

Block Word

Physical address

2K
2K
 Physical
memory
Linear address Translation lookaside HIT
buffer (TLB)

Segment Page MISS

Block

Segment table Page table

+
Block Word

(a) Associative memory (TLB) (b) Working of TLB

 Logical address

7-bits 5-bits 12-bits

Segment Page Word

Segment table Page table

127 31
30

1 1
0 0

Block Word

12-bits 12-bits

Physical address
 Local bus Main
Processor Cache memory

Local I/O
controller

System bus

Expansion
Network SCSI Modem Serial
bus interface

Expansion bus

Local bus Main

Processor Cache memory

Local I/O
controller

System bus

SCSI P 1394 Graphics Video LAN

High speed bus

Expansion
FAX Modem Serial
bus interface

Expansion bus
 1 0 1 0 1 0
Logical 1 (+5 V)
Crystal
Logical 0 (0 V)
oscillator

t0
t0  t1
t1
t2

Bus clock

Address
bus

Data bus

RD

t0 t1 t2
Bus cycle

t1
t2

t1
 Bus clock

Address
bus

Data bus

WR

t0 t1 t2
Bus cycle

Bus clock

Signals seen by master tAM

Address

tDM

Signals seen by slave tAS

Address

Data
tDS
t0 t1 t2 Time

t0

t AM
 t1
t DS
t DM t2 t 2  t DM

t2

t2 – t0

1 2 3 4

Clock

Address

Data

Slave-ready

RD
 Address bus

RD

Master-ready / Ready

Slave-ready / Accept

Data bus

t0 t1 t2 t3 t4 t5
Bus cycle
 Address bus

Data bus

WR

Master-ready / Ready

Slave-ready / Accept
t0 t1 t2 t3 t4 t5
Bus cycle

Data bus
Source Destination
unit Strobe unit

(a) Block diagram

Valid data
Data

Strobe

(b) Timing diagram

 Data bus
Source Destination
unit Strobe unit

(a) Block diagram

Valid data

Strobe

(b) Timing diagram

 Data bus
Source Data valid Destination
unit unit
Data accepted

(a) Block diagram

Data bus Valid data

Data valid

Data accepted

(b) Timing diagram

Source unit

Place data on
1.
the bus
Destination unit

2. Enable data Accept data from

valid signal 3. the bus

Disable data 4. Enable data

5.
valid signal accepted signal

6. Invalidate data 7. Disable data

on the bus accepted signal

Ready to accept data

Initial State

(c) Sequence of events

 Data bus
Source Data valid Destination
unit Ready for data unit

(a) Block diagram

Ready for data

Data valid

Data bus Valid data

(b) Timing diagram

Source unit Destination unit

1. Ready to accept data

Enable ready for data signal
2.
Place data on bus
Enable data valid

Accept data from bus

3.
Disable ready for data signal

Disable data valid

4. Invalidate data on bus

Initial state (c) Sequence of events

 Master 1 Master 2 Master N

Bus access Bus access Bus access

logic logic logic

Bus grant
Bus request
Controller
Bus busy
 Master 1 Master 2 Master N

Bus access Bus access Bus access

Module logic logic logic
address

Controller
Bus request
Bus busy
 Master 1 Master 2 Master N

Bus access Bus access Bus access

logic logic logic

Bus grant 1
Bus request 1
Bus grant 2
Bus request 2
Controller
Bus grant N
Bus request N
Bus busy


 VCC

ARB0

ARB1

ARB2

ARB3

Start Arbitration

1 1 1 0 1 0 0 0 1 0 0 1 1 0 0 0

0 0 0 1 0 1 1 1 0 1 1 0 0 1 1 1

Interface circuit Interface circuit Interface circuit

device A device B device N

Fig. 4.7.4 A distributed arbitration scheme

 Memory
address
space Total
address
space

I/O
address space
 Memory Total
address address
space space I/O
address
space

(a) Memory space (b) I/O space

 Start I/O
routine

Get I/O port A

status register

Is
Yes Call the I/O port A
service request
bit set service routine
?

No

Get I/O port B

status register

Is
Yes Call the I/O port B
service request
bit set service routine
?

No

Get I/O port C

status register

Is
Yes Call the I/O port C
service request
bit set service routine
?

No

End
 Interrupt request
I/O
CPU system
Interrupt acknowledgment
 Assert interrupt
request line

Complete current
instruction
Interrupt
Main Program
service
routine

PC
Put current program

sh
Pu
counter value on stack

Load program counter

Po
with address of

p
PC
interrupt service routine RET

Execute interrupt
service routine

Execute return from

the interrupt

Continue where
interrupted

it
 INTR

Processor
Device Device Device
1 2 n
INTA

INTR
 INTR

INTR1

INTA1 Device Device

1 2

INTRn

INTAn Device Device

Processor 1 2

Priority arbitration
circuit
 Start

Initialize counter
Initialize source pointer

Initialize port address

Get byte

Send byte

No
Last byte ?

Yes

Stop
 CPU DMA
Start

Request I/O transfer Acknowledge

Send addresses of
source and destination Request bus
and number of bytes
to transfer

No
Bus free !

Yes

Perform other activities Activate address lines

Perform data transfer

Release bus

Total data
bytes No
transferred

Yes

Notify CPU of
Acknowledge
completion

Stop
 Data bus

Address bus

Control bus

RD WR RS DS DMA REQ
Data Data Address Control
counter register register I/O devices
logic
BG BR INTR DMA ACK

DMA
HLDA HOLD
NTR

Processor
EOP
 Start Start Start

Is
Is Is
I/O device No
I/O device No I/O device No ready for
ready for ready for
data transfer
data transfer data transfer
?
? ?
Yes
Yes Yes
DMA acquires
DMA acquires DMA acquires the control of
the control of the control of buses from processor
buses from processor buses from processor

Transfers one byte

Transfers one Transfers one
byte byte
Is
No terminal
DMA relinquishes count exhausted
control of buses to Is ?
terminal Is
processor No
count Yes I/O device Yes
exhausted ready for
? data transfer
Is ?
Is No I/O device
Yes No
terminal ready for
No data transfer
count
exhausted ? DMA relinquishes
control of buses to DMA relinquishes
? control of buses to
Yes processor
processor
Yes

Stop Stop Stop

(a) Single transfer (b) Block transfer (c) Demand transfer

 Processor Main memory

System bus

Disk DMA Keyboard

Printer
controller controller

Disk Disk Network

interface

Memory

Address

Bus Data

Control

HOLD DRQ Floppy Data

Disk Floppy Disk
Processor HLDA DMA DACK Controller Control Drive (FDD)
(FDC) status

Interrupt request

Interrupt request
DACK

EOP
 TX TX
DTE RX RX DCE
(Transmitter) (Receiver)
GND GND
 USB Cable
USB USB
Host Device(s)

Front view

Front view
2 1

1 2 3 4
3 4

(a) (b)
 1 1 0 0 1 1 0 1 0 0 1 0 0
Digital data

NRZI data

Digital data

NRZI data
1 2 3 4 5 6

Stuffed bit
 Start

Data absent
dle

Data present (Send data)

Clear count

Get bit

Bit = 0 Bit Bit = 1

status ?

nvert output

1
Output

0 Count = Count + 1

Is No
count = 6
?

Yes

Send sync
bit

Clear count

No
Transmission
over ?

Yes
 

8 bits 1 to 1023 Bytes 16 bits

PID Data CRC 16

(a) Data packet

8 bits 7 bits 4 bits 5 bits

PID ADDR ENDP CRC 5

(b) Token packet

8 bits
PID

(c)Handshaking packet

8 bits 11 bits 5 bits

PID Frame number CRC5

(d) Start of frame packet

X5  X 2  1
X 16  X 15  X 2  1