Difference between revisions of "PDR.PODM Distributed Memory"

From crtc.cs.odu.edu
Jump to: navigation, search
(15 MPI ranks depth: 4)
 
(82 intermediate revisions by 2 users not shown)
Line 1: Line 1:
=== Current Issues ===
+
=== Issues ===
 
* No reuse of leaves refined by worker nodes. The picture below shows the issue. Two neighbour leaves (0,1) each refined as the main leaf (0 top, 1 bottom) but not refined as a neighor.
 
* No reuse of leaves refined by worker nodes. The picture below shows the issue. Two neighbour leaves (0,1) each refined as the main leaf (0 top, 1 bottom) but not refined as a neighor.
 
[[File:PDR_PODM_Leaves_not_refined.png| 700px]]
 
[[File:PDR_PODM_Leaves_not_refined.png| 700px]]
* Current algorithm to distribute cells to leaves misses some cells. Such a case can happen when two cells only share an edge as in the picture below.
+
* Current algorithm uses neighbour traversal to distribute cells to octree leaving some cells out in some cases. Such a case can happen when a cell is part of an octree leaf based on its circumcenter but
 +
it does not have any neighbour in the same leaf.
 +
 
 
[[File:PDR_PODM_Cells_not_distributed.png| 700px]]
 
[[File:PDR_PODM_Cells_not_distributed.png| 700px]]
 +
 +
* During unpacking the incident cell for each vertex is not set correctly. Specifically, in the case that the initial incident cell is not part of the working unit (Leaf + LVL.1 Neighbours) and thus is not local,
 +
it is set to the infinite cell. This causes PODM to crash randomly for some cases.
 +
 +
* Another issue comes from the way global IDs are updated for each cell's neighbors' IDs. The code that updates the cell's connectivity using global IDs takes the neighbor's pointer, retrieves its global ID and
 +
updates the neighborID field. However, when the neighbour is part of another work unit's leaf and is not local this pointer is NULL. In this case the neighborID field is wrongly reset to the infinite cell ID, which
 +
as result, deletes the connectivity information forever.
 +
 +
* The function that unpacks the required leaves before refinement does not discard duplicate vertices. Duplicate vertices will always be present since each leaf is packed and sent individually, and as a result,
 +
neighbouring leaves will include the shared vertices. Because duplicate vertices are not handled, multiple vertex objects are created that are in fact the same point geometrically. Thus, two cells that share
 +
a common vertex could have pointers to two different vertex objects and, as a result, each cell views a different state about the same vertex.
 +
 +
=== Fixes ===
 +
 +
 +
 +
 +
 +
 +
[[File:PDR_Fix.png| 700px]]
 +
 +
[[File:Work_Unit_After_Refinement.png| 700px]]
 +
 +
 +
= Interesting Findings =
 +
== Delta 0.880 ==
 +
=== 15 MPI ranks depth: 3 ===
 +
<div class="mw-collapsible mw-collapsed">
 +
 +
 +
 +
[[File:PDR PODM Histogram Time 15 d3.png| 700px]]
 +
[[File:PDR PODM Histogram Tasks 15 d3.png| 700px]]
 +
[[File:PDR PODM Time Break Down 15 d3.png| 700px]]
 +
 +
[[File:PDR PODM Parallelism.png| 700px]]
 +
[[File:PDR_PODM_Histogram_15.png| 700px]]
 +
</div>
 +
 +
=== 15 MPI ranks depth: 4 ===
 +
<div class="mw-collapsible mw-collapsed">
 +
 +
 +
 +
[[File:PDR PODM Histogram Time 15.png| 700px]]
 +
[[File:PDR PODM Histogram Tasks 15.png| 700px]]
 +
[[File:PDR PODM Time Break Down 15.png| 700px]]
 +
 +
</div>
 +
 +
=== 40 MPI ranks / 40 cores depth: 4 ===
 +
<div class="mw-collapsible mw-collapsed">
 +
