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  22

                                                                                                                                                  Sadece dört dersimiz daha kaldı, Prof. Demaine ile birlikte ileri seviyedeki konular üzerine iki dizi ders vermeyi kararlaştırdık. Bu nedenle bugün ve gelecek derste, probleminizi birden fazla işlemcinin parçalara bölüp saldırdığı algoritmalar, yani paralel algoritmalar üzerinde konuşacağız. Bu çok sıcak ve güncel bir başlık, çünkü chip yani yonga üreticilerinin hepsi bugünlerde içinde yonga başına birden fazla işlemcinin olduğu çok damarlı işlemciler üretiyorlar. Bu sebepten, bu konu hakkında bir şeyler bilmek faydalı olacak. Göreceğimiz ikinci konu da, önbelleğe alma yani caching  ve önbellekli sistemler için algoritma tasarımlarının nasıl yapılacağını kapsayacaktır.

Şimdiye kadar her şeye, sanki yalnız tek düzeyli bellekler varmış varsayımıyla yaklaştık ama bazı problemlerde bu programcılık anlayışı realist bir model olmaz. İçinde önbellek hiyerarşisinin olduğu ve bundan avantaj sağlayabileceğiniz modellere sahip olmak isteyebilirsiniz. Ve bu alanda da bir hayli araştırma bulunuyor. Özetle, bu iki konu, benim araştırma alanımdır. Yani bu konuları ben eğlenceli buluyorum.

Aslında,  büyük kısmı eğlencelidir. Yani, bugün paralel algoritmalar üzerinde konuşacağız. Başlığımız olan paralel algoritmalar ve paralelizm bağlamında pek çok model vardır. Serial algoritmalar yani dizisel algoritmalar için pek çok kimsenin genelde bizim bugüne dek kullanmış olduğumuz bu temel modeli tercih etmelerinin bir sebebi de budur. Bu modele, bazen rastgele erişim makine modeli yani random access machine model de deniliyor. Bu pek çok şeyi analiz için kullanageldiğimiz bir algoritmadır. Paralel alanda ise, o kadar çok sayıda model vardır ki, bu yüzden en iyi modelin hangisi olduğu hakkında genel bir görüş birliği yoktur; çünkü farklı yapılandırmaları olan farklı makineler vardır ve bu nedenle paralel makinelerin nasıl organize edileceği konusunda herkesin varmış olduğu genel bir fikir birliği yoktur.

Bu nedenle, dynamic multithreading yani dinamik çokizleklilik başlığı altında, paylaşılan bellek programcılığına uyumlu olarak üretilen günümüz makinelerine uygun özel bir modeli ele alacağız. Distributed memory programs yani dağıtılmış bellek programları için ise, bu model uygun değildir, çünkü bu tip programlarda, işlemciler her şeye erişim yapabilirler. O uygulamalarda daha detaylı modellere ihtiyacınız olur. Böylece, bunun nasıl yazacağını göstermek için,  bir örnek vererek başlayayım. Bu modelde n’inci Fibonacci sayısını hesaplamanız için size bir program vereceğim. Vereceğim algoritma gerçekten çok kötü bir algoritma çünkü bir üstel zaman algoritması. Ancak, birinci veya ikinci haftadaki derslerde, n’ninci  Fibonacci sayısını ve ne kadar zaman aldığını, onun sayesinde hesaplamıştık.

Log n zamanı. Öyleyse bu, elde etmeniz gerekenden iki üstsel daha fazladır. İki üstel daha fazla ve işte kodu. Aslında, esas itibariyle bir sözdekod yazacağız. Biraz izahat vereyim, burada daha evvel görmediğimiz bazı anahtar kelimeler var: Spawn yani çıkış ver ve  sync yani senkron  . Spawn özü itibariyle, çağırdığınızın altyordamın önünde bir  anahtar sözcük olarak kullanılır ve altyordamın ana yordamla aynı anda çalışmasını sağlar. Burada x eşittir n eksi bir’in spawn’u yani çıkışı dediğimizde, hemen bir sonraki komuta gideriz.

