Le matériel ou les algorithmes progressent-ils le plus vite ?

• Il est impossible de comparer ces deux types de progrès de manière générale

• Mais si l’on se limite à un algorithme précis, la comparaison devient possible.

• Comparaison de la vitesse de progression des algorithmes et du matériel en prenant comme référence le problème SAT (https://en.wikipedia.org/wiki/Boolean_satisfiability_problem), qui consiste à déterminer s’il existe une solution satisfaisant une formule donnée.

• Côté matériel, les deux références comparées sont un processeur Pentium III (467MHz) + 1.5GB de RAM (représentatif de 1999) et un Intel Xeon Silver 4112 CPU (2.60GHz) + 128GB de RAM (représentatif de 2019).

• La vitesse est comparée en mesurant, sur 200 instances, combien peuvent être résolues en moins de 900 secondes.

• Pour le problème SAT, les progrès des algorithmes sont plus rapides que ceux du matériel.

• « Lorsque Maple SAT solver, considéré comme le meilleur algorithme en 2019, est utilisé sur du matériel de 1999, il arrive qu’il résolve légèrement moins de cas que d’autres algorithmes. Les auteurs ne connaissent pas la raison exacte, mais supposent qu’une certaine structure de données utilisée par ce bon algorithme est peut-être bien mieux adaptée au matériel moderne. »