MIT Açık Ders malzemeleri

http://ocw.mit.edu

6.046J Algoritmalara Giriş, Güz 2005

Bu materyallerden alıntı yapmak veya kullanım şartları hakkında bilgi almak için:

Erik Demaine ve Charles Leiserson, 6.046J IntroductiontoAlgorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare). http://ocw.mit.edu (Giriş Tarihi: 08, 01, 2010). Lisans: Creative CommonsAttribution-Noncommercial-ShareAlike.

Not: Lütfen atıf taparken bilgilere eriştiğiniz gerçek tarihi kullanınız.

Atıflar ve Kullanım Koşulları konusunda daha fazla bilgi için:

http://ocw.mit.edu/terms ve http://www.acikders.org.tr sitesini ziyaret ediniz.

Ders 24

-- 6.046 haftası. Oooo..Bu son haftanın konusu, ileri düzeydeki konularımız arasında olan önbelleği dikkate almayan yani “cache oblivious” algoritmalar. Oldukça eğlenceli bir alan, benim için de özel yeri olan bir konu, çünkü üzerinde pek çok araştırma yaptım. Bu alan, Prof.Leiserson’un ortak katkılarıyla kuruldu. Gerçekten, Prof.Leiserson’la ilk buluşma konumuzu, onun önbelleği dikkate almayan algoritmalar hakkındaki konuşması oluşturmuştu. Sanırım, 1999da, Vancouver’daydı. İlginç bir yıldı. Böylece, önbelleği dikkate almayan algoritmalar hakkında o tarihlerde bilgi edindim ve bu alanda çalışmaya başladım. Eğlenceli bir alandır. Ancak, konu bazı bakımlardan bu sınıf için de geliştirildi. Yanılmıyorsam, bir sömestr galiba ’98-’99 da bütün problem setleri, önbelleği dikkate almayan algoritmalar içerikli idi.

Ve özellikle aynı zamanda araştırma fikirleri oluşturuyorlardı. Bu yönleriyle canlı, neşeli bir sömestr idi. Bu Sömestrde de bunu yapmayı düşündük, ama basite indirgedik. Tahmin edeceğiniz üzere önbelleği dikkate almayan algoritmalar hakkında günümüzde daha fazla şey biliyoruz. Evet, sanırım genel bilgi bundan ibaret. Bir grup MIT öğrencisi, bunların içinde özellikle Mühendis Harold Prokop tarafından geliştirilmiş demek istiyorum. Bu onun Yüksek Mühendislik teziydi. Şimdilik vereceğim bütün atıflar bunlar. Henüz bitirmedim, ancak web sayfamda yeralan bazı ders notları var. Fakat, bunlara, anlatacağım her şeyin olduğu kurs web sayfasına ayrıca bağlantılar yapacağım. Bunların hepsi, aşağı-yukarı son beş yıl içinde, özellikle ilk makalenin basıldığı ’99 yılından itibaren yapılmış bulunuyor.

Ve bu konu, nispeten yüksek seviyede olmasına rağmen, geçen haftanın konusu olan çok izlekli algoritmalar ile de ilişkili olup; modern makinelerdeki paralellik konusuyla da ilgilidir. Ve bu son iki ders boyunca, rastgele erişim yaptığımız çok basit model bilgisayarlarda olduğu gibi bu bilgisayarın belleğindeki herhangi birşeye tek maliyet ile girebilirsiniz. Belleğin bir kelimesini okuyabilir ve yazabilirsiniz. Bir kelimenin ne kadar büyük olabileceği ve daha bir sürü şey hakkında bazı ayrıntılar da mevcuttur ama çok özlü, sade ve düz bir modeldir. Belki, çok izlekli hesaplamadaki fikre göre bir anda hareket ediyor, buna rağmen belleği çok düz. Herkes bu belleğe sabit bir maliyetle giriş yapabilir. Şimdi o modeli değiştireceğiz.

Ve gerçek makinanın, gerçek makinanın belleğinin, bazı hiyerarşileri olduğunu kavrayacağız. CPU’larınız, bazı önbellekleriniz, muhtemelen, aynı yonga üzerinde, birinci düzey önbellek, 2.düzey önbellek var, eğer şanslı iseniz, ana belleğe varmadan önce, 3.düzey önbellekleriniz de var. Ve dahası, belki gerçekten büyük bir diskiniz var ve belki orada da bazı önbellekleriniz var, ama ben bunlar hakkında hiç düşünmeyeceğim bile.

Böylece belirtmek istediğim şu, çok sayıda farklı düzeyde belleğiniz var, burada değişen, CPU’ya çok yakın olan şeylere erişmekte çok süratli olması. Genellikle birinci düzey önbelleğe bir “cycle” ya da çevrimde veya daha az zamanda erişebilirsiniz. Sonrasında, bu hız giderek azalır. Belleğin maliyeti, hala 70 nanosaniye kadardır. Bu da uzun bir zaman. 70ns, şüphesiz çok uzun bir zaman.

Yani, buradan başladığımızda gittikçe yavaşlıyoruz. Aynı zamanda daha büyüyoruz. Başka bir deyimle, eğer her şeyi önbelleğin birinci düzeye koyabilseydik, sorun çözülmüş olurdu . Ancak düz bellek ne hale gelirdi. Herşeye bu düzeyde erişmenin aynı miktarda zaman alacağını varsaydık. Ama, genellikle buna yer ayıramayız, ayrıca, herşeyi birinci düzey belleğine koymak da mümkün değildir. Yani bir bellek hiyerarşisi olmasının da bir nedeni var, demek istiyorum. Bu nedenin ne olduğu hakkında bir şey söyleyecek olan var mı?

Hayattaki bazı limitler gibi bir şey. Yani? Hızlı bellek pahalı. Bu da pratikteki gerçek limit 1. düzeyde gittikçe daha fazla bellek oluşturmaya çalışabilirsiniz, belki gayret sarfedeblirsiniz, ama masraflar da önemli bir limittir ve pratikte bazı şeylerin sadece bulundukları ölçüde olmalarının da belki de nedenidir Ama, biran için belleğin gerçekten ucuz olduğunu varsayın. Bazı şeylerin gelişiminde fiziki limitlerin de yeri vardır. Işığın hızı gibi. Önemli bir sorun, değil mi? Ne kadar olursa olsun bir atoma sadece belli sayıda parça yükleyebileceğinizi varsayalım. Bu, belli bir alan içine sadece o kadar parça yükleyebileceksiniz demektir. Eğer daha fazla parça isterseniz, daha fazla alana ihtiyacınız olacak, daha fazla alana sahip olmanız, bir gidiş-dönüş yapabilmeniz için daha uzun zaman gerektirecek demektir. Netice olarak, CPU’nuzu uzayda bu nokta gibi, nispeten küçük ve verinizi içine alması gereken yeterlikte varsayarsanız, veriyi arttırdığınız ölçüde uzakta olması gerekir.

Ancak, CPU etrafında bu çekirdeklerin olduğunu, 3- boyutta olmadığımızı,yongaların genelde 2-boyutlu olduklarını biliyoruz ama, aldırmayalım. CPUya yakın olan ve erişilmesi daha hızlı olan küreye daima sahip olabilirsiniz. Buradan uzaklaştığınız ölçüde maliyet artar. Fizik, geometri ve sair disiplinlerde genelleştirilmiş olmasına karşın, bu modelin özü itibariyle temsil ettiği budur.

Bu belleği elde etmek için gidiş-dönüş zamanındaki gecikme büyük olmalıdır. Genel olarak belleğe erişim maliyeti iki şeyden oluşur: Bunlar gecikme ve özellikle ışık hızı ile sınırlanan gidiş-dönüş zamanıdır. Gidiş-dönüş zamanına ek olarak, veriyi dışarı çıkarmanız da gerekir. Ne kadar veri istediğinize bağlı olarak o kadar fazla zaman alacaktır. Öyle ise, bir şey daha var. Bunun, veri miktarı bölü band genişliği olduğunu hemen söyleyelim. Band genişliği veriyi dışarı alma hızıdır. Buradaki faklı belleklerin band genişliklerine bakarsanız, aşağı yukarı hepsi aynıdır. Gerçekten, iyi tasarlanmış bir bilgisayarınız varsa band genişliklerinin hepsi de aynı olmalıdır.

Yani, diskteki veriyi, gene de gerçekten hızlı bir şekilde, genellikle veri yolunun CPU’ya yani merkezi işlem birimine ulaşım hızıyla çıkarabilmeyi beklersiniz. Yani çıkışa gönderme gittikçe yavaşlasa da bu, sadece gecikme nedeniyle daha yavaş olur. Öyleyse, bu belki de makuldür. Genelde band genişliği aynı gibidir. Artan gecikme’dir. Öyle ise, gecikme artarken bizim hala aynı miktar band genişliğini bölmemiz gerekiyorsa, tüm bu düzeylerdeki erişim maliyetlerini yaklaşık aynı seviyede tutmak için ne yapmamız gerekir?

Bu sabit.. Pardon bu artıyor diyelim. Ama bu hala büyük kalıyor. Bu formülü dengelemek için ne yapabiliriz? Miktarları değiştirmek. Gecikme arttığına göre, miktarı arttırırsak, bir elemana amortize edilmiş giriş maliyeti de düşecektir. Demek ki bu, en basit anlamda amortizasyon oluyor. Öyleyse, buna tüm bloka erişim dıyelim, bu da blokun boyutu. Öyleyse bir elemana erişim için amortize edilmiş maliyet : gecikme bölü blokun boyutu, yani miktarı, artı 1 bölü band genişliğidir. Pekala, şimdi ister istemez şunu düşünmelisiniz. Demek ki, burada sadece ‘miktarlara’ bölüyorum, çünkü ‘miktar’ bir erişimde elde ettiğiniz eleman sayısı olur.

