Was entwickelt sich schneller – Hardware oder Algorithmen?

• Ein allgemeiner Vergleich dieser beiden Entwicklungen ist unmöglich

• Beschränkt man sich jedoch auf einen bestimmten Algorithmus, ist ein Vergleich möglich.

• Als Maßstab für den Vergleich der Entwicklungsgeschwindigkeit von Algorithmen und Hardware dient das SAT-Problem (https://en.wikipedia.org/wiki/Boolean_satisfiability_problem), bei dem entschieden wird, ob eine Lösung existiert, die eine gegebene Formel erfüllt.

• Für die Hardware werden zwei Systeme verglichen: ein Pentium III processor (467MHz) + 1.5GB RAM (repräsentativ für 1999) und ein Intel Xeon Silver 4112 CPU (2.60GHz) + 128GB RAM (repräsentativ für 2019).

• Die Geschwindigkeit wird verglichen, indem bei 200 Instanzen gemessen wird, wie viele davon innerhalb von 900 Sekunden gelöst werden können.

• Beim SAT-Problem entwickelt sich die Algorithmik schneller als die Hardware.

• „Wenn der 2019 als bester bekannte Maple SAT solver auf Hardware von 1999 verwendet wird, gibt es Fälle, in denen er etwas weniger Instanzen löst als andere Algorithmen. Auch die Autoren kennen den genauen Grund nicht; sie vermuten, dass bestimmte in guten Algorithmen verwendete Datenstrukturen möglicherweise deutlich besser zu moderner Hardware passen.“