2m ago

6 Views

0 Downloads

593.01 KB

15 Pages

Transcription

COMP 212 Computer Organization & ArchitectureCOMP 212 Fall 2008Cache & Disk System ReviewLecture 8MIPS Assembly ProgrammingComp 212 Computer Org & Arch1Z. Li, 2008Comp 212 Computer Org & ArchCache SystemZ. Li, 2008More on addressing For a 2-level cache/mem system Cache system:CPUaccess timet1 10ns– Typically» SRAM for cacheaddress 2W 256 words.total 2W-B blocks, e.g., 4 word a block, we havesize S1 500K– Memory / Cache Organization– Mem word address is W (e.g 8) bit, then we can– If we group 2B word into a block, then we haveCache (SRAM)» DRAM for memoryaccess timet2 100ns» Memory into blocks .26 64 blocks.– Cache organized into cache line, each .2M 16Cachelinesaccommodate a mem block. If we have 2M cache» Cache into linesMemory (DRAM)– Address mapping:lines, then we need M bits as cache line address.» E.g, 16 cache lines, need 4 bits.Size S2 2500K– We have more memory blocks than cache lines,» Mem address W is mapped to cachee.g, 64 16. So cache addressing is to find waysline location, and tagsComp 212 Computer Org & Arch2to map mem blocks into cache lines.3Z. Li, 2008Comp 212 Computer Org & Arch42W-B 64blocksZ. Li, 2008

Direct Cache Mapping Example (W 8, 4 word block, 16 cache lines)90h76h0000000012h0000001000000011Addr: 000000xxBlock 0 35hAddr: 000001xxBlock 1Cache Lines: 0 15line: 0000line: 0001Addr: 010000xx22h10hBlock 1699h45h90h76h35h12hAddr: 111111xxAddr: 010000xxAddr: 111111xx5Addr: 000001xx0000000012h0000001000000011Addr: 111110xxAddr: 100001001000011111110Block 621111101011111011Block 636Z. Li, 2008Disk I/O PerformanceCache Sets: 0 7010Block1622h11111000Comp 212 Computer Org & ArchZ. Li, 2008Block 1Addr: 010000xxCache Lines: 0 15line: 1111Addr: 111110xx111110101111101190h76h22h10hBlock 1699h45h11Block 63Block 0 35h0000001000000011Block 12-way Set Associative Cache Mapping ExampleAddr: 000000xx12hAddr: 000001xx0100001001000011Comp 212 Computer Org & Arch00000000Block 0 35hline: 0000line: 000111111000Block 6290h76hAddr: 000000xx0001000000line: 1111Addr: 111110xxAssociative Mapping Example (W 8, 4 word block, 16 cache lines)22h10h99h45h00022h10h99h45h90h76h35h12h Total time:01000000– T Tseek 1/ (2*rpm) b / (rpm*N)0100001001000011– Disk spin speed: rpm11111111000Block 620000011111101011111011– Disk data density: N bytes per track– Tseek: how fast to locate a track,Block 63related to disk electro-mechanicalsystem performanceComp 212 Computer Org & Arch7Z. Li, 2008Comp 212 Computer Org & Arch8Z. Li, 2008

Integer Conversion between Binary and Decimal Systems62Numbers and Arithmetic in Computer1122320 (a0)16620 (a1)32021 (a2)101 (a3)(12)10 (a3 a2 a1 a0)2 (1100)2,N (an 1an 2 .a1a0 ) 2N / 2 ( an 1 2 n 1 an 2 2 n 2 . a1 21 a0 ) / 2(an 1 2n 2 an 2 2n 3 . a1 20 ) a0QuotientComp 212 Computer Org & Arch9Z. Li, 2008Fraction Conversion between Decimal and Binary SystemsMultiply MethodN .(a 1a 2 .a m )2Comp 212 Computer Org & ArchRemainder10Z. Li, 2008Exercise 2: Decimal to Binary(28.59)10 ( ? )2(Calculate up to 5 bits for fraction)N 2 .(a 1 2 1 a 2 2 2 . a m 2 m ) 2 a 1 .(a 2 2 1 . a m 2 m 1 )FractionInteger(0.7)10 (? )2Procedure: 0.7 x 2 1.40.4 x 2 0.80.8 x 2 1.6 .Comp 212 Computer Org & Arch11(0.7)10 0.(101 )2Z. Li, 2008Comp 212 Computer Org & Arch12Z. Li, 2008

