L02: Memory & Data I CMPT 295
Memory, Data, & Addressing I
http://xkcd.com/953/
L02: Memory & Data I CMPT 295
Roadmap
C:
Java:
Memory & data
Arrays & structs Integers & floats RISC V assembly Procedures & stacks Executables Memory & caches Processor Pipeline Performance Parallelism
car *c = malloc(sizeof(car)); c->miles = 100;
c->gals = 17;
float mpg = get_mpg(c); free(c);
Car c = new Car();
c.setMiles(100);
c.setGals(17);
float mpg =
c.getMPG();
Assembly language:
Machine code:
Computer system:
OS:
0111010000011000
100011010000010000000010
1000100111000010
110000011111101000011111
2
L02: Memory & Data I CMPT 295
Hardware: Physical View
I/O controller
Storage connections
Memory
USB…
CPU
(empty slot)
3
Bus connections
L02: Memory & Data I CMPT 295
Hardware: Logical View
CPU
Memory
Disks
Net
Bus
USB
Etc.
4
L02: Memory & Data I CMPT 295
Hardware: 295 View (version 0) ?
CPU
! The CPU executes instructions
! Memory stores data
! Binary encoding!
” Instructions are just data
How are data and instructions represented?
Memory
5
L02: Memory & Data I CMPT 295
Binary Encoding Additional Details
! Because storage is finite in reality, everything is stored as “fixed” length
” Data is moved and manipulated in fixed-length chunks
” Multiple fixed lengths (e.g. 1 byte, 4 bytes, 8 bytes)
” Leading zeros now must be included up to “fill out” the fixed length
! Example: the “eight-bit” representation of the number 4 is 0b00000100
Most Significant Bit (MSB)
Least Significant Bit (LSB)
6
L02: Memory & Data I CMPT 295
Hardware: 295 View (version 0) instructions
?
CPU
data
! To execute an instruction, the CPU must:
1) Fetch the instruction
2) (if applicable) Fetch data needed by the instruction
3) Perform the specified computation
4) (if applicable) Write the result back to memory
7
Memory
L02: Memory & Data I CMPT 295
Hardware: 295 View (version 1) instructions
take 300
CPU
! We will start by learning about Memory
How does a program find its data in memory?
Memory
data
registers
8
L02: Memory & Data I CMPT 295
Byte-Oriented Memory Organization
•••
! Conceptually, memory is a single, large array of bytes, each with a unique address (index)
” Each address is just a number represented in fixed-length binary
! Programs refer to bytes in memory by their addresses
” Domain of possible addresses = address space
” We can store addresses as data to “remember” where other data is in memory
! But not all values fit in a single byte… (e.g. 351) ” Many operations actually use multi-byte values
9
00•••0
FF•••F
L02: Memory & Data I CMPT 295
Peer Instruction Question
! If we choose to use 4-bit addresses, how big is our address space?
” i.e. How much space can we “refer to” using our addresses?
A. 16 bits
B. 16 bytes
C. 4 bits
D. 4bytes
E. We’re lost…
10
L02: Memory & Data I CMPT 295
Machine “Words”
! We have chosen to tie word size to address size/width ” word size = address size = register size
” word size = 𝑤 bits → 2𝑤 addresses
! Current x86 systems use 64-bit (8-byte) words
” Potential address space: 𝟐𝟔𝟒 addresses
264 bytes » 1.8 x 1019 bytes
= 18 billion billion bytes = 18 EB (exabytes)
” Actual physical address space: 48 bits
11
L02: Memory & Data I CMPT 295
Word-Oriented Memory Organization
! Addresses still specify locations of bytes in memory
” Addresses of successive words differ by word size (in bytes): e.g. 4 (32-bit) or 8 (64-bit)
” Address of word 0, 1, … 10?
64-bit 32-bit Words Words
Bytes
Addr. (hex)
0x00 0x01 0x02 0x03 0x04 0x05 0x06 0x07 0x08 0x09 0x0A 0x0B 0x0C 0x0D 0x0E 0x0F
Addr = ??
Addr = ??
Addr = ??
Addr = ??
Addr = ??
Addr = ??
12
L02: Memory & Data I CMPT 295
Word-Oriented Memory Organization
! Addresses still specify locations of bytes in memory
” Addresses of successive words differ by word size (in bytes): e.g. 4 (32-bit) or 8 (64-bit)
” Address of word 0, 1, … 10?
! Address of word
= address of first byte in word
” The address of any chunk of memory is given by the address of the first byte
” Alignment
64-bit 32-bit Words Words
Bytes
Addr. (hex)
0x00 0x01 0x02 0x03 0x04 0x05 0x06 0x07 0x08 0x09 0x0A 0x0B 0x0C 0x0D 0x0E 0x0F
Addr =
0 0? 0? 0
Addr =
0 0? 0? 8
Addr =
0 0? 0? 0
Addr =
0 0? 0? 4
Addr =
0 0? 0? 8
Addr =
0 0? 1? 2
13
L02: Memory & Data I CMPT 295
A Picture of Memory (64-bit view)
! A “64-bit (8-byte) word-aligned” view of memory: ” In this type of picture, each row is composed of 8 bytes
” Each cell is a byte ” A 64-bit pointer
will fit on one row
one word
0x00 0x01 0x02 0x03 0x04 0x05 0x06 0x07
0x00 0x 0x 0x 0x 0x 0x 0x 0x 0x
Address
14
L02: Memory & Data I CMPT 295
A Picture of Memory (64-bit view)
! A “64-bit (8-byte) word-aligned” view of memory: ” In this type of picture, each row is composed of 8 bytes
” Each cell is a byte ” A 64-bit pointer
will fit on one row
one word
0x00 0x01 0x02 0x03 0x04 0x05 0x06 0x07
Address
0x00 0x08 0x10 0x18 0x20 0x28 0x30 0x38 0x40 0x48
0x08 0x09 0x0A 0x0B 0x0C 0x0D 0x0E 0x0F
15
L02: Memory & Data I CMPT 295
64-bit example Addresses and Pointers (pointers are 64-bits wide)
big-endian
! An address is a location in memory
! A pointer is a data object that holds an address
” Address can point to any data
Address
! Value 504 stored at
address 0x08 0x08
0x00 “504 =1F8 0x10
00
00
00
00
00
00
01
F8
00
00
00
00
00
00
00
08
10 16 0x18 = 0x 00 … 00 01 F8 0x20
0x28
0x30 0x38 points to 0x38
! Pointer stored at
address 0x08
0x40 0x48
16
L02: Memory & Data I CMPT 295
64-bit example Addresses and Pointers (pointers are 64-bits wide)
big-endian
! An address is a location in memory
! A pointer is a data object that holds an address
” Address can point to any data ! Pointer stored at
0x48 points to address 0x38
” Pointer to a pointer!
! Is the data stored at 0x08 a pointer?
” Could be, depending on how you use it
Address
0x00 0x08 0x10 0x18 0x20 0x28 0x30 0x38 0x40 0x48
00
00
00
00
00
00
01
F8
00
00
00
00
00
00
00
08
00
00
00
00
00
00
00
38
17
L02: Memory & Data I CMPT 295
Data Representations
! Sizes of data types (in bytes)
Java Data C Data Type 32-bit x86-64 Type
boolean bool 1 1
byte char 1 1
char 22
short short int 2 2
int int 4 4
float float 4 4
long int 4 8
double double 8 8
long long 8 8
long double 8 16
(reference) pointer * 4 8
(reference) pointer * 4 8
To use “bool” in C, you must #include
address size = word
size
18
L02: Memory & Data I CMPT 295
Memory Alignment
! Aligned: Primitive object of 𝐾 bytes must have an address that is a multiple of 𝐾
” More about alignment later in the course
𝐾
Type
1
char
2
short
4
int, float
8
long, double, pointers
! For good memory system performance, data has to be aligned.
19
L02: Memory & Data I CMPT 295
Byte Ordering
! How should bytes within a word be ordered in memory?
” Example: store the 4-byte (32-bit) int: 0x a1 b2 c3 d4
! By convention, ordering of bytes called endianness
” The two options are big-endian and little-endian
• In which address does the least significant byte go?
• Based on Gulliver’s Travels: tribes cut eggs on different sides (big, little)
20
L02: Memory & Data I CMPT 295
Byte Ordering
! Big-endian (SPARC, z/Architecture)
” Least significant byte has highest address
! Little-endian (x86, x86-64, RISC-V)
” Least significant byte has lowest address
! Bi-endian (ARM, PowerPC)
” Endianness can be specified as big or little
! Example: 4-byte data 0xa1b2c3d4 at address 0x100 0x100 0x101 0x102 0x103
Big-Endian Little-Endian
0a1
2b32
4c35
6d74
0x100 0x101 0x102 0x103
6d74
4c35
2b32
0a1
21
L02: Memory & Data I CMPT 295
Peer Instruction Question:
! We store the value0x01020304as a word at address 0x100 in a big-endian, 64-bit machine
! What is the byte of data stored at address 0x104?
A. 0x04
B. 0x40
C. 0x01
D. 0x10
E. We’re lost…
23
L02: Memory & Data I CMPT 295
Endianness
! Endianness only applies to memory storage
! Often programmer can ignore endianness because it
is handled for you
” Bytes wired into correct place when reading or storing from memory (hardware)
” Compiler and assembler generate correct behavior (software) ! Endianness still shows up:
” Logical issues: accessing different amount of data than how you stored it (e.g. store int, access byte as a char)
” Need to know exact values to debug memory errors
” Software emulation machine code (assignment 2)
24
L02: Memory & Data I CMPT 295
Summary
! Memory is a long, byte-addressed array
” Word size bounds the size of the address space and memory
” Different data types use different number of bytes
” Address of chunk of memory given by address of lowest byte in chunk
” Object of 𝐾 bytes is aligned if it has an address that is a multiple of 𝐾
! Pointers are data objects that hold addresses
! Endianness determines memory storage order for multi-byte data
25