| 1 | Key concept is one of independence of code executed in "omp parallel" scopes
|
|---|
| 2 | - a block of (non-pragma enclosed code) can be independent if
|
|---|
| 3 | it references only private or per-thread data
|
|---|
| 4 | - "for" can be independent if loop is dependence-free
|
|---|
| 5 | - "sections" is independent if the contained sections are
|
|---|
| 6 | mutually independent
|
|---|
| 7 | - "single", "master", "critical" are independent by definition
|
|---|
| 8 | - "barrier" divides code before and after into portions whose
|
|---|
| 9 | independence can be reasoned about separately
|
|---|
| 10 | -> "parallel" is independent if ALL subconstructs are independent
|
|---|
| 11 |
|
|---|
| 12 | Strategies for computing independence
|
|---|
| 13 | - overapproximate dependence - if there is none then its independent
|
|---|
| 14 | - precise dependence tracking, e.g., symbolic execution
|
|---|
| 15 | - note that this really should be demand-driven and targetted at
|
|---|
| 16 | shared data
|
|---|
| 17 |
|
|---|
| 18 | Systematic analysis of constructs
|
|---|
| 19 | - "omp for"
|
|---|
| 20 | - sync -> breaks regions into before and after
|
|---|
| 21 | - "omp for nowait"
|
|---|
| 22 | - "omp master", "omp single", "omp atomic"
|
|---|
| 23 | - a single thread executes within block
|
|---|
| 24 | - no sync on entry or exit
|
|---|
| 25 | - atomic has a very restricted form
|
|---|
| 26 | - "omp critical"
|
|---|
| 27 | - one thread at a time in the block
|
|---|
| 28 | - no sync on entry or exit
|
|---|
| 29 | - "omp barrier"
|
|---|
| 30 | - sync -> breaks regions into before and after
|
|---|
| 31 | - "omp sections"
|
|---|
| 32 | - "omp section"
|
|---|
| 33 |
|
|---|
| 34 | Treatment of omp_* calls
|
|---|
| 35 | - when simplifying a construct to remove parallelism
|
|---|
| 36 | - replace omp_get_thread_num() with "0"
|
|---|
| 37 | - replace omp_get_num_threads() with "1"
|
|---|
| 38 | - how should other calls be handled?
|
|---|
| 39 | - conservatively we can prevent simplification if other calls
|
|---|
| 40 | are present
|
|---|
| 41 |
|
|---|
| 42 | Clauses
|
|---|
| 43 | - "if", "num_threads"
|
|---|
| 44 | - these can be ignored, we check unconditional independence of workshares
|
|---|
| 45 | - privacy-related
|
|---|
| 46 | - must be processed to accurately compute dependences
|
|---|
| 47 |
|
|---|
| 48 | Deferred until later
|
|---|
| 49 | - "omp taskwait"
|
|---|
| 50 | - "omp taskgroup"
|
|---|
| 51 | - "omp flush"
|
|---|
| 52 | - "omp ordered"
|
|---|