Total Time: 824.29
 +
 +
Total Tasks: 11413
 +
 +
[[File:PDR PODM Histogram Time 40.png| 700px]]
 +
[[File:PDR PODM Histrogram Tasks 40.png| 700px]]
 +
[[File:PDR PODM Time Break Down 40.png| 700px]]
 +
</div>
 +
 +
=== 160 MPI ranks / 10 cores depth: 4 ===
 +
<div class="mw-collapsible mw-collapsed">
 +
Total Time: 378.32
 +
 +
Total Tasks: 12652
 +
 +
[[File:PDR PODM Histogram Time 160 10.png| 700px]]
 +
[[File:PDR PODM Histrogram Tasks 160 10.png| 700px]]
 +
[[File:PDR PODM Time Break Down 160 10.png| 700px]]
 +
</div>
 +
 +
== After Parallel int to pointer ==
 +
=== 15 MPI ranks depth: 3 ===
 +
<div class="mw-collapsible mw-collapsed">
 +
 +
 +
[[File:PDR PODM Histogram Time 15 d3 par int2ptr.png| 700px]]
 +
[[File:PDR PODM Histogram Tasks 15 d3 par int2ptr.png| 700px]]
 +
 +
 +
{| class="wikitable" style="text-align: center;
 +
! Sequential
 +
! Parallel
 +
|-
 +
| [[File:PDR_PODM_Time_Break_Down_15_d3.png| 700px]]
 +
| [[File:PDR PODM Time Break Down 15 d3 par int2ptr.png| 700px]]
 +
|}
 +
 +
</div>
 +
 +
=== 15 MPI ranks depth: 4 ===
 +
<div class="mw-collapsible mw-collapsed">
 +
Total time: 569.7
 +
 +
Total tasks: 8761
 +
 +
[[File:PDR PODM Histogram Time 15 par int2ptr.png| 700px]]
 +
[[File:PDR PODM Histogram Tasks 15 par int2ptr.png| 700px]]
 +
 +
 +
{| class="wikitable" style="text-align: center;
 +
! Sequential
 +
! Parallel
 +
|-
 +
| [[File:PDR_PODM_Time_Break_Down_15.png| 700px]]
 +
| [[File:PDR PODM Time Break Down 15 par int2ptr.png| 700px]]
 +
|}
 +
 +
</div>
 +
 +
=== 40 MPI ranks depth: 4 ===
 +
<div class="mw-collapsible mw-collapsed">
 +
Total time: 326.5
 +
 +
Total tasks: 11201
 +
 +
[[File:PDR PODM Histogram Time 40 par int2ptr.png| 700px]]
 +
[[File:PDR PODM Histogram Tasks 40 par int2ptr.png| 700px]]
 +
 +
 +
{| class="wikitable" style="text-align: center;
 +
! Sequential
 +
! Parallel
 +
|-
 +
| [[File:PDR_PODM_Time_Break_Down_40.png| 700px]]
 +
| [[File:PDR PODM Time Break Down 40 par int2ptr.png| 700px]]
 +
|}
 +
 +
</div>
 +
 +
=== 160 MPI ranks 10 cores depth: 4 ===
 +
<div class="mw-collapsible mw-collapsed">
 +
Total time: 264.3
 +
 +
Total tasks: 12826
 +
 +
[[File:PDR PODM Histogram Time 160 10 par int2ptr.png| 700px]]
 +
[[File:PDR PODM Histogram Tasks 160 10 par int2ptr.png| 700px]]
 +
 +
 +
{| class="wikitable" style="text-align: center;
 +
! Sequential
 +
! Parallel
 +
|-
 +
| [[File:PDR_PODM_Time_Break_Down_160_10.png| 700px]]
 +
| [[File:PDR PODM Time Break Down 160 10 par int2ptr.png| 700px]]
 +
|}
 +
 +
</div>
 +
 +
== After Parallel int to pointer and leaf distribution ==
 +
