Thread View: sci.engr
2 messages
2 total messages
Started by Ron Graham
Thu, 21 Jan 1993 16:28
Help with CPU internal clock - the summary!
Author: Ron Graham
Date: Thu, 21 Jan 1993 16:28
Date: Thu, 21 Jan 1993 16:28
88 lines
4405 bytes
4405 bytes
Here is the original question: We have an application where we are trying to estimate the order of a certain algorithm (whether O(N), O(N^2), etc.) by running it a certain number of times for various values of N. We measure the CPU time used by the algorithm using the FORTRAN "SECNDS" command, executing it just before and just after the algorithm runs through its paces. What we are finding is that the CPU measure we get back varies wildly, even for large values of N (~250) and for large numbers of runs (~30). The questions are as follows: (1) Are there aspects of the SECNDS command we don't know about, such as o sensitivity to system functions (user load, time of day, etc.) o inherent uncertainty (2) Is there a more reliable way to estimate the order of the algorithm? As you have guessed, we're running in FORTRAN, we're on a shared system, and we're not taking advantage of parallel processing or any other advanced programming tool. And here is a summary of responses: ********************************************************************** From: curran@pegasus.hks.com (Bill Mills-Curran) The VMS documentation for SECNDS ($ HELP FORTRAN INTRINS SECNDS) shows that it is measuring wall clock time. Try the C function "clock". You can call it quite easily from FORTRAN. Note that it returns an integer which counts hundreths of a second used in the current program. ********************************************************************** From: mpaul@unlinfo.unl.edu (marxhausen paul) This is no help, but estimating CPU time usage is tough even on dedicated single-user computers like PCs and similar - much of the "benchmarking" that goes on in popular computer magazines points this out. Hardware issues such as memory and disk cacheing, drive access times, etc. all make it hard to get objective results. In the case of a multiuser computer, things are much worse in this regard. The system has no real way to eliminate the delays imposed by swapping your process in and out, and the hardware delays are almost completely unpre- dicatable since the machine is servicing so many other requests at once. ********************************************************************** From: kk881595@princeton (kevin knappmiller) Timing commands on multitasking systems are often tricky if you want actual execution times. What is the system you are using? I would guess that your command is just sampling the system clock giving real time not execution time. It has been my experience that you have to do something slightly different on almost every system. One good choice might be to use the UNIX "time" command, and stucture your code so that the entire (or nearly) call execution time was taken by the algorithm. That is if you are using a UNIX with "time". ********************************************************************** From: mwj%se17@se01.wg2.waii.com (Mike Johnson) To a feeble-minded codeslinger like myself, the best way to determine the order of an algorithm is by inspection. For example, I know that a bubble sort or insertion sort is O(N**2), because, in the worst case, N comparisons may be required to put each of the N data items in its place. I know that a quicksort is O(N*log N), because log N operations are required for each of the N data items. (By log N, I mean the base 2 logarithm of N.) ********************************************************************** Unfortunately, the algorithm is simply too much for us to estimate by inspection with the time we have at hand. We were forced to scrap it, do to the need for a quick turnaround on engineering time. But the insight on clock time and run time measurement really helped us reach that decision in a hurry. Thanks to all who responded. RG Who became an engineer thinking "free-body diagrams" might be interesting.
Re: Help with CPU internal clock - the summary!
Author: Seetamraju UdayaBhaskar Sarma
Date: Thu, 21 Jan 1993 21:43
Date: Thu, 21 Jan 1993 21:43
104 lines
5277 bytes
5277 bytes
If Ur running the program on Sun workstations or on System Variants, then use the following command time Fortran_Prog where the second word is to be replaced by the name of the fortran executable (that is Ur program). On a multi-user system (Why even a multi-tasking system like OS/2) U cannot expect to determine the total execution time the way U did... Seetamraju Udaya Bhaskar Sarma (email : seetam @ ece7 . eng . wayne . edu) In article 21JAN199311283372@ariel.lerc.nasa.gov, ecaxron@ariel.lerc.nasa.gov (Ron Graham) writes: -+>Here is the original question: -+> -+>We have an application where we are trying to estimate the order of -+>a certain algorithm (whether O(N), O(N^2), etc.) by running it a certain -+>number of times for various values of N. We measure the CPU time used -+>by the algorithm using the FORTRAN "SECNDS" command, executing it just -+>before and just after the algorithm runs through its paces. -+> -+>What we are finding is that the CPU measure we get back varies wildly, -+>even for large values of N (~250) and for large numbers of runs (~30). -+>The questions are as follows: -+> -+>(1) Are there aspects of the SECNDS command we don't know about, such as -+> -+> o sensitivity to system functions (user load, time of day, etc.) -+> o inherent uncertainty -+> -+>(2) Is there a more reliable way to estimate the order of the algorithm? -+> -+>As you have guessed, we're running in FORTRAN, we're on a shared system, -+>and we're not taking advantage of parallel processing or any other advanced -+>programming tool. -+> -+>And here is a summary of responses: -+> -+>********************************************************************** -+> -+>From: curran@pegasus.hks.com (Bill Mills-Curran) -+> -+>The VMS documentation for SECNDS ($ HELP FORTRAN INTRINS SECNDS) shows -+>that it is measuring wall clock time. Try the C function "clock". -+>You can call it quite easily from FORTRAN. Note that it returns an -+>integer which counts hundreths of a second used in the current -+>program. -+> -+>********************************************************************** -+> -+>From: mpaul@unlinfo.unl.edu (marxhausen paul) -+> -+>This is no help, but estimating CPU time usage is tough even on dedicated -+>single-user computers like PCs and similar - much of the "benchmarking" -+>that goes on in popular computer magazines points this out. Hardware -+>issues such as memory and disk cacheing, drive access times, etc. all -+>make it hard to get objective results. -+> -+>In the case of a multiuser computer, things are much worse in this regard. -+>The system has no real way to eliminate the delays imposed by swapping your -+>process in and out, and the hardware delays are almost completely unpre- -+>dicatable since the machine is servicing so many other requests at once. -+> -+>********************************************************************** -+> -+>From: kk881595@princeton (kevin knappmiller) -+> -+>Timing commands on multitasking systems are often tricky if you -+>want actual execution times. What is the system you are using? -+>I would guess that your command is just sampling the system clock -+>giving real time not execution time. -+> -+>It has been my experience that you have to do something slightly -+>different on almost every system. One good choice might be -+>to use the UNIX "time" command, and stucture your code so that -+>the entire (or nearly) call execution time was taken by the -+>algorithm. That is if you are using a UNIX with "time". -+> -+>********************************************************************** -+> -+>From: mwj%se17@se01.wg2.waii.com (Mike Johnson) -+> -+>To a feeble-minded codeslinger like myself, the best way to determine the -+>order of an algorithm is by inspection. For example, I know that a bubble -+>sort or insertion sort is O(N**2), because, in the worst case, N comparisons -+>may be required to put each of the N data items in its place. I know that -+>a quicksort is O(N*log N), because log N operations are required for each -+>of the N data items. (By log N, I mean the base 2 logarithm of N.) -+> -+>********************************************************************** -+> -+>Unfortunately, the algorithm is simply too much for us to estimate by -+>inspection with the time we have at hand. We were forced to scrap it, -+>do to the need for a quick turnaround on engineering time. -+> -+>But the insight on clock time and run time measurement really helped us -+>reach that decision in a hurry. Thanks to all who responded. -+> -+>RG -+> -+>Who became an engineer thinking "free-body diagrams" might be interesting.
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads