A Parallel Algorithm For Constructing Adjacency Graphs Of FEA Data

摘要

Finite Element Analysis (FEA) data sets are unstructured. Adjacency graphs are utilized to represent connectivities of FEA cells. Most visualization and data compression methods of FEA data make use of the connectivity information. In this paper, a parallel algorithm for constructing adjacency graphs of FEA data is presented. In our algorithm, the faces of FEA cells serve as intermediate data structures. They are generated in parallel and assigned to different groups by using hash function. These groups are mutually independent and can be processed simultaneously without data exchange. Then the groups are allocated to different processors to calculate edges of the adjacency graph. When a group is sent to a processor, the face records of this group are sorted by using radix sort. Edges of the adjacency graph are calculated by scanning the sorted group. After all groups are processed, all edges of the adjacency graph are figured out and the adjacency graph is constructed. In order to achieve a dynamic load balance, a master-slave computational model is adopted to schedule the tasks.