15 213 Time Measurement October 25 2001 Topics class18 ppt Time scales Interval counting Cycle counters K best measurement scheme Computer Time Scales Time Scale 1 Ghz Machine Microscopic Integer Add FP Multiply FP Divide Macroscopic Keystroke Interrupt Handler Disk Access Screen Refresh Keystroke 1 ns 1 s 1 ms 1s 1 E 09 1 E 06 1 E 03 1 E 00 Time seconds Two Fundamental Time Scales 10 9 seconds Processor External events 10 2 seconds Keyboard input Disk seek Screen refresh class18 ppt 2 Implication Can execute many instructions while waiting for external event to occur Can alternate among processes without anyone noticing CS 213 F 01 Measurement Challenge How Much Time Does Program X Require CPU time How many total seconds are used when executing X Measure used for most applications Small dependence on other system activities Actual Wall Time How many seconds elapse between the start and the completion of X Depends on system load I O times etc Confounding Factors How does time get measured Many processes share computing resources Transient effects when switching from one process to another Suddenly the effects of alternating among processes become noticeable class18 ppt 3 CS 213 F 01 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 cummulative user time class18 ppt 4 CS 213 F 01 Activity Periods Light Load Activity Periods Load 1 Active 1 Inactive 0 10 20 30 40 50 60 70 80 Time ms Most of the time spent executing one process Periodic interrupts every 10ms Interval timer Keep system from executing one process to exclusion of others class18 ppt 5 Other interrupts Due to I O activity Inactivity periods System time spent processing interrupts 250 000 clock cycles CS 213 F 01 Activity Periods Heavy Load Activity Periods Load 2 Active 1 Inactive 0 10 20 30 40 50 60 70 80 Time ms Sharing processor with one other active process Periodic interrupts every 10ms Interval timer Keep system from executing one process to exclusion of others class18 ppt 6 Other interrupts Due to I O activity Inactivity periods System time spent processing interrupts Periods when other process executes CS 213 F 01 Interval Counting OS Measures Runtimes Using Interval Timer Each time get timer interrupt increment timer for executing process User time if running in user mode System time if running in kernel mode a Interval Timings A B A B A A 110u 40s Au Au Au As Bu Bs Bu Bu Bu Bu As Au Au Au Au Au Bs Bu Bu Bs Au Au Au As As B b Actual Times A A B A B A 120 0u 33 3s B 73 3u 23 3s 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 class18 ppt 7 CS 213 F 01 70u 30s Unix time Command time make osevent gcc O2 Wall g march i486 gcc O2 Wall g march i486 gcc O2 Wall g march i486 gcc O2 Wall g march i486 0 820u 0 300s 0 01 32 84 8 c c c o clock c options c load c osevent osevent c 0 0k 0 0io 4049pf 0w 0 82 seconds user time 82 timer intervals 0 30 seconds system time 30 timer intervals 1 32 seconds wall time 84 8 of total was used running these processes 82 0 3 1 32 848 class18 ppt 8 CS 213 F 01 Accuracy of Interval Counting A Minimum Computed time 70ms A Maximum Min Actual 60 Max Actual 80 0 10 20 30 40 50 60 70 80 Worst Case Analysis Timer Interval Single process segment measurement can be off by No bound on error for multiple segments Could consistently underestimate or consistently overestimate Average Case Analysis Over underestimates tend to balance out As long as total run time is sufficiently large 1 second Consistently miss 4 overhead due to timer interrupts class18 ppt 9 CS 213 F 01 Cycle Counters Most modern systems have built in registers that are incremented every clock cycle Very fine grained Maintained as part of process state In Linux counts elapsed global time 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 2 32 550 106 7 8 seconds High order 64 bits wrap around every 264 550 106 33539534679 seconds 1065 3 years class18 ppt 10 CS 213 F 01 Measuring with Cycle Counter Idea Get current value of cycle counter store as pair of unsigned s cyc hi and cyc lo Compute something Get new value of cycle counter Perform double precision subtraction to get elapsed cycles Keep track of most recent reading of cycle counter static unsigned cyc hi 0 static unsigned cyc lo 0 void start counter Get current value of cycle counter access counter cyc hi cyc lo class18 ppt 11 CS 213 F 01 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 Emit assembly with rdtsc and two movl instructions Code generates two outputs Symbolic register 0 should be used for hi Symbolic register 1 should be used for lo Code has no inputs Registers eax and edx will be overwritten void access counter unsigned hi unsigned lo Get cycle counter asm rdtsc movl edx 0 movl eax 1 r hi r lo No input edx eax class18 ppt 12 CS 213 F 01 Completing Measurement Get new value of cycle counter Perform double precision subtraction to get elapsed cycles Express as double to avoid overflow problems double get counter unsigned ncyc hi ncyc lo unsigned hi lo borrow Get cycle counter access counter ncyc hi ncyc lo Do double precision subtraction lo ncyc lo cyc lo borrow lo ncyc lo hi ncyc hi cyc hi borrow return double hi 1 30 4 lo class18 ppt 14 CS 213 F 01 Timing With Cycle Counter Determine Clock Rate of Processor Count number of cycles required for some fixed number of seconds double MHZ int sleep time 10 start counter sleep sleep time MHZ get counter sleep time 1e6 Time Function P First attempt Simply count cycles for one execution of P double tsecs start counter P tsecs get counter MHZ 1e6 class18 ppt 15 CS 213 F 01 Timi ng with Cyc double MHZ int sleep time 10 le start counter sleep sleep time Cou 1e6 MHZ get counter sleep time nter double tsecs start counter P tsecs get counter MHZ 1e6 class18 ppt 16 CS 213 F 01 Overhead Measurement Pitfalls Calling get counter incurs small amount of overhead Want to measure long enough code sequence to
View Full Document
Unlocking...