1 files changed, 89 insertions, 0 deletions
diff --git a/polly/lib/External/isl/imath/findthreshold.py b/polly/lib/External/isl/imath/findthreshold.py
new file mode 100755
index 00000000000..daf3de6580b
--- /dev/null
+++ b/polly/lib/External/isl/imath/findthreshold.py
@@ -0,0 +1,89 @@
+#!/usr/bin/env python
+##
+## Name:     findthreshold.py
+## Purpose:  Find a good threshold for recursive multiplication.
+## Author:   M. J. Fromberger <http://spinning-yarns.org/michael/>
+## Info:     $Id: findthreshold.py 456 2006-08-16 14:24:06Z sting $
+##
+## This tool computes some timing statistics to help you select a suitable
+## recursive multiplication breakpoint.  It uses the imtimer tool to run a
+## series of tests varying precision and breakpoint, and prints out a summary
+## of the "best" values for each category.  Each summary line contains the
+## following fields, tab-separated:
+##
+## prec     -- the precision of the operands (in digits).
+## thresh   -- the threshold for recursive multiplication (digits).
+## trec     -- total time using recursive algorithm (sec).
+## tnorm    -- total time without recursive algorithm (sec).
+## ratio    -- speedup (ratio of tnorm/trec).
+##
+## You are responsible for reading and interpreting the resulting table to
+## obtain a useful value for your workload.  Change the value of MP_MULT_THRESH
+## in imath.h once you have a satisfactory result.
+##
+import math, os, random, sys, time
+
+def get_timing_stats(num_tests, precision, threshold, seed = None):
+    """Obtain timing statistics for multiplication.
+
+    num_tests      -- number of tests to run.
+    precision      -- number of digits per operand.
+    threshold      -- threshold in digits for recursive multiply.
+    seed           -- random seed; if None, the clock is used.
+
+    Returns a tuple of (seed, bits, time) where seed is the random seed used,
+    bits is the number of bits per operand, and time is a float giving the
+    total time taken for the test run.
+    """
+    if seed is None:
+        seed = int(time.time())
+    
+    line = os.popen('./imtimer -mn -p %d -t %d -s %d %d' %
+                    (precision, threshold, seed, num_tests), 'r').readline()
+    
+    count, prec, bits, thresh, status = line.strip().split('\t')
+    kind, total, unit = status.split()
+
+    return seed, int(bits), float(total)
+
+def check_binary(name):
+    if not os.path.exists(name):
+        os.system('make %s' % name)
+        if not os.path.exists(name):
+            raise ValueError("Unable to build %s" % name)
+    elif not os.path.isfile(name):
+        raise ValueError("Path exists with wrong type")
+
+def compute_stats():
+    check_binary('imtimer')
+    seed = int(time.time())
+
+    print >> sys.stderr, "Computing timer statistics (this may take a while)"
+    stats = {}
+    for prec in (32, 40, 64, 80, 128, 150, 256, 384, 512, 600, 768, 1024):
+        sys.stderr.write('%-4d ' % prec)
+        stats[prec] = (None, 1000000., 0.)
+    
+        for thresh in xrange(16, 65, 2):
+            s, b, t = get_timing_stats(1000, prec, thresh, seed)
+            sp, bp, tp = get_timing_stats(1000, prec, prec + 1, seed)
+            
+            if t < stats[prec][1]:
+                stats[prec] = (thresh, t, tp)
+                sys.stderr.write('+')
+            else:
+                sys.stderr.write('.')
+        sys.stderr.write('\n')
+
+    return list((p, h, t, tp) for p, (h, t, tp) in stats.iteritems())
+
+if __name__ == "__main__":
+    stats = compute_stats()
+    stats.sort(key = lambda s: s[3]/s[2])
+    for prec, thresh, trec, tnorm in stats:
+        print "%d\t%d\t%.3f\t%.3f\t%.4f" % (prec, thresh, trec, tnorm,
+                                            tnorm / trec)
+
+    print
+
+# Here there be dragons