ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Optimal online scheduling of parallel jobs with dependencies
Full text PdfPdf (1.09 MB)
Source Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents
San Diego, California, United States
Pages: 642 - 651  
Year of Publication: 1993
ISBN:0-89791-591-7
Authors
Anja Feldmann
Ming-Yang Kao
Jiří Sgall
Shang-Hua Teng
Sponsor
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 2,   Downloads (12 Months): 22,   Citation Count: 8
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/167088.167254
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

1
Sandeep Bhatt , Fan Chung , Jia-Wei Hong , Arnold Rosenberg, Optimal simulations by Butterfly Networks, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.192-204, May 02-04, 1988, Chicago, Illinois, United States  [doi>10.1145/62212.62229]
 
2
Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
3
Ernest Davis , Jeffrey M. Jaffe, Algorithms for Scheduling Tasks on Unrelated Processors, Journal of the ACM (JACM), v.28 n.4, p.721-736, Oct. 1981  [doi>10.1145/322276.322284]
 
4
D. G. Feitelson , L. Rudolph, Wasted resources in gang scheduling, Proceedings of the fifth Jerusalem conference on Information technology, p.127-136, September 1990, Jerusalem, Israel
 
5
Anja Feldmann , Jiří Sgall , Shang-Hua Teng, Dynamic scheduling on parallel machines, Proceedings of the 32nd annual symposium on Foundations of computer science, p.111-120, September 1991, San Juan, Puerto Rico  [doi>10.1109/SFCS.1991.185355]
 
6
Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
 
7
R.L. Graham. Bounds for certain multiprocessor anomalies. Bell System Technical Journal., pages 1563- 1581, 1966.
 
8
Kai Hwang , Faye A. Briggs, Computer Architecture and Parallel Processing, McGraw-Hill, Inc., New York, NY, 1990
9
S R Kosaraju , M J Atallah, Optimal simulations between mesh-connected arrays of processors, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.264-272, May 28-30, 1986, Berkeley, California, United States  [doi>10.1145/12130.12157]
 
10
H.T. Kung. Computational Models for Parallel Computers. Technical report, CMU-CS-88-164, 1987.
 
11
James L. Peterson , Abraham Silberschatz, Operating system concepts (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
12
Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985  [doi>10.1145/2786.2793]
 
13
David B. Shmoys , Joel Wein , David P. Williamson, Scheduling parallel machines on-line, Proceedings of the 32nd annual symposium on Foundations of computer science, p.131-140, September 1991, San Juan, Puerto Rico  [doi>10.1109/SFCS.1991.185361]
 
14
Qingzhou Wang , Kam Hoi Cheng, A heuristic of scheduling parallel tasks and its analysis, SIAM Journal on Computing, v.21 n.2, p.281-294, April 1992  [doi>10.1137/0221021]

CITED BY  8
Walter Ludwig , Prasoon Tiwari, Scheduling malleable and nonmalleable parallel tasks, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.167-176, January 23-25, 1994, Arlington, Virginia, United States
Houman Alborzi , Eric Torng , Patchrawat Uthaisombut , Stephen Wagner, The k-client problem, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.73-82, January 05-07, 1997, New Orleans, Louisiana, United States
Soumen Chakrabarti , S. Muthukrishnan, Resource scheduling for parallel database and scientific applications, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.329-335, June 24-26, 1996, Padua, Italy
Xiaotie Deng , Patrick Dymond, On multiprocessor system scheduling, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.82-88, June 24-26, 1996, Padua, Italy
Klaus Jansen , Lorant Porkolab, Linear-time approximation schemes for scheduling malleable parallel tasks, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.490-498, January 17-19, 1999, Baltimore, Maryland, United States
Lixin Gao , Arnold L. Rosenberg , Ramesh K. Sitaraman, On trading task reallocation for thread management in partitionable multiprocessors, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.309-317, June 24-26, 1996, Padua, Italy
Keqin Li , Yi Pan, Probabilistic Analysis of Scheduling Precedence Constrained Parallel Tasks on Multicomputers with Contiguous Processor Allocation, IEEE Transactions on Computers, v.49 n.10, p.1021-1030, October 2000
Amrinder Arora , Fanchun Jin , Hyeong-Ah Choi, Scheduling resource allocation with timeslot penalty for changeover, Theoretical Computer Science, v.369 n.1, p.323-337, 15 December 2006

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency


General Terms:
Algorithms, Measurement, Performance, Theory, Verification

Collaborative Colleagues:
Anja Feldmann: colleagues
Ming-Yang Kao: colleagues
Jiří Sgall: colleagues
Shang-Hua Teng: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player