CS 740 Fall 2007 Homework Assignment 1 Assigned Thursday September 13 Due Wednesday September 26 3 00PM The purpose of this assignment is to develop techniques for measuring code performance to practice reasoning about low level code optimization and to develop your own performance analysis tool using binary instrumentation Policy You will work in groups of three people in solving the problems for this assignment A group of two may be necessary depending on the class size groups of one are definitely not allowed Turn in a single writeup per group indicating all group members Logistics Any clarifications and revisions to the assignment will be posted on the assignments web page on the class WWW directory In the following HOMEDIR refers to the directory afs cs cmu edu academic class 15740 f07 public and ASSTDIR refers to the subdirectory HOMEDIR asst asst1 Please hand in your assignment as a hard copy of formatted text Using Interval Timers Measuring performance is fundamental to the study of computer systems When comparing machines or when optimizing code it is often useful to measure the amount of time that it takes preferably at the resolution of processor clock cycles to execute a particular operation or procedure Some machines have special facilities to assist in measuring performance Even without such facilities almost all machines provide interval timers a relatively crude method of computing elapsed times In this assignment you will investigate how to reason about and control the accuracy of timing information that can be gathered using interval timers One of the goals is to develop a function timer which accurately measures the execution time of any function 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 the counter is incremented by Using the Unix library routine getitimer the user can poll the value of this counter Thus to measure the elapsed time of some operation Op the user can poll the counter to get a starting value Ts perform the operation and poll the counter to get a final value Tf The elapsed time for the operation can be approximated as Tobserved Tf Ts As the figure illustrates however the actual elapsed time Tactual may differ from Tobserved significantly 1 Tactual OP Ts Tf Tobserved Tf Ts Figure 1 Time Measurement with an Interval Timer due to the coarseness of the timer resolution Since the value of is around 10 milliseconds for most systems this error can be very significant We have encapsulated the Unix interval timer routines for you in a handy timer package called ASSTDIR etime c You should use this package for all measurements in the assignment See ASSTDIR example c for a simple example of how to use the package One notable feature is that it converts the measurements to units of seconds expressed as a C long double The procedure for timing operation Op is then init etime Ts get etime Op Tf get etime T observed Tf Ts Problem 1 Bounded Measurement Error Consider a processor with a 500 MHz clock rate where precisely one addition operation can be performed 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 back additions If your code sequence consists of 106 additions what will the relative measurement error of Tobserved with respect to Tactual be How about for 108 additions As always show all of your work Problem 2 Measuring for Your Timer Write 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 your scheme We can improve the accuracy of the measurements by making sure that the activity we measure has sufficient duration to overcome the imprecision of interval timers That is we can accurately measure the time required by Op by executing it n times for a sufficiently large value of n init etime 2 Ts 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 that Taggregate is larger than the minimum value Tthreshold which guarantees a relative measurement error less than the desired upper bound of E The value of Tthreshold can be computed based on and E However since the elapsed time for Op is unknown we cannot compute the minimum value of n ahead of time One approach is to start with n 1 and continue doubling it until the observed Taggregate is large enough to guarantee sufficient accuracy i e it is larger than Tthreshold Problem 3 Implementing a Function Timer Implement a function timer in C that uses the doubling scheme outlined above to accurately measure the running time of any function on any system Your function timer should have the following interface typdef 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 These prototypes are already defined for you in ASSTDIR func time h Implement your func time function in a separate file called func time c Your function timer should 1 determine the timer period using the scheme from the previous problem 2 calculate Tthreshold as a function of and E and then 3 repeatedly double n until Taggregate Tthreshold It should work for any function on any system regardless of the running time of the function or the timer period of the system Problem 4 Testing Your Function Timer Test your function timer using the program ASSTDIR freq c which uses func time to estimate the clock frequency of your machine This routine assumes that your machine executes an 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 Algorithms Recall 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 increasing the value of n Algorithm 1 Set n 1 initially and repeatedly multiply n by a factor of 2 until n is sufficiently large i e the algorithm used in Problem 3 3 Algorithm 2 Set n 1 initially and repeatedly multiply n by a factor of 10 until n is sufficiently large Algorithm 3 Set n 1 initially and repeatedly
View Full Document
Unlocking...