home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / parallel / 2519 < prev    next >
Encoding:
Text File  |  1992-11-13  |  5.3 KB  |  139 lines
  1. Newsgroups: comp.parallel
  2. Path: sparky!uunet!gatech!hubcap!fpst
  3. From: roy@skorpio.USask.ca (Kanad Roy)
  4. Subject: summary of responses on task generation & mapping 
  5. Message-ID: <1992Nov13.125053.20156@hubcap.clemson.edu>
  6. To: uunet!comp-parallel@uunet.UU.NET
  7. Apparently-To: uunet!comp-parallel
  8. Followup-To: roy@skorpio.usask.ca 
  9. Keywords: loosely coupled systems
  10. Sender: roy@skorpio.pa.dec.com (Kanad Roy)
  11. Nntp-Posting-Host: skorpio.usask.ca
  12. Organization: University of Saskatchewan, Saskatoon, Canada
  13. Date: Thu, 12 Nov 1992 10:31:46 -0700
  14. Approved: parallel@hubcap.clemson.edu
  15. Lines: 122
  16.  
  17. The following is a summary of the responses I received from various
  18. persons in reply to my posting requesting information for the literature
  19. on task graph generation and mapping on message passing systems.
  20. The formats of the citations are not consistent. They are in the form in
  21. which they were received.
  22.  
  23. Thanks a lot to the persons who replied.
  24.  
  25. I did not name the ftp sites, from where some of the papers can be obtained, without the consent of the respective persons concerned.
  26.  
  27. _______________________________________________________________________________________
  28.  
  29. @article{sarkar,
  30.    author        = "Vivek Sarkar and John Hennessy",
  31.    title         = "{C}ompile-time {P}artitioning and {S}cheduling of
  32.        {P}arallel {P}rograms", 
  33.    year          = 1986,
  34.    journal       = sigplan,
  35.    volume        = 21,
  36.    number        = 7,
  37.    month         = jul,
  38.    pages         = "17--26",
  39.    prelimnote    = "A very useful paper on static scheduling for
  40.        parallel programming.  It takes into account communications delays
  41.        between remote processes, although it requires the programmer to
  42.        give a priori estimates of these delays.  Gives a polynomial time
  43.        algorithm for partitioning and scheduling that is within a linear
  44.        factor of optimal (optimal solution is NP-complete).",
  45.    rstate        = "read",
  46. }       
  47.  
  48. @book{sarkar-thesis,
  49.    author        = "Vivek Sarkar",
  50.    title         = "{P}artitioning and {S}cheduling {P}arallel {P}rograms for
  51.        {M}ultiprocessors",
  52.    publisher     = "The MIT Press",
  53.    year          = 1989,
  54.    prelimnote    = "Book form of Sarkar's thesis.  He considers static
  55.        partitioning and both compile-time and run-time scheduling.
  56.        Assumes symmetric processors.",
  57.    rstate        = "read",
  58. }       
  59.  
  60. @inproceedings{macro-dataflow,
  61.    author        = "Vivek Sarkar and John Hennessy",
  62.    title         = "{Partitioning Parallel Programs for Macro-Dataflow}",
  63.    booktitle     = "ACM Conference on Lisp and Functional Programming",
  64.    year          = 1986,
  65.    month         = aug,
  66.    pages         = "202--211",
  67.    prelimnote    = "Presents a dataflow model for program partitioning.",
  68.    rstate        = "read",
  69. }       
  70.  
  71. __________________________________________________________________________________
  72.  
  73. 1. Gerasoulis and Yang, On the Granularity and Clustering of
  74.    Directed Acyclic Task Graphs, LCSR-TR-153, Rutgers Univ., 1990,
  75.    Revised 1992.
  76.  
  77. 2. Gerasoulis, Venugopal and Yang, Clustering task graphs
  78.    for message passing architectures, 4th ACM Inter. Conf. on 
  79.    Supercomputing (ICS 90), Amsterdam, June 1990, pp.447-456.
  80.  
  81. 3. Yang and Gerasoulis, A Fast Static Scheduling Algorithm
  82.    for DAGs on an Unbounded Number of Processors, Proc. of IEEE
  83.    Supercomputing 91, Albuquerque, NM, Nov. 1991, pp. 633-642.
  84.  
  85. 4. Gerasoulis and Yang, A Comparison of Clustering Heuristics for
  86.    Scheduling DAGs on Multiprocessors, LCSR-TR-169, Rutgers Univ. 1991.
  87.    To appear in  Journal of Parallel and Distributed Computing, Special issue 
  88.    on scheduling and load balancing, Dec. 1992
  89.  
  90. 5. Yang and Gerasoulis, PYRROS:Static Task Scheduling
  91.    and Code Generation for Message Passing Multiprocessors, Proc. of 6th
  92.    ACM Inter. Conf.  on Supercomputering (ICS 92), Washington D.C., July
  93.    1992, pp. 428-437.
  94.  
  95. 6. Yang and Gerasoulis, A parallel progamming tool for 
  96.    scheduling on distributed memory multiprocessors,  Proc. of Scalable 
  97.    High Performance Computing Conference, IEEE, Williamsburg, VA., April, 
  98.    1992, pp. 350-357.
  99.  
  100. 7. Gerasoulis and T. Yang, Static scheduling of parallel programs 
  101.    for message passing architectures.  Lecture Notes in Computer Science, 
  102.    No. 634, Parallel Processing: CONPAR 92 -- VAPP V, L. Bouge, M. Cosnard, 
  103.    Y. Robert and D. Trystram (Eds.), Springer-Verlag,  1992, pp. 601-612.
  104.  
  105. 8. Gerasoulis and Yang, Scheduling program task graphs
  106.    on MIMD architectures, To appear as a book chapter in "Algorithm Derivation 
  107.    and Program Transformation", edited by R. Paige, J. Reif, and R. Wachter, 
  108.    Kluwer Publisher. 
  109.  
  110. 9. Yang and Gerasoulis, List scheduling with and without
  111.    communication delay, To appear in Parallel Computing Journal, 1993.
  112.  
  113. 10.T. Yang and A. Gerasoulis, DSC: Scheduling Parallel Tasks on 
  114.    an Unbounded Number of Processors, Report, 1992.
  115.  
  116. ______________________________________________________________________________________
  117.  
  118. H. Shen, "Self-adjusting Mapping: A Heuristic Mapping Algorithm for Mapping
  119. Parallel Programs on to Transputer Networks", The Computer Journal, Vol. 35,
  120. No. 1, 1992, pp 71-80.
  121.  
  122. ______________________________________________________________________________________
  123.  
  124.  
  125.  
  126.  
  127.  
  128. =================================
  129. Kanad Roy (roy@skorpio.usask.ca) 
  130. Dept. of Computational Science
  131. Universtiy of Saskatchewan
  132. Saskatoon
  133. CANADA S7N 0W0
  134. =================================
  135.  
  136.  
  137.  
  138.  
  139.