Fork-Join model of parallel execution Execution starts with one thread of control - master thread Parallel regions fork off new threads on entry - team thread Threads join back together at the end of the region - only master thread continues

• Portable
  • Definition by Parallel Computing Forum
  • Fortran interface available for over a year
  • C and C++ interface announced just a few months ago

---

Shared-memory architectures (Some) Memory can be accessed by all threads

• Hardware and Software Vendors
  • Absoft Corp.
  • Digital Equipment Corp.
  • Edinburgh Portable Compilers
  • GENIAS Software GmBH
  • Hewlett-Packard
  • Intel
  • IBM
  • Kuck &Associates
  • Myrias Computer Technologies
  • Numerical Algorithms Group
  • The Portland Group, Inc.
  • Silicon Graphics / Cray Research
  • Sun Microsystems
• Application Developers and Others
  • ADINA R&D, Inc.
  • ANSYS, Inc.
  • Dash Associates
  • Fluent, Inc.
  • ILOG (CPLEX Division)
  • LSTC Corp.
  • MECALOG SARL
  • Oxford Molecular Group PCL
  • US Department of Energy ASCI Program

• MSI Systems
  • SGI Origin: Complete support for Fortran, C, C++
  • IBM SP:
  • Partial Support for Fortran
    • PARALLEL DO (Note: END PARALLEL DO now supported)
    • PARALLEL SECTIONS / SECTION / END PARALLEL SECTIONS
    • CRITICAL / END CRITICAL
  • Support for C, C++ coming
• Additional support for IBM SP in XL Fortran 6.1
• BARRIER directive
• DO/END DO directives and DO (work-sharing) construct
• END PARALLEL DO directive
• MASTER/END MASTER directives and MASTER construct
• PARALLEL/END PARALLEL directives and PARALLEL construct
• DEFAULT clause in directives
• FIRSTPRIVATE clause in directives
• omp_get_thread_num service and utility procedure
• omp suboption for the -qsmp comiler option

• Requires creating new parallel region
• Not supported on all OpenMP implementations
  • If no allowed, inner PARALLEL is a no-op

PROGRAM main
!$OMP PARALLEL
CALL foo()
CALL bar()
CALL error()
!$OMP END PARALLEL


SUBROUTINE error()
! Not allowed due to nested control structs
!$OMP SECTIONS
!$OMP SECTION
CALL foo()
!$OMP SECTION
CALL bar()
!$OMP END SECTIONS
END


SUBROUTINE foo()
!$OMP DO
DO i = 1, n
       ...
END DO
!$OMP END DO
END


SUBROUTINE bar()
!$OMP SECTIONS
!$OMP SECTION
CALL section1()
!$OMP SECTION
...
!$OMP SECTION
...
!$OMP END SECTIONS
END

!$OMP PARALLEL
!$OMP DO
   DO I=2, N
      B(I) = (A(I) + A(I-1)) / 2.0
   ENDDO
!$OMP END DO NOWAIT
!OMP DO
   DO I=1, M
     Y(I) = SQRT (Z(I))
   ENDDO
!$OMP END DO NOWAIT
!$OMP END PARALLEL

!$OMP PARALLEL DEFAULT(PRIVATE) SHARED(X,Y)
!$OMP CRITICAL (XAXIS)
       CALL DEQUEUE(IX_NEXT,X)
!$OMP END CRITICAL (XAXIS)

       CALL WORK(IX_NEXT,X)

!$OMP CRITICAL (YAXIS)
       CALL DEQUEUE(IY_NEXT,Y)
!$OMP END CRITICAL (YAXIS)

       CALL WORK(IY_NEXT,Y)

!$OMP END PARALLEL

• THREADPRIVATE directive
  • Makes common blocks private to a thread
  • Must appear in the declaration section
  • Data written to the common blocks by one thread not directly visible to other threads
  • For serial portions or MASTER sections, the master thread's copy is accessed
  • Must appear after every declaration of thread private common block
  • Variables in a thread private common block can not appear in any clause except COPYIN
• Data scope attribute clauses
  • PRIVATE (list)
  • SHARED (list)
  • ORDERED
  • SCHEDULE (type [, chunk])
    • Type: STATIC, DYNAMIC, GUIDED, RUNTIME
  • DEFAULT (PRIAVTE | SHARED | NONE)
  • FIRSTPRIVATE (list)
  • LASTPRIVATE (list)
  • REDUCTION ({operator | intrinsic } :list)
    • A variable can appear only once in a REDUCTION clause
    • Multiple REDUCTION clauses allowed for a directive
  • COPYIN (list)
    • Applies only to common blocks declared as THREADPRIVATE

INTEGER x(3), y(3), z
!$OMP PARALLEL DO DEFAULT (PRIVATE), SHARED(x), &
!$OMP REDUCTION(+:z)
   DO k = 1, 3
      x(k) = k
      y(k) = k*k
      z = z + x(k) * y(k)
   END DO
