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 vs.’yi 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ıbölü P’dir, ama neden? Bu kadar çok işleminiz olunca iş yapıyorsunuz, tamam mı? Her tam adımda P iş yapılıyor, öyleyse bölü P adımdan fazlasını yaparsam, yapılması gereken başka iş kalmaz. Böylece, tamamlanmış adımların sayısı dabölü P den fazla olamaz. Bu şu parça oluyor.

Şimdi, tamamlanmamış adımları toplayacağız ve T_sonsuz ile sınırlandığını göstereceğiz. Tamamlanmamış bir adım düşünelim. Bakalım ne oluyor. G üssü (prime), çalıştırılacak olan G’nin alt grafiği olsun. Pekala, burada bir tablo çizeceğiz. Diğer tahtanın üstüne çizelim. Burada bir grafik çiziyoruz. Grafiğimiz G olacak. Örnekte P eşittir üç olsun. Bunun G grafiği olduğunu tahayyül edin. Burada prosedürleri göstermiyorum çünkü bu gerçekte her DAG için işleyen bir teoremdir.

Prosedürün ana hatları gerekmiyor. İlgilendiğimiz tek şey izleklerdir. Bunun benim DAG’ım, G olduğunu, ve bu noktaya kadar işlemler yapmış olduğumu farz edin. Hangilerini işletmiştim? Evet, bunları çalıştırmıştım. Yani G üssü’nde olanlar henüz çalıştırılmamış ve işleme alınacak olanlardır. Ve bunlar da işlemlerini tamamlamış olanlardır. Ve hepsinin genellikleri kaybolmamış, birim zamanlı izlekler olduklarını hayal edeceğiz. Bunlardan her birine özel bir süre atanmış olsa da, teorem bunların arasından yoluna devam edecektir. Aynı çizelgeleme algoritmasındaki gibi iyi bir şekilde işleyeceklerdir. Pekiyi, çalıştırılmaya hazır izlekleri nasıl karakterize edebilirim?

Burada işletilmeye hazır izlekler hangileridir? Bir bakalım. O mu? Hayır, o işletilmeye hazır değil. Niçin? Çünkü burada bir halefi var. Buradaki mi? Bu çalışmaya hazır. Pekala, buradaki de çalıştırılmaya hazır.Yani, şu iki izlek işletilmeye hazır, bunu nasıl karakterize edebilirim? Bunların özelliği nedir? Sahip oldukları ne? G üssü’nde bunların çalıştırılmaya hazır olup olmadığını söyleyecek bir grafik teorik özellik var mı? Halefi yok ama bunu ifade etmenin başka şekli nedir? G üssü’nde hiç kendinden önce gelen halefi yok.

Bir boğum için bir grafikte kendinden önce gelen yok ne demek? Derece olarak, bu sıfır demek değil mi? Aynı şey. Pekala, G üssü içinde sıfır dereceli izlekler, işletilmeye hazır olanlardır. Pekiyi ama, eğer tamamlanmamış bir adım ise, ne yaparım? Çalıştıracağım, ama eğer tamamlanmamış bir adım ise o zaman hepsini çalıştıracağım. Bunların hepsini çalıştırırım. Şimdi sıfır derecedeki izleklerin hepsini çalıştırdığımda, geri kalan grafiğin kritik yol uzunluğu ne olacaktır?

Bir eksilir. Bu durumda, G üssü’nün geri kalan işletilmeye hazır kritik yol uzunluğu bir eksilir. Böylece, her tamamlanmamış adımda çalıştırılmaya başlanması için kalan, evet çalıştırılması için geri kalan, daima bir eksiliyor. Burada, bir sonraki adım böylece bir tamamlanmış adım oluyor, çünkü elimde işe başlamaya hazır dört şey var. Ve onları o şekilde işletmeye başlatabilirim ki kritik yol uzunluğu o adımda azalmaz. Ama eğer hepsini doğrudan çalıştırırsam, bu tarz bir yaklaşım kritik yol uzunluğunu azaltır.

Şimdi tabiatıyla, her ikisi de aynı zamanda gerçekleşebilir. Ama artık her tamamlanmamış adım durumumda, kritik yol uzunluğunu bir eksiltmeyi garanti etmiş oluyorum. Bu da, tamamlanmamış adımlar sayısının en çok T_sonsuz olduğunu ima eder. Ve bu sebepten, , en çok tamamlanmış adımların sayısı artı tamamlanmamış adımların sayısıdır. Ve sınırımızı elde ederiz. Bu bir çeşit amortize edilmiş bir argümanın sonucudur; eğer bu yönde düşünmek isterseniz, her adımdaki işlemi ya işe göre, ya kritik yol uzunluğuna göre, ya da her iki şıkkın bir arada olacakları bir duruma göre parçalara ayırıyorum.

