← Back to branch summary

~ubuntu-branches/ubuntu/intrepid/ecl/intrepid

« back to all changes in this revision

Viewing changes to src/gmp/mpn/x86/k7/README

  • Committer: Bazaar Package Importer
  • Author(s): Peter Van Eynde
  • Date: 2006-05-17 02:46:26 UTC
  • Revision ID: james.westby@ubuntu.com-20060517024626-lljr08ftv9g9vefl
Tags: upstream-0.9h-20060510
Import upstream version 0.9h-20060510

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/gmp/mpn/x86/k7/README
 
1
Copyright 2000, 2001 Free Software Foundation, Inc.
 
2
 
 
3
This file is part of the GNU MP Library.
 
4
 
 
5
The GNU MP Library is free software; you can redistribute it and/or modify
 
6
it under the terms of the GNU Lesser General Public License as published by
 
7
the Free Software Foundation; either version 2.1 of the License, or (at your
 
8
option) any later version.
 
9
 
 
10
The GNU MP Library is distributed in the hope that it will be useful, but
 
11
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 
12
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
 
13
License for more details.
 
14
 
 
15
You should have received a copy of the GNU Lesser General Public License
 
16
along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
 
17
the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 
18
02111-1307, USA.
 
19
 
 
20
 
 
21
 
 
22
 
 
23
                      AMD K7 MPN SUBROUTINES
 
24
 
 
25
 
 
26
This directory contains code optimized for the AMD Athlon CPU.
 
27
 
 
28
The mmx subdirectory has routines using MMX instructions.  All Athlons have
 
29
MMX, the separate directory is just so that configure can omit it if the
 
30
assembler doesn't support MMX.
 
31
 
 
32
 
 
33
 
 
34
STATUS
 
35
 
 
36
Times for the loops, with all code and data in L1 cache.
 
37
 
 
38
                               cycles/limb
 
39
        mpn_add/sub_n             1.6
 
40
 
 
41
        mpn_copyi                 0.75 or 1.0   \ varying with data alignment
 
42
        mpn_copyd                 0.75 or 1.0   /
 
43
 
 
44
        mpn_divrem_1             17.0 integer part, 15.0 fractional part
 
45
        mpn_mod_1                17.0
 
46
        mpn_divexact_by3          8.0
 
47
 
 
48
        mpn_l/rshift              1.2
 
49
 
 
50
        mpn_mul_1                 3.4
 
51
        mpn_addmul/submul_1       3.9
 
52
 
 
53
        mpn_mul_basecase          4.42 cycles/crossproduct (approx)
 
54
        mpn_sqr_basecase          2.3 cycles/crossproduct (approx)
 
55
                                  or 4.55 cycles/triangleproduct (approx)
 
56
 
 
57
Prefetching of sources hasn't yet been tried.
 
58
 
 
59
 
 
60
 
 
61
NOTES
 
62
 
 
63
cmov, MMX, 3DNow and some extensions to MMX and 3DNow are available.
 
64
 
 
65
Write-allocate L1 data cache means prefetching of destinations is unnecessary.
 
66
 
 
67
Floating point multiplications can be done in parallel with integer
 
68
multiplications, but there doesn't seem to be any way to make use of this.
 
69
 
 
70
Unsigned "mul"s can be issued every 3 cycles.  This suggests 3 is a limit on
 
71
the speed of the multiplication routines.  The documentation shows mul
 
72
executing in IEU0 (or maybe in IEU0 and IEU1 together), so it might be that,
 
73
to get near 3 cycles code has to be arranged so that nothing else is issued
 
74
to IEU0.  A busy IEU0 could explain why some code takes 4 cycles and other
 
75
apparently equivalent code takes 5.
 
76
 
 
77
 
 
78
 
 
79
OPTIMIZATIONS
 
80
 
 
81
Unrolled loops are used to reduce looping overhead.  The unrolling is
 
82
configurable up to 32 limbs/loop for most routines and up to 64 for some.
 
83
The K7 has 64k L1 code cache so quite big unrolling is allowable.
 
84
 
 
85
Computed jumps into the unrolling are used to handle sizes not a multiple of
 
86
the unrolling.  An attractive feature of this is that times increase
 
87
smoothly with operand size, but it may be that some routines should just
 
88
have simple loops to finish up, especially when PIC adds between 2 and 16
 
89
cycles to get %eip.
 
90
 
 
91
Position independent code is implemented using a call to get %eip for the
 
92
computed jumps and a ret is always done, rather than an addl $4,%esp or a
 
93
popl, so the CPU return address branch prediction stack stays synchronised
 
94
with the actual stack in memory.
 
95
 
 
96
Branch prediction, in absence of any history, will guess forward jumps are
 
97
not taken and backward jumps are taken.  Where possible it's arranged that
 
98
the less likely or less important case is under a taken forward jump.
 
99
 
 
100
 
 
101
 
 
102
CODING
 
103
 
 
104
Instructions in general code have been shown grouped if they can execute
 
105
together, which means up to three direct-path instructions which have no
 
106
successive dependencies.  K7 always decodes three and has out-of-order
 
107
execution, but the groupings show what slots might be available and what
 
108
dependency chains exist.
 
109
 
 
110
When there's vector-path instructions an effort is made to get triplets of
 
111
direct-path instructions in between them, even if there's dependencies,
 
112
since this maximizes decoding throughput and might save a cycle or two if
 
113
decoding is the limiting factor.
 
114
 
 
115
 
 
116
 
 
117
INSTRUCTIONS
 
118
 
 
119
adcl       direct
 
120
divl       39 cycles back-to-back
 
121
lodsl,etc  vector
 
122
loop       1 cycle vector (decl/jnz opens up one decode slot)
 
123
movd reg   vector
 
124
movd mem   direct
 
125
mull       issue every 3 cycles, latency 4 cycles low word, 6 cycles high word
 
126
popl       vector (use movl for more than one pop)
 
127
pushl      direct, will pair with a load
 
128
shrdl %cl  vector, 3 cycles, seems to be 3 decode too
 
129
xorl r,r   false read dependency recognised
 
130
 
 
131
 
 
132
 
 
133
REFERENCES
 
134
 
 
135
"AMD Athlon Processor X86 Code Optimization Guide", AMD publication number
 
136
22007, revision E, November 1999.  Available on-line,
 
137
 
 
138
        http://www.amd.com/products/cpg/athlon/techdocs/pdf/22007.pdf
 
139
 
 
140
"3DNow Technology Manual", AMD publication number 21928F/0-August 1999.
 
141
This describes the femms and prefetch instructions.  Available on-line,
 
142
 
 
143
        http://www.amd.com/K6/k6docs/pdf/21928.pdf
 
144
 
 
145
"AMD Extensions to the 3DNow and MMX Instruction Sets Manual", AMD
 
146
publication number 22466, revision B, August 1999.  This describes
 
147
instructions added in the Athlon processor, such as pswapd and the extra
 
148
prefetch forms.  Available on-line,
 
149
 
 
150
        http://www.amd.com/products/cpg/athlon/techdocs/pdf/22466.pdf
 
151
 
 
152
"3DNow Instruction Porting Guide", AMD publication number 22621, revision B,
 
153
August 1999.  This has some notes on general Athlon optimizations as well as
 
154
3DNow.  Available on-line,
 
155
 
 
156
        http://www.amd.com/products/cpg/athlon/techdocs/pdf/22621.pdf
 
157
 
 
158
 
 
159
 
 
160
 
 
161
----------------
 
162
Local variables:
 
163
mode: text
 
164
fill-column: 76
 
165
End: