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

Preliminary Data

Overall

cores	1	2	5	10	15	20	25	30	35	40
Time to reconstruct mesh	8.35	7.52	5.84	8.27	5.20	0.24	1.24	-1.73	0.35	-0.89
Time to initial coarsening	-3.37	-0.54	3.43	8.98	-2.44	-1.52	-26.42	-40.00	-50.00	-53.49
Surface Mesh Refinement
Number of iterations	0	11	-2	-3	3	0	8	5	1	5
Time to deactivate/group tets	1.02	10.57	2.43	-1.37	-9.60	-14.58	-10.66	-8.72	-8.68	-6.38
Time to create vertices	0.75	20.84	11.41	2.23	3.94	-1.97	3.62	1.79	1.95	0.65
Time to insert vertices	0.00	-50.00	-55.00	-150.00	-85.00	-76.19	-57.14	-66.67	-47.83	-70.00
Total time to optimize connectivity	0.18	7.21	-3.72	-3.50	5.85	0.59	6.35	2.74	5.03	6.13
Time to partition tetrahedra	0.43	20.03	-17.11	-9.54	-3.99	-7.07	6.50	-0.13	-4.23	2.34
Time to remove small edges	-1.77	10.92	10.14	29.20	13.08	14.02	29.27	17.27	26.15	37.76
Time to delete boundary slivers	8.00	-10.71	3.23	0.00	0.00	0.00	0.00	0.00	0.00	0.00
Total time to refine surface mesh	-0.02	11.64	-0.80	-0.32	-1.11	-5.36	2.88	-0.41	-0.14	1.82
Number of iterations	0	0	0	0	3	-2	0	0	0	-1
Mesh Refinement
Time to deactivate/group tets	0.16	2.01	2.46	-0.09	-4.19	-6.03	-3.39	-2.06	-1.92	-1.90
Time to create vertices	0.09	17.77	19.57	18.17	20.08	16.39	19.29	20.35	18.69	12.62
Time to insert vertices	2.38	6.32	1.12	0.58	-0.40	4.28	4.70	-0.88	4.73	5.65
Total time to optimize connectivity	0.09	-1.35	-1.11	-2.33	-3.63	-5.44	-6.01	-4.94	-5.64	-6.50
Time to partition tetrahedra	96.11	96.29	95.95	96.26	96.12	96.28	96.57	96.17	96.27	96.14
Time to remove small edges	-2.72	8.01	-41.21	-29.26	-14.11	-16.03	-21.31	-27.97	-23.25	-16.41
Total time to refine the mesh	0.15	1.05	-2.36	-1.21	0.71	0.10	0.51	0.94	2.09	2.92
Time to activate tetrahedra	5.26	23.53	3.85	8.00	-2.27	4.55	12.77	10.42	8.33	-9.09
Time to deactivate/group tetrahedra	-38.58	-41.11	-39.17	-37.35	-42.69	-36.99	-31.37	-26.94	-23.97	-23.61
Mesh Quality Improvement
Total time to optimize connectivity	0.06	2.46	3.05	3.13	0.89	1.39	1.95	2.97	2.34	3.63
Time to partition tetrahedra	-3.16	0.09	4.18	1.81	4.05	6.00	9.45	4.14	8.14	2.26
Time to smooth vertices	-0.96	0.94	7.84	7.48	7.70	7.31	7.92	7.96	8.48	15.51
Total time to improve the mesh	-1.56	0.31	4.59	4.37	3.39	3.44	4.27	4.52	4.87	8.81
Number of Tetrahedra	0	0	0	0	0	0	0	0	0	0
Number of Vertices	0	0	0	0	0	0	0	0	0	0
Summary
Memory used in MB	0.87	0.67	0.33	0.10	-0.02	-0.06	-0.08	-0.10	-0.11	-0.12
Total mesh generation time	-0.88	0.75	2.12	2.36	2.29	1.70	2.66	2.51	3.10	5.42

Smoothing

• 5 iterations of smoothing are applied for all cases
• case is delta wing 500k target complexity from scitech paper

total smoothing time

	cores	40	20	10	5	1
OpenMP static	chunck 1	13.07	23.02	45.42	75.93	319.32
	chunck 10	17.38	30.62	58.37	119.682	530.316
OpenMP dynamic	chunck 1	5.18	9.46	20.7	46.42	318.22
	chunck 10	8.41	14.53	30.41	62.54	318.82
OpenMP guided	chunck 1	15.32	28.54	56.36	111.56	526.962
	chunck 10	10.22	17.22	33.80	67.62	318.394
Argobots	chuck 1	10	18	35	71	330
	chunk 10	10.15	17.34	34.37	69.57	322

Average % of skipped vertices per iteration

	cores	40	20	10	5	1
OpenMP static	chunck 1	0.26	0.12	0.05	0.03	0
	chunck 10	1.52	1.62	1.52	1.05	0
OpenMP dynamic	chunck 1	61.8	59.1	51.45	42.4	0
	chunck 10	21.31	22.64	17.54	12.95	0
OpenMP guided	chunck 1	0.30	0.14	0.07	0.03	0
	chunck 10	0.31	0.14	0.06	0.03	0
Argobots	chuck 1	1.9	1.6	1.5	1.2	0
	chunk 10	0.50	0.30	0.15	0.09	0

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.15	0.95	0.13	0.2	1.58	0.24	0.25	3.98	0.48	0.48	5.73	2.06	2.08	27.09
OpenMP (guided,scheduling)	0.07	0.11	1.13	0.13	0.15	2.68	0.25	0.39	4.06	0.49	0.5	6.64	1.96	2.03	26.26

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)

// second version that allows for an extra field of common arguments to be shared among tasks
template<typename FunctionType, typename UserTaskArgs, typename UserCommonArgs>
inline void task_for(std::vector<UserTaskArgs>& user_task_args, FunctionType user_func, UserCommonArgs& user_common_args, 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 user_func
• abstracts 138 (with documentation) loc to 1.
  • 11 occurences in the current code ( 2019.09.27)

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

Implementation Notes

• Local reconnection and vertex creation (and other tasks directly related to them) operate on a single bucket.
• Edge collapse and vertex smoothing tasks operate of every vertex.
• Important refactoring is that even sequential operations like vertex insertion was modified to operate on buckets ( one at a time) this eases the transition, provides a common approach and prepares for the future parallelization of the operation.
• Future Work
  • The speculative approach introduces rollbacks , find a way to resolve them in the middleware level

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.