Pekala, böylece, amortize maliyet için, bu formülü elde ediyoruz. Bir bölü band genişliğinin hangi seviyede olursak olalım iyi olacağını iddia ediyorum. Burada, pahalılık dışında kayda değer gerçek hiçbir sınırlayıcı yok. Ve gecikme de, amortizeleri miktarları götürüyor, öyleyse, gecikme ne olursa olsun burası daha fazla büyüyor, gittikçe daha fazla şey elde ediyoruz, sonra bu iki terimi eşitliyoruz. Dengelemede, bu iyi bir yol olacak. Burada özellikle disk’in gerçekten yüksek gecikmesi vardır. Sadece ışığın hızı değil, disk’in izlerinde kafanın hareket hızı da söz konusu olur. Diğer şeylerin hiçbiri, genellikle fiziki bir harekete sahip değildir. Sadece elektrik olaylarıdır. Dolayısıyla, diskteki gecikme oldukça yavaşlatıcı bir faktördür ve bunun neticesinde, disk’ten bir şey okumak istediğinizde daha çok veri okumalısınız, örneğin bir megabayt civarında. Belki bu günlerde bu değer çoktan eskidi ve bu değeri günümüze uyumlu hale getirmek isterseniz, diskten bir şey okurken, belki birkaç megabayt okursanız bunları uyumlu hale getirebilirsiniz..

Bunu yapmakta bazı sorunlar vardır. Sorunun ne olduğu hakkında bir görüş var mı?. Yani , bu algoritma var ve disk’ten bir şey okuduğu zaman, sorguladığı elemanın etrafındaki bir megabyte tutarında diğer verileri de okuyor. Böylece, erişim için gereken amortize maliyet makul olabilir. Fakat bunu yaparken aslında bir şeyleri de varsaymak gerekli değil mi? -- Doğru. Yani geri kalan veriyi kullanacağımı varsayıyorum. Eğer istediğim bir bilginin etrafındaki 10MB bilgiyi kullanacaksam, A köşeliparantez I’ya erişim yaptığımda A etrafındaki I’ dan 10 milyon öge elde etmiş olursam, bu oldukça iyi bir şey olur tabii; eğer algoritmada bu veriyi bir amaç için kullanacaksa bu anlamlı olabilir.

Böylece bu “spatial locality” yani mekansal yerellik olacaktır.. Önbelleği dikkate almayan ve önbellek duyarlı algoritmaların dünyasında bu olduğunda, siz iyi performans gösteren algoritmalarlar istersiniz. İşte, bloklama fikri budur. Yani algoritmanın, bir blok içindeki elemanların tümünü, ya da en azından büyük bir kısmını kullanmasını, bunun neticesi olarak bir miktar belleği buna ayırnasını istiyoruz. İşte buna mekansal yerellik deniyor. Çünkü o zaman, ideal olarak hepsini kullanabiliriz. Ancak, algoritmanıza göre, bu biraz şaşırtıcıdır. Çünkü burada başka bir mesele daha var. Yani erişim yaptığınız şeyi, 10MB’ınızı ana belleğe okuyorsunuz ve bugünlerde en azından 4GB boyutunda bellekler var. Bu kapasitenizle, ana belleğe gerçekten farklı pek çok blok kaydedebilirsiniz. İstediğiniz, bu blokları mümkün olan en uzun süre boyunca kullanmak, ama belki de hiç kullanmayacaksınız. Eğer doğrusal zamanlı bir algoritmanız varsa, belki her elemanı sabit sayıda birkaç defa ziyaret edeceksiniz. Öyleyse, bu yeterli. Ama, algoritmanız doğrusal zamandan daha fazla ise, elemanlara birden fazla erişim yapacaksınız.

Sonuç olarak, bloku tamamen atmadan önce, bloktaki tüm elemanları sadece birer kere değil bir kaç kez kullanmanız iyi fikir olacaktır. Buna zamansal yerellik yani “temporal locality” diyoruz. Yani, ideal olarak blokları istediğiniz kadar, tekrar tekrar kullanıyorsunuz. Yani, tüm bu önbelleklere zaten sahibiz demek istiyorum. Bu kelimeyi önceden yazmamışım.

Bu önbellekleri birşey için kullanmalıyız. Gerçekten, bir bloktan fazla veri alabilirler..Bir önbellek birkaç blok depolayabilir Kaç tane mi? Birazdan göreceğiz. Pekala, genel amaç bu, ama bu noktada model hala güzel değil. Bu tür bir makinede doğrudan iyi çalışan bir algoritma tasarlamak isterseniz, mümkündür ama çok güçtür ve gerçek makinelere benzemesine karşılık, şimdiye kadar hiç yapılmadığını söylemeliyim.

En azından teorik ve daha çok pratik açıdan esas mesele aynı anda iki düzeyde düşünmek gerektiğidir. Doğal olarak bu, konunun bu modelde basitleştirilmiş bir ifadesi olur, ancak algoritmalarla ilgili pek çok şeyler söyleyebiliriz. Özetlemek gerekirse, bu modelde, her bir düzeyde farklı toplam boyutlar bulunur ve bu nitelikleri ile bu model, üzerinde çalışılması ve algoritmaların tasarlanması açısından çok karmaşıktır. Oysa, sadece iki düzey boyutunu düşünürseniz çözümü nispeten kolaydır.

Özetle, sabit sayıda kayıt olduğunu varsaydığımız CPU’muz var. İçinde birkaç veri olunca, bunlara ilaveler ve daha neler yapabileceğinizi biliyorsunuz. Sonra, burada gerçekten hızlı bir boru var. Onu, bazı önbelleklere doğru ve kalın şekilde çiziyorum. İşte önbellek bu. Ve, ana bellek dediğim, bu gerçekten büyük depoya bağlanan nispeten dar bir borumuz var. İşte, genel görüntü bu. Şimdi burası, herhangi iki düzeyi temsil edebilir. Bu L3 ön belleği ve “make memory” yani “üretilen bellek” arasında yer alabilir. Bu ne olabilir? İsim vermek, en iyisi. Veya önbellek makinenin RAM’ı telakki ettiğimiz, gerçek anabelleği olabilir. Oradaki bellek de, diskin belleği olabilir. Önemsediğiniz her şey olabilir. Genellikle bir programınız varsa, herşeyin ana belleğe sığdığını varsayarız.

Sonra, önbelleğin davranışı üzerinde durursunuz. Belki, bu iki düzeyin arasına bakarsınız. Burası, dahili programı muhtemelen en fazla ilgilendiren bölümdür, çünkü buradaki maliyet türevi buradaki maliyet türevine nispeten gerçekten çok büyüktür. Eğer veriniz, ana belleğe sığmıyorsa ve disk’e gitmek zorunda kalıyorsanız, bu düzeye gerçekten önem veriyorsunuz demektir, çünkü maliyet türevi burada çok büyüktür. 6 haneli büyüklükte olduğunu söyleyebiliriz. Dolayısıyla, pratikte sadece iki bellek düzeyi düşünürseniz, bu en uygunu olur.

Pek ala, şimdi bazı parametreleri tanımlayacağım. Sadece anlaşılır kılmak için, bunları ön bellek ve “make memory” olarak adlandıracağım, çünkü anabelleği olduğu gibi düşünmek istiyorum . Böylece şimdi üzerinde durmamız gereken ek kavram bu önbellek denilen şey. Belirli sınırda boyutlu ve bir blok boyutu var. Blok boyutu B ve birkaç blok da M bölü B ediyor. Böylece önbelleğin toplam boyutu M’ dir. Pekala, ana bellek de B boyutunda bloklarla bloklanmış. Biz bunun boyutunu sonsuz kabul ediyoruz. Bu resimdeki boyutunu dikkate almıyoruz. Algoritmanızın, verinizin yapısını içine alacak kadar büyük boyutta olduğunu varsayıyoruz.

Evet, genel model bundan ibaret. Ve ayrıntılarına girmek istemediğim acayip, tarihi nedenlerle bu şeyler, büyük M ve büyük B olarak adlandırılıyor. M, çağrışımla “memory” yani bellek gibi gelse de, önbellekten ibaret. Nedenini sormayın. Pekala, geçmişini böylece andık. Şimdi bu model ile ne yapacağız? İyi görünüyor, fakat onunla ilgili ne ölçeceğiz? Önbelleğin gerçekten hızlı olduğunu varsayacağım. Böylece CPU önbelleğe anında erişim yapabilir. CPU’nun yaptığı hesaplama için ise, gene de bir maliyetim var; önbelleğin yeter derecede yakın olduğunu varsayarak buna aldırmıyorum. O bellek çok büyük olduğu için, uzak olması gerekiyor ve bu nedenle bu boru sorun oluşturuyor. Almam gereken veri için bu boru kalın ama gerçekten çok uzun. O halde, gecikme büyük olacak.

Band genişliği hala yüksek. Burada tüm transferler bloklar halinde yapılmış. Dolayısıyla, başka bir işlem olmadığı zaman, CPU bellekteki A’ nın I’ sını istediğinde, bu önbellekte ise temin edebilir. Bunun maliyeti yoktur. Aksi halde CPU, aranan elemanı içeren bloku, ana bellekte yakalar, önbellek dolu ise bazı elemanları atar ve aradıklarını önbelleğe taşıdıktan sonra veriyi kullanabilir ve bu böyle devam eder. Önbellekte olmayan bir şeye gereksinim duyarsa, o zaman onu ana bellekte bulup alması gerekir.

Bir şeyi attığınız zaman, aslında geri dönüp belleğe yazıyorsunuz. İşte, model bu. Demek ki, önbelleğe erişimleri ücretsiz varsayıyoruz. Ama algoritmanın koşma süresi üzerinde hala düşünebiliriz. Koşma süresinin tanımını değiştirmeyeceğim. Bu hesaplama süresi olarak kalacak, veya çok izlekli lingosunu yani dilini kullanmak isterseniz, hesaplama süresine iş diyeceğim. Pekala , öyleyse, hala zamanımız var ve N’ nin T’ sinin anlamı, eskiden yapılanlar olacak. Şu anda yaptığımız, ne olup bittiğini daha iyi anlamaktan ibaret. Özü itibariyle, bellek sisteminde yararlanabileceğimiz paralelliği ölçmedir; bir şeye eriştiğiniz zaman, aslında B sayıda ögeyi elde edersiniz.

Bunlar eski uygulamalar. Şimdi yapmak istediğim, bellek aktarımlarını ölçmek. Bunlar blokların transferleri. Öyle ise, iki düzey arasındaki blok bellek transferleri, yani önbellek ile ana bellek arasında. Demek ki bellek transferleri, aslında, okunanı veya yazılanı okuma. Belki bunu belirtmeliyim. Bunlar, ana-bellekten okunanlardan ve oraya yazılanlardan oluşan bloklardır. Şimdi, yeni bir simgelemi tanıtacağım. Bu yeni bir simgelem ve işlerin nasıl yürüdüğüne bakacağız. N’ nin MT’ si. N boyutlu problemin süresi yerine sadece bellek transferlerinin sayısını ele almak istiyorum. Böyle bir fonksiyon sadece N’ ye değil, aynı zamanda, modelimizdeki B ve M parametrelerine de bağlıdır. Yani aslında (N), olması gerekiyor, ama görüldüğü gibi bu karmaşık olduğu için, ben, MT (N)’ye bağlı kalacağım.

