Fortran OpenMP并行化Differential Evolution中含收敛判断的do-while循环问题

Hey there! I’ve tackled exactly this kind of problem before—iterative optimization algorithms like Differential Evolution (DE) with convergence-based termination are tricky to parallelize at the outer loop level, but the good news is you can get massive speedups by parallelizing the compute-heavy inner work of each iteration. Let’s break this down step by step.

The Core Idea: Don’t Parallelize the Outer Do-While #

You’re right that you can’t slap !$OMP PARALLEL DO directly on the outer do-while—each iteration (generation) of DE depends on the state of the previous one (your population of atomic positions), so the outer loop has to run sequentially. Instead, focus on parallelizing the independent tasks inside each iteration.

Key Parallelizable Steps in DE #

For your atomic potential optimization, the most costly part is almost always calculating the fitness (potential energy) for each individual in the population. Each individual’s potential calculation is completely independent of the others—perfect for parallelization. Here’s how to implement this in Fortran (since you’re using !$OMP directives):

Example Parallelized Code Structure #

Let’s start with a simplified version of your original loop:

! Original serial code
do
    ! 1. Generate new candidate solutions (mutation/crossover)
    call generate_new_population(pop, new_pop, F, CR)
    
    ! 2. Calculate fitness (atomic potential) for each candidate
    do i = 1, pop_size
        fitness(i) = calculate_atomic_potential(new_pop(i))
    end do
    
    ! 3. Selection: Keep the best solutions
    call select_survivors(pop, new_pop, fitness)
    
    ! 4. Check convergence (e.g., change in best fitness is below threshold)
    converged = check_convergence(best_fitness, tolerance)
    if (converged) exit
end do

Now add OpenMP to the fitness calculation (and optionally the population generation, if that’s also independent):

! Parallelized version
do
    ! 1. Generate new candidates (if mutation/crossover is per-individual, parallelize this too)
    !$OMP PARALLEL DEFAULT(SHARED) PRIVATE(i)
    !$OMP DO SCHEDULE(STATIC)
    do i = 1, pop_size
        new_pop(i) = mutate_and_crossover(pop, i, F, CR)
    end do
    !$OMP END DO
    !$OMP END PARALLEL
    
    ! 2. Calculate fitness (the big one!)
    !$OMP PARALLEL DEFAULT(SHARED) PRIVATE(i)
    !$OMP DO SCHEDULE(DYNAMIC)  ! Use DYNAMIC if potential calc times vary per individual
    do i = 1, pop_size
        fitness(i) = calculate_atomic_potential(new_pop(i))
    end do
    !$OMP END DO
    !$OMP END PARALLEL
    
    ! 3. Selection (usually serial—depends on global fitness values)
    call select_survivors(pop, new_pop, fitness)
    
    ! 4. Convergence check (serial—needs global state)
    converged = check_convergence(best_fitness, tolerance)
    if (converged) exit
end do

Critical OpenMP Tips for Your Code #

• Variable Scoping: Always explicitly mark private variables (like loop index i) to avoid race conditions. Use DEFAULT(SHARED) for variables that all threads need access to (like pop, new_pop, fitness).
• Load Balancing: If calculating potential for some atomic configurations takes way longer than others, use SCHEDULE(DYNAMIC) instead of the default static scheduling. This lets threads pick up new tasks as they finish, balancing the workload.
• Avoid Overhead: If your population size is small (e.g., < 100), the overhead of spawning threads might outweigh speedups. Add a conditional check to only enable parallelism when pop_size is large enough.
• Convergence Check: This step has to stay serial—you need to look at the entire population’s fitness to determine if you’ve converged, so there’s no way to parallelize this part efficiently.

Advanced: Parallelizing Other DE Steps #

If your mutation/crossover logic is per-individual (no dependencies between candidates), parallelize that too as shown above. Some selection schemes can also be partially parallelized, but most basic DE selection is serial since it compares each candidate to its parent.

内容的提问来源于stack exchange，提问作者Rainer Hohn