Belleğe bağlı işlev - Memory-bound function

Hafıza sınırı , belirli bir hesaplama problemini tamamlama süresinin öncelikle çalışan verileri tutmak için gereken hafıza miktarına göre belirlendiği bir durumu ifade eder . Bu, temel hesaplama adımlarının sayısının belirleyici faktör olduğu hesaplamaya bağlı algoritmaların tersidir .

Bellek ve hesaplama sınırları bazen, örneğin ön sonuçları kaydedip yeniden kullanarak veya arama tablolarını kullanarak birbirlerine karşı takas edilebilir .

Belleğe bağlı işlevler ve bellek işlevleri

Belleğe bağlı işlevler ve bellek işlevleri, her ikisinin de kapsamlı bellek erişimini içermesi bakımından ilişkilidir, ancak ikisi arasında bir ayrım vardır.

Hafıza fonksiyonları bir kullanmak dinamik programlama denilen tekniği memoization verimsizlik rahatlatmak amacıyla özyineleme oluşabilir. Çözümlerin daha sonra alt problemleri yeniden hesaplamadan tekrar kullanılabilmesi için alt problemlere çözümlerin hesaplanması ve depolanması şeklindeki basit fikre dayanmaktadır . Hafızadan yararlanan en iyi bilinen örnek , Fibonacci sayılarını hesaplayan bir algoritmadır . Aşağıdaki sözde kod , özyineleme ve hafızaya alma kullanır ve doğrusal CPU zamanında çalışır : 

 Fibonacci (n)
 {
     for i = 0 to n-1
         results[i] = -1  // -1 means undefined

     return Fibonacci_Results (results, n);
 }

 Fibonacci_Results (results, n)
 {
     if (results[n] != -1)  // If it has been solved before,
         return results[n]  // look it up.
     if (n == 0)
         val = 0
     else if (n == 1)
         val = 1
     else
         val = Fibonacci_Results(results, n-2 ) + Fibonacci_Results(results, n-1)
     results[n] = val  // Save this result for re-use.

     return val
 }

Yukarıdakileri yalnızca özyineleme kullanan ve üstel CPU zamanında çalışan bir algoritma ile karşılaştırın : 

 Recursive_Fibonacci (n)
 {
     if (n == 0)
         return 0
     if (n == 1)
         return 1

     return Recursive_Fibonacci (n-1) + Recursive_Fibonacci (n-2)
 }

Sadece özyinelemeli algoritma, özyineleme ve hatırlatma kullanan algoritmadan daha basit ve daha zarif olsa da, ikincisi, öncekinden önemli ölçüde daha düşük bir zaman karmaşıklığına sahiptir.

"Hafızaya bağlı fonksiyon" terimi daha yeni ortaya çıktı ve esas olarak XOR kullanan ve her bir hesaplamanın önceki hesaplamaya bağlı olduğu bir dizi hesaplamadan oluşan bir işlevi tanımlamak için kullanılır. Bellek işlevleri uzun zamandır zaman karmaşıklığını iyileştirmede önemli bir rol oynasa da, belleğe bağlı işlevler çok daha az uygulama görmüştür. Ancak son zamanlarda bilim adamları, spam gönderenleri kaynakları kötüye kullanmaktan caydırmanın bir yolu olarak belleğe bağlı işlevleri kullanan bir yöntem önerdiler; bu, bu alanda büyük bir atılım olabilir.

İstenmeyen postaları önlemek için belleğe bağlı işlevleri kullanma

Belleğe bağlı işlevler , internette epidemik oranlarda bir sorun haline gelen istenmeyen postayı caydırabilecek bir çalışma kanıtı sisteminde yararlı olabilir .

1992 yılında, IBM, araştırma bilim adamları Cynthia Dwork ve Moni Naor kripto 1992 başlıklı bir makale yayımladı İşleme aracılığıyla Fiyatlandırma veya Mücadele Önemsiz Posta kullanmanın bir olasılık akla CPU-ciltli spam göndermek gelen kötüye kullananların caydırmak için işlevler. Plan, kaynağı kötüye kullanma maliyetinin ihmal edilebilir olması durumunda, bilgisayar kullanıcılarının bir kaynağı kötüye kullanma olasılığının çok daha yüksek olduğu fikrine dayanıyordu: İstenmeyen postanın bu kadar yaygınlaşmasının altında yatan neden, e-posta göndermenin istenmeyen posta gönderenler için çok düşük maliyete sahip olmasıdır.

