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 23

Günaydın. Bugün çokizlekli algoritmalar üzerindeki araştırmalarımıza devam edeceğiz. Son defa, çizelgelemenin bazı veçheleri üzerinde konuştuk ve çokizlekli hesaplamayı tanımlamak için biraz da, bazı tarifler üzerinde durduk. Bugün, bazı algoritmalarla doğrudan uğraşacağız. Bugün öğretmeye başlayacağım şeyleri, dersin daha ikinci haftasında size verebilirdim, çünkü gerçekten basit şeyler ve esas itibariyle adeta böl-ve-fethet çekicini alıp, problemleri ardı ardına onunla ezip geçmekten ibaret olacak.

Aslında, gelecek hafta göreceğimiz önbelleğe alma derslerimiz de çok benzer. Bu sebeple, herkes, ana teoremi ve yineleme için yerine koyma metotlarını iyi bir şekilde gözden geçirsin, çünkü bunları kullanacağız. Ve tabiatıyla sınavda bütün konular olacak. Pekala, şimdi matriks çarpımıyla başlayalım. Boyut n’ye n olsun. Böylece problemimiz C eşittir A çarpı B’yi çözmektir. Bunu yaparken daha evvel görmüş olduğumuz böl-ve-fethet ‘i kullanacağız; Strassen’in metodunu kullanmayacağız,.

Yani sıradan olanı kullanacağız ve Strassen’i egzersiz olarak bırakacağım. Demek ki, anafikir olarak, matriks çarpıma, n’ye n matriks ve n / 2’ ye, n / 2 matriksler cinsinden bakacağız. Böylece, C yi, dört bloka bölüyorum ve aynı şekilde A ile B’yi de. Bu çıkanları çarpıyoruz ve bu bize şunu veriyor: Tüm dizinlerimin doğru olduğundan emin olun. Böylece, , iki adet n’ye n matriksin toplamını veriyor. Örneğin birinci sıra ile birinci sütunu çarparsam, birinci terim çarpı ’i bu matrikse koyuyorum, çarpı ikinci matrikste burada yer alıyor.

Böylece, diğer girişleri de ele alıp onları topladığım zaman sonucumu alacağım. Böylece, bunu yazabiliriz; bunun tek tahta üzerine sığacağından emin değilim, göreceğiz. Elimden geleni yapacağım. Böylece bunu çok izlekli bir program olarak yazabiliriz. Burada n, basitleştirmek amacıyla ikinin tam kuvveti olacak. İki matris ilave etmemiz gerekeceğinden, bir tanesini, doğrudan çıkışımıza, yani C’ye koyacağız; bu, birincisi olacak, ve bir de geçici matriks T’yi kullanacağız ve bu da n’ye n olacak.

Ve kod, şöyle bir şey olacak: eğer, n eşit bir ise, C[1,1] ‘si, A[1,1] çarpı B[1,1] değerini alır. Aksi takdirde, yapacağımız şey matriksleri bölüntülemek olur. Onları bloklar halinde bölüntülere ayırırız.Eğer programcılığımda akıllıysam, matriksleri bloklara bölmem ne kadar zaman alır? Efendim? Hiç zaman almaz, veya azıcık bir zaman alır. Evet, esas itibariyle birinci düzeydir, çünkü hepsi sadece dizin hesaplarıdır ve dizinleri değiştirmeniz gerekir. Mesela, A, B ve C ye ilaveten, bu şeyler basit geçişlerdir ve temelde bir sabit genel gider oluşturmanız gerekir. Ancak, özü itibariyle O(1) zamanlıdır.

Temelde matriksleri bölmek birinci düzey süre alır çünkü yaptığımız şey sadece dizin hesaplarıdır. Ve yaptıklarımız esnasında dikkat etmemiz gereken tek şey, dizinlerin izini doğru takip ettiğimizden emin olmaktır, tamam mı? Bu konuda herhangi bir soru var mı? Herkes takip ediyor mu? Pekala, bu standart programlamadır. Sonra yaptığım, bol bol altmatriks üretmektir. Üretiyorum, -- devam ediyorum, C_2-1, A_2-1ve B_1-1’i alır; iki ve bakalım, 2-2, evet, bu 2-1’dir. Tamam, bir sonraki sayfada devam ediyorum.

Girintimi yani indentation‘ı doğru mu yapıyorum, bir emin olmalıyım. Bu benim girinti hizam ve bu hizada devam ediyorum. Ve şimdi yaptığım şey, sonuçları T’nin içine koymak, sonra da, bu çarpımların hepsini bolca çıkarmış oluyorum. Bunun anlamı, bolca çıktı ürettiğimde, bir sonraki komuta gidebilmek ve bu çalışırken bile onu çalıştırabilmektir. Tamam, işte çok izlekli programlama kavramımız bundan ibarettir. Tekrar özetlersek, bu sekiz şeyi temizledikten sonra ne yapıyorum? Bu kod’daki bir sonraki adım nedir ? Sync yani senkron. Evet. Sonuçları kullanmadan önce, tüm bu yaptıklarımın sona ermesini beklemem lazımdır.

Tamam, içine bir senkron koyuyorum, “spawn ettiğim şeylerin tamamlanmasını bekle” dıyorum, ve sonra ne olacak? Evet, T ve C’yi toplamanız lazım. Öyleyse, bu işlemi, altyordam çağrısı yoluyla yapalım; tamam, sonra yapacaklarımız bitiyor. En sonda, bir return yani dönüş yapıyoruz. Pekiyi, toplama için kod’u yazalım, çünkü yapabilirsek toplamayı da paralel olarak yapmak istiyoruz. Burada yaptığımız şey, C’nin, C artı T olmasıdır. Tamam mı? Öyleyse, C nin içineT’yi ekleyeceğiz. Böylece burada, taban şıkkımızı yapmak için belli kod var ve bildiğimiz böl-ve-fethet uygulaması için de bölüntüleme işlemi var. .

