MỘT Ổ ĐĨA ĐẦY ĐI MƯỢN GIÚP MÁY TÍNH CHẠY NHANH HƠN

Có những bài toán tốn ít thời gian nhưng ngốn nhiều bộ nhớ, có những bài toán thì ngược lại. Với một vài tác vụ cơ bản, các nhà lý thuyết đã chứng minh những giới hạn cứng cho sự đánh đổi này: với bộ nhớ làm việc nhỏ, bạn không thể nhanh được. Một bài báo mới cho thấy một tài nguyên kỳ lạ, một bộ nhớ đã đầy sẵn và phải được trả lại nguyên vẹn, phá vỡ những giới hạn đó.

Ổ cứng đi mượn

Mô hình này được gọi là tính toán xúc tác (catalytic computing), do Buhrman, Cleve, Koucký, Loff và Speelman đưa ra năm 2014. Một thuật toán được cấp một bộ nhớ sạch rất nhỏ, cỡ log n bit cho đầu vào kích thước n, cộng thêm một bộ nhớ bẩn khổng lồ đã chứa đầy dữ liệu tùy ý mà nó không chọn. Nó có thể dùng cả hai tùy thích, nhưng khi dừng lại, từng bit của bộ nhớ bẩn phải đúng y như cũ.

Các tác giả dùng hình ảnh quen thuộc: bạn mượn ổ cứng khổng lồ của một người bạn, đầy những kỷ niệm số quý giá, để chạy một phép tính. Bạn không muốn mất bạn, nên khi xong bạn khôi phục lại từng bit.

Ban đầu, mô hình này được đặt ra nhằm chứng minh rằng loại bộ nhớ như vậy là vô dụng. Theo trực giác, muốn khôi phục mọi thứ thì phải giữ lại toàn bộ thông tin, nên bạn chẳng bao giờ giải phóng được chỗ trống nào. Thật bất ngờ, điều ngược lại mới đúng: bộ nhớ đầy cho phép giải những bài toán mà chưa ai biết cách giải chỉ với bộ nhớ sạch. Nhưng những kết quả đó là về không gian, và các thuật toán thì cực kỳ chậm.

Nhanh hơn mức được chứng minh là có thể

Adelmo Morrison Orozco, Nathan Sheffield và Ryan Williams (MIT) nay xem xét tốc độ. Với bộ nhớ sạch cỡ logarit và một lượng bộ nhớ đi mượn cỡ đa thức, họ đưa ra các thuật toán:

• sắp xếp một danh sách và tính biến đổi Fourier rời rạc trong thời gian n^(1+o(1)), gần như tuyến tính;
• nhân ma trận trong thời gian n^(ω+o(1)), nhanh bằng phương pháp tốt nhất đã biết khi có bộ nhớ không giới hạn.

Khi không có ổ đĩa đi mượn, người ta đã chứng minh rằng tích của thời gian và bộ nhớ phải ít nhất ở cỡ n² đối với sắp xếp và biến đổi Fourier, và n³ đối với nhân ma trận. Vì vậy, các thuật toán xúc tác này đạt tốc độ mà không thuật toán bộ nhớ nhỏ thông thường nào đạt được. Các tác giả gọi đây là minh chứng vô điều kiện đầu tiên cho thấy thuật toán xúc tác vượt trội so với các thuật toán không xúc tác tương ứng.

Bật, đọc, hoàn tác

Thành phần then chốt là một mẹo tổ hợp ngắn gọn. Giả sử một thuật toán có thể chuyển một phần của bộ nhớ đi mượn giữa một giá trị chưa biết τ và τ + x, trong đó x là kết quả nó quan tâm. Trong một bảng “phụ trợ” lớn, cũng đi mượn, hãy cộng 1 vào một tập hợp ô được chọn cẩn thận. Ô ở vị trí τ tăng thêm một khi và chỉ khi x thuộc về một tập cho trước. Sau đó chạy ngược lại mọi bước, và ổ đĩa trở về như cũ, ngoại trừ một bit câu trả lời mà bạn muốn có.

Chồng mẹo này lên từng lớp một cho phép tính nhanh giá trị của các mạch nông. Rồi các tác giả viết lại mạng sắp xếp, biến đổi Fourier nhanh và nhân ma trận nhanh dưới dạng những mạch như thế. Với các phép tính số học, chỉ những lớp nhân hai đại lượng chưa biết với nhau mới tốn thêm chi phí; các lớp thuần tuyến tính gần như miễn phí.

Một phép so sánh công bằng

Có một phản bác: các giới hạn kinh điển giả định câu trả lời được ghi một lần, từ trái sang phải, trên một băng đầu ra riêng, trong khi thuật toán xúc tác ghi câu trả lời vào ổ đĩa đi mượn. Bài báo giải quyết điểm này. Các tác giả chỉ ra rằng thuật toán của họ có thể ghi câu trả lời trong hai lượt trên băng đầu ra, và với thuật toán thông thường, hai lượt chẳng giúp gì hơn một lượt. Do đó các giới hạn vẫn áp dụng, và sự phân tách vẫn đứng vững. Họ cũng chứng minh rằng một lượt là không đủ, ngay cả khi có ổ đĩa đi mượn: khi đó việc sắp xếp lại vấp phải đúng rào cản n².

Một danh sách dài những bài toán hưởng lợi

Cùng những công cụ ấy cho ra các thuật toán xúc tác nhanh để nhân số nguyên lớn và đa thức, đếm tam giác và tìm clique trong mạng lưới, phát hiện đường đi và chu trình, và so khớp mẫu văn bản có ký tự đại diện. Thời gian chạy của chúng khớp, sai khác những thừa số nhỏ, với các thuật toán tốt nhất đã biết khi có bao nhiêu bộ nhớ tùy thích. Trong mọi trường hợp, bộ nhớ đi mượn vẫn phải được trả lại đúng y như lúc cho mượn.