95 lines · python
1#!/usr/bin/env python2##3## Name: findthreshold.py4## Purpose: Find a good threshold for recursive multiplication.5## Author: M. J. Fromberger6##7## This tool computes some timing statistics to help you select a suitable8## recursive multiplication breakpoint. It uses the imtimer tool to run a9## series of tests varying precision and breakpoint, and prints out a summary10## of the "best" values for each category. Each summary line contains the11## 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 to20## obtain a useful value for your workload. Change the default in imath.c, or21## call mp_int_multiply_threshold(n) during program initialization, to22## establish a satisfactory result.23##24import math, os, random, sys, time25 26 27def 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 the37 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 52def 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 61def 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 85if __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 print93 94# Here there be dragons95