Ve bu daha da kolay. Sadece spawn yapıyoruz yani bolca üretiyoruz, C_1-1, T_1-1, n/ 2; C_1-2, T_1-2, n2; C_2-2, T_2-2, n/2; ve sonra senkron ve sonunda dönüşle bitiriyoruz. Böylece burada yapmakta olduğumuz şey, sadece dört parçaya bölmekten ve bu parçaları bolca üretmekten ibarettir. Bu kadar. Hepsi tamamlanıncaya kadar bekleyip, sonra sonucu çıkarırırız. Bu kodun nasıl çalıştığı konusunda soru var mı? Ama unutmayın, burada, altta çalışan ve çizelgelemeyi işlemcilerimiz üzerinde çalıştıran bir çizelgeleyicimiz olacak. Ve bu çizelgeleyicinin ne kadar iyi iş yaptığı hususunda kaygılanmamız gerekecek. Son derste, iki önemli ölçüt olduğunu, bunların özü itibariyle çok sayıda işlemcinin başarımını ölçmede kullanılabileceğini öğrenmiştik. Bu iki ölçüt neydi?

Evet, ve T_sonsuz ama bunlara bazı adlar vermiştik. iş idi, güzel, T_sonsuz da kritik yol uzunluğuydu, iyi. Kritik yol uzunluğu ve iş konusunda, eğer kritik yol uzunluğu ve işi bilirsek, örneğin programımızın paralelizminin ne olduğunu saptayabilir ve bu programı işletebilmek için kaç işlemcinin en iyi yapı olabileceğini anlayabiliriz. Öyle ise, bu analizi yapalım: (n), bir mult code yani çoklu kod’la çalışan P işlemcinin yürütme süresi olsun ve (n) de, matriks toplama kodumuz için aynı şey olsun.

Böylece ilk analizini yapacağımız şey ‘iş‘ olacak. İşimize yanıtın ne olmasını ümit ediyoruz? İşi analiz ettiğimizde ne olmasını istiyoruz? Küçük olmasını ümit ediyoruz. Size bu kadarını söylerim. Bunun denektaşı testini neye karşı yaparız? Evet, eğer içinde hiç paralelizm olmayan bir şey yazarsak. Paralel kodumuzun bir işlemci üzerinde çalıştığında, dizisel kodumuz kadar süratli olmasını isteriz; yani, problemi çözmek için yazacağımız normal kod kadar.

Genel olarak, bu şeylerin bu şekilde çalışmalarını isteriz, değil mi? Matriks çarpımi için o basit yol nedir? Evet, . Elbette Strassen’in algoritması veya daha hızlı algoritmalarla ’den daha iyi sonuçlar alırız. Ama bu problem için, analizimizi özellikle üzerinde odaklayacağız. Strassen’i yapmanızı, egzersiz olarak size bırakacağım. Öyleyse, işi analiz edelim. Pekala, toplama için bir altyordamımız olduğuna ve çarpma kodu kullandığımıza göre, toplama işlemini analiz ile başlıyoruz. Elimizde (n) var, biri bana bunun için bir özyineleme verebilir mi? Bu kodun yürütüm süresini anlamak için gerekli özyineleme nedir?

Pekala, bu aslında ikinci haftanın konusuydu. Hatta birinci dersti. Bu konu ders iki ve en kötü ihtimalle ders üçte işlendi. Kaldığımız yere dönersek, (n) . Artı birinci düzey, doğru mu? Evet, doğru. Öyle ise, n bölü iki boyutunda çözmemiz gereken dört problemimiz var. Tamam, bunu görmek için bunu paralel şekilde yapmakta olduğumuzu bilmeniz gerekmez, çünkü buradaki iş, esas itibariyle, dizisel makinede yürütülmesi durumundaki iştir. Bu da demek oluyor ki, dört tane n / 2 boyutlu problem artı birinci düzeyde iş, toplam işdir.

Bu özyinelemeyi nasıl elde ettiğime dair bir soru var mı? Çok direkt mi oldu? Değilse bileyim. Evet böyle ise bu özyinelemenin çözümü nedir? Evet, düzeyidir. Bu olduğunu nereden biliyoruz? Evet, ana metot, böylece, , ’dir. Bunu O(1) ile kıyaslayın. Bu, farklı şekilde hükmeder.Öyleyse, yanıt yani ’dir. Bunu herkes hatırlıyor mu? Pekala, herkesin iyi şekilde hazır olmasını istiyorum çünkü, bu özyineleme ve böl-ve-fethet ve diğer şeyler, pek çok aydır görmemiş olsak da finalde yer alacak. Bu iyi çünkü dizisel ile aynı. Eğer, 2N x n boyutlu matrisleri toplamak zorunda olsaydım, bunu ne kadar sürerdi? zaman sürerdi.

Pekala, öyleyse girişin boyutu , ’dir. Yani, eğer girişin her parçasına bakmanız gerekirse, girişin boyutunda olmayacaksınız. Pekala şimdi matriks çarpımları işini yapalım. Böylece, gene bir özyineleme elde etmek istiyoruz. Öyleyse, buradaki özyinelememiz nedir? Efendim? Pek değil. Sekiz, doğru, iyi. Pek ala, sekiz, , n / 2, artı, evet, toplama için theta ve sonra theta içine yedirebileceğimiz bir ekstra theta daha var.

Asimptotik olması ne kadar muhteşem değil mi? Evet, gerçekten muhteşem. Peki, bunun çözümü nedir? Theta . Niye böyle? Eski kasları çalıştırıyoruz, değil mi? Gerçekten kütür kütür ses veriyor. İşitebiliyorum. Niçin? Evet, ana metot, çünkü bakıyoruz ve neyi kıyaslıyoruz? Evet, n’nin, log tabanı ikide 8 kuvvetine veya , ’ye karşı olduğunda, bu sonuncusu yani düzeyi hakim oluyor. Pekiyi, öyle ise dizisel ile aynı. Bu da dizisel ile aynıydı. Ve bu dizisel ile aynı idi. Bu iyi. Bir programımız olduğunu ve tek işlemci üzerinde temeldeki dizisel kodumuz ile aynı çalışmayı yapacağını biliyoruz.

Şunu yapabilirdik; eğer tüm spawn ve senkronlardan kurtulmuş olsa idim bu, dizisel algoritmanın yürütüm süresini tanımlayan kusursuz iyi bir sözde kod olurdu. Ve yürütüm süresinin tamamen aynı olması, çok hayret edilecek bir şey değil. Şimdi, yeni şeyleri, kritik yol uzunluğunu yapalım. Burada, A_sonsuz( n) var. Ooo… öyleyse bu kodun kritik yolunu toplayacağız.

