Mar 31, 2016 -Thu
Date: 1st April, 2016
Time: 11:00 a.m. to 12:00 p.m.
Venue: KICS Seminar Hall, UET Lahore
An important emerging problem domain in computational science and engineering is the development of multi-scale computational methods for complex problems that span multiple spatial and temporal scales. An attractive approach to solving these problems is recursive decomposition: the problem is broken up into a tree of loosely coupled sub-problems which can be solved independently at different scales and granularity and then coupled back together to obtain the desired solution.
Given a mesh decomposition, a particular problem can be solved in myriad ways by coupling the sub-problems together in different tree schedules. As we argue in this work, the space of possible schedules is vast, the performance gap between an arbitrary schedule and the best schedules is potentially quite large, and the likelihood that a domain scientist can find the best schedule to solve a problem on a particular machine is vanishingly small.
Additionally, a given undecomposed mesh can be decomposed into exponentially large number of decompositions. Effective mesh partitioning is essential for good performance of multi-scale computational methods. The computational cost associated with different scales can vary by multiple orders of magnitude. Hence the problem of finding an optimal partitioning of the mesh, choosing appropriate timescales for the partitions, and determining the number of partitions at each timescale is non-trivial. Existing partitioning tools, such as METIS, overlook the constraints posed by multi-scale methods, leading to sub-optimal partitions with a high performance penalty. To handle multi-scale problems appropriately, partitioners and schedulers need to be equipped with domain-specific knowledge that helps generate near optimal partitions and coupling schedules.
In this work, we present a semantics-aware optimization framework that exploits domain-specific knowledge to produce optimized mesh partitioning automatically, and generate efficient coupling schedules to solve these complex multi-scale computational methods using recursive decomposition. Our Framework adopts the inspector-executor paradigm, where the problem is inspected and a novel heuristic finds an effective implementation, i.e. decomposition and its scheduling, based on domain properties evaluated by a cost model. Experimental results show that the derived implementation achieves optimal sequential and parallel performance when executed by a parallel run-time system (Cilk). We demonstrate that our cost model is highly correlated with actual application runtime. Mesh decompositions produced by our approach perform as well as, if not better than, decompositions produced by state-of-the-art partitioners, like METIS, and even those that are manually constructed by domain scientists. The schedule generated by our domain-specific heuristic also outperforms alternate scheduling strategies, as well as over 99% of randomly-generated recursive decompositions sampled from the space of possible solutions.
We explore structural dynamics problem domain and show that by using our framework a good domain-specific cost model is all that is required for a broad range of computational applications in each domain without having to rewrite libraries for each domain.
Dr. Hasan is an Assistant Professor at KICS, UET, Lahore. He recently completed his Ph.D. in Computer Engineering from Purdue University under Fulbright Fellowship. His research focused on optimizing the performance of multi-scale computational methods by exploiting domain knowledge. The project was funded by the Department of Energy with the collaboration of Sandia National Labs. Hasan was a Graduate Technical Summer Intern at Sandia National Labs in 2015. Dr. Hasan worked as a Research Associate and Senior Research Associate at Al-Khawarizmi Institute of Computer Science, UET, Lahore, from 2006 and 2009 respectively, before pursuing his PhD abroad in 2010.