Ama hiç değilse, her adım için bunlardan birini yapıyorum ve böylece sonunda sadece bu iki katkıyı toplamam yetiyor. Bu hususla ilgili herhangi bir soru var mı? Bu arada bunun bütün çizelgeleme işleminin temel teoremi olduğunu ilave edeyim. Eğer, çizelgelemeyle ilgili çalışırsanız, bu temel sonuç pek çok şeyin bir çeşit temelidir. Ve sonra herkes bunu on-line yapalım, çizelgeleyici ile yapalım ve saire gibi süsleyip püsler; bu sınırları birbiriyle uyuşturmaya çalışır. Çokbilmiş hırslı çizelgeleyicileri ve benzer her şeyi kullanır.

Yani bu, hemen hemen çizelgelemenin tüm alanını işgal eden türden bir temel teoremdir. Pekala, hızla bir corollary yani doğal sonuç çalışması yapalım. Şunları silmeyeceğim çünkü çok önemliler. Bunları sileceğim. Bunları da silmeyelim. Onu da silmek istemiyorum. Üstekine geri geleceğiz. Aslında doğal sonucu buraya yazacağım çünkü sadece bir satır. Doğal sonuç size tahsis ettiğiniz işlemcilerin sayısı, eğer işinizi sürdürdüğünüz düzende, paralelizm düzeyindeyse, doğrusal bir hızlanma elde edeceğinizi söylüyor. Yani, hırslı çizelgeleme, eğer yürütümü esas itibariyle paralelizm düzeyinde veya daha az sayıda işlemci ile sürdürülüyorsa, size doğrusal hızlanma veriyor.

Bunun niye böyle olduğunu görelim. Bunu birbirine uyduracağımı ümit ediyorum. Tamam mı? Böylece, P_bar,bölü T sonsuz’ dur. Bu da, P eşittir O (/ T_ sonsuz) ise, o zaman bunları buraya getirerek, T_sonsuz, O(/ P)’dir. Herkes benimle mi? Bu sadece cebirdir. Bu paralelizmin tanımıdır:bölü T_sonsuz. Ve buradan da, eğer P paralelizm düzeyindeyse, O(/ T_sonsuz) olur.

Şimdi bunu toparlarsak, T_sonsuz, O(/ P) olur. Öyleyse bu: T_sonsuz, O( /P)’dir. Bu sebeple, kanıta burada devam ediyoruz. Böylece,, en çokbölü P artı T_sonsuz olur. Eğer, bu O(/ P) ise, herşey O(bölü P)’dir. Tamam, öyleyse şimdi elimde, var ve bölü P düzeyinde; hesap yapmak için/ ‘ye ihtiyacımız var ve o da düzeyinde olacaktır. Tamam mı?

Herkes görüyor mu? Özetlersek, bunun söylemek istediği, “benim belli bir miktar paralelizmim var, bu paralelizmden daha az işlemci kullanmaya yönelirsem, hırslı çizelgeleme kullandığımda doğrusal hızlanma elde ederim. Paralelizmden daha fazla sayıda işlemci kullanmaya yönelirsem, boşuna israf yapmış olurum, çünkü bu ekstra işlemcileri kullanmayı haklı kılacak bir hızlanmayı elde edemem. Böylece, bir işin gerektirdiği paralelizmi anlamakla sahip olmak istediğim işlemcilerin sayısının limitini de öğrenmiş ve bilmiş oluyorum.Gerçekte, bunu elde edebilirim. Soru ?

Bu, aslında bir bakıma, bunun omega P olması lazım, demenin bir şeklidir. Öyleyse, uygundur. Tekrar sorar mısınız? Hayır, hayır, sadece yukarıda bir sabit ile sınırlanmış ise. ve T_sonsuz sabit değillerdir. Bu örnekte değişken olarak yer alırlar. Böylece, çok değişkenli, asimptotik analiz yapıyoruz. Dolayısıyla, bunların herhangi biri, başka bir şeyin fonksiyonu olabilir ve istediğimiz kadar büyüyebilir. Dolayısıyla, bize belli bir şey için verilmiş bulunuyorlar deyişimizdeki gerçek, o sayının bize gerçekten verilmemiş olduğudur. Aslında verilen şey, değişik DAG türleri ve boyutlarıdır.

Böylece, büyüme konusuna geçebilirim. Burada, paralelizmin, özür dilerim yürütüm süresinin büyümesinden bahsedildiği zaman ,ve T sonsuzun bir fonksiyonu olur. Yani burada büyüyen şeyler hakkında konuşuyorum, tamam mı? Pekala, öyleyse bunu çalıştırmaya başlayalım. Aslında, şimdi geriye, buraya gideceğim. Şimdi size birazcık kendi araştırmalarımdan ve yaptığımız bazı çalışmalarda bunu nasıl kullandığımızdan söz edeceğim. C lisanına dayandığı için, kısaltılmış şekliyle Cilk diye adlandırdığımız, bir dinamik- çok izlekli-dil geliştirdik.

