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.   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  , 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