tg at gmplib.org
Tue Dec 22 14:51:41 CET 2009
Did you see how the new TOOMAB_TO_TOOMCD thresholds are determined?
The idea is to measure along a line which the middle of the ideal lines
for toomAB and toomCD. The ideal line is the line where the
multiplicaiton for the evaluation at oo is balanced.
For TOOM43_TO_TOOM63 the ideal lines coincide, of course.
The code in mul.c is still a big comnpromise. I added the
TOOMAB_TO_TOOMCD to avoid some slowdown areas compared to the previous
mul.c, and I added that late during the rewrite.
The TOOMAB_TO_TOOMCD parameters should be considered as a limit on n.
(This might be changed by letting it be a limit on product size, m+n.)
We also need limits on "unbalancness", m/n. This is given naturally by
averaging ideal lines.
How should an ideal mul.c look?
* Measure all relevant TOOMAB_TO_TOOMCD.
* Identify primitive areas m,n qualitatively. (Such as areas for
mul_basecase, an area for toom22, an area for toom32.)
* When presented with (m,n), identify areas starting with the ones where
the fastest operation is expected for the area's smallest operands.
For example, mul_basecase's smallest operands are surely (1,1). Start
checking if (m,n) is in mul_basecase's area, using THRESHOLDs.
Next, check if it is in toom22's area. Then toom32's area.
More information about the gmp-devel