=== 15 MPI ranks depth: 4 ===
 +
<div class="mw-collapsible mw-collapsed">
 +
Total time: 452.3
 +
 +
Total tasks: 8813
 +
 +
[[File:PDR PODM Histogram Time 15 par int2ptr leaf dist bad elements.png| 700px]]
 +
[[File:PDR PODM Histogram Tasks 15 par int2ptr leaf dist bad elements.png| 700px]]
 +
 +
 +
{| class="wikitable" style="text-align: center;
 +
! Sequential
 +
! Parallel(int2ptr)
 +
! Parallel(leafDist,BadEl)
 +
|-
 +
| [[File:PDR_PODM_Time_Break_Down_15.png| 500px]]
 +
| [[File:PDR PODM Time Break Down 15 par int2ptr.png| 500px]]
 +
| [[File:PDR PODM Time Break Down 15 par int2ptr leaf dist bad elements.png| 500px]]
 +
|}
 +
 +
</div>
 +
 +
=== 40 MPI ranks depth: 4 ===
 +
<div class="mw-collapsible mw-collapsed">
 +
Total time: 271.9
 +
 +
Total tasks: 11455
 +
 +
[[File:PDR PODM Histogram Time 40 par int2ptr leaf dist bad elements.png| 700px]]
 +
[[File:PDR PODM Histogram Tasks 40 par int2ptr leaf dist bad elements.png| 700px]]
 +
 +
 +
{| class="wikitable" style="text-align: center;
 +
! Sequential
 +
! Parallel(int2ptr)
 +
! Parallel(leafDist,BadEl)
 +
|-
 +
| [[File:PDR_PODM_Time_Break_Down_40.png| 500px]]
 +
| [[File:PDR PODM Time Break Down 40 par int2ptr.png| 500px]]
 +
| [[File:PDR PODM Time Break Down 40 par int2ptr leaf dist bad elements.png| 500px]]
 +
|}
 +
 +
</div>
 +
 +
=== 160 MPI ranks 10 cores depth: 4 ===
 +
<div class="mw-collapsible mw-collapsed">
 +
Total time: 218.3
 +
 +
Total tasks: 12517
 +
 +
[[File:PDR PODM Histogram Time 160 10 par int2ptr leaf dist bad elements.png| 700px]]
 +
[[File:PDR PODM Histrogram Tasks 160 10 par int2ptr leaf dist bad elements.png| 700px]]
 +
 +
{| class="wikitable" style="text-align: center;
 +
! Sequential
 +
! Parallel(int2ptr)
 +
! Parallel(leafDist,BadEl)
 +
|-
 +
| [[File:PDR PODM Time Break Down 160 10.png| 500px]]
 +
| [[File:PDR PODM Time Break Down 160 10 par int2ptr.png| 500px]]
 +
| [[File:PDR PODM Time Break Down 160 10 par int2ptr leaf dist bad elements.png| 500px]]
 +
|}
 +
</div>
 +
 +
== After Parallel int to pointer, leaf distribution and extra comm thread ==
 +
=== 15 MPI ranks depth: 3 ===
 +
<div class="mw-collapsible mw-collapsed">
 +
 +
Total time: 1144.7
 +
 +
Total tasks: 1830
 +
 +
[[File:PDR PODM Histogram Time 15 d3 par int2ptr leaf dist bad elements comm thread.png| 700px]]
 +
[[File:PDR PODM Histrogram Tasks 15 d3 par int2ptr leaf dist bad elements comm thread.png| 700px]]
 +
 +
 +
{| class="wikitable" style="text-align: center;
 +
! Sequential
 +
! Parallel(best)
 +
! Parallel(best+comm_thread)
 +
|-
 +
| [[File:PDR_PODM_Time_Break_Down_15_d3.png| 500px]]
 +
| [[File:PDR PODM Time Break Down 15 d3 par int2ptr leaf dist bad elements.png| 500px]]
 +
| [[File:PDR PODM Time Break Down 15 d3 par int2ptr leaf dist bad elements comm thread.png| 500px]]
 +
 +
|}
 +
 +
