CS-TR-3207, UMIACS-TR-94-5

The Block Distributed Memory Model

by Joseph F. Já Já and Kwan Woo Ryu

(January 1994)

We introduce a computation model for developing and analyzing parallel algorithms on distributed memory machines. The model allows the design of algorithms using a single address space and does not assume any particular interconnection topology. We capture performance by incorporating a cost measure for interprocessor communication induced by remote memory accesses. The cost measure includes parameters reflecting memory latency, communication bandwidth, and spatial locality. Our model allows the initial placement of the input data and pipelined prefetching.

We use our model to develop parallel algorithms for various data rearrangement problems, load balancing, sorting, FFT, and matrix multiplication. We show that most of these algorithms achieve optimal or near optimal communication complexity while simultaneously guaranteeing an optimal speed-up in computational complexity.

In IEEE Transactions on Parallel and Distributed Systems, 8(7):830-840, 1996.

HTML Version or PostScript Version of this report.

For more infomation on any of the these topics, click on the hotlink.
Any queries, comments, or inquiries to:
   Joseph F. JáJá
   E-mail: joseph@umiacs.umd.edu

Office phone: (301)405-6722

FAX: (301)314-9658

Return to the Experimental Parallel Algorithmics page.