Lightweight Parallelism library based on Ada 2022 features

A full implementation of the parallel features of Ada 2022 is yet to be released. In the meantime, here is a light-weight-threading library that provides essentially all of the parallel features of Ada 2022, using various generics, etc. Scheduling is provided using a plug-in architecture. If no scheduler is plugged in, the light-weight threads are simply executed sequentially. If a light-weight-thread scheduler is plugged in, then the light-weight threads spawned by instances of the various generic packages are managed by that scheduler.

There are currently two LWT scheduler plug-ins:

  • a wrapper for the GNU implementation of OpenMP (lwt-openmp.ads)
  • a work-stealing based plug-in, written entirely in Ada (lwt-work_stealing.ads)

Below is a link to the “readme.md” documentation for the GitHub lwt library. It is currently part of the ParaSail GitHub repository, but the files in “lwt” are actually independent of ParaSail. ParaSail has its own work-stealing-based scheduler built-in, but at some point we plan to shift over to using the “lwt” library. But at the moment, there is no dependence either way between the ParaSail interpreter/compiler and the lwt library.

Feel free to open GitHub Issues if you find problems with the implementation, or have suggestions for improvements.

Enjoy!

-Tucker Taft

The ParaSail GitHub repository was created by my colleague Olivier Henley, and he has also helped to improve the documentation and testing scripts. Much appreciated!

10 Likes

Hi, this is great to know. is the plan also for GNAT to use this to implement Ada2022 parallel constructs?

1 Like

That is to be determined. There is some interest in doing this work directly on the FSF sources, without waiting for AdaCore.

6 Likes

Maybe such work could be proposed for the Google Summer of Code 2024? Cf. thread on this forum: https://forum.ada-lang.io/t/urgent-participation-in-google-summer-of-code-2024/

2 Likes

Hi @sttaft!

I took a look at your library as I was interested in OMP and Ada interop. I had seen your work in the past plus the one done by Sara Royuela and Luis Miguel’s.

From what I saw in parasail/lwt/lwt-openmp.ads at 19b7ca4eab850579fcf950f2c90a36c6439cb4a8 · parasail-lang/parasail · GitHub, you are not using pragma OMP but “just” bolting the OMP infraestructure with Import. I saw that in Sara’s and Miguel’s paper, they seem to be using pragma OMP as their parallel directives, see their open access paper Enabling Ada and OpenMP runtimes interoperability through template-based execution. So it may seem that GNAT could potentially deal with OpenMP/OpenACC directives in Ada… I also know you/AdaCore have played around with this technology. I am interested in this technology as one can use OpenMP/OpenACC to offload code to accelerators, such as GFX cards (my laptop has two and GCC-GCN and NVPTX targets support them!).

Do you know if one can have somewhat native OpenMP/OpenACC support in Ada? Here is what I tried and what I got…

OpenMP turmoil

I tried reproducing some code snippets from the aforementioned paper with GNAT 14, using pragma OMP, see the semi-valid code snipped below. However, it does not seem to be supported by GNAT.

with Ada.Text_IO; use Ada.Text_IO;

procedure Fibonacci_OMP is
   function Parallel_Fibonacci(N : Positive) return Positive
   is
      pragma OMP (Parallel, Shared=>X,
        Firstprivate => N);
      pragma OMP (Single, Nowait);
      X : Positive := 1;
      Y : Positive := 1;
   begin
      if N <= 2 then
         return N;
      else
         pragma OMP (task, Shared => X, Firstprivate => N);
         X := Parallel_Fibonacci(N - 2);

         pragma OMP (task, Shared => Y, Firstprivate => N);
         Y := Parallel_Fibonacci(N - 2);
      end if;

      pragma OMP (taskwait);
      return X + Y;
   end Parallel_Fibonacci;
