CS 740, Fall 2007Homework Assignment 1Assigned: Thursday, September 13Due: Wednesday, September 26, 3:00PMThe purpose of this assignment is to develop techniques for measuring code performance, topractice reasoning about low-level code optimization, and to develop your own performanceanalysis tool using binary instrumentation.PolicyYou will work in groups of three people in solvi ng the problems for this assignment. (A groupof two may b e necessary depending on the class size—groups of one are definitely not allowed.)Turn in a single writeup per group, indicating all group members.LogisticsAny clarifications and revisions to the assignment will be posted on the “assignments” web pageon the c lass WWW directory.In the following, HOMEDIR refers to the directory:/afs/cs.cmu.edu/academic/class/15740-f07/publicand ASSTDIR refers to the subdirectory HOMEDIR/asst/asst1.Please hand in your assignment as a hard copy of formatted text.Using Interval TimersMeasuring performance is fundamental to the study of computer systems. When comparingmachines, or when optimizing code, it is often useful to measure the amount of time that ittakes (preferably at the resolution of processor clock cycles) to execute a particular operationor procedure. Some machines have special facilities to assist in measuring performance. Evenwithout such facilities, almost all machines provide interval timers—a relatively crude methodof computing elapsed times. In this assignment, you will investigate how to reason about andcontrol the accuracy of timing information that can be gathered using interval timers. One ofthe goals is to develop a function timer which accurately measures the execution time of anyfunction on any machine.The overall operation of an interval timer is illustrated in Figure 1. The system maintains a(user-settable) counter value which is updated periodically. That is, once every ∆ time units, thecounter is incremented by ∆. Using the Unix library routine getitimer, the user can poll thevalue of this counter. Thus, to measure the elapsed time of some operation Op, the user can pollthe counter to get a starting value Ts, perform the operation, and poll the counter to get a finalvalue Tf. The elapsed time for the operation can be approximated as Tobserved= Tf− Ts. As thefigure illustrates, however, the actual elapsed time Tactualmay differ from Tobservedsignificantly,1∆OPTactualTfTsTobserved= Tf- TsFigure 1: Time Measurement with an Interval Timerdue to the coarseness of the timer resolution. Since the value of ∆ is around 10 milliseconds formost systems, this er ror can be very significant.We have encapsulated the Unix interval timer routines for you in a handy timer package calledASSTDIR/etime.c. You should use this package for all measurements in the assignment. SeeASSTDIR/example.c for a simple example of how to use the package. One notable featureis that it converts the measurements to units of seconds, expressed as a C long double. Theprocedure for timing operation Op is then:init_etime();Ts = get_etime();Op;Tf = get_etime()T_observed = Tf - Ts;Problem 1: Bounded Measurement ErrorConsider a processor with a 500 MHz clock rate where precisely one addition operation can beperformed every clock cycle, and where the value of ∆ for the interval timer is 10 milliseconds.You would like to time a section of code (Op) consisting purely of a sequence of back-to-backadditions.If your code sequence consists of 106additions, what will the relative measurement error ofTobservedwith respect to Tactualbe? How about for 108additions? As always, show all of yourwork..Problem 2: Measuring ∆ for Your TimerWrite a C procedure that uses measurements to estimate (as accurately as possible) the value of∆ on any UNIX machine. Provide a listing of your code along with a brief description of yourscheme..We can improve the accuracy of the measurements by making sure that the activity we measurehas sufficient duration to overcome the imprecision of interval timers. That is, we can accuratelymeasure the time req uired by Op by executing it n times for a sufficiently large value of n:init_etime();2Ts = get_etime();for (i=0; i<n; i++) {Op;}Tf = get_etime()T_aggregate = Tf - Ts;T_average = T_aggregate/n;How do we choose a large enough value of n? The idea is that n must be large enough such thatTaggregateis larger than the minimum value (Tthreshold) which guarantees a relative measurementerror less than the desired upper bound of E. The value of Tthresholdcan b e computed based on∆ and E. However, since the elapsed time for Op is unknown, we cannot compute the minimumvalue of n ahead of time.One approach is to start with n = 1, and continue doubling it until the observed Taggregateislarge enough to guarantee sufficient accuracy (i.e. it is larger than Tthreshold).Problem 3: Implementing a Function TimerImplement a function timer in C that uses the doubling scheme outlined above to accuratelymeasure the running time of any function on any system. Your function timer should have thefollowing interfacetypdef void (*test_funct)(void);double func_time(test_funct P, double E);where P is the function to be timed and E is the maximum relative measurement error. Theseprototypes are already defined for you in ASSTDIR/functime.h. Implement your func time()function in a separate file c alled functime.c.Your function timer should: (1) determine the timer period ∆ using the scheme from the previousproblem; (2) calculate Tthresholdas a function of ∆ and E; and then (3) repeatedly double nuntil Taggregate≥ Tthreshold. It should work for any function on any system, regardless of therunning time of the function or the timer period of the system..Problem 4: Testing Your Function TimerTest your function timer using the program ASSTDIR/freq.c, which uses func_time() toestimate the clock frequency of your machine. This routine assumes that your machine executesan integer addition in one clock cycle. This is a safe assumption for most modern processors.Turn in the output string from freq.c and the type of system you ran it on..Problem 5: Alternative Timer AlgorithmsRecall that in Problem 3, you repeatedly doubled the value of n until it was sufficiently large(i.e. until Taggregate≥ Tthreshold). Now consider the following three algorithms for increasingthe value of n:Algorithm 1: Set n = 1 initially, and repeatedly multiply n by a factor of 2 until n is sufficientlylarge (i.e. the algor ithm used in Problem
View Full Document
Unlocking...