RENUMBERING UNSTRUCTURED GRIDS TO IMPROVE THE PERFORMANCE OF CODES ONHIERARCHICAL MEMORY MACHINES

The performance of unstructured grid codes on workstations and distrib uted memory parallel computers is substantially affected by the effici ency of the memory hierarchy. This efficiency essentially depends on t he order of computation and numbering of the grid. Most grid generator s do not take into account the effect of the memory hierarchy when pro ducing grids so application programmers must renumber grids to improve the performance of their codes. To design a good renumbering scheme a detailed runtime analysis of the data movement in an application code is needed. Thus, a memory hierarchy simulator has been developed to a nalyse the effect of existing renumbering schemes such as bandwidth re duction, the Greedy method, colouring, random numbering and the origin al numbering produced by the grid generator. The renumbering is applie d to either vertices, edges, faces or cells and two algorithms are pro posed to consistently renumber the other entities used in the solver. The simulated and actual timings show that bandwidth reduction and Gre edy methods give the best performance on IBM RS/6000, SGI Indy, SGI In digo and SGI Power Challenge machines for three-dimensional Poissons's , Maxwell's and the Euler equations solvers. The improvement in perfor mance is over a factor of two for applications with large grids and a high ratio of memory-accesses to computation. This factor is even high er for memory hierarchies with small caches. (C) 1997 Elsevier Science Limited.