::: Goal

Problems in scientific computing are in general large, irregular and computationally intensive. Load imbalance is one of the main performance degradation factors of scientific applications running in heterogeneous environments often used in cluster and grid computing. Our research objective is to improve performance of parallel algorithms for applications in science and engineering, such that simulations of physical phenomena they represent could derive tractable and accurate predictions. Our specific goal is to advance the state-of-the-art in dynamic scheduling and load balancing algorithms for improving the scalability and performance of parallel applications in scientific computing. Therefore, our research efforts are directed towards the analysis and development of these algorithms on theoretical and experimental bases.

Our research activities are focused towards the development of algorithms, techniques and tools that address load imbalance factors generated by the unpredictable behavior of simulations, such as irregularities rising from problem characteristics, algorithms, and software environments. The development of these algorithms is essential, especially in applications characterized by highly irregular behavior, or by a continuous and dynamic change, where none of the existing techniques accommodate their unpredictable behavior. In addition to developing the theoretical foundations of dynamic scheduling and load balancing algorithms, our research group develops tools for the integration of these algorithms into applications, as well as into run-time environments. Our research activities are supported by grants from the National Science Foundation (NSF-CAREER, ITR, and others).

Another important goal of our work consists in performance analysis, evaluation and prediction (from analytical and experimental perspectives) of parallel applications running in heterogeneous environments using these novel techniques.

::: Methodology

Since loops are an important source of parallelism in scientific computing, the development of our dynamic scheduling and load balancing algorithms are based on theoretical advances in loop scheduling. The techniques developed are based on probabilistic analyses. Over time, we developed a number of adaptive algorithms which could address a wide range of irregularities. From a historical perspective, the algorithms developed in recent years have a higher degree of generality than the ones developed earlier (and therefore, they are robust), since some of the theoretical constraints used in modeling are progressively relaxed. The theoretical results of this work are significant, especially to the research community interested in scalability analysis of parallel applications.

Another component of our group's research work is the development of application programming interfaces, libraries, and tools, to facilitate the integration of these newly developed techniques into parallel applications running in heterogeneous environments. Furthermore, the dynamic scheduling techniques are integrated into runtime systems to ensure load balancing at both task and data parallel levels.

A research initiative of our group lies in the introduction of optimization through machine learning for the use of our dynamic scheduling algorithms into parallel applications. Therefore, a faster assimilation of our research work would be possible in the emerging technology of autonomic computing.