Transcript Formal Processor Verification

Processor Architecture
Architecture (I)
Goal
Understand basic computer organization

Instruction set architecture
Deeply explore the CPU working mechanism

How the instruction is executed: sequential and pipeline
version
Help you programming

–2–
Fully understand how computer is organized and works will
help you write more stable and efficient code.
Processor
CPU Design (Why?)
It is interesting.
Aid in understanding how the overall computer system
works.
Many design hardware systems containing processors.
Maybe you will work on a processor design.
–3–
Processor
CPU Design
Instruction set architecture
Logic design
Sequential implementation
Pipelining and initial pipelined implementation
Making the pipeline work
Modern processor design
–4–
Processor
Suggested Reading
- Chap 4.1, 4.2
–5–
Processor
Instruction Set Architecture #1
What is it ?

Assemble Language Abstraction

Machine Language Abstraction
Instruction Set
Architecture (ISA)
What does it provide?

An abstraction of the real computer, hide the details of
implementation
 The syntax of computer instructions
 The semantics of instructions
 The execution model
 Programmer-visible computer status
–6–
Processor
Instruction Set Architecture #2
Assembly Language View

Processor state
 Registers, memory, …

Instructions
 addl, movl, leal, …
 How instructions are encoded as
bytes
Layer of Abstraction

Above: how to program machine
 Processor executes instructions
in a sequence

Below: what needs to be built
Application
Program
Compiler
OS
ISA
CPU
Design
Circuit
Design
Chip
Layout
 Use tricks to make it run fast
 E.g., execute multiple
–7–
instructions simultaneously
Processor
Instruction Set Architecture #3
ISA define the processor family

Two main kind: RISC and CISC
 RISC:SPARC, MIPS, PowerPC
 CISC:X86 (or called IA32)

Another divide: Superscalar, VLIW and EPIC
 Superscalar: all the above
 VLIW: Philips TriMedia
superscalar:[计算机]超标量体系结构
 EPIC: IA64
Under same ISA, there are many different processors

From different manufacturers:
 X86 from Intel and AMD and VIA

Different models
 8086, 80386, Pentium, Pentium 4
–8–
Processor
Y86 Processor State
Program
registers
%eax
%esi
%ecx
%edi
%edx
%esp
%ebx
%ebp

P258 Figure 4.1
Condition
codes
Memory
OF ZF SF
PC
Program Registers
 Same 8 as with IA32. Each 32 bits

Condition Codes
 Single-bit flags set by arithmetic or logical instructions
» OF: Overflow

ZF: Zero
SF:Negative
Program Counter
 Indicates address of instruction

Memory
 Byte-addressable storage array
 Words stored in little-endian byte order
–9–
Processor
Y86 Instructions
P259 Figure 4.2
Format (P259)

1--6 bytes of information read from memory
 Can determine instruction length from first byte
 Not as many instruction types, and simpler encoding than with
IA32

Each accesses and modifies some part(s) of the program state
Errata: JXX and call are 5 bytes long.
– 10 –
Processor
Encoding Registers
P261 Figure 4.4
Each register has 4-bit ID
%eax
%ecx
%edx
%ebx

0
1
2
3
%esi
%edi
%esp
%ebp
6
7
4
5
Same encoding as in IA32, but IA32 using only 3-bit ID
Register ID 8 indicates “no register”

– 11 –
Will use this in our hardware design in multiple places
Processor
Instruction Example
P261 Figure 4.3
Addition Instruction
Generic Form
Encoded Representation
addl rA, rB

6 0 rA rB
Add value in register rA to that in register rB
 Store result in register rB
 Note that Y86 only allows addition to be applied to register data

Set condition codes based on result
e.g., addl %eax,%esi Encoding: 60 06

Two-byte encoding

 First indicates instruction type
– 12 –
 Second gives source and destination registers
Processor
Arithmetic and Logical Operations
Instruction Code
Add
addl rA, rB
Function Code
6 0 rA rB

Refer to generically as “OPl”

Encodings differ only by
“function code”
 Low-order 4 bytes in first
Subtract (rA from rB)
subl rA, rB
6 1 rA rB
And
andl rA, rB
instruction word


6 2 rA rB
Set condition codes as side
effect
Notice: no multiply or divide
operation
Exclusive-Or
xorl rA, rB
– 13 –
6 3 rA rB
Processor
Move Operations
rrmovl rA, rB
P259 Figure 4.2
Register --> Register
2 0 rA rB
3 0 8 rB
V
rmmovl rA, D(rB) 4 0 rA rB
D
5 0 rA rB
D
irmovl V, rB
mrmovl D(rB), rA
Register --> Memory
Memory --> Register