Ve şimdi n eksi bir’in Fib ‘ ini çalıştırırken, aynı zamanda kendi çıktısını verecek bu komutu da çalıştırabiliriz. Devam edersek senkron yani sync komutuna geliriz. Ve senkronun anlamı, “bütün çocuklar yani ardıllar bitene kadar bekle” dir . Söylenmek istenen bu noktaya gelindiğinde her şey tamamlanana kadar beklemeniz ve x  artı y’yi ondan sonra  uygulamanız; aksi takdirde daha x ve y’nin değerlerini bilmeden x artı y’yi hesaplamaya  kalkmış olursunuz. İşte  temel yapılanma budur.  Bunun neyi tanımladığına bakmadan, burada kaç tane işlemci veya başka bir altyapı öğesini belirtmediğimize dikkat edin; bu aslında sadece mantıksal paralelizmi tanımlıyor, uygulamada kullanıldığımız paralelizmi değil. Bu nedenle bir çizelgeleyiciye ihtiyaç duyarız ve bununla kaç tane işlemciniz varsa, bunlara dinamik uygulama eşlemlemesi yaparız. Bugün çoğunlukla çizelgeleme hakkında konuşacağız. Gelecek derste, özgün uygulama algoritmalarını ve bunların çözümlemesini göreceğiz. Böylece, çok izlekli hesaplamayı şöyle gözlemlemelisiniz:

Eğer paralel komut akışına bir göz atarsanız, sadece yönlendirilmiş acyclic yani çevrimsiz bir grafik olduğunu görürsünüz, tamam mı? Şimdi nasıl çalıştığını göstereyim. Normal olarak bir komut akışı olduğu zaman, her talimatın uygulanmış olduğuna bakarım. Eğer bir döngü içinde isem, ona bir döngü olarak bakmam; sadece, çalıştırılmış komutların birbirini takip sırasına bakarım. Bunu, bir zincir olarak görebilirim. Bir komutu uygulamadan önce, bir evvelki talimatı çalıştırmam gerekir. Onu infaz etmeden önce de, ondan evvelkini. En azından bu bir soyutlamadır. İşlemcileri incelediyseniz, komut düzeyli paralelizmin nasıl uygulanacağı konusunda bir sürü hile yapıldığını ve bu yolla dizisel talimat akışının paralel yollarla işletilebildiğini fark etmişsinizdir.

Biz, çoğunlukla mantıki paralelizm üzerinde durup bu bağlamda ne yapabileceğimize bakacağız. Bu DAG’ın yani yönlendirilmiş çevrimsiz grafiğin içindeki tepe noktaları izlekler olup, bunlar paralel kontrol içermeyen maksimal komut dizileridir. Paralel kontrol derken, sadece, spawn’u, senkronu ve spawn işleminin çıkışını kastediyorum. Demek ki, tepe noktaları izlekler oluyor. Öyleyse, burada bulunan tepe noktalarını ve izlekleri sadece işaretleyelim. Böylece, burada fonksiyona girince, esas itibariyle, bu noktaya kadar işlem yapıyoruz; bu izleğe A diyelim. Burası, sequential execution yani ardışık uygulama yaptığımız ve ya geri döndüğümüz yada n eksi bir’in Fib’ine spawn uygulamaya başladığımız nokta oluyor.

Aslında, A izleği, n eksi bir’in hesaplanmasını, altyordam atlamasını yaptığınız noktaya kadar içerecektir. Bu A izleğidir. B izleği, Fib’ den sonra yapacağınız şeyleri, af edersiniz, B, bu spawn’u yapmıştık. Evet, B, y’nin spawn’una kadar olur.Pekiyi, n eksi ikinin Fib’inin spawn’u, y’yi hesaplamak için olduğundan, bundan sonra, boş bir izleğimiz olur; şimdilik bunu bir kenara bırakacağım. Ancak, gerçekte, sync’ den sonra, x artı y  dönüşünü elde ettiğimiz noktaya kadar olan kısmı böylece kapsamış oluruz. Temelde baktığımız şey tümü dizisel olan maksimal komut dizileridir.

