This presentation is OPEN to the public.
UPCRC Research Seminar
Case Studies in Asynchronous, Message-Driven Shared-Memory Programming
by Pritish Jetley, Illinois Computer Science
Thursday, February 24 at 2PM (Central Time)
2405 Siebel Center for Computer Science
Live Stream: http://media.cs.illinois.edu/live/UPCRClive.asx
Live Chat: http://www.upcrc.illinois.edu/chat/
Will be activated at day/time of seminar.
Abstract: In order to exploit the parallelism inherent in tree-based shared memory computations, one must contend with several confounding factors. First, a programming model must provide the right abstraction of a task, so that the parallelism inherent in the problem may be managed dynamically. Second, the irregular nature of parallelism in such programs often necessitates the use of mutual exclusion devices. Third, non-uniformities in the problem domain manifest themselves as load imbalance in the parallel program, which in turn degrades performance.
In this talk, we tackle these issues through an object-based, message-driven approach to the programming of irregular, shared memory programs. We base our approach on the Charm++ programming language and runtime system, in which programmers express computations in terms of communicating objects. The defining features of this approach are:
1. Overdecomposition of problems into medium-grained tasks, which engenders data locality;
2. Implicit synchronization between objects, which is realized through the exchange of messages;
3. Asynchrony of communication, which allows communication latency to be overlapped with useful computation;
4. Automatic scheduling of dynamically generated tasks, which removes imbalance of load;
5. Prioritization of tasks, which allows greater control over the amount of memory used.
We outline the productivity and performance benefits of this paradigm in the context of two tree-based applications, namely, N-body computations using the Barnes-Hut method, and the construction of SAH-balanced kd-trees for efficient rendering of three-dimensional scenes.
Bio: Pritish Jetley is a doctoral student of computer science at the University of Illinois, Urbana-Champaign. He works in the Parallel Programming Laboratory, which is directed by his advisor, Prof. Laxmikant V. Kale. His research interests include parallel programming languages, computational cosmology and high performance communication. He is currently developing a multi-paradigm approach to productive parallel programming, which involves a family of incomplete, interoperable, domain-specific languages. He obtained a B.Tech. degree from the Indian Institute of Technology, Guwahati in 2006.