Fakat bu, büyümeyi esas itibariyle daima N cinsinden önemsememden; büyümeyi her şey açısından önemsiyorum, ancak değiştirebildiğim tek şey N. Nitekim, biz yinelemeleri yazarken olduğu gibi, çoğunlukla yalnız N’nin değiştiğini düşünürüz. Blok boyutunda yineleme yapamam. Önbelleğin boyutu üzerinde de yineleme yapamam. Bunlar bana verilmiş, sabit büyüklüklerdir. Öyleyse, esas itibariyle N’ yi değiştireceğiz. Fakat, B ve M burada daima önemlidir. Sabit değildirler. Modelin parametreleridirler.

Pekala, oldukça kolay. Buna disk erişim modeli denir; modelleri çok seviyorsanız, isterseniz dış bellek modeli veya önbelleğin bilincinde olan model diyebilirsiniz.. Belki bunu tekrar belirtmeliyim. Bu önbelleğin farkında olan yani cache aware bir modeldir. Genel olarak bu çeşit modellerde, bu makine modelinde çalışan bazı algoritmalar vardır. Bu önbelleği önemseyen bir algoritmadır. Biz önbelleği önemseyen algoritmalarla çok ilgilenmiyoruz. Bir tanesini görmüştük, B ağaçlarını. B ağaçları, önbelleği önemseyen veri yapılarıdır. Bunun altında B boyutunda bazı bloklar olduğunu varsayarsınız. Gördüğünüz model belki tam olarak bu değildi. Özellikle, önbelleğin büyüklüğünün ne olduğuna pek aldırmazsınız; çünkü B sayıda öğeyi okuduğumda, hepsini istediğim kadar kullanabilir ve B sayıda ögenin neresine sığacağını anlayabilirim ve bu da bana log N yerine B tabanında log N sayıda bellek transferi verir. Ve bu da tercih ettiğiniz dengeli ikili arama ağacını kullanma durumunuzdaki performans olur.

Özetle, N’nin, B tabanlı logaritması, N’nin 2 tabanlı logaritmasından kesinlikle daha iyidir. B ağaçları, ön belleği önemseyen algoritmalardır. Bugün ve gelecek derste, önbelleği dikkate almayan yani cache oblivious algoritmaları elde etmeye çalışacağız. Önbelleği önemseyen ile dikkate almayan algoritmalar arasında, özü itibariyle sadece bir tek fark vardır. Önbelleği dikkate almayan algoritmalarda, algoritma B ve M’ nin ne olduğunu bilmez. Bu biraz zorlayıcı ancak çok da ilginç bir fikirdir.

Makinenin modelinin bu olduğunu varsayıyorsunuz ve bu M boyutundaki önbellek ile, B bloku yani, ana bellek ile B bloku arasındaki bellek transferleriyle ilgileniyorsunuz. Fakat, modelin ne olduğu nu hiç bilmiyorsunuz. Modelin diğer parametrelerini bilmiyorsunuz. Buna benziyor ama, enini bilmiyorsunuz. Yüksekliğini bilmiyorsunuz. Neden olmasın? Yani B ve M’nin ne olduğunu analizler biliyor. Şimdi, ders süresince gördüğümüz eski, sıkıcı algoritmalara benzeyen bazı algoritmalar yazacağız.

Bu modelin güzel taraflarından biri de bu. Gördüğümüz algoritmaların önbelleği dikkate almayan algoritmalar olduğunu biliyoruz, çünkü bu sınıfta bugüne kadar önbellek kelimesini dahi bilmiyorduk. Böylece, içlerinden seçebileceğimiz pek çok algoritma var. Tabii, bunların arasından bazıları bu modelde iyi işleyecek, bazıları ise işlemeyecek. Bu yüzden, B ile M ne olurlarsa olsun, tıpkı eski algoritmalarımızda olduğu gibi, iyi işleyecek algoritmalar tasarlamak istiyoruz. Başka bir deyişle, eğer önbelleği dikkate almayan iyi bir algoritmanız varsa, B ve M’ nin her değerinde iyi çalışması gerekir.

Bu varsayımın bazı sonuçları var. Önbelleği önemseyen bir algoritmada, belleğimi B boyutta parçalar halinde bloklarım, diyebilirsiniz. İşte buradaki gibi.. Bu B elemanlarını şurada , bu B elemanlarını da burada depolardım; B’yi bildiğiniz için bunu yapabilirsiniz. Pekala, şimdi bu B elemanlarını önbelleğe okumak, sonra bunları buraya yazmak istiyorum, diyebilirsiniz. Böylece, önbelleğinizi tartışmasız bir şekilde muhafaza edebilirsiniz. Oysa, önbelleği dikkate almayan algoritmalarla bunu yapamazsınız, çünkü ne olduğunu bilmezsiniz.

Yani, her şeyin varsayımsal olması lazım. Disk için hariç, zaten önbellekler, daha ziyade bu şekilde çalışırlar. Öyleyse, oldukça akılcı bir model, özellikle, önbellekte olmayan bir elemana erişim yaptığınızda, o elemanı içeren bloku otomatik olarak ele alırsınız. Ve, eğer, o blokta değil ise, bir bellek transferi bedeli ödersiniz. Pekiyi, ya önbelleğiniz dolu ise? O takdirde, önbelleğinizden bazı blokları atmak zorundasınız. Öyleyse, blokun atılabileceği bazı modellere ihtiyacımız var, çünkü bu durumu biz kontrol edemiyoruz. Algoritmamız içinde blokların ne oldukları hakkında hiç bilgimiz yok. O halde, bu modelde varsayacağımız şey ideal durum; yani, yeni bir bloku aldığınızda, önbelleğiniz dolu ise, en son kullanılacak bir bloku kapı dışarı etmek olacak.

Özür dilerim, ’zaman’ açısından, en son; ‘mesafe’ açısından değil. ‘En ilerdeki’, zamanı, en uzak geleceği ifade ediyor. Bu da, yapılması mümkün en iyi şey oluyor. Uygulamada, yapılması biraz zor, çünkü kahin değilseniz genellikle geleceği bilemezsiniz. Yani bu biraz ideal bir model. Ama çok akılcı, eğer 20 numaralı notu okuduysanız, Sleator ve Tarjan o belgede, rekabetçi algoritmalar fikrini ileri sürüyorlar. Liste depolamada ön buluşsal bir yeri olan bu belgenin, sadece küçük bir kısmını anlatmış oldum.

Ama bu not, bu tür stratejiler olduğunu doğruluyor. Belki bu konuyu etütte duymuşsunuzdur. Bazıları bu konuya değindiler, bazıları ilgilenmedi. Buna strateji sayfalaması deniyor. Yani, sayfalardan veya bloklardan oluşan belli miktarı önbellekte muhafaza etmek istiyorsunuz ve sadece önbelleğiniz de olmayan bir bloka erişim yaptığınızda, bir şey ödüyorsunuz. Yapılacak en iyi şey, en son kullanılacak bloku atarak kalan diğer blokları kullanmak. Eğer geleceği biliyorsanız, bu offline yani çevrimdışı en iyi strateji olur.

Fakat, bu stratejiye karşı, özü itibariyle devamlı rekabetçi olan algoritmalar var. Bunların ayrıntılarına girmek istemiyorum, çünkü gerçekte her zaman rekabetçi değiller. Fakat bu dersin amaçları bakımından öyle farz edebiliriz; detayları konusunda endişelenmeyin. Genellikle, bu konudaki varsayımı hiç kullanmıyoruz bile. Önbelleği dikkate almayan model, işte budur. Yapılması gereken herhangi bir şeyin yapılacağı düşüncesi, her şeyi daha da netleştiriyor.

En iyi yerine en rekabetçiyi kullanmak istediğinizde de iyi, buluşsal, ne varsa onu simüle edebilirsiniz. Tamam, önbelleği önemsemeyen algoritmalar hakkında bu kadar yeter. İki düzeyli bir modeli elde ettiğinizde, B ve M’ yi bilmediğinizi farz edin. Bu otomatik talep ve benzerleri yazılımda var. Çizimlerin hepsini tablo şeklinde yapacağımdan bu evrede daha anlaşılır olması için biraz daha konuşmak gerekli.

Demek ki, doğrusal düzenin ne olduğu belli değil. Doğrusal düzen, okuma sırasıdır. Her zaman açıkça söylemesek de, tipik model belleğin doğrusal bir dizilim olduğu haldir. Programınızda depoladığınız her şey, bu doğrusal dizilimde yazılıdır. Assembly ve benzeri programlamalardaki model budur. Bir adres alanınız var. Ve, burası ile şurası arasında herhangi bir sayı bu alan olabilir. Buna fiziksel bellek diyoruz. Yazabileceğiniz alanın hepsi bu. Görüldüğü üzere, 0’da başlıyor ve buraya, sonsuz diyeceğimiz yere kadar gidiyor. Kim bilir? Pekala, genellikle bunu fazla düşünmeyiz. Şimdi beni ilgilendiren, bu görünümde belleğin bloklanmış olduğu. Başka deyimle, parçanız belleğe nasıl yerleşmiş olursa olsun, B uzunluğunda bloklarla gruplanmıştır.

Eğer buna bir dersem daha iyi olacak. Bu B. Bu B pozisyonu artı bir. Bu 2B ve 2B artı bir, ve saire. Bunlar, bellek içindeki anahtar listeleri. Bu, bloğun nasıl oluştuğunu gösteriyor. Burada bir şeye erişim yaptığınızda, şu bloku U’dan alırsınız, B’nin bir önceki katına veya bir sonraki katına yuvarlarsınız. Bu, her zaman böyle olur. Bazen buraya özgü bir dizilimi ele alırsanız, o dizilimin belki de bloklarla uyumlu şekilde dizilmemiş olabileceğini daima hatırınızda tutmalısınız. Fakat genellikle uyumlu olacağı için, fazla üzerinde durmuyoruz. Ancak burada hassas bir durum olabilir. Model hakkında bilmeniz gerekenler bunlar.

