NDLI: Improved cache utilization and preconditioner efficiency through use of a space-filling curve mesh element- and vertex-reordering technique

Content Provider	Springer Nature Link
Author	Sastry, Shankar P. Kultursay, Emre Shontz, Suzanne M. Kandemir, Mahmut T.
Copyright Year	2014
Abstract	Solving partial differential equations using finite element (FE) methods for unstructured meshes that contain billions of elements is computationally a very challenging task. While parallel implementations can deliver a solution in a reasonable amount of time, they suffer from low cache utilization due to unstructured data access patterns. In this work, we reorder the way the mesh vertices and elements are stored in memory using Hilbert space-filling curves to improve cache utilization in FE methods for unstructured meshes. This reordering technique enumerates the mesh elements such that parallel threads access shared vertices at different time intervals, reducing the time wasted waiting to acquire locks guarding atomic regions. Further, when the linear system resulting from the FE analysis is solved using the preconditioned conjugate gradient method, the performance of the block-Jacobi preconditioner also improves, as more nonzeros are present near the stiffness matrix diagonal. Our results show that our reordering reduces the L1 and L2 cache miss-rates in the stiffness matrix assembly step by about 50 and 10 %, respectively, on a single-core processor. We also reduce the number of iterations required to solve the linear system by about 5 %. Overall, our reordering reduces the time to assemble the stiffness matrix and to solve the linear system on a 4-socket, 48-core multi-processor by about 20 %.
Starting Page	535
Ending Page	547
Page Count	13
File Format	PDF
ISSN	01770667
Journal	Engineering with Computers
Volume Number	30
Issue Number	4
e-ISSN	14355663
Language	English
Publisher	Springer London
Publisher Date	2014-05-11
Publisher Place	London
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Parallel mesh warping Vertex reordering Element reordering Hilbert space-filling curves Cache utilization Preconditioner efficiency Computer-Aided Engineering (CAD, CAE) and Design Math. Applications in Chemistry Systems Theory, Control Calculus of Variations and Optimal Control; Optimization Mechanics ApplicationMathematics/Computational Methods of Engineering
Content Type	Text
Resource Type	Article
Subject	Engineering Computer Science Applications Modeling and Simulation Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The geometric element transformation method for mixed mesh smoothing

Topological improvement procedures for quadrilateral finite element meshes

An algorithm for filling complex holes in reverse engineering

Parallel mesh adaptation for high-order finite element methods with curved element geometry

Using mesh-geometry relationships to transfer analysis models between CAE tools

Moving curved mesh adaptation for higher-order finite element simulations

Local refinement of three-dimensional finite element meshes

Surface remeshing with robust high-order reconstruction

Reconstructing high-order surfaces for meshing

Improved cache utilization and preconditioner efficiency through use of a space-filling curve mesh element- and vertex-reordering technique

Similar Documents

The geometric element transformation method for mixed mesh smoothing

Topological improvement procedures for quadrilateral finite element meshes

An algorithm for filling complex holes in reverse engineering

Parallel mesh adaptation for high-order finite element methods with curved element geometry

Using mesh-geometry relationships to transfer analysis models between CAE tools

Moving curved mesh adaptation for higher-order finite element simulations

Local refinement of three-dimensional finite element meshes

Surface remeshing with robust high-order reconstruction

Reconstructing high-order surfaces for meshing

Improved cache utilization and preconditioner efficiency through use of a space-filling curve mesh element- and vertex-reordering technique