home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / parallel / 1779 < prev    next >
Encoding:
Text File  |  1992-07-23  |  1.4 KB  |  45 lines
  1. Newsgroups: comp.parallel
  2. Path: sparky!uunet!gatech!hubcap!fpst
  3. From: grendel@fen.arc.nasa.gov (Raymond E. Suorsa)
  4. Subject: Task allocation for multiprocessors
  5. Message-ID: <1992Jul23.135001.5315@hubcap.clemson.edu>
  6. Apparently-To: comp-parallel@ames.arc.nasa.gov
  7. Sender: usenet@news.arc.nasa.gov
  8. Reply-To: grendel@windchime.arc.nasa.gov
  9. Organization: NASA Ames
  10. Date: Wed, 22 Jul 1992 19:43:40 GMT
  11. Approved: parallel@hubcap.clemson.edu
  12. Lines: 31
  13.  
  14.  
  15. Hello,
  16.  
  17. I have a little problem some of you should be able to help me with.
  18.  
  19. I am working with a computer vision problem domain which may be
  20. divided into M independent tasks with each task requiring a variable
  21. amount of time T_i, where the total problem is solved in T seconds of
  22. processor time:
  23.  
  24. T=sum_{i=1}^M T_i
  25.  
  26. The optimal allocation of these tasks onto a N processor machine,
  27. where M > N, is an NP-complete problem.
  28.  
  29. There are several ways to do a good allocation by first sorting the
  30. set of M tasks, and assigning the longest running tasks first.  This
  31. helps reduce the balancing errors as the end of the sorted list is
  32. approached.
  33.  
  34. I have found many papers concerning task allocation using graph
  35. methods.  I am looking for a simpler treatment closer to this problem
  36. type.  (i.e. What is the Best Choice for M given N and the minimum and
  37. maximum expected T_i.)
  38.  
  39. Thanks,
  40.  
  41.   __o   Ray Suorsa,
  42.   \<,   grendel@windchime.arc.nasa.gov,
  43. ()/ ()  NASA/Ames (415)604-6334
  44.  
  45.