Özetle, B ağaçları hariç, gördüğümüz her algoritma, önbelleği dikkate almayan bir algoritmadır. Ve sorumuz, her şeyin koşma süresi açısından ne olduğunu biliyoruz ama şimdi bellek transferlerini, MT(N)’ sini ölçmek istiyoruz. Bir başka gerçek veya teoremi belirtmek istiyorum. Kesin şekilde tanımlamak istemediğim için, köşeli parantez içine alıyorum. Eğer iki seviyede etkin bir algoritmanız varsa, başka bir deyimle, buradaki gibi algoritmanız iki düzeyli bir dünyada etkiliyse ve önbelleği önemsemeyen bir algoritma ise, bellek hiyerarşisinin örneğin L sayıdaki düzeyinde de etkilidir. Ama, ‘etki‘ nin ne olduğunu tanımlamak istemiyorum.

Fakat sezgisel olarak, eğer makineniz gerçekten buna benziyor ise ve önbelleği önemsemeyen bir algoritmanız varsa, önbelleği önemsemeyen analizleri B ve M’lerin tümüne uygulayabilirsiniz. Yani bellek transferlerinin sayısını, burada, burada, burada, burada ve burada çözümleyebilirsiniz. Ve eğer iyi bir önbelleği önemsemeyen algoritmanız varsa, bütün düzeylerdeki performansların iyi olması gerekir. Bundan ötürü, toplam performans da ‘iyi’ olur. ’İYİ ‘ burada, sabit faktörlere kadar, asimptotik açıdan en iyi durumu ifade etmektedir. Bunu ispatlamak istemiyorum; önbelleği önemsemeyen algoritmalar ile ilgili makaleleri okuyabilirsiniz.

Önbelleği önemsemeyen algoritmaların iyi tarafı budur. Öte yandan, eğer belli değerde B’ye , belli değerde de M’ye ayarlanan önbelleği önemseyen bir algoritmanız varsa, bu sorunu yaşamazsınız. Bu, önbelleği önemsememenin güzel bir niteliğini oluşturur. Bir diğer güzel nitelik de, algoritmayı kodlarken, B’yi ve M’yi kullanmanızın gerekmemesidir. Bu özellik, her şeyi biraz basitleştirir. Şimdi, biraz algoritma yapalım.

Modeller hakkında bu kadar yeter. Çözümleme bağlamında ısınmak için, gerçekten basit şeylerle başlayacağız. Önbelleğin önemsenmediği dünyada yapabileceğiniz en basit iyi iş taramadır. Tarama, bir dizilimde ögeleri sadece kendi düzen sıraları içinde ziyaret etmekten ibarettir. Böylece ’den ’e kadar sırayla ziyaret edin. Ziyaret nosyonu açısından bu sabit zamanlı bir operasyondur. Örneğin, dizilimin toplamını hesaplamak istediğinizi düşünelim; dizilimde bulunan tüm ögeleri toplamak istiyorsunuz. Böylece bir ekstra değişkeniniz var, ama bunu bir kayıt-saklayıcısında veya nerede isterseniz orada depolayabilirsiniz; bu basit bir örnek. Dizilimi toplayın. Pekala, işte resmi burada.

Belleğimiz var. Bu hücrelerden her biri bir ögeyi, bir elemanı temsil ediyor, log N sayıda biti, bir sözcüğü, her neyse. Dizilimimiz burada bir yerde. Belki de orada. Ve buradan buraya, buraya, buraya gidiyoruz. Ve böyle devam ediyoruz. Pekiyi bu kaça mal oluyor? Bellek transferinin sayısı ne? Bunun doğrusal zamanlı bir algoritma olduğunu biliyoruz. Düzey N zamanı alıyor. Bellek transferi açısından kaça mal olur? N bölü B, çok fazla. Düzeyinin, N bölü B olduğunu artı iki veya büyük O da bir olduğunu söylemek istiyoruz. Bu biraz endişe verici. Demek istediğim, N, B’den küçük olabilir. Gerçekten, tüm olasılıkları düşünmek istiyoruz, çünkü genellikle böyle bir şeyi, N boyutunda yapmıyorsunuz. Bunu k gibi bir boyutta yapıyorsunuz ve k hakkında da aslında fazla şey bilmiyoruz.

Ama genellikle, bu N bölü B artı bir’ dir, çünkü N sıfır olmadıkça bir şeye bakabilmek için en az bir bellek transferine ihtiyacımız olur. Ve özellikle sabitlerle ilgileniyorsanız, artı ikidir. Eğer büyük O’yu yazmazsam azami artı iki olacaktır, çünkü aslında ilk bloku harcayabilirsiniz ve her şey bir süre yolunda gider. Ondan sonra, eğer şansızsanız, son bloku harcarsınız. O bloğun içinde sadece bir öge vardır ve ondan fazla bir kazancınız olmaz. Ama ortadaki her şeyin, birinci blok ile son blok arasındaki her blokun dolu olması gerekir. Dolayısıyla, bu elemanların tümünü kullanırsınız. Bunun sonucu, N sayıda ögeden elinizde yalnız N bölü B sayıda blok olur, çünkü blokta B kadar eleman vardır. Pekala bu oldukça önemsiz bir durum. Biraz daha enteresan bir şey yapayım : aynı anda iki tarama gibi..

Bu taramada M hakkında hiçbir varsayımda bulunmuyoruz. Önbelleğin boyutu hakkında bir varsayım yapmıyoruz, sadece tek blok tutabileceğimizi farz ediyoruz. En son ziyaret ettiğimiz blok orada olmalı. Pekiyi, sabit sayıda paralel tarama da yapabilirsiniz. Bu, çok izleklilik bağlamında gerçek paralellik değil, bit-simülasyonlu paralellik. Yani, demek istediğim, eğer sabit bir sayı varsa, bir tane yapın, ötekini yapın, ötekini yapın, geri gelin, geri gelin, geri gelin, tamam, onları sırasıyla ziyaret edin. Mesela, burada güzel bir kod parçası var. Eğer bir dizilimi tersine çevirmek istiyorsanız bunu yapabilirsiniz. Bu iyi bir yapbozdur.

Esas itibariyle, ilk ve son elemanlarını sürekli değiştirdiğiniz iki taramayla yapabilirsiniz. Ben de ’ yi, N eksi i +1 ile yer değiştirip, bir ile yeniden başlıyordum. İşte diziliminiz bu. Bunun gerçekten benim dizilimim olduğunu düşünün. Bu ikisinin yerlerini değiştiriyorum ve bu ikisini görüyorum, böylece devam ediyor. Bu dizilimimi tersine çevirir ve dizilim tek sayılı olsa bile, bunun ortada iyi çalışması lazım. Ayrıca bir şey yapmasına ihtiyaç yok. Böylece bunu ‘ iki tarama ‘ olarak görebilirsiniz. Bir tarama bu yöne geliyor. Bir de tersine tarama var ama biraz daha karışık ve bu yöne doğru geri geliyor. Şüphesiz,tersine taramanın analizi aynıdır. Tabii belleğiniz en azından iki bloku depolayacak kadar büyükse, ki bu çok makul bir varsayımdır; öyleyse, yazalım.

Bellekteki blokların sayısının M bölü B olduğunu farz ederseniz ve bu algoritmada en az iki tane var, bellek transferinin sayısı hala N bölü B artı bir düzeyindedir. Evet, belki sabit yukarı çıkar ama bu durumda muhtemelen çıkmaz. Kimin umurunda? Öyleyse, sabit sayıda tarama ve sabit sayıda dizilim yaptığınız sürece, bir tanesi tersine çevrilir; ne şekil alırsa alsın, buna doğrusal zaman alır deriz. Girdinizdeki blokların sayısı cinsinden doğrusaldır. Mükemmel, şimdi bir dizilimi tersine çevirebilirsiniz: heyecan verici. Bir başka basit bir algoritmayı, başka bir tahta üstünde deneyelim.

İkili aramayı deneyelim. Böylece, tıpkı geçen hafta olduğu gibi temel bilgilerimize geri dönüyoruz. Bu sınıfta scanning yani tarama hakkında konuşmadık bile. İkili arama hakkında bir parça konuştuk. Basit bir “Böl ve fethet” algoritması idi. Ümit ederim hepiniz hatırlıyorsunuzdur. Ve bir dizilime bakarsak ve burada hücreleri çizmek istemiyorum, çünkü gerçekten çok büyük bir dizilimde ikili aramayı tahayyül etmek istiyorum. Fakat hep sola gittiğini düşünün. Ortadaki bu elemanı ziyaret ederek işe başlıyor. Sonra, ilk başta dörtte bir noktasına gidiyor. Sonra da, sekizde bir noktasına gidiyor. Pekala, bu ikili aramanın hipotetik bir uygulaması.. Ve sonunda aradığı elemanı buluyor. En azından nereye yerleşeceğini buluyor.

Böylece x burada. Ve bunun log N kadar zaman aldığını biliyoruz. Peki, bu süre içinde kaç bellek transferi yaptı? Şimdi bu dizilimi, B boyutunda parçalar halinde blokladım. Kaç bloka dokunurum? Buradaki biraz daha zor..N ile B nin göreceli boyutlarına bağlı, öyle değil mi? N’ nin B log tabanı, iyi bir tahmin olabilir. Öyle olmasını istiyoruz, ümit ediyoruz çünkü temelde N sayıda ögesi olan sıralanmış bir listeyi, B ağaçlarının N’nin log B tabanındaki süresinde arayabileceğini biliyoruz.

Bu da, önbelleği dikkate almayan ya da iki düzeyli bir modelde, N nin B log tabanı kadar harcamanın optimum yani en iyi değer olduğunu ortaya çıkarır. Burada bunun kanıtlamasını yapmayacağım. Log N kıyaslamalarına, normal modelde ikili arama yapmak için de aynı nedenle ihtiyacınız var. Aslında, N nin B log tabanını B yi bilmeden de elde etmek mümkündür. Fakat, ikili tarama bunu yapmaz. Log N bölü B, evet. Öyleyse, N sayıda öge ile yapılan bellek transferinin sayısı log N bölü B dir ki, burada bir de artı bir var diyelim, bu da aynı zamanda log N eksi log B olarak bilinir.

