![]() ![]() Sadayappan, OSU Chau-Wen Tseng, UMD Also, thanks to Ohio Supercomputer Center, European Center for Parallelism in Barcelona, and William Pugh 2ģ Motivating the Problem Suppose we have a large search space and a treestructured search.ġ UTS: An Unbalanced Tree Search Benchmark LCPCĢ Coauthors Stephen Olivier, UNC Jun Huan, UNC/Kansas Jinze Liu, UNC Jan Prins, UNC James Dinan, OSU P. Tree Search (UTS) benchmark over the current version are about 14 and 10 for similar scale runs, respectively. How could we do this in parallel? 3Ĥ Motivating the Problem Suppose we have a large search space and a treestructured search. How could we do this in parallel? Now suppose the tree is highly unbalanced. 4ĥ Meet UTS Unbalanced computation requiring continuous dynamic load balancing for high performance Exposes trade-offs between communication costs and granularity of load balance Fundamentally disadvantages systems with coarse-grained communication networks Challenges the expressibility and performance portability of parallel programming languages 5Ħ Benchmark Characteristics Implicit Generation Tree nodes generated on the fly Mimics systematic search Well-suited for parallel exploration Imbalance Large variation in subtree sizes Parameterization Can create trees of different depths and sizes 6ħ Outline Tree Generation Implementation Performance Analysis Conclusions and Future Work 7Ĩ Generation Strategy Each node consists of a 20B descriptor Implicit child creation using cryptographic hash (Parent Descriptor, Child Index) Hash Child Node Descriptor Number of children determined by sampling a probability distribution using the descriptor 8ĩ Generating Binomial Trees In a Binomial Tree, each node has 0 or m children A node has children with probability q 1 1 qm When qm < 1, expected size is As qm approaches 1, subtree size variation increases (Imbalance!) Expected subtree size rooted at each node is independent of its location in the tree How large a subtree at each?. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |