For parallel computing to become the vehicle of choice for a broad variety of computing problems, not just regular numeric ones, the expression and exploitation of irregular parallelism must be efficient. This research addresses the major challenge, programmability, by 1) supporting the expression of irregular parallelism with concurrent object-oriented programming languages and 2) supporting the exploitation of irregular parallelism with high performance routing networks and network interfaces. Concurrent object-oriented languages enable programmers to hide concurrency and distribution, allowing incremental parallelization and also confining the complexity arising from irregular parallelism to a small part of the program. However, efficient implementation requires aggressive locality and grain size optimizations in the underlying compiler and runtime system. This project is exploring aggressive type inference and dynamic data structure analysis techniques to enable such program optimizations. Type inference is used to discover program control flow, and dynamic data structure analysis approximates the program storage map. Runtime techniques are also being explored. These techniques are embodied in the publicly available Illinois Concert System. This system is being used to develop a number of parallel application programs.