Beri taraftan, N nin B log tabanı, log N bölü log B dir, tamam mı ve bu da çıkarma işlemi yapmaktan çok daha iyidir. Netice bu ise iyi, ama bu ise kötü. Oysa çoğu zaman bu log N olur ve işe yaramayabilir; yani hiç blok kullanmazsınız. Demek istediğim burada, bu şeyi ihtiva eden, birkaç küçük, küçücük bir blok var. Küçücük, diyorum ama bu, B nin ne kadar büyük olduğuna bağlı. Diğer taraftan, siz x değerinde bir blokun içine girinceye kadar, bu ögelerin her biri başka bir blok içinde olacaktır. x değerinde bir blokun içine girdiğinizde, artık sadece sabit sayıda bloklar sizi ilgilendirir, başka bir deyişle, tüm bu erişimler, aslında aynı bir bloğun içinde olur. Peki bunlardan kaç tane var? Küçük a içinde sadece log B kadar, çünkü küçük k boyutlu aralıklar içinde iseniz, blok içinde sadece log k sayıda adım atabilirsiniz. Öyleyse, burada log B yi tasarruf edersiniz ama toplam olarak, log N ödersiniz, yani, sadece, log N eksi log B artı belli bir sabiti elde edersiniz.

Öyle ise,ikili arama için, bu kötü haber. Demek ki, şimdiye kadar görmüş olduğumuz algoritmaların hepsi bu modelde iyi netice vermeyecek. Bu nedenle ikili arama sorununu çözmeden önce daha fazla düşünmeye ihtiyacımız var; sıralanmış bir listede, B yi bilmeden N nin B log tabanında bir elemanın bulunması konusunda.. Pekala, B ağaçlarını kullanabileceğimizi biliyoruz. Eğer B yi bilirseniz, bu mükemmel, hem işleyen, hem de en iyi durum olur; ama B’yi bilmiyorsanız, biraz daha güçtür.

Bu bizi, böl ve fethet dünyasına taşır. Geçen hafta ve bu sınıfın ilk haftalarında olduğu gibi, gene böl ve fethet, sizin dostunuzdur. İlginç olan, önbelleği dikkate almayan algoritmaların tasarımında, böl ve fethet, sadece yegane değil, aynı zamanda gerçekten yararlı bir alettir. Niçin olduğunu söyleyeyim.. Bir çok böl ve fethet temeline dayanan algoritma göreceğiz önbelleği önemsemeyenler bağlamında.. Sezgime göre, bütün favori algoritmalarımızı alabiliriz ama bunların her zaman işe yaramayacağı açıktır. İkili arama, bir böl ve fethet algoritmasıydı. Bu o kadar önemli bir şey değil.

Önemli olan, genel olarak algoritmanızın, normal böl ve fethet işlemini yapabilmesi, tamam mı? Böylece, probleminizi defalarca, sabit büyüklükteki alt problemler haline gelene dek bölüyorsunuz. Daha önce yaptığınız gibi.. Fakat, bölme işlemini özyineleme yoluyla yaparken bir noktada durup, bunu algoritma sonuna kadar zaten yapıyor diye düşünebilirsiniz. Ama problemin bir bloğa veya önbelleğe sığması konusunu da düşünebiliriz .

Tamam, bu çözümlemeydi.. Probleminiz yeterince küçük olduğunda başka yoldan nasıl çözümleyebileceğimizi zamanı geldiğinde düşüneceğiz. Demek ki, genel olarak, özyineleme kullanıyoruz. Bir yineleme alıyoruz. Değiştirdiğimiz, esas itibariyle taban şıkkı oluyor. Taban şıkkında aslında sabit bir boyuta inmiyoruz. O yol çok uzak. Size birkaç örnek göstereceğim. Özyinelemede de, ya problemin önbelleğe sığdığı, böylece M’ye küçük-eşit olduğu; veya , ‘bir düzeyindeki bloklara” sığdığı özyineleme noktasını düşünmek istiyoruz. Bu işi normal zamanda yapmanın başka bir yoludur. “Bir düzeyinde bloklar, önbelleğe sığma şıkkından daha da iyi olacaktır..

Öyleyse bu, B düzeyinde boyut anlamına gelir. Bu, yinelemenin taban şıkkını değiştirecek ve kötü yanıtlar yerine iyi yanıtlar verecek hale dönüştürecek. Şimdi basit bir örnek yapalım. İyi dostumuz, düzey istatistikleri, özellikle ortancaları bulmak için.. Hepiniz ezbere biliyorsunuz ümit ederim. Bloom tarafından bulunan ortancayı bulma algoritmasının en kötü durumunun doğrusal zamanlı olduğunu hatırlayın. Bunu hızlı yazacağım. Dizilimimizi bölüntülere ayırıyoruz. Olduğu şekliyle iyi bir algoritma olduğu ortaya çıkıyor. Dizimimizi, prensip itibariyle, N bölü beş şeklinde, beş katlı, beşli gruplara bölüyoruz.

Bu, son yazdığımın aynısı olmayabilir. Kontrol etmedim ama aynı algoritma. Her beş katın ortancasını hesaplıyorsunuz. Sonra bu ortancaların ortancasını özyinelemeli, olarak hesaplıyorsunuz. Sonra, x’in etrafında bölüntülere ayırıyorsunuz. Bu bize kabaca ortada olan belli bir eleman vermişti. Sanırım, orta yarımın içindeydi. x etrafında bölüntülemeyi yaptıktan sonra özyinelemeyi her zaman sadece bir tarafta yapabileceğinizi göstereceğiz..

Pekala, bu hesaplamadaki eski dostumuz, düzey istatistikleri, ortancalardı.. Pekiyi bu ne kadar zaman alır? Aslında ne kadar olduğunu biliyoruz. Doğrusal zaman olması lazım. Ama kaç tane bellek transferi gerektiriyor? Prensipte bölüntülemeyi öyle yapabilirim ki bu sıfır olur. Belki burada N bölü beşi hesaplamam lazım, büyük bir iş değil. Burada hesaplamayı düşünmüyoruz. Her katın ortancasını bulmam lazım. Burada, dizilimimin ne şekilde düzenlenmiş olduğu önemli. Ama yapacağım şey, dizilimimi almak, ilk beş elemanı almak, sonra ardından gelen beş elemanı alarak sonuna kadar devam etmek. Bunlar benim beşli katlarım. Öyleyse,önce sadece tarama yaparım, sonra da CPU ‘mdaki beş kayıt yada yazmaçta muhafaza ettiğim o beş elemanın ortancalarını bulurum. Bunu yaparken, yeterli sayıda kayıt olduğunu varsayacağım.

Ve ortancayı hesaplayarak buradaki bir dizilime yazarım. Böylece tek eleman olur. Buradaki ortanca oraya giriyor.. Bunların ortancaları da oraya giriyorlar ve böylece devam ediyor. Burada tarama yapıyorum ve bunu paralel olarak yapıyorum. Buradaki bir çıkışı tarıyorum. Böylece iki paralel tarama oluyor. Ve bu işlem doğrusal zaman alıyor. Yani bu N bölü B düzeyi artı bir adet bellek transferi gerektiriyor. Pekala, sonra da ortancaların ortancasını özyinelemeli olarak hesaplamamız gerek. Bu aşama, N’nin T’si bölü beş idi. Şimdi, B ve M nin aynı değerleri ile, MT(N) bölü beş.. Sonra x’in etrafında bölüntü yapıyoruz. Bölmek, eğer hesaplarsanız üç paralel tarama yapmak gibidir. Yani bu da, N bölü B artı bir düzeyinde doğrusal bellek transferi gerektiriyor. Bundan sonra da sadece taraflardan birinde özyineleme yapıyoruz. Çözümlemenin eğlenceli tarafı bu ve burada tekrarlamayacağım.

Fakat, MT’yi N nin yaklaşık dörtte üçü kadar elde ediyoruz. Tahminim ilk başta onda yedi idi, biz dörtte üçe sadeleştirdik; bu da onda yediden büyük. Evet, büyük. Pekiyi, bu yeni çözümleme.. Şimdi bir özyineleme elde edeceğiz. Onu yapalım. Çözümlemede elde ettiğimiz N’nin MT si, N bölü beşin MTsi, artı üç bölü dört N’nin MT’si ; bu da tamamen önceden olduğu gibi. Daha önce burada doğrusal işlem yapmıştık. Şimdi, doğrusal diye adlandırabileceğimiz sayıda bellek transferi ve doğrusal sayıda bloklar var. Pekiyi buradaki artı biri dikkate almayacağım. Çok kritik değil. Böylece özyinelememiz bu. Artık taban şıkkımızın ne olduğuna bağlı. Ve genelde sabit boyutta taban şıkkı kullanırız; sabit boyutlu taban şıkkı kullandığımızda ne olacağını sırf bunun önemini görmek için deneyelim.

Bu durum yinelemeyi karmaşık yinelemelerden biri olacak hale getiriyor. Yerine substitution yani yerine koyma yöntemini kullanmak istemiyorum. Sadece, bunun niye oldukça büyük bir şeyi çözeceğinin sezgisini istiyorum. Bana en büyük sezgiyi daima özyineleme ağaçları verir. Eğer özyinelemenin çözümünü bilmez ve bir tahmine ihtiyaç duyarsanız, özyineleme ağaçlarını kullanın. Ve bugün sizlere sadece iyi tahminler vereceğim. Yerine koymayı kullanarak bir şey ispatlamak istemiyorum, çünkü daha büyük fikirlere ulaşmak istiyorum.

Bu, özyineleme ağaçları açısından bile karışık, çünkü bu dengesiz boyutlar var ve kökte N bölü B gibi dengesiz boyutlarla başlıyoruz. Sonra N bölü B’yi, beşte bir N bölü B ve dörtte üç N bölü B gibi boyutları olan şeylere bölüyorsunuz ve bu can sıkıcı,çünkü bu alt ağaç bundan daha büyük olacak, veya bu daha çabuk son bulacak. Yani bu oldukça dengesiz. Her düzeyde toplama yapmak da bu evrede size bir şey ifade etmez. Ama en alt düzeye bir bakalım.

Bu özyineleme ağacındaki tüm yapraklara bakın. Yani bunlar taban şıkları.. Kaç tane taban şıkkı var? Bu ilginç bir soru. Bu özyineleme bağlamında bu konuda hiç düşünmedik. Bir bakıma hayret verici bir yanıt veriyor. Üzerinde ilk çalışmamda da, benim için, hayret verici olmuştu. Sorumuz: bu özyineleme ağacının kaç yaprağı var? Hemen bir özyineleme yazabiliriz. N büyüklüğünde bir sorudaki yaprakların sayısı, bu problemdeki yaprakların sayısı, artı bu problemdeki yaprakların sayısı, artı sıfır olacak. O da başka bir özyineleme. Buna, N’ nin L’ si, diyeceğiz. Pekala, şimdi taban şıkkı gerçekten önemli.

