Instruction Set Comparisons CS 740 Sept 18 2000 Topics Code Examples Procedure Linkage Sparse Matrix Code Instruction Sets Alpha PowerPC VAX Procedure Examples Procedure linkage Passing of control and dataCode Example stack management int rfact int n Control Register tests Condition codes loop counters 2 if n 1 return 1 return n rfact n 1 CS 740 F 00 Alpha rfact Registers 16 Argument n 9 Saved n Callee save 0 Return Value rfact Stack Frame ldgp 29 0 27 setup gp lda 30 16 30 frame 30 16 26 0 stq 26 0 30 stq 9 8 30 mask 0x4000200 16 prologue 1 bis 16 16 9 cmple 9 1 1 bne 1 80 subq 9 1 16 bsr 26 rfact ng mulq 9 0 0 br 31 81 align 4 sp 16 bis 31 1 0 return val 1 ldq 26 0 30 ldq 9 8 30 addq 30 16 30 ret 31 26 1 restore retrn addr restore 9 sp 16 rfact ng 16 bytes 9 26 return PC sp 8 sp 0 3 save 9 save 26 save return addr save 9 9 n if n 1 then branch to 80 16 n 1 recursive call 0 n rfact n 1 branch to epilogue 80 81 CS 740 F 00 VA X Pinnacle of CISC Maximize instruction density Provide instructions closely matched to typical program operations Instruction format OP arg1 arg2 Each argument has arbitrary specifier Accessing operands may have side effects Condition Codes Set by arithmetic and comparison instructions Basis for successive branches Procedure Linkage Direct implementation of stack discipline 4 CS 740 F 00 VAX Registers R0 R11 General purpose Varies with push pop R2 R7 Callee save in example code Use pair to hold double SP Temp R12 AP Argument pointer Space Stack region holding procedure arguments R13 FP Frame pointer Local Current Vars Frame Base of current stack frame FP R14 SP Stack pointer Saved Caller Top of stack State R15 PC Program counter Arg Count AP Used to access data in code Previous N C V Z Condition codes Frame Args Information about last operation resultAddress Negative Carry 2 s OVF Zero 5 CS 740 F 00 VAX Operand Specifiers Forms Notation Value Side Ef Use Ri ri General purpose register v v Immediate data Ri M ri Memory reference v Ri M ri v Mem ref with displacement A Ri M a ri d Array indexing A is specifier denoting address a d is size of datum Ri M ri Ri d Stepping pointer forward Ri M ri d Ri d Stepping pointer back Examples Push src Pop dest 6 move src SP move SP dest CS 740 F 00 VAX Procedure Linkage Caller SP Push Arguments Argn Relative to SP Execute CALLS narg proc narg denotes number of argument words Arg1 proc starts with mask denoting registers to be saved on stack CALLS Instruction Creates stack frame Saved registers PC FP AP mask PSW Sets AP FP SP Callee SP FP AP Compute return value in R0 Execute ret Undoes effect of CALLS proc mask 1st instr CALLS narg Saved State narg Argn Arg1 7 CS 740 F 00 VAX rfact Registers rfact word 0x40 movl 4 ap r6 cmpl r6 1 jgtr L1 movl 1 r0 ret r6 saved n r0 return value Stack Frame save r6 Save register r6 r6 n if n 1 then goto L1 r0 1 return L1 pushab 1 r6 push n 1 calls 1 rfact call recursively mull2 r6 r0 return result n ret Note Destination argument last SP FP Temp Space r6 Current Saved Caller Frame State 1 n AP 8 Previous Frame CS 740 F 00 Sparse Matrix Code Task Multiply sparse matrix times dense vector Matrix has many zero entries Save space and time by keeping only nonzero entries Common application Compressed Sparse Row Representation 3 50 9 2 2 4 1 1 9 4 6 0 72 7 3 0 2 9 1 2 2 8 3 4 9 0 3 5 1 0 9 3 2 2 1 4 1 3 1 9 0 4 6 2 0 7 3 2 7 5 3 0 2 2 9 2 1 2 4 2 8 5 3 4 CS 740 F 00 Parameters CSR Encoding typedef struct int nrow int nentries double val int cindex int rstart csr rec csr ptr nrow Number of rows and columns nentries Number of nonzero matrix entries Val List of nonzero values nentries Cindex List of column indices nentries Rstart List of starting positions for each row 10 nrow 1 CS 740 F 00 CSR Example Parameters nrow 6 nentries 13 Val 3 5 0 9 2 2 4 1 1 9 4 6 0 7 2 7 3 0 2 9 1 2 2 8 3 4 Cindex 0 1 3 1 3 Rstart 0 3 5 9 10 12 13 11 0 2 3 5 2 2 4 5 0 3 5 1 0 9 3 2 2 1 4 1 3 1 9 0 4 6 2 0 7 3 2 7 5 3 0 2 2 9 2 1 2 4 2 8 5 3 4 CS 740 F 00 CSR Multiply Clean Version void csr mult smpl csr ptr M double x double z int r ci for r 0 r M nrow r z r 0 0 for ci M rstart r ci M rstart r 1 ci z r M val ci x M cindex ci Innermost Operation z r M r c x c Column c given by cindex ci Matrix element M r c by val ci cindex ci z M x r 12 CS 740 F 00 CSR Multiply Fast Version void csr mult opt csr ptr M ftype t x ftype t z ftype t val M val int cindex start M cindex int cindex M cindex int rnstart M rstart 1 ftype t z end z M nrow while z z end ftype t temp 0 0 int cindex end cindex start rnstart while cindex cindex end temp val x cindex z temp Performance Approx 2X faster Avoids repeated memory references 13 CS 740 F 00 Optimized Inner Loop while temp valp x cip Inner Loop Pointers cip steps through cindex valp steps through Val Multiply next matrix value by vector element and add to sum 14 CS 740 F 00 VAX Inner Loop Registers r4 cip r2 r3 temp r5 valp r6 cip end r10 x while temp valp x cip Observe muld3 instruction does 1 2 of the work L36 movl r4 r0 r0 cip muld3 r5 r10 r0 r0 r0 r1 valp x r0 addd2 r0 r2 temp r0 r1 cmpl r4 r6 if not done jlssu L36 then goto L36 15 CS 740 F 00 Power PowerPC History IBM develops Power architecture Basis of RS6000 Somewhere between RISC CISC IBM Motorola Apple combine to develop PowerPC architecture Derivative of Power Used in Power Macintosh CISC like features Registers with control information Set of condition registers CR0 7 holding outcome of comparisons link register LR to hold return PC count register CTR to hold loop count Updating …
View Full Document
Unlocking...