Transcript Storage System - Computer Architecture Laboratory @ KAIST

Lecture 5
Storage System
CS311-Computer Organization
Memory System
Lecture 5 -1
Lecture 5:
Memory System
In this lecture, we will study
• Storage Hierarchy
• Main Memory
– Main memory cell
» Static Cell and Dynamic Cell
– RAM
» Organization of RAM chip
» Construction Main Memory using RAM chips
» Dynamic RAM and Refreshing
– Main Memory Timing Parameters
• Memory Bus Architectures
– System Bus(single bus) architecture
– 2-Bus architecture
– Memory Bus and Multiple I/O Bus architecture
CS311-Computer Organization
Memory System
Lecture 5 -2
Lecture 5:
Memory System
In this lecture, we will study(Continue)
• Auxiliary Storage
– Magnetic Tape
– Disk
» Moving Head Disk
» Fixed Head Disk
• Characteristics of Storage
• Main Memory Addressing
–
–
–
–
–
Address Space and Storage Space
Method of accessing method using address
Method of representing address
Method of mapping address to the storage space
Precision of address
• Addressing patterns of programs
CS311-Computer Organization
Memory System
Lecture 5 -3
Memory System
•
•
Storage Access Time and Storage Capacity have been the
major limitations of the hardware resource to the
programmers
Thus when you design a storage system, Time and Space
must be traded off
– If you need a very fast storage access time, you should have a
large capacity main memory by sacrificing the storage capacity
– If you need a very large storage capacity, you should have the
secondary storage by sacrificing the storage access time
CS311-Computer Organization
Memory System
Lecture 5 -4
2 Types of Storage Systems
• System with a Single Storage System
– Main Memory only
– Embedded computers for simple applications
• System with Hierarchical Storage System
– Conventional system with Primary Memory and Secondary
Storage
– Primary Memory
» Random Accessible(addressable)
» Relatively small capacity
– Secondary Storage(Auxiliary Storage)
» Access through I/O class instructions via I/O bus or channel
» Slower and cheaper than main memory
CS311-Computer Organization
Memory System
Lecture 5 -5
Storage Hierarchy
Storage Hierarchy
– Different storage M1, M2, … , MS, with different characteristics
Storage
M1
M2
…
Capacity
S1
S2
…
MS
SS
Access Time
t1
t2
…
tS
Cost
C1
C2
…
S1<S2<…<ss
t1<t2<…<ts
C1>C2>…>Cs
CS
– Storage Hierarchy provides;
» Capacity: MS (Capacity = Capacity of the lowest level storage)
» Access Time: t1 (AT= AT of the highest level storage)
» Cost: CS (Cost= Cost of the lowest level storage)
e.g. M1- M2- M3 = Cache - Main Memory – Disk hierarchy
Capacity = Capacity of the Disk
Access Time = Access time of the Cache
Cost = Cost of the Disk
CS311-Computer Organization
Memory System
Lecture 5 -6
Memory Access
• Two Registers are needed in CPU for memory access
– MAR(Memory Address Register)
» A register that needs to be stored with address by CPU for memory access
– MBR(Memory Buffer Register or Memory Data Register)
» A register that stores data for memory access
» For Read access, memory puts the data read from memory
» For Write access, CPU puts the data to be stored in memory
• Read Access
– CPU stores address into MAR and the CU sends Read control signal to Memory
– Memory puts the data read from memory into MBR
– Read data appears in MBR after the memory access time
• Write Access
– CPU stores address in MAR and data in MBR and CU sends Write control signal
to Memory
– Storing data completes after the memory cycle time
CS311-Computer Organization
Memory System
Lecture 5 -7
Memory Access Time/Cycle Time
• Cycle Time
– Time from a memory access to the next memory access
• Access Time
– Time from sending an address and Read control signal to the
memory to the time when the read data is available
t
R
Read data
available
MBR
Send
address(MAR)
Send address
for the next access
Access Time
Cycle Time
CS311-Computer Organization
Memory System
Lecture 5 -8
Main Memory Timing
Parameters
2 different accesses;
2 different timing parameters;
–
– Read Access
MAR
address
Apply R(read) control signal to M
MBR
data
Access Time
From the time when address and
control signal R is applied to the
time when the data is in MBR.
– Write Access
Represents the time when the
read data is available.
MAR
address
MBR
data
– Cycle Time
Apply W(write) control signal to M From the time when address and
In general
Access Time < Cycle Time
control signal R is applied to the
time when the next address and
control signal R can be applied.
Represents how often memory
can be accessed.
CS311-Computer Organization
Memory System
Lecture 5 -9
Main Memory
Main Memory
• Only Storage that CPU can directly access
• Random Access Memory
– Random Access Memory is accessed by using Address
– Each location in which a unit of information can be stored is
assigned a unique address
– Address is used to access a unit of information at the desired
location
– Access time is constant, i.e., independent of memory location
or address
» Memory Access
• Read Access
• Write Access
CS311-Computer Organization
Memory System
Lecture 5 -10
Main Memory Organization
Memory System
•
•
•
•
•
•
•
Memory Cell
Memory Word(or Byte)
Block(or Page or Segment)
RAM Chip
Memory Module
Memory Bank
Memory System
Memory Bank
Memory Module
RAM
…
Memory Module
RAM
…
...
RAM
RAM
...
Memory Bank
Memory Module
RAM
…
RAM
CS311-Computer Organization
Memory System
Memory Module
...
RAM
…
RAM
Lecture 5 -11
Time Out
•
매일 매일 일 때문에 바쁘게 살아가는 부부가 있었다.
•
큰 아들이 신병훈련을 마치고 퇴소식을 갖게 되었으므로 부부는 그 식에
참석하러 가기로 했다.
•
그들은 이 번 여행을 그들 둘만의 특별한 여행으로 만들고 싶었다.
•
그들은 아들과 헤어진 후 five star 호텔에 투숙해서 호화판 저녁식사를
하며 즐겁게 보낸 다음 호텔 방으로 올라갔다.
•
약 15분쯤 지나서 누가 방문을 두드렸다. 방문을 열어보니 아들이 환하게
웃으며 서 있었다.
•
“어머니 오늘 저녁을 어머니 아버지와 함께 지내려고 왔어요!”
CS311-Computer Organization
Memory System
Lecture 5 -12
Model of a Memory Cell
SEL(address bit)
SEL
DI
S
DO
Q
SRF
R
DI
Q’
cell
DO
R
R(1: Read, 0: Write)(control signal)
For an Access:
SEL=1
Read:
Write:
CS311-Computer Organization
Memory System
SEL . R
SEL . R’
Lecture 5 -13
SRAM - Static Memory Chip
Static RAM - SRAM
– Preserve stored information as long as the power is on:
Access Time and Cycle Time are approximately equal
– Current demand is steady -> low cost power supply is OK
– A cell is made of several transistors, thus chip density is
lower than DRAM
– Chip is organized in the form of (n x m)-bit(cell)
» Allows to access m bits(usually m=8, a byte) in one access
– Faster access time and more expensive than DRAM - For
small quantity applications, SRAM pays off
CS311-Computer Organization
Memory System
Lecture 5 -14
DRAM - Dynamic Memory Chip
Dynamic Cell - DRAM
– Information is stored in the form of charge, thus, stored
information is discharged as the time elapses even if power is on
– Made of a single transistor, thus chip density is higher than
SRAM
– To preserve the stored information, needs periodic refresh,
Refresh Cycle (2mSec)
» Peak load for current
» Usually refresh logic is provided on the chip
» Access Time < Cycle Time
– Chip is organized in the form of (n x 1)-bit
» Allows to access 1 bit per access
– Much slower access time than SRAM
» For large capacity applications, DRAM pays off
CS311-Computer Organization
Memory System
Lecture 5 -15
DRAM - Refresh
Refresh Operation
Cell
Array
...
[1] All the cells in a selected row are read to the particular
cells, one for each column in an extra row
[2] From this extra row, cells in the selected row are
recharged
Refresh Buffer
• Refresh by 1 row at a time, all the cells in a row together
1 refresh operation requires the Row Address
m rows require m refresh operations
• Refresh Counter
Provides a Row Address for a refresh operation
Counter advances for the next row address to refresh
CS311-Computer Organization
Memory System
Lecture 5 -16
Refresh Methods
Refresh Methods
Transparent
1/2 of memory cycles to CPU and I/O and 1/2 for refresh
Cycle Steal
A Time-out signal generates a cycle steal request at the
period of (Refresh Cycle Time / Number of row) to refresh
a row
Burst
Refresh request is made in every refresh cycle to refresh all
rows, one row by one in succession
CS311-Computer Organization
Memory System
Lecture 5 -17
Cell Layout in RAM
Square layout of cells
- Accommodate largest
number of cells in the
same chip area
- e.g. 64 x 64 layout
CS311-Computer Organization
Memory System
Lecture 5 -18
(8 x 8) RAM Chip Organization
DI0
DI1
DI2
...
Write Amplifier
DI
0,0
0,1
0,7
SEL
DO
R
1
1,0
1,1
1,2
1,7
DI0 DI1 DI2 . . . DI7
2
2,0
2,1
2,2
a0
a1
a2
2,7
8x8
CS
R/W
DO0 DO1 DO2 . . . DO3
7
7,0
R/W
0,2
...
Address Decoder
Address
a2
CS
...
0
a0
a1
DI8
Chip
Select
7,1
Read Buffer/Sense Amplifier
DO0
CS311-Computer Organization
7,2
DO1
DO2
Memory System
7,7
...
DO7
Lecture 5 -19
Construction of Memory
with RAM
(n × m) Memory using (p × q) RAM
– Number of chips to get m-bit word = m/q
– Number of chips to get n words = n/p
– Number of chips to get (n x m) memory = n/p × m/q
e.g. Construction of (1K × 32) Memory
– (8 × 8) RAM Chips
1024/8 × x 32/8 = 128 × 4 = 512
– (64 × 1) RAM Chips
– 1024/64 × 32/1 = 16 × 32 = 512
CS311-Computer Organization
Memory System
Lecture 5 -20
(16 x 16) Memory
Using (8 x 8) RAM
Data Bus (d8 ~ d15)
Data Bus (d0 ~ d7)
Address Bus (a0a1a2)
Address Bus (a3)
...
DI’s
U0 CS
R/W
DO’s
...
a0
a1
a2
DI’s
DI’s
U1 CS
R/W
DO’s
...
...
a
a00
a11
a22
DI’s
U2 CS
R/W
DO’s
...
...
a0
a1
a2
DI’s
CS
U3 R/W
DO’s
...
Memory Bus
a0
a1
a2
...
Control Bus(R/W)
CS311-Computer Organization
Memory System
Lecture 5 -21
Refreshing DRAM:
Refresh Counter
A0
32 x 32 DRAM array
A1
A2
A3
A4
Refresh
A0
A1
A2
A3
A4
a0
CS311-Computer Organization
a1
a2
Memory System
a3
a4
To memory
Lecture 5 -22
Memory Bus Architecture
System Bus - Simple single bus
Main
Memory
System Bus
CPU
I/O
...
I/O
– Most often found in low cost PCs
– Single bus prevents concurrent data transfers
– CPU communicates with and controls I/O devices as it
accesses memory
– Both roles of memory and I/O buses, value on the
address bus determines role of the bus
CS311-Computer Organization
Memory System
Lecture 5 -23
2-Bus Architecture
I/O Bus
Memory Bus
Main
Memory
CPU
I/O
Controller
(DMAC)
I/O
Device
...
I/O
Device
– CPU communicates with I/O over I/O Bus
– CPU and DMA Controller access memory over Memory Bus
– Permits high speed Memory Bus with short interconnection
length
– I/O data and I/O address bus width can be narrower than
Memory Bus
– Multi-port memory has internal scheme which handles and
coordinates each port
CS311-Computer Organization
Memory System
Lecture 5 -24
Memory Bus/Multiple I/O
Bus Architecture
Main
Memory
Memory Bus
CPU
I/O
Channel
...
I/O
Channel
To I/O Controllers and/or Adapters
– CPU, I/O Channels, and Memory communicate over Memory Bus
– Several channels can be active at the same time
– I/O channel multiplexes slower devices
CS311-Computer Organization
Memory System
Lecture 5 -25
Oak Valley resort in Fall
CS311-Computer Organization
Memory System
Lecture 5 -26
Auxiliary Storage
CS311-Computer Organization
Memory System
Lecture 5 -27
Auxiliary Storage
• Sequential Access Storage Device(SASD)
– Magnetic Tapes
» Reel Tape
» Cassette, cartridge
• Direct Access Storage Device(DASD)
– Magnetic Disks
» Moving head disk - Diskette
» Fixed head disk - Hard disk
CS311-Computer Organization
Memory System
Lecture 5 -28
Magnetic Tape
File i
Storage Organization
– Store Files, separated by EOF
– Files consist of Blocks, separated
by IRG(inter-record gap)
– Blocks contain Records, a basic
information unit
block
block
R1 R2 R3
R4 R5
block
IRG
EOF
Tape Access - to read record R4 in Filei
– Read in forward direction until
EOF of Filei-1
– Continue read in forward direction
Until the first IRG
– Continue read
– Sequential Access
CS311-Computer Organization
Memory System
Lecture 5 -29
Magnetic Disk
Moving Head Disk
Fixed Head Disk
Sector m
Sector 0
Track 0
Track 1
Track m
Track
Tracks
CS311-Computer Organization
Surface
Memory System
Cylinder
Lecture 5 -30
Magnetic Disk
Address
Drive No. / Surface No. / Track(Cylinder) No. / Sector No.
Random Accessible Storage
Access Time
– Seek Time consists of
» Time to position the read/write head to the desired track
» Intra-Cylinder access does not need seek time
» Fixed Head Disk does not have seek time unless current access
requires to access from the different disk drive
– Head Switching Time
» Time to activate a head when the head used for the last access is
different from the one that is going to be used for the current
access
» Both Moving and Fixed Head Disk require head switching time
CS311-Computer Organization
Memory System
Lecture 5 -31
Access Characteristics
of Storage Systems
Access Time
RAM
DASD
SASD
Seek Time
Distance of Storage Locations
CS311-Computer Organization
Memory System
Lecture 5 -32
Memory Bandwidth
Use of Memory Bandwidth
CPU - Read Instructions from memory
Memory
Read Operands from memory
Store Results to memory
Memory Bus
CPU
I/O
DASD
or
SASD
I/O
Dev
...
I/O
Dev
- Initially read Program and Data from input device to memory
CPU and I/O device(s) are competing
before
running
to use memory bus, causing a
- (Read
Operands
from Bus
input device to Memory for processing)
Bottleneck
at the Memory
- Write the Results of execution of the program to the output
device
CS311-Computer Organization
Memory System
Lecture 5 -33
Address
• Address
– Assigned to each stored object to retrieve the object later via its
address
– Eventually needed to be mapped onto a physical memory
location
– In most current systems, an Address and a Memory Location are
distinct concepts related by the Mapping Function
– 1-1 mapping implies that the an address and the memory location
are referred to synonymously
• Address Space
Address Space
Addresses visible
to programmers
CS311-Computer Organization
Memory Space
Mapping
Function
Memory System
Storage
Locations
Lecture 5 -34
Address Design Considerations
• Efficient Specifications of addresses
• Independence of Address Space
• Services to users
CS311-Computer Organization
Memory System
Lecture 5 -35
Address Design Considerations:
Address Specification Efficiency
– Space considerations
» Minimize the umber of bits to specify address in an instruction
» Minimize the size of mapping tables, descriptors, etc
– Time considerations
» Minimize time to retrieve an operand, and update the address
structure
» Minimize the time for automatic generation of addresses by
compiler
CS311-Computer Organization
Memory System
Lecture 5 -36
Address Design Considerations:
Independence of Address Space
– Relocatability
» Speedy relocation of user jobs in Multiprogramming
environment
» Make the garbage collection fast
– Portability
» By uncoupling the address space from memory space
program for one computer can be run in different
computers
CS311-Computer Organization
Memory System
Lecture 5 -37
CS311-Computer Organization
Memory System
Lecture 5 -38
Multiprogramming
• CPU is the most expensive hardware resource
– With respect to Memory, Secondary storage(such as disks), I/O
• We would like to keep the CPU busy all the time
• What makes CPU from busy all the time?
– Mainly I/O operations including disk accesses
• What can we do about it so that the expensive CPU time
cannot be wasted?
– Provide more jobs, i.e., have multiple of programs in the
memory which are ready to be executed
– When the execution of one job causes CPU idle, immediately
initiate another job ready to be executed in the memory
CS311-Computer Organization
Memory System
Lecture 5 -39
Multiprogramming
Job 1
Job 2
Job
Job 33
Job4
Waiting
Job
CS311-Computer Organization
Memory System
Waiting
Job
Job 5
Waiting
Job
Lecture 5 -40
Multiprogramming:
Relocation
Job 1
Job 2
Waiting
Job 3
Job
Job4
Job4
Job 5
Waiting
Job
CS311-Computer Organization
Memory System
Lecture 5 -41
Multiprogramming:
Relocation
Job
Job4
1
Job 2
Waiting
Job 3
Job
Job4
Job 5
Waiting
Job
Job4
CS311-Computer Organization
Memory System
Lecture 5 -42
Multiprogramming:
Garbage Collection
Job 1
Job
Job
2 2
Job 6
CS311-Computer Organization
Job 3Job 3Job4Job4
Job7
Memory System
Job 5
Job 8
5
Job 8
Lecture 5 -43
Address Design Considerations:
Services to Users
– Provide illusion of much larger memory than the actual
» virtual storage
– Provide Protection and Sharing for Multiprogramming
Sub A
job1
job2
Job3
(currently running)
Reference
that needs
protection;
• Security
• Privacy
job1 Sub A
job2
Sub A
Job3
(currently running)
job4 Sub A
job4
CS311-Computer Organization
Shared
Routine
Memory System
Lecture 5 -44
Time Out
• 오래 전부터 사업상 알고 지내는 두 남자가 함께 거리를 걸어가던
중 한 남자가 당황해 하며 말했다.
• “야단났네, 내 마누라가 내 정부와 함께 이리로 오고 있어.”
• “어이쿠!” 다른 남자가 말했다. “내 마누라와 정부도 함께 이리로
오고 있는데.”
CS311-Computer Organization
Memory System
Lecture 5 -45
Basic Addressing Modes
OP-code
Ri
Rx
X
Ri: Arbitrary address register
Rx: Index Register
Rb: Base Address Register
Modes
Operand
Register Direct
Immediate
Direct
Register Indirect
[Ri]
X
M[X]
M[[Ri]]
Base + Displacement
Indexed;
Auto-increment
Auto-decrement
Base + Index
Register-Memory Indirect
Memory Indirect
M[[Rb] + X]
M[X + [Rx]];
[Rx] [Rx]+1
[Rx] [Rx]-1
M[[Rb] + [Rx] + X]
M[M[[Ri]]]
M[M[X]]
CS311-Computer Organization
Memory System
Lecture 5 -46
Properties of address:
Operand Access Method from the
Specified Address
• Direct Address:
ADD X
(EFA=X; AC <= AC+M[X] )
– 1 memory access per operand
– Consumes a lot of instruction bits for a direct address
• Indirect Address
ADD @X
(EFA=M[X]; AC <= AC+M[M[X]] )
– At least 2 memory accesses per operand
– Indirect by a bit flag(if MSB of the accessed address is 1 then further indirect)
– Register indirection : 1 memory + 1 reg accesses per operand access
• Calculated Address
ADD $X
(EFA=M[X+[R]]; AC <= AC+M[X+[R]])
– 1 memory access + 1 register access plus calculation per operand
– Little shorter than direct address --> saves instruction bits
• Immediate Address
ADD #X
(EFA=na; AC <= AC+X)
– No memory access for operand
– Consumes a lot of instruction bits
CS311-Computer Organization
Memory System
Lecture 5 -47
Example
ADD
100
Make an addition of the number 50 stored in AC(data register in CPU) and the
operand obtained using 100.
Assume that an address register Rb(Base Address Register) contains 150.
What would be the results of additions?
250
213
200
200
125
100
100 is a direct address : 50 + 200 = 250
100 is an indirect address: 50 + M[M[100]] = 50 + M[200] = 50 + 125 = 175
100 is a calculated address using Rb: 50 + M[100 + [Rb]] = 50 + M[250]
= 50 + 213 = 263
100 is an immediate address: 50 + 100 = 150
CS311-Computer Organization
Memory System
Lecture 5 -48
Properties of address:
Method of Representing Address
• Full Address
LDA
X
(EFA=X; AC<-M[X])
– Requires the largest number of bits(instruction becomes long)
• Abbreviated Address
LDA
X
(EFA=[R]+X; AC<-M[[R]+X])
– Fewer number of bits for an address(X), but uses a register
– Usually, part of an address is in a register which is implied
– Register includes Base Address, Page Address, Segment Address, ...
• Implied Address
ADD
X
( AC is implied)
– No space(bit) at all(instruction becomes short) when there is a unique
operand register
– Accumulator in 1-address machines
– Stack(top) in 0-address machines
• Immediate Address
ADD
X
(AC<-X)
– No instruction bits for address, but for operand(instruction becomes long)
– Large number of instruction bits
CS311-Computer Organization
Memory System
Lecture 5 -49
Abbreviating/Implying Address
• Implying Address
– When the desired operand is stored in a unique special
register
» AC, Stack
• Abbreviating Address
– When the desired operand is stored in the adjacent to the
address stored in the special address registers
– Address in the instruction needs to be specified only a few
least significant bits, remainder of address is stored in a
special address register;
» PC
1236
register
» Base Address Register
+24
» Index Register
1260
operand
address
» Page/Segment Address Register
24 is shorter than 1260
CS311-Computer Organization
Memory System
Lecture 5 -50
Page/Segment
- Page Page
– Page is a hardware concept, nothing to do with the program
– A page is a fixed length contiguous block of words
– In a Paged Memory, entire memory is partitioned into pages
which are equal size, and there is a unique Page Address
Register that stores the address of the starting location of the
page
– In a paged memory, a stored object is addressed in relative
location to the address stored in PAR(Page Address Register)
» Effective address = PAR + displacement within the
page(specified addr)
CS311-Computer Organization
Memory System
Lecture 5 -51
Page/Segment
- Segment Segment
– Segment is a software concept
– A segment is a variable length contiguous block of words
» A program consists of several procedures may be
partitioned such that each procedure becomes a segment
– A stored object is addressed in relative to the address stored
in SAR(Segment Address Register)
» Effective address=SAR+displacement within the
segment(specified addr)
CS311-Computer Organization
Memory System
Lecture 5 -52
Paged/Segmented Memory
Paged System
...
Segmented System
Paged Segment System
...
Fragmentation
CS311-Computer Organization
Memory System
Lecture 5 -53
Properties of address:
Method of Mapping Address Space
to the Memory Space
• Absolute Address
• Relative Address
ADD X
ADD X
(EFA=X )
(EFA=[BAR] + X)
– Address should be related to Statically or Dynamically assigned
Base Address Register(BAR)
– Base Address may be implied(CDC 600: Dynamic Relocation) or
specified(IBM S/360: Static Relocation) using a GPR
– Displacement(X) must be specified, but can be abbreviated
• Capability Address
ADD X
(EFA=[S]+X)
– A pass to use an object stored in memory
– A unique code(S) for each segment created and never used again even
if the segment disappears
– For a given code, hardware finds the base-address and size of the
segment in the memory
Relocation : Possible by both relative and capability addresses
Protection and Sharing: Capability is stronger
CS311-Computer Organization
Memory System
Lecture 5 -54
Relocation with
Relative Addressing
BAR
100
ADD
X(BAR)
X
BAR
500
100
[BAR]
+
100
101
102
103
104
A0
A1
A2
A3
A4
…
100+X
.
AX
148
149
A148
A149
Relocation
Base + Displacement
addressing makes
relocation very easy
CS311-Computer Organization
500
501
502
503
504
…
500+X
.
548
549
A0
A1
A2
A3
A4
AX
A148
A149
Relocation operation
1. Change content of BAR
2. Instruction does not change
ADD X(BAR)
Memory System
Lecture 5 -55
Protection with
Segment Addressing
Memory
Memory
Sharing
- 2 sets of BAR/FL or Limit
- 1 set for individual user
and 1 set for shared area
BAR
FL
Limit
CS311-Computer Organization
Memory System
Lecture 5 -56
Properties of address:
Method of Modifying Address
• Manual by programmer
• Self Modifying program codes
– Program modifies the address part of an instruction
– Sometimes unpredictable
– Reentrant procedure is not possible
Y
ADD
[X]
JMP Y
X
[X]+1
Y
ADD
[R]
JMP
$X
[R]+1
Y
Y
ADD
JMP
$X
Y
• Modification not of program but of registers by program
– Flexible for programming
– Powerful
– Permit pure reentrant code
• Automatic modification by system
– Automatic indexing and loop control
– Hardware and Software triggered table updates
– Base Address Register in CDC 6000 series
CS311-Computer Organization
Memory System
Lecture 5 -57
Automatic Mapping
and Automatic Indexing
• Automatic Mapping
– Relieves programmers of device dependent details
– Implement some level of protection and relocatability
– Global optimization of space usage and portability
• Automatic Indexing
– Efficient operations on vectors, arrays
– Loop control by controlled sequencing and branch(BXH, BXL,
BCT, …)
CS311-Computer Organization
Memory System
Lecture 5 -58
Properties of address:
Resolution of Address
• Resolution of address
– Bit, Byte, Word, Page
– Hierarchy of address resolutions
– Greater resolution implies more bits for specification for
greater flexibility
• Length of the addressed operands
– Implicit(fixed to one word)
– Variable length
» Specified explicitly in each instruction
» Specified by a register
» Specified by delimiter marks associated with the data
> reserved-bit delimiter(field or word mark)
> reserved-bit configuration(record or group mark)
» Direction of processing
> right to left for arithmetic
> Left to right(or right to left) for moving
CS311-Computer Organization
Memory System
Lecture 5 -59
Addressing Patterns of Programs(1):
Locality of Reference
Locality of Reference
During an interval of execution, a program favors a relatively small
subset of Pages, and this set of favored pages changes membership
slowly.
Reasons
Context: A program executes within a particular context
Looping: Programs tend to loop within a small set of pages
Spatial Locality:
There is a high probability that a set of data, whose address
differences are small, will be accessed in small time difference.
Temporal Locality:
There is a high probability that the recently referenced data will be
referenced in near future.
CS311-Computer Organization
Memory System
Lecture 5 -60
Addressing Patterns of Programs(2):
Generation of Multiple EFA from
One Written Address
The number of written addresses in a program is much less
than the number of executed effective addresses
Calculated addresses: Many different executed addresses are
generated from a given written address
in the program
– Automatic Indexing
– Relocation
– Temporary Registers
CS311-Computer Organization
Memory System
Lecture 5 -61
Addressing Patterns of Programs(3):
Reference Patterns of
Instruction and Data
References to data tend to be more random than references to
instructions, which tend to sequential except for branches,
procedure calls and returns, interrupts
Run-length = Number of sequential addresses in an addressing
pattern
Expected instruction stream run-length:
14.4 words
7~8 words(Stanford)
Expected data stream run-length:
1 word
CS311-Computer Organization
Memory System
Lecture 5 -62
Improving Addressing Mechanism
Using Properties of Address
Improve address specification
– Locality
» Use residual control to reduce the number of bits required
for an address(abbreviated address)
– Number of effective addresses >> written addresses
» Existence of temporaries, array processing
> Use registers, stacks to imply address to reduce
instruction length
> Use auto-indexing for array processing
– Based on Run-length
» Use of separate memory for instructions and data and use
of different algorithms to optimize access
CS311-Computer Organization
Memory System
Lecture 5 -63