Paralel komutu, yani spawn veya senkronu her uyguladığımda, ya da bunlardan dönüş yaptığımda, kullanılan izlek sona eriyor. Böylece, buna, bir izlekler demeti olarak bakabiliriz. Java izleklerine aşina olanlar ve POSIX izleklerini, pekala, P izlekleri denen izlekleri tanıyanlar bunların ağır yük statik izlekleri olduğunu bilirler. Burada bahsettiğimiz, izlek bunların çok daha hafif sıklette bir versiyonudur. Evet, bunlar izleklerdi. Şimdi, bunun nasıl çalıştığının bir haritasını yapmaya çalışayım. Böylece, kenarların nereden ortaya çıktıklarını anlamış oluruz.

Şimdi, dördün Fib’ini uyguladığımızı hayal edelim. Bunun için, boylamasına bir oval çiziyorum. Bu, prosedürsel  uygulamaya tekabül edecek. Ve bu prosedürde, esas itibariyle üç izlek var. A ile başlıyoruz, bu başlangıç izleğimiz olacak.. Sonra A bir spawn’u  çalıştırınca, yeni bir prosedür yaratacak ve o prosedür içinde, yeni bir A özyinelemeli olarak çalışacak. Ancak aynı zamanda, ana prosedürde B’yi de çalıştırmış olacağız; burada bir spawn olduğunda paralel uygulama gerçekleşiyor. Ve böylece burada bir kenar oluşuyor. Bu kenara spawn edge yani çıktı kenarı diyeceğiz; buna da devam kenarı yani continuation edge deniliyor. Çünkü, sadece, uygulama  prosedürünü devam ettiriyor.

Pekiyi, bu noktada, aynı anda çalışan iki şeyimiz var. Bir kere A’yı işlettikten sonra, şimdi aynı anda çalıştırma yapan iki şeyim var. Mesela bu, şimdi şurada başka bir izleği spawn edebilir. Bu üçün Fib’iydi, değil mi? Ve şimdi bu ikinin Fib’i olur. Böylece bu başka bir elemanı spawn eder ve aynı zamanda burada pekala B’yi devam kenarından çalıştırabilir. Ve bu noktada aslında B de spawn yapabilir. Bu da şimdi ikinin Fib’i olur.

Ve şimdi bu noktada, spawn uygulamış olsam bile C’yi  işletemiyoruz. Çünkü, senkron  komutunu vermediğimiz sürece, C’de uygulama olmayacaktır. Ve C, A ile B tamamlanana kadar çalışmayacaktır.Yani bir nevi, orada oturacak ve bekleyecektir. Yani çizelgeleyici  ona işlemeye başlamasını söyleyemez; görevlendirse bile burada hiçbir şey olmayacaktır. Tamam mı? Öyle ise devam edebiliriz. Bir bakalım, buraya bir’in Fib’ ini çağırabiliriz. Birin Fib’i,sadece A komutuyla çalışabilir.                                                                     

Pekala, elbette burada çalışmaz, çünkü eğer kod’a bakarsak, A bir’in Fib’ini işlettiğim zaman, hiçbir zaman B veya C’yi çalıştırmıyor. Ve, aynı şekilde, buradaki eleman da bir’in Fib’ini uygular. Pekala, bu eleman da bir başka bir’in Fib’ini çağırabilir. Ve bu da bir başka Fib(1) yapabilir. O takdirde, bu sıfır’ın Fib’ i olur, değil mi? Şu oku,yanlış yere çizmeye devam ediyorum. Tamam mı?                           

Ve şimdi, bu elemanlar  şuraya dönüyorlar diyelim, şimdi C’yi şimdi çalıştırabilirim. Ancak, bu işlemlerin ikisi de tamamlanmış olmadıkça, bu işlemi başlatamam. Gördüğünüz gibi, C’yi uygulamadan önce, burada bir senkron noktası elde ediyoruz. Ve sonra, benzer şekilde, bunu ve bunu tamamlamış olduğumuz için, şimdi bu işlemi de çalıştırabiliriz. Sonuç olarak, şu dönüşler oraya gidiyor. Gene, benzer şekilde, burada, bu işlem, kendi C‘sini çalıştırabilir. Ve şu ikisi de tamamlandıktan sonra buradaki C’yi de çalıştırabiliriz. Sonunda işimiz de bitmiş olur, çünkü bu son izleğimizdi.

