Compiler and run-time support for irregular computations
Lain, Antonio
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/20771
Description
Title
Compiler and run-time support for irregular computations
Author(s)
Lain, Antonio
Issue Date
1996
Doctoral Committee Chair(s)
Banerjee, Prithviraj
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
Abstract
There are many important applications in computational fluid dynamics, circuit simulation and structural analysis that can be more accurately modeled using iterations on unstructured grids. In these problems, regular compiler analysis for Massively Parallel Processors (MPP) with distributed address space fails because the communication can only be determined at run-time. However, in many of these applications the communication pattern repeats for every iteration. Therefore, equivalent optimizations to the regular case can be achieved with a combination of run-time support (RTS) and compiler analysis.
Moreover, many real applications have irregular access patterns with certain structure. This structure is needed to improve sequential performance, better exploiting the memory hierarchy. In many cases this structure is reflected in the array subscript expressions in the form of hybrid accesses, that is, affine combinations of array indirection and regular accesses. We will show that when we get advantage of this structure, we can dramatically reduce pre-processing overheads, both in terms of memory and time, and improve communication and single node performance.
In order to achieve these goals we need a combination of run-time and compiler support. Unfortunately, existing irregular run-time support cannot get advantage of regularity and therefore, our first requirement was to develop a new run-time support for irregular computations, that we called PILAR (Parallel Irregular Library with Application of Regularity). Our second requirement was to automate the task of exploiting regularity in irregular applications through compiler support. For this task we extended the PARADIGM compiler, developed at the University of Illinois, to handle irregular problems. Experimental results will validate the efficacy of our approach.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
