ÖDÜNÇ ALINMIŞ DOLU BİR DİSK BİLGİSAYARLARI HIZLANDIRIYOR

Bazı problemler zaman açısından ucuz ama bellek açısından açgözlüdür, bazılarıysa tam tersi. Birkaç temel görev için kuramcılar, bu ödünleşim üzerinde kesin sınırlar kanıtlamıştır: küçük bir çalışma belleğiyle hızlı olamazsınız. Yeni bir makale, tuhaf bir kaynağın, yani zaten dolu olan ve sağlam bir şekilde geri verilmesi gereken bir belleğin, bu sınırları aştığını gösteriyor.

Ödünç alınan sabit disk

Bu modelin adı katalitik hesaplama (catalytic computing); 2014’te Buhrman, Cleve, Koucký, Loff ve Speelman tarafından ortaya atıldı. Bir algoritma, n boyutunda bir girdi için log n bit mertebesinde minik bir temiz bellek ile, kendisinin seçmediği rastgele verilerle zaten dolu dev bir kirli bellek alır. İkisini de istediği gibi kullanabilir, ama durduğunda kirli belleğin her biti tam olarak eskisi gibi olmalıdır.

Yazarlar standart imgeyi kullanıyor: bir hesaplama yapmak için bir arkadaşınızın değerli dijital anılarla dolu devasa sabit diskini ödünç alıyorsunuz. Bir arkadaşınızı kaybetmek istemezsiniz, bu yüzden işiniz bitince her biti geri yüklersiniz.

Model ilk başta böyle bir belleğin işe yaramaz olduğunu kanıtlamak için tasarlanmıştı. Sezgisel olarak, her şeyi geri yüklemek için tüm bilgiyi saklamanız gerekir, dolayısıyla hiç yer açamazsınız. Şaşırtıcı biçimde tam tersinin doğru olduğu ortaya çıktı: dolu bellek, kimsenin yalnızca temiz bellekle nasıl çözeceğini bilmediği problemleri çözmeyi sağlıyor. Ama bu sonuçlar alan (bellek) ile ilgiliydi ve algoritmalar son derece yavaştı.

Kanıtlanmış olarak mümkün olandan daha hızlı

Adelmo Morrison Orozco, Nathan Sheffield ve Ryan Williams (MIT) şimdi hıza bakıyor. Logaritmik temiz bellek ve polinom miktarda ödünç bellekle, şunları yapan algoritmalar veriyorlar:

• bir listeyi sıralamak ve bir ayrık Fourier dönüşümü hesaplamak, n^(1+o(1)) sürede, yani neredeyse doğrusal;
• matrisleri çarpmak, n^(ω+o(1)) sürede, yani sınırsız bellekle bilinen en iyi yöntem kadar hızlı.

Ödünç disk olmadan, zaman ile belleğin çarpımının sıralama ve Fourier dönüşümü için en az n² mertebesinde, matris çarpımı için n³ mertebesinde olması gerektiği kanıtlanmış durumda. Dolayısıyla bu katalitik algoritmalar, sıradan hiçbir küçük bellekli algoritmanın ulaşamayacağı hızlara ulaşıyor. Yazarlar bunu, katalitik algoritmaların katalitik olmayan karşılıklarını geride bıraktığının ilk koşulsuz gösterimi olarak tanımlıyor.

Değiştir, oku, geri al

Temel bileşen kısa bir kombinatoryal hiledir. Bir algoritmanın, ödünç belleğin bir bölümünü bilinmeyen bir τ değeri ile τ + x arasında değiştirebildiğini varsayalım; burada x, algoritmanın ilgilendiği sonuçtur. Yine ödünç alınmış büyük bir “yardımcı” tabloda, özenle seçilmiş bir girdi kümesine 1 ekleyin. τ konumundaki girdi, ancak ve ancak x belirli bir kümeye aitse bir artar. Sonra her adımı geriye doğru çalıştırın; disk, istediğiniz cevap biti dışında, eskisi gibi olur.

Bu hileyi katman katman üst üste koymak, sığ devreleri hızla değerlendirmeyi sağlar. Yazarlar ardından sıralama ağlarını, hızlı Fourier dönüşümlerini ve hızlı matris çarpımını bu tür devreler olarak yeniden ifade ediyor. Aritmetikte yalnızca iki bilinmeyeni çarpan katmanlar ek maliyet getiriyor; tamamen doğrusal katmanlar neredeyse bedava.

Adil bir karşılaştırma

Bir itiraz şu: klasik sınırlar, cevabın ayrı bir çıktı şeridine soldan sağa bir kez yazıldığını varsayıyor, oysa katalitik algoritmalar cevaplarını ödünç diske yazıyor. Makale bu konuyu ele alıyor. Yazarlar, algoritmalarının cevabı bir çıktı şeridi üzerinde iki geçişte yazabildiğini ve sıradan algoritmalar için iki geçişin bir geçişten daha fazla yardımcı olmadığını gösteriyor. Dolayısıyla sınırlar hâlâ geçerli ve ayrım korunuyor. Ayrıca ödünç diskle bile tek geçişin yeterli olmadığını kanıtlıyorlar: bu durumda sıralama aynı n² engeline takılıyor.

Uzun bir yararlananlar listesi

Aynı araçlar; büyük tam sayıları ve polinomları çarpmak, ağlarda üçgen saymak ve klik bulmak, yol ve döngü tespit etmek, joker karakterli metin kalıplarını eşleştirmek için hızlı katalitik algoritmalar sağlıyor. Çalışma süreleri, küçük çarpanlara kadar, istedikleri kadar belleğe sahip bilinen en iyi algoritmalarınkiyle eşleşiyor. Her durumda ödünç bellek, tam olarak ödünç verildiği gibi geri dönmek zorunda.