Telaffuzu bir kısaltma oluşturmuyor, çünkü ‘silk’ güzel ipliklere benzer. Her ne kadar bir noktada öğrencilerim kısa ad “Cilk”in ne anlama geldiği konusunda bir yarışma yapmış olsalar da sonunda kazanan, Charles’ın “Idiotic Linguistic Kluge” tekerlemesi oldu. Her neyse, eğer bakmak isterseniz, onun hakkında burada bazı şeyler bulabilirsiniz. Bu aslında karmaşık çizelgeleyicilerden biridir ve Randomized online scheduler yani bir rastgeleleştirilmiş çevrimiçi çizelgeleyici kullanır. Ve P işlemci üzerindeki umulan yürütüm süresine bakarsanız, bölü P artı O( T_sonsuz)’a kanıtlanabilir şekilde eşit olur.

Ve gözlemsel açıdan, büyük O içinde neyin saklı olduğunu ortaya çıkarmak için ne tür yürütüm süreleri elde ettiğinize bir bakarsanız, gerçekten,bölü P artı T_sonsuz çıkar ve buradaki sabitler deneysel olarak bire çok yakındır. Garantisi yok fakat bu çok iyi bir sınır olarak beliriyor. Bazen, T_sonsuz üzerinde, dörde yakın bir katsayı görürsünüz. Ancak, genellikle, bundan daha büyük bir şey görmezsiniz. Ve çoğunlukla, eğer linear regression yani doğrusal bağlanım eğrisini uydurabilirseniz, burada bir’e yakın, bir civarında bir sabit elde edersiniz. Ve böylece yürütüm süreniz için bu formülü bir model olarak kullanırsanız, kusursuza yakın hızlanma elde ediyorsunuz. Kusursuza yakın doğrusal hızlanmayı, kullandığınız işlemcilerin sayısı, ortalama paralelizminizden çok az ise elde ediyorsunuz ki bu da, T_ sonsuz’ un ,bölü P den çok az olması gibi bir şey demek oluyor.

Böylece burada, P’nin P sonsuz’ dan çok daha küçük olduğu zaman, yani, T_sonsuz, bölü P den çok az olduğu durumda, bu terimin bir önemi kalmıyor ve böylece çok iyi bir hızlanma elde ediyorsunuz. Böylece, işlemci sayısının paralelizmden çok daha az olduğu bir çerçeve içinde kaldığınız sürece, her işlemciniz size diğer işlemcinizin işini veriyor. Bu dil ile, yıllar önce, şimdi insana hakikaten pek çok yıl geçmiş gibi geliyor, yarışmalara katıldık. Çok sayıda satranç programları tasarladık.

Bu programların arasında, Starsocrates, Cılkchess ve başkaları vardı. Bunlar, dünya çapında programlardı.1995’te, Hong Kong’da yapılan Dünya Bilgisayar Satranç Şampiyonasında birinciliğe kadar geldik, sonra play-off oynadık ve kaybettik. Gerçekten utanç verici idi. Büyük paralel bir makinede oynuyorduk ve kazanmak üzereydik. Belki bazılarınız tesadüfen bilebilirsiniz, Deep Blue Chess Playing Programı idi. Rakibimizin Dünya Şampiyonu Kasparov ile yaptığı karşılaşmalarından bir yıl önceydi. Programlara karşı yarışıyorlardı. O turnuvada üçüncü oldular. Onları biz saf dışı ettik. Bununla beraber, kafa-kafaya yarışmada, onlar bizi yendi. Böylece, finallere kadar, sadece bir maç kaybettik. Onların bir kaybı, bir de beraberlikleri vardı. Pek çok kişi, Kasparov ile karşılaştıkları zaman Deep Blue’ nun dünyanın en üstün bilgisayarı olmadığını bilmiyordu. Kasparov’a karşı müsabakaya çıkmalarının nedeni, IBM ortaya bahis için para koymaya arzulu olması idi. Evet, konumuza dönersek, bu satranç programlarını geliştirdik. Ve geliştirme şeklimizle ilgili olarak, özellikle Starsocrates’ten biraz bahsedeyim. Bu ilginç anormallik başımıza geldi. MIT’de 32 işlemcili bir bilgisayarı geliştirme çalışması yapıyorduk.

Turnuva için Illinois Üniversitesinde NCSA da 512 işlemcili bir bilgisayara erişimimiz vardı. Bu büyük makinemiz vardı. Bize vermeyi pek fazla istemediler; MIT’de yani bizde de aynı makinenin küçük modeli vardı. Böylece bunun üzerinde geliştirmeyi yapacaktık, ara sıra da bununla çalışabilecektik. Bu kendi işlemcimiz için geliştirmeye çalıştığımız bilgisayardı. Şimdi size, ortaya çıkan anormalliği göstereyim.

