computablee / DotMP

A collection of powerful abstractions for parallel programming in .NET with an OpenMP-like API.
https://computablee.github.io/DotMP/
GNU Lesser General Public License v2.1
29 stars 8 forks source link

Add `ordered` construct #11

Closed computablee closed 1 year ago

computablee commented 1 year ago

OpenMP supports an ordered construct. It is a little complex and I believe it is best explained here.

I was thinking of implementing it like this:

OpenMP.Parallel.For(0, n, action: () => {
    // ...
    OpenMP.Parallel.Ordered(() => {
        // ...
    });
    // ...
});

The functionality is a little tricky to implement. We'll need to store each thread's current working iteration in the Init class. Then we need some way to impose an order on the action. There might be a best way to do this efficiently without spinwaits, but I can't think of one off the top of my head. Let's discuss before I assign this issue to anyone.

diogolopes18-cyber commented 1 year ago

From what I've understood of the Stack Overflow you shared, all threads execute concurrently until they encounter an ordered region, then they execute sequentially. There are two approaches mentioned: the static and the dynamic one. I'm assuming the goal is to implement a behavior similar to the dynamic one, right?

computablee commented 1 year ago

@diogolopes18-cyber The static versus dynamic question is with regards to the scheduler passed to OpenMP.Parallel.For. The implementation of ordered shouldn't depend on the schedule. A naive pseudocode implementation would be

while (current_thread.current_iteration != this_ordered_region.current_iteration)
    spin.SpinOnce();

action();
++this_ordered_region.current_iteration;
computablee commented 1 year ago

I've gone ahead and implemented this myself.