</div>
 +
 +
=== 15 MPI ranks depth: 4 ===
 +
<div class="mw-collapsible mw-collapsed">
 +
 +
Total time: 354.6
 +
 +
Total tasks: 8892
 +
 +
[[File:PDR PODM Histogram Time 15 par int2ptr leaf dist bad elements comm thread.png| 700px]]
 +
[[File:PDR PODM Histrogram Tasks 15 par int2ptr leaf dist bad elements comm thread.png| 700px]]
 +
 +
 +
{| class="wikitable" style="text-align: center;
 +
! Sequential
 +
! Parallel(best)
 +
! Parallel(best+comm_thread)
 +
|-
 +
| [[File:PDR_PODM_Time_Break_Down_15.png| 500px]]
 +
| [[File:PDR PODM Time Break Down 15 par int2ptr leaf dist bad elements.png| 500px]]
 +
| [[File:PDR PODM Time Break Down 15 par int2ptr leaf dist bad elements comm thread.png| 500px]]
 +
 +
|}
 +
 +
</div>
 +
 +
=== 40 MPI ranks depth: 4 ===
 +
<div class="mw-collapsible mw-collapsed">
 +
 +
Total time: 208.3
 +
 +
Total tasks: 11468
 +
 +
 +
[[File:PDR PODM Histogram Time 40 par int2ptr leaf dist bad elements comm thread.png| 700px]]
 +
[[File:PDR PODM Histrogram Tasks 40 par int2ptr leaf dist bad elements comm thread.png| 700px]]
 +
 +
 +
{| class="wikitable" style="text-align: center;
 +
! Sequential
 +
! Parallel(best)
 +
! Parallel(best+comm_thread)
 +
|-
 +
| [[File:PDR_PODM_Time_Break_Down_40.png| 500px]]
 +
| [[File:PDR PODM Time Break Down 40 par int2ptr leaf dist bad elements.png| 500px]]
 +
| [[File:PDR PODM Time Break Down 40 par int2ptr leaf dist bad elements comm thread.png| 500px]]
 +
 +
|}
 +
 +
</div>
 +
 +
=== 160 MPI ranks depth: 4 ===
 +
<div class="mw-collapsible mw-collapsed">
 +
 +
Total time: 202.2
 +
 +
Total tasks: 12715
 +
 +
 +
[[File:PDR PODM Histogram Time 160 10 par int2ptr leaf dist bad elements comm thread.png| 700px]]
 +
[[File:PDR PODM Histrogram Tasks 160 10 par int2ptr leaf dist bad elements comm thread.png| 700px]]
 +
 +
 +
{| class="wikitable" style="text-align: center;
 +
! Sequential
 +
! Parallel(best)
 +
! Parallel(best+comm_thread)
 +
|-
 +
| [[File:PDR_PODM_Time_Break_Down_160_10.png| 500px]]
 +
| [[File:PDR PODM Time Break Down 160 10 par int2ptr leaf dist bad elements.png| 500px]]
 +
| [[File:PDR PODM Time Break Down 160 10 par int2ptr leaf dist bad elements comm thread.png| 500px]]
 +
 +
|}
 +
 +
</div>
 +
 +
== Delta 0.3780 ==
 +
=== 15 MPI ranks depth: 4 ===
 +
<div class="mw-collapsible mw-collapsed">
 +
 +
 +
 +
[[File:PDR PODM Histogram Time small_delta 15.png| 700px]]
 +
[[File:PDR PODM Histogram Tasks small_delta 15.png| 700px]]
 +
[[File:PDR PODM Time Break Down small_delta 15.png| 700px]]
 +
 +
</div>

Latest revision as of 11:26, 6 May 2020

Issues

  • No reuse of leaves refined by worker nodes. The picture below shows the issue. Two neighbour leaves (0,1) each refined as the main leaf (0 top, 1 bottom) but not refined as a neighor.

