From: roy@skorpio.USask.ca (Kanad Roy)
Subject: summary of responses on task generation & mapping 
To: uunet!comp-parallel@uunet.UU.NET
Apparently-To: uunet!comp-parallel
Followup-To: roy@skorpio.usask.ca 
Keywords: loosely coupled systems
Organization: University of Saskatchewan, Saskatoon, Canada
Date: Thu, 12 Nov 1992 10:31:46 -0700

The following is a summary of the responses I received from various
persons in reply to my posting requesting information for the literature
on task graph generation and mapping on message passing systems.
The formats of the citations are not consistent. They are in the form in
which they were received.

Thanks a lot to the persons who replied.

I did not name the ftp sites, from where some of the papers can be obtained, without the consent of the respective persons concerned.

_______________________________________________________________________________________

@article{sarkar,
   author        = "Vivek Sarkar and John Hennessy",
   title         = "{C}ompile-time {P}artitioning and {S}cheduling of
       {P}arallel {P}rograms", 
   year          = 1986,
   journal       = sigplan,
   volume        = 21,
   number        = 7,
   month         = jul,
   pages         = "17--26",
   prelimnote    = "A very useful paper on static scheduling for
       parallel programming.  It takes into account communications delays
       between remote processes, although it requires the programmer to
       give a priori estimates of these delays.  Gives a polynomial time
       algorithm for partitioning and scheduling that is within a linear
       factor of optimal (optimal solution is NP-complete).",
   rstate        = "read",
}       

@book{sarkar-thesis,
   author        = "Vivek Sarkar",
   title         = "{P}artitioning and {S}cheduling {P}arallel {P}rograms for
       {M}ultiprocessors",
   publisher     = "The MIT Press",
   year          = 1989,
   prelimnote    = "Book form of Sarkar's thesis.  He considers static
       partitioning and both compile-time and run-time scheduling.
       Assumes symmetric processors.",
   rstate        = "read",
}       

@inproceedings{macro-dataflow,
   author        = "Vivek Sarkar and John Hennessy",
   title         = "{Partitioning Parallel Programs for Macro-Dataflow}",
   booktitle     = "ACM Conference on Lisp and Functional Programming",
   year          = 1986,
   month         = aug,
   pages         = "202--211",
   prelimnote    = "Presents a dataflow model for program partitioning.",
   rstate        = "read",
}       

__________________________________________________________________________________

1. Gerasoulis and Yang, On the Granularity and Clustering of
   Directed Acyclic Task Graphs, LCSR-TR-153, Rutgers Univ., 1990,
   Revised 1992.

2. Gerasoulis, Venugopal and Yang, Clustering task graphs
   for message passing architectures, 4th ACM Inter. Conf. on 
   Supercomputing (ICS 90), Amsterdam, June 1990, pp.447-456.

3. Yang and Gerasoulis, A Fast Static Scheduling Algorithm
   for DAGs on an Unbounded Number of Processors, Proc. of IEEE
   Supercomputing 91, Albuquerque, NM, Nov. 1991, pp. 633-642.

4. Gerasoulis and Yang, A Comparison of Clustering Heuristics for
   Scheduling DAGs on Multiprocessors, LCSR-TR-169, Rutgers Univ. 1991.
   To appear in  Journal of Parallel and Distributed Computing, Special issue 
   on scheduling and load balancing, Dec. 1992

5. Yang and Gerasoulis, PYRROS:Static Task Scheduling
   and Code Generation for Message Passing Multiprocessors, Proc. of 6th
   ACM Inter. Conf.  on Supercomputering (ICS 92), Washington D.C., July
   1992, pp. 428-437.

6. Yang and Gerasoulis, A parallel progamming tool for 
   scheduling on distributed memory multiprocessors,  Proc. of Scalable 
   High Performance Computing Conference, IEEE, Williamsburg, VA., April, 
   1992, pp. 350-357.

7. Gerasoulis and T. Yang, Static scheduling of parallel programs 
   for message passing architectures.  Lecture Notes in Computer Science, 
   No. 634, Parallel Processing: CONPAR 92 -- VAPP V, L. Bouge, M. Cosnard, 
   Y. Robert and D. Trystram (Eds.), Springer-Verlag,  1992, pp. 601-612.

8. Gerasoulis and Yang, Scheduling program task graphs
   on MIMD architectures, To appear as a book chapter in "Algorithm Derivation 
   and Program Transformation", edited by R. Paige, J. Reif, and R. Wachter, 
   Kluwer Publisher. 

9. Yang and Gerasoulis, List scheduling with and without
   communication delay, To appear in Parallel Computing Journal, 1993.

10.T. Yang and A. Gerasoulis, DSC: Scheduling Parallel Tasks on 
   an Unbounded Number of Processors, Report, 1992.

______________________________________________________________________________________

H. Shen, "Self-adjusting Mapping: A Heuristic Mapping Algorithm for Mapping
Parallel Programs on to Transputer Networks", The Computer Journal, Vol. 35,
No. 1, 1992, pp 71-80.

______________________________________________________________________________________





=================================
Kanad Roy (roy@skorpio.usask.ca) 
Dept. of Computational Science
Universtiy of Saskatchewan
Saskatoon
CANADA S7N 0W0
=================================

 


Newsgroups: comp.parallel