Title:  Scheduling of Structured and Unstructured Computation

Author: A. Gerasoulis, J. Jiao, T. Yang

Date:   April, 1994

Abstract:  Automatic scheduling has been shown to be practical for parallel
machines with a small number of processors.  However, the practicality of 
scheduling for scalable machines with a large number of processor still
remains an open research area.  The purpose of this paper is to investigate the
applicability of scheduling on scalable architectures where communication
cost is significant.  We have built a system named PYRROS that schedules 
task graphs and also generates parallel code based on the scheduling result.  
We report on experiments performed on the NCUBE-2, a scalable parallel 
distributed architecture, using common application programs, including the
dense Gaussian and Gauss Jordan Elimination algorithms, sparse matrix
computation, fast fourier transforms and fast hierarchical algorithms for 
2D N-body simulations.  These preliminary experiments have produced very
promising results with regard to the practicality of automatic scheduling
for scalable architectures.

NOTE:  The text of this report is not currently available via internet.  To
obtain a copy, please send electronic mail to techreport@cs.rutgers.edu.