These data structures, developed in the context of the research carried out by the authors to create an unified computational framework which facilitates the implementation of the alternative formulations, offer an efficient and effective solution for the manipulation of the information associated with the problems being modelled. In this context two classes of data structures were proposed.

The first class collects the topological data structures which define the finite element mesh, allowing for an efficient determination of the relations between its components [2].

The second class, which is presented here, consists in a set of matrix handling data structures, which organise the intervening systems in such a way that the relations between the logical divisions of the solution and the corresponding processor are efficiently established.

The characteristics of the non-conventional formulations imply that, when a domain decomposition is used to split up the data for distributed computation, the variables associated with shared edges are shared between processors, while for conventional formulations this happens to shared nodes. To handle this variety of perspectives about similar problems two data structures were defined, the Part and the Block, which allow to organise the structural variables and the associated matrix.

This is achieved by considering the vectors involved as "vectors of vectors", divided into components, called Parts. In a distributed environment the solution vector components are reordered using a criterion based on the sharing of data.

For each subdomain one Part holds the vectors associated with the internal variables, while the variables shared with each adjacent subdomain are held in different Parts.

Global computations involve the interface variables, implying data exchange between the corresponding shared Parts. For this reason information defining the locality of data is needed at Part level. This is controlled using fields (*SubDomains, NSubDomains and number) which indicate whether the part is shared or not and which subdomains share that Part.

The approach used for the design of the Part assumes that a direct relation between each topological entity and the corresponding Part can always be established. This mapping information is associated with each topological entity (Loop, Edge or Node) using a pointer to the Part. This pointer is used when the mesh entity generates structural variables or is zero if the associated solution vector is empty.

The intervening submatrices in the governing system can be indexed by the corresponding Parts, i.e., the Parts can be used as a coordinate system to access the submatrices, termed Blocks, which are designed to store the matrix entries and to describe the behaviour of the corresponding Parts.

The matrix vector products are performed at sub-domain level, multiplying each Block by the corresponding column Part and adding the result to the row Part. After these calculations have been performed the result obtained in each shared Part is sent to the neighbour(s), while expecting to receive as many sets of values as the number of neighbours. The result of the matrix vector product is obtained by adding all these values to the local vector. To update the global vector, the local product is sent to each "other shared part" of the neighbour processors. When data is received from any processor its origin is determined and the local values are updated with the terms received, using a saxpy like routine.

The parallel performance obtained shows that on a homogeneous, network based, parallel virtual machine, for applications with a reasonable computation/communication ratio, the speedup and efficiency obtained are promising.

1

J.A.T. Freitas, J.P.M. Almeida, and E.M.B.R. Pereira. "Non-conventional formulations for the finite element method", Computational Mechanics, 23(5-6), 488-501, 1999. doi:10.1007/s004660050428

2

I. Cismasiu and J.P. Moitinho de Almeida. "The use of topological data-structures in the distributed solution of non-conventional finite element formulations", Computers and Structures, 2004. (accepted for publication). doi:10.1016/j.compstruc.2004.03.036

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 £95 +P&P)