Keywords: parallel assembling, shared memory, graph theory, metal forming simulation.

Besides the solution of the linear equation system, assembling of the stiffness matrix is the most time consuming task in finite element codes. This is especially true if one uses elements with many integration points and complicated material laws needed in order to achieve sufficient accuracy. The rapidly decreasing prices for computer hardware make multi-processor machines (e.g. a dual Intel PC) affordable even for small companies. Thus we have developed an algorithm for stiffness matrix assembling on shared memory multi-processor architectures for our 3D bulk forming simulation code. The algorithm is easy to implement and nevertheless efficient.

The main problem with parallel assembling of the stiffness matrix is that different elements may contribute to the same entry in the matrix. Several approaches to avoid access conflicts to matrix entries have been proposed including the use of semaphores [1], special renumber and divide techniques [2] and row-wise assembling [3]. Our algorithm is based on graph theory: first we generate the dual graph of the finite element mesh. A recursive maximal independent set algorithm works on the dual graph and delivers indices of elements which do not share any nodes. These elements are being assembled by different processors and the element matrices can be directly added to the global stiffness matrix.

The algorithm is quite easy to implement. Furthermore it is independent of dimension, element type and model shape. We incorporated the algorithm into the non-linear FE program PressForm [4]. This code uses an Arbitrary Lagrangian-Eulerian descripton to simulate extrusion and other 3D bulk forming processes. The non-linear equilibrium equations are being solved by the direct iteration method, i.e. within one increment one has to assemble and solve several linear systems. Using real life examples of various size we discuss several performance aspects: a good parallel efficiency as well as the scalability of the construction of the dual graph and the maximal independent set algorithm.

1

H. Adeli and O. Kamal, Concurrent Analysis of Large Structures 1. Algorithms, Comput Struct, 42(3):413-424, 1992. doi:10.1016/0045-7949(92)90037-Z

2

L.S. Chien and C.T. Sun, Parallel Processing Techniques for Finite Element Analysis of Nonlinear Large Truss Structures, Comput Struct, 31(6):1023-1029, 1989. doi:10.1016/0045-7949(89)90287-3

3

M.N. De Rezede and J.B. de Paiva, A parallel algorithm for stiffness matrix assembling in a shared memory environment, Comput Struct, 76:593-602, 2000. doi:10.1016/S0045-7949(99)00181-9

4

L. Tong, FE Simulation of Bulk Forming Processes with a mixed Eulerian-Lagrangian Formulation, Ph.D. Thesis, Institut für Umformtechnik, ETH Zürich, 1995.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £85 +P&P)