Bu arada etiketleme de yapmış olmam lazımdı. Buradaki çıkışı elde ettiğimde, bu işlemin bir return edge yani bir dönüş kenarı olduğunu belirtmeliydim. Böylece, üç tip kenar var, bunlar:  spawn, dönüş ve devam kenarları’ dır. Ve bunu bu şekilde tanımlamakla, temelde açılım yapan bir DAG elde ediyorum. Böylece, yalnızca bir serial execution trace yani dizisel çalıştırma izi elde etmektense, hala dizisel uygulamaların olduğu ama aynı zamanda da eş zamanlı birkaç işin yapılabildiği bir uygulama elde etmiş oluyorum.   Netice, nasılız? Bir sual mi var?  Her spawn bir senkron ile kapsanıyor mu? Etkin olarak, evet. Aslında burada null thread yani sıfır izleği denen bir izlek var ama ben izaha gerek görmedim. Fakat haklısınız, bu olmazsa yaptığımızda bir paralellik de olmaz. Aslında spawn ile dışarı çıkarıyorsunuz fakat ana prosedürde bir şey yapmıyorsunuz. Uygulama aşağı yukarı dizisel şekilde yapılıyormuş gibi olur.

Böylece, temelde burada gördüğümüz şey, bir anlamda, bir ağacın içine gömülmüş bir DAG yani oluyor. Böylece, prosedür yapısının bir çeşit parçası olan bir ağacınız var, ama, içinde bir de DAG var, ve bu DAG gerçekten çok komplike hale gelebilir. Pekala, şimdi altyapıda bir yönlendirilmiş çevrimsiz grafiğin bulunduğunu anlıyoruz; bunun ışığı altında, konumuzu, özel bir DAG uygulamasının performans özniteliklerini yani performance attrıbute’larını incelemeye çevirmek istiyorum. Yani,  performans ölçütlerine bakacağız.

Böylece, kullanacağımız simgelemde , P sayıda işlemci üzerinde işlemimiz ne olursa olsun, yürütüm süresi olacak. Pekala, , bunu P işlemcide yürütmek için geçecek süredir. Genelde bu, belli bir sayı olmayacaktır. Çünkü farklı çizelgeleme disiplinleri beni,  için farklı sayılar elde etmeye yönlendirebilirler, tamam mı?  Ancak, yürütüm süresinden bahsederken, hala bu simgelemi kullanacağız ve konuyu geliştirirken, bunun bu kontekst içinde ne anlam taşıdığı konusunda bir karışıklık olmamasını temin için dikkatli olacağım.  

Bunların birkaçı oldukça iyi tanımlanmıştır. Birincisi’dir.. Yani, , tek işlemci üzerindeki yürütüm zamanıdır. Eğer bunu tek işlemci üzerinde çalıştırmak isteseydim, spawn ve senkron gibi her şeyden kurtulup uygulama yapacağımı hayal edebilirsiniz.  Bu bana belli bir yürütüm süresi verecektir. Bir işlemci üzerindeki yürütüm süresine, work yani iş deriz. Bu özü itibariyle serial yani dizisel zamanlıdır.  Burada, hesaplama çalışmasından bahsederken, esas itibariyle bir dizisel yürütüm süresini ifade ediyoruz. Öte yandan, ilginç olan diğer ölçüt T sonsuz dediğimiz durumdur. Ve bu, DAG’ın içindeki kritik yol uzunluğu olur; esas itibariyle en uzun yoldur.

Böylece, mesela, Fib(4) örneğimize bakacak olursak,eşittir bir şeyler olacak ama, şimdilik izleklerimiz birim zaman izlekleri olduğunu varsayalım. Birim zaman olmadıklarını biliyorum ama bunu anlamak için her izleğin uygulamada bir birim’e mal olduğunu hayal edelim. Bu özel hesaplamadaki iş ne olur? 17, doğru. Çünkü  bütün yapmamız gereken  bunları toplamaktır: 3, 6, 9, 12, 13, 14, 15, 16, 17. Yani birim zaman izlekler durumunda iş 17 olacaktır.

