State of Parallel Gibbon

[ulysses4ever]

At the last group meeting, we discussed the issue with Parallel Gibbon relying on the Cilk library, which is not as easily available as it once used to be when it was a part of the GCC 7 distribution. As a consequence of this Cilk issue, we don't test anything about Parallel Gibbon in CI.

Our options for modernizing Parallel Gibbon and liberating from the GCCV 7 dependency seem to be:

• Switch to the successor of Cilk Plus -- OpenCilk
  • Seemingly the most straightforward option but there's a catch: it's huge and compiling it means, among other things, compiling (a fork of) LLVM. Also, it's not packaged in nixpkgs , see Package request: OpenCilk NixOS/nixpkgs#144256
• Switch to a Cilk alternative that's lighter than OpenCilk. E.g
  • https://github.com/cmuparlay/parlaylib
  • OpenMP
    @vollmerm says that it's not trivial because the new library should allow us to observe steals
• Do nothing and wait until OpenCilk becomes more approachable
• Roll out our own work-stealing task parallelism on top of Pthreads or similar. May be a good student project.

@vollmerm regarding the issue with observing steals that you mentioned: I dived a little into the implementation, and it looks like the current way to observe steals is to record the thread ID (and the ICFP'21 paper confirms it):

gibbon/gibbon-compiler/src/Gibbon/Passes/ParAlloc.hs

Lines 243 to 248 in 32723ed

	pure $ LetE (cont_id, [], IntTy, Ext GetCilkWorkerNum) $
	LetE (not_stolen, [], BoolTy, PrimAppE EqIntP [VarE cont_id, VarE parent_id]) $
	IfE (VarE not_stolen)
	(Ext $ LetAvail [v] $
	Ext $ LetLocE loc (AfterVariableLE v loc2 False) bod2) -- don't allocate in a fresh region
	(Ext $ LetParRegionE newreg Undefined Nothing $ Ext $ LetLocE newloc (StartOfRegionLE newreg) bod1)

Getting the thread ID seems like a pretty basic operation that most alternatives would be capable of (e.g. OpenMP has omp_get_thread_num) Is that right?

/cc @ckoparkar @rrnewton

[vollmerm]

👍 on just using OpenMP, since we only need to compare the thread number. We can use the OpenMP task pragma: https://www.ibm.com/docs/en/zos/3.1.0?topic=processing-pragma-omp-task