Introduction

The UK Parliamentary Office of Science and Technology (2022) reported a global energy consumption of 555 TWh for data centers and user devices in 2020 (excluding cryptomining, networks and TVs) and is projected to grow to 720 TWh in 2030. IBM estimated that sorting - a basic component of software - is responsible for 25% of computing (Mehlhorn (1977))1. If these old estimates hold, sorting costs 11.5 12TWh Nuclear Power Stations (NPS) in 2020 or 15 NPS in 2030, plus embodied energy resp. greenhouse gas for the production of data centers and user devices. Software developers usually consume sorting from few off-the-shelf sorting libraries, improving these libraries can massively save runtime energy (operational costs) and required hardware (embodied costs). Particularly reducing hardware requirements allows using older machines longer, which leads to more sustainable amortization of embodied costs. This paper reports the results of the greeNsort® project (2010 - 2023), which developed simple sorting algorithms that need less runtime energy and/or less required hardware.

Sustainability measures

The classic academic KPI for empirically comparing algorithms is runtime in seconds (\(runTime\)). However, runTime ignores embodied costs and does not allow fair comparison of different sorting algorithms because they require different amounts of memory relative to data size \[\%RAM = (dataRAM+bufferRAM)/dataRAM\] with an expected trade-off: lower memory costs (embodied) correlate with higher runtime costs (operational). A straightforward Footprint KPI combining embodied and operational costs is the integral of required hardware over runtime, i.e. \[tFootprint = avg(\%RAM) * runTime\] Because operational energy (\(Energy\) measured at RAPL Socket) is highly correlated with runtime, similar reasoning leads to the energy footprint calculated as \[eFootprint = avg(\%RAM) * Energy\] Note that cloud Functions as a Service (FaaS) such as AWS Lambda has the payment metric Memory over Time, this is exactly tFootprint.

Scope of greeNsort®

greeNsort® investigates binary divide&conquer algorithms for general comparison in-memory sorting. This investigation and the design of new algorithms is guided by the following values and principles: greeNsort® aims on algorithms that are sustainable, general, directly stable, robust, resilient, scalable, reliable, adaptive, potentially parallel, simple and beautiful.

  1. The first non-analog computer was a pure sorting machine designed by Herman Hollerith and sold by a predecessor of IBM in 1890↩︎