PDR PODM Leaves not refined.png

  • Current algorithm uses neighbour traversal to distribute cells to octree leaving some cells out in some cases. Such a case can happen when a cell is part of an octree leaf based on its circumcenter but

it does not have any neighbour in the same leaf.

PDR PODM Cells not distributed.png

  • During unpacking the incident cell for each vertex is not set correctly. Specifically, in the case that the initial incident cell is not part of the working unit (Leaf + LVL.1 Neighbours) and thus is not local,

it is set to the infinite cell. This causes PODM to crash randomly for some cases.

  • Another issue comes from the way global IDs are updated for each cell's neighbors' IDs. The code that updates the cell's connectivity using global IDs takes the neighbor's pointer, retrieves its global ID and

updates the neighborID field. However, when the neighbour is part of another work unit's leaf and is not local this pointer is NULL. In this case the neighborID field is wrongly reset to the infinite cell ID, which as result, deletes the connectivity information forever.

  • The function that unpacks the required leaves before refinement does not discard duplicate vertices. Duplicate vertices will always be present since each leaf is packed and sent individually, and as a result,

neighbouring leaves will include the shared vertices. Because duplicate vertices are not handled, multiple vertex objects are created that are in fact the same point geometrically. Thus, two cells that share a common vertex could have pointers to two different vertex objects and, as a result, each cell views a different state about the same vertex.

Fixes

PDR Fix.png

Work Unit After Refinement.png


Interesting Findings

Delta 0.880

15 MPI ranks depth: 3


PDR PODM Histogram Time 15 d3.png PDR PODM Histogram Tasks 15 d3.png PDR PODM Time Break Down 15 d3.png

PDR PODM Parallelism.png PDR PODM Histogram 15.png

15 MPI ranks depth: 4


PDR PODM Histogram Time 15.png PDR PODM Histogram Tasks 15.png PDR PODM Time Break Down 15.png

40 MPI ranks / 40 cores depth: 4

Total Time: 824.29

Total Tasks: 11413

PDR PODM Histogram Time 40.png PDR PODM Histrogram Tasks 40.png PDR PODM Time Break Down 40.png

160 MPI ranks / 10 cores depth: 4

Total Time: 378.32

Total Tasks: 12652

PDR PODM Histogram Time 160 10.png PDR PODM Histrogram Tasks 160 10.png PDR PODM Time Break Down 160 10.png

After Parallel int to pointer

15 MPI ranks depth: 3


PDR PODM Histogram Time 15 d3 par int2ptr.png PDR PODM Histogram Tasks 15 d3 par int2ptr.png


Sequential Parallel
PDR PODM Time Break Down 15 d3.png PDR PODM Time Break Down 15 d3 par int2ptr.png

15 MPI ranks depth: 4

Total time: 569.7

Total tasks: 8761

PDR PODM Histogram Time 15 par int2ptr.png PDR PODM Histogram Tasks 15 par int2ptr.png


Sequential Parallel
PDR PODM Time Break Down 15.png PDR PODM Time Break Down 15 par int2ptr.png

40 MPI ranks depth: 4

Total time: 326.5

Total tasks: 11201

PDR PODM Histogram Time 40 par int2ptr.png PDR PODM Histogram Tasks 40 par int2ptr.png


Sequential Parallel
PDR PODM Time Break Down 40.png PDR PODM Time Break Down 40 par int2ptr.png

160 MPI ranks 10 cores depth: 4

Total time: 264.3

Total tasks: 12826

PDR PODM Histogram Time 160 10 par int2ptr.png PDR PODM Histogram Tasks 160 10 par int2ptr.png


Sequential Parallel
PDR PODM Time Break Down 160 10.png PDR PODM Time Break Down 160 10 par int2ptr.png

After Parallel int to pointer and leaf distribution

15 MPI ranks depth: 4

Total time: 452.3

Total tasks: 8813

PDR PODM Histogram Time 15 par int2ptr leaf dist bad elements.png PDR PODM Histogram Tasks 15 par int2ptr leaf dist bad elements.png


Sequential Parallel(int2ptr) Parallel(leafDist,BadEl)
PDR PODM Time Break Down 15.png PDR PODM Time Break Down 15 par int2ptr.png PDR PODM Time Break Down 15 par int2ptr leaf dist bad elements.png

40 MPI ranks depth: 4

Total time: 271.9

Total tasks: 11455

PDR PODM Histogram Time 40 par int2ptr leaf dist bad elements.png PDR PODM Histogram Tasks 40 par int2ptr leaf dist bad elements.png


Sequential Parallel(int2ptr) Parallel(leafDist,BadEl)
PDR PODM Time Break Down 40.png PDR PODM Time Break Down 40 par int2ptr.png PDR PODM Time Break Down 40 par int2ptr leaf dist bad elements.png

160 MPI ranks 10 cores depth: 4

Total time: 218.3

Total tasks: 12517

PDR PODM Histogram Time 160 10 par int2ptr leaf dist bad elements.png PDR PODM Histrogram Tasks 160 10 par int2ptr leaf dist bad elements.png

Sequential Parallel(int2ptr) Parallel(leafDist,BadEl)
PDR PODM Time Break Down 160 10.png PDR PODM Time Break Down 160 10 par int2ptr.png PDR PODM Time Break Down 160 10 par int2ptr leaf dist bad elements.png

After Parallel int to pointer, leaf distribution and extra comm thread

15 MPI ranks depth: 3

Total time: 1144.7

Total tasks: 1830

PDR PODM Histogram Time 15 d3 par int2ptr leaf dist bad elements comm thread.png PDR PODM Histrogram Tasks 15 d3 par int2ptr leaf dist bad elements comm thread.png


Sequential Parallel(best) Parallel(best+comm_thread)
PDR PODM Time Break Down 15 d3.png 500px PDR PODM Time Break Down 15 d3 par int2ptr leaf dist bad elements comm thread.png

15 MPI ranks depth: 4

Total time: 354.6

Total tasks: 8892

PDR PODM Histogram Time 15 par int2ptr leaf dist bad elements comm thread.png PDR PODM Histrogram Tasks 15 par int2ptr leaf dist bad elements comm thread.png


Sequential Parallel(best) Parallel(best+comm_thread)
PDR PODM Time Break Down 15.png PDR PODM Time Break Down 15 par int2ptr leaf dist bad elements.png PDR PODM Time Break Down 15 par int2ptr leaf dist bad elements comm thread.png

40 MPI ranks depth: 4

Total time: 208.3

Total tasks: 11468


PDR PODM Histogram Time 40 par int2ptr leaf dist bad elements comm thread.png PDR PODM Histrogram Tasks 40 par int2ptr leaf dist bad elements comm thread.png


Sequential Parallel(best) Parallel(best+comm_thread)
PDR PODM Time Break Down 40.png PDR PODM Time Break Down 40 par int2ptr leaf dist bad elements.png PDR PODM Time Break Down 40 par int2ptr leaf dist bad elements comm thread.png

160 MPI ranks depth: 4

Total time: 202.2

Total tasks: 12715


PDR PODM Histogram Time 160 10 par int2ptr leaf dist bad elements comm thread.png PDR PODM Histrogram Tasks 160 10 par int2ptr leaf dist bad elements comm thread.png


Sequential Parallel(best) Parallel(best+comm_thread)
PDR PODM Time Break Down 160 10.png PDR PODM Time Break Down 160 10 par int2ptr leaf dist bad elements.png PDR PODM Time Break Down 160 10 par int2ptr leaf dist bad elements comm thread.png

Delta 0.3780

15 MPI ranks depth: 4


PDR PODM Histogram Time small delta 15.png PDR PODM Histogram Tasks small delta 15.png PDR PODM Time Break Down small delta 15.png