Hımm, böyle bir kod parçasının kritik yolunu nasıl anlayacağım? Demek ki, o DAG’lardan birinin içine yayılacak. DAG neye benzeyecek? Ne çeşit muhakeme yürüteceğim? Öyleyse, sadece kodda ne olduğunu düşünmek ve DAG’ı düşünmemek gerçekten daha kolay. Evet? Evet, böylece, spawn’ların dördü de aynı şeyi yaydıklarından ve paralel hareket ettiklerinden, içlerinde sadece bir tanesine bakabilirim.

Veya genelde birkaç şeyi spawn ettiysem, spawn edilenler arasında, maksimum kritik yolu olanına bakarım. Böylece iş yaparken, çoklu altyordamlarım olduğunda, genellikle fazladan iş yapıyorum. Kritik yolda çalıştığımız zaman maksimumu yapıyoruz. Kritik yolun üzerinde çağırdığım altyordamlar maksimum olacaktır. Ama burada hepsi birbirine eşit. Öyleyse elde ettiğim özyineleme nedir?

Bundan elde edeceğim özyineleme ne olacaktır? Evet, A _sonsuz ( n / 2 ) artı bir sabit. Bu dört tane n’in en kötüsü, çünkü hepsi birbirinin aynı. Hepsi, problemin yarı boyutunda yarı boyutlu kritik yola bakan tek problem haline dönüşüyor. Pekala, herkes benimle mi? Öyleyse, bunun çözümü nedir? Evet, theta (log n)’dir. Bir kere daha, master teoremin ikinci durumu, çünkü bunun çözümü n’nin log 2 tabanlı bir kuvveti, yani n’nin sıfırıncı kuvvetidir.

Böylece, bu tarafta, elimizde bir var ve burada onu bir ile kıyaslıyoruz. Hepsi aynı, bu sebeple, o ekstra log n”yi ekliyoruz. Pekala, bir log n”yi ilave ediyoruz.Bu ana metodun ikinci durumudur. Çok iyi. Bu çok iyi çünkü kritik yol log n; log işe kıyasla çok kısa. Öyleyse bunu yapalım, çünkü biraz daha ilginç ama daha güç değil. Ya bu nasıl? Özyinelemesi ne olacak? Çarpımın kritik yolu ne olur?

Böylece, bir kere daha paralel olarak yaydığımız her şeyin maksimumu olacak, bu da simetri gereği onlardan biri olmakla aynı şeydir. Öyleyse, burada ne elde ederim? M_sonsuz ( n / 2) artı theta (log n). Theta log n, nereden geldi? Evet, toplama işleminden. Bu toplamanın kritik yoludur. Şimdi, bu neden tüm şu spawnların maksimumu değildir? Spawnları yayarken, onları başlatmadan önce senkronlarsınız. Ve senkron size hepsi tamamlanana kadar bekle der. Bu sebeple, sadece maksimumu alırsınız ve senkronların bir tarafındakileri diğer taraftakilerle toplarsınız.

Yani, senkronların etrafında ve paralel şekilde spawn yaptıklarınızı topluyorsunuz. Orası, maksimumu uyguladığınız yerdir. Fakat senkronunuz olması, ‘son’ demektir. Bu durumda maksimumu yaptığınız noktada her şeyin bitmesini beklemek zorundasınız. Bu, onunla paralel şekilde devam etmiyor; ondan sonra devam ediyor. Dolayısıyla, buradaki kritik yol ne olursa olsun, sonsuz sayıda işlemcim de olsaydı, bu noktada gene de beklemem gerekecekti ve o da, bu sebepten, geri kalan çalışma ne kadar kritik olursa olsun, bunun kritik yolunu ekleyecektim.

Herkes için açık mı? Tamam, bu takdirde, şu özyinelemeyi elde ediyoruz. Ve bunun çözümü ne oluyor? Evet, theta log kare n . Bir kere daha, ana metodun ikinci durumu gereği, bu log n’ye karşı bir sabit olarak sonuçlanır; bunlar polinomsal bir değer veya bir logaritma faktörü kadar değişiklik göstermezler. Böyle bir durumda yaptığımız bir ekstra log faktörü eklemektir. Böylece, söylediğim gibi, ana metodu yeniden gözden geçirmekte fayda var. Pekala, bu çok iyi. Böylece şimdi elde ettiğimiz paralelizme bir bakalım.

Çarpım için burada yapacağız. Pekala, çarpım için paralelizm nedir? Paralelizmin formülü ne? Bu problemde kullandığımız simgelem P_bar dır.Paralelizm ne kadar olacak? Alacağım oran nedir? Evet, (n) bölü M_sonsuz (n). Pekiyi, bu , bu da . log , pardon, log kare n. Bu paralelizm oluyor. Bunun anlamı, bu sayıda işlemci kullanabilir ve bu uygulamadan doğrusal bir hızlanma elde etmeyi ümit edebilirsiniz. Ama paralelizmden daha fazla işlemci kullanmaya kalkarsam doğrusal hızlanma elde etmeyi de artık ümit edemem. Çünkü çalışma zamanı kritik yol uzunluğu ile orantılı olacaktır ve daha fazla sayıda işlemciyi işe koşmamın bana fazla bir yararı olmayacaktır.

Şimdi buna burada ne olduğunu kavrayabilmek için bakalım. Sabitlerin işlemlerimizle hiçbir ilgilerinin olmadığını ve bin kere bin boyutlu matrislerimiz olduğunu tahayyül edelim. Öyle ise paralelizmimiz, bölü 1000’in log karesidir. 1,000 in log’u ne eder? On. Yaklaşık olarak değil mi? 1,000’in log’u, yaklaşık olarak ondur; yani, bu olur. Öyleyse paralelizm var. Pekiyi, ne kadar büyük bilen var mı? On milyon işlemci. Pekiyi, on milyon işlemcisi olan bir makineyi bilen var mı?

İçinizde en büyük işlemci sayısı olarak kim ne biliyor? Yok, o kadar da değil. IBM’in Blue Jean’inin anormal sayıda, 10000 i aşkın işlemcisi var. Ya. Onlar, tek-bit’li işlemciler. Pekala, bu çok büyük bir sayı ve paralelizmimiz de pratikte olabilecek işlemci sayısından çok daha büyük. Böylece böyle bir makineyi kullanmayı ve bundan çok iyi bir performans elde etmeyi bekleyebiliriz. Çünkü bu çapta bir algoritmada, başarım açısından bir sınırlama olması asla söz konusu olmayacaktır.

