CON03-F. Protect multithreading recurrences to avoid data races

Developers should ensure that loop-carried dependencies in multithreaded code are properly protected using synchronization directives or parallel patterns to prevent data races and ensure deterministic behavior.

A recurrence computation pattern, or loop-carried dependency, occurs when a loop iteration reads or writes to a memory that is also accessed by another iteration. This pattern encompasses both true dependencies (read-after-write) and anti-dependencies (write-after-read). Parallelizing a loop with such dependencies without proper protection can result in data races, producing nondeterministic or inconsistent results.

Noncompliant Code Example

In this noncompliant example, an exclusive scan (prefix sum) is parallelized naively. Each iteration of y(i) depends on y(i-1) . When threads execute iterations out of order, a thread may read y(i-1) before it is updated, causing a data race and nondeterministic results.

subroutine scan_risk(x, y)
  implicit none
  integer, intent(in) :: x(:)
  integer, intent(inout) :: y(:)
  integer :: i
  
  y(1) = 0
  ! Noncompliant: i depends on y(i-1), creating a loop-carried dependency.
  ! Naive parallelization results in a data race.
  !$omp parallel do private(i) shared(x, y)
  do i = 2, size(y, 1)
    y(i) = y(i - 1) + x(i - 1)
  end do
  !$omp end parallel do
end subroutine scan_risk

Compliant Solution

In the compliant solution, prefix sums can be safely parallelized using OpenMP's scan directive. The inscan reduction type ensures the dependencies are managed by the runtime, providing a happens-before relationship for the intermediate results.

subroutine scan_safe(x, y)
  implicit none
  integer, intent(in) :: x(:)
  integer, intent(out) :: y(:)
  integer :: scan_x, i
  
  scan_x = 0
  ! Compliant: Using the inscan reduction and scan directive 
  ! to safely manage the recurrence pattern.
  !$omp parallel do private(i) reduction(inscan, +:scan_x) shared(x, y)
  do i = 1, size(y, 1)
    y(i) = scan_x
    !$omp scan exclusive(scan_x)
    scan_x = scan_x + x(i)
  end do
  !$omp end parallel do
end subroutine scan_safe

Risk Assessment

Unprotected recurrences lead to data races that cause data integrity violations and non-deterministic logic errors. This can lead to incorrect state management or exploitable vulnerabilities.

Attachments: