Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Energy Efficient Sorting, Selection and Searching

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 13973))

  • 596Accesses

Abstract

In this paper, we introduce a model for studying energy efficient algorithms by extending the well-studied comparison model. In our model, the result of a comparison is determined based on two parameters: (i) the energy used to perform a comparison, and (ii) the absolute difference between the two values being compared – thus introducing an energy-accuracy trade-off. This model also extends the ideas presented by Geissmann and Penna [SOFSEM 2018] and Funke et al. [Comput. Geom. 2005] wherein they use two distinct types of comparisons namely low and full-energy (cheap and expensive) comparisons, by introducing multiple types of comparisons. In this extension, the accuracy of a comparison becomes a function of the energy used. We consider the fundamental problems of (i) sorting (ii) selection (iii) searching, and design efficient algorithms for these problems in the new model. We also present lower bounds on the energy usage for some of these problems, showing that some of our algorithms are asymptotically optimal with respect to the energy usage.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 8579
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 10724
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Similar content being viewed by others

Notes

  1. 1.

    Throughout this paper,\(\lg \) denotes the logarithm to the base 2, and we ignore ceiling and floors which do not affect our results asymptotically.

  2. 2.

    In [10], they defined the cheap comparison based on the absolute difference between therank of operands. This corresponds to the case when input is a permutation over integers 1 ton.