Bununla beraber, kullanabileceğimiz bazı kaçamak yollar olabilir. Bu kodun bir özelliği bazı overhead yani genel giderlerin olmasıdır. İilk bakışta belirgin değil, çünkü bu kodu sizinle birlikte hiç çalıştırmadık; aslında bunu yapabilirdim. Bu kodda, şu geçici matriks T var ve yürütüm yığıtına bakarsanız, T’yi önce tahsis ediyor, sonra bertaraf ediyoruz vs. Ve gerçek kodun başarımına baktığınızda, artık algoritma konusunda bir temeliniz olduğu için bu işi öngörüyle yapmaya kendinizi hazır hissediyorsunuz. Şüphesiz, sadece asimptotik bir davranıştan daha fazlasını elde etmek istiyorsunuz. Gerçek şeyler üzerinde, gerçek başarım sağlamak istiyorsunuz. Sabitler ile de bu anlamda ilgileniyorsunuz. Diğer bir açıdan geniş ve geçici bir değişkene sahip olmak önemli bir genel gider getiriyor.

Nitekim gerçek koda baktığınızda sıkça karşılaştığınız şey, eğer alanı eniyileştirebilirseniz, süreyi de en-iyileştirmiş oluyorsunuz. Aynı şekilde, eğer kodunuzu daha küçük alanda kullanabilirseniz, süre açısından da daha kısa zaman kullanmış olursunuz ve bu bir sabit faktör avantajı olur. Ayrıca, bu sabitler toplandığında ve bir temel algoritmanız olduğunda, sizin kodunuz ile başkasının kodu arasında hız bakımından lehinize bir faktör de oluşabilir. Böylece bu örnekteki fikir, ihtiyaçtan fazla paralelizm olduğundan paralelizmin alan verimliliği adına feda edilmesidir.

Pekala, fikir T’den kurtulmak. Öyleyse, bunu atalım. Burada T’den nasıl kurtulabileceğimi söyleyebilecek kimse var mı? Bu geçici matriksden kurtulmayı. Evet? Evet. Yani, C’nin içine ekleyerek mi? Buradaki mesele, oraya geldiğinizde, eğer her ikisi de C’nin içine alınırsa mümkün olur ama bu halde, iki alt-hesaplama arasında bir girişim söz konusu olur. Şimdi, bu işi yapmanın yolları vardır, ancak siz güncelleştirmenizi yaparken, başka birinin güncelleştirme yapmadığından emin olmak için, üzerinde konuşmayacağımız mutual exclusıon yani karşılıklı dışlama gibi kavramlar konusunda kaygılanmak zorundasınız; ve yarışma koşulları yaratmamaya özen göstermelisiniz.

Fakat bunu, gerçekten bu bağlam içinde ve yarışma koşulları üretmeden de yapabilirsiniz. Evet, doğru. Gerçekten. Yani itibar edeceğiniz fikir, dördünü de spawn etmektir. Bunların hepsi kendi C kopyalarını güncelleştirir, sonra da ,C’nin içine kendi değerlerini ekleyen diğer dört tane spawn edilir. Bu, mult add yani çarpım-toplam olarak adlandıracağımız bir kod parçasıdır. Bu, C’nin, C artı (A çarpı B) değerini almasını sağlıyor. Yani, ilk başta, C’yi sıfırlamanız gerekecek ama bu işi toplama koduna benzer kod ile düzeyinde iş ve log n düzeyinde kritik yol ile yapabiliriz.

Böylece bu uğraşmak zorunda olduğumuzun büyük kısmı olmayacaktır. Pekala, işte kodu. Esas olarak, taban durumu ve bölüntüyü yapıyoruz; bunun kodunu yazmayacağım , , , , n / 2’ den oluşan bir çarpım toplamını çoğaltıyoruz ve aşağıda dördüncüye kadar bunlardan bir kaçını daha yapıyoruz. Ve sonra, bir senkron koyuyoruz. Bundan sonra, diğer dördü yapıyoruz --- -- onu da bitirdikten sonra yine senkron var.

Bu kodu herkes anlıyor mu? Esas itibariyle aynı hesaplamayı yaptığına dikkat edin. Gerçekte, artık bunu toplam olarak çağırmaya gerek kalmıyor çünkü bunu çarpımın bir parçası olarak yapıyoruz, çünkü içine ekliyoruz. Ancak mutlak başlatmamız gerekiyor. Evet, bu durumda matriksi mutlaka başlatmamız gerekiyor. Yani başka bir aşama daha var. Bundan ötürü, bu kodun semantics yani anlambilimini herkes anlıyor. Öyle ise, analiz edelim. n’nin Çarpım- toplamı’ nın işi nedir? Aslında aynı şey değil midir?

Bu düzeyindedir. Çünkü dizisel kod, yaklaşık olarak yukarıdaki dizisel kod ile aynıdır. Tamam, pek değildir. Fakat esas itibariyle aynı özyinelemeyi elde edersiniz, sadece bunda, toplama işlemi yoktur. Burada aynı özyinelemeyi birinci düzeyde elde edersiniz. Pardon, birinci düzey şurada yukarıda. Böylece, çözüm hala düzeyindedir. Bu nedenle çok güç olmadığını düşünüyorum. Kritik yol uzunluğuna gelince; yazalım, böylece n’nin çarpım-toplamı eşittir, pekala, bu kod için özyinelemem ne olur?

Evet, 2MA_sonsuz, n bölü 2 artı düzey 1. Artı birinci düzey, evet. Demek ki, kritik yol için bu dört şeyi çoğaltacağımızdan, onların maksimum olanı hangisiyse onu alırız ama simetrik olduklarından bu herhangi biri olabilir. Tamam, bundan sonra beklemem lazım. Ve sonra tekrar yaparım. Böylece, o senkron bir kere daha analizde kritik yolda bir artı anlamına geliyor ve bunlar da maksimumunu alıp paralel olarak çoğalttığım şeyler. Herkes bunu görüyor mu? Böylece bu özyinelemeyi elde ediyorum: 2MA (n/2) artı birinci düzey; ve bunun çözümü nedir?

