@article {15038,
	title = {The block distributed memory model},
	journal = {Parallel and Distributed Systems, IEEE Transactions on},
	volume = {7},
	year = {1996},
	month = {1996/08//},
	pages = {830 - 840},
	abstract = {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. Ongoing experimental work in testing and evaluating these algorithms has thus far shown very promising results},
	keywords = {accesses;single, address, algorithms;performance, algorithms;performance;remote, allocation;sorting;, balancing;matrix, bandwidth;communication, communication;load, complexity;computation, complexity;computational, complexity;cost, complexity;distributed, distributed, evaluation;resource, FFT;block, Fourier, latency;parallel, locality;communication, machines;interconnection, measure;data, memory, model;communication, model;computational, multiplication;memory, multiplication;parallel, problems;distributed, rearrangement, space;sorting;spatial, systems;fast, topology;interprocessor, transforms;matrix},
	isbn = {1045-9219},
	doi = {10.1109/71.532114},
	author = {JaJa, Joseph F. and Ryu,Kwan Woo}
}
@conference {15016,
	title = {Practical parallel algorithms for dynamic data redistribution, median finding, and selection},
	booktitle = {Parallel Processing Symposium, 1996., Proceedings of IPPS {\textquoteright}96, The 10th International},
	year = {1996},
	month = {1996/04//},
	pages = {292 - 301},
	abstract = {A common statistical problem is that of finding the median element in a set of data. This paper presents a fast and portable parallel algorithm for finding the median given a set of elements distributed across a parallel machine. In fact, our algorithm solves the general selection problem that requires the determination of the element of rank i, for an arbitrarily given integer i. Practical algorithms needed by our selection algorithm for the dynamic redistribution of data are also discussed. Our general framework is a distributed memory programming model enhanced by a set of communication primitives. We use efficient techniques for distributing, coalescing, and load balancing data as well as efficient combinations of task and data parallelism. The algorithms have been coded in SPLIT-C and run on a variety of platforms, including the Thinking Machines CM-5, IBM SP-1 and SP-2, Gray Research T3D, Meiko Scientific CS-2, Intel Paragon, and workstation clusters. Our experimental results illustrate the scalability and efficiency of our algorithms across different platforms and improve upon all the related experimental results known to the authors},
	keywords = {algorithms;performance, algorithms;scalability;statistical, allocation;, balancing, clusters;distributed, CM-5;communication, CS-2;SPLIT-C;Thinking, data, data;median, evaluation;resource, finding;parallel, Gray, Machines, memory, model;dynamic, Paragon;Meiko, primitives;distributed, problem;workstation, Programming, redistribution;load, research, scientific, SP-1;Intel, systems;parallel, T3D;IBM},
	doi = {10.1109/IPPS.1996.508072},
	author = {Bader, D.A. and JaJa, Joseph F.}
}
@conference {15039,
	title = {The block distributed memory model for shared memory multiprocessors},
	booktitle = {Parallel Processing Symposium, 1994. Proceedings., Eighth International},
	year = {1994},
	month = {1994/04//},
	pages = {752 - 756},
	abstract = {Introduces 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},
	keywords = {accesses;shared, address, algebra;parallel, algorithms;performance, algorithms;performance;pipelined, allocation;shared, balancing;matrix, bandwidth;computation, block, Communication, communication;load, complexity;computational, complexity;cost, complexity;distributed, complexity;optimal, data, distributed, evaluation;resource, Fourier, latency;optimal, locality;communication, measure;data, memory, model;communication, model;computational, multiplication;memory, multiprocessors;single, placement;interprocessor, prefetching;remote, problems;fast, rearrangement, space;sorting;spatial, speedup;parallel, systems;fast, systems;sorting;, transforms;input, transforms;matrix},
	doi = {10.1109/IPPS.1994.288220},
	author = {JaJa, Joseph F. and Ryu,Kwan Woo}
}
