Computer Architecture

Automatic Detection of Parallelism

Automatic Detection of Parallelism

A Grand Challenge for High-Performance Computing

W. Blume, R. Eigenmann, J. Hoelflinger, D. Padua, P. Petersen, L. Rauchwerger, P. Tu

May 4, 2007

Gustavo Petri

Automatic Detection of Parallelism

Automatic Detection of Parallelism Motivation

Motivation

Again: Moore law is falling. Overcome: Multicores (Multithreading). Programming Multithreading:

How Processors Communicate. How Data is Mapped. Usually not Portable.

Therefore:

Hard. Error Prone. Expensive.

We want:

Sequential Programming. Parallel Execution. Machine Specific Work ← Compiler.

Gustavo Petri Automatic Detection of Parallelism

Automatic Detection of Parallelism Motivation

Approaches

Parallelizing Compilers. Transactional Memory Models. Still an Issue.

Gustavo Petri

Automatic Detection of Parallelism

Automatic Detection of Parallelism Motivation

Today Compilers (as per 1994)

Not really good:

Parallelization of Scalar Independent Variables. Very simple array access patterns (No nested loops).

Why:

Analysis Techniques are not good enough (do’h). Static Analysis not enough.

Gustavo Petri

Automatic Detection of Parallelism

Automatic Detection of Parallelism Basic Techniques

Basic Techniques (High Level)

Data Dependence Analysis:

Flow Dependencies: S2 → S1 S1 : x := ......... := ... x ... S2 : Anti-Dependencies: S2 → S1 S1 : := ... x ... S2 : x := ......... Output-Dependencies: S2 → S1 S1 : x := ......... S2 : x := .........

od ad fd

No dependencies ⇒ Parallelizable!!.

Gustavo Petri

Automatic Detection of Parallelism

Automatic Detection of Parallelism Basic Techniques

(Scalars) Dependencies Example

S1 S2 S3 S4 S3 → S1 ad S4 → S2 Parallelizable: S1; S3

fd

: : : :

A D G H

:= := := :=

B E A H

+ + + +

C F C C

S2; S4

Gustavo Petri

Automatic Detection of Parallelism

Automatic Detection of Parallelism Basic Techniques...