Evet, o n düzeyindedir, çünkü, n’nin log tabanı ikide 2’si n’dir. Ve bu birden büyüktür, böylece n düzeyini elde ederiz. Tamam mı? Böylece paralelizm, P_bar eşittir, M(n) bölü MA_sonsuz (n) olur; bu da eşittir, bölü n, yani düzey olur. Böylece, örneğin 1,000’e 1,000 bir matriksler için; bu konuya değinmişken, bugünlerde 1000’e 1000 küçük bir matriks sayılıyor çünkü, sadece bir milyon girişe tekabül ediyor.

Bunu dizüstü bilgisayarınızda kolaylıkla çalıştırabilirsiniz. Yani 1,000 çarpı 1,000 matris ile, paralelliğimiz yaklaşık ‘dır. Bir kere daha bu günümüzde yapacağımız herhangi şey için yeterince büyük paralelliktir. Ve aslında uygulamada daha da hızlıdır ; çünkü, daha az alan gerektirir. Ancak teori ya da araştırma makalelerinde herkes azami paralelizm elde etmek için çabalıyor; bu oynanacak iyi bir oyundur, ama yegane oyun da değildir.

Bilhassa, eğer çok paralelizminiz varsa yapacağınız en kolay şeylerden biri, paralelizm konusunda biraz geri çekilmek ama bu sayede kodunuz içinde istediğiniz başka özellikleri kazanmak olabilir. Gördüğümüz, bunun güzel bir örneğidir. Nitekim ve bu bir egzersiz olacak; iş için düzeyine ve kritik yol için de log n düzeyine ulaşmayı başarabilirsiniz ki, bu paralelizm bağlamında bu iki algoritmadan daha iyidir.

Bu size, bölü log n paralelizm veriyor. Öyleyse, bu bir egzersiz olacak. Yararlı olacak diğer bir egzersiz, paralel Strassen, tamam mı? Strassen ile aynı şeyi yapın, çözümleyin ve Strassen kodundaki çalışma kritik yolu ve paralelizm ne olduğuna bakın. Pekala, matriks çarpımı hakkında herhangi bir soru var mı? Evet? Evet, kritik yola bir log n ilave eder ki, n ile kıyaslandığında, bu hiçbir şey değildir. Efendim? Her şeyden önce C’nin sıfır olduğundan emin olmalısınız. BU durumda tüm girişleri sıfırlamanız gerekir, bu iştir ve yapmakta olduğunuz iş ile kıyaslanamayacak bir değerdir. Ve kritik yola eklenecek bir log n’ye mal olur ki bu harcadığınız düzey n ile kıyaslandığında, bir hiç mertebesindedir.

Matriks çarpımları hakkında başka soru var mı? Söylediğim gibi bunlar, ikinci haftanın falan ders konularıydı. Bir yorumunuz mu var? Evet yapabilirsiniz. Evet yapabilirsiniz. Buna bakmak enteresandır. Aslında daha sonra konuşacağız. Dersler bittikten sonra bir araştırma makalesi yazacağız çünkü ortada enteresan açık sorular var. Başka konuya, belki haftalarca önce kurtulduğunuzu sandığınız konuya, sıralama konusuna geçelim.

Sıralamaya geri dönüyoruz. Ancak bu defaki, paralel sıralamanın nasıl yapılacağı, tamam mı? Önemli ve çok boyutlu bir problem. Şöyle bir bakıp sıralama için kullanılabilecek algoritmaları düşünürsek, hangisi paralelleştirme bakımından kolay olabilir? Süratli bir sıralama için; çabuk sıralama, evet bu iyi bir seçimdir. Evet, hızlı paralelleştirme ve çözümleme açılarından çok iyi bir algoritmadır. Fakat, unutmayın, çabuk sıralamanın çözümlenmesi diğer algoritmalara oranla oldukça karmaşıktır. Paralelleştirmesi kolay gibi görünen diğer algoritma hangisidir? Birleştirme sıralaması. Ne zaman öğretmiştik? İlk gün. Pekala, birleştirme sıralamasını yapalım, analizi biraz daha kolaydır. Aynı denemeyi, çabuk sıralama ile de yapabiliriz.

Birleştirme sıralaması ile başlıyoruz. Bu p’den r’ye kadar A’nın sıralamasını yapacak. Eğer p, r’den daha küçükse, orta elemanı elde ederiz ve sonra çoğaltacağız çünkü hatırlarsanız birleştirme sıralaması yaparken, önce iki alt-dizilimi özyinelemeli olarak sıralarsınız. Paralel olarak da yapmamanız için hiçbir neden yoktur. O nedenle, paralel olarak yapalım. Çoğaltalım. A,p,q’ya birleştirme sıralaması uygulayalım, çoğaltalım; sonra da , A,q+1,r’nin birleştirme sıralamasını yapalım.

Ve sonra bunların tamamlanmalarını bekleyelim. Senkronlarınızı unutmayın. Bat veya yüz. Pekala, sonra bu yaptıklarımızla ne yapacağız? Birleştiririz. Yani, A,p,q,r’yi birleştiriyoruz: Bu da A[p’den q’ya kadar] ve A[q+1’den r’ye kadar] ‘ın birleştirmesi olur. Ve birleştirdikten sonra işimiz biter. Bu, ilk gün gördüğümüz kod ile aynıdır, farkı birkaç çoğaltma ve senkron olmasıdır. Haydi bunu çözümleyelim. İş, (n)’dir. Bunun için yineleme nedir?

Bu gerçekten birinci güne dönüş gibi oluyor. Gerçekten, bunu ilk gün yaptık. Pekala, özyinelemesi ne? 2(n/ 2) artı düzey n; birleştirme n düzeyinde bir işlemdir, tamam mı? Ve bu bize, n log n çözümünü verir; çözümü bilmeseniz de cevabı bilmeniz gerekir ve bunun dizisel koddakinin aynı olması şaşırtıcı değildir. İstediğimiz budur. Pekiyi, kritik yol uzunluğu, T_sonsuz(n) eşittir, T_sonsuz (n/ 2) artı, gene düzey n.

Bu da, düzey n’ye eşittir, tamam mı? Öyleyse, paralelizm, P_bar eşittir,(n) /T_sonsuz(n) eşittir theta log n. Çok fazla paralelizm mi var mı? Hayır, onun için teknik bir ismimiz var: Çelimsiz yani puny. Bu çelimsiz paralelizmdir. Ya log n? Şimdi bu muhtemelen, piyasada satılan küçük çaptaki bazı işlemciler, bilhassa çok damarlı işlemciler ve daha küçük SMP’ler, Symmetric Multi Processors yani, simetrik çoklu işlemciler için gerçekten uygun bir algoritmadır.

