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
• case is delta wing 500k target complexity from scitech paper

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

	cores	40		20		10		5		1
OpenMP
static	chunck 1	(0.25,0.26,0.27)	13.07	(0.11,0.12,0.13)	23.02	(0.05,0.05,0.06)	45.42
	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	(42,42.4,42.8)	46.42	(0,0,0)	318.22
	chunck 10
guided	chunck 1
guided	chunck 10
Argobots
chuck 1		(1.8,1.9,3)	10	(1.6,1.6,1.9)	18	(1.5,1.5,1.6)	35	(0.86,1.2,1.7)	71	(0,0,0)	330
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	(0,0,0)	322

Edge Collapse

• Collapse is performed in 3 places, afterreconstruction, after surface refinement, after volume refienement

time for mesh coarsening for openMP and Argobots

cores	40	20	10	5	1
Argobots	0.1	0.13	0.24	0.48	2.06
OpenMP (guided,scheduling)	0.07	0.13	0.25	0.49	1.96

Common Interface

Implemented an abstract interface for creating tasks

/**
* @brief launch tasks using the abt_wrapper and wait until they all finish

* For this version of the function the user_function must expect a pointer
* to one of the elemnts of the provided task_vector
*
* @param user_task_args vector of tasks
* @param user_func the user function to be executed, type should be void func(void*), 
* where argument is ptr to an item in user_task_args
* @param nthreads  number of threads to use
* @param chuck size of the "unit of work" 
*/

template<typename FunctionType, typename UserTaskArgs>
inline void task_for(std::vector<UserTaskArgs>& user_task_args, FunctionType user_func,int nthreads, size_t chuck = 10)

• Two level task creation
  • Create 2*nthreads (level-0) tasks that statically divide the iteration space into user tasks. This allows for multithreaded task creation and better initial load balancing.
  • Each level0 task will create level-1 tasks that will execute chunck times
• abstracts 138 (with documentation) loc to 1.

TODO

• remove void typecasting
• Variadic template

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)

Pre-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)

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.