kumar@uunet.UU.NET (Vipin Kumar) (02/26/88)
The following reports are available:
Parallel Depth First Search on the Ring Architecture
by Vipin Kumar, V. Nageshwara Rao and K. Ramesh,
Department of Computer Sciences,
University of Texas at Austin, January 1988.
Abstract:
This paper presents the implementation and analysis of parallel
depth-first search on the ring architecture.
The effectiveness of the parallel formulation is strongly
influenced by the choice of work distribution scheme
that divides the work between different processors.
We found that a most commonly used work distribution scheme
gives very poor performance on large rings( > 32 processors).
We present a new work distribution scheme that is better than the
work distribution scheme used by other researchers, and gives good
performance even on large rings (128 processors).
We introduce the concept of iso-efficiency function
to characterize the effectiveness of different
work distribution schemes. The iso-efficiency function
has been found quite useful in characterizing the scalability of many
other parallel algorithms as well.
Concurrent Access of Priority Queues
by V.N. rao and Vipin Kumar,
Department of Computer Sciences,
University of Texas at Austin, January 1988.
Abstract:
The heap is an important data structure used as a priority queue
in a wide variety of parallel algorithms (e.g., multiprocessor scheduling,
branch-and-bound). In these algorithms, contention for
for the shared heap limits the obtainable speedup.
This paper presents an approach to allow concurrent insertions
and deletions on the heap. Our scheme has much smaller overhead
and gives a much better performance than a previously
reported scheme. The scheme also retains the strict priority ordering
of the serial access heap algorithms;
i.e., a delete operation returns the best key of all keys
that have been inserted or are being inserted at the time delete is started.
Our experimental results on the BBN Butterfly parallel processor
demonstrate that the use of concurrent-heap algorithms
in parallel branch-and-bound improves its performance substantially.
To get a copy, write or send mail to
US Mail: Dr. Vipin Kumar
Assistant Professor
Computer science Department
University of Texas at Austin
Austin, TX 78712
Arpanet: kumar@sally.utexas.edu
uucp: ....{harvard,ihnp4}!ut-sally!kumar