Biliyorsunuz, SMP’lerin, dört veya sekiz civarında işlemcisi olur. Bunlara uygun olabilir. Çok fazla paralelizm yok. Bir milyon eleman için, log n, yaklaşık 20’dir. Ve ayrıca sabit genel giderler vs vardır. Bu, hiç de fazla paralelizm değildir. Soru? Evet, öyleyse nasıl daha iyi yapabiliriz? Demek istediğim, birleştirme düzey n alıyor. Eğer daha iyisini yapmak istiyorsam, ne yapmam lazım? Evet?

Yerinde sıralama yani sort-in place, ama mesela,çabuk sıralama ve bölme yaparsanız, gene doğrusal zaman bölüntüsü elde edersiniz. Böylece aşağı yukarı aynı durumda olursunuz. Fakat burada başka ne yapabilirim? Paralel birleştirme. Yani, birleştirmeyi paralel biçimde yürütelim; orası kritik yolun bulunduğu yer.Çok kısa kritik yolu olacak bir birleştirme programı modelini nasıl yapabileceğimizi bulmaya çalışalım. Birleştirmeyi paralelleştirmelisiniz. Bu muhteşem; bu derse katılanların, bir bakışta işlerinde neyi nereye koymaları gerektiğini sezdiklerini görmek o kadar hoş ve güzel ki.

Algoritmalar hakkında bilmeniz gereken şey,kodlama yaptığınız zaman bir program yaratmanızı önlememesidir. Bir programı kodlama konusunda algoritmalar dışında daha çok şey vardır ve bunları ilk gün de konuşmuştuk. Mesela, algoritmayı modüler yapmak ve bakımını sağlamak ve buna benzer pek çok şey. Fakat algoritmaların yaptığı bir şey, dikkatinizi nerede toplamanız gerektiğini size söylemesidir.

Mesela bunların dördünü elde etmek ümidiyle, n / 4 boyutunda çoğaltayım diye düşünmenin bir anlam yoktur, çünkü işi yaptığınız yer orası değildir. İşi, birleştirmenin içine koyarsınız, çünkü işin tıkandığı yer orasıdır. Algoritmaların güzel tarafı, mühendislik pratiğinde algoritmik tasarımlar yaparken emeğinizi harcamanız gereken yere sizi süratle yönlendirmesidir. Bu sebepten birleştirmenizi paralelleştirmelisiniz.

Birleştirme konusunda kullanacağımız temel fikir şudur: Genelde birleştirme yaparken, özyinelemeli birleştirmemizi yaparken iki dizilime sahip oluruz. Bunlara A ve B diyelim. Orada A dedim. Keşke A’yı kullanmayıp, başka türlü adlandırsaydım. Fakat notlarımda hep böyle, öyleyse notlara bağlı kalalım. Burada biraz daha fazla alan lazım, bakalım ne oluyor? İki dizilimimiz var. Onlara A ve B diyorum, tamam mı? Ve bundan sonra yapacağımız; bunlar önceden sıralanmış olacaklar. Bizim işimiz bunları birleştirmek. Sonra yapacağım şey, A’nın orta elemanını almak.

Böylece bu, birden l’ye gidiyor diyelim, bu da, birden m’ ye gidiyor. Pekala, ortadaki elemanı alacağım, I / 2’deki eleman diyelim. Ve şimdi yapacağım, B diziliminde nereye gittiğini anlayabilmek için, ikili aramayı kullanmak olacak, tamam mı? Bu eleman nereye gidiyor? Burada bir noktaya gidiyor; bu noktada j var ve burada da j artı 1 var. Bunlar zaten sıralanmış oldukları için bütün bu şeylerin, A [ l /2 ]’ye eşit ya da ondan daha küçük olduğunu, ve tüm bu şeylerin de A [ l /2]’ye eşit veya daha büyük olduklarını biliyoruz. Ve aynı şekilde o eleman buraya geldiği için, tüm bu şeylerin, A [ l /2 ]’ye eşit veya daha küçük olduklarını anlıyoruz.

Ve doğal olarak, tüm bu şeyler de A [ l /2 ]’ye eşit veya daha büyük olacaktır. Öyle ise, şimdi yapabileceğim şey, bir kere bunun nereye gittiğini anladıktan sonra, bu dizilimi bununla ve bu dizilimi de bununla özyinelemeli olarak birleştirebilirim. Sonra da eğer ardı ardına bağlayabilirsem, birleştirilmiş dizilimime sahip olurum. Haydi, kodu yazalım. Herkes, burada olanın bitenin farkına vardı mı? Birleştirmeyi nasıl paralelleştireceğimizi kavradı mı? Şüphesiz, j herhangi bir yerde olabileceğinden biraz karışacağını görebiliyorsunuzdur. Paralel birleştirme kodum burada ve bunu C [1..n]’nin içine koyacağız ve böylece n elemanım olacak.

10.

Bu, A ile B’nin, C’nin içinde birleştirilmeleridir ve n eşittir I artı m olur. Demek ki, iki dizilimi alacağız ve üçüncü dizilimin içinde birleştireceğiz, tamam mı? Genellemeyi kaybetmeden, l’nin m’den daha büyük olduğunu söyleyeceğim; şurada gösterdiğim gibi ve eğer değilse ne yaparım? Tamamen tersini, değil mi? Böylece, hangisinin daha büyük olduğunu çıkarırım. Bu kontrolü yapmak bana sadece düzey bire mal olur, veya o civarda bir şeye.

Ve sonra bir taban durumu yaparım. Biliyorsunuz, eğer iki dizilim boş veya her ne iseler ve yeterli derecede küçüklerse, uygulamada yapacağınız dizisel birleştirmedir. Eğer yeterli derecede küçükseler diyorum, böylece fazla bir paralelizm elde etmeyi ummuyorum. Burada fazla iş yoktur. Dizisel birleştirme de yapabilir ve biraz daha verimli olabilirsiniz, tamam mı? Böylece, taban şıkkını yapın. Sonra yapacağım şey, B [ j ]’nin, A[ l /2]’den daha küçük veya ona eşit olduğunda ve B [j+1]’den daha küçük veya ona eşit olduğunda j’yi ikili arama yoluyla bulmaktır. İkili aramayı ne zaman işledik? Oh evet, ilk haftaydı, değil mi?