!$OMP END PARALLEL DO

• For controlling execution
  • Needed for tuning, but may limit portability
  • Control through environment variables or runtime library calls
    • Runtime library takes precedence in conflict

• OMP_NUM_THREADS: How many to use in parallel region
  • OMP_GET_NUM_THREADS, OMP_SET_NUM_THREADS
  • Related: OMP_GET_THREAD_NUM, OMP_GET_MAX_THREADS, OMP_GET_NUM_PROCS
• OMP_DYNAMIC: Should runtime system choose number of threads?
  • OMP_GET_NESTED, OMP_SET_DYNAMIC
• OMP_NESTED: Should nested parallel regions be supported?
  • OMP_GET_NESTED, OMP_SET_NESTED
• OMP_SCHEDULE: Choose DO scheduling option
  • Used by RUNTIME clause
• OMP_IN_PARALLEL: Is the program in a parallel region?

Code with OpenMP and/or SGI directives:
f77 -options -mp code.f

Automatic Parallelization:
f77 -apo mycode.f

REAL x(nnode), y(nnode), flux
INTEGER iedge(nedge,2)
err = tol * 1e6
DO WHILE (err > tol)
   DO i = 1, nedge
      flux = (y(iedge(i,1))-y(iedge(i,2))) / 2
      x(iedge(i,1)) = x(iedge(i,1)) - flux
      x(iedge(i,2)) = x(iedge(i,2)) + flux
      err = err + flux(i)*flux(i)
   END DO
   err = err / nedge
   DO j = 1, nnode
      y(i) = x(i)
   END DO
END DO

• Flux computations are data-parallel
  • flux=(x(iedge(i,1)) - x(iedge(i,2)))/2
• Node updates are nearly data-parallel
  • x(iedge(i,1)) = x(iedge(i,1)) - flux
  • Not independent if iedge(iy,1) = iedge(ix,2)
  • But ATOMIC supports associative updates
• Error check is a reduction
  • err = err + flux(i)*flux(i)
  • REDUCTION class for variables

• Communication needed for all parts
  • Edge-node (computing flux); node-node (computing x); reduction (computing err)
  • Communication handled simply by shared or reduction variables
• Because of the tight ties between flux, x, and err, keep the loop intact
  • Incremental parallelization via OpenMP works perfectly
  • Any agglomeration scheme balances computation load
  • Agglomeration will change locality though

!$OMP PARALLEL, DEFAULT(SHARED)
!$OMP SINGLE
err = tol * 1e6
!$OMP END SINGLE
DO WHILE (err > tol)
    !$OMP DO, PRIVATE(flux), REDUCTION(+:err)
    DO i = 1, nedge
        flux = (y(iedge(i,1))-y(iedge(i,2)))/2
        !$OMP ATOMIC
        x(iedge(i,1)) = x(iedge(i,1)) - flux
        !$OMP ATOMIC
        x(iedge(i,2)) = x(iedge(i,2)) + flux
        err = err + flux(i)*flux(i)
    END DO
    !$OMP END DO
    !$OMP SINGLE
    err = err / nedge
    !$OMP SINGLE
    !$OMP DO
    DO j = 1, nnode
        y(i) = x(i)
    END DO
    !$OMP END DO
END DO
!$OMP END PARALLEL

• There may be significant differences in data movement based on scheduling
• The ideal:
  • Every thread runs over its own edges (static scheduling)
  • Endpoints of these edges are not shared
  • Data moves to its home on the first pass, then stays put
• The reality:
  • Connect graph => some endpoints must be shared
  • Multi-word data moves (cache lines) => false sharing
  • OpenMP does not standardize how to resolve this
    • Best bets: Reorder data for locality or use nonstandard directives (HPF + MPI?)

!$OMP PARALLEL, DEFAULT(SHARED)
CALL renumber_nodes( iedge, permute_node)
!$OMP DO
DO i = 1, nnode
    x( permute_node(i) ) = old_x(i)
END DO
!$OMP END DO NOWAIT
!$OMP DO
DO i = 1, nedge
    iedge(i,1) = permute_node(iedge(i,1))
    iedge(i,2) = permute_node(iedge(i,2))
END DO
!$OMP END DO
CALL sort_edges(iedge, nedge)
!$OMP SINGLE
err = tol * 1e6
!$OMP END SINGLE
DO WHILE (err > tol)
    !$OMP DO, SCHEDULE(STATIC), PRIVATE(flux), REDUCTION(+:err)
    ...
    !$OMP END DO
END DO
!$OMP END PARALLEL

• Based on fork-join parallelism in shared memory
  • Threads start at beginning of parallel region, come back together at end
  • Close to some hardware
  • Linked from traditional languages
• Very good for sharing data and incremental parallelization
• Unclear if it is feasible for distributed memory