Manuals / AMD / Computer Equipment / Typewriter

AMD x86 manual Pipelined Pair of 24-Bit Precision Divides, Newton-Raphson Reciprocal

Models: x86

1 256

Download 256 pages 58.62 Kb

Page 125

22007E/0 — November 1999

AMD Athlon™ Processor x86 Code Optimization

Pipelined Pair of 24-Bit Precision Divides

This divide operation executes with a total latency of 21 cycles, assuming that the program hides the latency of the first MOVD/MOVQ instructions within preceding code.

Example:

MOVQ	MM0, [DIVISORS]	;	y x
PFRCP	MM1, MM0	; 1/x 1/x		(approximate)
MOVQ	MM2, MM0	;	y x
PUNPCKHDQ	MM0, MM0	;	y y
PFRCP	MM0, MM0	; 1/y 1/y		(approximate)
PUNPCKLDQ	MM1, MM0	; 1/y 1/x		(approximate)
MOVQ	MM0, [DIVIDENDS]	;	z w
PFRCPIT1	MM2, MM1	; 1/y 1/x		(intermediate)
PFRCPIT2	MM2, MM1	; 1/y 1/x		(final)
PFMUL	MM0, MM2	; z/y w/x

Newton-Raphson Reciprocal

Consider the quotient q = a/b. An (on-chip) ROM-based table lookup can be used to quickly produce a 14-to-15-bit precision approximation of 1/b using just one PFRCP instruction. A full 24-bit precision reciprocal can then be quickly computed from this approximation using a Newton Raphson algorithm.

The general Newton-Raphson recurrence for the reciprocal is as follows:

Zi+1 = Zi • (2 – b • Zi)

Given that the initial approximation is accurate to at least 14 bits, and that a full IEEE single-precision mantissa contains 24 bits, just one Newton-Raphson iteration is required. The following sequence shows the 3DNow! instructions that produce the initial reciprocal approximation, compute the full precision reciprocal from the approximation, and finally, complete the desired divide of a/b.

X0 = PFRCP(b)

X1 = PFRCPIT1(b,X0)

X2 = PFRCPIT2(X1,X0)

q= PFMUL(a,X2)

The 24-bit final reciprocal value is X2. In the AMD Athlon processor 3DNow! technology implementation the operand X2 contains the correct round-to-nearest single precision reciprocal for approximately 99% of all arguments.

Use 3DNow!™ Instructions for Fast Division

109

Image 125

AMD x86 manual Pipelined Pair of 24-Bit Precision Divides, Newton-Raphson Reciprocal

Contents

