Concurrency and Computation: Practice and Experience

Special Issue Paper

Parallel implementation and performance analysis of a linear octree finite element mesh generation scheme

Corresponding Author

Jose J. Camata

High Performance Computing Center, COPPE, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil

Correspondence to: Jose J. Camata, Department of Civil Engineering, Center for Parallel Computing, COPPE/Federal University of Rio de Janeiro, P.O. Box 68506, Rio de Janeiro, RJ, 21945, Brazil.

E-mail: [email protected]

Search for more papers by this author

Alvaro L. G. A. Coutinho,

Alvaro L. G. A. Coutinho

High Performance Computing Center, COPPE, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil

Search for more papers by this author

Jose J. Camata,

Corresponding Author

Jose J. Camata

High Performance Computing Center, COPPE, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil

Correspondence to: Jose J. Camata, Department of Civil Engineering, Center for Parallel Computing, COPPE/Federal University of Rio de Janeiro, P.O. Box 68506, Rio de Janeiro, RJ, 21945, Brazil.

E-mail: [email protected]

Search for more papers by this author

Alvaro L. G. A. Coutinho,

Alvaro L. G. A. Coutinho

High Performance Computing Center, COPPE, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil

Search for more papers by this author

First published: 08 July 2012

https://doi.org/10.1002/cpe.2869

Citations: 7

Share a link

Email
Wechat
Bluesky

SUMMARY

We show a parallel implementation and performance analysis of a linear octree-based mesh generation scheme designed to create reasonable-quality, geometry-adapted unstructured hexahedral meshes automatically from triangulated surface models. We present algorithms for the construction, 2:1 balancing and meshing large linear octrees on supercomputers. Our scheme uses efficient computer graphics algorithms for surface detection, allowing us to represent complex geometries. An isogranular analysis demonstrates good scalability. Our implementation is able to execute the 2:1 balancing operations over 3.4 billion octants in less than 10 s per 1.6 million octants per CPU core. Copyright © 2012 John Wiley & Sons, Ltd.

REFERENCES

