Transcript Abstractions and MAL

Abstractions and Computers and
the MAL programming Language
1
Computer Architecture
Definition: Interface between a computers
hardware and its software. Defines exactly what
the computer’s instructions do, and how they
are specified.
Instruction Set Architecture (ISA)
CMPE12c
2
Gabriel Hugh Elkaim
Computer Architecture
• SAL – Simple Abstract Language
• MAL – MIPS Assembly Language
• TAL – True Assemble Language
SAL
CMPE12c
MAL
TAL
3
MIPS
machine language
Gabriel Hugh Elkaim
Computer Architecture
High
Level
Language
Compiler
Assembly
Assembler Machine
Language
Language
Compiler: A computer program that translates code
written in a high level language into an intermediate
level abstract language.
CMPE12c
4
Gabriel Hugh Elkaim
Computer Science
Definition: Fundamentally the study of
algorithms and data structures.
Abstraction: Use of level of abstraction in
software design allows the programmer to
focus on a critical set of problems without
having to deal with irrelevant details.
CMPE12c
5
Gabriel Hugh Elkaim
Computer Science
Procedure or Function
int average (a, b)
begin
avg = (a+b)/2;
return (avg);
end
CMPE12c
main ()
…
x = 4;
y = 2;
k = average (x,y);
printf (“%d”, k);
…
6
Gabriel Hugh Elkaim
Computer
CPU
(MIPS)
Control info
Write data
Memory
Read data
CPU Interacts with the memory in 3 ways:
• fetches instructions
• loads the value of a variable
• stores the new value of a variable
Memory is capable of only 2 operations:
• reads – a load or a fetch
• writes – operation of a storing the value of a variable
CMPE12c
7
Gabriel Hugh Elkaim
CMPE12c
8
Gabriel Hugh Elkaim
Instruction Fetch / Execute
Cycle
In addition to input & output a program also:
•Evaluates arithmetic & logical functions to
determine values to assign to variable.
•Determines the order of execution of the
statements in the program.
In assembly this distinction is captured in the notion
of Arithmetic, logical, and control instructions.
CMPE12c
9
Gabriel Hugh Elkaim
Instruction Fetch / Execute Cycle
Arithmetic and logical instructions evaluate variables
and assign new values to variables.
Control instructions test or compare values of a
variable and makes decisions about what instruction is to
be executed next.
Program Counter (PC)
Basically the address at which the current executing
instruction exists.
CMPE12c
10
Gabriel Hugh Elkaim
Instruction Fetch / Execute Cycle
Address
CMPE12c
1.
2.
3.
4.
5.
6.
7.
8.
load rega, 10
load regb, 20
add regc, rega, regb
beq regc, regd, 8
store regd, rege
store regc, regd
load regb, 15
load rega, 30
11
PC
Gabriel Hugh Elkaim
Instruction Fetch / Execute Cycle
The CPU begins the execution of an instruction
by supplying the value of the PC to the memory &
initiating a read operation (fetch).
The CPU “decodes” the instruction by identifying
the opcode and the operands.
PC increments automatically unless a control
instruction is used.
CMPE12c
12
Gabriel Hugh Elkaim
Instruction Fetch / Execute Cycle
For example:
PC  add A, B, C
• CPU Fetches Instruction
• Decodes it and sees it is an add operation,
needs to get values for the variables “B” & “C”
• CPU executes a load operation, gives
address of variable “B”
• Does the same for variable “C”
• Does the “add” operation and stores the
result in location of variable “A”
CMPE12c
13
Gabriel Hugh Elkaim
Instruction Fetch / Execute Cycle
Branch – like a goto instruction, next instruction to
be fetched & executed is an instruction other than
the next in memory.
fred:
CMPE12c
add A, B, C
beq A, 5, fred
sub A, D, 3
sub A, D, 4
If A==5 then next
instruction is at
fred
14
Gabriel Hugh Elkaim
Breaking down an instruction
add a, b, c
add
a b c
Source registers
Opcode
Destination register
CMPE12c
15
Gabriel Hugh Elkaim
Locality of reference
We need techniques to reduce the instruction
size. From observation of programs we see that a
small and predictable set of variables tend to be
referenced much more often than other variables.
CMPE12c
16
Gabriel Hugh Elkaim
Basically, locality is an indication that
memory is not referenced randomly.
This is where the use of registers comes
into play.
CMPE12c
17
Gabriel Hugh Elkaim
Registers and MAL
IO
Memory
(disk)
ALU
Memory Ctrl
Data cache
Inst. cache
Register
Array
Program “code” is in memory (or cache), use registers to
hold commonly used variables for faster execution
CMPE12c
18
Gabriel Hugh Elkaim
CISC vs. RISC
CISC : complex instruction set computer
Lots of instructions of variable size, very
memory optimal, typically less registers.
RISC : reduced instruction set computer
Less instructions all of a fixed size, more
registers, optimized for speed. Usually a
“Load/Store” architecture.
CMPE12c
19
Gabriel Hugh Elkaim
Specifying addresses
For a load/store architecture, registers are
used to supply source operands and
receive results from all instructions except
loads and stores.
Basically, load the registers with the
operands from memory first, then perform
the operation.
CMPE12c
20
Gabriel Hugh Elkaim
How do we fit the “stuff” in 32bit instructions?
So we have arithmetic instructions and
branch type instructions that cannot
contain all the needed info in a single 32bit word.
CMPE12c
21
Gabriel Hugh Elkaim
Ways to get an effective address
1. Instruction might occupy 2 words.
opcode
reg
address
Effective
address
2. Instruction might specify a register that contains the
address, 1 word instruction.
opcode
CMPE12c
reg
address
reg
22
Effective
address
Gabriel Hugh Elkaim
Effective Address Calculation
3. Instruction might specify a small constant and a second
register, 1 word instruction.
opcode
reg
CMPE12c
reg
constant
address
+
23
Effective address
Gabriel Hugh Elkaim
Effective Address Calculation
4. The instruction might specify 2 additional registers, 1
word instruction.
opcode
reg
reg
address
reg
reg
address
+
Effective address
CMPE12c
24
Gabriel Hugh Elkaim
Addressing modes
Methods a computer uses to specify an
address within an instruction.
CMPE12c
25
Gabriel Hugh Elkaim
Addressing Modes
• Immediate
– The operand is contained directly in the
instruction. Ex: li reg1, 5
• Register
– The operand is contained in a register.
Ex: add reg1, reg2, reg3
• Direct
– The address of the operand is contained in
the instruction (two-word instruction)
CMPE12c
26
Gabriel Hugh Elkaim
Addressing Modes
• Register Direct
– The address of the operand is contained in
a register. Ex: lw reg1, reg3
• Base Displacement
– The address is computed as the sum of the
contents of a register (the base) and a
constant contained in the instruction (the
displacement). Ex: lw reg1, 5(reg3)
CMPE12c
27
Gabriel Hugh Elkaim
Addressing Modes
• Indirect
The instruction specifies a register containing
an address the content of which is the address
of the operand
opcode
reg
Memory
address
reg
address
address
Effective address
CMPE12c
28
Gabriel Hugh Elkaim
MAL
(MIPS Assembly Language)
MIPS is a load/store RISC architecture
2 distinct register files:
• 32 general registers
• 16 floating point registers
CMPE12c
29
Gabriel Hugh Elkaim
MAL
The 32 general registers are numbered $0 - $31.
$0 is always the value “Zero”.
$1 is used by the assembler.
$26 & $27 are used by the operating system.
$28, $29, & $31 have special conventions for the
use of them.
CMPE12c
30
Gabriel Hugh Elkaim
Common aliases for registers
$2-$3
$4-$7
$8-$15
$24-$25
$16-$23
$30
$29
$31
CMPE12c
$v0-$v1
procedure results
$a0-$a3
parameters for procedure
$t0-$t7
temporary registers
$t8-$t9
$s0-$s7
saved registers
$s8
$sp
stack pointer
$ra
return address register
31
Gabriel Hugh Elkaim
MAL
The 16 floating point registers are intended
exclusively for holding floating point operands.
These registers are 64-bits in size for holding both
single precision (32-bit) floats and double precision
(64-bit) floats.
These registers are named $f0, $f2, $f4,…., $f30.
Why?
CMPE12c
32
Gabriel Hugh Elkaim
MAL
MAL uses a single, versatile addressing mode
for its regular load store.
Base displacement.
General since its special cases provide for both
direct and register direct address.
CMPE12c
33
Gabriel Hugh Elkaim
MAL Syntax
Syntax of MAL
one instruction, declaration per line
comments are anything on a line following #
comments may not span lines
MAL has 3 basic types:
• Integer
• Floating point
• Character
CMPE12c
34
Gabriel Hugh Elkaim
MAL Syntax
“C”
type
variablename;
“MAL”
variablename:
type
value
type is
.word (integer)
.byte (character)
.float (floating point)
value is optional – the initial value
CMPE12c
35
Gabriel Hugh Elkaim
MAL Syntax
Examples:
flag:
counter:
variable3:
e:
uservalue:
letter:
.byte
.word
.word
.word
.float
0
0
2.71828
.byte
‘a’
•One declaration per line
•Default initial value is 0
(but you may lose points if you depend on this)
CMPE12c
36
Gabriel Hugh Elkaim
MAL Syntax
Directives give information to the assembler. All
directives start with ‘.’ (period)
Examples:
.byte
.word
.float
main:
# tells simulator to start execution at this location.
.data
# .data identifies the start of the declaration section
# there can be more than 1 .data sections in a program.
CMPE12c
37
Gabriel Hugh Elkaim
MAL Syntax
.text
# identifies where instructions are, there can be
# more than 1 .text sections in a program
.asciiz
“a string.\n”
# places a string into memory and null terminates
# the string
“new string.”
.ascii
# places a string into memory with no null
# termination.
CMPE12c
38
Gabriel Hugh Elkaim
MAL Syntax
C
MAL
lw $s1, x
lw $s2, y
move $s3, $s2
add $s3, $s1, $s2
sub $s3, $s1, $s2
mul $s3, $s1, $s2
div $s3, $s1, $s2
rem $s3, $s1, $s2
sw $s3, z
z = y;
z = x + y;
z = x - y;
z = x * y;
z = x / y;
z = x % y;
An immediate is a value specified in an instruction, not in the
.data section.
Examples: li $s2, 0
# load immediate
add $s2, $s2, 3 # add immediate
CMPE12c
39
Gabriel Hugh Elkaim
MAL Program
Simple MAL program
avg:
i1:
i2:
i3:
.data
.word
.word
.word
.word
.text
div $s4, $s4, $s3
sw $s4, avg
li $2, 10 # done cmd
syscall
0
20
13
2
main:
lw $s1, i1
lw $s2, i2
lw $s3, i3
add $s4, $s1, $s2
CMPE12c
40
Gabriel Hugh Elkaim
Program Execution
• Assembler translates to executable
– machine language
• Linker combines multiple MAL files
• Loader puts executable into memory
and makes the CPU jump to the first
instruction “main:”
– Executes
– When done returns to OS
• Simulator or Monitor
• To rerun with different data, repeat the
process
CMPE12c
41
Gabriel Hugh Elkaim
MAL Programming
HLL – if/else statements…
if (condition)
statement;
else
statement;
“C” if (count < 0)
count = count + 1;
CMPE12c
42
Gabriel Hugh Elkaim
MAL Programming
“MAL”
ifstuff:
endif:
“OR”
endif:
CMPE12c
lw
$t1, count
bltz $t1, ifstuff
b
endif
add $t1, $t1, 1
# next instruction goes here
lw
$t1, count
bgez $t1, endif
add $t1, $t1, 1
# next instruction goes here
43
Gabriel Hugh Elkaim
MAL Programming
Loops can be built out of IF’s – WHILE:
“C”
while (count > 0)
{
a = a % count;
count--;
}
CMPE12c
44
Gabriel Hugh Elkaim
MAL Programming
“MAL”
lw
lw
while:
blez
rem
sub
b
endwhile: sw
sw
CMPE12c
$s1, count
$s2, a
$s1, endwhile
$s2, $s2, $s1
$s1, $s1, 1
while
$s2, a
$s1, count
45
Gabriel Hugh Elkaim
MAL Programming
Repeat loops
“C”
/* do statement while expression is TRUE */
/* when expression is FALSE, exit loop */
do {
if (a < b)
a++;
if (a > b)
a--;
} while (a != b)
CMPE12c
46
Gabriel Hugh Elkaim
MAL Programming
“MAL”
repeat:
secondif:
until:
CMPE12c
lw
lw
bge
add
ble
sub
bne
47
$s3, a
$s4, b
$s3, $s4, secondif
$s3, $s3, 1
$s3, $s4, until
$s3, $s3, 1
$s3, $s4, repeat
Gabriel Hugh Elkaim
MAL Programming
While Loops (Part II)
“C”
while ( (count < limit) && (c ==d) )
{ /* loop’s code goes here */}
“MAL”
while:?
?
# loop code goes here
?
endwhile:
CMPE12c
48
Gabriel Hugh Elkaim
CMPE12c
49
Gabriel Hugh Elkaim
MAL Programming
For loops
“C”
for ( I = 3; I <= 8; I++)
{ a = a+I;}
“MAL”
?
for: ?
?
?
?
endfor:
CMPE12c
50
Gabriel Hugh Elkaim
CMPE12c
51
Gabriel Hugh Elkaim
Procedure Calls
Simple procedure calls require 2 instructions:
“JAL” Jump and Link
•Link means save the return address in $ra ($31)
“JR” Jump Register
• Be careful with registers!!
• Cannot nest unless $ra is saved elsewhere
• Cannot be recursive without a stack
CMPE12c
52
Gabriel Hugh Elkaim
MAL Procedures
Example
jal
average
# calls proc.
…
average:
CMPE12c
add $s2, $s3, $s4
div $s2, $s2, 2
jr
$ra
53
# returns
Gabriel Hugh Elkaim
Operating System Calls
Very tedious and dangerous for a
programmer to deal with IO. This is why
we like to have an OS. Need an
instruction though to get its attention.
Use $2 ($v0) to pass code to OS
Use $4 ($a0) to pass data to OS
Use “syscall” instruction to call OS
CMPE12c
54
Gabriel Hugh Elkaim
Operating System Codes
Code ($v0)
CMPE12c
Function
Usage & Result
1
Print Integer
Put integer in $a0
2
Print Float
Put floating point number in $f12
3
Print Double
Put double in $f12
4
Print String
Put address of string into $a0
5
Read Integer
Returns integer read in $v0
6
Read Float
Returns float read in $f0
7
Read Double
Returns double read in $f0
8
Read String
Put address in $a0, length in $a1
10
Exit
Quits program
11
Print Character
Put character in $a0
12
Get Character
Returns character in $v0
55
Gabriel Hugh Elkaim
SYS Calls Examples
To print a character
# address of the char must be in $s0
lb
$a0, ($s0) # $4 char to be printed
li
$v0, 11
# code for putc
syscall
To read in a character
li
$v0, 12
syscall
CMPE12c
# code for getc
# character returned
# in $v0
56
Gabriel Hugh Elkaim
SYS Calls Examples
To end your program
li
$v0, 10
syscall
CMPE12c
# code for done
57
Gabriel Hugh Elkaim
CMPE12c
58
Gabriel Hugh Elkaim
CMPE12c
59
Gabriel Hugh Elkaim
CMPE12c
60
Gabriel Hugh Elkaim