Orijinal program diye adlandıracağım bir programın, bizde bir sürümü vardı. Ve programın daha hızlı işlemesi için, tamamen yeni özelliklerle optimizasyon yapan bir programımız vardı. Bu programı 32 işlemcili makinemize zamanladık. Yürütüm sadece 65 saniye aldı. Evet, sonra bu yeni programı zamanladık. Buna, 32 işlemci makinemiz üzerinde T üssü diyeceğim; çalışınca denektaşı yürütümü sadece 40 saniye sürdü. Şimdi itiraf edeyim, hesaplamayı kolaylaştırmak amacıyla gerçek rakamlar konusunda yalan söyledim. Fakat, fikir olarak aynı şeyler oldu. Sadece rakamlar daha karmaşık.

Böylece, sonuç yürütüm süresinde kayda değer bir gelişmeye benziyor ancak, biz optimizasyonu reddettik. Reddetmemizin sebebi, iş ve kritik yol konularını daha önceden kavramış olmamızdı. Şimdi size, o tarihte yapmış olduğumuz analizi göstereyim. Analiz, kullandığımız enstrümanlara baktığımızda, bu durumdaki işin 2.048 olduğunu ortaya koyuyordu. Ve kritik yol bir saniye idi. Burada ise, optimize edilmiş programla iş 1,024 oluyordu. Ama kritik yol sekiz oluyordu.

Böylece, şuradaki basit modelimizle ilişkilendirirsek, yukarıdaki ile bazı değerleri yuvarladığım şeklini; elimde, T_32 eşittirbölü 32 artı T_sonsuz var. Bu da eşittir, bakalım, iş 2,048 bölü 32. Ne yapıyor 64, iyi; artı kritik yol da 65 olur. Öyleyse, daha evvel gördüğümüzle uyuşuyor. Gerçekten, biz de böyle yaptık ve uyuştu. Çok yakındı. Pekala, burada Tüssü_32 eşittir; bir bölü 32, artı T üssü_sonsuz. Ve bu da 1.024 bölü 32, 32 artı sekiz, buradaki kritik yol’ dur.

Bu 40 eder. Böylece, bu da uyumlu çıktı. Bunun üzerine, şimdi bunun, büyük makinede dış değerlemesini yapalım, dedik. Büyük makinemizde bunlar ne kadar hızlı çalışacaklar? Biz bunu T_512 olarak istiyoruz. Bu eşittir,bölü 512, artı T_sonsuz olur. Öyle ise, 2,048 bölü 512 kaç oluyor? Dört, artı T_sonsuz, bu da eşit beş oluyor. Öyleyse, bunun üzerinde daha hızlı çalışıyor. Fakat, burada, T_512 eşittir,üssü bölü 512 artı T_sonsuz üssü, eşittir, 1,024 bölü 512, iki eder; artı kritik yol 8, toplamda on ediyor.

Böylece, gördüğünüz üzere, eğer o ‘”optimizasyon “ u kabul etmiş olsaydık, büyük makinede iki misli daha yavaş çalışacaktık. Çünkü paralelizm’den ayrıldığımızda yolumuz da daha uzadı. Bunu düzeltecek bir yola ihtiyaç vardı ve işi azaltabilirdik. Evet işi azaltmak iyidir, ancak yürütüm süresi kapsamında kullanabilmeyi ümit ettiğimiz kritik yol’un paralellik özelliğinden kurtularak değil.

Bu iki misli yavaş’ dır. Evet, iki kat yavaştır. Buradaki ana fikir, bir işlemcideki iş ile kritik yol uzunluğunun performansı, yürütüm süresinden daha iyi tahmin edebildiğidir. Scalability yani ölçeklenebilirliğe gelince, bu makinelerin çoğunda önemli bir meseledir; her zaman olmasa da bazen ölçeklenebilirlikten endişe duymazsınız. Bazen de duyarsınız. Eğer, 32 işlemcili makineyi kullanıyor olsaydık bu optimizasyonu kabul ederdik. Ticari bakımdan başarılı bir sonuç olurdu. Çok daha fazla sayıda işlemci ile çalıştığımızı ve paralelizmden gittikçe çıkmaya başladığımızı bildiğimizden, o noktada, kritik yolu arttırma, bir anlam ifade etmiyordu. Çünkü sadece hesaplamamızın paralelizmini azaltıyordu.

Pekala, önce bu konuda bir sual var mı? Hayır. Pekala. Gelecek sefer, artık modelin nasıl çalıştığını anladığımız için, dinamik çok izlekli şekilde kodladığımız özel algoritmaların performanslarına bakmaya başlayacağız. Tamam!