Binary Addition and SubtractionBinary Multiplications and Divisions Relatively straight forward:Subtraction Rules:0-0 1-1 01-0 10-1 1 with a borrow of 1Addition Rules:0 0 sum-0 carry-01 0 sum-0 carry-01 1 sum-0 carry-111 1 1 carry1011 01011011- 0101011010000Comp 212 Computer Org & Archborrows13Z. Li, 2008– If multiplicate by 0, copy all zero– Add them together10111X1010000001011100000 1011111100110Comp 212 Computer Org & ArchBinary Divisions – If multiplicate by 1, copy the rowMultiplication:14Z. Li, 2008Signed Integers– Sign Magnitude : Rarely used147 / 11 ?– Division:– 2’s Complement (n bit) : -X [X]2 2n – (X)2– Simple Two Steps: -X [X] 1, [] is the Boolean complement operator,flipping each bit.1. Take the complement of each bit of N ( 0 1, 1 0 )given:Flipping each bit:2. Add 1.The complement:0011,11001100,0011 11100,0100 (sum: 1,000,0000)– Solution: Quotient 13 (1101)2, remainder 4 (100)2 .Comp 212 Computer Org & Arch15Z. Li, 2008Comp 212 Computer Org & Arch16Z. Li, 2008

2’s complement arithmetic2’s complement arithmetic examples Addition very much the same as un-signed A-B A [B]2 Overflow: iff A and B are the same sign while result notthe same sign Pad “1” to the negative number, and “0” to the positivenumber:– Eg. (-18)10 1001 0010 11111111 10010010– ( 18)10 00010010 00000000 00010010Comp 212 Computer Org & Arch17Z. Li, 2008Floating Point RepresentationZ. Li, 2008 For the 32 bit example in Fig. 9.18:– What is the sign, exponent, and significand ofthe following number ?Eg.: 30.25 ?(1)Integer part: 30 16 8 4 2 11110(2) Fraction part: 0.25 0.01(3) 30.25 11110.01, need to normalize s.t. the point isnext to the msb 1.(4)11110.01 (1.111001)x24, sign 0 (positive), exponent 4 bias 4 127 131 1000 0011 Signifcand 111001000000000000001918Floating Point Representation For the 32 bit example in Fig. 9.18:Comp 212 Computer Org & ArchComp 212 Computer Org & ArchZ. Li, 2008– What is the sign, exponent, and significand ofthe following number ?(2)-45.125 ?Integer part: 45 101101Fraction part: 0.125 0.00145.125 101101.001, need to normalize s.t. the point isnext to the msb 1.101101.001 (1.01101001)x25, sign 1 (negative), exponent 5 bias 5 127 132 1000 0100 Signifcand 01101001000000 000Comp 212 Computer Org & Arch20Z. Li, 2008

About Mid-term Mid-term Cover PageCoverage:– Only covers materials in lectures 1 5– Account for 25% of the final assessment, Quiz-1 will not be counted. Time & Venu:– Oct 30th, 2008, 8:30am-10:50am– Lecture Room N 001, the COMP 212 class room. Rules:– Close book, close notes– NO calculator– Do it independently, no discussion– Violation of Rules may result in zero marks for the mid-term.Comp 212 Computer Org & Arch21Z. Li, 2008Comp 212 Computer Org & Arch22Z. Li, 2008Reference Materials MIPS simulator on PC:– SPIM from Univ of Wisconsin:http://pages.cs.wisc.edu/ larus/spim.htmlMIPS Assembly Programming– Contains a lot of useful info, check it out and download the simulator. MIPS Assembly Programming– R. L. Britton– Optional but very useful– See to be available for download at:» nguage-ProgrammingComp 212 Computer Org & Arch23Z. Li, 2008Comp 212 Computer Org & Arch24Z. Li, 2008

OutlineMIPS Architecture Introduction to MIPS architectureArithmetic & Logic Ops MIPS Assembly Language– Arithmetic:» add, sub, addi, addu, addiu, subuProgram Control– Data movement :» lw, sw, lbu, sb, lui, ori– Program Control:» Branch, jump, stacks and procedure calls– MIPS programming examplesComp 212 Computer Org & Arch25Z. Li, 2008Comp 212 Computer Org & ArchAbout MIPS26Z. Li, 2008MIPS register file What is MIPS ? Total 32 registers– Microprocessor w/o Interlocked Pipeline Stages– Each 32 bit– In MIPS programming, named as 0 31, or : It is a RISC– as compared with CISC processor like Pentium– Very successful, 1/3 RISC chip is MIPS based.– Used in SGI stations, CISCO routers, Motorola Set-Top Boxes,SONY Play station, PSP, Nintendo 64 .etc.Comp 212 Computer Org & Arch27Z. Li, 2008Comp 212 Computer Org & Arch28Z. Li, 2008