Genel olarak, orada olan komutları veya her ne varsa toplayacaktınız. Burada T_sonsuz en uzun yol olur. Bu en uzun dizidir. Bu, sonsuz sayıda işlemcileriniz olsa da, bazı şeylerin diğerlerinden önce gelmesi gerektiğinden, hala her şeyi bir anda yapamadığınız, bir durumdur. Gerçekten, sonsuz sayıda, istediğiniz kadar işlemciniz olsaydı, bunu en hızlı ne kadar zamanda yapabilirdiniz?

Biraz şaşırtıcı bir soru. Yedi mi?  Peki, sizin yediniz nedir?  Yani, bir, iki, üç, dört, beş, altı, yedi, sekiz; evet, sekiz en uzun yoldur. İş ve kritik yol uzunluğu, burada göreceğimiz üzere, herhangi bir hesaplamanın iki anahtar özniteliğidir. Soyut olarak, bu husus yalnız birim zaman izlekleri için geçerlidir. Bu durumda ,  için alt sınırlar belirlerken, P’nin  bir ile sonsuz arasında değişen değerlerinde bu iki ölçütü kullanabiliriz. Tamam mı?

Buna göre, çıkarabileceğimiz birinci alt sınır, ’nin en az bölü P olduğudur. Pekiyi, bu niçin bir alt sınır oluyor? Evet? Eğer P işlemcim varsa, pekala, alt sınırım neden bu olsun? Tamam, siz doğru fikre sahipsiniz. Acaba bunun hakkında biraz daha belirgin olabilir miyiz? Evet, doğru, demek ki, siz işlemcilerin hepsini kullanmak istiyorsunuz.

Siz işlemcilerin hepsini kullanabilirseniz, ben niye ’leri bundan da daha az elde edemiyorum? Niçin, en az bölü P büyüklüğünde olması lazımdır? Sadece, yanıtın biraz daha kesin olabilmesi için soruyorum. Siz tamamen doğru fikre sahipsiniz, ancak sınıfın geri kalan kısmını bunun alt sınır olduğu konusunda ikna edeceksek, biraz daha kesin bir yanıt bekliyorum. Evet?  Evet, bu konuya bir başka yoldan bakış şekli. Eğer hesaplamayı dizisel kılsaydınız, her adımda her ne çalıştırırsanız, bu şeylerin P kadarını yapmış olursunuz ve böylece, eğer diziselleştirdiyseniz, bu, P işlemcisi olan bir makinede, P yolunun bir adımını çalıştırmak P adımları kadar sürecektir. David?  Evet, iyi, bunu biraz daha işleyeyim. Demek ki, P sayıda işlemciye güveniyoruz.  P işlemci bir adımda azami P iş yapabilir, doğru mu? Öyle ise, bir kerede azami P iş yapabiliyorlar, yani, P işten fazla iş yapamıyorlar. Öyleyse, eğer bir adımda azami P iş yapabiliyorlarsa, eğer adımların sayısı, bölü P’den az ise, P adımda,’den daha fazla iş yapabilecekler demektir.

Ama yapılacak iş miktarı sadece . Ben de, aldığım kötü cevaplar kadar kötü bir beyan da bulundum. Pekala, P işlemci, bir defadaiş yapabiliyor, öyle mi? Eğer yapılacak iş kadarsa, adımların sayısı da en azbölü P olur, tamam mı? Öyleyse, yolumuza devam edelim; o kadar da zor değildi. Tıpkı, belli miktar,kadar yapılacak işim var. Her adımda azami P kadarını yapabiliyorum.Kaç adım olur? Sadece bölün. Öyleyse, en az o kadar olması gerek. Diğer aşağı sınırda, , T sonsuzdan daha büyük veya ona eşittir.

Biriniz bana neden doğru olabileceğini izah etsin. Evet, evet, eğer sonsuz sayıda işlemciniz varsa, P’niz sonsuz olur ve belli bir zamanda P ile yaptığınız işi kadar zamanda sonsuz işlemci ile de yapabilirsiniz. Pekala, bu model iletişim maliyetleri, karışım gibi bir sürü konuya model teşkil etmiyor.

Ancak, bu pratikte çok iyi çalışan basit bir modeldir; her durumda, P işlemciyle, sonsuz sayıdaki işlemciden daha fazla iş yapamazsınız. Bu bilgiler, örneğin, bir şeyi hızlandırmaya çalıştığımızda, sınırlar nasıl oluşuyor ve daha fazla niye hızlandıramıyorsunuz diye kafanızı duvara vurmak yerine, neyi başarabilmeyi ümit edebileceğinizi bilmek açısından yararlıdır.

