Speed scaling of tasks with precedence constraints. (English) Zbl 1140.68010
Summary: We consider the problem of speed scaling to conserve energy in a multiprocessor setting where there are precedence constraints between tasks, and where the performance measure is the makespan. That is, we consider an energy bounded version of the classic problem \(Pm|prec| C_{\text{max}}\). We extend the standard 3-field notation and denote this problem as \(Sm| prec, energy |C_{\text{max}}\). We show that, without loss of generality, one need only consider constant power schedules. We then show how to reduce this problem to the problem \(Qm|prec|C_{\text{max}}\) to obtain a poly-\(\log(m)\)-approximation algorithm.
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68W25 | Approximation algorithms |
References:
| [1] | Alon, N., Azar, Y., Woeginger, G., Yadid, T.: Approximation schemes for scheduling on parallel machines. J. Sched. 1(1), 55–66 (1998) · Zbl 0909.90168 · doi:10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J |
| [2] | Bansal, N., Pruhs, K.: Speed scaling to manage temperature. In: Symposium on Theoretical Aspects of Computer Science, pp. 460–471 (2005) · Zbl 1118.68769 |
| [3] | Bansal, N., Kimbrel, T., Pruhs, K.: Dynamic speed scaling to manage energy and temperature. In: IEEE Symposium on Foundations of Computer Science, pp. 520–529 (2004) · Zbl 1326.68043 |
| [4] | Brooks, D.M., Bose, P., Schuster, S.E., Jacobson, H., Kudva, P.N., Buyuktosunoglu, A., Wellman, J.-D., Zyuban, V., Gupta, M., Cook, P.W.: Power-aware microarchitecture: design and modeling challenges for next-generation microprocessors. IEEE Micro 20(6), 26–44 (2000) · doi:10.1109/40.888701 |
| [5] | Chekuri, C., Bender, M.A.: An efficient approximation algorithm for minimizing makespan on uniformly related machines. J. Algorithms 41, 212–224 (2001) · Zbl 1051.68150 · doi:10.1006/jagm.2001.1184 |
| [6] | Chen, J.-J., Kuo, T.-W., Lu, H.-I.: Power-saving scheduling for weakly dynamic voltage scaling devices. In: Workshop on Algorithms and Data Structures, pp. 338–349 (2005) · Zbl 1161.90390 |
| [7] | Chudak, F.A., Shmoys, D.B.: Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. J. Algorithms 30(2), 323–343 (1999) · Zbl 0923.68012 · doi:10.1006/jagm.1998.0987 |
| [8] | Graham, R.L.: Bounds for certain multiprocessor anomalies. Bell Syst. Tech. J. 45, 1563–1581 (1966) · Zbl 0168.40703 |
| [9] | Graham, R.L., Lawler, E., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic scheduling: a survey. Ann. Discrete Math. 5, 287–326 (1979) · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |
| [10] | Gruian, F., Kuchcinski, K.: Lenes: task-scheduling for low-energy systems using variable voltage processors. In: Asia South Pacific–Design Automation Conference, pp. 449–455 (2001) |
| [11] | Irani, S., Pruhs, K.: Algorithmic problems in power management. SIGACT News 32(2), 63–76 (2005) · doi:10.1145/1067309.1067324 |
| [12] | Kwon, W.-C., Kim, T.: Optimal voltage allocation techniques for dynamically variable voltage processors. ACM Trans. Embed. Comput. Syst. (TECS) 4(1), 211–230 (2005) · doi:10.1145/1053271.1053280 |
| [13] | Li, M., Liu, B.J., Yao, F.F.: Min-energy voltage allocation for tree-structured tasks. In: 11th International Computing and Combinatorics Conference (COCOON 2005), pp. 283–296 (2005) · Zbl 1128.68337 |
| [14] | Luo, J., Jha, N.K.: Power-conscious joint scheduling of periodic task graphs and aperiodic task graphs in distributed real-time embedded systems. In: International Conference on Computer Aided Design, pp. 357–364 (2000) |
| [15] | Mishra, R., Rastogi, N., Zhu, D., Mossé, D., Melhem, R.G.: Energy aware scheduling for distributed real-time systems. In: International Parallel and Distributed Processing Symposium, p. 21 (2003) |
| [16] | Mudge, T.: Power: a first-class architectural design constraint. Computer 34(4), 52–58 (2001) · doi:10.1109/2.917539 |
| [17] | Pruhs, K., Uthaisombut, P., Woeginger, G.: Getting the best response for your erg. In: Scandinavian Workshop on Algorithms and Theory, pp. 14–25 (2004) · Zbl 1095.68553 |
| [18] | Yao, F.F., Demers, A.J., Shenker, S.: A scheduling model for reduced cpu energy. In: IEEE Symposium on Foundations of Computer Science (FOCS 1995), pp. 374–382 (1995) · Zbl 0938.68533 |
| [19] | Yun, H.-S., Kim, J.: On energy-optimal voltage scheduling for fixed priority hard real-time systems. ACM Trans. Embed. Comput. Syst. 2(3), 393–430 (2003) · doi:10.1145/860176.860183 |
| [20] | Zhang, Y., Hu, X., Chen, D.Z.: Task scheduling and voltage selection for energy minimization. In: Design Automation Conference, pp. 183–188 (2002) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