İlk etüt yada öyle bir şeydi. Evet, hayret verici bir şey. Pekala, şimdi yapacağımız, A[1..l/2], B[1..j]’nin P-birleştirmesini çoğaltmak ve bunu C [ 1.. l/2 +j]’nin içine yapıştırmaktır. Benzer şekilde, A [ I/2+1..l ]’nin, B[ j+1..m]’nin ve C[ l/2+j+1..n]’nin P-birleştirmesini çoğaltabiliriz. Bundan sonra da senkron yaparım. Yani kod oldukça anlaşılır haldedir; burada yapılması gerektiğini söylediğim şeyin aynısıdır. Çözümlemesi ise biraz daha karmaşıktır; daha karmaşıktır. Bu nedenle çözümlemeyi yapmadan önce bunu anlamaya çalışalım. Neden, küçük dizilim yerine, ortadaki büyük dizilimin orta elemanını seçmek istiyorum?

Oradaki mantığım, nedir? Bu aslında işin anahtarı, yani çözümlemenin anahtar kısmıdır. Evet? Evet, örneğin içinde sadece bir tane eleman olan, veya birkaç tane eleman olan B’yi düşünün; bunu A’nın içinde bulmak demek, A’nın başına yakın bir yerde bulmanız demektir. Ve bu durumda çok büyük alt problemlerle baş başa kalabilirim. Öte yandan işaret ettiğiniz gibi buradan başlarsam ve eğer tüm elemanlarımın sayısı n ise, şu yinelemelerden hangisi en küçüğü olabilir?

n bölü 4 en küçüğü olabilir. Evet, çünkü toplamın en azından dörtte bir elemanı burada sol tarafta veya burada sağ tarafta olacaktır. Eğer özyinelememi ters yöne yaparsam, yaklaşık n’ye yakın büyüklükte bir özyineleme elde edebilirim ki ve bu da tıpkı çabuk sıralamanın çözümlenmesinde iyi bir bölme elemanımız olmadığında karşılaştığımız farklılığı andırır.

Bölme elemanı ortalarda bir yerdeyse bu gerçekten iyi bir durumdur, oysa, her zaman bir uçtaysa, bu araya yerleştirme sıralamasından daha iyi değildir. Böl ve fethet’inizden en azından sabit bir kesri, logaritmik davranış elde etmek için atmak istersiniz. Pekala, bunu çözümlemede göreceğiz. Ancak buradaki anahtar husus, özyineleme yaparken daha küçük olan hangisiyse orada en az n bölü 4 elemanımız olacaktır. Haydi, başlayalım. İş, bunun güç tarafıdır. Onun yerine, kritik yol uzunluğundan başlayalım. Pekala, kritik yol uzunluğuna bakın.

Böylece paralel birleştirme, PM_sonsuz(n) en çok, eğer, küçük parçada en az dörtte bir varsa bu ikisinin daha büyük olanı ne olur? Şuradaki iki şey. Burada çoğalan iki problem var. Şimdi, gerçekten maksimum uygulaması yapmamız lazım, çünkü simetrik değiller. Hangisi daha kötü olacaktır? Bir tanesi, n’nin azami dörtte üçü olabilir. 3n / 4 artı, pekala, o iki taneden en kötüsü elemanların dörtte üçü olacaktır. Artı ne?

Artı, log n. log n, nedir? İkili aramadır. Pekiyi, bu bana neyin çözümünü veriyor? Bu sonunda n’nin nesi oluyor? n’nin sıfırıncı kuvveti, doğru. Tamam, bu bir‘in, n’nin log tabanı üç bölü dört kuvvetindeki değeridir. Pekala, birin herhangi bir tabanda logaritması sıfırdır. Öyleyse, n’nin sıfırıncı kuvveti log n ile kıyaslandığında, bu log kare n olarak yazılabilir. Böylece, log kare n düzeyinde bir kritik yol olur. Bu iyi haber.

Şimdi, işi, büyük bir miktar şişirmediğimizi ümit edelim. Böylece iş, P(n) eşittir, ama bölüntünün ne olduğunu bilmiyoruz; ona alfa diyelim. Öyleyse, bir tarafta alfa n var ve öbür taraftaki iş de, P ((1- α)n) artı, ve sonra gene ikili arama için log n düzeyi; ki orada, daha evvel söylediğimiz gibi, alfa dörtte bir ile dörtte üç arasında olacaktır.

Bunun gibi bir özyinelemeyi nasıl çözeriz? Bu çeşit bir özyineleme için kullanılan teknik isim nedir? Hairy yani karmaşık. Bu bir Karmaşık-Özyinelemedir. Karmaşık özyinelemeleri nasıl çözeceğiz? Yerine koyma ile. Pekala, iyi. Yerine koyma. Öyleyse, P(k) daha azdır veya eşittir… Burada iyi bir tahmin yapmak istiyorum, çünkü bununla oyalanmıştım. Doğrusal olmasını istiyorum, onun için burada doğrusal bir terim olacak; a çarpı k eksi, ve sonra b log k koyacağım. Bu düşük düzeyli bir terimi çıkartma hilesidir, bunu hatırlıyor musunuz? Yerine koymada, daha kuvvetli kılmak için.. Eğer sadece a çarpı k yapsam, iş çalışmayacak çünkü, burada n elde edeceğim ve yerine koymayı yaptığımda, a-alfa-n elde edeceğim ve sonra a bir-eksi-alfa-n ve bu ikisi yan yana buradaki her şeye eklenecektir.

Yani bu terimi eklediğimde bunu azaltmanın yol yoktur. Öyleyse, ikisinden de bir şeyler çıkarmalıyım ki bu terim yedirilebilsin, değil mi? Bu adımları atlıyorum, çünkü o işlemleri ikinci derste falan yapmıştık.Böylece, bıraktığımız noktaya yani, a ve b’nin sıfırdan büyük olduklarını tahmin edeceğim noktaya gelmiş oluyorum. Haydi Yerine Koymayı yapalım. Elimizde, n nin P(n) var, bu eşittir veya daha azdır.. Bu iki terim için tümevarım hipotezi uyguluyoruz.