Bu, yinelemenin sonucunu belirler. Şimdi biz, bir boyutunda bir problemde bir yaprak, olduğunu farz edelim.Yegane taban şıkkımız bu. Böyle görünüyor, sanırım burada tahmin etmeniz gerekiyor . Bu yeterince açık değil. Öğretim Görevlilerinden birinin bu problemin çözümü konusunda bir tahmini var mı? Herhangi bir kimsenin? Yalnız Öğretim Görevlilerinin değil. Sorum, herkese açık. Eğer Charles burada olsa idi, ona da sorardım. Bu konuda biraz düşünmek zorunda kaldım ve bu doğrusal değil, evet, çünkü bir hayli küçülüyorsunuz.

Öyleyse, doğrusaldan daha küçük, ama bir sabitten de daha büyük. Pekala, öyleyse ortadaki tercih ettiğiniz fonksiyon ne? N bölü log N, hala çok büyük. Devam edin. Burada bir kahin olmalı.. N’nin k’nıncı kuvveti, evet yakın. Yani, k genellikle bir tamsayıdır. N’nin alfa kuvveti ve alfa sıfır ile bir arasında belli bir rakamdır. Evet, onu demek istemiştiniz. Bu en kısa matematiksel şaka gibi; epsilonun yeterince büyük değerleri için, epsilon sıfırdan küçük olsun durumu gibi.. Yani, doğru harfleri kullanmanız lazım. Bakalım, N’nin alfa kuvveti olduğunu farz edelim. O zaman bu N bölü beşin alfa kuvvetini ve üç bölü dört N’nin alfa kuvvetini elde etmiş oluruz.

Böyle güzel bir yinelemeniz olduğunda, bir tahmin yapıp, işleyip işlemeyeceğini araştırabilirsiniz ve tabii bu sadece alfa’ya bağımlı olacaktır. Yani burada alfaya bağımlı bir denklem elde edeceğiz. Tüm bu ögeler N’nin alfa kuvvetini içerecektir. Öyleyse, N’nin alfa kuvveti ile bölme yapabilirim. Tabii,alfanın sıfır veya öyle bir şey olmadığını varsayıyoruz. Bu makul görünüyor. Öyleyse elimizde, bir eşittir bir bölü beş üzeri alfa artı üç bölü dört üzeri alfa var.

Bu finalde gelmeyecek çünkü Maple veya Mathematica dışında bunu çözecek başka bir yol bilmiyorum. Eğer çok zekiseniz, eminim bunu daha iyi bir şekilde hesaplayabilirisiniz, fakat alfa 0.8 civarında çıkacaktır. Öyleyse yaprakların sayısı, sabit ile doğrusal arasında bir şey. Genellikle, polinomsal olmak tam sayıların gücene sahip olduğunuz anlamı taşır. Biz de polinomsal diyelim. Neden olmasın? Yaprakların çok sayıda olmaları nedeniyle, eğer her bir yaprağın maliyeti sabit sayıda bellek transferi gerektirirse, zor durumda kalırız; çünkü o takdirde bellek transferlerinin en az bu olması gerekir. Eğer en az bu kadarsa, o takdirde potansiyel olarak N bölü B den büyüktür; yani asimptotik anlamda daha da büyük olur demek istiyorum.

Bu, eğer B büyük ise, N bölü B nin küçük omegasıdır. Eğer B, en az N’nin 0,2 kuvveti gibi veya yedide biri kadar ise bu böyledir.. Ama, B en az, N’nin 0,2 kuvveti ise, o zaman bu, şundan büyük demektir. Öyleyse, bu iyi bir çözümleme değil, aksine kötü bir çözümleme, çünkü elde etmek istediğimiz yanıt olan N bölü B’ yi vermiyor. Ortanca için yapabileceğiniz en iyi şey N bölü B dir, çünkü tüm elemanları okumak zorundasınız ve sadece doğrusal zaman sarf etmelisiniz. Demek ki N bölü B elde etmek istiyoruz. Bu algoritma ise N bölü B artı bir. İşte bundan dolayı, iyi bir taban şıkkına ihtiyacınız var, tamam mı? Anlatmak istediğim bu.. Öyleyse şimdi sorun, hangi taban şıkkını kullanmalıyım?

Demek ki elimizde bu özyineleme var, hangi taban şıkkını kullanmam lazım? Sabit, çok küçüktü. Burada bazı seçim olanakları listelenmiş. Bir önerisi olan var mı? B, pekala B nin MT si nedir? Zor kısım. Benim sorunum eğer dizilimimin boyutu bir bloka sığıyorsa ve tüm bu şeyleri onun üzerinde yaparsam, bu kaç bellek transferi sürer? Bir veya sabit kadar, sıralanış şekline bağlı olarak. Belki iki bellek transferi ama sabit.. İyi. Her durumda bu taban şıkkından çok daha iyi, birin MT si, eşit, birinci düzeydir ve bu belirgin olarak daha güçlü. Bu umarız doğru yanıtı verir ve şimdi gerçekten doğru yanıtı veriyor.

Bu çözümlemeyi çok seviyorum. Onun için ellerimi sallayacağım. Pekiyi ama, bu çözümleme özellikle bize ne verir, bir önceki çözümlemeyi yapsak, yaprakların sayısı ne olur? Şimdi yapraklarda eşit bir yerine, eşit bir. Yani bu daha önce duruyor. Bu ne zaman durur? Burada, N ‘yi 0.8 düzeyine yaklaştırmak yerine , N bölü B’ yi 0.8 kuvvetine yaklaştırıyoruz. Bu durumda yaprakların sayısı, N bölü B üstü alfa oluyor ki, bu da N bölü B ‘nin küçük o’suna karşılık gelir. Önemsemiyoruz, çünkü çok küçük. Ve eğer özyineleme ağacındaki kök maliyete bakarsanız bu N bölü B’dir ve yaprak maliyeti de N bölü B’ nin küçük o’ sudur; eğer ellerinizi sallar, gözlerinizi kapar, aradan kaçamak bakarsanız, aşağı indikçe maliyet de belirli belirsiz geometrik olarak azalır.

Bütün sona eren şeylerden ötürü biraz karmaşık ama maliyetin kabaca geometrik olduğunu söylemeliyiz. Final sınavında bunu yapmayın ama bu kadar karmaşık özyinelemelerle zaten karşılaşmayacaksınız. Bunun için endişelenmeyin. Ancak ağacın aşağısında, kök maliyetlerin hakim olduğunu iddia ediyorum; bunu siz kanıtlayacaksınız. Ve kök maliyeti N bölü B çünkü N bölü B’ yi elde ediyoruz. Böylece bu doğrusal zamanlı algoritma, düzey istatistikleri ve önbelleği dikkate almama uygulamasında iyi bir algoritmadır. Bu sizi işten biraz soğutabilir ama bu çok basit gibi bir algoritma olmasına karşın yapacağımız en karışık çözümlemedir.

Gelecekte algoritmalarımız daha karmaşık, çözümlemeleri ise nispeten basit olacak. Bu genelde önbelleği dikkate almayan algoritmalar için de geçerlidir. Bunları, anlattıklarımın neden yeterli olması gerektiği konusunda sezginizi arttırmak için söylüyorum. Kanıtlamasını sizin yapmanız gerekiyor.

Pekala, böl ve fethet’ in yararlı olduğu başka bir probleme, iyi dostumuz matris çarpımına geçelim. Bu sınıfta bunu kaç defa gördüğümüzü bilmiyorum ama, özellikle geçen hafta, bir çok izlekli algoritmada, özyinelemeli matris çarpımı bağlamında görmüştük.

Gene algoritmayı hemen vermeyeceğim, fakat çok farklı bir şekilde analiz edeceğiz. Şimdi büyük harf C ve büyük harf A mız var ve bu seçimleri kendiniz yapabilirsiniz. Aslında standart matris çarpımı işlemini sıra sıra ve sütun sütun yapabilirim. Ve bunun niye burada kötü olduğunu görürüz. Ve sonra özyinelemeli olanı yapar ve onun niye iyi olduğunu görürüz. Veya standart algoritmayı atlayabiliriz. Şimdi kaç kişi standard algoritmanın neden kötü olduğunu görmek istiyor? Çünkü bu çok açık değil. Bir, iki, üç, dört, beş,sınıfın yarısı mı? Vay,vay, bu bayağı çok oy. Şimdi kaç kişi bunu atlamak istiyor? Hiç kimse? Bir kişi, tamam. Ve geri kalanlar uykudalar. Öyleyse bu çok iyi, % 50nin uyanık olması fena değil. Pekala öyleyse konumuz, standart matris çarpımı .

Bunu süratli yapacağım çünkü hepiniz algoritmayı biliyorsunuz değil mi? Bu C değerini hesaplamak için A da bu sırayı alırsınız ve B de bu sütunu. Özür dilerim, biraz dikkatsizlik yaptım. Ama bunun aynı hizada olması lazım,değil mi? Böylece, tüm bu şeyleri alıyor bu şeyler ile çarpıyorum, hepsini topluyorum, nokta çarpımını buluyorum. Bu bana bu elemanı veriyor. Ve bunları bu düzende, sıra sıra yapıyorum. Böylece, C deki her öge için A’daki bu sıra ve B deki bu sütunu çevrime alıp onları birbirleriyle çarpıyorum. Bu bellekteki erişim modeli.. Kesin olarak kaça mal olacağı tabii bu matrislerin bellekte ne şekilde düzenlendiğine bağlı. Bu önceki örneklerde her şey tekdüze olduğu için endişelenmediğimiz bir incelikti.. Standard algoritmaya iyi bir algoritma olması için en iyi şansı tanımak istediğimden C yi, sıra öncelikli düzende, A’ yı sıra öncelikli ve B yi de, sütun öncelikli düzende depolayacağım.

Böylece, her şey güzel ve tarama yapıyorsunuz. Öyleyse, bu iç ürün yani çarpım, bir taramadır. Mükemmel. Harika görünüyor, değil mi? Ama kötü. A nın büyük sıra öncelikli, B nin sütun öncelikli olduklarını farz edin. Ve C nin de ikisinden herhangi birine benzeyebileceğini varsayabilirsiniz, ama onu sıra sıra ele aldığım için, C yi sıra öncelikli kabul edeceğim. İşte buna matrislerin düzeni, yani matrislerin bellek düzeni diyorum. Bu, bu algoritma için iyi, ama algoritma iyi değil. Öyleyse, o kadar da muhteşem değil..