Like the IA32 movl instruction

Simpler format for memory addresses
Give different names to keep them distinct

– 14 –
Immediate --> Register
Distinct: 清楚的
Processor
Move Instruction Examples
IA32
Y86
Encoding
movl $0xabcd, %edx
irmovl $0xabcd, %edx
30 82 cd ab 00 00
movl %esp, %ebx
rrmovl %esp, %ebx
20 43
movl -12(%ebp),%ecx
mrmovl -12(%ebp),%ecx
50 15 f4 ff ff ff
movl %esi,0x41c(%esp)
rmmovl %esi,0x41c(%esp)
40 64 1c 04 00 00
movl $0xabcd, (%eax)
—
movl %eax, 12(%eax,%edx)
—
movl (%ebp,%eax,4),%ecx
—
– 15 –
Processor
Jump Instructions
P259 Figure 4.2
Jump Unconditionally
jmp Dest
7 0
Dest
Jump When Less or Equal
jle Dest
7 1
7 2
7 3
7 4
Encodings differ only by
“function code”
Based on values of condition
codes
Dest

Dest
Jump When Not Equal
jne Dest


Jump When Equal
je Dest
Refer to generically as “jXX”
Dest
Jump When Less
jl Dest

Dest

Same as IA32 counterparts
Encode full destination
address
 Unlike PC-relative
addressing seen in IA32
Jump When Greater or Equal
jge Dest
7 5
Dest
Jump When Greater
jg Dest
– 16 –
7 6
Dest
Processor
Y86 Program Stack
Stack “Bottom”
Region of memory holding
program data

Used in Y86 (and IA32) for
supporting procedure calls
Stack top indicated by %esp

•
Increasing
Addresses

 Address of top stack element
•

•
Stack grows toward lower
addresses
 Top element is at lowest address
%esp
Stack “Top”
– 17 –
in the stack
 When pushing, must first
decrement stack pointer
 When popping, increment stack
pointer
Processor
Stack Operations
pushl rA
a 0 rA 8

Decrement %esp by 4

Store word from rA to memory at %esp

Like IA32
popl rA
– 18 –
P259 Figure 4.2
b 0 rA 8

Read word from memory at %esp


Save in rA
Increment %esp by 4

Like IA32
Processor
Subroutine Call and Return
call Dest
Dest

Push address of next instruction onto stack

Start executing instructions at Dest
Like IA32

ret
9 0

Pop value from stack

Use as address for next instruction
Like IA32

– 19 –
8 0
P259 Figure 4.2
Processor
Miscellaneous Instructions
0 0
nop

Don’t do anything
halt
1 0

Stop executing instructions

IA32 has comparable instruction, but can’t execute it in
user mode
We will use it to stop the simulator

– 20 –
P259 Figure 4.2
Processor
Y86 Program Structure
irmovl Stack,%esp
rrmovl %esp,%ebp
irmovl List,%edx
pushl %edx
call len2
halt
.align 4
List:
.long 5043
.long 6125
.long 7395
.long 0
# Set up stack
# Set up frame
# Push argument
# Call Function
# Halt

Program starts at
address 0

Must set up stack
 Make sure don’t
overwrite code!
# List of elements


Must initialize data
Can use symbolic
names
# Function
len2:
. . .
# Allocate space for stack
.pos 0x100
– 21 –
Stack:
Processor
Assembling Y86 Program
unix> yas eg.ys

Generates “object code” file eg.yo
 Actually looks like disassembler output
0x000:
stack
0x006:
0x008:
0x00e:
argument
0x010:
Function
0x015:
0x018:
0x018:
0x018:
0x01c:
0x020:
0x024:
– 22 –
308400010000 |
irmovl Stack,%esp
2045
|
308218000000 |
a028
|
rrmovl %esp,%ebp # Set up frame
irmovl List,%edx
pushl %edx
# Push
8028000000
|
call len2
10
|
halt
| .align 4
| List:
|
.long
|
.long
|
.long
|
.long
b3130000
ed170000
e31c0000
00000000
# Set up
# Call
# Halt
# List of elements
5043
6125
7395
0
Processor
Simulating Y86 Program
unix> yis eg.yo

Instruction set simulator
 Computes effect of each instruction on processor state
 Prints changes in state from original