Belki de bu, alt sınırlarından birinin çalışmasından ötürüdür. Her şeye rağmen biz, nasıl daha hızlı çalışabileceğimizle ilgileniyoruz Çok sayıda işlemcinin kullanılmasının ana sebebi, tek işlemcide olduğundan daha hızlı gideceğinizi ümit etmenizden ileri geliyor.  bölü ’yi , P sayıda işlemcinin,  hızlandırması olarak tanımlıyoruz. Peki, P işlemci, tek işlemciden, ne kadar daha hızlıdır? Bu hızlandırmasıdır. Eğer,bölü , P düzeyindeyse bu doğrusal bir hızlanmadır. Başka bir deyimle,  niçin?

Çünkü, formül bu: yani, P sayıda işlemciyi işe koşuyorsam, P ile orantılı bir hızlandırma elde edeceğim demektir. Özetle, P sayıda işlemciyi işe koştuğum ve ’yi elde ettiğim zaman, eğer bu P düzeyindeyse, bu bir anlamda, işlemcilerimden her birinin, sabit faktör sınırları içinde tam destekle katkı yapmış olduklarını ifade eder. Bu, P’ye eşit olsaydı, buna kusursuz doğrusal hızlandırma yani perfect linear speedup diyecektik. Ancak biz burada, kendimize teorik amaçlarla, birazcık sabit tampon yani constant buffer veriyoruz. Eğer, bölü , P den daha büyük ise, buna süper doğrusal hızlandırma yani  super linear speedup adını veririz.

Öyleyse, ne zaman süper doğrusal hızlanma elde edebileceğimi söyleyebilecek kimse var mı? Süper doğrusal hızlanmayı ne zaman elde edebilirim? Asla. Pekiyi, neden?  Evet,  eğer bu alt sınırları ele alırsak, buradaki birinci alt sınırlamada, , bölü P’ den büyük veya ona eşittir. Ve eğer sadecebölü yi alırsam, o da P’den daha az veya ona eşittir. Öyleyse, bu modelde bu asla mümkün değildir. Önbellek etkilerine ve buna benzer bazı etkilere dayanarak süper doğrusal hızlandırmanın elde edilebileceği başka modeller vardır.

Ama tetkik etmekte olduğumuz bu basit modelde, süper doğrusal hızlanmayı elde etmek mümkün değildir. Tamam mı? Mümkün değildir. Şimdi, maximum possible speedup yani olası azami hızlandırma, belli miktar iş ve kritik yol uzunluğu verildiğinde ne olur? Birçok işlemciden elde edebileceğim elde edebileceğim maksimum hızlanma nedir?  Demek istediğim, işlemci sayısında bir sınır yoksa, elde edebileceğim azami hızlanma nedir?

bölü T sonsuz, çünkübölü T sonsuz, elde edebileceğim maksimum değerdir . Pekala, eğer probleme sonsuz sayıda işlemci tahsis edersem, bu bana en büyük hızı verecektir. Buna paralelizm diyoruz. Evet, paralelizmin tarifi bu oluyor. Böylece, belirli bir algoritmanın paralelizmi, esas itibariyle, işin kritik yol uzunluğuna bölümü oluyor.

Diğer bir bakış şekli,  kritik yolun her adımı boyunca, paralel olarak yapılabilecek ortalama iş miktarıdır.  Ekseriyetle, bunu P_ bar ile gösteririz. Dolayısıyla şaşırmayın, P_bar’ın, başka bir düzeydeki  P ile hiçbir ilişkisi yoktur. Pekala P,kullanmakta olduğunuz işlemci sayısı olacak. P_bar ise, uygulamakta olduğunuz hesaplama cinsinden tanımlanır, kullanmakta olduğunuz makine üzerinden değil. Özetle, kritik yolun  her adımı boyunca paralel olarak yapılabilecek ortalama iştir. Buraya kadar bir soru var mı?

