Copyright 2005 Intel Corporation All Rights Reserved Intel Threading Tools Paul Petersen Intel 1 Copyright 2005 Intel Corporation All Rights Reserved INFORMATION IN THIS DOCUMENT IS PROVIDED IN CONNECTION WITH INTEL PRODUCTS EXCEPT AS PROVIDED IN INTEL S TERMS AND CONDITIONS OF SALE FOR SUCH PRODUCTS INTEL ASSUMES NO LIABILITY WHATSOEVER AND INTEL DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY RELATING TO SALE AND OR USE OF INTEL PRODUCTS INCLUDING LIABILITY OR WARRANTIES RELATING TO FITNESS FOR A PARTICULAR PURPOSE MERCHANTABILITY OR INFRINGEMENT OF ANY PATENT COPYRIGHT OR OTHER INTELLECTUAL PROPERTY RIGHT Intel may make changes to specifications product descriptions and plans at any time without notice All dates provided are subject to change without notice Other names and brands may be claimed as the property of others Copyright 2005 Intel Corporation 2 Copyright 2005 Intel Corporation All Rights Reserved Threading You lock too much You don t lock enough The program crashes You try to debug the program Debugging a threaded program has a lot in common with medieval torture methods IMHO random quote found via GOOGLE search 3 Copyright 2005 Intel Corporation All Rights Reserved Example Prime Number Generation 2 3 5 7 9 11 13 15 17 include stdio h const long N 18 long primes N number of primes 0 main printf Determining primes from 1 d n N primes number of primes 2 special case for long number 3 number N number 2 long factor 3 while number factor factor 2 if factor number primes number of primes number printf Found d primes n number of primes 3 3 5 3 5 7 3 3 5 7 9 11 3 5 7 9 11 13 3 3 5 7 9 11 13 15 17 4 Copyright 2005 Intel Corporation All Rights Reserved Example Prime Number Kernel 2 3 5 7 9 11 13 15 17 for for long longnumber number 3 3 number number N N number number 22 long longfactor factor 3 3 while while number number factor factor factor factor 2 2 ifif factor number factor number primes primes number of primes number of primes number number 3 3 5 3 5 7 3 3 5 7 9 11 3 5 7 9 11 13 3 3 5 7 9 11 13 15 17 5 Copyright 2005 Intel Corporation All Rights Reserved Example Not Quite Right include include stdio h stdio h const const long long NN 100000 100000 long long primes N primes N number of primes number of primes 0 0 main main printf printf Determining Determining primes primes from from 1 d 1 d n n NN primes primes number of primes number of primes 2 2 special special case case pragma pragma omp omp parallel parallel for for for for long long number number 3 3 number number N N number number 22 long long factor factor 3 3 while while number number factor factor factor factor 2 2 if if factor factor number number primes primes number of primes number of primes number number printf printf Found Found d d primes n primes n number of primes number of primes 6 Copyright 2005 Intel Corporation All Rights Reserved Intel Threading Tools Intel Thread Checker Pinpoint notorious threading bugs like data races stalls and deadlocks http www intel com software products threading tcwin Intel Thread Profiler Visualize your threads over time Identify synchronization objects that cause delays http www intel com software products threading tp 7 Copyright 2005 Intel Corporation All Rights Reserved Data Flows VTune Performance Analyzer Intel Thread Checker Primes exe Binary Instrumentation Runtime Data Collector Primes exe Instrumented DLLs Instrumented threadchecker thr results Win32 threads POSIX threads OpenMP 8 Third party marks and brands are the property of their respective owners Copyright 2005 Intel Corporation All Rights Reserved Intel Thread Checker 9 Copyright 2005 Intel Corporation All Rights Reserved Example A Bit Better include include stdio h stdio h const const long long NN 100000 100000 long long primes N primes N number of primes number of primes 0 0 main main printf printf Determining Determining primes primes from from 1 d 1 d n n NN primes primes number of primes number of primes 2 2 special special case case pragma pragma omp omp parallel parallel for for for for long long number number 3 3 number number N N number number 22 long long factor factor 3 3 while number while number factor factor factor factor 2 2 if if factor factor number number pragma pragma omp omp critical critical primes primes number of primes number of primes number number printf printf Found Found d d primes n primes n number of primes number of primes 10 Copyright 2005 Intel Corporation All Rights Reserved Fundamental Concepts Thread Synchronization Instruction Segment Precedence Relation between Segments Parallel Segments Vector Clock of a Segment Data Race 11 Copyright 2005 Intel Corporation All Rights Reserved Definitions Thread An Independent Sequence of Instructions Sync Instruction Creates a thread Destroys a thread Posts information about host thread Brings information posted by another thread to host thread Segments Parts of a thread separated by sync instructions 12 Copyright 2005 Intel Corporation All Rights Reserved Precedence Relation between Segments T1 Partial Order S 21 S31 S32 T3 S 31 S 11 S11 S12 S13 S21 S22 S23 T2 S 12 S 22 S 32 S 13 S 23 S21 S12 S23 S11 S23 13 Copyright 2005 Intel Corporation All Rights Reserved Parallel Segments Two segments S and S are parallel if S S and S S are both false Examples S11 and S21 S11 and S22 S11 and S32 S22 and S31 T1 T2 S21 T3 S31 S11 S12 S22 S32 S13 S23 14 Copyright 2005 Intel Corporation All Rights Reserved Vector Clock of a Segment Vector clocks represent numerically the precedence relation between segments Vector Clock VS of a segment S is a function on threads with values in 0 1 2 Take a segment S on a thread T Take a thread T known to S Then VS T is one more than the number of segments S on T such that S S Vector clock of a segment is computed from the vector clocks of its immediate predecessors 15 Copyright 2005 Intel Corporation All Rights Reserved Conditions in Terms of Vector Clocks T1 Let S denote a segment on a thread T and S a segment on a thread T S S iff VS T VS T T2 0 1 0 T3 0 0 1 1 0 0 2 2 0 0 2 0 0 0 2 S and S are parallel iff VS T VS T VS T VS T 3 2 0 3 3 0 3 4 3 16 Copyright 2005 Intel Corporation All Rights Reserved Data Race There is a data race between two segments S and S if The segments are parallel There is a location x in shared memory that both segments access and at least one of the accesses is a write 17 Copyright 2005 Intel Corporation All Rights Reserved Data Race Detection Basic Result x A location in shared memory S A