home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / parallel / 2516 < prev    next >
Encoding:
Internet Message Format  |  1992-11-12  |  2.6 KB
  1. Path: sparky!uunet!ogicse!uwm.edu!zaphod.mps.ohio-state.edu!darwin.sura.net!gatech!hubcap!fpst
  2. From: ramani@cse.iitb.ernet.in (K V Ramani)
  3. Newsgroups: comp.parallel
  4. Subject: Information wanted on how to estimate communication and
  5.          execution times of a task graph.
  6. Message-ID: <1992Nov12.131022.2244@hubcap.clemson.edu>
  7. Date: 11 Nov 92 11:03:11 GMT
  8. Article-I.D.: hubcap.1992Nov12.131022.2244
  9. Sender: usenet@cse.iitb.ernet.in (news dummy user)
  10. Organization: Department of Computer Science,IIT, Bombay
  11. Lines: 47
  12. Approved: parallel@hubcap.clemson.edu
  13. Apparently-To: comp-parallel@uunet.uu.net
  14.  
  15.  
  16.     We are developing a parallelizing compiler which translates
  17. Fortran-77 programs to a language called Par-Fortran. The target
  18. language has been designed to run on a network of transputers.  The
  19. front end of the compiler produces a task graph identifying fragments
  20. of code which can potentially be run in parallel. The nodes of the
  21. task graph represent statements which should be run sequentially, and
  22. the edges represent communication between the nodes.
  23.  
  24.         The back end of the compiler  has to:
  25. 1. estimate the execution time of each node and the communication
  26. along each edge, and use this information to
  27.  
  28. 2. Partition and schedule the task graph on a given topology of
  29. transputers, so that the overall execution time is minimized. 
  30.  
  31.         Note that, in our context, the program  which evaluates the
  32. execution time has to take to account
  33.  
  34.   a. the time taken to execute the basic instructions of the transputer,
  35.      and,
  36.   b. the code generation strategy of the Par-fortran compiler. 
  37.         
  38.         There are essentially two problems. The first concerns
  39. branches. We are currently assuming that information on the branch
  40. probabilities are available. We would like to know how to estimate
  41. branch probabilities. Can these figures be made independent of the
  42. input? 
  43.         The second problem is specific to transputers. The time
  44. required to execute certain instructions (prod, div etc.) are dependent
  45. on the values of their operands. These values may not be available at
  46. compile time. A related problem, which may arise if we use a later
  47. generation of transputers (T9000-which has multiple functional units
  48. operating concurrently) is how to estimate execution costs in the
  49. presence of pipelining and caching. 
  50.  
  51.         We would appreciate receiving any relevant information on
  52. these matters. Any fundamentally different approach towards solving
  53. these problem would also be useful.
  54.  
  55.     Since access to news is problematic here, we would appreciate if
  56. responses are  sent to us by e-mail.
  57.     
  58.                 Thanks in advance.
  59.  
  60.                 as@cse.iitb.ernet.in
  61.                 ramani@cse.iitb.ernet.in
  62.