Böylece,  bu ana kadar, çoğunlukla sadece tanımlar yapıyoruz. Pekiyi, şimdi artık konuya giriyoruz. Böylece, paralelizmin ne olduğunu bilmek faydalıdır çünkü hızlandırmayı paralelizmden daha süratli hale getirmek için çaba sarf etmenin gerçekte hiçbir anlamı yoktur. Öyleyse, size belirli bir hesaplama verilmiş ise, “Oh, bundan daha hızlı olmuyor” diyebileceksiniz. Daha fazla işlemci koyuyorsunuz. Neden daha hızlanmıyor? Cevabı daha fazla paralelizm olmayışı olabilir. Şimdi ne yapmak istediğimi toparlayayım, evet, sanırım bu örneği silebiliriz. Bu model üzerinde daha çok konuşacağız. Şimdi, esas itibariyle, DAG’lar yani yönlendirilmiş çevrimsiz grafikler hakkında konuşacağız. Programlama modelini ise, bir dahaki sefere ele alacağız.            

Öyleyse, çizelgeleme ile başlayalım. Çizelgeleyicinin hedefi, P işlemciye hesaplama eşlemlemesi yapmaktır. Tipik olarak bu, bir yürütüm süresi sistemi yani runtime system tarafından yapılır. Bu, size göstermiş olduğum  language layer yani dil katmanı altında çalışan bir algoritmadır. Böylece programcı, spawn, senkron vsyi kullanarak bir algoritma tasarımı yapar. Ayrıca bunun altında bu yürütüm programını makinenin işlemcilerine yürütüm sırasında  eşlemlemesi gereken bir algoritma daha vardır. İşte çizelgeleyici bundan ibarettir. Gördüğünüz gibi, tipik olarak, dil yürütüm zamanlama sistemi tarafından yapılıyor.

Bu arada, çevrimiçi yani  online çizelgeleyicilerin karmaşık olduklarını söyleyeyim. Yapılması kolay şeyler değiller. Aslında, çok da kötü değillerdir, ama bu konuya girecek değiliz, çünkü elimizdeki iki konu için dahi sadece iki ders zamanımız var. Dolayısıyla, o konunun tamamına girmek yerine, off-line  yani çevrimdışı çizelgelemeyi kullanarak, bazı fikirleri göstereceğim. Bunlardan, çizelgeleyicinin ne yaptığı hakkında bir fikir elde edeceksiniz. Bu tip şeyleri çevrimiçi yapmak, bahsettiğim güçlüğün de ötesinde, bir başka seviyede karmaşa yaratır. Tipik olarak, bugünlerde iyi olan çevrimiçi çizelgeciler, rastgele yani randomized çizelgeleyicilerdir.                                                                                                                                                   

Bunların, performans yeteneklerini doğrulayan kuvvetli kanıtları var.  Ama  bunun da ayrıntılarına girmeyeceğiz. Açıklamamızı çok basit tutacağız. Özellikle,greedy scheduler yani hırslı çizelgeleyici denen özel bir türe bakacağız. Böylece, işlemcinizi yürütmek için bir DAG’ınız varsa, çizelgeleyiciyle ilgili temel prensiplere göre bir boğumu çalıştırabilmeniz için, DAG içinde ondan önceki  tüm boğumların çalıştırılmış olması gerekir. Böylece, herşey tamamlanana kadar beklemeniz gerekir. Buna göre, “Greedy Scheduler” size “ Her adımda mümkün olanın en fazlasını yapalım.” demek ister.

Başka deyişle, “Bir şeyi geciktirmenin yararlı olacağını tahmin etmeyi bile denemem” der. “Eğer şimdi bir şey yapabilirsem, şimdi yaparım.” der. Böylece, her adım, iki tipten birine karşılık olur. İlk tipi, tamamlanmış adım yani complete step olarak adlandıracağız. Bu adım içinde çalışmaya hazır en azından P kadar izleğin olduğu adımdır.  P işlemci üzerinde yürütüm yapıyorum. En az P sayıda çalışmaya hazır izleğim var. Buradaki greedy strateji nedir? P işlemcim var; en az P izleğim var. Herhangi bir P üzerinde yürütüm yapılabilir. Ama  ilk P, eğer komut verme durumunuz varsa  oluşacaktır ve bu da çok makuldür. Öyleyse, bu durumda herhangi bir P’yi yürütebiliriz.