Dwork ve Naor, pahalı bir CPU hesaplaması biçiminde ek bir maliyet enjekte ederek istenmeyen postaların azaltılabileceğini öne sürdü : CPU'ya bağlı işlevler, her mesaj için gönderenin makinesindeki CPU kaynaklarını tüketir ve böylece çok büyük miktarlarda istenmeyen postanın gönderilmesini engeller. kısa süre.

Suistimallere karşı korur temel düzeni aşağıdaki gibidir:
Let S , gönderen olmak R alıcı olabilir ve M bir e-posta olun. Eğer R e-posta almak için önceden kabul etti S , daha sonra M normal şekilde iletilir. Aksi takdirde, S bazı G (M) fonksiyonlarını hesaplar ve (M, G (M)) ' yi R'ye gönderir . R , S'den aldığı şeyin (M, G (M)) biçiminde olup olmadığını kontrol eder . Evet ise, R M'yi kabul eder . Aksi takdirde, R , M'yi reddeder . Sağdaki şekil, önceden anlaşmanın olmadığı durumları göstermektedir .

G () fonksiyonu , R ile doğrulama nispeten hızlı olacak (bir milisaniye sürüyor) ve S ile hesaplamanın bir şekilde yavaş olacağı (en az birkaç saniyeyi içeren ) olacak şekilde seçilir . Bu nedenle, S'nin önceden anlaşma olmaksızın M'yi birden çok alıcıya göndermesi engellenecektir : G () hesaplamanın hem zaman hem de hesaplama kaynakları açısından maliyeti, milyonlarca e-posta göndermek isteyen bir spam gönderen için tekrar tekrar engelleyici hale gelecektir. .

Yukarıdaki şemayı kullanmanın en büyük sorunu, hızlı CPU'ların yavaş CPU'lardan çok daha hızlı işlem yapmalarıdır. Ayrıca, üst düzey bilgisayar sistemleri, aynı zamanda, hesaplamaları kolaylaştıran karmaşık boru hatlarına ve diğer avantajlı özelliklere sahiptir. Sonuç olarak, son teknoloji ürünü bir sisteme sahip bir spam gönderen, bu tür caydırıcılıktan neredeyse hiç etkilenmezken, vasat bir sisteme sahip tipik bir kullanıcı olumsuz bir şekilde etkilenecektir. Bir hesaplama yeni bir bilgisayarda birkaç saniye sürüyorsa , eski bir bilgisayarda bir dakika ve bir PDA'da birkaç dakika sürebilir ; bu, eski bilgisayar kullanıcıları için bir sıkıntı olabilir, ancak PDA kullanıcıları için muhtemelen kabul edilemez. İstemci CPU hızındaki eşitsizlik, CPU'ya bağlı bir işleve dayalı herhangi bir şemanın yaygın olarak benimsenmesinin önündeki en önemli engellerden birini oluşturur. Bu nedenle araştırmacılar, çoğu bilgisayar sisteminin yaklaşık olarak aynı hızda değerlendireceği işlevleri bulmakla ilgilenirler, böylece ileri teknoloji sistemler bu işlevleri düşük kaliteli sistemlerden biraz daha hızlı değerlendirebilir (2-10 kat daha hızlı, ancak 10-100 kat değil daha hızlı) CPU eşitsizliklerinin ima edebileceği gibi. Bu oranlar , amaçlanan uygulamalar için yeterince " eşitlikçi " dir: işlevler, kötüye kullanımları caydırmada etkilidir ve geniş bir sistem yelpazesinde meşru etkileşimlere engelleyici bir gecikme eklememektedir.

Yeni eşitlikçi yaklaşım, belleğe bağlı işlevlere güvenmektir. Daha önce belirtildiği gibi, belleğe bağlı bir işlev, hesaplama süresine belleğe erişmek için harcanan zamanın hakim olduğu bir işlevdir. Belleğe bağlı bir işlev, büyük bir bellek bölgesindeki konumlara öngörülemeyen bir şekilde, önbellek kullanımının etkili olmayacağı şekilde erişir. Son yıllarda, CPU'nun hızı önemli ölçüde arttı, ancak daha hızlı ana bellek geliştirmede nispeten küçük ilerleme kaydedildi. Yana oranlar arasında hafıza latanslarında son beş yıl içinde inşa makinelerin tipik ikiden büyüktür ve hemen hemen her zaman daha az dörtten, hafıza-ciltli fonksiyon öngörülebilir gelecekte en sistemlerine eşitlikçi olacaktır.

Ayrıca bakınız

Referanslar

Dış bağlantılar