begin
   Put_Line(Parallel_Fibonacci(50)'Image);
end Fibonacci_OMP;

If I compile the code with a simple gnatmake fibonacci-omp.adb, GNAT gets confused by the existence of the task keyword in the pragma, see error below:

gcc -c fibonacci-omp.adb
fibonacci-omp.adb:15:22: error: missing operand
fibonacci-omp.adb:18:22: error: missing operand
fibonacci-omp.adb:20:06: error: missing "end;" for "begin" at line 18
fibonacci-omp.adb:20:06: error: missing "end;" for "begin" at line 15
fibonacci-omp.adb:20:06: error: missing "begin" for procedure <error> at line 12
gnatmake: "fibonacci-omp.adb" compilation error

If I issue the gnatmake fibonacci-omp.adb -fopenmp compilation command, the compiler generates the same error message plus a warning, indicating that OpenMP is not supported for Ada:

gnat1: warning: command-line option ‘-fopenmp’ is valid for C/C++/Fortran/LTO/ObjC/ObjC++ but not for Ada

From what I saw, one can first do a normal code compilation into object code and then, during binding, the OpenMP infraestructure will be bolted in, so I ran gcc -c ada fibonacci-omp.adb -o fibonacci-omp.o -fopenmp with the pragma OMP (task...) commented out (so that it actually gets correctly parsed) and it generated the following:

fernando@localhost:~/Dirt> gcc -c ada fibonacci-omp.adb -o fibonacci-omp.o -fopenmp
gnat1: warning: command-line option ‘-fopenmp’ is valid for C/C++/Fortran/LTO/ObjC/ObjC++ but not for Ada
fibonacci-omp.adb:3:11: warning: file name does not match unit name, should be "fibonacci_omp.adb" [enabled by default]
fibonacci-omp.adb:6:14: warning: unrecognized pragma "Omp" [-gnatwg]
fibonacci-omp.adb:8:14: warning: unrecognized pragma "Omp" [-gnatwg]
fibonacci-omp.adb:22:14: warning: unrecognized pragma "Omp" [-gnatwg]
gcc: warning: ada: linker input file unused because linking not done
gcc: error: ada: linker input file not found: No such file or directory

It says that the OMP pragma is not recognised… I expected it to be, as the code shown in Sara’s paper was used in the benchmark… I checked the generated object file to see if there were any .openmp directives but there are none, so the OMP pragmas were completely ignored…

It should be possible?

From what I read in attachment:OpenMP-OpenACC-Offload-Cauldron2022-1.pdf of cauldron2022talks - GCC Wiki one could theoretically compile any code down to object/GIMPLE format (with the OpenMP directives being present in the generated file) and then that would be correctly processed down to assembly/the target architecture…
But of course, if the pragma OMP directives are ignored, there is not that much to do…

Is there a special flag that needs to be given to GNAT in order for it to process OMP directives? Is it maybe a development branch that is being used?

OpenACC tests

I know that the idea of usign OpenACC has been studied within AdaCore (see this article/video). But once again, no info on the matter…

GNAT implementation

I saw no pragmas related to parallelism/OpenMP/OpenACC/Offloading in the 2. Implementation Defined Pragmas — GNAT Reference Manual 25.0w documentation GNAT documentation… So there does not seem to be anything available…


Soooo… That is all from my side… It does not seem to be possible to have any OpenMP/OpenACC support in Ada from the default GCC/GNAT…

Have you/AdaCore explored upstreaming the work done? If it maybe possible to do so with LLVM? I know that there is GitHub - AdaCore/cuda and some CUDA support in GNAT…

EDIT: for information, here is the GCC documentation regarding offloading Offloading - GCC Wiki and Offloading - GCC Wiki AMD GCN Options (Using the GNU Compiler Collection (GCC))

The only work that AdaCore has done is with CUDA, which includes new aspects “with CUDA_Global” and “with Designated_Storage_Model => …” and a new “pragma CUDA_Execute(…)”. AdaCore is yet to support the Ada 2022 parallel syntax. As far as pragma OMP, that might have been implemented by Sara Royuela et al, but it is not directly supported by the GNAT distributed by AdaCore.

Using the OpenMP API rather than OpenMP pragmas works pretty well, but as you have implied, it doesn’t support offloading to accelerators. You might be able to figure out a way to combine GNAT’s CUDA-oriented pragmas and aspects with uses of the OpenMP API and/or the lightweight parallelism library that I described, but I have not personally tried that.

1 Like

Looks like this requires protected objects. I hope the Ada 2022 won’t but I guess it will. You can say that adding protected object runtime support is easy. However unless a runtime with protected object support is going to be provided for whole chip families like cortex then how can you say it is easy. Containers certainly could have and should have worked in many cases on light runtimes too.

I shall just write my own scheduler (without threads) that works on any chip instead :roll_eyes:.

Does tinygo achieve more easily portable co routines?

Ayke van Laethem – Goroutines in TinyGo :sweat_smile: :innocent:

I have a bootstrap-compiler I’m writing with GRAAL/Truffle, Truffle allows polyglot programs/free-interop and among the language implementations is NVidia’s grCUDA… so the plan for the bootstrap compiler is to implement the PARALLEL constructs/processing by “handing it over” to grCUDA.

There were a few race conditions found in the handling of the work-stealing queue, when it was in the process of being doubled in size (ironic to have a race condition in the scheduler… ;-). These race conditions have now been repaired in the version on GitHub. There was also a storage leak detected by Valgrind, which has been fixed.

To reiterate, the light-weight threading library is available at:
//github.com/parasail-lang/parasail/tree/main/lwt

2 Likes

What about libdispatch?
Apple created Grand Central Dispatch for parallelism on macOS.
It is also used by Apache in its famous HTTP server.
It has been ported to Linux at least ArchLinux.
The Apple Github repo is available under Apache license.

Libdispatch has a number of interesting features, but it probably isn’t a great match for the lightweight parallelism features of Ada 2022. It could be an interesting alternative if provided as a library of generics for Ada.