پردازنده MIPS
مقدمه
دستورات
& کتاب Patterson & Henessi
مقدمه
MIPS یکی از اولین پردازندهای RISC است که بصورت تجاری عرضه و موفق شده است. در سال 1984 توسط تیمی دردانشگاه استانفورد طراحی شده است.
پردازنده ای ساده ولی در عین حال قوی است.
در تجهیزات مختلفی بصورت embedded استفاده شده است:
Various routers from Cisco
Game machines like the Nintendo 64 and Sony Playstation 2
ویژگیها
تعداد زیاد رجیسترهای همه منظوره
مجموعه کوچک دستورات
MIPS32: 168 instructions
MIPS64: 258 instructions
اندازه دستورات ثابت ولی فرمت آنها متغیر است
دسترسی به حافظه محدود به دستورات load/store است
مد های آدرس دهی محدود است.
رجیسترها
این پردازنده دارای 32 رجیستر 32 بیتی است:
R0 .. R31
رجیستر R0 بصورت سخت افزاری با مقدار صفر پر شده است یعنی همیشه برابر با صفر است
رجیستر R1 برای کار اسمبلر رزرو شده است
از بقیه رجیستر ها میشود در برنامه ها استفاده نمود.
عملوند ها همیشه باید در یکی از رجیستر ها قرار داشته باشند.
رجیستر فایل
If Write = 1, then D data is stored into D address.
You can read from two registers at once, by supplying the A address and B address inputs. The outputs appear as A data and B data.
Registers are clocked, sequential devices.
We can read from the register file at any time.
Data is written only on the positive edge of the clock.
وقتی تعداد رجیسترها افزایش مییابد آنها بصورت رجیستر فایل ساخته میشوند:
سایر رجیستر ها
علاوه بر ر جیسترهای فوق MIPS دارای رجیسترهای دیگری نیز میباشد:
PC (program counter) register and Status register
Floating point registers
نامگذاری رجیسترها برای سهولت استفاده در نرم افزار
0 zero constant 0
1 at reserved for assembler
2 v0 expression evaluation &
3 v1 function results
4 a0 arguments
5 a1
6 a2
7 a3
8 t0 temporary: caller saves
. . . (callee can clobber)
15 t7
16 s0 callee saves
. . . (callee must save)
23 s7
24 t8 temporary (cont’d)
25 t9
26 k0 reserved for OS kernel
27 k1
28 gp Pointer to global area
29 sp Stack pointer
30 fp frame pointer
31 ra Return Address (HW)
برای اینکه برنامه نویسی اسمبلی راحت تر باشد به هر رجیستر اسمی داده شده است
انواع داده
مقایسه رجوع به داده ها بر اساس اندازه آنها
0%
20%
40%
60%
80%
Byte
Halfword
Word
Doubleword
0%
0%
31%
69%
7%
19%
74%
0%
Int Avg.
FP Avg.
داده های حمایت شده
Integer
8-bit char
16-bit half-word
32-bit word
64-bit double-word
Floating point
32-bit single precision
64-bit single precision
paired single precision
IEEE 754 standard
حافظه MIPS
MIPS دارای 32 خط آدرس است. یعنی میتواند تا 232 محل حافظه را آدرس دهی نماید. در هر محل حافظه یک بایت داده قرار میگیرند.
This results in a 232 x 8 RAM, which would be 4 GB of memory.
سازمان حافظه
هر کلمه دارای 4 بایت میباشد
232 bytes with byte addresses from 0 to 232-1
230 words with byte addresses 0, 4, 8, … 232-4
Registers hold 32 bits of data
سازمان حافظه : Alignment
Words are aligned
سازمان حافظه : Alignment
توجه داشته باشید که آدرس حافظه بر مبنای بایت ایجاد میشود. از اینرو یک کلمه 32 بیتی 4 محل حافظه را اشغال خواهد نمود.
در معماری MIPS کلمات باید بصورت aligned در حافظه قرار گیرند. یعنی یک کلمه 32 بیتی باید در یک محلی از حافظه قرار گیرد که آدرس آن مضربی از 4 باشد.
0, 4, 8 and 12 are valid word addresses.
1, 2, 3, 5, 6, 7, 9, 10 and 11 are not valid word addresses.
در صورتی که به اشتباه قصد دسترسی به بک محل حافظه unaligned داشته باشد یک خطای bus error رخ خواهد داد.
این محدودیت برای برنامه نویسی با زبان سطح بالا تاثیر قابل ملاحظه ای ندارد اما به پردازنده کمک میکند تا اندکی سریعتر عمل کند.
آرایه ای از کلمات
باید هنگام کار با آرایه ها مراقب بود که اگر آرایه ای برای مثال از محل 2000 حافظه شرع شود، عضو اول آن در آدرس 2000 و عضو دوم آن در آدرس 2004 خواهد بود و نه در آدرس 2001
برای مثال اگر رجیستر $a0 دارای مقدار 2000 باشد:
lw $t0, 0($a0)
به اولین عضو اشاره میکند در حالیکه
lw $t0,8($a0)
به سومین عضو آرایه که در آدرس 2008 است دسترسی پیدا خواهد نمود.
ترتیب بایت های یک کلمه در حافظه
دو روش برای مشخص کردن ترتیب بایتها در حافظه وجود دارد:
Big endian:
word address (lowest numerical byte address) is the address of the most significant byte
Little endian:
word address is the address of the least significant byte
B is some base address
ترتیب بایت های یک کلمه در حافظه
Big Endian
Little Endian
78
34
12
56
12
56
78
34
memory address
similar to writing English
B=200 is the base address in this example
در معماری MIPS میتوان پردازنده را برای هر یک از این دو روش تنظیم کرد.
انواع اصلی دستورالعملهای MIPS
Arithmetic
Integer
Floating Point
Memory access instructions
Load & Store
Control flow
Jump
Conditional Branch
Call & Return
دستورات محاسباتی
چهار دسته دستورات محاسباتی وجود دارند:
Add
Subtract
Multiply
Divide
دستورات محاسباتی
تمامی دستورت ALU نظیر دستورات جمع و ضرب دارای 3 عملوند هستند: یکی برای مقصد و دو تای دیگر برای مبدا داده ها. هر سه عملوند ها باید یکی از رجیستر های MIPS باشند. تمامی محاسبات 32 بیتی هستند.
C code: A = B + C; E = F – A; MIPS code: add $t0, $s1, $s2 sub $s4, $s5, $s0
Unsigned arith: addu/subu (overflow undetected)
Assembly language format: label: operation dest reg, first src reg, second src reg # Comment
دستورات محاسباتی
اصول معماری:
تمامی محاسبات بر روی داده های رجیسترها انجام میشود. یعنی نمیتوان عددی را که در حافظه ذخیره شده است با یک رجیستر جمع کرد. برای اینکار ابتدا باید محتوی حافظه به رجیستر به منتقل شده و عملیات بر روی داده های رجیستر ها انجام شود.
ترتیب اپراندها همیشه ثابت است: اول مقصد نوشته میشود.
نوشتن توضیحات در برنامه نویسی به زبان اسمبلی MIPS
Hash (#) is used for MIPS comments
anything from hash mark to end of line is a comment and will be ignored
دستورات محاسباتی
Add/Sub_Immediate instructions یک عدد 16 بیتی با علامت و یا بدون علامت را با یکی از رجیستر های 16 بیتی جمع / تفریق مینماید.
Destination Reg = Source Register + Immediate Example: A = A – 4
addi $t0, $t0, -4 # $t0 = $t0 –4 Signed/Unsigned Arithm: addi, addiu
Assembly language format(I-format): label: operation dest_reg, src_reg, immediate value/constant # Comment
مثال
تبدیل برنامه C به اسمبلی MIPS
a = b + c + d – e;
Break into multiple instructions
add $t0, $s1, $s2 # temp = b + c
add $t0, $t0, $s3 # temp = temp + d
sub $s0, $t0, $s4 # a = temp – e
Notice: A single line of C may break up into several lines of MIPS.
مثال
How do we do this?
f = (g + h) – (i + j);
Use intermediate temporary register
add $t0,$s1,$s2 # temp = g + h
add $t1,$s3,$s4 # temp = i + j
sub $s0,$t0,$t1 # f=(g+h)-(i+j)
دستورات منطقی
برخی ازدستورات منطقی موجود درMIPS
AND
bit-wise AND between registers
and $t1, $s0, $s1
OR
bit-wise OR between registers
or $t1, $s0, $s1
NOR
Bit-wise NOR between registers
nor $t1, $s0, $s1
nor $t1, $t0, $0 # $t1 = NOT($t0)
Immediate modes
andi and ori
دستورات دسترسی به حافظه
داده ها را بین حافظه و رجیسترها منتقل میکنند. دارای 3 اپراند میباشند:
LW/SW instruction:
آدرس داده در حافظه بصورت زیر محاسبه میشود
Source Address = Source Base Address + Offset
Assembly language format(I-format): label: operation dest_reg, offset ( src_reg) # Comment
Load/Store
Name of register
to put value in
A number
Name of register to get base address from
مثال : Load Word
lw $s0, 4($s3)
If $s3 has the value 100, this will copy the word at memory location 104 to the register $s0.
$s0 <- Memory[104]
مثال : Store Word
sw $s0, 4($s3)
If $s3 has the value 100, this will copy the word in register $s0 to memory location 104.
Memory[104] <- $s0
خواندن از حافظه
lw R6, 0(R5) # R6 <= mem[0x14]
مثال
C code: A[8] = h + A[8]; assume h in $s2 and base address of the array A in $s3
MIPS code: lw $t0, 32($s3) add $t0, $s2, $t0 sw $t0, 32($s3)
این نحوه آدرس دهی طراحی دستورالعمل ها را ساده کرده و به پیاده سازی آرایه ها و استراکچرها کمک میکند
دستورات دسترسی به حافظه
مثال
C code: z = w + y;
MIPS code:
la $t0, w # put address of w into $t0
lw $s0, 0($t0) # put contents of w into $s0
la $t1, y # put address of y into $t1
lw $s1, 0($t1) # put contents of y into $s1
add $s2, $s0, $s1 # add w + y, put result in $s2
la $t2, z # put address of z into $t2
sw $s2, 0($t2) # put contents of $s2 into z
la= load address , lw= load word , sw= store word
Must load address (la) to get the address of the memory location into a register
0($t0)means go 0 bytes from the address specified by$t0
1010101010101010
0000000000000000
0000000000000000
1010101010101010
1010101010101010
1010101010101010
ori
Then must get the lower order bits right, i.e., ori $t0, $t0, 1010101010101010
انتقال بلادرنگ مقادیر 32 بیتی به رجیسترها
اینکار در دو مرحله با انتقال 16 بیت با ارزش و کم ارزش و ترکیب آنها صورت میپذیرد
16 بیت با ارزش با دستور load upper immediate منتقل میشود.
lui $t0, 1010101010101010
دستورات کنترلی
این دستورات سیر اجرای برنامه را تغییر میدهند یعنی اینکه دستور بعدی که باید اجرا شود را تعیین میکنند.
انواع مختلف دستورات کنترلی
conditional branches
jumps (unconditional branch)
procedure calls
procedure returns
دستورات انشعاب
دستورات انشعاب شرطی در MIPS عبارتند از:
bne $t0, $t1, Label beq $t0, $t1, Label
Example: if (i==j) h = i + j; bne $s0, $s1, Label add $s3, $s0, $s1 Label: ….
Note the reversal of the condition from equality to inequality!
دستورات کنترلی
دستورات انشعاب غیرشرطی در MIPS عبارتند از:
j label Unconditional jump
jr $t0 “jump register”. Jump to the instruction specified in register $t0
Example: if (i!=j) beq $s4, $s5, Lab1 h=i+j; add $s3, $s4, $s5 else j Lab2 h=i-j; Lab1:sub $s3, $s4, $s5 Lab2: …
دستورات کنترلی
اغلب در کنار دو دستور فوق از دستوردیگری نیز استفاده میشود:
slt and slti // set if less than (w/ and w/o an immediate)
slt $t0, $s1, $s2
از این دستور به همراه دستورات قبلی استفاده میشود:
if $s1 < $s2 then $t0 = 1
else $t0 = 0
slti $at, $a0, 5 # $at = 1if $a0 < 5
bne $at, $0, Label #Branch if $a0 < 5
نحوه محاسبه آدرس در دستورات کنترلی
PC-relative addressing
فرمت این دستورات از نوع I-Type است که در آن آدرس بصورت یک مقدار 16 بیتی نوشته میشود. این مقدار بصورت یک افست نسبت به مقدار رجیستر PC نوشته میشود.
bne $t4,$t5,Label Next instruction is at Label if $t4 $t5
beq $t4,$t5,Label Next instruction is at Label if $t4 = $t5
نحوه محاسبه آدرس در دستورات کنترلی
j Label Next instruction is at Label
Pseudodirect addressing
در این دستور فقط از بیت های با ارزش PC استفاده میشود.
32-bit jump address = 4 Most Significant bits of PC concatenated with 26-bit word address (or 28- bit byte address)
Address boundaries of 256 MB
For larger distances: Jump register jr required.
Example
LOOP: mult $9, $19, $10 # R9 = R19*R10 lw $8, 1000($9) # R8 = @(R9+1000)
bne $8, $21, EXIT add $19, $19, $20 #i = i + j j LOOP EXIT: ……
Assume LOOP is placed at location 80000
مثالی ازپیاده سازی LOOP
MIPS:
Assume: x , y , and sum are in $s0 $s1 , and $s2 respectively. Will use $t0 for I and $t1 for the constant 1
C code:
sum = 0;
for (i = 0; i < y; i++)
sum = sum + x;
add $s2, $zero, $zero # sum = 0
add $t0, $zero, $zero # i = 0
LoopBegin:
slt $t2,$t0, $s1
Beq $t2, $zero, LoopEnd # is i < y ??
add $s2, $s2, $s0 # sum = sum + x
add $t0, $t0, $t1 # i++
j LoopBegin
LoopEnd:
صدا زدن توابع و بازگشت ازآن
از این دستور برای صدا زدن برنامه فرعی استفاده میشود:
jal: jump & link instruction
jal stores the return address in R31 and jumps to address in rt
این دستور آدرس برگشت را در رجیستر R31 قرار میدهد و به آدرس ذکر شده دردستور انشعاب میکند.
برای بازگشت از برنامه فرعی از دستور زیر استفاده میشود:
jr Reg[R31]
ذخیره رجیسترها در هنگام صدا زدن توابع تودرتو
بعلت محدودیت رجیسترها لازم است تا محتوی رجیسترهائی را که برای تابع مهم هستند قبل از صدا زدن تابع ذخیره نموده و بعد از بازگشت از تابع آنها را بازیابی نمود.
رجیسترها در پشته ذخیره خواهند شد. برای اینکه برنامه ها مجبور نباشند تمامی رجیسترها را ذخیره نمایند قاعده زیر رعایت میشود:
تابع صدا زننده رجیسترهای زیر را ذخیره و بازیابی میکند:
t0-$t9 $a0-$a3 $v0-$v1
تابع صدا شونده رجیسترهای زیر را ذخیره و بازیابی میکند:
$s0-$s7 $ra
دستورت شیفت
MIPS Shift Instructions
Format: op code/dest reg/src reg/shift amount
sll $t4, $t0, 5 #shift left logical 5 bits (multiply by 32) sra $t5, $t0, 2 #shift right arithmetic 2 bits (divide by 4), #sign extended srl $v0, $t0, 1 #shift right logical 1 bit. Sign bit is now 0 srlv $v0, $t0, $t1 #shift right logical, $t1 says how many bits
Type of shift Left Right
Logical sll sllv srl srlv
Arithmetic (none: use sll) sra srav
Rotate rol ror
خلاصه دستورات
MIPS — loading words but addressing bytes — arithmetic on registers only
Instruction Meaning add $s1, $s2, $s3 $s1 = $s2 + $s3 sub $s1, $s2, $s3 $s1 = $s2 – $s3 lw $s1, 100($s2) $s1 = Memory[$s2+100] sw $s1, 100($s2) Memory[$s2+100] = $s1
مثالی از یک برنامه C
swap(int v[], int k);
{ int temp;
temp = v[k]
v[k] = v[k+1];
v[k+1] = temp;
}
swap:
muli $2 , $5, 4
add $2 , $4, $2
lw $15, 0($2)
lw $16, 4($2)
sw $16, 0($2)
sw $15, 4($2)
jr $31
Explanation:
index k : $5
base address of v: $4
address of v[k] is $4 + 4.$5
فرمت دستورات
فرمت و طول دستورات کامپیوتر پایه مانو ثابت و یکسان بود. در حالت کلی:
اگر اندازه کد تولید شده مهم باشد از دستوراتی با فرمت متفاوت استفاده میشود
اما اگر کارائی ( سرعت) مهم باشد از دستوراتی با طول یکسان استفاده میشود.
Variable:
Fixed:
…
…
فرمت دستورات MIPS
طول هر دستور 32 بیت است.
هر دستور به تعدادی Field تقسیم میشود. هر فیلد توضیحی در مورد دستور العمل ارائه میدهد.
از آنجائیکه دستورات مختلف نیازمند ارائه توضیحات مختلفی هستند لذا در MIPS سه نوع فرمت مختلف ( ولی با طول یکسان) برای دستورات در نظر گرفته شده است.
R-format Register instructions are used for register based ALU operations.
I-format Immediate instructions, can be either Load/Store operations, Branch operations, or Immediate ALU operations.
J-format Jump instructions, devote all of the non-opcode space to a 26-bit jump destination field.
فرمت دستورات MIPS
3 نوع فرمت مختلف بصورت زیر هستند:
opcode
Offset added to PC
6
26
opcode
rs
rd
immediate
6
5
5
16
I-Type
R-Type
J-Type
opcode
rs
rt
6
5
5
rd
5
shamt
5
func
6
Note the regularity of instruction encoding. This is important for implementing an efficient pipelined CPU.
فیلد های مختلف دستورالعمل ها
op operation of the instruction
rs first register source operand
rt second register source operand
rd register destination operand
shamt shift amount
funct function (select type of ALU operation)
add = 32
sub = 34
مثال
Example: add $t0, $s1, $s2
registers have numbers, $t0=8, $s1=17, $s2=18
Instruction Format: 000000 10001 10010 01000 00000 100000 op rs rt rd shamt funct
دستوراتR-Type
opcode: basic operation to be performed
rs: source register 1
rt: source register 2
rd: destination register
shamt: shift amount
funct: specific variant of opcode
این دستورات دارای opcode=0 بوده و برای عملیات ALU استفاده میشوند.
عمل مورد نظر توسط فیلد مشخص میشود:
add: 32
sub: 34
فرمت دستور ADD
32 bits
این فرمت برای تعداد زیادی دستور غیر از Add نیز استفاده میشود. که همه این نوع دستورات R-type نامیده میشوند.
اندکنیگ دستور
For add:
op is 010 (000000)
funct is 3210 (100000)
Register encodings:
$s0 is 1610 (10000), $s1 is 1710, …
$t0 is 810 (01000), $t1 is 910, …
بصورت HEX مقدار این دستور برابر است با:02288020
rs
op
rt
rd
shamt
funct
000000 10001 01000 10000 00000 100000
add $s0, $s1, $t0
Opcode
lw: 35 (100011)
sw: 43 (101011)
opcode value differentiates I- and R-Type instructions
rs: base register
rt:
destination register for lw
source register for store
immediate: offset from base
range: -215 to (215-1)
Similarity in opcode for lw & sw simplifies hardware
دستورات I-Type
rs
op
rt
address
16 bits
32 bits
rs is the base register
rt is the destination of a load (source of a store)
address is a signed integer
فرمت دستور/SW LW
lw $s0, 24($t1)
100011 01001 10000 0000000000011000
rs
op
rt
address
sw $s0, 24($t1)
101011 01001 10000 0000000000011000
rs
op
rt
address
فرمت دستورات با آدرس دهی بلادرنگ
برای دستورات ALU که نیاز به یک اپراند ثابت دارند استفاده میشود. (e.g., X=X+4)
همچنین برای load کردن مقادیر ثابت از حافظه بکار میرود.
مقادیر ثابت بصورت یک عدد 16 بیتی کد میشوند. لذا در رنج -215 to (215-1) خواهند بود.
مثال:
addi R4, R8, 79
slti R1, R2, 56: sets Reg[R1]=1 if Reg[R2]<56 else Reg[R1]=0
دستورات J-Type
دستورات پرش غیرشرطی به فرم J-Type کد میشوند.
اپکد دستور J برابر با 2 و اپکد دستور Jal برابر با 3 می باشد.
مقدار جابجائی نسبت به PC+4 محاسبه میشود.
مد های آدرس دهی Mips
Immediate
add R4, #7 # Regs[R4]=Regs[R4]+7
16-bit field for the constant
Register
add R4, R3, R2 # Regs[R4]=Regs[R3]+Regs[R2]
Displacement
lw R4, 100(R1) #regs[R4]=Regs[R4]+Mem[Regs[R1]+100]
16-bits for displacement
Special cases of displacement mode
indirect mode: displacement value=0
lw R4, 0(R1) #regs[R4]=Regs[R4]+Mem[Regs[R1]]
absolute addressing : R0 as base register (always stores 0)
lw R4, 8769(R0)
مد های آدرس دهی Mips
Pseudo-instructions
MIPS assemblers support pseudo-instructions that give the illusion of a more expressive instruction set, but are actually translated into one or more simpler, “real” instructions.
In addition to the la (load address) we saw on last lecture, you can use the li and move pseudo-instructions:
li $a0, 2000 # Load immediate 2000 into $a0
move $a1, $t0 # Copy $t0 into $a1
They are probably clearer than their corresponding MIPS instructions:
add $a0, $0, 2000 # Initialize $a0 to 2000
add $a1, $t0, $0 # Copy $t0 into $a1
پشته یا Stack
پشته محلی از حافظه اصلی است که جهت ذخیره داده ها استفاده میشود.
موارد استفاده از پشته
ذخیره متغیرهای یک برنامه
ذخیره محتوی سایر رجیسترها وقتی که یک برنامه فرعی صدا زده میشود
کمک به ترجمه عملیات محاسباتی با روش RPN
رجیسترSp محل آخرین داده ذخیره شده در پشته را مشخص میکند
عملیات زیر روی پشته تعریف میشوند:
Push
SPSP-1
M[SP]DR
POP
DRM[SP]
SPSP+1
پشته و برنامه های برگشت پذیر
استفاده از پشته باعث میشود تا امکان پیاده سازی برنامه های برگشت پذیر فراهم گردد.
با استفاده از پشته میتوان برای هر نسخه از تابع صدا زده شده حافظه جداگانه ای در نظر گرفت
آرگومانها و متغیرهای محلی را میتوان در پشته ذخیره نمود.
آدرس دهی متغیرهای محلی و آرگومانها نسبت به موقعیت پشته انجام میشود.
بازگشت از توابع عکس حالتی است که صدا زده شده اند
پشته یا Stack
در MIPS پشته از آدرسهای بالا به سمت آدرسهای پائین رشد میکند.
هنگام push کردن داده در پشته باید مقدار رجیستر $sp را کاهش داد.
استفاده از stack برای صدا زدن تابع فرعی
قبل از صدا زدن تابع مقادیر رجیسترها در پشته ذخیره میشود
تابع با استفاده ازدستور صدا زده میشود: jal address
در پایان اجرای تابع، برای بازگشت به برنامه اصلی از دستور jr (jump register) استفاده میشود.
بعد از بازگشت از تابع مقادیر رجیسترها از پشته خارج میشوند.
$sp
low address
high address
filled
empty
Save $s0 and $s1:
subi $sp,$sp,8
sw $s0,4($sp)
sw $s1,0($sp)
Restore $s0 and $s1:
lw $s0,4($sp)
lw $s1,0($sp)
addi $sp,$sp,8
مثالی از استفاده از پشته
مثالی ازپیاده سازی تابع
int func(int g, int h, int i, int j)
{ int f;
f = ( g + h ) – ( i + j ) ;
return ( f );
} // g,h,i,j – $a0,$a1,$a2,$a3, f in $s0
func :
addi $sp, $sp, -12 #make room in stack for 3 words
sw $t1, 8($sp) #save the regs we want to use
sw $t0, 4($sp)
sw $s0, 0($sp)
add $t0, $a0, $a1 #$t0 = g + h
add $t1, $a2, $a3 #$t1 = i + j
sub $s0, $t0, $t1 #$s0 has the result
add $v0, $s0, $zero #return reg $v0 has f
lw $s0, 0($sp) # restore $s0
lw $t0, 4($sp) # restore $t0
lw $t1, 8($sp) # restore $t1
addi $sp, $sp, 12 # restore sp
jr $ra
we did not have to restore $t0-$t9 (caller save)
we do need to restore $s0-$s7 (must be preserved by callee)
نمایش لهستانی معکوس Reverse Polish Notation (RPN)
روش معمولی نمایش عبارات ریاضی:
A*B+C*D
روش PN برای نمایش عبارات ریاضی: عملگرها قبل از عملوندها قرارمیگیرند.
+*AB*CD
روش RPN برای نمایش عبارات ریاضی: عملگرها بعد از عملوندها قرا میگیرند
AB*CD*+
استفاده از پشته برای پیاده سازی RPN
در برخی ماشینهای حساب و کامپیوترها از ترکیب پشته و RPNبرای محاسبه عبارات ریاضی استفاده میکنند.
ابتدا عبارت بصورت RPN نوشته میشود ) معمولا اینکار توسط کامپایلر انجام میشود(
در هنگام محاسبه
با برخورد به عملوندها آنها را در پشته PUSH میکنیم
با برخورد با عملگرها ، دو داده موجود در بالای پشته POPشده و عمل مورد نظر بر روی آنها انجام و حاصل درپشته PUSH میشود.
مثال
برای محاسبه عبارت زیر یک کامپایلر ممکن است کد زیر را تولید نماید. a= b + c * d;
در اینصورت محتوی پشته بصورت زیر خواهد بود:
PUSH b
PUSH c
PUSH d
MUL
ADD
POP a
b
PUSH b
عبارت معادل RPN بصورت زیر خواهد بود:
bcd*+
b
c
PUSH c
b
c
d
b
c*d
PUSH d
MUL
b+c*d
ADD
pop
تمرین:
با مطالعه پردازنده کمکی MIPS گزارشی در مورد محاسبات اعشاری و دستورات floating point مورد استفاده دراین پردازنده ارائه دهید.