Optimal Speed Scaling with a Solar Cell

Preprint English OPEN
Barcelo, Neal ; Kling, Peter ; Nugent, Michael ; Pruhs, Kirk (2016)
  • Subject: Computer Science - Data Structures and Algorithms
    acm: ComputerSystemsOrganization_SPECIAL-PURPOSEANDAPPLICATION-BASEDSYSTEMS
    arxiv: Computer Science::Operating Systems

We consider the setting of a sensor that consists of a speed-scalable processor, a battery, and a solar cell that harvests energy from its environment at a time-invariant recharge rate. The processor must process a collection of jobs of various sizes. Jobs arrive at different times and have different deadlines. The objective is to minimize the *recharge rate*, which is the rate at which the device has to harvest energy in order to feasibly schedule all jobs. The main result is a polynomial-time combinatorial algorithm for processors with a natural set of discrete speed/power pairs.
  • References (11)
    11 references, page 1 of 2

    [1] S. Angelopoulos, G. Lucarelli, and K. T. Nguyen. Primal-dual and dualtting analysis of online scheduling algorithms for generalized ow time problems. In Proceedings of the 23rd Annual European Symposium on Algorithms (ESA), pages 35{46. Springer, 2015.

    [2] A. Antoniadis, N. Barcelo, M. E. Consuegra, P. Kling, M. Nugent, K. Pruhs, and M. Scquizzato. E cient computation of optimal energy and fractional weighted ow trade-o schedules. In Symposium on Theoretical Aspects of Computer Science, pages 63{74, 2014.

    [3] N. Bansal, T. Kimbrel, and K. Pruhs. Speed scaling to manage energy and temperature. J. ACM, 54(1):3:1{3:39, March 2007.

    [4] N. Bansal, H.-L. Chan, and K. Pruhs. Speed scaling with a solar cell. Theoretical Computer Science, 410(45):4580{4587, 2009.

    [5] D. M. Brooks, P. Bose, S. E. Schuster, H. Jacobson, P. N. Kudva, A. Buyuktosunoglu, J.-D. Wellman, V. Zyuban, M. Gupta, and P. W. Cook. Poweraware microarchitecture: Design and modeling challenges for next-generation microprocessors. IEEE Micro, 20(6):26{44, 2000. ISSN 0272-1732.

    [6] D. Cole, D. Letsios, M. Nugent, and K. Pruhs. Optimal energy trade-o schedules. In International Green Computing Conference, pages 1{10, 2012.

    [7] K. Pruhs, P. Uthaisombut, and G. J. Woeginger. Getting the best response for your erg. ACM Transactions on Algorithms, June 2008.

    [8] K. Remick, D. D. Quinn, D. M. McFarland, L. Bergman, and A. Vakakis. High-frequency vibration energy harvesting from impulsive excitation utilizing intentional dynamic instability caused by strong nonlinearity. Journal of Sound and Vibration, 370:259{279, 2016. doi: 10.1016/j.jsv.2016.01.051.

    [9] N. G. Stephen. On energy harvesting from ambient vibration. Journal of Sound and Vibration, 293(1{2):409{425, 2006. doi: 10.1016/j.jsv.2005.10.003.

    [10] R. Vullers, R. van Schaijk, I. Doms, C. V. Hoof, and R. Mertens. Micropower energy harvesting. Solid-State Electronics, 53(7):684{693, 2009.

  • Metrics
    No metrics available