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## 24import math, os, random, sys, time 25 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 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 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 print 93 94# Here there be dragons 95