FPGA Technology Mapping
- PDF / 278,616 Bytes
- 5 Pages / 547.087 x 737.008 pts Page_size
- 98 Downloads / 197 Views
F
Formal Methods
in speed makes some very simple heuristics have performances that can be very close to the optimum. As to the algorithm’s knowledge of the input instance, an interesting case in the on-line setting, consistent with many real applications, is the non-clairvoyant case described above. This aspect has been considered in [1,3]. In particular, the authors of [1] proved that a randomized variant of the MLF heuristic described above achieves a competitive ratio that in the average is at most a polylogarithmic factor away from the optimum. Applications The first and traditional field of application for scheduling policies is resource assignment to processes in multitasking operating systems [11]. In particular, the use of shortest-job-like heuristics, notably the MLF heuristic, is documented in operating systems of wide use, such as UNIX and WINDOWS NT [8,11]. Their application to other domains, such as access to Web resources, has been considered more recently [2]. Open Problems Shortest-job-first-based heuristics such as those considered in this survey have been studied in depth in the recent past. Still, some questions remain open. One concerns the off-line, parallel-machine case, where no non-constant lower bound on the approximation is known yet. As to the on-line case, there still is no tight lower bound for the non-clairvoyant case on parallel machines. The current ˝(log n) lower bound was achieved for the singlemachine case [7], and there are reasons to believe that it is below the one for the parallel case by a logarithmic factor.
4. Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47(4), 617–643 (2000) 5. Kellerer, H., Tautenhahn, T., Woeginger, G.J.: Approximability and nonapproximability results for minimizing total flow time on a single machine. In: Proceedings of 28th Annual ACM Symposium on the Theory of Computing (STOC ’96), 1996, pp. 418– 426 6. Leonardi, S., Raz, D.: Approximating total flow time on parallel machines. In: Proceedings of the Annual ACM Symposium on the Theory of Computing STOC, 1997, pp. 110–119 7. Motwani, R., Phillips, S., Torng, E.: Nonclairvoyant scheduling. Theor. Comput. Sci. 130(1), 17–47 (1994) 8. Nutt, G.: Operating System Projects Using Windows NT. Addison-Wesley, Reading (1999) 9. Schrage, L.: A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16(1), 687–690 (1968) 10. Smith, D.R.: A new proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 26(1), 197–199 (1976) 11. Tanenbaum, A.S.: Modern Operating Systems. Prentice-Hall, Englewood Cliffs (1992)
Formal Methods Learning Automata Symbolic Model Checking
FPGA Technology Mapping 1992; Cong, Ding JASON CONG1 , YUZHENG DING2 1 Department of Computer Science, UCLA, Los Angeles, CA, USA 2 Synopsys Inc., Mountain View, CA, USA
Cross References
Keywords and Synonyms
Minimum Flow Time Minimum Weighted Completion Time Multi-level Feedback Queues Shortest Elapsed Time First Scheduling
Lookup-Table Mapping;
Data Loading...