Pekiyi, bu ne kadar zaman alıyor ? Kaç tane bellek transferi var? Bunun M küp zaman aldığını biliyoruz. Bunu sınamaya veya aşmaya çalışmayacağım. Standard matris çarpımını deneyip elde etmek için daha hızlı gideceğim. Buradaki her öğeyi taramak ve iç çarpımı elde etmek için N bölü B ödüyorum. Öyleyse bu öge başına N bölü B ediyor. Yani bu N bölü B, veya buradaki artı biri kullanarak her ‘yi hesaplayabiliriz. Bu da üst sınır olarak, en azından N küp bölü B yi hatıra getirir. Gerçekten de bu doğru sınırdır; yani teta. Tabii bunlar bellek transferleri, zaman değil.

Gerçekten olay bu, çünkü sonraki adımlara bakarsanız, bu ’de işlem yaptığımda, sonra bunda, bunda, bunda ve bunda, j ‘ yi arttırır ve i‘ yi sabit tutarım, tamam mı ? Böylece kullandığım sıra, uzun süre sabit kalır. Böyle kalıyorsa, örneğin belki bir bloka sığıyorsa, o sırayı tekrar kullanırım, yani eğer önbelleğe sığıyor ise birkaç kere daha kullanırım. Fakat, sütun, her defasında değişiyor. Öyleyse, bir sonraki ‘yi hesaplamak için buraya her gelişimde, bir sütun önbelleğe sığsa bile, bütün sütunları önbelleğe sığdıramam. Çünkü, bildiğiniz gibi ziyaret ettiğim sütunlar hareket ederler ve bir taraftan diğerine tarama yaparlar. Öyle ise, her defasında bu matris‘in tamamını tarıyorum. Matrisinizin tamamı önbelleğe sığdığı takdirde, ki bu halde her şeyi yapabilir, hiçbir şeye aldırmazsınız, işlem sabit bir zaman alacaktır veya onu önbelleğe okumak, yapacağınızı yapmak ve tekrar dışarı almak M bölü B süresini alacaktır..

O sıkıcı durum hariç, burada her sıra için, N kare bölü B ödemeniz gerekir, çünkü her bir sıra için tüm sütunları taramak zorundasınız. Buradaki her sıra için bu matrisin tamamını okumanız gerekir . Yani bunların tümü için gerçekten, N küp bölü B ‘ye ihtiyacınız olur. Bu da genellikle bir teta’dır. Ziyanı yok, buna mükemmel diyebilirsiniz. Bu problemimin büyüklüğü, olağan koşma süresi bölü B’dir. Bu olayla, doğrusal zamanlı düşünürken karşılaşmıştık, N’ye karşı N bölü B idi. Probleminiz N boyutunda ise, N bölü B ‘den daha iyisini yapamazsınız. Oysa şimdi karşımızda kübü var. Bu da bizi iyi bir mekansal yere sahip olmaya yönlendiriyor. Bir bloku okurken tamamını kullanıyoruz. Güzel, optimal gözüküyor. Ancak, iyi bir zamansal yerimiz yok. Doğru şeyleri depolamış, onları saklamış ve defalarca kullanmış olabiliriz; çünkü bir elemanı aradığımızda, genellikle küpü sayısında kullanırız.

Belki doğru söyleyiş tarzı tam bu değil, fakat matrisleri ve bu öğeleri sıkça kullanırız. Eğer, N kare şey üzerinde N küp çalışma yapıyorsak çok kullanıyoruz demektir. Ama bundan daha iyisini yapmak istersek görmüş olduğumuz özyinelemeli algoritmayı kullanmalıyız. Bu algoritmayı oldukça iyi biliyoruz. Sizlere sadece düzeninin ne olduğunu söylemem lazım. , vs. gibi bölüntülerden oluşan C’ yi alıyoruz. Böylece, N x N matrisim var, bunu, N/2 ye N/2’lik alt matrislere bölüntülüyorum ve üçünü de neyle çarpmam gerekiyorsa çarpıyorum.

Bunu yazabilirim ama gene daha yazmayacağım. Tamam, bunu sekiz matris çarpımı ve bir takım matris toplamıyla özyinelemeli olarak hesaplayabilirsiniz. Sabit sayı hariç, kaç tane olduklarına aldırmıyorum. Bunu şimdiye kadar en az iki defa gördük onun için tekrar göstermeyeceğim. Şimdi, matrisleri nasıl düzenlerim? Herhangi bir öneri var mı? Bunları sıra öncelikli düzende yerleştirebilirim. Buna öncelikli düzen diyeceğim.. Ama şimdi bu pek doğal olmaz. Burada sıralar ve sütunlarla ilgili herhangi bir şey yapmıyoruz.

Pekala, hangi yerleşimi kullanmalıyım? Quartet öncelikli düzen mi? Belki quadrant major order, yani dörtlü öncelikli düzen demeliydiniz; tabii müziğe eğiliminiz yoksa . Bu iyi fikir. Bu düzeni şimdiye kadar hiç görmediniz, belki bunun için olağan gelmeyebilir. Bir şekilde bunu bloklar halinde gruplamak istiyorum . Sanırım, hepsi bu kadar. Yani, bu özyinelemeli bir yerleşim.. Bu kolay bir soru değildi. Zararı yok. Matrisleri ,özyinelemeli şekilde bloklar halinde depolayın veya yerleştirin. Birazcık hile yapıyorum. Matrislerinizin bu şekilde yerleştirildiğini varsayarak, problemi yeniden tanımlıyorum. Ama çok fark etmeyecek. Hile yapabiliriz değil mi? Aslında hiç fark etmez.

Bir matrisi, çok fazla doğrusal bir çalışma yapmadan, neredeyse doğrusal çalışmayla bu yerleşime dönüştürebilirsiniz. Belki log faktörleri oranında çalışmayla. Demek ki, A matrisimi doğrusal bir şekilde depolamak istersem, şu yerleşimi özyinelemeli şekilde tanımlarım ve sol üst köşeyi özyinelemeli olarak depoladıktan sonra, örneğin sağ üst köşeyi depolarım. Bunu hangi sıra ile yaptığımın hiç önemi yok. Bunu daha büyük çizmeliydim. Sonra da sol alt köşeyi ve sonra sağ alt köşeyi özyinelemeli olarak depolamalıyım.

Öyleyse, bunu nasıl depo edersiniz? Dörde bölersiniz, sol üst köşenin yerleşimini yararsınız ve böyle devam edersiniz. Evet, bu doğrusal bir dizilimde elemanın nasıl depo edileceğinin özyinelemeli bir tanımlamasıdır. Biraz gariptir ama önbelleği dikkate almayan algoritmalar için çok güçlü bir fikirdir. Bunu birkaç kez kullanacağız. Şimdi yapmamız gereken şey, bellek transferlerinin sayısını çözümlemektir. Bu ne kadar güç olabilir? Yani, bütün matrisleri bu düzende depolayacağız ve bellek transferlerini, N ye N bir matris için hesaplamak istiyoruz. Görüyorsunuz, küçük harf n’ ye geçtim ve konuyu biraz değiştirdim. Bu hafta boyunca tarihi nedenlerle, algoritmaların anlatımında hep büyük N kullanmalıyım; tüm dış bellek türü algoritmalar ve 2 düzeyli algoritmalarda hep büyük N tercih edilmiştir. Ve nedenini sormayın. Küçük n’ nin ne olması gerektiği konusunda yapılmış tanımları görmelisiniz.

Pekala, şimdi yinelemenin ne olması gerektiği konusunda herhangi bir görüş var mı? Yinelemeyle ilgili bütün bu kurulum aslında çok kolay. Şüphesiz, N bölü ikiye N bölü iki matrislerin çarpımını içeriyor. Böylece, buraya ne gelir? Sekiz, teşekkür ederim. Onu bilmeniz gerek. Ve şaşırtıcı kısım da burada neyin geldiği. Pekiyi, şimdi buraya neyin geldiğini de yazabilirim, bu matris toplamaları. Şimdilik onları unutun. Yoklarmış gibi farz edin. Sadece, özyinelemeli şekilde çarpma yapmam lazım. Burada sekiz çarpı N bölü iki sayıda bellek transferinin olması durumu, bu yerleşime dayanır.

Tamam, verilen dizilimlerin yan yana yani ardışık aralıklar ve bellekler şeklinde olduklarını varsayıyorum. Eğer böyle değillerse, tersine tüm bellek üzerinde oraya buraya düzensiz olarak saçılmışlarsa, bittim demektir .Yapabileceğim hiçbir şey olmaz. Fakat, elimdeki bu özyinelemeli yerleşim varsa, bu çeşit özyinelemeli çarpımların, ben ne yaparsam yapayım, daima ardışık üç parça-belleği kapsayacağını biliyorum; biri A, biri B ve biri de C için olmak üzere.. Diğer taraftan, ardışık depolandıklarından özyinelemeli olarak o invariant yani değişmez’ e de sahibim. Ve özyineleme yapmaya aralıksız olarak devam edebilirim. Ve her zaman üç ardışık bellek parçasıyla çalışırım.

Bu nedenle, bu yerleşimimin de bunları anlatabilmesini istiyorum. Peki, şimdi toplamanın maliyeti ne kadar? Size sadece iki matris vereceğim. Bunlar, belli bir doğrusal düzende, üçü için de aynı doğrusal düzende depolanmışlar. Doğrusal düzenin ne olduğunu dikkate alıyor muyum? Çıkışı elde etmek için iki matrisi nasıl toplamalıyım? Evet? Doğru, eğer üç dizilimin her biri aynı düzende depolanmışsa, üçünü de paralel şekilde tarayarak, birbirine karşılık gelen elemanları toplar ve üçüncü’ ye çıkış yapabilirim. Öyleyse bu değişmediği sürece ve bölü B’yi elde ettiğim sürece düzenin ne olduğuna aldırmam. Buradaki artı biri dikkate almıyorum . Bu sadece matrisin bütününe bakmaktır. Devam ediyoruz; bir yineleme daha var. Bunu, olarak görmüştük, şimdi ’ü elde ettik. Ama öyle görünüyor ki, şimdi doğru taban şıkkını kullanabilirsek, daha iyi bir şey elde edebiliriz. Böylece, şimdi taban şıkkına, yani şaşırtıcı kısma gelmiş bulunuyoruz. Bu durumda ne çeşit bir taban şıkkı kullanmamız gerektiği konusunda bir görüş var mı?

