MIT Department of Electrical Engineering & Computer Science

E E C S

Reducing Communication Overheads in Dynamic Multithreaded Computations

Vijay Karamcheti
University of Illinois at Urbana-Champaign

Thursday, March 20, 1997
3:15 PM (3:00 refreshments)
Room NE43-518
EECS Special Seminar

Abstract

Although high-level programming languages which provide a shared object space and fine-grained dynamic thread creation simplify the expression of irregular parallel applications, they have not achieved widespread use because of inefficient implementations on distributed memory machines. A major cause of this inefficiency is the communication overhead associated with managing the shared object space. The dynamic nature of such computations precludes a static partitioning of data objects to minimize communication, and produces communication patterns which are both spatially and temporally irregular. Such patterns are poorly matched to current-day communication architectures and conventional support for messaging and shared object spaces, resulting in implementations that are orders of magnitude slower than explicitly tuned approaches.

In this talk, I shall present three components of our approach for reducing communication overheads which spans the design of suitable communication architectures, robust runtime mechanisms and utilization of application semantics. First, I will present an analysis of the software overheads in messaging layers which makes a case for raising the level of network communication services (to provide in-order and reliable delivery). Second, I will introduce a new messaging technique, Pull Messaging, which delivers robust performance over a variety of traffic patterns utilizing hardware-supported remote memory operations to implement distributed message queuing with receiver-initiated data transfer. Finally, I will describe a shared object space mechanism, View Caching, which is tolerant to unresponsive processors and utilizes application information to construct coherence protocols that require reduced synchronization.

Pull Messaging and View Caching have been incorporated into the Illinois Concert System, an execution platform for dynamic multithreaded computations. Results for various irregular applications show that these mechanisms enable a high-level expression of programs to achieve performance comparable to explicitly tuned versions.

URL of this page: http://www-eecs.mit.edu/AY96-97/events/29.html
Created: Mar 20, 1997 | Modified: Jun 24, 1997
This announcement is from the MIT EECS 1996-97 archive. | Current events
To MIT EECS home page | Your comments and inquiries are welcome.