Stopped in 41 steps at
Changes to registers:
%eax:
%ecx:
%edx:
%esp:
%ebp:
%esi:
Changes to memory:
0x00f4:
0x00f8:
0x00fc:
– 23 –
PC = 0x16.
Exception 'HLT', CC Z=1 S=0 O=0
0x00000000
0x00000000
0x00000000
0x00000000
0x00000000
0x00000000
0x00000003
0x00000003
0x00000028
0x000000fc
0x00000100
0x00000004
0x00000000
0x00000000
0x00000000
0x00000100
0x00000015
0x00000018
Processor
Summary
Y86 Instruction Set Architecture

Similar state and instructions as IA32

Simpler encodings
Somewhere between CISC and RISC

How Important is ISA Design?

Less now than before
 With enough hardware, can make almost anything go fast

Intel is moving away from IA32
 Does not allow enough parallel execution
 Introduced IA64
» 64-bit word sizes (overcome address space limitations)
» Radically different style of instruction set with explicit parallelism
» Requires sophisticated compilers
– 24 –
Radically: 根本上
Processor
Logic Design
Digital circuit

What is digital circuit?

Know what a CPU will base on?
Hardware Control Language (HCL)


– 25 –
A simple and functional language to describe our CPU
implementation
Syntax like C
Processor
Category of Circuit
Analog Circuit

Use all the range of Signal

Most part is amplifier
Hard to model and automatic design



Use transistor and capacitance as basis
We will not discuss it here
Amplifier: 放大器
Transistor：晶体管
Capacitance: 电容
Digital Circuit

Has only two values, 0 and 1

Easy to model and design
Use true table and other tools to analyze



– 26 –
Use gate as the basis
The voltage of 1 is differ in different kind circuit.
 E.g. TTL circuit using 5 voltage as 1
Processor
Digital Signals
0
1
0
Voltage
Time

Use voltage thresholds to extract discrete values from
continuous signal

Simplest version: 1-bit signal
 Either high range (1) or low range (0)
 With guard range between them

Not strongly affected by noise or low quality circuit elements
 Can make circuits simple, small, and fast
– 27 –
Processor
Overview of Logic Design
Fundamental Hardware Requirements

Communication
 How to get values from one place to another



Computation
Storage (Memory)
Clock Signal
Bits are Our Friends


Everything expressed in terms of values 0 and 1
Communication
 Low or high voltage on wire

Computation
 Compute Boolean functions


– 28 –
Storage
Clock Signal
Processor
Category of Digital Circuit
Combinational Circuit

Without memory. So the circuit can’t have state. Any same
input will get the same output at any time.

Needn’t clock signal
Typical application: ALU

Sequential Circuit
– 29 –

= Combinational circuit + memory and clock signal


Have state. Two same inputs may not generate the same
output.
Use clock signal to control the run of circuit.

Typical application: CPU
Processor
Computing with Logic Gates
And
a
b
Or
out
out = a && b



P272 Figure 4.8
a
b
Not
out
out = a || b
a
out
out = !a
Outputs are Boolean functions of inputs
Not an assignment operation, just give the circuit a name
Respond continuously to changes in inputs
 With some, small delay
Rising Delay
Falling Delay
a && b
b
Voltage
a
– 30 –
Time
Processor
Combinational Circuits
Acyclic Network
Inputs
Outputs
Acyclic Network of Logic Gates
– 31 –

Continuously responds to changes on inputs

Outputs become (after some delay) Boolean functions of
inputs
Processor
Bit Equality
a
P272 Figure 4.9
Bit equal
HCL Expression
eq
bool eq = (a&&b)||(!a&&!b)
b

Generate 1 if a and b are equal
Hardware Control Language (HCL)

Very simple hardware description language
 Boolean operations have syntax similar to C logical operations

– 32 –
We’ll use it to describe control logic for processors
Processor
Bit-Level Multiplexor
s
Bit MUX
P273 Figure 4.10
HCL Expression
bool out = (s&&a)||(!s&&b)
b
out
a

Control signal s

Data signals a and b
Output a when s=1, b when s=0



– 33 –
Its name: MUX
Usage: Select one signal from a couple of signals
Processor
Word Equality
P274 Figure 4.11
Word-Level Representation
b31
a31
b30
Bit equal
Bit equal
eq31
B
=
A
eq30
a30
HCL Representation
Eq
b1
a1
b0
a0
– 34 –
Eq
Bit equal
Bit equal
bool Eq = (A == B)
eq1
eq0

32-bit word size

HCL representation
 Equality operation
 Generates Boolean value
