Sorting algorithms should be simple, robust and sustainable.


Simplicity

Simplicity is prerequisite for reliability ― Edsger W. Dijkstra

In the post-Moore era, it will be essential for algorithm designers and hardware architects to work together to find simple abstractions that designers can understand and that architects can implement efficiently ― Leiserson et. al1

Sorting algorithms must be simple for reliable industrial grade use. Complexity hinders widespread use and carries risks. Examples of this are the following:


Robustness, Adaptivity and Resilience

It is time to develop the discipline of resilient algorithms ― Moshe Y. Vardi3

Sorting algorithms must function robustly under divers conditions. Simple algorithms also tend to be more robust. Tuning for specific conditions not only makes algorithms more complex, the success of some tuning techniques also strongly depends on CPU and compiler version, notoriously for tuning against branch-misprediction. greeNsort® algorithms require less tuning than other algorithms. Even without tuning greeNsort® algorithms are very adaptive to many diverse data inputs, and some algorithms even reduce branch-misprediction. Still, greeNsort® algorithms may be tuned for specific preferences. The covid-19 pandemie increased appreciation for short local supply chains: greeNsort® algorithms prefer local memory access over distant memory access, where possible. Finally, greeNsort® algorithms allow the resilient execution under difficult conditions: some are designed for economic execution with negligible buffer memory, others allow to cope with temporary shortage of memory when calling them.


Sustainability

What can software professionals do? Software can be designed and tuned for efficiency and memory size, enabling client devices to remain viable for over eight years. Software upgrades should have as a design goal to avoid driving client hardware obsolescence. ― Andrew A. Chien4

We must redesign cloud software and hardware to flexibly follow renewable energy. For cloud computing, the majority of carbon emissions arise from power consumed during operation (80% for typical four-year use). But embodied carbon for hardware and datacenter infrastructure (scope 3) cannot be ignored. ― Andrew A. Chien5

The footprint of software is composed of fixed investment cost (hardware production) and variable runtime cost (energy consumption). However, academic research has almost exclusively compared sorting algorithms with regard to variable cost (typically measuring runtime or counts of certain operations such as moves and comparisons). Ignoring the fixed costs has two major drawbacks:

We introduce the sorting footprint6 for measuring and comparing algorithms with different memory needs: greeNsort® algorithms achieve better runtime with less hardware.


greeNsort® algorithms are simple, robust and sustainable

The most sustainable way is to not make things. The second most sustainable way is to make something very useful, to solve a problem that hasn’t been solved. ― Thomas Sigsgaard

greeNsort® algorithms are …



There’s a way to do it better. Find it. ― Thomas Edison


  1. There’s plenty of room at the Top. What will drive computer performance after Moore’s law?↩︎

  2. Peter Lammich 2020 Efficient Verified Implementation of Introsort and Pdqsort↩︎

  3. Efficiency vs. Resilience: What COVID-19 Teaches Computing, COMMUNICATIONS OF THE ACM, 05/2020↩︎

  4. What Do DDT and Computing Have in Common?, COMMUNICATIONS OF THE ACM, 06/2020↩︎

  5. Driving the Cloud to True Zero Carbon, COMMUNICATIONS OF THE ACM, 02/2021↩︎

  6. The footprint measure integrates fixed and variable costs by integrating resources such as CPU and RAM over \(runtime\) and the \(footprint\) measure allows to compare algorithms with different \(memory\) requirements. For single-threaded sorting the \(footprint\) is just \(\int_{t=0}^{runtime} memory_t \; dt\), for algorithms using constant \(memory\) this simplifies to \(runtime \cdot memory\), where \(energy\) is measured instead of \(runtime\), the \(efootprint\) is calculated as \(energy \cdot memory\)↩︎


greeNsort logo


Copyright © 2020 Dr. Jens Oehlschlägel - All rights reserved - TermsPrivacyImpressum