Internal:Argobots and CDT3D

Objective

Replace native/system threads with Argobots tasklets. Goal offload load balancing and thread manipulation to Argobots and ultimately to PREMA

Data

Smoothing

• 5 iterations of smoothing are applied for all cases

Data format (min,avg,max) % of roolbaks per iteration , total smoothing time

	cores	40		20		10		5
OpenMP
static	chunck 1
	chunck 10
dynamic	chunck 1	(61.6,61.8,62.1)	5.18	(58.9,59.1,59.5)	9.46	(51.13,51.45,51.76)	20.7
	chunck 10
guided	chunck 1
guided	chunck 10
Argobots
chuck 1		(1.8,1.8,3.2)	10
chunk 10		(0.46,0.50,0.95)	10.15	(0.28,0.30,0.38)	17.34	(0.15,0.15,0.20)	34.37	(0.08,0.09,0.18)	69.57

Implementation Notes

• There are Blocking and non-blocking tasks.
• Both can wait for their children
• Blocking can wait(yield) on Argobbots specific mutexes, locks etc
• There is a task create and join capability
• Thread id is can be acquired within in the task ( we need it in CDT3D in order to know in which memory pool to allocate ith no syncronization)
• Preferably we would like many tasks created in a tree-like fashion so that task initialization cost can be distributed
• In create_vertices we could use blockable tasks (spinlocks can be replaced with ABT spinlocks) also atomic locks can become atomic "read locks"
• remember to tweak stack size to the size required by predicates.
• Candidates for porting:
  • (Vertex-based) smoothing (easy)
    • OpenMP based
  • Edge collapse (easy)
    • OpenMP based
  • vertex creation (modetate)
    • custom bucket based load balancer
  • parallel reconnection (moderate)
    • custom bucket based load balancer

--Christos Tsolakis 19:49, 5 September 2019 (EDT)

Important Findings

• For operations applied on neighboring entities (vertices,tetrahedra) a bigger chunk size in OpenMP plays a very imporant role

in the chance of rollbacks. This is because a small chunk is associated with different cores and thus increases the propability of roolback.

• In Argobots.PREMA because we launch the tasks in two stages, many chuncks are grouped together and thus this chance is lower.

--Christos Tsolakis 18:11, 12 September 2019 (EDT)

Previous Discussions

Ideas

Try first at element granularity :

Refactor Local Reconnection loop so that a function of type

   for every element t :
       attempt_flip(t)

attempt_flip will be a tasklet in the Arbobots nomenclature (ie the lightest work units, that run to executing and offer no blocking)

Bonus present it in a power-aware fashion

Advantages

• Offload load balancing from CDT3D to PREMA.
• Allow take advantage from PREMA's future plans on memory locality awareness on DSM systems.
• Ability to "boost" a CDT3D instance if more than on of them are running on the same PREMA process.
  • Reason: If we have more that one CDT3D instance a shared task pool will provide access to more parallelism when one of the CDT3D instances runs a section of the code sequencially or with small number of threads.
  • Example: Two CDT3D instances (A &B) with 8 threads sharing a task pool. If A runs a sequential part of the code, B can use up to 17 threads to run its parallel parts. ( Caveat: Starvation may appear see solution below using groups.)
  • Indirect contribution to PDR.

Details

• Bucket-level granularity since element-level would to too fine.
  • Should be have constant size of buckets or constant number of buckets(current implementation):
    • TODO Gather data on time per bucket (Histogram)
    • TODO Use histogram distribution to create mini benchmark/test application for PREMA.
    • Constant size of bucket will allow for CDT3D to come closer to PODM ie cavity level parallelism.
• As a first attempt we can try to replace push to thread pool to push to arbobots pool this should have no runtime overhead. (Use example code from Polykarpos).
• Keep buckets alive.
• Replace Mesh Partitioning with bucket rebalancing in parallel.
• Bucket rebalancing task may launch additional tasks. there is no need of synchonization between rebalancing and mesh operation.
• Task crearion and distribution will be done recursively.
• Update global inactive tertahedra pointer carefully.(CAS, one per bucket)

• Thread-id will be replaced by stream id.
  • Thread-id is used (a) to write to a memory pool that no other thread is writing. (b) To tag locked vertices
• Ultimately we would like to recast all parallel parts of CDT3D into parallel executrion modes with a unique interface, having thus only one part of the code, interfacing with Argobots. Moreover, a proper refactoring will allow thread-based implementation to co-exist as a fallback option when CDT3D is compiled without Argobots.
• Thread groups is also a interesting and usefull idea towards building this integration.
  • Problem WITHOUT groups : If we have two CDT3D instances ( A & B) running on the same PREMA process, a unique task-pool will be offered by PREMA. This means that tasks (with varying size) from either instance A or B will be pushed into the task-pool. Due to the non-deterministict nature of the task-scheduling there is a possibbility that one CDT3D instance will starve because few of its tasks are waiting into the task-pool while the other one consumes all the available threads.
  • Solution: Divide requested number of threads of the two CDT3D instances into two groups. Use hierachical work stealing to give priority first to local tasks and then to remote.