Processor
Word Multiplexor
P275 Figure 4.12
Word-Level Representation
s
s
b31
B
out31
a31
b30
a0
– 35 –
Out
A
HCL Representation
int Out = [
s : A;
1 : B;
];
out30
a30
b0
MUX

Select input word A or B
depending on control signal s

HCL representation
 Case expression
out0
 Series of test : value pairs
 Output value for first successful
test
Processor
HCL Word-Level Examples
P277, P276
Minimum of 3 Words
C
B
A
MIN3
Min3
int Min3 = [
A < B && A < C : A;
B < A && B < C : B;
1
: C;
];


Find minimum of three
input words
HCL case expression

Final case guarantees
match

Select one of 4 inputs
based on two control
bits
HCL case expression
4-Way Multiplexor
s1
s0
D0
D1
D2
D3
– 36 –
MUX4
Out4
int Out4 = [
!s1&&!s0: D0;
!s1
: D1;
!s0
: D2;
1
: D3;
];


Simplify tests by
assuming sequential
matching
Processor
Arithmetic Logic Unit
0
Y
A
X
B

A
L
U
P278 Figure 4.13
1
Y
A
X+Y
OF
ZF
SF
X
A
L
U
B
2
Y
A
X-Y
OF
ZF
SF
X
B
3
Y
A
L
U
A
X&Y
OF
ZF
SF
X
B
A
L
U
X^Y
OF
ZF
SF
Combinational logic
 Continuously responding to inputs

Control signal selects function computed
 Corresponding to 4 arithmetic/logical operations in Y86


– 37 –
Also computes values for condition codes
We will use it as a basic component for our CPU
Processor
Storage
Registers

Hold single words or bits

Loaded as clock rises
Not only program registers

I
Random-access memories

Hold multiple words

E.g. register file, memory
Possible multiple read or write ports



– 38 –
O
Clock
Read word when address input changes
Write word as clock rises
Processor
Register Operation
P279 Figure 4.14
State = x
Input = y
Output = x
x
State = y

Rising
clock

Output = y
y

Stores data bits

For most of time acts as barrier between input and output
As clock rises, loads input

Barrier: 屏障
– 39 –
Processor
State Machine Example
Comb. Logic
0
A
L
U
0
Out
MUX
In
1
Load

Accumulator
circuit

Load or
accumulate on
each cycle
Clock
Clock
Load
In
Out
– 40 –
x0
x1
x0
x0+x1
x2
x0+x1+x2
x3
x4
x3
x3+x4
x5
x3+x4+x5
Processor
Random-Access Memory
P280
valA
srcA
A
valW
Register
file
Read ports
valB
srcB
W
dstW
Write port
B
Clock

Stores multiple words of memory
 Address input specifies which word to read or write

Register file
 Holds values of program registers
 %eax, %esp, etc.
 Register identifier serves as address
» ID 8 implies no read or write performed

Multiple Ports
 Can read and/or write multiple words in one cycle
– 41 –
» Each has separate address and data input/output
Processor
Register File Timing
Reading
valA
srcA
x
A

Register
file
valB
srcB
x
2

B
 After some delay
2
Writing
2

Like register

Update only as clock rises
x
valW
Register
file
W
Clock
– 42 –
Like combinational logic
Output data generated based on
input address
dstW
y
2

Rising
clock
2

y
valW
Register
file
W
dstW
Clock
Processor
Hardware Control Language

Very simple hardware description language

Can only express limited aspects of hardware operation
 Parts we want to explore and modify
Data Types

bool: Boolean
 a, b, c, …

int: words
 A, B, C, …
 Does not specify word size---bytes, 32-bit words, …
Statements
– 43 –

bool a = bool-expr ;

int A = int-expr ;
Processor
HCL Operations

Classify by type of value returned
Boolean Expressions

Logic Operations
 a && b, a || b, !a

Word Comparisons
 A == B, A != B, A < B, A <= B, A >= B, A > B

Set Membership
 A in { B, C, D }
» Same as A == B || A == C || A == D
Word Expressions

Case expressions
 [ a : A; b : B; c : C ]
 Evaluate test expressions a, b, c, … in sequence
– 44 –
 Return word expression A, B, C, … for first successful test Processor
Summary
Computation

Performed by combinational logic

Computes Boolean functions
Continuously reacts to input changes

Storage

Registers
 Hold single words
 Loaded as clock rises

Random-access memories
 Hold multiple words
 Possible multiple read or write ports
 Read word when address input changes
 Write word as clock rises
– 45 –
Processor