Ancak daha sonra fazla paralelliği mümkün kılacak özel birini şimdi çalıştırırsak, bir hata yapmış olabiliriz; onu çalıştırmamış da olabiliriz.  Bilmiyoruz. Tamam, ancak yapacağımız şey, ister istemez, herhangi bir P’yi harekete geçirmektir. Ama bu adımın atılışında, bir belirsizlik vardır, çünkü işletmeye başladığınızda bu iyi bir seçim olabilir de, olmayabilir de. İkinci tip ise, incomplete step yani tamamlanmamış adımdır. Yani, bunda yürütüme hazır P’ den daha az izlek vardır. Öyleyse buradaki stratejimiz ne olabilir?   

İzleklerin hepsini çalıştırmak olur. Eğer hırslı ise, çalıştırmamak diye bir tutum zaten söz konusu değildir. Özetlersek, işletilmeye hazır P’den çok izlek varsa, herhangi P’yi;  işletilmeye hazır P’den az izlek varsa, izleklerin hepsini çalıştırıyoruz. Bu iyi bir strateji gibi görünüyor ama mükemmel değildir. Gerçekte, P işlemci üzerinde bir  DAG’ı en iyi şekilde çizelgelemeye çalışmak “NP complete” olur;  bu da çok güç demektir. Böylece, 6.045 veya 6.840’i alacaklar için  bu kurları tavsiye ediyorum; son dersimizde mühendislik yoğun teoride bir parça işleyeceğimiz gibi,  son dersimizde bu konuyu daha fazla konuşacağız.

“NP complete” konusu kapsamında, bazı problemler için bildiğimiz iyi algoritmaların olmadığını ve bunun gerçekten ne demek olduğunu öğrenebilirsiniz. Böylece, bu çeşit çizelgeleme probleminin, en iyi neticenin elde edilmesine olanak vermeyen çok güç bir problem olduğu ortaya çıkıyor. Ancak  Graham ve Brent’ ten bu konuda güzel teorem vardır. Esas itibariyle,  bir greedy scheduler yani hırslı çizelgeleyicinin, her hesaplamayı çalıştırdığını ifade ediyor:

G hesaplamasında, işi, ve T_sonsuz kritik yol uzunluğunda,P işlemli bir bilgisayar üzerinde süre , bölü P artı T_sonsuz ‘dan az veya ona eşittir. Böylece,”bölü P artı T_sonsuzda başarabilirim”, diyor. Bu ne diyor? Eğer buna bakar ve bizim yürütüm süresi  alt sınırları ile kıyaslarsak, bu ne kadar verimlidir?   Bu, en iyi işletim ile nasıl  kıyaslanır? Evet, iki competitive yani alternatiflidir. En iyinin iki faktörü içinde kalır, çünkü bu bir alt sınır ve bu da bir alt sınırdır.

Öyleyse, bu ikisinin iki defa maksimumunu alırsam; bu ikisinin iki kere en çok değerleri toplamdan büyük olacaktır. Öyle ise, hangisi daha büyük olursa olsun, iki faktörü içinde kalıyorum; herhangi bir durumda hangi alt sınır daha büyük olursa olsun. Böylece, bu, P işletici üzerinde, yürütüm süresi bazında çizelgeleme verimliliğinde, ikinin bir faktör olarak  devreye girdiğini söylüyor. Herkes bunu görüyor mu? Öyleyse, bu teoremi kanıtlayalım. Çok güzel ve rafine bir teoremdir.Güç bir teorem değildir. Bu haftanın güzel taraflarından biri, hiçbir şeyin çok zor olmaması. Sadece, farklı düşünmenizi gerektiriyor. Öyleyse, ispatın,  toplama ile ilgili olması lazım, yani, kaç tane tamamlanmış adımımız, kaç tane de tamamlanmamış adımımız var. 

Öyleyse tamamlanmış adımların sayısı ile başlayacağız. Adımların azami sayısının ne olduğunu söyleyebilecek biri var mı? Evet, arkada birinin mırıldadığını işittim. bölü P. Niçin bu? Evet, tam adımların azami sayısı