CMPEN
Lecture 3
331
•
Pitfall: MIPS as a Performance Metric
MIPS: Millions of Instructions Per Second
• Doesn’taccountfor
• Differences in ISAs between computers
• Differences in complexity between instructions
MIPS = Instruction count Execution time ´106
= Instruction count = Clock rate Instructioncount´CPI´106 CPI´106
Clock rate
n CPI varies between programs on a given CPU Chapter 1 — Computer Abstractions and Technology — 2
Instructions: Language of the Computer
CHAPTER 2
Assembly Language for Intel-Based Computers 5/e, 2007.
3
Instruction Set
• The repertoire of instructions of a computer
• Different computers have different instruction sets • Butwithmanyaspectsincommon
• Early computers had very simple instruction sets • Simplifiedimplementation
• Many modern computers also have simple instruction sets
Chapter 2 — Instructions: Language of the Computer — 4
Introduction
• Abitisthemostbasicunitofinformationina computer.
• It is a state of “on” or “off” in a digital circuit.
• Sometimes these states are “high” or “low” voltage instead of “on” or “off..”
• Abyteisagroupofeightbits.
• A byte is the smallest possible addressable unit of
computer storage.
• The term, “addressable,” means that a particular byte can be retrieved according to its location in memory.
5
The MIPS Instruction Set
• Usedastheexamplethroughoutthebook
• StanfordMIPScommercializedbyMIPS Technologies (www.mips.com)
• Largeshareofembeddedcoremarket
• Applications in consumer electronics, network/storage equipment, cameras, printers, …
• TypicalofmanymodernISAs Chapter 2 — Instructions: Language of the Computer — 6
Reminders
• Install MARS on your laptop
• Keep track of course updates on CANVAS
• Make sure your CSE account is operational
• Question/comments about the lab account/hardware/system, contact helpdesk@cse.psu.edu
• Questions about the programming assignments go to the course TAs
Chapter 1 — Computer Abstractions and Technology —7
Memory Organization
• Memory consists of many millions of cells
• Each cell holds a bit of information, 0 or 1
• Information is usually handled in larger units
• Awordisagroupofnbits
• Word length can be 16 to 64 bits but we will stick with 32 bits as a one word through out the semester
• Memory is a collection of consecutive words of the size specified by the word length
Computer Organization Embedded Systems 6e
Computer Organization Embedded Systems 6e
Primary Memory (2)
Three ways of organizing a 96-bit memory
Word and Byte Encoding
• A common word length is 32 bits
• Such a word can store a 32-bit signed integer or four 8-bit bytes (e.g., ASCII characters)
• For 32-bit integer encoding, bit b31 is sign bit
• Words in memory may store data or machine
instructions for a program
• Each machine instruction may require one or more consecutive words for encoding
Computer Organization Embedded Systems 6e
Computer Organization Embedded Systems 6e
Addresses for Memory Locations
• To store or retrieve items of information, each memory location has a distinct address
• Numbers 0 to 2k - 1 are used as addresses for successive locations in the memory
• The 2k locations constitute the address space
• Memory size set by k (number of address bits)
• Examples: k = 20 ® 220 or 1M locations, k = 32 ® 232 or 4G locations
Computer Organization Embedded Systems 6e
Byte Addressability
• Byte size is always 8 bits
• Impractical to assign an address to each bit
• Instead, provide a byte-addressable memory that assigns an address to each byte
• Byte locations have addresses 0, 1, 2, …
• Assuming that the word length is 32 bits, word locations have addresses 0, 4, 8, …
Computer Organization Embedded Systems 6e
Big
• Byte ordering, or endianness, is another major architectural consideration.
• Two ways to assign byte address across words
• Big-endian addressing assigns lower addresses to more significant (leftmost) bytes of word
• Little-endian addressing uses opposite order
• Addresses for 32-bit words are still 0, 4, 8, …
• Bits in each byte labeled b7 … b0, left to right
–
and Little
–
Endian Addressing
Computer Organization Embedded Systems 6e
–
and Little
–
Big
• Ifwehaveatwo-byteinteger,theintegermaybe stored so that the least significant byte is followed by the most significant byte or vice versa.
• In little endian machines, the least significant byte is followed by the most significant byte.
• Big endian machines store the most significant byte first (at the lower address).
16
Endian Addressing
Computer Organization Embedded Systems 6e
Big
• Asanexample,supposewehavethe hexadecimal number 0x12345678.
• Thebigendianandsmallendianarrangementsof the bytes are shown below.
–
and Little
–
Endian Addressing
18
Little Endian Order
• All data types larger than a byte store their individual bytes in reverse order. The least significant byte occurs at the first (lowest) memory address.
• Example:
12345678h
Irvine, Kip R. Assembly Language for Intel-Based Computers, 2007.
19
Word Alignment
• # of bytes per word is normally a power of 2
• Word locations have aligned addresses if they begin at byte addresses that are multiples of the number of bytes in a word
• Examples of aligned addresses:
2 bytes per word ® 0, 2, 4, … 8 bytes per word ® 0, 8, 16, …
Computer Organization Embedded Systems 6e
Memory Models
Figure 5-2. An 8-byte word in a memory. (a) Aligned. (b) Not aligned. Some machines require that words in memory be aligned.
Memory Operations
• Memory contains data & program instructions
• Control circuits initiate transfer of data and instructions between memory and processor
• Read operation: memory retrieves contents at address location given by processor
• Write operation: memory overwrites contents at given location with given data
Computer Organization Embedded Systems 6e
Instructions and Sequencing
• Instructions for a computer must support:
• data transfers to and from the memory • arithmetic and logic operations on data • program sequencing and control
• input/output transfers
Computer Organization Embedded Systems 6e
Register Transfer Notation
• Register transfer notation is used to describe
hardware-level data transfers and operations
• Arbitrary names for locations in memory
• Use […] to denote contents of a location
• Use ¬ to denote transfer to a destination
• Example: R2 ¬ [LOC]
(transfer from LOC in memory to register R2)
Computer Organization Embedded Systems 6e
Register Transfer Notation
• RTN can be extended to also show arithmetic operations involving locations
• Example: R4 ¬ [R2] + [R3]
(add the contents of registers R2 and R3,
place the sum in register R4)
• Right-hand expression always denotes a value, left- hand side always names a location
Computer Organization Embedded Systems 6e
Assembly
• RTN shows data transfers and arithmetic
• Another notation is needed to represent machine instructions & programs using them
• Assembly language is used for this purpose
• For the two preceding examples using RTN, the assembly-language instructions are:
lw R2, LOC add R4, R2, R3
–
Language Notation
Computer Organization Embedded Systems 6e
RISC and CISC Instruction Sets
• Nature of instructions distinguishes computer
• Two fundamentally different approaches
• Reduced Instruction Set Computers (RISC) have one-word instructions and require arithmetic operands to be in registers
• Complex Instruction Set Computers (CISC) have multi-word instructions and allow operands directly from memory
Computer Organization Embedded Systems 6e
RISC Instruction Sets
• RISC is simpler
• RISC instructions each occupy a single word
• A load/store architecture is used, meaning:
• only Load and Store instructions are used to access memory operands
• operands for arithmetic/logic instructions must be in registers, or one of them may be given explicitly in instruction word
Computer Organization Embedded Systems 6e
Real
• TheMIPSfamilyofCPUshasbeenoneofthemost successful in its class.
• In1986thefirstMIPSCPUwasannounced.
• Ithada32-bitwordsizeandcouldaddress4GBof memory.
• Overtheyears,MIPSprocessorshavebeenusedin general purpose computers as well as in games.
• TheMIPSarchitecturenowoffers32-and64-bit versions.
29
World Architectures
Real
• MIPSwasoneofthefirstRISCmicroprocessors.
• MIPSwasdesignedwithperformanceinmind:Itisa load/store architecture, meaning that only the load and store instructions can access memory.
• TheregistersintheMIPSarchitecturekeepsbus traffic to a minimum.
30
World Architectures
Arithmetic Operations
• Add and subtract, three operands • Twosourcesandonedestination
adda,b,c #agetsb+c
• All arithmetic operations have this form
• Design Principle 1: Simplicity favours regularity
• Regularitymakesimplementationsimpler
• Simplicityenableshigherperformanceatlowercost
Chapter 2 — Instructions: Language of the Computer — 31
§2.2 Operations of the Computer Hardware
Arithmetic Example
• C code:
f = (g + h) – (i + j);
• Compiled MIPS code:
addt0,g,h #tempt0=g+h addt1,i,j #tempt1=i+j subf,t0,t1 #f=t0-t1
Chapter 2 — Instructions: Language of the Computer — 32
Register Operands
• Arithmeticinstructionsuseregister operands
• MIPShasa32×32-bitregisterfile • Use for frequently accessed data
• Numbered 0 to 31
• 32-bit data called a “word”
• Assemblernames
• $t0, $t1, …, $t9 for temporary values • $s0, $s1, …, $s7 for saved variables
• DesignPrinciple2:Smallerisfaster • main memory: millions of locations
Chapter 2 — Instructions: Language of the Computer — 33
§2.3 Operands of the Computer Hardware
Register Operand Example
• C code:
f = (g + h) – (i + j);
• f,…,jin$s0,…,$s4
• Compiled MIPS code:
add $t0, $s1, $s2
add $t1, $s3, $s4
sub $s0, $t0, $t1
Chapter 2 — Instructions: Language of the Computer — 34
Memory Operands
• Mainmemoryusedforcompositedata • Arrays, structures, dynamic data
• Toapplyarithmeticoperations
• Load values from memory into registers • Store result from register to memory
• Memoryisbyteaddressed
• Each address identifies an 8-bit byte
• Wordsarealignedinmemory • Address must be a multiple of 4
• MIPSisBigEndian
• Most-significant byte at least address of a word
Chapter 2 — Instructions: Language of the Computer — 35
Memory Operand Example 1
• C code:
g = h + A[8];
• gin$s1,hin$s2,baseaddressofAin$s3
• Compiled MIPS code:
• Index8requiresoffsetof32 • 4 bytes per word
lw $t0, 32($s3) # load word
add $s1, $s2, $t0
offset base register
Chapter 2 — Instructions: Language of the Computer — 36
CMPEN
Lecture
4
331
Memory Operand Example 2
• C code:
A[12] = h + A[8];
• hin$s2,baseaddressofAin$s3
• Compiled MIPS code:
• Index8requiresoffsetof32
lw $t0, 32($s3)
add $t0, $s2, $t0
sw $t0, 48($s3)
# load word
# store word
Chapter 2 — Instructions: Language of the Computer — 38
Registers vs. Memory
• Registers are faster to access than memory
• Operating on memory data requires loads and stores • Moreinstructionstobeexecuted
• Compiler must use registers for variables as much as possible
• Onlyspilltomemoryforlessfrequentlyusedvariables • Registeroptimizationisimportant!
Chapter 2 — Instructions: Language of the Computer — 39
Immediate Operands
• Constant data specified in an instruction, add immediate
addi $s3, $s3, 4
• No subtract immediate instruction • Justuseanegativeconstant
addi $s2, $s1, -1
• Design Principle 3: Make the common case fast • Smallconstantsarecommon
• Immediateoperandavoidsaloadinstruction
Chapter 2 — Instructions: Language of the Computer — 40
The Constant Zero
• MIPS register 0 ($zero) is the constant 0 • Cannotbeoverwritten
• Useful for common operations • E.g.,movebetweenregisters
add $t2, $s1, $zero
Chapter 2 — Instructions: Language of the Computer — 41
Unsigned Binary Integers
• Given an n-bit number
nRange:0to+2n –1 n Example
n 0000 0000 0000 0000 0000 0000 0000 10112 =0+…+1×23 +0×22 +1×21 +1×20
= 0 + … + 8 + 0 + 2 + 1 = 1110
n Using 32 bits
n 0 to +4,294,967,295
n-1 n-2 1 0 x=xn-12 +xn-22 +!+x12 +x02
Chapter 2 — Instructions: Language of the Computer — 42
§2.4 Signed and Unsigned Numbers
2s
• Given an n-bit number
nRange:–2n–1 to+2n–1 –1 n Example
n 1111 1111 1111 1111 1111 1111 1111 11002 = –1×231 + 1×230 + … + 1×22 +0×21 +0×20 = –2,147,483,648 + 2,147,483,644 = –410
n Using 32 bits
n –2,147,483,648 to +2,147,483,647
–
Complement Signed Integers
n-1 n-2 1 0 x=-xn-12 +xn-22 +!+x12 +x02
Chapter 2 — Instructions: Language of the Computer — 43
2s
• Bit31issignbit
• 1 for negative numbers
• 0 for non-negative numbers
• Non-negativenumbershavethesame unsigned and 2s-complement representation
• Somespecificnumbers
• 0: 0000 0000 … 0000
• –1: 1111 1111 … 1111
• Most-negative: 1000 0000 … 0000
• Most-positive: 0111 1111 … 1111
–
Complement Signed Integers
Chapter 2 — Instructions: Language of the Computer — 44
Signed Negation
• Complement and add 1
• Complementmeans1→0,0→1
x+x=1111…111 =-1 2
x+1=-x
n Example: negate +2
n +2 = 0000 0000 … 00102
n–2=11111111…11012 +1 = 1111 1111 … 11102
Chapter 2 — Instructions: Language of the Computer — 45
Sign Extension
• Representinganumberusingmorebits • Preserve the numeric value
• InMIPSinstructionset
• addi: extend immediate value
• lb, lh: extend loaded byte/halfword
• Replicatethesignbittotheleft • unsigned values: extend with 0s
• Examples:8-bitto16-bit
• +2: 0000 0010 => 0000 0000 0000 0010 • –2: 1111 1110 => 1111 1111 1111 1110
Chapter 2 — Instructions: Language of the Computer — 46
Representing Instructions
• Instructionsareencodedinbinary • Called machine code
• MIPSinstructions
• Encoded as 32-bit instruction words
• Small number of formats encoding operation code (opcode), register numbers, …
• Regularity!
• Registernumbers
• $t0–$t7arereg’s8–15
• $t8–$t9arereg’s24–25 • $s0–$s7arereg’s16–23
Chapter 2 — Instructions: Language of the Computer — 47
§2.5 Representing Instructions in the Computer
MIPS R
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
• Instruction fields
• op:operationcode(opcode)
• rs:firstsourceregisternumber
• rt:secondsourceregisternumber
• rd:destinationregisternumber
• shamt:shiftamount(00000fornow)
• funct:functioncode(extendsopcode)
–
format Instructions
op
rs
rt
rd
shamt
funct
Chapter 2 — Instructions: Language of the Computer — 48
R
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
add $t0, $s1, $s2
–
format Example
op
rs
rt
rd
shamt
funct
special
$s1
$s2
$t0
0
add
0
17
18
8
0
32
000000
10001
10010
01000
00000
100000
000000100011001001000000001000002 = 0232402016
Chapter 2 — Instructions: Language of the Computer — 49