PyTorch'ta 0/1 Sırt Çantası Problemi ve Bellek Optimizasyonu

Özet (TL;DR): Eğer PyTorch'ta varsayılan olarak torch._functorch.config.activation_memory_budget_solver=dp yapılandırmasını kullanıyorsanız, bunu dp_knapsack_sliding_hirschberg olarak değiştirerek bellek planlaması sırasındaki tepe (peak) RAM kullanımınızı 20 kat azaltabilirsiniz. Derin öğrenme modelleri geliştirirken derleyici aşamasındaki bu tür küçük yapılandırma değişiklikleri, büyük ölçekli modellerin donanım sınırlarına takılmadan çalışmasını sağlar.

Nedir? (What?)#

PyTorch, makine öğrenmesi modelinizin hesaplama grafiğini (computation graph) oluştururken onu hem hızlı hem de bellek açısından verimli hale getirmek için çeşitli optimizasyon teknikleri uygular. Bu tekniklerden biri, ileri (forward) ve geri (backward) hesaplama grafiklerini birleştirerek hangi işlemlerin bellekte saklanıp yeniden kullanılacağını (saved) ve hangilerinin tekrar hesaplanacağını (recomputed) seçmektir.

• Her işlem çalışmak için belirli bir zamana ihtiyaç duyar.
• Bellekte saklanan her işlem sınırlı RAM kapasitesinden yer tüketir.
• Geliştiriciler için buradaki temel mühendislik problemi, çalışma zamanı hızı ile bellek tüketimi arasındaki ödünleşimi (trade-off) en doğru şekilde yönetmektir.

0/1 Sırt Çantası Problemi (0/1 Knapsack Problem)#

Değerli eşyalarla dolu bir yere giren bir hırsız olduğunuzu ve en fazla 10 kilogram taşıyabilen bir sırt çantanız olduğunu hayal edin. Amacınız çaldığınız eşyaların toplam değerini maksimize etmektir. Çantaya 10 kilodan fazla yük koyarsanız çanta yırtılır ve hiçbir şey alamazsınız. Sadece küçük eşyaları seçmek gibi sezgisel (heuristic) yöntemler kullanabilirsiniz; ancak bu durumda optimal sonuca ulaşamazsınız.

İşte bu noktada devreye 0/1 Sırt Çantası (Knapsack) çözücüleri girer. Belirli bir kapasite (maksimum ağırlık) ve her birinin kendi değeri ile maliyeti (ağırlığı) olan eşya listesi verildiğinde, en optimal seçimi hesaplayan algoritmalar bulunur. PyTorch'un yaptığı işlem tam olarak budur:

• Sırt Çantası Kapasitesi: Mevcut RAM bütçesi.
• Eşyalar: Hesaplama grafiğindeki işlemler (operasyonlar).
• Değer (Value): İşlemi bellekte tutmanın çalışma zamanında (runtime) kazandırdığı süre.

dp_knapsack#

Şu anda PyTorch'taki varsayılan sırt çantası çözücüsü, problemi dinamik programlama (dynamic programming - DP) yaklaşımıyla çözen dp_knapsack algoritmasıdır. Algoritmanın mantığı kavrandığında oldukça basittir. Örneğin 4 eşya (indeks i, değer v, ağırlık w) ve 6 birimlik bir kapasite düşünelim. Hesaplamaların yapıldığı DP tablosu normalde 6 sütun (kapasite birimleri) ve 4 satırdan (eşyalar) oluşur.

Ancak pratikte sıfırlarla doldurma (padding) yapıldığı için tabloda 7 sütun ve 5 satır yer alır. Yazılım geliştirme açısından sıfırlarla doldurma (padding) tekniği kritik bir pratik çıkarım sunar:

• Her satır ve sütunun bir üst öğeye (parent) sahip olmasını garanti eder.
• İndeks aritmetiğini (index arithmetic) karmaşık sınır kontrollerinden kurtararak kodun okunabilirliğini ve bakımını ciddi ölçüde kolaylaştırır.

Bir DP Tablosu Oluşturma (Building a DP table)#

Dinamik programlama tabanlı 0/1 Sırt Çantası algoritması adım adım şu şekilde ilerler:

• Listeden bir eşya alınır ve DP tablosundaki ilgili satır boyunca sütun sütun ilerlenir.
• Mevcut sütun indeksi, o anki maksimum çanta kapasitesini temsil eder; eşyanın değeri mevcut hücredeki (satır, sütun) değerle karşılaştırılır.
• Eğer eşyanın ağırlığı mevcut sütun indeksinden büyükse, çantaya sığmayacağı için bir sonraki sütuna geçilir.
• Eğer eşyanın ağırlığı sütun indeksine eşitse ve eşyanın değeri mevcut hücre değerinden yüksekse, tablo bu yeni optimal değerle güncellenir.

Algoritma ve veri yapıları bilgisinin modern yapay zeka derleyicilerinde doğrudan karşılık bulduğunu görmek, temel bilgisayar bilimleri kavramlarını öğrenmenin önemini bir kez daha kanıtlamaktadır.