Trong nửa thế kỷ qua, ngành công nghiệp mạch tích hợp đã phát triển nhanh chóng dưới sự hướng dẫn của Định luật Moore và hiệu quả của các thuật toán đã duy trì sự cải thiện trên diện rộng. Năm 2018, máy tính nhanh nhất thế giới, IBM Summit, nhanh hơn gần 30 nghìn tỷ lần so với máy tính điện tử đầu tiên trên thế giới ENIAC vào năm 1945.

Tuy nhiên, khi Định luật Moore đang tiến gần đến giới hạn vật lý, chi phí phát triển và sản xuất chip đã tăng mạnh và khả năng dựa vào sức mạnh tính toán để cải thiện hiệu suất tính toán trong tương lai là rất hạn chế. Có thể ngày càng khó đáp ứng nhu cầu tính toán khối lượng lớn bằng cách cải thiện hiệu suất của phần cứng máy tính.Giải pháp trong tương lai nằm ở việc cải thiện hiệu quả của các thuật toán.

Bài báo mới này của MIT tóm tắt mức độ hiệu quả của thuật toán đã được cải thiện nhanh chóng như thế nào trong 80 năm qua.

Khi nói đến thuật toán, nó gần giống như cha mẹ của máy tính, nó sẽ cho máy tính biết cách hiểu thông tin và máy tính có thể nhận được những điều hữu ích từ thuật toán.

Thuật toán càng hiệu quả thì máy tính càng phải làm ít công việc hơn. Đối với tất cả những tiến bộ công nghệ trong phần cứng máy tính và tuổi thọ của Định luật Moore gây tranh cãi nhiều, hiệu suất của phần cứng máy tính chỉ là một khía cạnh của vấn đề.

Mặt khác, vấn đề nằm bên ngoài phần cứng: hiệu quả của thuật toán. Nếu hiệu quả của thuật toán được cải thiện, sức mạnh tính toán cần thiết cho cùng một tác vụ tính toán sẽ giảm đi.

Mặc dù các vấn đề về hiệu quả của thuật toán có thể ít được quan tâm hơn, nhưng bạn có bao giờ nhận thấy rằng công cụ tìm kiếm thường dùng của mình đột nhiên nhanh hơn một phần mười, trong khi di chuyển qua các bộ dữ liệu lớn giống như lội qua bùn không?

Tất cả đều liên quan đến hiệu quả thuật toán.

Gần đây, các nhà khoa học tại Phòng thí nghiệm Khoa học Máy tính và Trí tuệ Nhân tạo (CSAIL) của MIT đã đặt câu hỏi: Hiệu quả thuật toán được cải thiện nhanh như thế nào?

Phần lớn dữ liệu hiện có về câu hỏi này là tường thuật và phần lớn trong số đó là các nghiên cứu điển hình cho các thuật toán cụ thể và kết quả của các nghiên cứu này được khái quát hóa.

Trước tình trạng thiếu dữ liệu nghiên cứu thực nghiệm, nhóm nghiên cứu chủ yếu sử dụng dữ liệu từ 57 sách giáo khoa và hơn 1110 tài liệu nghiên cứu để theo dõi lịch sử cải thiện hiệu quả của thuật toán.

Một số bài báo này chỉ ra trực tiếp mức độ hiệu quả của thuật toán mới trong kết luận của họ, trong khi những bài báo khác yêu cầu tác giả xây dựng lại nó bằng cách sử dụng "mã giả" (một mô tả đơn giản về các chi tiết cơ bản của thuật toán).

Tổng cộng, các nhà nghiên cứu đã xem xét 113 "dòng thuật toán" hoặc tập hợp các thuật toán giải quyết cùng một vấn đề quan trọng nhất trong sách giáo khoa khoa học máy tính. Họ xem lại lịch sử của từng họ thuật toán, theo dõi mỗi khi một thuật toán mới được đề xuất cho một vấn đề, đặc biệt chú ý đến các thuật toán hiệu quả hơn.

Hình 1 Khám phá và cải tiến thuật toán. (a) Số họ thuật toán mới được phát hiện mỗi thập kỷ. (b) Tỷ lệ các họ thuật toán đã biết tăng lên sau mỗi thập kỷ. (c) Phân loại độ phức tạp thời gian tiệm cận của họ thuật toán khi lần đầu tiên được phát hiện. (d) Xác suất trung bình hàng năm của việc chuyển đổi từ thuật toán có độ phức tạp lần này sang độ phức tạp thời gian khác (phản ánh mức độ tăng độ phức tạp trung bình của hệ thống thuật toán). Độ phức tạp thời gian của ">n3" trong (c) và (d) có nghĩa là lớn hơn mức đa thức, nhưng nhỏ hơn mức hàm mũ.

Bộ phận thuật toán sớm nhất có thể được bắt nguồn từ những năm 1940. Mỗi bộ phận thuật toán có trung bình 8 thuật toán và hiệu quả được cải thiện dần theo trình tự thời gian. Để chia sẻ khám phá này, nhóm cũng đã tạo trang "Algorithm Wiki" (Algorithm-Wiki.org).

