Toom selection

Torbjorn Granlund tg at
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 mailing list