Proceedings of the 5th Annual MIT Student Workshop on Scalable Computing

Edited by Frederic T. Chong

August 8, 1995

(Multibody simulation image courtesy of Ruaidhri O'Connor)

The 5th Annual MIT Student Workshop on Scalable Computing

General Chair

Yonald Chery

Program Chair

Frederic Chong

Invited Speakers and Publicity Chair

Jon Kleinberg

Faculty Advisor

Alan Edelman

Program Committee

  • Michael Bolotski, Abacus Group
  • Frederic Chong, Alewife Group
  • Derek Chiou, Computation Structures Group
  • Jon Kleinberg, Theory of Computation Group
  • Kathleen Knobe, Concurrent VLSI Architectures Group
  • Ulana Legedza, Large-scale Parallel Software Group
  • Andrew Myers, Programming Methodology Group
  • Joel Phillips, Research Laboratory for Electonics
  • David Shoemaker, Numesh Group
  • Deborah Wallach, Parallel and Distributed Operating Systems Group
  • H. B. Weinberg, Theory of Computation Group
  • Administrative Assistance

    Irena Kveraga

    The papers in this volume were submitted to the 5th Annual MIT Student Workshop on Scalable Computing. Though this is the first year that the workshop has been organized entirely by students, it would not have been possible to get the workshop off the ground without the faith, encouragement, and ``pearls of wisdom'' offered by the workshop's founder Prof. Charles E. Leiserson. I thank him for all his help.

    The workshop would not have come into being were it not for the active leadership exercised by our Program Chair Fred Chong and Jon Kleinberg, who was our chair for both Invited Speakers and Publicity. When I approached Fred, he enthusiastically supported the idea and went all out recruiting members of the Program Committee. Likewise, Jon exercised zeal and creativity in handling all advertising and in his labors to arrange for invited speakers. Thank you Fred, Jon, and all the Program Committee members for a job well done.

    I would also like to also thank Prof. Alan Edelman and Al Vezza for their formative counsel as advisors to the organizing committee. Special thanks to Irena Kveraga for her support and patience with us as we got our act together.

    In the past, this workshop has been an excellent venue for more ``tenured'' students to impart their insights. It has also provided an opportunity for the more junior students to meet other researchers that share similar intellectual pursuits. It is my hope that this workshop will continue to grow and improve from this year forward as a student production serving to strengthen our research community.

    Yonald Chery, Conference Chair

    16 of the 58 abstracts in this volume, those marked with an asterisk were chosen for presentation by the program committee. The program committee consisted of students drawn from a cross-section of research groups involved in scalable computing.

    The committee tried to select quality abstracts which provide a good sampling of groups and research areas related to scalable computing. Preference was given to new topics or new faces to our community. Some preference was also given to authors not involved in the program committee. I would like to thank each and every member of the committee for their contributions to the workshop.

    Frederic T. Chong , Program Chair

  • Safe Functional Abstractions in a Polymorphic, Imperative Language*

    Shail Aditya.
  • Web File System: File-like Access to the Web

    Atul Adya, Joseph Bank, Jim Napier, Jordan Slott, and H.B. Weinberg.

    (Class project for 6.853 Computer Systems)
  • Finding Deadlocks in Cache-Coherent Distributed Shared Memory Machines

    Boon S. Ang and Derek Chiou
  • Addressing Partitioned Arrays in Distributed Memory Multiprocessors - the Software Virtual Memory Approach*

    Rajeev Barua.
  • A Representation and Query Structure to Approximate Mincuts of a Network

    Andras Benczur.
  • CHARISMA: A Smart Look at Parallel File-Access *

    Michael L. Best.
  • Cilk: An Efficient Multithreaded Runtime System

    Robert Blumofe.
  • Feedback-Directed Specialization of C

    Jeremy Brown
  • Communication Efficient Shared Memory

    Miguel Castro.
  • Embedded Dynamic Memories

    Derrick Chen.
  • Using GCC as an Efficient, Portable Back-End

    Derek Chiou
  • Remote Queues: Exposing Message Queues for Optimization and Atomicity

    Frederic T. Chong, Lok Liu, Shamik Sharma, and John Kubiatowicz.
  • Parallel Sparse Triangular Solution with Partitioned Inverses and Prescheduled DAGs

    Frederic T. Chong.
  • Specialization Theory

    André DeHon
  • AVM: Application-Level Virtual Memory *

    Dawson R. Engler and Sandeep K. Gupta.
  • Efficient, Safe, Application-Specific Message Processing*

    Dawson R. Engler and Deborah A. Wallach.
  • A First Generation DPGA Implementation

    Ian Eslick, Derrick Chen, Edward Tau, Jeremy Brown, Ethan Mirsky, and André DeHon
  • Instruction Scheduling on the M-Machine Multicomputer

    Marco Fillo, Stephen W. Keckler, Nicholas P. Carter, Andrew Chang, Yevgeny Gurevich, and Whay S. Lee.
  • Rediscovering the FFT

    Matteo Frigo.
  • Achieving Independence Efficiently and Securely*

    Visualization of the Parallel Jacobi Algorithm

    Peter Godman. (animated demo)

    (Class project for 18.337 Scientific Computing)
  • Improving the Practical Space and Time Efficiency of the Shortest-Paths Approach to Sum-of-Pairs Multiple Sequence Alignment

    Sandeep K. Gupta.
  • A Substitution Model for the Kernel of Scheme

    Grant Ho
  • Flexible User-Level Network Interface based on Embedded Processors

    James C. Hoe.
  • Selecting Better-Performing Alternative Code Using Run-Time Profiling Feedback

    Ping-Shun Huang <>
  • PVM Implementation of Uncertainty Analysis

    Jose L. Jimenez and Cheng Wang.

    (Class project for 18.337 Scientific Computing)
  • Rover: A Toolkit for Mobile Information Access*

    Anthony D. Joseph, Joshua A. Tauber, and Alan deLespinasse.
  • Direct Computation of Reduced-Order Models for Circuit Simulation of 3-D Interconnect Structures

    Mattan Kamon and L. Miguel Silveira.
  • NuMesh Video System Using Distributed Frame Buffers

    Frank Kim.
  • The Disjoint Paths Problem

    Parallel Solution of Burger's Equation in Two Dimensions by Joshua Koppelman, Tony Caola, and Ross Lippert.

    (Class project for 18.337 Scientific Computing)
  • Reducing Synchronization Overhead in Parallel Synchronization

    Ulana Legedza.
  • A Case Study of Shared Memory and Message Passing: The Triangle Puzzle

    Kevin Lew and Kirk Johnson.
  • The FUGU Scalable Workstation Prototype*

    Kenneth Mackenzie, Matthew Frank, Silvina Hanono, John Kubiatowicz, Victor Lee and Jon Michelson.
  • Collecting Cyclic Distributed Garbage*

    Umesh Maheshwari.
  • Whiteboards

    Umesh Maheshwari.
  • A New Communication-Efficient Distributed Fourier Transform Algorithm

    Peter McCorquodale and Sivan Toledo.
  • Parallelized Scatter/Gather Browse

    Greg McLaren.

    (Class project for 18.337 Scientific Computing)
  • C-to-C: A Type-checking Preprocessor for C Extension Languages

    Robert C. Miller.
  • MATRIX: Coarse-Grain Reconfigurable Computing*

    Ethan Mirsky and André DeHon
  • Quickstep: A Performance Monitoring and Debugging System for Alewife

    Sramana Mitra.
  • Portable Multibody Simulation Using MPI*

    Ruaidhri O'Connor.
  • Precorrected-FFT methods for Electromagnetic Analysis of Complex 3-D Interconnect and Packages

    Joel R. Phillips.
  • Dynamic Documents: Scalable Access to the WWW

    Thomas Pinckney, Joshua A. Tauber .
  • Path Splitting: a Technique for Improving Data Flow Analysis

    Massimiliano Poletto.
  • Parallel Algorithms for the Circuit Value Update Problem*

    Keith H. Randall.
  • Rational Clocking

    Luis F. G. Sarmenta.
  • Cell Loss Clustering Prevents Avalanches in ATM Networks

    Andrew Shaw.
  • Implementing I-structures at Cache Coherence Level*

    Xiaowei Shen and Boon S. Ang
  • Optimized Hardware Architecture and Communication Protocols for Static Routing*

    David Shoemaker.
  • Information Hierarchies

    Ellen Spertus.
  • Out-of-Core Krylov-Subspace Methods

    Sivan Toledo.
  • Parallel Monte Carlo Simulations of Temperature Programmed Desorption

    Rajesh Venkataramani.

    (Class project for 18.337 Scientific Computing)
  • A Reversible Computer Architecture*

    Carlin Vieri.
  • A Study of Multi-Grain Shared Memory Systems

    Donald Yeung.
  • Routing with Short Wires

    Lisa Zhang and Matthew Andrews.
  • Increasing Cross-Domain Call Batching Using Promises and Batched Control Structures*

    Quinton Zondervan.