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

Argobots

% improvement of argobots vs thread implementation, ( input delta wing 500k complexity)

cores	1	2	5	10	15	20	25	30	35	40
Mesh Refinement
Time to insert vertices	1.76	6.87	4.47	0.97	2.58	-0.76	-6.42	-9.59	6.46	11.49
Time to create vertices	1.1	18.34	21.33	20.25	20.68	13.6	15.71	19.87	20.63	21.1
Total time to optimize connectivity	-0.7	1.83	0.83	1.69	2.49	0.55	0.3	-1.02	-3.14	-2.01
Time to remove small edges	-2.98	9.56	-42.45	-12.48	-40.41	10.64	-65.03	4.82	-18.08	0.69
Total time to refine the mesh	-0.68	3.46	-1.82	1.82	0.37	3.78	-2.95	2.47	0.61	3.82
Mesh Quality Improvement
Total time to optimize connectivity	0.85	3.02	3.81	4.11	2.36	2.63	1.24	2.65	2.94	3.8
Time to smooth vertices	-1.13	2.2	9.22	7.81	7.88	7.32	7.19	8.21	9.32	16.09
Total time to improve the mesh	-1.32	1.17	5.7	5.05	4.45	3.9	3.33	4.79	5.51	9.3
Summary
Total mesh generation time	-1.04	2.13	3.05	3.61	2.68	3.07	0.58	3.47	2.37	6.01

Argobots + avoid repartitioning in mesh refinement

The changes introduced in the code due to argobots inttegration made easier to avoid the costly re-partitioning of active elements at every iteration. In fact for the previous case we had to force merging to keep similar flow of execution.

% improvement of argobots vs thread implementation

cores	1	2	5	10	15	20	25	30	35	40
Mesh Refinement
Time to insert vertices	2.79	5.76	-1.63	0.97	-1.39	3.04	1.25	-6.65	-8.0	-5.46
Time to create vertices	0.25	15.88	13.34	19.48	20.68	16.14	20.0	21.47	20.63	15.19
Total time to optimize connectivity	-0.51	-0.33	-1.78	-4.87	-2.22	-4.08	-7.8	-5.63	-7.05	-6.62
Time to remove small edges	-2.95	3.18	-13.54	8.88	-62.65	-29.65	-18.7	6.13	-39.48	-45.08
Total time to refine the mesh	-0.36	1.37	-0.47	1.49	-3.23	-0.14	-0.72	3.22	-1.08	-0.24
Mesh Quality Improvement
Total time to optimize connectivity	1.2	2.64	4.24	4.37	1.27	0.65	2.61	2.75	3.5	3.54
Time to smooth vertices	-1.21	2.23	8.26	7.76	7.71	7.26	8.24	8.82	8.9	15.47
Total time to improve the mesh	-1.18	1.09	5.31	4.81	3.69	3.11	4.42	5.26	5.73	8.93
Summary
Total mesh generation time	-0.82	1.32	3.24	3.39	0.91	1.12	1.99	3.58	2.48	3.63

Argobots + naive bucket rebalancing in mesh refinement

For this method at evey iteration buckets with size > 2*max_allowed are split in half

% improvement of argobots (+ rebalancing) vs thread implementation

cores	1	2	5	10	15	20	25	30	35	40
Mesh Refinement
Time to insert vertices (seq)	2.38	6.32	1.12	0.58	-0.4	4.28	4.7	-0.88	4.73	5.65
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 optimize connectivity	0.09	-1.35	-1.11	-2.33	-3.63	-5.44	-6.01	-4.94	-5.64	-6.5
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 mesh	0.15	1.05	-2.36	-1.21	0.71	0.10	0.51	0.94	2.09	2.92
Mesh Quality Improvement
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 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 mesh	-1.56	0.31	4.59	4.37	3.39	3.44	4.27	4.52	4.87	8.81
Summary
Total mesh generation time	-0.88	0.75	2.12	2.36	2.29	1.70	2.66	2.51	3.10	5.42
Number of Vertices	0.03	-0.11	-0.001	0.03	0.07	0.05	0.1	0.06	0.12	0.1
Number of Tetrahedra	0.03	-0.12	-0.003	0.04	0.08	0.06	0.11	0.07	0.12	0.12

Notes

• Evaluated using (threads_time - argobots_time)/threads_time *100, same for counters

Updated : --Christos Tsolakis 12:27, 30 September 2019 (EDT)

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.