References

  1. Ajtai, M., Feldman, V., Hassidim, A., Nelson, J.: Sorting and selection with imprecise comparisons. ACM Trans. Algorithms12(2), 19:1–19:19 (2016)

    Google Scholar 

  2. Alonso, L., Chassaing, P., Gillet, F., Janson, S., Reingold, E.M., Schott, R.: Quicksort with unreliable comparisons: a probabilistic analysis. Comb. Probab. Comput.13(4–5), 419–449 (2004).https://doi.org/10.1017/S0963548304006297

    Article MathSciNet MATH  Google Scholar 

  3. Arumugam, G.P., et al.: Novel inexact memory aware algorithm co-design for energy efficient computation: algorithmic principles. In: Proceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition, DATE 2015, pp. 752–757. ACM (2015)

    Google Scholar 

  4. Bennett, C.H.: Time/space trade-offs for reversible computation. SIAM J. Comput.18(4), 766–776 (1989)

    Article MathSciNet MATH  Google Scholar 

  5. Bianchi, E., Penna, P.: Optimal clustering in stable instances using combinations of exact and noisy ordinal queries. Algorithms14(2), 55 (2021)

    Article MathSciNet  Google Scholar 

  6. David, H.A.: The Method of Paired Comparisons, 2nd edition, vol. 12. London (1988)

    Google Scholar 

  7. Demaine, E.D., Lynch, J., Mirano, G.J., Tyagi, N.: Energy-efficient algorithms. In: Sudan, M. (ed.) Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, 14–16 January 2016, pp. 321–332. ACM (2016)

    Google Scholar 

  8. Feige, U., Raghavan, P., Peleg, D., Upfal, E.: Computing with noisy information. SIAM J. Comput.23(5), 1001–1018 (1994)

    Article MathSciNet MATH  Google Scholar 

  9. Finocchi, I., Italiano, G.F.: Sorting and searching in faulty memories. Algorithmica52(3), 309–332 (2008)

    Article MathSciNet MATH  Google Scholar 

  10. Funke, S., Mehlhorn, K., Näher, S.: Structural filtering: a paradigm for efficient and exact geometric programs. Comput. Geom.31(3), 179–194 (2005)

    Article MathSciNet MATH  Google Scholar 

  11. Geissmann, B., Leucci, S., Liu, C., Penna, P.: Optimal sorting with persistent comparison errors. In: 27th Annual European Symposium on Algorithms, ESA 2019. LIPIcs, vol. 144, pp. 49:1–49:14 (2018)

    Google Scholar 

  12. Geissmann, B., Leucci, S., Liu, C.H., Penna, P., Proietti, G.: Dual-mode greedy algorithms can save energy. In: 30th International Symposium on Algorithms and Computation (ISAAC 2019), vol. 149, pp. 64–1. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2019)

    Google Scholar 

  13. Geissmann, B., Penna, P.: Inversions from sorting with distance-based errors. In: Tjoa, A.M., Bellatreche, L., Biffl, S., van Leeuwen, J., Wiedermann, J. (eds.) SOFSEM 2018. LNCS, vol. 10706, pp. 508–522. Springer, Cham (2018).https://doi.org/10.1007/978-3-319-73117-9_36

    Chapter  Google Scholar 

  14. Geissmann, B., Penna, P.: Sorting processes with energy-constrained comparisons. Phys. Rev. E97(5), 052108 (2018)

    Article  Google Scholar 

  15. Huang, Z., Kannan, S., Khanna, S.: Algorithms for the generalized sorting problem. In: Ostrovsky, R. (ed.) IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp. 738–747. IEEE Computer Society (2011)

    Google Scholar 

  16. Korkmaz, P., Akgul, B.E.S., Palem, K.V.: Energy, performance, and probability tradeoffs for energy-efficient probabilistic CMOS circuits. IEEE Trans. Circuits Syst. I Regul. Pap.55(8), 2249–2262 (2008)

    Article MathSciNet  Google Scholar 

  17. Landauer, R.: Irreversibility and heat generation in the computing process. IBM J. Res. Dev.5(3), 183–191 (1961).https://doi.org/10.1147/rd.53.0183

    Article MathSciNet MATH  Google Scholar 

  18. Leucci, S., Liu, C.H.: Approximate minimum selection with unreliable comparisons. Algorithmica84(1), 60–84 (2022)

    Article MathSciNet MATH  Google Scholar 

  19. Mehlhorn, K.: Data Structures and Algorithms 1: Sorting and Searching, EATCS Monographs on Theoretical Computer Science, vol. 1. Springer, Cham (1984).https://doi.org/10.1007/978-3-642-69672-5

    Book  Google Scholar 

  20. Palem, K.V., Avinash, L.: Ten years of building broken chips: the physics and engineering of inexact computing. ACM Trans. Embed. Comput. Syst.12(2s), 87:1–87:23 (2013)

    Google Scholar 

  21. Zurek, W.H.: Thermodynamic cost of computation, algorithmic complexity and the information metric. Nature341, 119–124 (1989)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Indian Institute of Technology Mandi, Kamand, India

    Varunkumar Jayapaul

  2. Chungnam National University, Daejeon, South Korea

    Seungbum Jo

  3. Rice University, Houston, USA

    Krishna Palem

  4. Norwegian University of Science and Technology, Trondheim, Norway

    Srinivasa Rao Satti

Authors
  1. Varunkumar Jayapaul

    You can also search for this author inPubMed Google Scholar

  2. Seungbum Jo

    You can also search for this author inPubMed Google Scholar

  3. Krishna Palem

    You can also search for this author inPubMed Google Scholar

  4. Srinivasa Rao Satti

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toSeungbum Jo.

Editor information

Editors and Affiliations

  1. National Yang Ming Chiao Tung University, Hsinchu, Taiwan

    Chun-Cheng Lin

  2. National Yang Ming Chiao Tung University, Hsinchu, Taiwan

    Bertrand M. T. Lin

  3. University of Perugia, Perugia, Italy

    Giuseppe Liotta

Rights and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Jayapaul, V., Jo, S., Palem, K., Satti, S.R. (2023). Energy Efficient Sorting, Selection and Searching. In: Lin, CC., Lin, B.M.T., Liotta, G. (eds) WALCOM: Algorithms and Computation. WALCOM 2023. Lecture Notes in Computer Science, vol 13973. Springer, Cham. https://doi.org/10.1007/978-3-031-27051-2_16

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 8579
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 10724
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

[8]ページ先頭
©2009-2025 Movatter.jp