β Scribed by Prakash Panangaden; Clark Verbrugge
No coin nor oath required. For personal study only.
A fundamental problem in parallel computing is partitioning data structures in such a way as to minimize communication between processes while keeping the loads balanced. The problem is particularly acute when the underlying data structures are irregular, pointer-based structures.
Here we present a methodology for partitioning a general class of dynamic data structures with guaranteed bounds on load-balancing and communication costs. Our method is based on a form of graph grammar, which speciΓΏes only families of graphs for which a "good" partitioning must exist. By modeling the construction and changes in a data structure using our formalism, one can quickly derive a good partitioning for a wide variety of common data structures. Moreover, expressing the structure updates in our grammars is generally a trivial operation with little overhead; this makes our approach particularly well-suited to dynamic situations.
π SIMILAR VOLUMES
A representation for a mesh based on the topological hierarchy of vertices, edges, faces and regions, is described. The representation is general and easily supports procedures ranging from mesh generation to adaptive analysis processes. Three implementations are given which concentrate on different