Các nhà nghiên cứu đã lập biểu đồ về mức độ hiệu quả của các họ thuật toán này được cải thiện nhanh như thế nào, tập trung vào các đặc điểm được phân tích nhiều nhất của thuật toán—những đặc điểm có xu hướng xác định tốc độ giải quyết vấn đề (theo cách nói của điện toán, “độ phức tạp trong trường hợp xấu nhất”) ).

Hình 2 Mức tăng hiệu quả tương đối của họ thuật toán, được tính bằng cách sử dụng các thay đổi độ phức tạp của thời gian tiệm cận. Dòng tham chiếu là hiệu suất cơ sở SPECInt. (a) Các cải tiến lịch sử cho bốn họ thuật toán so với thuật toán đầu tiên trong chuỗi (n = 1 triệu). (b) Độ nhạy của cải tiến thuật toán đối với kích thước đầu vào (n) của họ thuật toán "Tìm kiếm hàng xóm gần nhất". Để thuận tiện cho việc so sánh hiệu quả cải thiện của thuật toán theo thời gian, trong Hình (b), hệ thống thuật toán và khoảng thời gian ban đầu của điểm chuẩn phần cứng được căn chỉnh.

Kết quả cho thấy một loạt các biến, nhưng cũng khám phá thông tin quan trọng về mức tăng hiệu quả của các thuật toán biến đổi trong khoa học máy tính. Ngay lập tức:

1. Đối với các bài toán tính toán quy mô lớn, lợi ích do việc cải thiện hiệu quả của 43% hệ thống thuật toán mang lại không kém gì lợi ích do Định luật Moore mang lại.

2. Trong 14% vấn đề, lợi ích của việc cải thiện hiệu quả thuật toán vượt xa lợi ích của việc cải thiện hiệu suất phần cứng.

3. Đối với các vấn đề dữ liệu lớn, lợi ích của việc nâng cao hiệu quả của thuật toán là đặc biệt lớn, do đó, trong những năm gần đây, hiệu ứng này ngày càng rõ ràng hơn so với Định luật Moore.

Thay đổi lớn nhất xảy ra khi hệ thống thuật toán chuyển từ độ phức tạp hàm mũ sang hàm đa thức.

Cái gọi là thuật toán phức tạp hàm mũ giống như một người đoán mật khẩu của khóa kết hợp. Nhiệm vụ sẽ dễ dàng nếu chỉ có một chữ số trên đĩa kết hợp. Nếu mặt số là 4 chữ số như khóa xe đạp, người ta ước tính rằng rất khó để ai đó lấy trộm xe đạp của bạn, nhưng bạn vẫn có thể thử từng cái một. Nếu mặt số là 50 chữ số thì gần như không thể bẻ khóa và phải thực hiện quá nhiều bước.

Hình 3. Phân phối tốc độ trung bình hàng năm của 110 hệ thống thuật toán dựa trên tính toán độ phức tạp thời gian tiệm cận, trong đó quy mô bài toán là: (a) n = 1000, (b) n = 1 triệu, (c) n = 1 tỷ. Đường cải thiện hiệu suất phần cứng thể hiện tốc độ tăng trưởng trung bình hàng năm của hiệu suất điểm chuẩn SPECInt từ năm 1978 đến năm 2017

Loại vấn đề này cũng là vấn đề mà máy tính gặp phải, khi quy mô của vấn đề ngày càng lớn, nó sẽ sớm vượt quá khả năng xử lý của máy tính, vấn đề này không thể chỉ giải quyết bằng định luật Moore.

Giải pháp nằm ở việc tìm kiếm các thuật toán có độ phức tạp đa thức.

Mô tả hình ảnh

Hình 4 Đánh giá tầm quan trọng của hằng số đầu trong việc cải thiện hiệu suất thuật toán

Các phát hiện cho thấy rằng, về mặt lịch sử, lợi ích thu được từ hiệu quả thuật toán được cải thiện là rất đáng kể. Tuy nhiên, giữa hai bên có sự khác biệt về tần suất, sự cải thiện do Định luật Moore mang lại diễn ra suôn sẻ và chậm chạp, trong khi việc cải thiện hiệu quả của thuật toán là một bước nhảy vọt về phía trước, nhưng nó xảy ra ít thường xuyên hơn.

Tác giả tương ứng Neil Thompson cho biết:

Đây là bài báo đầu tiên trong ngành minh họa tốc độ cải thiện hiệu quả của thuật toán. Thông qua phân tích của chúng tôi, chúng tôi có thể biết có bao nhiêu nhiệm vụ có thể được hoàn thành với cùng sức mạnh tính toán sau khi thuật toán được cải thiện.

Khi các vấn đề phát triển về quy mô, chẳng hạn như hàng tỷ hoặc hàng nghìn tỷ điểm dữ liệu, mức tăng về hiệu quả của thuật toán vượt xa mức tăng về hiệu suất phần cứng và hơn thế nữa.

Liên kết tham khảo:

Liên kết tham khảo:

https://news.mit.edu/2021/how-quickly-do-algorithms-improve-0920

https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9540991

Biên tập viên: Sue, Tầm nhìn giữa các vì sao