polly/lib/External/isl/imath/tools/findthreshold.py

   1 #!/usr/bin/env python
   2 ##
   3 ## Name:     findthreshold.py
   4 ## Purpose:  Find a good threshold for recursive multiplication.
   5 ## Author:   M. J. Fromberger
   6 ##
   7 ## This tool computes some timing statistics to help you select a suitable
   8 ## recursive multiplication breakpoint.  It uses the imtimer tool to run a
   9 ## series of tests varying precision and breakpoint, and prints out a summary
  10 ## of the "best" values for each category.  Each summary line contains the
  11 ## following fields, tab-separated:
  12 ##
  13 ## prec     -- the precision of the operands (in digits).
  14 ## thresh   -- the threshold for recursive multiplication (digits).
  15 ## trec     -- total time using recursive algorithm (sec).
  16 ## tnorm    -- total time without recursive algorithm (sec).
  17 ## ratio    -- speedup (ratio of tnorm/trec).
  18 ##
  19 ## You are responsible for reading and interpreting the resulting table to
  20 ## obtain a useful value for your workload.  Change the default in imath.c, or
  21 ## call mp_int_multiply_threshold(n) during program initialization, to
  22 ## establish a satisfactory result.
  23 ##
  24 import math, os, random, sys, time
  25
  26
  27 def get_timing_stats(num_tests, precision, threshold, seed=None):
  28     """Obtain timing statistics for multiplication.
  29
  30     num_tests      -- number of tests to run.
  31     precision      -- number of digits per operand.
  32     threshold      -- threshold in digits for recursive multiply.
  33     seed           -- random seed; if None, the clock is used.
  34
  35     Returns a tuple of (seed, bits, time) where seed is the random seed used,
  36     bits is the number of bits per operand, and time is a float giving the
  37     total time taken for the test run.
  38     """
  39     if seed is None:
  40         seed = int(time.time())
  41
  42     line = os.popen(
  43         './imtimer -mn -p %d -t %d -s %d %d' % (precision, threshold, seed,
  44                                                 num_tests), 'r').readline()
  45
  46     count, prec, bits, thresh, status = line.strip().split('\t')
  47     kind, total, unit = status.split()
  48
  49     return seed, int(bits), float(total)
  50
  51
  52 def check_binary(name):
  53     if not os.path.exists(name):
  54         os.system('make %s' % name)
  55         if not os.path.exists(name):
  56             raise ValueError("Unable to build %s" % name)
  57     elif not os.path.isfile(name):
  58         raise ValueError("Path exists with wrong type")
  59
  60
  61 def compute_stats():
  62     check_binary('imtimer')
  63     seed = int(time.time())
  64
  65     print >> sys.stderr, "Computing timer statistics (this may take a while)"
  66     stats = {}
  67     for prec in (32, 40, 64, 80, 128, 150, 256, 384, 512, 600, 768, 1024):
  68         sys.stderr.write('%-4d ' % prec)
  69         stats[prec] = (None, 1000000., 0.)
  70
  71         for thresh in xrange(8, 65, 2):
  72             s, b, t = get_timing_stats(1000, prec, thresh, seed)
  73             sp, bp, tp = get_timing_stats(1000, prec, prec + 1, seed)
  74
  75             if t < stats[prec][1]:
  76                 stats[prec] = (thresh, t, tp)
  77                 sys.stderr.write('+')
  78             else:
  79                 sys.stderr.write('.')
  80         sys.stderr.write('\n')
  81
  82     return list((p, h, t, tp) for p, (h, t, tp) in stats.iteritems())
  83
  84
  85 if __name__ == "__main__":
  86     stats = compute_stats()
  87     stats.sort(key=lambda s: s[3] / s[2])
  88     for prec, thresh, trec, tnorm in stats:
  89         print "%d\t%d\t%.3f\t%.3f\t%.4f" % (prec, thresh, trec, tnorm,
  90                                             tnorm / trec)
  91
  92     print
  93
  94 # Here there be dragons