AMD AthlonTM Processor Trademarks Contents Instruction Decoding Optimizations Cache and Memory Optimizations Scheduling Optimizations Floating-Point Optimizations General x86 Optimization Guidelines 127 Appendix B Pipeline and Execution Unit Resources Overview Appendix E Programming the Mtrr and PAT List of Figures Xii List of Tables Xiv Revision History Xvi About this Document IntroductionSource Level Optimizations. Describes optimizations that AMD Athlon Processor Family AMD Athlon Processor Microarchitecture Summary AMD Athlon Processor Microarchitecture Summary AMD Athlon Processor x86 Code Optimization Top Optimizations Optimization Star Memory Size and Alignment IssuesGroup I Optimizations Essential Optimizations Use the 3DNow! Prefetch and Prefetchw InstructionsSelect DirectPath Over VectorPath Instructions Group II Optimizations-Secondary OptimizationsLoad-Execute Instruction Usage Use Load-Execute InstructionsAvoid Branches Dependent on Random Data Take Advantage of Write CombiningUse 3DNow! Instructions Avoid Placing Code and Data in the Same 64-Byte Cache Line 22007E/0 November Use 32-Bit Data Types for Integer Code Source Level OptimizationsExample Preferred Consider the Sign of Integer OperandsExample 1 Avoid Example Avoid Use Array Style Instead of Pointer Style CodeUse unsigned types for Use signed types forVertex Example 2 Preferred Avoid Unnecessary Store-to-Load Dependencies Completely Unroll Small LoopsAvoid Unnecessary Store-to-Load Dependencies Consider Expression Order in Compound Branch Conditions Use Prototypes for All Functions Switch Statement UsageOptimize Switch Statements Example Use Const Type QualifierGeneric Loop Hoisting Generalization for Multiple Constant Control Code Declare Local Functions as Static Introduce Explicit Parallelism into Code Dynamic Memory Allocation ConsiderationExplicitly Extract Common Subexpressions Example Language Structure Component ConsiderationsAvoid PreferredNew ordering, with padding Preferred Sort Local Variables According to Base Type SizeOriginal ordering Avoid Improved ordering Preferred Accelerating Floating-Point Divides and Square RootsAccelerating Floating-Point Divides and Square Roots Avoid Unnecessary Integer Division AMD Athlon Processor x86 Code Optimization Overview Instruction Decoding OptimizationsUse Load-Execute Integer Instructions Select DirectPath Over VectorPath InstructionsLoad-Execute Instruction Usage TOP Use Short Instruction Lengths Align Branch Targets in Program Hot SpotsExample 2 Avoid Avoid Partial Register Reads and WritesReplace Certain Shld Instructions with Alternative Code Use 8-Bit Sign-Extended ImmediatesCode Padding Using Neutral Code Fillers Use 8-Bit Sign-Extended DisplacementsRecommendations for the AMD Athlon Processor Code Padding Using Neutral Code Fillers AMD Athlon Processor x86 Code Optimization NOP6EDI AMD Athlon Processor x86 Code Optimization Avoid Memory Size Mismatches Memory Size and Alignment IssuesCache and Memory Optimizations Use the 3DNow! Prefetch and Prefetchw Instructions Align Data Where PossibleCode Example Multiple PrefetchesMOV ECX, -LARGENUM Prefetch Distance = 200 DS/C bytes Determining Prefetch DistanceAvoid Placing Code and Data in the Same 64-Byte Cache Line Take Advantage of Write CombiningStore-to-Load Forwarding Pitfalls -True Dependencies Store-to-Load Forwarding RestrictionsExample 4 Avoid Example 3 AvoidExample 7 Avoid Example 5 PreferredExample 6 Avoid Summary of Store-to-Load Forwarding Pitfalls to Avoid Stack Alignment ConsiderationsAlign Tbyte Variables on Quadword Aligned Addresses Sort Variables According to Base Type Size Avoid Branches Dependent on Random Data Branch OptimizationsBlended AMD-K6and AMD Athlon Processor Code AMD Athlon Processor Specific CodeExample 7 Integer Signum Function Always Pair Call and ReturnExample 6 Increment Ring Buffer Offset Muxing Constructs Replace Branches with Computation in 3DNow! Code3DNow! code Sample Code Translated into 3DNow! CodeCode MM5 Pfsub Psrad Avoid Far Control Transfer Instructions Avoid the Loop InstructionAvoid Recursive Functions Schedule Instructions According to their Latency Scheduling OptimizationsUnrolling Loops Complete Loop UnrollingPartial Loop Unrolling With Partial Loop Unrolling Without Loop UnrollingControl For Partially Deriving LoopUnrolled Loops Example 1 rolled loopOverview Use Function InliningAlways Inline Functions if Called from One Site Avoid Address Generation InterlocksMinimize Pointer Arithmetic in Loops Use Movzx and MovsxMOV ECX, Maxsize Example 3 Preferred Push Memory Data CarefullyPush Memory Data Carefully Multiplication by Reciprocal Division Utility Integer OptimizationsReplace Divides with Multiplies Unsigned Division by Multiplication of Constant Restricted Dividend Signed Division by Multiplication of ConstantSimpler Code for Signed Division By 2n Signed Division ByRemainder of Signed Integer 2 orInteger 2n or -2n Use Alternative Code When Multiplying by a ConstantADD REG1, REG1 REG1, REG2 SHL Use MMX Instructions for Integer-Only Work Guidelines for Repeated String Instructions Repeated String Instruction UsageLatency of Repeated String Instructions Ensure DF=0 UP Using MovqAlign Source Destination withEfficient 64-Bit Integer Arithmetic Use XOR Instruction to Clear Integer RegistersExample 6 Multiplication Example 4 Left shiftExample 5 Right shift EBX, ESP+12 Dividendlo Example 7 DivisionExample 8 Remainder SHR EDX Step Efficient Implementation of Population Count FunctionBit field. Thus the following computation is performed MOV EDX, EDX SHR Derivation of Multiplier Used for Integer Division by Utility sdiv.exe was compiled using the following code MOV ECX EDX Imul ADD SHR SAR Use Multiplies Rather than Divides Floating-Point OptimizationsEnsure All FPU Data is Aligned Use Ffreep Macro to Pop One Register from the FPU Stack Floating-Point Compare InstructionsUse the Fxch Instruction Rather than FST/FLD Pairs Avoid Using Extended-Precision DataExample 1 Fast Minimize Floating-Point-to-Integer ConversionsExample 2 Potentially faster Example 4 Fastest Example 3 Potentially fasterFloating-Point Subexpression Elimination 104 Take Advantage of the Fsincos Instruction 106 Use Femms Instruction 3DNow! and MMX OptimizationsUse 3DNow! Instructions Optimized Full 24-Bit Precision Divide Use 3DNow! Instructions for Fast DivisionOptimized 14-Bit Precision Divide Newton-Raphson Reciprocal Pipelined Pair of 24-Bit Precision DividesOptimized 24-Bit Precision Square Root Optimized 15-Bit Precision Square RootNewton-Raphson Reciprocal Square Root AMD Athlon 3DNow! and MMX Intra-Operand SwappingSpecific Code Blended CodeUse MMX Pxor to Negate 3DNow! Data Fast Conversion of Signed Words to Floating-PointBoth Numbers Use MMX Pcmp Instead of 3DNow! PfcmpPositive One Negative, One PositiveAMD-K6and AMD Athlon Processor Blended Code Use MMX Instructions for Block Copies and Block Fills116 Processor Specific Use MMX Pxor to Clear All Bits in an MMX Register Use MMX Pcmpeqd to Set All Bits in an MMX Register Optimized Matrix MultiplicationMOV EBX, RES Optimized Matrix Multiplication 121 Data Use 3DNow! Pavgusb for MPEG-2 Motion Compensation MM0=QWORD1 Stream of Packed Unsigned Bytes Complex Number Arithmetic Short Forms General x86 Optimization GuidelinesStack Allocation DependenciesRegister Operands Introduction AMD Athlon Processor MicroarchitectureSuperscalar Processor AMD Athlon Processor MicroarchitectureAMD Athlon Processor Microarchitecture 131 Branch Prediction PredecodeEarly Decoding Data Cache Instruction Control UnitInteger Execution Unit Integer SchedulerFloating-Point Scheduler 12 to Floating-Point Execution UnitLoad/Store Unit Load-Store Unit LSUAMD Athlon System Bus L2 Cache ControllerWrite Combining 140 AMD Athlon Processor Microarchitecture Fetch and Decode Pipeline Stages Pipeline and Execution Unit Resources OverviewC T L R O M Cycle 2-SCAN Cycle 1-FETCHCycle 3 DirectPath Cycle 3 VectorPathInteger Pipeline Stages Integer Pipeline StagesCycle 8-EXEC Cycle 7-SCHEDCycle 9-ADDGEN Cycle 10 -DCACCFloating-Point Pipeline Stages Floating-Point Pipeline StagesCycle 8-REGREN Cycle 7-STKRENCycle 9-SCHEDW Cycle 10 -SCHEDTerminology Execution Unit ResourcesOperands ResultsInteger Decode Types Integer Pipeline OperationsInteger Pipeline Operation Types Floating-Point Decode Types Floating-Point Pipeline OperationsFloating-Point Pipeline Operation Types Stage 1 Cycle Stage 2 Cycle Stage 3 Cycle Load/Store Pipeline OperationsLoad/Store Unit Stages Code Sample Analysis INC EBX ADD ESI, EDX Imul EAX, ECX INC ESI MOVADD EDI, EBX SHL SAR Sample 2 Integer Register and Memory Load OperationsDEC EDX MOV EDI, ECX SUB Implementation Write Combining Appendix CProgramming Details What is Write Combining?Write-Combining Definitions and Abbreviations Write-Combining Operations INIT, Halt Write Combining Completion EventsSending Write-Buffer Data to the System AMD Athlon System Bus Commands Generation Rules160 Write-Combining Operations Performance Counter Usage Performance-Monitoring CountersPerfEvtSel30 Registers PerfEvtSel30 MSRs MSR Addresses C0010000h-C0010003hPerformance Counter Usage 163 Performance-Monitoring Counters 73h 65hSnoop hits 74hWaited to use the L2 Event Source Event DescriptionInstruction cache fetches Instruction cache missesPerfCtr30 MSRs MSR Addresses C0010004h-C0010007h Starting and Stopping the Performance-Monitoring Counters Event and Time-Stamp Monitoring SoftwareMonitoring Counter Overflow 170 Monitoring Counter Overflow Memory Type Range Register Mtrr Mechanism Programming the Mtrr172 Memory Type Range Register Mtrr Mechanism 100000h Kbytes each Fixed Ranges C0000h 80000h Fixed RangesFFFFFFFFh Memory Type Encodings Memory TypesMtrr Capability Register FormatMemory Type Range Register Mtrr Mechanism 175 Standard Mtrr Types and Properties Attribute Table MSR 277h Attribute Table PATPATi 3-Bit Encodings PAT Entry Reset ValueMTRRs and PAT PATiPAT Memory Type Mtrr Memory Type Effective Memory Type Based on PAT and MTRRsInput Memory Type Final Output Memory TypesAttribute Table PAT 181 9FFFF 9BFFF 97FFF 93FFF 8FFFF 8BFFF 87FFF 83FFF 7FFFF 6FFFF 5FFFF 4FFFF 3FFFF 2FFFF 1FFFF 0FFFFBffff Bbfff B7FFF B3FFF Affff Abfff A7FFF A3FFF C7FFF C6FFF C5FFF C4FFF C3FFF C2FFF C1FFF C0FFFAttribute Table PAT 183 MTRRphysMaskn Register Format MTRR-Related Model-Specific Register MSR Map 186 Instruction Dispatch Execution Resources Appendix FAAA Integer InstructionsAAD AAMADC mreg8, reg8 ModR/M Decode ByteADC mem8, reg8 ADC mreg16/32, reg16/32Bswap EAX BoundBswap ECX Bswap EDXCLC CBW/CWDECLD CLICMOVE/CMOVZ reg16/32, mem16/32 0Fh CMOVE/CMOVZ reg16/32, reg16/32 0FhCMOVG/CMOVNLE reg16/32, reg16/32 0Fh CMOVG/CMOVNLE reg16/32, mem16/32 0FhCWD/CDQ CpuidDAA DASAL, DX EnterAX, DX EAX, DXInvlpg InvdLeave LahfLOOPNE/LOOPNZ disp8 E0h LOOPE/LOOPZ disp8 E1hLSL reg16/32, mreg16/32 0Fh 03h LSL reg16/32, mem16/32 0Fh 03hNOP Xchg EAX, EAX OUT DX, AX OUT DX, ALOUT DX, EAX POP ESPOP ESP POP EBXPOP EBP POP ESIRdtsc RdmsrRdpmc Sahf SBB mem16/32, reg16/32 SBB mreg16/32, reg16/32SBB reg8, mreg8 SBB reg8, mem8Sets mem8 Sets mreg8Setns mreg8 Setns mem8STI STCSTD Sysenter SyscallSysexit SysretXchg EAX, ECX Xchg EAX, EAXXchg EAX, EDX Xchg EAX, EBXEmms MMX InstructionsDFh Pandn mmreg1, mmreg2Pandn mmreg, mem64 Pcmpeqb mmreg1, mmreg2FADD/FMUL FPU MMX ExtensionsFloating-Point Instructions Fdecstp FcomppFcos FLD1 FincstpFinit FLDL2T FLDL2EFLDLG2 FLDLN2Ftst Fstsw AXFucom FucompFemms DNow! InstructionsDNow! Extensions DirectPath Instructions DirectPath versus VectorPath InstructionsCBW/CWDE CLC CMC DirectPath Integer InstructionsBT mreg16/32, reg16/32 BT mreg16/32, imm8 BT mem16/32, imm8 INC mreg8 INC mem8 INC mreg16/32 INC mem16/32 JO short disp8 DEC mreg8 DEC mem8 DEC mreg16/32 DEC mem16/32222 DirectPath Instructions DirectPath Instructions 223 224 DirectPath Instructions Wait Xchg EAX, EAX 226 DirectPath Instructions DirectPath MMX Instructions DirectPath MMX Extensions Fcompp Fdecstp DirectPath Floating-Point InstructionsFist mem16int FLD1 FLDL2E FLDL2T FLDLG2 FLDLN2 Fldpi FldzFtst Fucom Fucomp Fucompp Fwait Fxch VectorPath Integer Instructions VectorPath InstructionsAAA AAD AAM AAS CLD CLI CltsAL, DX AX, DX EAX, DX Invd Invlpg Instruction Mnemonic DIV EAX, mem16/32Push mreg16/32 Push mem16/32 POP mreg 16/32 POP mem 16/32PUSHA/PUSHAD PUSHF/PUSHFD Rdmsr Rdpmc RdtscVectorPath MMX Extensions VectorPath MMX InstructionsSyscall Sysenter Sysexit Sysret Wbinvd WrmsrFptan Fpatan Frndint VectorPath Floating-Point InstructionsFscale Fsin Fsincos Fxam Fxtract FYL2X FYL2XP1236 Index 238 Index Index 239 240 Index