Load-Balancing and Task Mapping for Exascale Systems

In many areas of science and engineering, both problem and dataset sizes are increasing rapidly due to technological advances that enable generation and storage of such data. Many of the datasets generated are irregular, in the sense that no immediately observable or predictable pattern exists among data elements. Lack of such patterns makes it difficult to find simple, effective and efficient mechanisms to partition data for scalable parallel processing. Moreover, the hierarchy of the parallel processing systems becomes more complex with the increase in system sizes. Thus, scalable partitioning and mapping tasks to processors has become critical to application performance. In the literature, this problem is referred as the mapping problem.;Computational tasks in scientific computing are modeled by either using spatial information or connectivity based topological information. The mapping problem is usually solved with a two-phase approach; in the first phase, a load-balanced partitioning of the tasks is found, while in the second phase, each part is mapped to a physical processor. In this work, two-phase mapping problems are investigated. The load-balancing and task mapping problems are studied in the contexts of both spatial and connectivity-based models.;For the applications with spatial information, spatial partitioning is used for load-balancing. In this work, parallel spatial partitioning methods are investigated on distributed systems, and a parallel multi-jagged algorithm (MJ) is proposed. In contrast to the traditional recursive coordinate bisection algorithm (RCB), which recursively bisects subdomains, the proposed parallel algorithm does recursive multi-sections in each dimension, therefore it reduces the recursion depth with respect to RCB. Moreover, it implements wise algorithms to predict the cost of the data movements, and avoids data movements when the gain is predicted not to amortize the data movement cost. This reduces the data movements, and significantly improves the scalability of the algorithm compared to the efficient implementations of RCB. Once the load-balance is achieved, further optimizations are exploited with spatial task mapping. Using the proposed geometric partitioner MJ, a geometric mapping algorithm is proposed. The proposed mapping algorithm judiciously assigns the interdependent tasks to the nearby cores, and hence, lowers the distances messages travel and the network contention.;The spatial models have a major drawback as they do not provide an exact model for the actual communication requirements. This becomes problematic especially for the applications with irregular communication patterns. In such applications, the load distribution to the processors with minimized the inter-processor communication is achieved with connectivity-based models and partitioners adapting these models. In this work, a novel directed hypergraph model that allows to formulate multiple communication metrics is proposed. A multi-objective and k-way hypergraph partitioning algorithm that improves multiple communication metrics in a single phase is studied. The proposed model and algorithm are implemented under a software tool, UMPa. In order to improve the scalability, parallelization of hypergraph coarsening and matching methods on multicore architectures are examined. Moreover, since the matrices and hypergraphs are expected to be bigger and more complex in future, efficient compression and sparsification techniques are investigated to reduce processing time. Further optimizations for the communication overhead minimization are investigated by using graph models in task mapping problem for the applications with connectivity information. As the spatial models do not provide an exact model for the communication requirements of unstructured applications, graph mapping algorithms that accurately addresses various communication metrics are proposed and the effect of these communication metrics on the actual communication time is investigated.