15 213 Performance Evaluation May 2 2000 Topics Getting accurate measurements Amdahl s Law class29 ppt Time on a Computer System real wall clock time user time time executing instructing instructions in the user process system time time executing instructing instructions in kernel on behalf of user process some other user s time time executing instructing instructions in different user s process real wall clock time We will use the word time to refer to user time class29 ppt 2 CS 213 S 00 Time of Day Clock return elapsed time since some reference time e g Jan 1 1970 example Unix gettimeofday command coarse grained e g 3 sec resolution on Linux 10 msec resolution on Windows NT Lots of overhead making call to OS Different underlying implementations give different resolutions include sys time h include unistd h struct timeval tstart tfinish double tsecs gettimeofday tstart NULL P gettimeofday tfinish NULL tsecs tfinish tv sec tstart tv sec 1e6 tfinish tv usec tstart tv usec class29 ppt 3 CS 213 S 00 Interval Count Down Timers set timer to some initial value timer counts down toward zero coarse grained e g 10 msec resolution on Linux void init etime first it value tv sec 86400 setitimer ITIMER VIRTUAL first NULL Using the interval timer class29 ppt double get etime struct itimerval curr getitimer ITIMER VIRTUAL curr return double first it value tv sec curr it value tv sec first it value tv usec curr it value tv usec 1e 6 init etime secs get etime P secs get etime secs printf lf secs n secs 4 CS 213 S 00 Cycle Counters Most modern systems have built in registers that are incremented every clock cycle Very fine grained Maintained as part of process state Save restore with context switches Counter will reflect time spent by user process Special assembly code instruction to access On recent model Intel machines 64 bit counter RDTSC instruction sets edx to high order 32 bits eax to low order 32 bits Wrap Around Times for 550 MHz machine Low order 32 bits wrap around every 232 550 106 7 8 seconds High order 64 bits wrap around every 264 550 106 33539534679 seconds 1065 3 years class29 ppt 5 CS 213 S 00 Using the Cycle Counter Example Function that returns number of cycles elapsed since previous call to function Express as double to avoid overflow problems Keep track of most recent reading of cycle counter static unsigned cyc hi 0 static unsigned cyc lo 0 static double delta cycles unsigned ncyc hi ncyc lo double result Get cycle counter as ncyc hi and ncyc lo Do double precision subtraction cyc hi ncyc hi cyc lo ncyc lo return result class29 ppt 6 CS 213 S 00 Accessing the Cycle Counter cont GCC allows inline assembly code with mechanism for matching registers with program variables Code only works on x86 machine compiling with GCC unsigned ncyc hi ncyc lo Get cycle counter asm rdtsc nmovl edx 0 nmovl eax 1 r ncyc hi r ncyc lo No input edx eax Emit assembly with rdtsc and two movl instructions Code generates two outputs Symbolic register 0 should be used for ncyc hi Symbolic register 1 should be used for ncyc lo Code has no inputs Registers eax and edx will be overwritten class29 ppt 7 CS 213 S 00 Accessing the Cycle Counter cont Emitted Assembly Code delta cycles pushl ebp movl esp ebp pushl esi pushl ebx APP rdtsc movl edx esi movl eax ecx NO APP movl ecx ebx subl cyc lo ebx cmpl ecx ebx seta al xorl edx edx movb al dl movl esi eax class29 ppt Stack stuff Result of ASM Statement Uses esi for ncyc hi Uses ecx for ncyc lo ncyc lo ncyc hi 8 CS 213 S 00 Using the Cycle Counter cont Keep track of most recent reading of cycle counter static unsigned cyc hi 0 static unsigned cyc lo 0 static double delta cycles unsigned ncyc hi ncyc lo unsigned hi lo borrow double result Do double precision subtraction lo ncyc lo cyc lo borrow lo ncyc lo hi ncyc hi cyc hi borrow result double hi 1 30 4 lo class29 ppt 9 CS 213 S 00 Timing with Cycle Counter double tsecs delta cycles P tsecs delta cycles MHZ 1e6 class29 ppt 10 CS 213 S 00 Measurement Pitfalls Overhead Calling delta cycles incurs small amount of overhead Want to measure long enough code sequence to compensate Unexpected Cache Effects artificial hits or misses e g these measurements were taken with the Alpha cycle counter foo1 array1 array2 array3 68 829 cycles foo2 array1 array2 array3 23 337 cycles vs foo2 array1 array2 array3 70 513 cycles foo1 array1 array2 array3 23 203 cycles class29 ppt 11 CS 213 S 00 Dealing with Overhead Cache Effects Keep doubling number of times execute P until reach some threshold Used CMIN 50000 int cnt 1 double cmeas 0 double cycles do int c cnt P Warm up cache void delta cycles while c 0 P cmeas delta cycles cycles cmeas cnt cnt cnt while cmeas CMIN Make sure have enough return cycles 1e6 MHZ class29 ppt 12 CS 213 S 00 Context Switching Context switches can also affect cache performance e g foo1 foo2 cycles on an unloaded timing server 71 002 23 617 67 968 23 384 68 840 23 365 68 571 23 492 69 911 23 692 Why Do Context Switches Matter Cycle counter only accumulates when running user process Some amount of overhead Caches polluted by OS and other user s code data Cold misses as restart process Measurement Strategy Try to measure uninterrupted code execution class29 ppt 13 CS 213 S 00 Detecting Context Switches Clock Interrupts Processor clock causes interrupt every t seconds Typically t 10 ms Same as interval timer resolution t Measurement takes place without interval timer advancing time Can detect by seeing if interval timer has advanced during measurement start get etime Perform Measurement if get etime start 0 Discard measurement class29 ppt 14 CS 213 S 00 Detecting Context Switches Cont External Interrupts E g due to completion of disk operation Occur at unpredictable times but generally take a long time to service Detecting See if real time clock has advanced Using coarse grained interval timer start get rtime Perform Measurement if get rtime start 0 Discard measurement Reliability Good but not 100 Can t get clean measurements on heavily loaded system class29 ppt 15 CS 213 S 00 Improving Accuracy Current Timer Code Assume that bad measurements always overestimate time True if main problem is due to context switches Take multiple samples 2 10 until lowest two are within some small tolerance of each other Better Timing Code Erroneous measurements both under and over estimate time but are not correlated to each other Look for clustering of times among samples class29 ppt 16 CS 213 S 00 Measurement Summary It s
View Full Document
Unlocking...