Annotation of OpenXM_contrib/gmp/doc/tasks.html, Revision 1.1.1.1
1.1 maekawa 1: <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
2: <html>
3: <head>
4: <title>
5: GMP Itemized Development Tasks
6: </title>
7: </head>
8: <body bgcolor=lightgreen>
9:
10: <center>
11: <h1>
12: GMP Itemized Development Tasks
13: </h1>
14: </center>
15:
16: <comment>
17: An up-to-date html version of this file is available at
18: <a href="http://www.swox.com/gmp/tasks.html">http://www.swox.com/gmp/tasks.html</a>.
19: </comment>
20:
21: <p> This file lists itemized GMP development tasks. Not all the tasks
22: listed here are suitable for volunteers, but many of them are.
23: Please see the <a href="projects.html">projects file</a> for more
24: sizeable projects.
25:
26: <h4>Correctness and Completeness</h4>
27: <ul>
28: <li> HPUX 10.20 assembler requires a `.LEVEL 1.1' directive for accepting the
29: new instructions. Unfortunately, the HPUX 9 assembler as well as earlier
30: assemblers reject that directive. How very clever of HP! We will have to
31: pass assembler options, and make sure it works with new and old systems
32: and GNU assembler.
33: <li> The various reuse.c tests need to force reallocation by calling
34: <code>_mpz_realloc</code> with a small (1 limb) size.
35: <li> One reuse case is missing from mpX/tests/reuse.c: <code>mpz_XXX(a,a,a)</code>.
36: <li> When printing mpf_t numbers with exponents > 2^53 on machines with 64-bit
37: <code>mp_exp_t</code>, the precision of
38: <code>__mp_bases[base].chars_per_bit_exactly</code> is insufficient and
39: <code>mpf_get_str</code> aborts. Detect and compensate.
40: <li> Fix <code>mpz_get_si</code> to work properly for MIPS N32 ABI (and other
41: machines that use <code>long long</code> for storing limbs.)
42: <li> Make the string reading functions allow the `0x' prefix when the base is
43: explicitly 16. They currently only allow that prefix when the base is
44: unspecified.
45: <li> In the development sources, we return abs(a%b) in the
46: <code>mpz_*_ui</code> division routines. Perhaps make them return the
47: real remainder instead? Changes return type to <code>signed long int</code>.
48: <li> <code>mpf_eq</code> is not always correct, when one operand is
49: 1000000000... and the other operand is 0111111111..., i.e., extremely
50: close. There is a special case in <code>mpf_sub</code> for this
51: situation; put similar code in <code>mpf_eq</code>.
52: <li> mpf_eq doesn't implement what gmp.texi specifies. It should not use just
53: whole limbs, but partial limbs.
54: <li> Install Alpha assembly changes (prec/gmp-alpha-patches).
55: <li> NeXT has problems with newlines in asm strings in longlong.h. Also,
56: <code>__builtin_constant_p</code> is unavailable? Same problem with MacOS
57: X.
58: <li> Shut up SGI's compiler by declaring <code>dump_abort</code> in
59: mp?/tests/*.c.
60: <li> <code>mpz_get_si</code> returns 0x80000000 for -0x100000000.
61: </ul>
62:
63:
64:
65: <h4>Machine Independent Optimization</h4>
66: <ul>
67: <li> In hundreds of places in the code, we invoke count_leading_zeros and then
68: check if the returned count is zero. Instead check the most significant
69: bit of the operand, and avoid invoking <code>count_leading_zeros</code> if
70: the bit is set. This is an optimization on all machines, and significant
71: on machines with slow <code>count_leading_zeros</code>.
72: <li> In a couple of places <code>count_trailing_zeros</code> is used
73: on more or less uniformly distributed numbers. For some CPUs
74: <code>count_trailing_zeros</code> is slow and it's probably worth
75: handling the frequently occurring 0 to 2 trailing zeros cases specially.
76: <li> Change all places that use <code>udiv_qrnnd</code> for inverting limbs to
77: instead use <code>invert_limb</code>.
78: <li> Reorganize longlong.h so that we can inline the operations even for the
79: system compiler. When there is no such compiler feature, make calls to
80: stub functions. Write such stub functions for as many machines as
81: possible.
82: <li> Rewrite <code>umul_ppmm</code> to use floating-point for generating the
83: most significant limb (if <code>BITS_PER_MP_LIMB</code> <= 52 bits).
84: (Peter Montgomery has some ideas on this subject.)
85: <li> Improve the default <code>umul_ppmm</code> code in longlong.h: Add partial
86: products with fewer operations.
87: <li> Write new <code>mpn_get_str</code> and <code>mpn_set_str</code> running in
88: the sub O(n^2) range, using some divide-and-conquer approach, preferably
89: without using division.
90: <li> Copy tricky code for converting a limb from development version of
91: <code>mpn_get_str</code> to mpf/get_str. (Talk to Torbjörn about this.)
92: <li> Consider inlining these functions: <code>mpz_size</code>,
93: <code>mpz_set_ui</code>, <code>mpz_set_q</code>, <code>mpz_clear</code>,
94: <code>mpz_init</code>, <code>mpz_get_ui</code>, <code>mpz_scan0</code>,
95: <code>mpz_scan1</code>, <code>mpz_getlimbn</code>,
96: <code>mpz_init_set_ui</code>, <code>mpz_perfect_square_p</code>,
97: <code>mpz_popcount</code>, <code>mpf_size</code>,
98: <code>mpf_get_prec</code>, <code>mpf_set_prec_raw</code>,
99: <code>mpf_set_ui</code>, <code>mpf_init</code>, <code>mpf_init2</code>,
100: <code>mpf_clear</code>, <code>mpf_set_si</code>.
101: <li> <code>mpz_powm</code> and <code>mpz_powm_ui</code> aren't very
102: fast on one or two limb moduli, due to a lot of function call
103: overheads. These could perhaps be handled as special cases.
104: <li> <code>mpz_powm</code> and <code>mpz_powm_ui</code> want better
105: algorithm selection, and the latter should use REDC. Both could
106: change to use an <code>mpn_powm</code> and <code>mpn_redc</code>.
107: <li> <code>mpn_gcd</code> might be able to be sped up on small to
108: moderate sizes by improving <code>find_a</code>, possibly just by
109: providing an alternate implementation for CPUs with slowish
110: <code>count_leading_zeros</code>.
111: <li> Implement a cache localized evaluate and interpolate for the
112: toom3 <code>USE_MORE_MPN</code> code. The necessary
113: right-to-left <code>mpn_divexact_by3c</code> exists.
114: <li> <code>mpn_mul_basecase</code> on NxM with big N but small M could try for
115: better cache locality by taking N piece by piece. The current code could
116: be left available for CPUs without caching. Depending how karatsuba etc
117: is applied to unequal size operands it might be possible to assume M is
118: always smallish.
119: </ul>
120:
121:
122: <h4>Machine Dependent Optimization</h4>
123: <ul>
124: <li> Run the `tune' utility for more compiler/CPU combinations. We would like
125: to have gmp-mparam.h files in practically every implementation specific
126: mpn subdirectory, and repeat each *_THRESHOLD for gcc and the system
127: compiler. See the `tune' top-level directory for more information.
128: <li> Alpha: Rewrite <code>mpn_addmul_1</code>, <code>mpn_submul_1</code>, and
129: <code>mpn_mul_1</code> for the 21264. On 21264, they should run at 4, 3,
130: and 3 cycles/limb respectively, if the code is unrolled properly. (Ask
131: Torbjörn for his xm.s and xam.s skeleton files.)
132: <li> Alpha: Rewrite <code>mpn_addmul_1</code>, <code>mpn_submul_1</code>, and
133: <code>mpn_mul_1</code> for the 21164. This should use both integer
134: multiplies and floating-point multiplies. For the floating-point
135: operations, the single-limb multiplier should be split into three 21-bit
136: chunks.
137: <li> UltraSPARC: Rewrite 64-bit <code>mpn_addmul_1</code>,
138: <code>mpn_submul_1</code>, and <code>mpn_mul_1</code>. Should use
139: floating-point operations, and split the invariant single-limb multiplier
140: into 21-bit chunks. Should give about 18 cycles/limb, but the pipeline
141: will become very deep. (Torbjörn has C code that is useful as a starting
142: point.)
143: <li> UltraSPARC: Rewrite <code>mpn_lshift</code> and <code>mpn_rshift</code>.
144: Should give 2 cycles/limb. (Torbjörn has code that just needs to be
145: finished.)
146: <li> SPARC32/V9: Find out why the speed of <code>mpn_addmul_1</code>
147: and the other multiplies varies so much on successive sizes.
148: <li> PA64: Improve <code>mpn_addmul_1</code>, <code>mpn_submul_1</code>, and
149: <code>mpn_mul_1</code>. The current development code runs at 11
150: cycles/limb, which is already very good. But it should be possible to
151: saturate the cache, which will happen at 7.5 cycles/limb.
152: <li> Sparc & SparcV8: Enable umul.asm for native cc. The generic
153: longlong.h umul_ppmm is suspected to be causing sqr_basecase to
154: be slower than mul_basecase.
155: <li> UltraSPARC: Write <code>umul_ppmm</code>. Important in particular for
156: <code>mpn_sqr_basecase</code>. Using four "<code>mulx</code>"s either
157: with an asm block or via the generic C code is about 90 cycles.
158: <li> Implement <code>mpn_mul_basecase</code> and <code>mpn_sqr_basecase</code>
159: for important machines. Helping the generic sqr_basecase.c with an
160: <code>mpn_sqr_diagonal</code> might be enough for some of the RISCs.
161: <li> POWER2/POWER2SC: Schedule <code>mpn_lshift</code>/<code>mpn_rshift</code>.
162: Will bring time from 1.75 to 1.25 cycles/limb.
163: <li> X86: Optimize non-MMX <code>mpn_lshift</code> for shifts by 1. (See Pentium code.)
164: <li> Alpha: Optimize <code>count_leading_zeros</code>.
165: <li> Alpha: Optimize <code>udiv_qrnnd</code>. (Ask Torbjörn for the file
166: test-udiv-preinv.c as a starting point.)
167: <li> R10000/R12000: Rewrite <code>mpn_add_n</code> and <code>mpn_sub_n</code>.
168: It should just require 3 cycles/limb, but the current code propagates
169: carry poorly. The trick is to add carry-in later than we do now,
170: decreasing the number of operations used to generate carry-out from 4 to
171: to 3.
172: <li> PPC32: Try using fewer registers in the current <code>mpn_lshift</code>.
173: The pipeline is now extremely deep, perhaps unnecessarily deep. Also, r5
174: is unused. (Ask Torbjörn for a copy of the current code.)
175: <li> PPC32: Write <code>mpn_rshift</code> based on new <code>mpn_lshift</code>.
176: <li> PPC32: Rewrite <code>mpn_add_n</code> and <code>mpn_sub_n</code>. Should
177: run at just 3.25 cycles/limb. (Ask for xxx-add_n.s as a starting point.)
178: <li> Fujitsu VPP: Vectorize main functions, perhaps in assembly language.
179: <li> Fujitsu VPP: Write <code>mpn_mul_basecase</code> and
180: <code>mpn_sqr_basecase</code>. This should use a "vertical multiplication
181: method", to avoid carry propagation. splitting one of the operands in
182: 11-bit chunks.
183: <li> Cray: Vectorize main functions, perhaps in assembly language.
184: <li> Cray: Write <code>mpn_mul_basecase</code> and
185: <code>mpn_sqr_basecase</code>. Same comment applies to this as to the
186: same functions for Fujitsu VPP.
187: <li> Improve <code>count_leading_zeros</code> for 64-bit machines:
188:
189: <pre>
190: if ((x >> W_TYPE_SIZE-W_TYPE_SIZE/2) == 0) { x <<= W_TYPE_SIZE/2; cnt += W_TYPE_SIZE/2}
191: if ((x >> W_TYPE_SIZE-W_TYPE_SIZE/4) == 0) { x <<= W_TYPE_SIZE/4; cnt += W_TYPE_SIZE/4}
192: ... </pre>
193:
194: </ul>
195:
196: <h4>New Functionality</h4>
197: <ul>
198: <li> <code>mpz_get_nth_ui</code>. Return the nth word (not necessarily the nth limb).
199: <li> Maybe add <code>mpz_crr</code> (Chinese Remainder Reconstruction).
200: <li> Let `0b' and `0B' mean binary input everywhere.
201: <li> Add <code>mpq_set_f</code> for assignment from <code>mpf_t</code>
202: (cf. <code>mpq_set_d</code>).
203: <li> Maybe make <code>mpz_init</code> (and <code>mpq_init</code>) do lazy
204: allocation. Set <code>ALLOC(var)</code> to 0, and have
205: <code>mpz_realloc</code> special-handle that case. Update functions that
206: rely on a single limb (like <code>mpz_set_ui</code>,
207: <code>mpz_[tfc]div_r_ui</code>, and others).
208: <li> Add <code>mpf_out_raw</code> and <code>mpf_inp_raw</code>. Make sure
209: format is portable between 32-bit and 64-bit machines, and between
210: little-endian and big-endian machines.
211: <li> Handle numeric exceptions: Call an error handler, and/or set
212: <code>gmp_errno</code>.
213: <li> Implement <code>gmp_fprintf</code>, <code>gmp_sprintf</code>, and
214: <code>gmp_snprintf</code>. Think about some sort of wrapper
215: around <code>printf</code> so it and its several variants don't
216: have to be completely reimplemented.
217: <li> Implement some <code>mpq</code> input and output functions.
218: <li> Implement a full precision <code>mpz_kronecker</code>, leave
219: <code>mpz_jacobi</code> for compatibility.
220: <li> Make the mpn logops and copys available in gmp.h. Since they can
221: be either library functions or inlines, gmp.h would need to be
222: generated from a gmp.in based on what's in the library. gmp.h
223: would still be compiler-independent though.
224: <li> Make versions of <code>mpz_set_str</code> etc taking string
225: lengths rather than null-terminators.
226: <li> Consider changing the thresholds to apply the simpler algorithm when
227: "<code><=</code>" rather than "<code><</code>", so a threshold can
228: be set to <code>MP_SIZE_T_MAX</code> to get only the simpler code (the
229: compiler will know <code>size <= MP_SIZE_T_MAX</code> is always true).
230: <li> <code>mpz_cdiv_q_2exp</code> and <code>mpz_cdiv_r_2exp</code>
231: could be implemented to match the corresponding tdiv and fdiv.
232: Maybe some code sharing is possible.
233: </ul>
234:
235:
236: <h4>Configuration</h4>
237:
238: <ul>
239: <li> Improve config.guess. We want to recognize the processor very
240: accurately, more accurately than other GNU packages.
241: config.guess does not currently make the distinctions we would
242: like it to do and a --target often needs to be set explicitly.
243:
244: For example, "sparc" is not very useful as a machine architecture
245: denotation. We want to distinguish old 32-bit SPARC without
246: multiply support from newer 32-bit SPARC with such support. We
247: want to recognize a SuperSPARC, since its implementation of the
248: UDIV instruction is not complete, and will trap to the OS kernel
249: for certain operands. And we want to recognize 64-bit capable
250: SPARC processors as such. While the assembly routines can use
251: 64-bit operations on all 64-bit SPARC processors, one can not use
252: 64-bit limbs under all operating system. E.g., Solaris 2.5 and
253: 2.6 doesn't preserve the upper 32 bits of most processor
254: registers. For SPARC we therefore sometimes need to choose GMP
255: configuration depending both on processor and operating system.
256:
257: <li> Remember to make sure config.sub accepts any output from config.guess.
258:
259: <li> Find out whether there's an alloca available and how to use it.
260: AC_FUNC_ALLOCA has various system dependencies covered, but we
261: don't want its alloca.c replacement. (One thing current cpp
262: tests don't cover: HPUX 10 C compiler supports alloca, but
263: cannot find any symbol to test in order to know if we're on
264: HPUX 10. Damn.)
265: <li> Identify Mips processor under Irix: `hinv -c processor'.
266: config.guess should say mips2, mips3, and mips4.
267: <li> Identify Alpha processor under OSF: "/usr/sbin/sizer -c".
268: Unfortunately, sizer is not available before some revision of
269: Dec Unix 4.0, and it also returns some rather cryptic names for
270: processors. Perhaps the <code>implver</code> and
271: <code>amask</code> assembly instructions are better, but that
272: doesn't differentiate between ev5 and ev56.
273: <li> Identify Sparc processors. config.guess should say supersparc,
274: microsparc, ultrasparc1, ultrasparc2, etc.
275: <li> Identify HPPA processors similarly.
276: <li> Get lots of information about a Solaris system: prtconf -vp
277: <li> For some target machines and some compilers, specific options
278: are needed (sparcv8/gcc needs -mv8, sparcv8/cc needs -cg92,
279: Irix64/cc needs -64, Irix32/cc might need -n32, etc). Some are
280: set already, add more, see configure.in.
281: <li> Options to be passed to the assembler (via the compiler, using
282: whatever syntax the compiler uses for passing options to the
283: assembler).
284: <li> On Solaris 7, check if gcc supports native v9 64-bit
285: arithmetic. If not compile using "cc -fast -xarch=v9".
286: (Problem: -fast requires that we link with -fast too, which
287: might not be very good. Pass "-xO4 -xtarget=native" instead?)
288: <li> Extend the "optional" compiler arguments to choose the first
289: that works from from a set, so when gcc gets athlon support it
290: can try -mcpu=athlon, -mcpu=pentiumpro, or -mcpu=i486,
291: whichever works.
292: <li> Detect gcc >=2.96 and enable -march=pentiumpro for relevant
293: x86s. (A bug in gcc 2.95.2 prevents it being used
294: unconditionally.)
295: <li> Build multiple variants of the library under certain systems.
296: An example is -n32, -o32, and -64 on Irix.
297: <li> There's a few filenames that don't fit in 14 chars, if this
298: matters.
299: <li> Enable support for FORTRAN versions of mpn files (eg. for
300: mpn/cray/mulww.f). Add "f" to the mpn path searching, run AC_PROG_F77 if
301: such a file is found. Automake will generate some of what's needed in the
302: makefiles, but libtool doesn't know fortran and so rules like the current
303: ".asm.lo" will be needed.
304: <li> Only run GMP_PROG_M4 if it's needed, ie. if there's .asm files
305: selected from the mpn path. This might help say a generic C
306: build on weird systems.
307: </ul>
308:
309: <p> In general, getting the exact right configuration, passing the
310: exact right options to the compiler, etc, might mean that the GMP
311: performance more than doubles.
312:
313: <p> When testing, make sure to test at least the following for all out
314: target machines: (1) Both gcc and cc (and c89). (2) Both 32-bit mode
315: and 64-bit mode (such as -n32 vs -64 under Irix). (3) Both the system
316: `make' and GNU `make'. (4) With and without GNU binutils.
317:
318:
319: <h4>Miscellaneous</h4>
320: <ul>
321:
322: <li> Work on the way we build the library. We now do it building
323: convenience libraries but then listing all the object files a
324: second time in the top level Makefile.am.
325: <li> Get rid of mp[zq]/sub.c, and instead define a compile parameter to
326: mp[zq]/add.c to decide whether it will add or subtract. Will decrease
327: redundancy. Similarly in other places.
328: <li> Make <code>mpz_div</code> and <code>mpz_divmod</code> use rounding
329: analogous to <code>mpz_mod</code>. Document, and list as an
330: incompatibility.
331: <li> Maybe make mpz_pow_ui.c more like mpz/ui_pow_ui.c, or write new
332: mpn/generic/pow_ui.
333: <li> Make mpz_invert call mpn_gcdext directly.
334: <li> Make a build option to enable execution profiling with gprof. In
335: particular look at getting the right <code>mcount</code> call at
336: the start of each assembler subroutine (for important targets at
337: least).
338: </ul>
339:
340:
341: <h4>Aids to Debugging</h4>
342: <ul>
343: <li> Make an option for stack-alloc.c to call <code>malloc</code>
344: separately for each <code>TMP_ALLOC</code> block, so a redzoning
345: malloc debugger could be used during development.
346: <li> Add <code>ASSERT</code>s at the start of each user-visible
347: mpz/mpq/mpf function to check the validity of each
348: <code>mp?_t</code> parameter, in particular to check they've been
349: <code>mp?_init</code>ed. This might catch elementary mistakes in
350: user programs. Care would need to be taken over
351: <code>MPZ_TMP_INIT</code>ed variables used internally.
352: </ul>
353:
354:
355: <h4>Documentation</h4>
356: <ul>
357: <li> Document conventions, like that <code> unsigned long int</code> is used for
358: bit counts/ranges, and that <code>mp_size_t</code> is used for limb counts.
359: <li> <code>mpz_inp_str</code> (etc) doesn't say when it stops reading digits.
360: </ul>
361:
362: <hr>
363:
364: <table width="100%">
365: <tr>
366: <td>
367: <font size=2>
368: Please send comments about this page to
369: <a href="mailto:tege@swox.com">tege@swox.com</a>.<br>
370: Copyright (C) 1999, 2000 Torbjörn Granlund.
371: </font>
372: </td>
373: <td align=right>
374: </td>
375: </tr>
376: </table>
377:
378: </body>
379: </html>
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to tasks.html CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / gmp / doc