1 George P. L. Automatic Mesh Generation: Applications to Finite Element Methods. John Wiley & Sons, Inc.: New York, NY, USA, 1992.
Google Scholar
2 Carey G. Computational Grids: Generation, Adaptation and Solution Strategies. Taylor and Francis: Washington, DC, 1997.
Google Scholar
3 Dongarra J, Foster I, Fox G, Gropp W, Kennedy K, Torczon L, White A. Sourcebook of Parallel Computing. Morgan Kaufmann Publishers Inc.: San Francisco, CA, USA, 2003.
Google Scholar
4 International Meshing Roundtable. (Available from: http://www.imr.sandia.gov/. accessed on Februery 16, 2011).
Google Scholar
5 Verhoeven N, Weatherill N, Morgan K, Ecer A, Periaux J, Satdfuka N, Taylor S. Dynamic load balancing in a 2D parallel Delaunay mesh generator. In Parallel Computational Fluid Dynamics 1995. North-Holland: Amsterdam, 1996; 641–648.
10.1016/B978-044482322-9/50133-X
Web of Science® Google Scholar
6 Chrisochoides N, Nave D. Simultaneous mesh generation and partitioning for Delaunay meshes. Mathematics and Computers in Simulation Dec 2000; 54: 321–339. DOI: 10.1016/S0378-4754(00)00192-0. ACM ID: 364639.
10.1016/S0378‐4754(00)00192‐0
Web of Science® Google Scholar
7 Topping BHV, Cheng B. Parallel and distributed adaptive quadrilateral mesh generation. Computers & Structures Oct 1999; 73(1-5): 519–536.
10.1016/S0045-7949(98)00254-5
Web of Science® Google Scholar
8 Lämmer L, Burghardt M. Parallel generation of triangular and quadrilateral meshes. Advances in Engineering Software Dec 2000; 31(12): 929–936.
10.1016/S0965-9978(00)00068-5
Web of Science® Google Scholar
9 Löhner R, Camberos J, Merriam M. Parallel unstructured grid generation. Computer Methods in Applied Mechanics and Engineering 1992; 95(3): 343–357.
10.1016/0045-7825(92)90192-M
Web of Science® Google Scholar
10 Muthukrishnan SN, Shiakolos PS, Nambiar RV, Lawrence KL. Simple algorithm for adaptative refinement of three-dimensional nite element tetrahedral meshes. AIAA Journal 1995; 33: 928–932.
10.2514/3.12386
Web of Science® Google Scholar
11 Samet H. Applications of Spatial Data Structures: Computer Graphics, Image Processing and Gis. Addison-Wesley Pub (Sd): Reading, MA, 1989.
Google Scholar
12 Sundar H, Sampath RS, Adavani SS, Davatzikos C, Biros G. 2007. Low-constant parallel algorithms for finite element simulations using linear octrees. In Proceedings of the 2007 ACM/IEEE Conference on Supercomputing, SC '07. ACM: New York, NY, USA, 2007; 25:1–25:12.
10.1145/1362622.1362656
Google Scholar
13 Tu T, O'Hallaron DR, Ghattas O. 2005. Scalable parallel octree meshing for terascale applications. In Proceedings of the 2005 ACM/IEEE Conference on Supercomputing, SC '05. IEEE Computer Society: Washington, DC, USA, 2005.
Google Scholar
14 Burstedde C, Wilcox LC, Ghattas O. p4est: scalable algorithms for parallel adaptive mesh refinement on forests of octrees. SIAM Journal on Scientific Computing 2011; 33(3): 1103–1133, DOI: 10.1137/100791634.
10.1137/100791634
Web of Science® Google Scholar
15 Camata JJ, Coutinho ALGA. Parallel linear octree meshing with immersed surfaces. In Proceedings of the 2010 22nd International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD '10. IEEE Computer Society: Washington, DC, USA, 2010; 151–158.
10.1109/SBAC-PAD.2010.26
Google Scholar
16 Morton. A computer oriented geodetic data base and a new technique in file sequencing. Technical Report Ottawa, Ontario, Canada, IBM Ltd., 1966.
Google Scholar
17 Aluru S, Sevilgen F. Parallel domain decomposition and load balancing using space-filling curves. In HIPC '97 Proceedings of the Fourth International Conference on High-Performance Computing. IEEE Computer Society: Washington, DC, 1997; 230–235.
10.1109/HIPC.1997.634498
Web of Science® Google Scholar
18 Ericson C. Real-Time Collision Detection. Morgan Kaufmann: San Francisco, CA, 2005.
Google Scholar
19 O'Rourke J. Computational Geometry in C, 2 edn. Vol. volume. Cambridge University Press: Cambridge, UK, 1998.
10.1017/CBO9780511804120
Google Scholar
20 Elias R, Camata J, Aveleda A, Coutinho A. Evaluation of message passing communication patterns in finite element solution of coupled problems. Lecture Notes in Computer Science 2011; 6449: 306–313. DOI: 10.1007/978-3-642-19328-6_29.
10.1007/978‐3‐642‐19328‐6_29
Web of Science® Google Scholar
21 MVAPICH, 2011. (Available from: http://mvapich.cse.ohio-state.edu/ accessed on 05-25-2011).
Google Scholar
22 MPI Forum, 2011. (Available from: www.mpi-forum.org/ accessed on 05-25-2011).
Google Scholar
23 IPM, 2011. (Available from: http://ipm-hpc.sourceforge.net/ accessed on 05-29-2011).
Google Scholar
24 Tendulkar S, Beall M, Shephard MS, Jansen K. Parallel mesh generation and adaptation for CAD geometries. Technical Report SCOREC Report 2011-2, Scientific Computation Research Center, Rensselaer Polytechnic Institute, 2011.
Google Scholar

Citing Literature

Volume25, Issue6

Special Issue:Latest Trends in Computer Architectures and Parallel and Distributed Technologies

25 April 2013

Pages 826-842

Parallel implementation and performance analysis of a linear octree finite element mesh generation scheme

SUMMARY

REFERENCES

Citing Literature

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

Parallel implementation and performance analysis of a linear octree finite element mesh generation scheme

SUMMARY

REFERENCES

Citing Literature

References

Related

Information