home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / engr / 2515 < prev    next >
Encoding:
Text File  |  1993-01-21  |  4.2 KB  |  101 lines
  1. Newsgroups: sci.engr
  2. Path: sparky!uunet!think.com!ames!data.nas.nasa.gov!eagle!ariel.lerc.nasa.gov!ecaxron
  3. From: ecaxron@ariel.lerc.nasa.gov (Ron Graham)
  4. Subject: Help with CPU internal clock - the summary!
  5. Message-ID: <21JAN199311283372@ariel.lerc.nasa.gov>
  6. News-Software: VAX/VMS VNEWS 1.41    
  7. Sender: news@eagle.lerc.nasa.gov
  8. Nntp-Posting-Host: ariel.lerc.nasa.gov
  9. Organization: NASA Lewis Research Center
  10. Date: 21 Jan 1993 11:28 EST  
  11. Lines: 88
  12.  
  13. Here is the original question:
  14.  
  15. We have an application where we are trying to estimate the order of
  16. a certain algorithm (whether O(N), O(N^2), etc.) by running it a certain
  17. number of times for various values of N.  We measure the CPU time used
  18. by the algorithm using the FORTRAN "SECNDS" command, executing it just 
  19. before and just after the algorithm runs through its paces.
  20.  
  21. What we are finding is that the CPU measure we get back varies wildly,
  22. even for large values of N (~250) and for large numbers of runs (~30).
  23. The questions are as follows:
  24.  
  25. (1) Are there aspects of the SECNDS command we don't know about, such as
  26.  
  27.     o  sensitivity to system functions (user load, time of day, etc.)
  28.     o  inherent uncertainty
  29.  
  30. (2) Is there a more reliable way to estimate the order of the algorithm?
  31.  
  32. As you have guessed, we're running in FORTRAN, we're on a shared system,
  33. and we're not taking advantage of parallel processing or any other advanced
  34. programming tool.
  35.  
  36. And here is a summary of responses:
  37.  
  38. **********************************************************************
  39.  
  40. From:    curran@pegasus.hks.com (Bill Mills-Curran)
  41.  
  42. The VMS documentation for SECNDS ($ HELP FORTRAN INTRINS SECNDS) shows
  43. that it is measuring wall clock time.  Try the C function "clock".
  44. You can call it quite easily from FORTRAN.  Note that it returns an
  45. integer which counts hundreths of a second used in the current
  46. program.
  47.  
  48. **********************************************************************
  49.  
  50. From: mpaul@unlinfo.unl.edu (marxhausen paul)
  51.  
  52. This is no help, but estimating CPU time usage is tough even on dedicated
  53. single-user computers like PCs and similar - much of the "benchmarking"
  54. that goes on in popular computer magazines points this out. Hardware 
  55. issues such as memory and disk cacheing, drive access times, etc. all 
  56. make it hard to get objective results.
  57.  
  58. In the case of a multiuser computer, things are much worse in this regard.
  59. The system has no real way to eliminate the delays imposed by swapping your
  60. process in and out, and the hardware delays are almost completely unpre-
  61. dicatable since the machine is servicing so many other requests at once.
  62.  
  63. **********************************************************************
  64.  
  65. From: kk881595@princeton (kevin knappmiller)
  66.  
  67. Timing commands on multitasking systems are often tricky if you
  68. want actual execution times.  What is the system you are using?
  69. I would guess that your command is just sampling the system clock
  70. giving real time not execution time.
  71.  
  72. It has been my experience that you have to do something slightly 
  73. different on almost every system.  One good choice might be
  74. to use the UNIX "time" command, and stucture your code so that
  75. the entire (or nearly) call execution time was taken by the
  76. algorithm.  That is if you are using a UNIX with "time".
  77.  
  78. **********************************************************************
  79.  
  80. From: mwj%se17@se01.wg2.waii.com (Mike Johnson)
  81.  
  82. To a feeble-minded codeslinger like myself, the best way to determine the 
  83. order of an algorithm is by inspection. For example, I know that a bubble 
  84. sort or insertion sort is O(N**2), because, in the worst case, N comparisons 
  85. may be required to put each of the N data items in its place. I know that 
  86. a quicksort is O(N*log N), because log N operations are required for each 
  87. of the N data items.  (By log N, I mean the base 2 logarithm of N.) 
  88.  
  89. **********************************************************************
  90.  
  91. Unfortunately, the algorithm is simply too much for us to estimate by
  92. inspection with the time we have at hand.  We were forced to scrap it,
  93. do to the need for a quick turnaround on engineering time.
  94.  
  95. But the insight on clock time and run time measurement really helped us
  96. reach that decision in a hurry.  Thanks to all who responded.
  97.  
  98. RG
  99.  
  100. Who became an engineer thinking "free-body diagrams" might be interesting.
  101.