MIPS Assembly ProgramsExample: add rd, rs, rt MIPS instructions and data– Instructions are given in .text segments» A MIPS program can have multiple .text segments– Data are defined in .data segments using MIPS assembly directives» .word, for example, defines the following numbers in successive memorywords Assembly Programs– One instruction one line (32 bit)– Use readable symbols instead of 32 bits 10101010 patternsComp 212 Computer Org & Arch29Z. Li, 2008Comp 212 Computer Org & Archaddi rt, rs, imm30Z. Li, 2008Arithmetic Instructions Additions: I Type (Immediate) instruction:– rt rt rs imm– 5 bits to specify one of the 32 registers– 16 bit for immediate number (signed)Comp 212 Computer Org & Arch31– Add rd, rs, rt# rd rs rt, signed int– Addu rd, rs, rt# rd rs rt, unsigned– Addi rt, rs, imm# rt rs imm– Addiu rt, rs, imm# rt rs imm, unsigned Subtraction:Z. Li, 2008– Sub rd, rs, rt# rd rs – rt– Subu rd, rs, rt# rd rs - rtComp 212 Computer Org & Arch32Z. Li, 2008

First MIPS ProgramRun it with SPIM simulator How to compute:– A 19 20 – 24 ? Program:– Li reg, imm# load imm value to registerComp 212 Computer Org & Arch33Z. Li, 2008Comp 212 Computer Org & ArchMore complex arithmetic MIPS memory– 32 bit mem address [0 232-1] mem address space– Organized in word (32 bit), has address in multiples of 4 Use Macros: sub and mul Load word from memory––––– MIPS programli t0, xli t1, yadd t0, t0, 5#x 5sub t0, t0, t1#x 5-ymul t0, t0, 35#(x 5 - y)*35div t0, t0, 3#(x 5 - y)*35/3Comp 212 Computer Org & ArchZ. Li, 2008Data Load and Movement Compute: (x 5 - y) * 35 / 3–3435Lw dest reg, const(addr start reg)Dest reg : specify which register to load word toConst: a constant numberAddr start reg: where data array startsEffective address: (addr start reg) const Example– Lw s0, 4( s3)– La s4, gradesZ. Li, 2008Comp 212 Computer Org & Arch# load word at ( s3) 4# load array “grades” start addr to s436Z. Li, 2008

Example of Load/Save DataProgram 3 students’ grades are saved in the memory, compute its .text signal the startsum and store at the end of array:of program Grades [94 90 83], store 94 90 83 at Total .data signal the startof data definitions Use store register value to mem:– Sw s1, 12( s2) Data labels, “grades”,# store s1 to mem start at s2, with offset 12“total” has a mem addr.Comp 212 Computer Org & Arch37Z. Li, 2008Comp 212 Computer Org & ArchExecution in SPIM38Z. Li, 2008Address Mode Why this weird way of address memory ?– To support array operation which is very typical– A register offers base, or start of array address– Immediate number provides the offset– ! Notice that word address increment by 4, so element k in the arrayhas offset 4*k:Comp 212 Computer Org & Arch39Z. Li, 2008Comp 212 Computer Org & Arch40Z. Li, 2008

Branch and JumpingBranch and Jumping The syntax: How about the following program control: MIPS implementation– begz r1, r2, addr# if r1 r2, jump to addr– beq r1, r2, addr# if r1 r2, jump to addr– bne, r1, r2, addr# if r1 r2, jump to addr– bgtz, r1, addr# if r1 0, jump to addr– b next# branch around jump to next Address labels: next, addr– The address labels are offset relative to current PC– Computed at the compiling time.– Offset signed integer, so we can jump back and forwards– Limitation: 15 bits for addr, limited jump spaceComp 212 Computer Org & Arch41Z. Li, 2008Comp 212 Computer Org & ArchIF-THEN42Z. Li, 2008For Loop Operations IF-THEN operation: For loop control: MIPS implementation MIPS Implementation:Comp 212 Computer Org & Arch43Z. Li, 2008Comp 212 Computer Org & Arch44Z. Li, 2008

While Loop ControlExample: String Copy While Loop: String copy in C:While ( a1 a2) do{ a1 a1 1 a2 sa - 1} MIPS implementation: Copy contents from mem location X to Y String by def are 0 terminated.– X [12, 3, 2, 19, 0], Y [ 23, 4, 5, 0], then after strcpy(x, y)– X [23, 4, 5, 0]Comp 212 Computer Org & Arch45Z. Li, 2008Comp 212 Computer Org & ArchExample: String Copy46Z. Li, 2008MIPS implementation MIPS implementation:– Load/store byte from memory:» lb t0, 0( s2)# load byte to address in ( s2)» sb t0, 0( s3)# store byte to address in ( s3)– Increment/Decrement register by 1, as byte address are incremented by 1» addi s0, s0, 1#s0 » addi s0, s0, -1# s0--– System call to print a string to the console:» li v0, 4» la a0, str» syscallComp 212 Computer Org & Arch47Z. Li, 2008Comp 212 Computer Org & Arch48Z. Li, 2008

Subroutine CallsRegister usage convention Goal: a0 a4:– A segment of code for certain functions that can be called by others,– Example: multiply, y mult(x1, x2)– registers for passing arguments v0, v1: Issues:– return values– How to call a subroutine ? ra:» How to pass parameters, e.g. x1, x2– return address register, sub routine should return to when finishing» How to get return values ?, eg. Y ?up the operation. Use stack to implement– How to write a subroutine ?– Before calling the subroutine, save PC 4 to ra,» Where to look for parameters ?» Use jump & link: jal mult subroutine» Save registers, return value– Return by calling jr ra» Return to the caller.Comp 212 Computer Org & Arch49Z. Li, 2008Comp 212 Computer Org & ArchSave registers50Z. Li, 2008An example What if sub routines need to use registers ? Compute the sum of an array:– int sum(*x, n) Temp registers are ok– Psuedo code:– t0 t7, no need to save their valueSum 0; Need to save before use:For k 1:n– s0 s7Sum sum x(k);– Usually done by push to stack and pop out later before jr raEnd– parameters:» a0 : *x, array address, a1: n» Return: v0Comp 212 Computer Org & Arch51Z. Li, 2008Comp 212 Computer Org & Arch52Z. Li, 2008

MIPS implementationMIPS implementation Call it in main:– Move parameters to a0, a1– Call sum by: jal sum– Retrieve results and print: v0Comp 212 Computer Org & Arch53Z. Li, 2008Comp 212 Computer Org & ArchRun it in Simulator54Summary-Useful MIPS instructionsaddMIPS assembly languageExampleMeaningadd s1, s2, s3 s1 s2 s3Three operands; data in registerssubtractsub s1, s2, s3 s1 s2 - s3Three operands; data in registers s1 s2 100 s1 Memory[ s2 100]Memory[ s2 100] s1 s1 Memory[ s2 100]Memory[ s2 100] s1Used to add constantsCategoryArithmeticInstructionadd immediateaddi s1, s2, 100lw s1, 100( s2)store wordsw s1, 100( s2)lb s1, 100( s2)Data transfer load bytestore bytesb s1, 100( s2)load upper immediate lui s1, 100load wordConditionalbranchUnconditional jumpComp 212 Computer Org & Arch55Z. Li, 2008Z. Li, 2008 s1 100 * 216CommentsWord from memory to registerWord from register to memoryByte from memory to registerByte from register to memoryLoads constant in upper 16 bitsbranch on equalbeq s1, s2, 25if ( s1 s2) go toPC 4 100Equal test; PC-relative branchbranch on not equalbne s1, s2, 25if ( s1 ! s2) go toPC 4 100Not equal test; PC-relativeset on less thanslt s1, s2, s3if ( s2 s3) s1 1;else s1 0Compare less than; for beq, bneset less thanimmediatesltijumpjjrjaljump registerjump and linkComp 212 Computer Org & Arch s1, s2, 100 if ( s2 100) s1 1;Compare less than constantelse s1 0Jump to target addressgo to 10000For switch, procedure returngo to ra ra PC 4; go to 10000 For procedure call2500 ra250056Z. Li, 2008

MIPS Summary A RISC architecture 32 registers Instructions:– Data movement– Arithmetic– Program Control– Subroutine and System CallsComp 212 Computer Org & Arch57Z. Li, 2008

Introduction to MIPS architecture MIPS Assembly Language – Arithmetic: » add, sub, addi, addu, addiu, subu – Data movement : » lw, sw, lbu, sb, lui, ori – Program Control: » Branch, jump, stacks and procedure calls – MIPS programming examples Comp 212 Computer Org & ArchComp 212 Compute