Giữa phần cứng và thuật toán, bên nào phát triển nhanh hơn?

• Không thể so sánh hai kiểu tiến bộ này theo cách tổng quát.

• Nhưng nếu giới hạn vào một thuật toán cụ thể thì có thể so sánh được.

• Dùng bài toán SAT (https://en.wikipedia.org/wiki/Boolean_satisfiability_problem), tức bài toán xác định liệu có tồn tại nghiệm thỏa mãn công thức đã cho hay không, làm chuẩn để so sánh tốc độ phát triển của thuật toán và phần cứng.

• Về phần cứng, hai đối tượng được đem ra so sánh là Pentium III processor (467MHz) + 1.5GB RAM (đại diện cho năm 1999) và Intel Xeon Silver 4112 CPU (2.60GHz) + 128GB RAM (đại diện cho năm 2019).

• Tốc độ được so sánh bằng cách đo số lượng instance có thể giải trong vòng 900 giây trên tổng 200 instance.

• Riêng với bài toán SAT, sự tiến bộ của thuật toán nhanh hơn sự tiến bộ của phần cứng.

• "Khi Maple SAT solver, được xem là thuật toán tốt nhất năm 2019, chạy trên phần cứng năm 1999 thì trong một số trường hợp lại giải được ít hơn đôi chút so với các thuật toán khác. Chính các tác giả cũng không biết chính xác lý do, và phỏng đoán rằng có thể một cấu trúc dữ liệu cụ thể được dùng trong thuật toán tốt hơn lại phù hợp với phần cứng hiện đại hơn nhiều."