Böylece, a(α n) eksi b log(α n) artı a(( 1- α) n) eksi b log (( 1- α)n); kendime yetecek alan bırakmadım, bunu buradan şuraya taşıyayım ki çok alan kullanmayayım.

Devam ederek eksi b log (( 1- α)n) artı Θ( log n) elde ederim. Bu nasıl? Bu konuda herkes rahat mı? Bu sadece yerine-koymadır. Şimdi biraz cebir yapalım. O da, eşittir: a çarpı alfa n, a kere bir eksi alfa n, sadece a çarpı n’dir. Tamam, eksi b o kadar kolay değil. Bir b terimim var, şimdi, orada bir sürü şeyim var: log (α n) var, sonra eksi log (( 1- α)n) var, sonra da artı Θ( log n) var.

Bunu doğru mu yaptım? Uygun görünüyor mu? Öyle ise bakalım. Şimdi, bunların bazılarını çarpımla dışarı çıkaralım. Böylece a çarpı n eksi b kere alfa n’nin log’u sadece log alfa’dır, artı log n’dir. Sonra artı log( 1- α), artı log n, artı Θ( log n) var. Bunların hepsi logaritmalar için kurallarımızı uyguladığımız cebirdir. Şimdi bunu benim çözümüm, eksi arzuladığım çözüm, eksi bir kalan olarak yazayım: a kere n, eksi b log n, eksi, ve şu b log n’lerden biriydi, tamam mı? o burada; diğerleri de bunun içinde yer alacaklar. b çarpı log n artı log(α( 1- α) eksi parantezler çok oldu.

Kapattıklarımın sayısı doğru mu? Onu kapa, onu kapa, iyi, eksi Θ( log n). İkinci parantez orada. Vay canına yazım bozuluyor. Pekala, doğru yaptım mı? Parantezlerim doğru mu? O uyumlu,o uyumlu, o uyumlu, iyi. Ve b sona ulaşıyor. Tamam, iyi. Ve ben eğer b’yi yeterince büyük seçersek, bunun a çarpı n eksi b log n’e eşit veya ondan küçük olduğunu savunuyorum. Tamam, bu grup buna hükmediyor, çünkü temelde burada bir log n var ve bu da bir sabit. Tamam. Şimdi eğer b’ yi arttırırsam çarpı log n ile, buradaki log n düzeyli sabiti aşabilirim.

Asimptotik simgelem ile gizlenmiş olan sabit ne olursa olsun, b çarpı log n artı alfanın log alfa çarpı bir eksi alfa, theta log n’ ye hükmeder. Ve ben, başlangıç koşulları ne olursa olsun, onları kontrol edebilecek büyüklükte taban durumunu seçebilirim.Böylece, a’yı, tümevarım taban şartlarını tatmin edecek büyüklükte seçeceğiz. Böylece, P(n) Θ(n)’ye eşittir, tamam mı?

Aslında O düzeyini göstermiştim. Alt sınır olan omega n’yi almak daha anlaşılırdır, çünkü bunda özyineleme daha kolaydır ve aynı yerine koyma uygulanabilir. Yani alt düzey terimleri çıkartmak zorunda kalmam. Öyleyse, sadece O değil, aslında theta. Bu bize bir log verir; kritik yol ne demiştik? Kritik yol paralel birleştirme için logaritma kare n’dir. Öyle ise, bunu kullanarak birleştirme sıralamasını çözümleyelim. İş, bildiğimiz üzere(n), bu da Θ (n log n),çünkü, biraz önce çözümlediğimiz işimiz n düzeyinde idi; dizisel algoritma için olanla aynı, tamam mı?

Kritik yol uzunluğu, şimdi, T_sonsuz (n)’ye eşittir. Normal birleştirme sıralamasında, yarım boyutlu bir problemimiz var, yani T(n/2), artı birleştirme için benim kritik yolum artık daha evvel olduğu gibi n düzeyinde değil. Aksine, oradaki arkadaş? Logaritma kare n, evet. Böylece bu bize, theta log küp n verir. Bu durumda paralelizmimiz, theta (n) bölü log küp n Ve bugüne dek, alınmış en iyi sonuç, af edersiniz, log kare n, haklısınız, log kare n, çünkü bu, n log n bölü log küp n dir.

n bölü logaritma kare n’dir, tamam mı? Ve en iyi sonuç, şimdi acaba burda bir yazım hatası var mı diye merak ediyorum. Evet en iyisi : P_bar eşittir Θ( n / log n)’ dir. Doğru mu? Sanıyorum evet. Bugüne kadar en iyisi. Günümüzün, en iyisi. Yanılmıyorsam bunu yapan kişi Occoli. Yani aslında oldukça iyi bir sonuç elde ediyorsunuz ama gördüğünüz gibi sıralamanın paralelleştirme uygulaması gerçekten güç bir problem olarak beliriyor; gerçekten iyi sabitler elde etmeniz ve tamamen aynı çalışmayı sağlamanız zor. Matriks çarpımında paralel çalışmayı daha kolay gerçekleştirebilirsiniz ve belli miktarda işlemci ile doğrusal hızlanmayı daha sağlıklı elde edebilirsiniz. .

Pek çok paralelizm var ve gittikçe artan sayıda işlemcide, her işlemcinin tam güç çalışması bekleniyor. Sıralama ile tipik olarak benim tecrübeme göre % 20 kaybınız oluyor, herhalde devam eden diğer işlemler nedeniyle; çünkü bu birleştirme algoritmasının sabitlerini normal birleştirmenin sabitlerine kadar indirmeniz için gerçekten çok çalışmanız gerekir. Çok iyi bir algoritma olduğu doğrudur, yani kendi başına çalışan ve iki listeyi alıp birleştiren, demek istiyorum. Bu sebeple, ilginç bir konudur ve sıralama konusunda pek çok kimse çok sıkı çalışıyor, çünkü bir yanda sabitleri azaltmaya çalışırken diğer yanda işlemci sayısı arttıkça başarımın artmasının nasıl garanti edilebileceği çok önemli bir sorundur. Pekala, böylece paralellik ülkesinde biraz gezindik ve gelecek hafta ön belleğe alma üzerinde konuşacağız ve bu özellikle algoritma alanında ve programcılıkta çok önemli bir diğer konudur.