Blok boyutu, iyi bir öneri. Eğer blok boyutu B düzeyinde ise, bunun sabit sayıda bellek transferi gerektireceğini biliyoruz. Ama bunun yeterli olmadığı anlaşılıyor. Burada bir çözüm sağlamayacak. Ama iyi bir tahmindi. Ancak bu durumda problemin doğru yanıtı değil. Olmadığını göstermek için, biraz sezgiye başvuracağım. Biz burada bölü B’ yi geliştirmeye çalışıyoruz. Eğer bunun sadece B’ye bölünmesiyle ilgilenseydiniz, bu çok iyi bir taban şıkkı olurdu. Ama burada yalnızca blok boyutunun getireceği bir iyileştirme yeterli değildir.

Öyleyse, önbelleğin büyük olduğunu hatırlayarak, bir şekilde bu olanağı kullanmalıyız. Ön belleğin boyutu M, M ne kadar büyük ise boyut da o kadar büyük demektir. Tamam bunu geliştirmek istiyorsak, formülümüzde bir yerlerde M olması lazım, oysa henüz M’ler yok. ,M’nin bir yerde olması lazım. Şu ne? M’ nin MT’ si bölü B mi? Bu işe yarar, ama M nin MT’si, aynı zamanda belli bir sabit çarpı M demektir. Bu sabiti, problemin tamamını önbelleğe sığdırabilecek kadar küçük yapmak istiyorum.

Yani, üçte bir kadar. bir dakika, bu aslında karekök M değil mi? Evet, bu bir N’ye N Matris. Öyleyse, bunun C kere karekök M olması gerek. Af edersiniz., karekök M’ye karekök M boyutlu matrisin M sayıda girişi vardır. Eğer C yi üçte bir veya o civarda yaparsam, üç matrisin tamamını belleğe sığdırabilirim. Aslında bir bölü karekök üç de bunu karşılar ama kimin umurunda. Belli miktar C sabiti için şimdi her şey belleğe sığıyor. Bu kaç bellek transferi eder? Bir mi? Bu biraz az çünkü problemi okuma zamanı da lazım. Şimdi burada bir vardı, çünkü okuyacak yalnız bir blok vardı. Şimdi okunacak kaç blok var? Sabitler mi? Hayır.

B mi? Hayır. M bölü B, iyi. Sonunda doğruyu buldunuz. Kahin gibi düşünmenin iyi tarafı da bu. İstediğiniz kadar tahmin yapmaya devam edebilirsiniz. M bölü B, çünkü M boyutunda önbelleğimiz var. M boyutlu önbelleğin içinde de okunacak M bölü B blok var, değil mi? Belki, uzun süredir kullanmadığımız için, M’nin ne olduğunu unuttunuz. Fakat M, önbellekteki elemanların sayısıdır. Bu ise önbellekteki blokların sayısı.

Pekala, bazılarınız B diyordu, M bölü B nin B kadar olabileceğini düşünmek makul. Karesel önbellek gibi ama genellikle bu varsayımı yapmayız. Pekala, nerede kalmıştık? Dersi bitirmiş gibiyiz, iyi çünkü üç dakikamız var. Demek ki, taban şıkkımız bu. Burada bir karekök var; bunu unuttum. Şimdi bunu çözmemiz lazım. Şimdi, bu daha kolay bir yineleme, değil mi? Master metodu kullanmak istemiyorum çünkü, Master Metot bu B’ ler, M’ ler ve bu çılgın taban şıklarını çözümleyemez.

Tamam, master metod ‘ü kanıtlayabilir. Mükemmel. Master metod bu çeşit sorunları değerlendirmez. Fakat, recursion trees yani özyineleme ağaçları durumunda eğer gerilere gidip master metodun kanıtlanmasını hatırlarsanız, özyineleme ağacına bakıp, geometrik açıdan aşağıda yukarıda her şey eşitse, bunların hepsini her düzeyde toplamıştık. Buradaki önemli nokta, bunun iyi bir özyineleme olduğudur. Tüm alt-problemler,aynı boyutta ve bu çözümleme daima işler, yani herşey, tüm çocuklar aynı boyutta olursa..

Öyle ise, burada bir özyineleme ağacı var. Tepede bölü B var. Bunu, her biri yarım bölü B maliyetinde, sekiz alt-probleme bölüyoruz. Ayrı ayrı hepsini yazmayacağım. Siz toplayın. Ne elde edersiniz? Sekiz tane idi. Sekiz defa yarım iki yapar. Hayır, dört eder. Teşekkürler. Dört, değil mi? Aritmetikte zayıfım. Belki daha önce de söyledim, üç çeşit matematikçi vardır, toplama yapabilenler ve yapamayanlar. Pekala, buna niye bakıyorum? Bu çok açık.

Öyleyse, devam ederiz. Bu geometrik olarak artıyor görünüyor. Değil mi? Eğer ilk iki düzeyde çalışırsanız,artıyor mu azalıyor mu, eşit mi, değiller mi, içinizden bilebilirsiniz.. Sonra düşünseniz iyi olur. Ama ben bunu geometrik olarak artıyor görüyorum. Sanırım, bir sonraki düzeyde gerçekten 16 gibi olacak görünüyor. Tamam zaten artmalı.. Yani artıyor.. Artmaya devam etmesi yaprakların önemini gösterir.. Öyleyse yaprakları hesaplayalım.

Ve bu taban şıkkını kullandığımız aşamadır. Karekök M boyutunda bir problemimiz var. Ve böylece, evet, bir sorunuz mu var? Oh, gerçekten. Bir şeyin olduğunu biliyordum. Şuradakinin iki olması lazımdı. Teşekkürler. Sizler bunun için buradasınız. Gerçekten bu, N bölü iki kare bölü B. Teşekkürler. N bölü 2 yi, bunun yerine koyuyorum. Böylece bu aslında bölü 4 B. Böylece 2 elde ediyorum, çünkü sekiz çarpı bir bölü dört var. Aslında çok fazla uzaklaşmamışım. Hala geometrik olarak artıyor, değil mi? Ama artık gerçekten fark etmez. Maliyet ne olursa olsun, bir’den büyük olduğu sürece, mükemmel. Şimdi yapraklara bakıyoruz. Yapraklar, karekök M’ye kare kök M.. Karekök M’ yi, bunun yerine koyuyorum. M bölü B ile bazı sabitler elde ediyorum.

Kimin umurunda? Böylece her yaprak, M bölü B ve bunlardan çok var. Kaç tane? Özyineleme ağaçlarıyla çalışırken bunun tek sıkıcı tarafı her zaman, yaprakların sayımı olur. Haydi, N’ ye N matris ile başlayalım. Aşağı doğru , karekök N’ye karekök N matrise geldiğimizde duralım. Şu sanki bir şeymiş gibi görünüyor. O da ne, burada hile yapıyorum. Gerçekten mi? Bu kadar çok olması üzerinde durmaya değer. Pekala, iddia şu ve burada hile yapacağım. Yani, burada kehanet kullanacağım ve bunun niye böyle olduğunu meydana çıkaracağız. (N bölü kök M) küp yaprak.. O da ne? Galiba, burada ağacı görmek güç.

Ama,matrisin içinde görmek kolay. Matrisin içine girelim. Burada büyük matrisimiz var. Yarıya böldük. Özyinelemeyle yarıya bölüyoruz. Özyinelemeyle ikiye bölüyoruz Fikri kavrıyor musunuz, tamam mı? Şimdi, belli noktada bu sektörler, diyelim ki bu sektörlerden bir tanesi ve bu sektörlerin her biri önbelleğe sığıyor. Ve üçü de önbelleğe sığıyor. Çözümlemede özyinelemeyi o zaman durduruyoruz. Algoritma ise, sonuna kadar devam ediyor. Ama çözümlemede, M’ de duruyoruz diyelim, Şimdi, kaç tane yaprak veya problem var? Fakat bir dakika, bunlar hala belirgin değil. Pekala, buradaki yaprak parçalarının sayısının, N bölü kök M kadar olduğunu söylüyorum. Ama bu hala çok açık değil, çünkü bu şeylerden o kadar çok var ki. Ama zarar yok, şimdi bu boyutta parçalarla normal, sıkıcı matris çarpımının nasıl yapılacağını düşünelim.

Aslında bunu bana yaprakların söylemesi lazım. Bu büyük problemle başlıyorum; tüm bu küçük, küçücük şeylere özyineleme yaparak çıkıyorum, bunu onunla çarpıyorum, tamam, bu karekök M’ye karekök M parçasında. Pekala, onlarla kaç tane işlem, kaç tane çarpma yapıyorum? . Ama şimdi N matriksim bu küçük alt-matrisler cinsinden N bölü karekök M. Böylece bu boyutlu N bölü karekök tane alt-problem olur. Eğer bunu hesaplarsanız, normalde sabit boyuttaki şeyler elde ederiz ve bunlardan tam , M küp adet olur. Şimdi bu aşamada durur ve bunlardan kaç tane varsa da onun küpü kadar olacağını söyleyebiliriz. Tamam, bu bir çeşit işi kısa kesmek...

Bunu, yaprakların sayısını yineleme yöntemiyle çözebilirsiniz. Ama işte elde ettik bile. Böylece, buradaki toplam, N bölü... ne olduğunu hesaplayalım. bölü M’nin üç bölü ikinci kuvveti, yani yaprakların sayısı çarpı yaprak başına maliyet yani M bölü B. Bazı M’ler birbirini götürür ve bölü B çarpı karekök M’yi elde ederiz ki bu da, bölü B’ den karekök M faktörü kadar daha iyidir. Aslında bu bayağı fazla; önbellek boyutunun karekökü kadar. Bu optimal yani en iyi sonuçtur. İki düzeyli matris çarpım algoritmasıyla

elde edilebilecek en iyi bellek transferi sayısı bölü B karekök M‘dir.

Hayret, ders süresini aştım.

Bu algoritmayı önemli şeyler için genelleştirebilirsiniz, ama bunun en yararlı olduğu konu özyineleme yoluyla matris çarpımı yapmaktır.

Gelecek derste önbelleği dikkate almayan algoritmalar için başka özyineleme örneklerini göreceğiz.