Makine Öğrenimi ve Sinir Ağları - sayfa 30

[MetaQuotes]

Anlatım 11. Depolama Tahsisi

Anlatım 11. Depolama Tahsisi

Öğretim görevlisi, bu videoda hem bellek ayırmayı hem de boşaltmayı kapsayan depolama ayırmayı tartışıyor. Yığın ve yığının yanı sıra sabit ve değişken boyutlu tahsis şemaları dahil olmak üzere farklı depolama türleri ele alınmaktadır. Dağıtılan bellek bloklarının neden olduğu harici parçalanma, disk sayfası başına boş listeler veya bit eşlemler gibi çözümlerle de tartışılır. Referans sayımı ve bu algoritmanın sınırlamaları da dahil olmak üzere çöp toplama kavramı da tanıtılmaktadır. "İşaretle ve süpür" ve "durdur ve kopyala" çöp toplama prosedürleri de açıklanmakta ve ikincisinin parçalanmayı nasıl ele aldığına ve işaretçi güncellemelerinin neden olduğu olası doğruluk sorununa odaklanılmaktadır. Video, durdurma ve kopyalama algoritmasının zaman ve mekan karmaşıklığı ve harici parçalanmayı ortadan kaldırması üzerine notlarla sona eriyor.

Bu video, Buddy sistemi, işaretleme ve süpürme prosedürleri, optimizasyonlar, nesiller arası ve gerçek zamanlı çöp toplama, çok iş parçacıklı depolama tahsisi ve paralel çöp toplama dahil olmak üzere dinamik depolama tahsisi ile ilgili çeşitli konuları kapsar. Öğretim görevlisi, kuşak çöp toplamanın, daha genç nesnelerin daha sık taranması fikrine dayandığını, gerçek zamanlı çöp toplamanın ise program yürütülürken arka planda çalıştığını, ancak nesne ve işaretçi grafiği sürekli değişirse doğruluk sorunlarına yol açabileceğini açıklıyor. Son olarak ders, yığın ve öbek dahil olmak üzere farklı depolama tahsisi türlerini ve referans sayma, işaretle ve süpür ve durdur ve kopyala gibi farklı çöp toplama yöntemlerini özetler. Öğretim görevlisi, öğrencilerin yaklaşan ev ödevlerinde bu yöntemlerden bazılarını deneyeceklerinden bahseder.

• 00:00:00 Bu bölümde öğretim görevlisi, hem bellek ayırmayı hem de boşaltmayı içeren depolama ayırmayı tartışır. En basit depolama şekli, belleğin yığın işaretçisinin artırılmasıyla ayrıldığı ve yığın işaretçisinin azaltılmasıyla serbest bırakıldığı bir yığındır. Ancak yığının uygulanabilirliği sınırlıdır çünkü yalnızca tahsis edilen son şeyi serbest bırakabilir ve kullanılan bölgenin ortasında hiçbir şeyi serbest bırakamaz. Öğretim görevlisi ayrıca verimlilik nedeniyle yığın taşmasının genellikle derleyiciler tarafından kontrol edilmediğini de not eder.
  
  
• 00:05:00 Bu bölümde öğretim görevlisi iki tür depolamadan bahsediyor: yığın ve yığın. Yığın, verimli ancak her şey için kullanılamayan sabit boyutlu bir depolamadır, yığın ise daha geneldir ancak düzenlenmesi ve verimli bir şekilde kullanılması zordur. Yığın tahsisi için malloc ve ücretsiz C işlevleri kullanılabilir, ancak C ve C++ bir çöp toplayıcı sağlamadığından, programcıların belleği kendilerinin yönetmesi gerekir, bu da bellek sızıntılarına, sarkan işaretçilere ve çift serbestliğe neden olabilir. Öğretim görevlisi, programdaki bellek hatalarının sayısını azaltmak için adres temizleyici ve Valgrind gibi bellek denetleyicilerinin kullanılmasını önerir.
  
  
• 00:10:00 Bu bölümde, konuşmacı, her bir depolama parçasının aynı boyuta sahip olduğu ve bazı blokların kullanıldığı, bazılarının kullanılmadığı sabit boyut tahsisinden başlayarak, depolamayı tahsis etmenin farklı yollarını tartışıyor. Kullanılmayan bloklar, serbest liste adı verilen bir listede tutulur ve serbest listedeki her bloğun, listedeki bir sonraki bloğa işaretçisi vardır. Serbest listeden bir nesne tahsis etmek için, program işaretçiyi serbest olarak ayarlar ve sonra serbest işaretçiyi serbest listedeki bir sonraki şeyi işaret edecek şekilde ayarlar ve işaretçiyi serbest listedeki ilk nesneye döndürür. Serbest bırakmak için, nesnenin bir sonraki işaretçisini serbest olarak ayarlar ve serbest ayarını serbest bırakılacak nesneye eşitler. Serbest listeyle, ayırma ve serbest bırakma sürekli zaman alır ve kişi aynı zamanda iyi bir zamansal konum elde eder.
  
  
• 00:15:00 Bu bölümde, kullanılan bellek blokları tüm bellek alanına yayıldığında ortaya çıkan harici parçalanma kavramı tanıtılmaktadır. Bu, daha büyük bir sayfa tablosuna yol açabilir, bu da disk çökmesine neden olabilir ve çevirilere bakmayı daha az verimli hale getirebilir. Harici parçalanmayı azaltmak için, disk sayfası başına ücretsiz bir liste veya bitmap kullanılabilir ve en dolu sayfadan ayırma, öykü bloklarını serbest bırakma ve boş sayfaları sayfalama yapılabilir. Sabit boyutlu yığın tahsisi, harici parçalanmayı azaltmak için de yararlı olabilir. Son olarak, değişken boyutlu yığın tahsisi, farklı boyutlarda ayrılmış bellek için boş listelerin verimliliğinden yararlanan bin içermeyen listelerle kullanılabilir.
  
  
• 00:20:00 Bu bölümde, bir bellek ayırma sisteminde farklı boyutlarda bellek bloklarını depolamak için bir şema sunulmaktadır. Şema, blokların boyutlarına göre kutulara bölünmesini içerir; her kutu, ikinin kuvvetleri olan belirli bir boyuttaki blokları tutar. Bellek tahsis edilirken, istenen boyuta göre uygun bölme seçilir ve boşsa, boş olmayan daha büyük bir bölme, istenen boyutu elde etmek için daha küçük parçalara bölünür. Bununla birlikte, bu şema, israfa yol açan dahili bellek parçalanmasına neden olabilir, bu nedenle kullanılan kutu sayısı sınırlıdır ve yükü azaltmak için küçük bloklar sayfalar halinde gruplandırılır. Gerektiğinde daha fazla bellek sağlamak için işletim sistemi kullanılabilir ve bu amaçla kullanılabilen sistem çağrıları vardır.
  
  
• 00:25:00 Bu bölümde video, bellek tahsisinin nasıl çalıştığını tartışıyor ve 'malloc'un standart uygulamalarının işletim sisteminden bellek almak için 'break' gibi komutlara dayandığına dikkat çekiyor. İşletim sistemi büyük miktarda bellek verir ve bunu daha küçük bloklara bölmek depolama ayırma sistemine bağlıdır. Bu bölüm ayrıca, blok boyutlarını depolamak için farklı şemalar ve sanal bellek adres alanının bir programda nasıl düzenlendiği dahil olmak üzere bellek ayırıcının varyantlarını da kapsar. Yığın ve yığının birbirine doğru büyüdüğünü ancak asla kesişmediğini belirtir. Son olarak, bir programdaki büyük sabit tablolarının önceden hesaplanmasının, veri bölümünden okumayı gerektirdiği için yükleme süresini artırabileceğinden bahsedilir.
  
  
• 00:30:00 Bu bölümde, harici parçalanmaya, sayfa tablosunun performansının düşmesine, disk çökmesine ve belleğin dağılması durumunda düşük TLB isabet oranlarına yol açabilen sanal bellekle parçalanma konusu ele alınmaktadır. Depolama tahsisinin amacı, kullanılan bellek bölümlerini kompakt tutarken mümkün olduğunca az sanal bellek kullanmaktır. Bin serbest liste ayırma şeması, yığın depolama tarafından tüketilen sanal bellek miktarının M log M tarafından üst sınırlandığını belirten bir teorem ile analiz edilir. Charles Leiserson tarafından yazılan bir makaleye göre, bu yöntem, en uygun ayırıcıdan yalnızca bir sabit faktör daha kötü olan standart bin serbest liste algoritmasına kıyasla yüksek olabilir.
  
  
• 00:35:00 Bu bölümde, konuşmacı depolama tahsisi kavramını ve bunun yığın depolama ile uğraşırken parçalanmayı nasıl azaltabileceğini açıklıyor. Ayrıca, programcıyı nesneleri manuel olarak serbest bırakmak zorunda bırakmayan çöp toplama fikrini de tartışıyor. Konuşmacı, üç tür bellek nesnesini (kökler, canlı nesneler ve ölü nesneler) ve çöp toplamanın ikincisini nasıl geri dönüştürebileceğini açıklar. Son olarak, serbest bırakılıp bırakılmayacağını belirlemek için bir nesneye başvuran işaretçilerin sayısını sayan basit bir çöp toplama biçimi olan referans saymayı açıklar.
  
  
• 00:40:00 Bu bölümde, konuşmacı bir çöp toplama şeması olarak referans sayma kavramını tanıtıyor ve referans sayma algoritmasının nasıl çalıştığını açıklıyor. Bununla birlikte, referans grafiğindeki döngülerin toplanamadığı durumlarda, algoritmanın bir sınırlamasına dikkat çekilmektedir. Konuşmacı daha sonra bu sınırlamayı önlemek için bazı programlama dillerinde güçlü ve zayıf işaretçilerin kullanımını tartışır. Son olarak, konuşmacı, referans grafiğindeki döngülerle uğraşırken referans sayımının sınırlandırılmasını önleyen diğer iki çöp toplama şemasını, "işaretle ve süpür" ve "durdur ve kopyala" önizlemesini yapar.
  
  
• 00:45:00 Bu bölümde konuşmacı, bellekteki tüm canlı nesneleri bulmak için genişlik öncelikli arama algoritmasının kullanımını tartışıyor. Arama için bir FIFO kuyruğunu temsil etmek üzere iki işaretçili bir dizi kullanılır ve algoritma, köklerden erişilebilen her canlı nesneyi işaretler. Arama tamamlandıktan sonra, işaretlenmemiş nesneler çöp toplama için kullanılabilir. İşaretle ve süpür prosedürü iki aşamadan oluşur: genişlik öncelikli arama algoritmasını içeren işaretli aşama ve işaretlenmemiş nesneleri serbest bırakmak için belleğin taranmasını içeren tarama aşaması. Bununla birlikte, bu şemanın, tüm belleği tarama ihtiyacı ve başvurulmayan nesnelere bakmayla ilişkili ek yük gibi sınırlamaları vardır.
  
  
• 00:50:00 Bu bölümde video, parçalanmayla ilgilenen "durdur ve kopyala" çöp toplama prosedürünü tanıtıyor. Bu prosedür işaretle ve süpür algoritmasına benzer, ancak canlı nesnelerin bellekte bitişik olmasını sağlamak için farklı bir yaklaşım benimser. Prosedür, iki ayrı bellek alanı kullanır - uzaydan ve uzaya - ve nesneleri, boşluk dolana kadar tahsis eder ve boşluktan serbest bırakır. Ardından, çöp toplama algoritması çalıştırılır ve iki boşluk, iki boşlukta belleğe bitişik olarak yerleştirilecek olan canlı nesneleri tanımlamak için genişlik öncelikli arama için kuyruk olarak kullanılır. Ancak, bu algoritmanın kullanılması, uzaydan nesnelere işaret eden işaretçilerin artık doğru olmayabileceği olası bir doğruluk sorununa yol açabilir. Bunu ele almak için prosedür, uzaydan ilgili nesnede bir iletme işaretçisini depolar ve genişlik öncelikli aramada bir nesneyi sıradan kaldırırken bu yönlendirme işaretçilerini izleyerek tüm işaretçileri günceller.
  
  
• 00:55:00 Bu bölümde konuşmacı, çöp toplamayı durdur ve kopyala algoritmasını, zaman karmaşıklığını ve harici parçalanma ile nasıl başa çıktığını tartışıyor. Durdur ve kopyala algoritması, nesnelerin uzaydan uzaya kopyalanmasını ve ardından bu nesnelerin işaretçilerinin uzayda güncellenmesini içerir. Bu algoritma zaman ve uzayda doğrusaldır, bu da onu çöp toplamanın daha verimli ve etkili bir yolu yapar. From alanı dolduğunda, kullanıcı yeni bir yığın alanı talep edebilir ve from alanının boyutunu iki katına çıkarabilir. Bu şemanın gerektirdiği sanal bellek alanı, sabit çarpı optimaldir ve bu algoritma, harici parçalanmayı ortadan kaldırır.
  
  
• 01:00:00 Bu bölümde konuşmacı, birleştirme yapmak için Buddy sistemi, işaretleme ve süpürme prosedürünün varyantları, performansı iyileştirmek için optimizasyonlar, kuşak çöp toplama, gerçek zamanlı çöp toplama gibi dinamik depolama tahsisi ile ilgili daha fazla konuyu tartışır. , çok iş parçacıklı depolama ayırma ve paralel çöp toplama. Nesiller boyu çöp toplama, birçok nesnenin kısa ömürlü olduğu, bu nedenle çoğu zaman yalnızca daha genç nesnelerin tarandığı fikrine dayanır. Gerçek zamanlı çöp toplama, program çalışırken arka planda çalışır, ancak nesnelerin ve işaretçilerin grafiği değişiyorsa doğruluk sorunlarına yol açabilir. Çok iş parçacıklı depolama tahsisi ve paralel çöp toplama, çalışan birden çok iş parçacığına sahiptir, bu da algoritmaların yarışlar ve diğer doğruluk sorunlarıyla başa çıkmasını zorlaştırır. Konuşmacı ayrıca yığın ve öbek dahil olmak üzere farklı depolama tahsisi türlerini ve referans sayma, işaretle ve süpür ve durdur ve kopyala gibi çöp toplama yapmanın farklı yollarını özetler.
  
  
• 01:05:00 Bu bölümde eğitmen, depolama tahsis planlarını daha ayrıntılı inceleyeceklerini ve öğrencilerin yaklaşan ev ödevlerinde bazılarını deneme fırsatı bulacaklarını söyledi. Eğitmen daha sonra dersi sonlandırdı ve başka sorular için oturumu açtı.

[MetaQuotes]

Ders 12. Paralel Depolama Tahsisi

Ders 12. Paralel Depolama Tahsisi

Video, çeşitli bellek ayırma stratejilerini ve bunların değiş tokuşlarını tartışıyor. Malloc ve hizalı ayırmanın kullanımı ve ayrıca ücretsiz ile uygun bellek ayırmanın önemi açıklanır. Harici parçalanma ve yavaş performans sorunlarının yanı sıra sanal bellek tahsisi için Mmap kullanımı da ele alınmaktadır. C ve C++ programlamasındaki yığın kavramı, yığın çerçevelerini tahsis etmek için yığın tabanlı bir kaktüs yığını yaklaşımına vurgu yapılarak araştırılır, bu da daha iyi uzaya bağlı provalara ve üst sınırlara yol açabilir. Parçalanmayı en aza indirmek için küçük blokları optimize etmenin önemi ile birlikte bir doğrusal yığın havuzunun kullanımı da tartışılmaktadır. Video, küresel ve yerel yığın yaklaşımları ve bunların potansiyel sorunlarının yanı sıra bu sorunları ele almak için deposuz listeler ve periyodik bellek yeniden dengeleme gibi yaklaşımların tartışılmasıyla sona eriyor.

Video ayrıca paralel depolama tahsisi için çözümleri tartışıyor ve bir çözüm olarak İstif ayırıcıyı tanıtıyor. İstif ayırıcı, yanlış paylaşımı azaltmak, ölçeklenebilirliği iyileştirmek ve harici parçalanmayı azaltmak için yığınlar arasında taşınabilen yerel ve küresel yığınlar ile büyük süper blokların bir kombinasyonunu kullanır. Genel öbekte ayrılan maksimum depolama, en fazla yerel yığınlarda ayrılan maksimum depolamadır ve ayak izi, kullanıcı ayak izi artı yerel yığınlarda ayrılan ancak kullanılmayan depolama ile üst sınırdır. Video ayrıca Je malloc ve Super malloc gibi diğer ayırıcıları da kısaca tartışıyor ve kıyaslama sonuçları Super malloc'un Je malloc ve Hoard'dan daha iyi performans gösterdiğini gösteriyor. Tartışma, çöp toplama ayrıntıları için çevrimiçi slaytlara atıfta bulunularak sona erer.

• 00:00:00 Bu bölümde öğretim görevlisi, malloc ve hizalanmış ayırma da dahil olmak üzere bellek ayırma ilkellerini inceler. Hizalanmış ayırma, belleği önbellek satırlarına hizalamak için kullanılabilir, böylece bir önbellek satırındaki bir nesneye erişim yalnızca bir önbellek erişimi gerektirerek önbellek kayıplarının sayısını azaltır. Öğretim görevlisi ayrıca, belleği serbest işlevle düzgün bir şekilde serbest bırakmanın ve bellek sızıntılarından ve çift boşaltmadan kaçınmanın önemini tartışır. Son olarak öğretim görevlisi, bir destek dosyası olmadan sanal belleği tahsis etmek için kullanılabilen Mmap sistem çağrısını tanıtır.
  
  
• 00:05:00 Bu bölümde, konuşmacı, uygulamanın adres alanında, istenen bellek boyutunu tutmaya yetecek kadar büyük kullanılmayan bitişik bir bölge bulan bir sistem çağrısı olan M haritasını kullanarak bellek tahsis etme sürecini açıklamaktadır. tahsis edilen sayfalar için bir giriş içeren sayfa tablosu. Bir kütüphane çağrısı olan ve C kütüphanesinin yığın yönetim kodunun bir parçası olan malloc'tan farklı olarak, M haritası istenen hafıza için fiziksel hafızayı hemen ayırmaz, ancak sayfa tablosunu değiştirilen özel bir sıfır sayfasını gösteren girişlerle doldurur ve yalnızca kullanıcı ilk yazdığında fiziksel belleğe çevrilir. Ayrıca, M haritası işletim sisteminden bellek almaktan sorumluyken malloc, parçalanmayı azaltmak ve zamansal yerelliği iyileştirmek için önceden ayrılmış belleği yeniden kullanmaktan sorumludur.
  
  
• 00:10:00 Bu bölümde video, MMAP ve MALLOC'un depolama tahsisi için kullanılması arasındaki farkları tartışıyor ve MMAP'nin nispeten ağır olduğunu ve küçük tahsisler için bile tüm sayfaları tahsis ederek harici parçalanmaya ve yavaş performansa yol açtığını vurguluyor. Video ayrıca, sanal adresin belleğe erişmek için kullanıldığı ve donanımın sayfa tablosunda uygun fiziksel adresi aradığı adres dönüştürme sürecini de inceler. Video, TLB'lerin en son sayfa tablosu aramalarını önbelleğe alarak nasıl çalıştığını açıklıyor ve uzamsal veya zamansal konumu olan programların TLB'de depolanan birçok yeni erişime sahip olacağını ve bunun da daha hızlı performans sağlayacağını belirtiyor.
  
  
• 00:15:00 Bu bölümde, konuşmacı modern makinelerde adres çevirisinin nasıl çalıştığını tartışıyor ve ayrıca C ve C++ programlamasında yığın kavramını derinlemesine inceliyor. Yığınlar, işlev çağrılarını ve yerel değişkenleri takip etmek ve doğrusal bir sıra izlemek için kullanılır. Konuşmacı, geleneksel doğrusal yığınlardaki işaretçilerin bir kuralını vurgular: bir ebeveyn, değişkenlerin üzerine yazılmasını önlemek için işaretçileri kendi yığın değişkenlerine alt çocuklarına iletebilir, ancak tam tersi mümkün değildir. Konuşmacı ayrıca, belleği bir çocuk işlevden ebeveyne geri geçirmek için yığında veya ebeveynin yığınında bellek ayırma gibi seçenekler önerir.
  
  
• 00:20:00 paralel yığın tahsisi doğru, yığın tabanlı bir kaktüs yığını kullanmayla ilgili olası sorun, bellek parçalanmasıdır; burada gelecekteki ayırmalar için yeterli bitişik bellek kalmayabilir, bu da boş alana ve potansiyel olarak, bellek veya programın çökmesi. Paralel programlama için erken sistemler bu stratejiyi kullanırken, performansın etkisini en aza indirmek ve bellek parçalanmasının sonuçlarını dikkate almak için kodu optimize etmek önemlidir.
  
  
• 00:25:00 Bu bölümde video, maksimum derinliğe bir üst sınır koymadan yığın çerçevelerini tahsis etmek için yığın tabanlı bir kaktüs yığını yaklaşımının kullanımını tartışıyor. Ancak, bu yığın tabanlı kaktüs yığınıyla geleneksel doğrusal yığın kodunu kullanmaya çalışırken birlikte çalışabilirlik bir sorundur. Bu, iş parçacığı yerel bellek eşleme adı verilen bir yaklaşım kullanılarak düzeltilebilir, ancak bu yaklaşım, işletim sisteminde değişiklik yapılmasını gerektirir. Buna rağmen, yığın tabanlı kaktüs yığını yaklaşımı pratikte hala iyidir ve onu kullanan bir İpek programının uzaya bağlı olduğunu kanıtlamak için kullanılabilir. Bu boşluğa bağlı, yığın tabanlı bir kaktüs yığını kullanan bir P çalışan yürütmesinin yığın alanının P çarpı s1 ile üst sınırlandığını gösterir; burada s1, Silk programının seri yürütülmesi için gereken yığın alanıdır. Bu, yığın tabanlı kaktüs yığını yaklaşımının güzel bir özelliğidir.
  
  
• 00:30:00 Bu bölümde, Uzay-Zaman Takas Teoremine nasıl uygulanabileceğini anlamak için böl ve fethet matrisi çarpım kodu analiz edilir. Kod, her biri N/2 boyutunda sekiz özyinelemeli çağrı yapar ve her çağrıdan önce, N kare büyüklüğünde geçici bir alan elde etmek için bir malloc yapar ve işlev geri dönmeden hemen önce serbest bırakılır. Tahsisler bir yığın disiplinini takip ettiğinden, yığından ayırma yapılırken bile, önceki slayttan bağlanan alan, P çalışan alanının üst sınırı olarak kullanılabilir. İş N küptür ve aralık log kare N şeklindedir. Uzay için yineleme s of N/2 + theta of N squared'dir, bu da N kareyi çözer. Bu nedenle, meşgul yapraklar özelliği ve uzay sınırı teoremi, P işlemcilerde uzayın P çarpı N kare ile sınırlandığını gösterir.
  
  
• 00:35:00 Bu bölümde, konuşmacı önceki bölümde tartışılan algoritma için daha güçlü bir uzay sınırının nasıl kanıtlanacağını dinleyicilere anlatıyor. Algoritmanın yapısını analiz ederek ve özyineleme ağacının tepesine mümkün olduğunca yakın dallanmaya odaklanarak, konuşmacı, önceki üst sınırlardan daha iyi olan, P'nin üçte bir katı N kareye bir uzay sınırını gösterebilir. . Konuşmacı, bir algoritmanın yapısını analiz etmenin, yalnızca genel bir teoremi uygulamaktan daha güçlü uzaya bağlı kanıtlara yol açabileceğini belirtiyor. Bu bölüm, paralel işlevlerin eski ve üçüncü taraf seri ikili dosyalarla birlikte çalışma konusunda nasıl başarısız olduğunu tartışarak sona erer.
  
  
• 00:40:00 Bu bölümde, konuşmacı, eski kod için yığın havuzunu korumak için kullanılabilen, depolama tahsisinde doğrusal yığın havuzunun kullanımını tartışır. Havuzdaki yığın sayısı, boşluk sınırının korunması için işlemci sayısının sabit katı olmalıdır. Ancak bu strateji, iş çalma algoritmasının zaman sınırını etkileyebilir çünkü daha fazla yığın yoksa çalışan çalamayabilir. Konuşmacı daha sonra, ayırıcı hızı ve kullanıcı ayak izi dahil olmak üzere yığın depolama ayırıcılarının temel özelliklerinden bahseder ve ayırmadaki parçalanma ve ek yük potansiyeli nedeniyle küçük bloklar için iyileştirmenin önemini vurgular. Parçalanma, ayırıcı ayak izi bölü kullanıcı ayak izi olarak tanımlanır.
  
  
• 00:45:00 Videonun bu bölümünde konuşmacı, ikisinin oranını en aza indirmek için ayrılan ayak izinin kullanıcı ayak izine mümkün olduğunca yakın tutulmasını tartışıyor. Çözümlerden biri, işletim sistemine belirli bir bellek sayfasının artık gerekli olmadığını ve sanal bellekte tutulması gerektiğini söyleyen M tavsiyesi adı verilen bir şey kullanmaktır. Konuşmacı ayrıca, bir önceki dersteki, bin içermeyen listeler için parçalanmanın, U'nun ayrılmış toplam bellek miktarı olduğu, U'nun iki tabanlı log tabanı olduğu teoreminden bahseder ve ek alan, dahili parçalanma ve harici parçalanma arasındaki farkları açıklar. Son olarak, konuşmacı, modern 64 bit işlemcilerin yaklaşık 2 ila 48 bayt sanal adres alanı sağladığını ve bunun çoğu program için yeterli olduğunu, ancak yine de tipik bir makinedeki fiziksel bellekten daha fazla olduğunu belirtiyor.
  
  
• 00:50:00 Bu bölümde, video, varsayılan C++ ayırıcısının nasıl çalıştığı, muteks korumalı küresel bir yığın kullanarak paralel bir yığın ayırma stratejisini araştırıyor. Bir seri ayırıcıya kıyasla ek alan gerektirmediği için bu stratejinin patlaması birdir. Ancak, her ayırma ve serbest bırakma için kilidin edinilmesi yavaş olduğundan ve artan işlemcilerle daha da kötüleştiğinden, bu yaklaşımla ilgili olası sorun performans düşüşüdür. Kilit çekişmesi, daha yüksek istek oranları nedeniyle küçük tahsisler için daha sorunlu olan ve büyük blok tahsisleri daha fazla çalışma gerektiren zayıf ölçeklenebilirliğin birincil nedenidir.
  
  
• 00:55:00 Bu bölümde video, yerel bir yığın yaklaşımı kullanmanın bellek kaymasına ve sınırsız patlamaya neden olabileceği olası sorunu tartışıyor. Temel olarak, tüm belleğinizi bir iş parçacığına ayırır, ancak diğerinde boşaltırsanız, sistemde, ayırıcının yeniden kullanmak için yeterince akıllı olmadığı, kullanılmayan bellek olabilir. Sonuç olarak, birden fazla işlemci üzerinde çalışan programınızın belleği sonunda tükenebilir, ancak yalnızca tek bir çekirdek üzerinde çalışıyorsa bu olmaz. Video, bu sorunu çözmek için, serbest bırakılan bloğun bağlantılı listelerden birinde görünebilmesi için bin içermeyen liste veri yapısında işaretçilerin ayarlanmasını içeren bir bin free list yaklaşımının kullanılmasını önerir. Başka bir strateji, belleği periyodik olarak yeniden dengelemektir, ancak daha basit bir yaklaşım da tartışılmaktadır.
  
  
• 01:00:00 Bu bölümde, video, her iş parçacığının genel bir yığına ihtiyaç duymadan kendi yığınına erişmesi gibi istenen davranışı elde etmek için bellek ayırıcının nasıl değiştirileceğini tartışır. Bir yaklaşım, her nesneyi bir sahiple etiketlemek ve serbest kaldığında onu sahibinin yığınına iade etmektir. Bu şekilde, yerel nesneler hızlı bir şekilde tahsis edilir ve serbest bırakılırken, uzak nesneler bir miktar senkronizasyon gerektirir, ancak küresel bir yığın kadar değil. Ayrılabilecek maksimum bellek miktarı, sıralı program tarafından kullanılan miktar olan X ile sınırlanır ve patlama oranı, yığın sayısı olan P ile üst sınırlanır. Bu yaklaşım aynı zamanda birden çok işlemci aynı önbellek satırında farklı bellek konumlarına eriştiğinde ortaya çıkan yanlış paylaşıma karşı dirençlidir.
  
  
• 01:05:00 Bu bölümde, konuşmacı paralel yığın ayırmanın nasıl yanlış paylaşıma yol açabileceğini tartışıyor ve bir çözüm olarak yığın ayırıcıyı tanıtıyor. İstif ayırıcı, yerel ve küresel yığınların bir kombinasyonunu kullanır ve belleği yığınlar arasında taşınabilen büyük süper bloklar halinde düzenler. Bu yaklaşım hızlı, ölçeklenebilir ve yanlış paylaşıma karşı dirençlidir. Bir ayırma yapıldığında, ayırıcı yerel öbekte boş bir nesne olup olmadığını kontrol eder ve varsa onu alır. Değilse, daha fazla bellek almak için genel yığına gider.
  
  
• 01:10:00 Bu bölümde, konuşmacı, süper blokların hareketini yoğunlaştırmak için Horde ayırıcının en dolu olmayan süper bloktan serbest bir nesne tahsis ederek harici parçalanmayı nasıl azalttığını açıklar. Nesne yerel yığında bulunmazsa, genel yığını kontrol eder ve genel yığın boşsa işletim sisteminden yeni bir süper blok çağırır. Horde ayırıcı, yığının en fazla yarı kullanıldığı yerde bir değişmez tutar ve yığının az kullanıldığını tespit ederse, yarı boş bir süper bloğu küresel yığına taşır. Konuşmacı daha sonra, global öbekte ayrılan maksimum depolamanın en fazla yerel yığınlarda ayrılan maksimum depolama olduğunu belirten bir lemma sunar. Son olarak, konuşmacı, Horde ayırıcısının ayak izinin u artı SP sırasına göre üst sınırlandığı teoremini kanıtlar; burada u, program için kullanıcı ayak izidir ve SP, yerel yığınlarda tahsis edilmiş ancak kullanılmayan depolamadır. Patlama daha sonra bir artı sıra SP bölü u olarak hesaplanır.
  
  
• 01:15:00 Bu bölümde, konuşmacı Je malloc ve Super malloc dahil olmak üzere farklı ayırıcıları tartışıyor. Je malloc, farklı ayırma boyutları için ayrı küresel kilitlere sahiptir ve farklı ayırma izlerine karşı sağlam olmasını sağlayan em tavsiyesini kullanarak boş sayfaları serbest bırakır. Öte yandan, Super malloc çok az kod satırına sahip ve çok hızlı gelişiyor. Konuşmacı, Super malloc'un Horde'dan daha iyi performans gösteren J malloc'tan daha iyi performans gösterdiği, varsayılan ayırıcının ise düşük performans gösterdiği kıyaslama sonuçlarını paylaşır. Tartışma aynı zamanda çöp toplamaya da uzanıyor, ancak konuşmacı bunun ayrıntılarını çevrimiçi slaytlara bırakıyor.

[MetaQuotes]

Ders 13. Cilk Çalışma Zamanı Sistemi

Ders 13. Cilk Çalışma Zamanı Sistemi

Cilk çalıştırma zamanı sistemi, hesaplamaları çalışma zamanında işlemcilere eşlemek için rastgele bir iş çalma zamanlayıcısı kullanarak paralel işlemciler üzerindeki hesaplamaları programlamaktan ve yük dengelemeden sorumludur. Sistem, ek çalma maliyeti pahasına programın seri yürütülmesini optimize etmek için tasarlanmıştır. Çalışan, yığın çerçevelerine işaretçiler içeren ve baş ve kuyruk işaretçileri kullanan ayrı bir deste veri yapısını korur. Çalınmaya müsait çerçeveler, güverte çağrı yığınının dışındayken çalmanın gerçekleşmesi için gerekli bilgileri içeren ek bir yerel yapıya sahiptir. Bu bölüm, sistemin işlemcilerin çalışan bir işlevin ortasından yürütmeye başlamasını nasıl sağladığını ve belirli işlemciler hala hesaplamaların bitmesini beklediği için noktanın ötesinde yürütülemeyen bir senkronizasyon ifadesine ulaşıldığında işlemciler arasındaki eşitlemenin nasıl karmaşık hale geldiğini açıklar. Buna ek olarak, konuşmacı, sistemin performansını, tasarım hususlarını ve veri yapılarını ve sistemin THC protokolünü kullanarak yürütmeyi nasıl optimize ettiğini ele alıyor ve biri işi yürüten işçi için, diğeri hırsız için olmak üzere iki protokol setini içeriyor.

Cilk Runtime System, mağdur süreçlerin yürütme destelerinden yapılan hesaplamaların çalınmasını önlemek için bir set atlama ve uzun atlama protokolü kullanır. Cactus Stack soyutlaması, hırsız sürecinin kurbanın yığınlarının bozulmasını önlemek için kendi çağrı yığınına sahip olmasına izin verir. Sistemin senkronizasyon protokolü, senkronizasyonun yalnızca bir işlev içindeki iç içe hesaplamalar arasında gerçekleşmesini sağlamak için bir hesaplama ağacı ve bir Kaktüs Yığını kullanır. Tam Çerçeve Ağacı, senkronizasyon sürecini basitleştirmek için olağanüstü alt hesaplamalarla hesaplamalar arasındaki üst-alt ilişkileri korur. Ek olarak, çalışma zamanı sistemi, geçerli işlevin olağanüstü alt hesaplamaları olmadığı ve tüm çalışanların meşgul olduğu ortak durumu optimize eder. Desteklenen diğer özellikler arasında C++ istisnaları, indirgeyici hiper nesneler ve soyağaçları bulunur.

• 00:00:00 Bu bölümde Tibi, paralel işlemcilerde programlama ve yük dengeleme hesaplamalarından sorumlu olan Cilk runtime sistemini açıklıyor. Çalışma zamanı sistemi, hesaplamaları çalışma zamanında işlemcilere eşlemek için rastgele bir iş çalma zamanlayıcısı kullanır ve verimli bir yürütme sağlar. Tibi, Cilk çalışma zamanı sisteminin karmaşık bir yazılım parçası olduğunu, ancak temel sihrinin Cilk derleyicisi ve çalışma zamanı kitaplığının işbirliği yoluyla uygulandığını belirtiyor. Ek olarak, derlemeden sonra basit bir Cilk programı için sözde kodu gösterir ve bu da Cilk'in çalışma zamanı sisteminin altında yatan karmaşık süreci vurgular.
  
  
• 00:05:00 Bu bölümde, konuşmacı Cilk çalışma zamanı sistemi için gereken işlevselliğin yanı sıra performansla ilgili hususları açıklamaktadır. Cilk programının, program bir işlemci üzerinde çalışırken dinamik olarak ortaya çıkan bir hesaplama gününü nasıl yürüttüğünü göstermek için paralelleştirilmiş bir Fibonacci rutini örneği kullanıyor. Ancak silk spawn deyimiyle karşılaşıldığında, fib 3 için yeni bir çerçeve oluşturulur ve paralel olarak yürütülecek başka bir iplikçik bulunur. İşlemci daha sonra sanki sıradan bir işlev çağrısıymış gibi fib of 3'ü yürütmeye başlar. Talimat işaretçisi fib yordamı başlangıcına döndüğünde işlem kendini tekrar eder.
  
  
• 00:10:00 Bu bölümde, birden çok işlemcinin Cilk runtime sistemi yardımıyla bir fib yordamını nasıl paralel olarak yürüttüğünü görüyoruz. Her işlemci, bağımsız kayıtlara sahip olmasına rağmen, yürütülen bir işlevin ortasına atlar ve onu çalıştırmaya başlar; bu, Silk sisteminin işlemcilerin çalışan bir işlevin ortasından yürütmeye başlamasını nasıl sağladığı sorusunu gündeme getirir. Ayrıca, işlemciler arasındaki senkronizasyon, noktanın ötesinde yürütülemeyen bir senkronizasyon ifadesine ulaşıldığında karmaşık hale gelir, çünkü belirli işlemciler hala hesaplamaların bitmesini bekler, bu da iç içe desen içinde ince taneli bir senkronizasyon gerektirir.
  
  
• 00:15:00 Bu bölümde, konuşmacı Cilk çalışma zamanı sistemi için uygulama konularını tartışıyor. Üç ana husustan bahsediyorlar: tek bir çalışanın programı yürütebilmesi, işlevleri yürütmenin ortasına atlayabilme ve diğer işlemcilerin kaldığı yerden devam edebilme ve senkronizasyon. Ek olarak Silk, yığının tüm görünümlerini kullanılabilir ve tutarlı hale getirmek için doğru şekilde uygulanması gereken bir kaktüs yığını kavramına sahiptir. Son olarak, sistemin, işlemcilerin birbirlerinden çerçeve çalmasına izin vererek iş hırsızlığına izin vermesi gerekir.
  
  
• 00:20:00 Bu bölümde konuşmacı, seri yürütme, çalışan işlevlerin ortasına atlayan hırsızlar, iç içe ince taneli bir şekilde eşitlemek için eşitleme, bir kaktüs yığınını içeren Cilk Çalıştırma Zamanı Sistemi için gereken işlevselliği tartışır. tüm çalışanların görmesi ve hesaplamayı çaldıklarında mevcut olabilecek yumurtlama çerçeveleri ve adı verilen çerçevelerin karışımlarıyla uğraşması. Daha sonra bölüm, bol miktarda paralelliğe ihtiyaç duyduğumuz, T1 bölü T sonsuzunun P'den çok daha büyük olması gerektiği ve programı çalıştırmak için işlemci sayısını artırırken doğrusal hızlanma istediğimiz sistemin performansını ele almak için devam eder. Bu bölüm ayrıca P işlemciler üzerinde TCP'nin beklenen çalışma süresini de kapsar; bu, hesaplama işinin işlemci sayısına bölümü artı hesaplama aralığı sırasına göre bir şeyle orantılıdır.
  
  
• 00:25:00 Bu bölümde Cilk Runtime Sistemini ve yeterli paralelliğe sahip programlarda yüksek iş verimliliği sağlama amacını öğreniyoruz. Silk Runtime System, çeliklere bazı ek maliyetler pahasına programın seri olarak yürütülmesini optimize ederek, önce iş prensibine uyar. Çalışma zamanı sistem kitaplığı, paralel yürütmeyle ilgili sorunları ele alır ve çelikler oluştuğunda daha yavaş yürütme yollarını işler. Çalışan, yığın çerçevelerine işaretçiler içeren ve baş ve kuyruk işaretçileri kullanan ayrı bir deste veri yapısını korur. Çalınmaya müsait çerçeveler, güverte çağrı yığınının dışındayken çalmanın gerçekleşmesi için gerekli bilgileri içeren ek bir yerel yapıya sahiptir.
  
  
• 00:30:00 Bu bölümde Cilk Runtime System tasarımı ve temel veri yapılarını öğreniyoruz. Sistem, her hesaplama için, sırasıyla bir yumurtlama işlevinin ve bir yumurtlama yardımcısının her örneği için bir çalışan yapısını ve İpek yığın çerçeve yapısını koruyan bir yumurtlama yardımcı işlevi oluşturur. Silk RTS yığın çerçevesi, İpek yığın çerçevesinin durumunu özetlemek için arabellek ve bayraklar tamsayı gibi alanları ve çağrı yığınındaki bir üst İpek yığın çerçevesine işaretçi içerir. Çalışan yapısı, geçerli Silk RTS yığın çerçevesine bir deste ve bir işaretçi tutar. Bu veri yapıları, Intel so+ çalışma zamanı sisteminin detaylandırdığı Cilk Çalışma Zamanı Sisteminin temel unsurlarıdır.
  
  
• 00:35:00 Bu bölümde video, "foo" yumurtlama işlevi kodunu ve yumurtlama yardımcısı işlevini araştırıyor. "foo" kodu, atlama rutini ile bir yumurtlama için ayarlanan yığın çerçevesini başlatmak için bir çağrı, yumurtlama yardımcı işlevi "yumurtlama çubuğu"na bir çağrı, Silk RTS'deki bir havuz için koşullu bir kod bloğu içerir. ve temizleme için pop ve yaprak çerçevelerine çağrılar. Yumurtlama yardımcısı kodu, yığın çerçevesini başlatmak için bir çağrı ve yığın yapısı için ek temizleme işlevleriyle İpek RTS'yi ayırmak için bir çağrı içerir. Kurulum rutini, hırsızların işlevin devamını çalmasına izin veren bir işlev olarak tanımlanır ve işlev konumunu devam ettirmek için gerekli bilgileri depolamak üzere bir arabelleği argüman olarak alır.
  
  
• 00:40:00 Bu bölümde, konuşmacı kayıt kümesinin nasıl kısıtlanacağını ve bunların bir işlev çağrısı için önceden belirlenmiş bir kümeye nasıl kaydedileceğini tartışır. Kayıtları kaydetme sorumluluğu fonksiyona aittir, ancak talimat işaretçisi ve yığın işaretçileri ara belleğe kaydedilir. Bölüm, bir yumurtlama yardımcısı işlevini ve bunun çalışan yapılarını ve geçerli yığın çerçevelerini nasıl güncellediğini tartışmaya devam ediyor. Son olarak, bu bölüm çerçeve girme hızlı yordamının çağrı yığınında bir üst işaretçiyi nasıl oluşturduğunu ve çalışanın mevcut yığın çerçevesini en alt noktayı gösterecek şekilde nasıl güncellediğini açıklar.
  
  
• 00:45:00 Bu bölümde, "The Cilk Runtime System" başlıklı YouTube videosunun transkripti, Silk RTS ayırma işlevinin hesaplamanın çalınmasına nasıl izin verdiğini açıklıyor; burada silk artistik yürütme bittiğinde bir hırsız gelip çalabilir ipek yumurtlamanın devamı. Pop çerçeve, yığın çerçeve yapısını temizlemekten ve geçerli yığın çerçevesini ebeveyne işaret edecek şekilde güncellemekten sorumludur. Bu işlev çağrısı geri dönebilir veya dönmeyebilir ve çalışma zamanı sisteminin optimize etmesi için bu iki durumdan hangisinin daha önemli olduğu, ikisi önce çalışan prensibine dayanan başarı durumudur.
  
  
• 00:50:00 Bu bölümde, konuşmacı, işçilerin düzenli seri yürütme gerçekleştirdiğinin varsayıldığı birinci durumda, Cilk çalışma zamanı sisteminin çalışan yürütme üzerindeki optimizasyonunu tartışıyor. Ayrıca, hırsızın kurbanın destesinin üstünü hedef alması, öğeyi kuyruktan çıkarması ve destenin başını ve mevcut yığın çerçeve işaretçisini güncellemesiyle işçi hırsızlığının nasıl çalıştığını açıklarlar. Ortaya çıkan işlevin sonucu, orijinal SIL kodundaki ana yığın çerçevesine döndürülür.
  
  
• 00:55:00 Bu bölümde, konuşmacı Cilk Runtime System'in THC protokolü adı verilen bir protokol kullanarak birden fazla işlemciyi içeren eşzamanlı erişimleri ele alma yaklaşımını açıklıyor. Protokol, biri işi yürüten işçi ve diğeri hırsız için olmak üzere iki protokol seti içerir. İşçinin protokolü, güvertenin altından bir şey çıkarmaya çalışılarak optimize edilmiştir ve yalnızca başarısızlık durumunda güvertede bir kilit elde ederken, hırsız herhangi bir güverte işlemi gerçekleştirmeden önce her zaman bir kilidi alır. Hırsız daha sonra sihirli bir şekilde uzun atlama işlevini çağırarak, ayarlanmış atlama işlevinden alınan yığın çerçeve arabelleğini geçerek ve kayıt durumunu çalınan devamın durumu olarak ayarlayarak çalınan bir devamı sürdürür.
  
  
• 01:00:00 Bu bölümde konuşmacı, Cilk çalışma zamanı sistemi içindeki set jump ve uzun atlama çağrıları arasındaki etkileşimi tartışır. Bir uzun atlama rutini çağrıldığında, set atlamadan ikinci kez, bu sefer ikinci bağımsız değişkende belirtilen farklı bir değerle etkin bir şekilde nasıl geri döndüğünü açıklarlar. Hırsız, uygun arabelleği ve ikinci argümanı kullanarak kurbanın kodundaki belirli bir hesaplamayı atlamak için uzun bir sıçrama gerçekleştirebilir. Konuşmacı, bir aramanın üzerinden atlamak ve farklı bir yaklaşım kullanmak için gereken mesafeyi statik olarak hesaplamanın mümkün olduğunu, ancak ayarlanmış atlama ve uzun atlama protokolünün Cilk çalışma zamanı sistemi için daha esnek bir yöntem olarak hizmet ettiğini belirtiyor. Genel olarak, konuşmacı, hırsızın Cilk kullanarak kurbanın güvertesinden hesaplamaları çalması için mevcut olan çeşitli teknikleri vurgular.
  
  
• 01:05:00 Bu bölümde, Cilk runtime sistemi için bir kaktüs yığını soyutlama ihtiyacı tartışılmaktadır. Kurbanın yığınının kullanılmasının kurbanın yığınının bozulmasına yol açabileceği ve tüm çalışanlar arasında tutarlılığın sağlanmasında sorunlara neden olabileceği açıklanmaktadır. Bu nedenle, hırsız için ayrı bir çağrı yığınına ihtiyaç vardır. Kaktüs yığınının uygulanması, hırsızın devamı çalmasını ve yığın işaretçisini kendi yığınına ayarlarken, RB p'den ofsetler aracılığıyla kurbanın yığınındaki işlevin durumuna hala erişebilmesini içerir.
  
  
• 01:10:00 Bu bölümde, konuşmacı SIL çalışma zamanı sisteminin farklı işlemcilerde hesaplama senkronizasyonunu nasıl ele aldığını açıklıyor. Sistem, senkronizasyonun genel olarak program değil, yalnızca bir işlev altındaki iç içe alt hesaplamalar arasında olmasını sağlamak için kaktüs yığınını ve bir hesaplama ağacını kullanır. Bir işçi, tüm alt hesaplamalar geri dönmeden önce bir ipek eşitleme ifadesine ulaştığında hırsız olur ve çalınan bir hesaplamanın yığın çerçevesi üzerinde çalışmaya devam eder. Bu, sistemin çalışan israfını önlemesine ve iç içe geçmiş hesaplamaların uygun şekilde senkronize edilmesini sağlamasına olanak tanır. Sistem, derleyiciye bu yaklaşımla çelişebilecek bir optimizasyon kullanmaması talimatını verir.
  
  
• 01:15:00 Bu bölümde, Cilk Çalışma Zamanı Sisteminin, hangi hesaplamaların diğer hangi hesaplamaların bitmesini beklediğini takip eden, tam çerçeveler adı verilen bir durum ağacını sürdürdüğü açıklanmaktadır. Bu sistem, ana çerçevelere, potansiyel olarak alt çerçevelere yönelik işaretçiler ve olağanüstü alt hesaplamaların birbiriyle nasıl ilişkili olduğu dahil olmak üzere, paralel yürütme için çok sayıda bilgiyi takip etmek için bir tam çerçeve ağacı kullanır. Bir çalışan bir eşitlemeyle karşılaştığında, olağanüstü bir alt hesaplamaya sahipse, eşitleyemez ve daha fazla iş çalmak için hırsız olana kadar tüm çerçevesini askıya alması gerekir. Bu sistem, bir programın geniş paralelliğe sahip olmasını sağlar ve senkronizasyon protokollerini basitleştirir.
  
  
• 01:20:00 Bu bölümde, konuşmacı Cilk Runtime System'in yürüten işlevin öne çıkan alt öğesi olmadığı ve sistemdeki tüm çalışanların kendi görevleriyle meşgul olduğu ortak durumu nasıl optimize ettiğini tartışır. Çalışma zamanı sistemi, ipek eşitleme için eşitlemenin gerekli olup olmadığını değerlendirmek için ilişkili bir yığın çerçevesinin bayrak alanından gelen bitleri kullanır. Konuşmacı ayrıca çalışma zamanı sistemi tarafından desteklenen C++ istisnaları, indirgeyici hiper nesneler ve soyağaçları gibi diğer bazı özelliklerden bahseder.

[MetaQuotes]

Ders 14. Önbelleğe Alma ve Önbelleği Verimli Algoritmalar

Ders 14. Önbelleğe Alma ve Önbelleği Verimli Algoritmalar

Önbelleğe alma ve önbelleği verimli kullanan algoritmalar hakkındaki videoda eğitmen, modern makinelerin önbellek hiyerarşisini, tamamen ilişkilendirilebilir ve doğrudan eşlenmiş önbellekler arasındaki farkları ve ayarlı birleştirici önbelleklerin avantajlarını ve dezavantajlarını açıklıyor. Video ayrıca ideal önbellek modelini ve önbelleği verimli kullanan algoritmalar kavramını da tanıtıyor. Konuşmacı önbellek eksik lemmasını, uzun önbellek varsayımını ve alt matris önbelleğe alma lemmasını tartışır. Ayrıca, bir alt matrisi okurken ve matris çarpımı sırasında ortaya çıkan önbellek kayıplarını da analiz ederler. Video, döşemeli matris çarpımı kavramını ve bunun performansı nasıl önemli ölçüde artırabileceğini tanıtarak sona eriyor, ancak bunun taşınabilir olmadığını ve birden çok önbellek düzeyi için optimize etmenin pahalı olabileceğini de belirtiyor.

Ders, örnek olarak özyinelemeli matris çarpımını kullanarak önbelleğe alma ve önbelleği verimli kullanan algoritmaları kapsar. Konuşmacı, hem işi hem de önbellek kayıplarını ayrı ayrı analiz etmenin önemini vurguluyor ve farklı önbellek boyutları nedeniyle önbelleğe duyarlı algoritmaların tüm makineler için ideal olmayabileceğini belirtiyor. Konuşmacı ayrıca herhangi bir önbellek boyutu için otomatik ayar yapan önbellekten habersiz algoritmaları tartışıyor ve paralel önbellekten habersiz koddaki gelişmelerden bahsediyor. Son olarak amaç, ya önbellek farkında olan ya da önbellekten habersiz algoritmalar tasarlamaktır ve önbellekten habersiz algoritma tasarımı tartışması bir sonraki derste devam edecektir.

• 00:00:00 Önbelleğe alma ve önbelleği verimli kullanan algoritmalarla ilgili bu bölümde eğitmen, özel L1 verilerini ve her işlemci için talimat önbelleklerini, özel bir L2 önbelleğini ve son düzey önbelleği içeren modern makinelerin önbellek hiyerarşisini tartışır. tüm işlemciler arasında paylaşılır. Bu önbelleklerin boyutları, bellek hiyerarşisinde yukarı çıkıldıkça artar, DRAM en yavaş ve en büyüğüdür. Önbelleğin ve gecikmenin ilişkilendirilebilirliği, bellek hiyerarşisinde yukarı çıkıldıkça artar, L1 önbelleği en hızlı ve en ilişkilendirilebilirdir. Eğitmen ayrıca paralel işleme için bellek adres erişimlerinde tutarlılığı sağlamak için önbellek tutarlılık protokollerinin öneminden bahseder. Programlarda yerellikten nasıl yararlanılacağını anlamak, daha hızlı bellek önbelleklerinin verimli şekilde kullanılmasına yardımcı olabilir.
  
  
• 00:05:00 Bu bölümde, tamamen ilişkilendirilebilir ve doğrudan eşlenmiş önbellekler arasındaki farklar tartışılmaktadır. Tamamen ilişkilendirilebilir bir önbellek, yavaş ve verimsiz olabilecek bir bloğu bulmak için tüm önbelleğin aranmasını gerektirir, çünkü bir bloğu bulmak birden çok satıra erişmeyi gerektirebilir. Öte yandan, doğrudan eşlenmiş önbellek, her blok için yalnızca bir olası konuma sahiptir, bu da bloklara erişimi daha az çakışma ile çok daha hızlı hale getirir. Önbellek bloğunun konumunu belirlemek için sanal bellek adresini bölerken, adres alanının üç bileşeni olan ofset, küme ve etiket de açıklanır. Etiket, önbellek bloğunun hangi bellek bloğuna karşılık geldiğini tanımlar ve küme, W bitlik toplam adres alanı ile bloğun önbellekte hangi konuma gideceğini belirler.
  
  
• 00:10:00 Bu bölümde, video, önbellekte yalnızca bir konumun aranması gerektiğinden hızlı olan, ancak önbellek bloklarının birbirini çıkarmaya devam ettiği durumlarda çakışmaya yatkın olan doğrudan eşlemeli önbelleklerin avantajlarını ve dezavantajlarını tartışıyor. performansı azaltmak. Ardından video, her kümenin birden çok satır içerdiği ve her önbellek bloğu için önbellekte birden fazla olası konuma izin verdiği hibrit bir çözüm olan küme ilişkisel önbellekleri tanıtıyor. Video ayrıca, bir önbellek bloğuna ilk kez erişildiğinde meydana gelen ve önlenemeyen soğuk atlamalar da dahil olmak üzere, farklı önbellek kaçırma türlerinin bir taksonomisinden bahseder.
  
  
• 00:15:00 Bu bölümde video, kapasite eksiklikleri, çakışma eksiklikleri ve paylaşım eksiklikleri dahil olmak üzere farklı önbellek kayıp türlerini tartışıyor. Kapasite kayıpları, önbellek dolduğunda ve erişilmesi gereken tüm önbellek bloklarına sığamadığında meydana gelirken, aynı küme eşlemesinden önbelleğe çok fazla blok geldiğinde küme ilişkisel önbelleklerde çakışma kayıpları meydana gelir. Son olarak, birden çok işlemci aynı önbellek satırına eriştiğinde ve bunlardan en az biri ona yazarken, paralel bir bağlamda paylaşım eksiklikleri meydana gelir. Video ayrıca, satır ana düzeninde saklanan daha büyük bir matris içindeki bir alt matrise erişilirken çakışma eksiklikleri için kötü bir durum örneği sağlar.
  
  
• 00:20:00 Bu bölümde konuşmacı, önbelleğe alma ve önbelleği verimli kullanan algoritmaları tartışıyor. Daha büyük bir matris içindeki bir alt matrise erişmenin bir örneğini ve önbellek yalnızca 4 yollu ilişkisel olduğunda çakışma kayıplarının nasıl oluşabileceğini kullanırlar. Konuşmacı, matristeki her satırın sonuna sabit miktarda boşluk eklenmesini önerir, böylece her satır 2^15 bayttan uzun olur, bu da çakışma kayıplarını azaltmaya yardımcı olabilir.
  
  
• 00:25:00 Bu bölümde konuşmacı, algoritmaların önbellek performansını analiz etmek için kullanılan bir model olan ideal önbellek modelini tartışıyor. Bu model, iki seviyeli bir önbellek hiyerarşisi, tamamen ilişkilendirilebilir bir önbellek ve optimal bir Nishant değiştirme politikası varsayar. Konuşmacı, önemli olan iki performans ölçüsünün N'nin sırası ve önbellek kayıp sayısı olduğunu açıklıyor; burada ideal senaryo, işi geleneksel standart algoritmadan artırmadan düşük sayıda önbellek kaçırmaya sahip olmaktır. 1985'te kanıtlanmış olan LRU lemmasından da bahsedilmektedir ve bu, M boyutunda ideal bir önbellekte Q önbellek kaçırmalarına neden olan bir algoritmanın, LRU ilkesini kullanan 2M boyutunda tamamen ilişkilendirilebilir bir önbellekte 2Q önbellek kayıplarına neden olacağını belirtir.
  
  
• 00:30:00 Bu bölümde, konuşmacı önbelleği verimli kullanan algoritmalar kavramını ve bunların önbellek kayıplarının sayısını en aza indirerek program performansını nasıl geliştirebileceklerini tanıtıyor. LRU kullanan ideal önbelleğin iki katı büyüklüğünde tamamen ilişkilendirilebilir bir önbelleğin, önbellek kayıplarının sayısının iki katından fazlasına neden olmayacağını belirten en son kullanılan (LRU) değiştirme politikasını açıklıyor. Bu, asimptotik analiz gerçekleştirirken önbellek kayıplarının daha kolay analiz edilmesini sağlar. Konuşmacı ayrıca, bir program önbellek boyutunun üçte birinden daha küçük olan ve ortalama boyutu en az bir önbellek satırının boyutu olan bir dizi veri segmentini okursa, o zaman sayı olduğunu belirten bir önbellek eksik lemması sunar. hepsini okumak için önbellek özlüyor, bölümlerin toplam boyutunun bir önbellek satırının boyutuna bölünmesiyle en fazla üç katıdır.
  
  
• 00:35:00 Bu bölümde, video önbelleğe alma ile ilgili iki varsayımı tartışıyor - önbellek eksik lemma ve uzun önbellek varsayımı. Cache miss lemma, eğer veri segmentlerinin ortalama uzunluğu bir önbellek bloğu boyutundan büyükse, bunun önbellek kayıplarının sayısını sadece sabit bir faktör kadar artırdığını belirtir. Uzun önbellek varsayımı, önbelleğin genişliğinden daha uzun olduğunu varsayar ve pratikte genellikle karşılanır. Video ayrıca, alt matrisleri önbellek satırlarına sığdırmada kısa önbelleklerle ilgili sorunu ve uzun önbellek varsayımının bu sorunu çözmede neden yararlı olduğunu tartışan alt matrisi önbelleğe alma lemmasını da açıklıyor.
  
  
• 00:40:00 Bu bölümde konuşmacı, önbelleğe alma ve önbelleği verimli kullanan algoritmaları tartışıyor. Bir kare alt matrisi önbelleğe okurken oluşan önbellek kayıplarının sayısını analiz ederler ve matrisin tüm öğelerini önbelleğe okumak için gereken önbellek kayıplarının sayısının en fazla 3n^2/B olduğunu göstermek için önbellek kayıp lemmasını kullanırlar. . Daha sonra, matrisin satır ana düzeninde olduğunu ve uzun önbellek varsayımını karşıladığını varsayarak, standart kübik çalışma matrisi çarpma algoritmasında oluşan önbellek kayıplarının sayısını analiz ederler. Üç durumu ele alıyorlar ve ikinci ve üçüncü durumlar için LRU'yu varsayıyorlar, sonuçta algoritma tasarımında önbellek optimizasyonunun önemini gösteriyorlar.
  
  
• 00:45:00 Bu bölümde konuşmacı, önbelleğe alma ve önbelleği verimli kullanan algoritmaları tartışıyor. Matris çarpımı için, n'nin M bölü B'den büyük olduğu ve n'nin C çarpı M bölü B'den küçük olduğu iki durumu analiz ederler. Bir LRU değiştirme politikası kullanırlar ve matris B'ye erişirken ortaya çıkan önbellek kayıplarının sayısını hesaplarlar. durumda, n küplü önbellek kayıplarının tetasına ihtiyaç duyduklarını ve bunun da algoritmada konuma sahip olmaktan hiçbir kazanç elde etmediklerini fark ederler. İkinci durumda, uzamsal yerellikten yararlanabilirler ve önbellek kayıplarının sayısını B faktörü kadar azaltabilirler, bu da daha verimli olan n küp bölü B önbellek kayıplarının tetasına neden olur.
  
  
• 00:50:00 Videonun bu bölümünde konuşmacı, önbelleğe alma ve önbelleği verimli kullanan algoritmaları tartışıyor. Önce tüm matrisin önbelleğe sığdığı durumu analiz ederler, bu da n kare bölü B'nin toplam önbellek kayıp teta sayısıyla sonuçlanır. toplam önbellek kayıp sayısını n küp bölü B'nin tetasına düşürün. Bununla birlikte, döşeme adı verilen bir optimizasyon kullanarak daha iyisini yapmanın mümkün olduğunu belirtiyorlar; burada döşemeler üzerinde döngü yapmak için altı for döngüsü kullanılıyor ve her bir alt birim için hesaplama yapılıyor. -matriks bir sonrakine geçmeden önce. Boyutları s'ye s olan bir alt matrisin işi, s'nin küpüdür.
  
  
• 00:55:00 Bu bölümde, karo matris çarpımı kavramı tanıtılır ve ayrıntılı olarak tartışılır. Bu algoritmanın amacı, alt matrisleri önbelleğe sığdırmaktır, böylece tüm hesaplamalar, daha fazla önbellek hatası olmaksızın önbellekte yapılabilir. Önbellek kayıplarının sayısı analiz edilir ve toplam n^3/B * sqrt(M) önbellek kayıplarının sayısı için önbellek kayıp sayısının n/s^3 çarpı s^2 /B olduğu bulunur. Bu sayı, matris çarpma kodunun performansını iyileştirmede çok önemlidir. Bununla birlikte, algoritmada bir sorun ortaya çıkar: Çalıştığı makinenin önbellek boyutuna büyük ölçüde bağlı olduğu için taşınabilir değildir. Ayrıca, çok boyutlu ayarlama optimizasyonu çok daha pahalı hale gelir ve çoklu önbellek seviyeleri için optimizasyon yapılırken kod daha karmaşık hale gelir.
  
  
• 01:00:00 Bu bölümde ders, önbelleğe alma ve önbelleği verimli kullanan algoritmaları araştırıyor. Konuşmacı, önbelleği verimli kullanan bir algoritma için parametreleri ayarlamanın ve onu belirli bir makine için optimize etmenin zorluklarını tartışıyor. Giriş matrislerinin dört alt matrise veya çeyreğe bölündüğü yinelemeli bir matris çarpma algoritması sunarlar. Çıkış matrisinin her çeyreği için, iki matrisin toplamı yinelemeli olarak oluşur. Son olarak, konuşmacı bu algoritmanın çalışmasını analiz eder ve bunun hala iyi önbellek performansını koruyan daha basit bir tasarım olduğu sonucuna varır.
  
  
• 01:05:00 Bu bölümde konuşmacı, önbelleğe alma ve önbelleği verimli kullanan algoritmaları tartışıyor ve iş analizi ile önbellek kayıplarının analizi arasındaki farkı açıklamak için matris çarpımı örneğini kullanıyor. Konuşmacı, boyut problemini ve dallanma alt problemlerini görselleştirmek için bir özyineleme ağacı çizer ve yapraklara kadar olan seviye sayısının log 2 tabanı n olduğunu not eder. Yaprak sayısı, n'nin küpü ile aynı olan n'nin log tabanı 2'ye göre sekiz olarak hesaplanır. İş miktarı basitçe teta n küp şeklindedir ve önbellek eksiklikleri, alt matrisin önbelleğe sığdığı ve N kare bölü önbellek kayıplarının tetasının kullanıldığı farklı bir temel durumla analiz edilir. Konuşmacı, seviyelerin sayısının sadece n'nin log tabanı 2 olmadığını, aynı zamanda önbelleğin boyutuna da bağlı olduğunu ve farklı sayıda yaprakla sonuçlandığını, n'nin teta küpü bölü m üzeri üç yarı olduğunu vurgular.
  
  
• 01:10:00 Bu bölümde, konuşmacı özyinelemeli matris çarpım kodu örneğini kullanarak önbelleği verimli kullanan bir algoritmada önbellek kayıplarının sayısının nasıl analiz edileceğini açıklıyor. Kod, önbellekten habersizdir, yani önbellekler hakkında açık bir bilgisi yoktur ve üzerinde çalıştığı makinenin belirli önbellek boyutu için kendini pasif bir şekilde otomatik olarak ayarlar. Konuşmacı ayrıca, günümüzün en iyi önbellek bilgisiz kodlarının keyfi dikdörtgen matrisler üzerinde çalıştığından ve sekiz yollu bölme yerine ikili bölme gerçekleştirdiğinden bahseder. Konuşmacı, paralel bağlamı tartışır ve özel önbelleklere sahip birden çok işlemci üzerinde çalışan deterministik bir hücre hesaplamasında önbellek kayıplarının sayısının nasıl analiz edileceğini açıklar.
  
  
• 01:15:00 Bu bölümde konuşmacı, önbelleğe alma ve önbelleği verimli kullanan algoritmaları tartışıyor. Seri yanılsamadaki önbellek kayıplarını en aza indirerek, bunları düşük açıklıklı algoritmalar için paralel yürütmede esasen en aza indirebiliriz. Konuşmacı, seri yürütme ile aynı olan bir paralel özyinelemeli matris çarpma algoritması için bir önbellek kayıp sınırı sağlar. Amaç, önbellek hakkında açık bilgiye sahip olan veya önbellekten habersiz olan algoritmalar tasarlamaktır. Konuşmacı her ikisine de örnekler veriyor ve bir sonraki derste önbellekten habersiz algoritma tasarımı hakkında daha fazla tartışma olacağından bahsediyor.

[MetaQuotes]

Ders 15. Önbelleği Bilmeyen Algoritmalar

Ders 15. Önbelleği Bilmeyen Algoritmalar

Video, bir makinedeki önbellek boyutunu otomatik olarak ayarlayabilen, iyi önbellek verimliliği sağlayan ve makinenin önbellek parametreleri hakkında bilgi gerektirmeyen önbellekten habersiz algoritmaları tartışıyor. Video, bir 2B matris üzerinde şablon yöntemini kullanarak diferansiyel denklemler yoluyla ısı difüzyonunu simüle etmek için kodun nasıl yazılacağını gösterir. Kodun hem döngülü hem de yamuk versiyonları vardır; ikincisi önbellek açısından daha verimlidir ancak döngü kodunun erişim modelinin öngörülebilirliği nedeniyle 2B simülasyonda önemli ölçüde daha hızlı değildir. Video ayrıca önbelleğe alma ile paralellik arasındaki etkileşimi ve olası paralel hızlanma darboğazlarının teşhisini tartışıyor. Son olarak, konuşmacı şablon hesaplamalarını ve bir dizideki her noktanın, şablon adı verilen, önbellek kayıplarından muzdarip olabilen ve zamansal ve uzamsal konumlardan yararlanan verimli algoritmalar kullanılarak azaltılabilen depolama gereksinimleri olan sabit bir model kullanılarak nasıl güncellendiğini açıklar.

Videonun ikinci kısmı, sıralama ve birleştirme için önbellekten habersiz algoritmaları tartışıyor. Video özellikle birleştirme sıralamasının önbellek karmaşıklığını ele alıyor, çok yollu birleştirme kavramını tanıtıyor ve çok yollu birleştirme algoritmasının önbellek karmaşıklığını açıklıyor. Video ayrıca, K kareli öğeleri ve K sıralı listeleri birleştirebilen, önbellekten habersiz bir sıralama algoritması olan huni sıralama algoritmasını da tartışıyor. Huni sıralama algoritması optimaldir ve yinelemeli olarak K hunisinin karekökü ile oluşturulur. Video, b-ağaçları, sıralı dosya bakımı ve öncelik sıraları gibi önbellekten habersiz başka birçok algoritma ve veri yapısı olduğunu açıklıyor. Genel olarak video, konu hakkında daha fazla bilgi edinmek isteyenler için önbellekten habersiz algoritmalara bir giriş sağlar.

• 00:00:00 Bu bölümde video, bir makinedeki önbellek boyutunu otomatik olarak ayarlayan ve önbellek parametreleri hakkında herhangi bir bilgi sahibi olmaya ihtiyaç duymadan iyi bir önbellek verimliliği sağlayan bir algoritma olan önbellekten habersiz algoritmaları tartışıyor. makine. Video, bilimsel hesaplamanın fiziksel süreçleri tanımlamak için genellikle diferansiyel denklemlere nasıl dayandığını ve ardından süreci simüle etmek için verimli kod yazması gerektiğini göstermek için diferansiyel denklemler yoluyla ısı difüzyonunu simüle etme örneğini kullanır. Video, 1B ısı denklemini simüle etmek için sonlu fark yaklaşımı yöntemine dayalı kodun nasıl yazılacağını gösterir.
  
  
• 00:05:00 Bu bölümde konuşmacı, şablon yöntemini kullanarak sonlu fark yaklaşımına izin veren bir simülasyon denklemi için kodun nasıl yazılacağını ele alıyor. Denklem U'nun T ve X'e göre kısmi türevlerini kullanır ve konuşmacı bu kısmi türevlerin yaklaşık yöntemler kullanılarak nasıl elde edileceğini gösterir. 2B alan, sırasıyla yatay ve dikey olarak temsil edilen X ve T değerlerine sahip bir matris kullanılarak temsil edilir. Konuşmacı matrisin sınırlarını açıklar ve denklemi kullanarak U'yu hesaplar.
  
  
• 00:10:00 Bu bölümde sunum yapan kişi, bilimsel hesaplamada çeşitli amaçlar için yaygın olarak kullanılan bir yöntem olan şablon hesaplamalarını açıklamaktadır. Bu yöntemde, bir dizideki her nokta şablon adı verilen sabit bir model kullanılarak güncellenir. Hesaplama, diğer üç değere bağlıdır ve bu, üç noktalı duruş olarak bilinir. Şablon hesaplamaları büyük X değerleri için kullanılabilse de, önbelleğe almayla ilgili performans düşebilir ve önbellek kayıplarıyla sonuçlanabilir. Ayrıca, nokta değerlerini güncellemek için mevcut ve önceki satırlar olmak üzere yalnızca iki satırın saklanmasıyla verileri depolamak için gereken depolama alanı azaltılabilir.
  
  
• 00:15:00 çalışır: her zaman adımında, yalnızca belirli bir satır için X değerlerini bir önceki satırdaki değerleri kullanarak güncelliyoruz. Böylece, hangi satırı güncellediğimizi ve hangi satırı önceki satır olarak kullandığımızı değiştirebiliriz ve yalnızca fazladan bir değer satırı tutmamız gerekir. Bununla birlikte, bu kod önbellek açısından çok verimli değildir ve döşeme veya önbellekten habersiz algoritmalar kullanarak onu daha verimli hale getirebiliriz. İdeal önbellek modeli, optimal veya LRU değiştirme ilkesiyle tamamen ilişkilendirilebilir bir önbelleği varsayar ve bir seri yürütmede kapasite eksikliklerini yakalar ancak çakışma kayıplarını yakalamaz. Bununla birlikte, zamansal ve uzamsal yerellikten yararlanan verimli algoritmalar tasarlamak için hala yararlıdır.
  
  
• 00:20:00 Bu bölümde konuşmacı, önbellekten habersiz bir algoritmanın, bir 2D matristeki yamuk uzay içindeki noktaları, bunun dışına bakmadan hesaplamak için nasıl kullanılabileceğini açıklıyor. Hesaplama, UT modunun bir işaretçisini X'e götüren ve 0'ın W'si artı alfa çarpı W'nin negatif 1 eksi 2 çarpı 0'ın W'si artı 1'in W'sini döndüren bir çekirdek işlevini içerir. Önbelleğe alma davranışı, LRU değiştirme ilkesi varsayılarak analiz edilir ve önbellek kayıplarının sayısı, her satır için NT bölü B'nin Theta'sıdır. Ancak konuşmacı, döşeme ile daha iyi bir performans elde edilebileceğini belirtiyor, ancak önbellekten habersiz sürümü tartışmaya devam ediyorlar. Yamuk, T1'de bir üst tabana ve T0'da bir alt tabana sahiptir. Algoritma, yamuk içindeki tüm noktaları, T, t0, t1, X, x0, x1, DX0, DX1'i içeren eşitsizlik koşullarını kullanarak hesaplar; burada DX0 ve DX1, eğimleri temsil eden -1, 0 veya 1'dir.
  
  
• 00:25:00 Bu bölümde, konuşmacı yamuk kuralı algoritması için bir böl ve fethet yaklaşımını anlatıyor. Yaklaşım, yamuğun yüksekliğinin 1 olduğu ve bir döngünün tüm değerleri hesaplama sırasına göre hesapladığı bir temel duruma sahiptir. Algoritma, sırasıyla yamuğun genişliğine ve yüksekliğine bağlı olan boşluk kesmesi ve zaman kesmesi olmak üzere iki özyinelemeli duruma sahiptir. Yamuk çok geniş olduğunda, yamuğun merkezinden geçen bir negatif eğimli bir çizgi ile yamuğun dikey olarak kesildiği bir boşluk kesimi uygulanır. Buna karşılık, yamuk çok uzun olduğunda bir zaman kesimi uygulanır ve merkezden geçen yatay bir çizgi ile kesilir. Özyinelemeli algoritma, noktalar arasındaki karşılıklı bağımlılığı önlemek için sırasıyla yamuk sol ve sağ taraflarını ve alt ve üst taraflarını belirli bir sırada geçen iki çağrı yapar.
  
  
• 00:30:00 Bu bölümde konuşmacı, önbellekten habersiz algoritmaların önbellek karmaşıklığını tartışıyor. Özyineleme ağacı yaklaşımını analiz ederler ve algoritmanın, HW noktalarının tetasını temsil eden temel duruma ulaşana kadar kendisini her seviyede iki alt probleme ayırdığını bulurlar; burada H, Theta of W'dir. Yaprak başına önbellek kayıp sayısı teta W'dur B bölü ve yaprak sayısı NT bölü HW'nin Theta'sıdır. Dahili düğümler, önbellek karmaşıklığına önemli ölçüde katkıda bulunmaz. Önbellek karmaşıklığı birden fazla boyuta genelleşir ve d bir ise, NT over MB ile sonuçlanır.
  
  
• 00:35:00 Bu bölümde konuşmacı, M'nin önbellek satırlarının sayısı olduğu bir M faktörünü kaydederek çok daha iyi önbellek karmaşıklığına sahip olan döngü kodu ile yamuk kodu arasındaki farkı açıklar. Simülasyon, yamuk kodun döngü koduna kıyasla daha az önbellek hatasına neden olduğunu ve böylece hesaplamayı çok daha hızlı tamamladığını gösteriyor. Ancak konuşmacı, bu simülasyonun yalnızca bir boyut için olduğunu belirtiyor ve iki boyutta neler olduğuna dair bir demo göstermeye devam ediyor.
  
  
• 00:40:00 Bu bölümde sunum yapan kişi, ekrandaki renklerin sıcaklıklara karşılık geldiği 2 boyutlu bir alanda gerçek zamanlı bir ısı difüzyonu simülasyonu gösterir. Sunum yapan kişi, döngü kodu ile yamuk kodunun performansını karşılaştırır ve yamuk kodun çok daha az önbellek hatasına neden olmasına rağmen, döngü kodundan çok az daha hızlı olduğunu ortaya çıkarır. Bunun, erişim modeli düzenli ve tahmin edilmesi kolay olduğundan, döngü koduna yardımcı olan donanım ön yüklemesinden kaynaklanabileceği öne sürülür.
  
  
• 00:45:00 Bu bölümde konuşmacı, önbelleğe alma ve paralellik arasındaki etkileşimi tartışıyor. Seri yürütmede önbellek kayıplarını en aza indirmenin, düşük açıklıklı bir algoritma varsayarak paralel yürütmede bunları esasen en aza indirebileceğini belirten bir teoremi açıklarlar. Daha sonra, yamuk algoritmasının, iki bağımsız yamuğun paralel olarak çalıştığı ve ardından gri yamuğun çalıştığı bir V kesimi kullanarak paralel olarak nasıl çalışabileceğini gösterirler. Ayrıca ters yamuklar için kullanılan baş aşağı V kesiminden de bahsediyorlar.
  
  
• 00:50:00 Bu bölümde, konuşmacı paralel döngü kodunun ve paralel yamuk kodunun performansını seri eşdeğerlerine kıyasla tartışıyor. Paralel döngü kodu, yamuk kodundan daha fazla potansiyel paralelliğe sahip olmasına rağmen, potansiyel hızlanmanın yarısından daha azına ulaşır. Bunun nedeni, paralel durumda, bol miktarda bellek bant genişliğinin olduğu seri durumla karşılaştırıldığında, önceden getirmenin paralel döngü koduna yardımcı olmasını önleyen bir bellek bant genişliği darboğazının olmasıdır. Buna karşılık, yamuk kod, doğrusala yakın hızlanma sağlar; bu, önbelleğin giriş boyutuna kıyasla çok küçük olduğu daha büyük girdi boyutlarında önbellek verimliliğinin çok daha büyük bir rol oynamasıyla tutarlıdır.
  
  
• 00:55:00 Bu bölümde, konuşmacı bir paralel hızlanma darboğazının nasıl teşhis edileceğini tartışır ve yetersiz paralellik, zamanlama yükü, bellek bant genişliği eksikliği ve çekişme gibi buna neden olabilecek birkaç şeyi tanımlar. Koddaki paralelliği ölçmek için İpek Ölçeği kullanmak ve bellek bant genişliğini ölçmek için donanım sayaçları yapmak da dahil olmak üzere, bu sorunları teşhis etmek için birkaç yol önerirler. Bununla birlikte, çekişmeyi teşhis etmek özellikle zordur ve konuşmacı, sorunun çekişme olup olmadığını değerlendirmeden önce ilk üç potansiyel nedene bakılmasını önerir. Son olarak, konuşmacı kalıp hesaplamasını tartışmak için devam eder.
  
  
• 01:00:00 Bu bölümde, konuşmacı önce iki sıralanmış giriş dizisini birleştirmenin karmaşıklığını analiz ederek birleştirme sıralamasının önbellek karmaşıklığını analiz etmeyi tartışıyor. Bunu yapma süresi, giriş dizilerinin boyutlarının toplamı ile orantılıdır. n öğeyi birleştirirken oluşan önbellek kayıplarının sayısı teta n bölü B'dir; burada B, bir önbellek satırındaki bayt sayısıdır. Merge sort, yarı boyuttaki girişlerde iki yinelemeli çağrıya sahiptir ve yinelemeli aramalarının sıralanmış çıktılarını birleştirir. Birleştirme sıralamasının genel çalışması, özyineleme ağacı yöntemi kullanılarak analiz edilen n log n'nin tetasıdır. Birleştirme sıralamasının önbellek karmaşıklığı da tartışılır ve önbellek kayıplarının sayısının, verileri depolamak için gereken önbellek bloklarının sayısıyla orantılı olduğu gösterilir; bu, teta n bölü B log M'dir; alt blok olabilir.
  
  
• 01:05:00 Bu bölümde, konuşmacı birleştirme sıralamasının önbellek karmaşıklığının tekrarını açıklıyor. Temel durum, problem boyutu önbelleğe sığdığında ve Θ(n/B) önbellek kayıplarının meydana gelmesiyle oluşur. Aksi takdirde, algoritmanın sonuçları birleştirmek için n/2 boyutunda ve Θ(n/B) önbellek kayıplı iki özyinelemeli çağrısı vardır. Analiz, CM'nin bir sabit olduğu n/CM'nin log tabanı 2 olan bir özyineleme ağacının düzey sayısını içerir. Yaprak başına önbellek kayıplarının sayısı Θ(M/B * n/CM)'dir ve ilk terimde bir B faktörü tasarruf ederek Θ(n/B * log (n/CM)) toplam önbellek kayıp sayısını verir. . Bununla birlikte, daha büyük problem boyutları için, işe kıyasla yalnızca B faktörünü kaydederken, küçük problem boyutları için B log n faktörünü tasarruf ederiz. Konuşmacı daha iyi bir çözüm olup olmadığını sorar ve cevap her zaman evettir.
  
  
• 01:10:00 Bu bölümde, konuşmacı sıralanmış alt dizileri birleştirmek için çok yollu birleştirmenin nasıl kullanılacağını açıklıyor ve alt dizilerin minimum öğelerini belirlemek için bir turnuva ağacı fikrini tanıtıyor. Sıralama için önbellekten habersiz algoritmalarda kullanılan bu yaklaşımın iş ve önbellek karmaşıklıklarını da açıklarlar. Çok yollu birleştirmenin iş karmaşıklığı, ikili birleştirme sıralamasıyla aynıdır, önbellek karmaşıklığı ise turnuva ağacını doldurmak ve giriş dizilerine erişmek için gereken önbellek kayıplarının sayısı tarafından belirlenir; bu, R daha küçükse optimize edilebilir. Küçük bir C sabiti için C*M/B.
  
  
• 01:15:00 Bu bölümde konuşmacı, çok yönlü birleştirme sıralama algoritmasının önbellek karmaşıklığını tartışır ve ikili birleştirme sıralama algoritmasıyla karşılaştırır. Çok yollu birleştirme sıralama algoritması, sorunu n/R boyutunda alt problemlere bölmeyi ve bunları birleştirmek için n/B önbellek kayıplarını ödemeyi içerir. Özyineleme ağacının düzey sayısı, n/cm log tabanı R'dir ve yaprak boyutu cm'dir. Konuşmacı, R'yi M/B'nin tetasına eşitleyerek mümkün olduğu kadar büyük yapar ve teta n log n bölü B log M olduğu ortaya çıkan önbellek karmaşıklığını analiz eder. İkili birleştirme sıralama algoritmasıyla karşılaştırıldığında, çoklu -way birleştirme sıralama algoritması, önbellek kayıplarında bir günlük M faktörü kaydeder. Bununla birlikte, algoritma önbellekten habersiz değildir ve R'nin değerinin belirli bir makine için ayarlanması gerekir; bu, önbellek için rekabet eden diğer işler çalışıyorsa sorun olabilir.
  
  
• 01:20:00 Bu bölümde konuşmacı, K kareli öğeleri ve K sıralı listeleri birleştirebilen, önbellekten habersiz bir sıralama algoritması olan huni sıralama algoritmasını tartışıyor. Bu birleştirmenin maliyetinin çok yollu birleştirme sıralama algoritmasıyla aynı olduğu gösterilmiştir, ancak huni sıralama algoritması önbellekten habersizdir ve sınırı optimaldir. Konuşmacı, bir K hunisinin neye benzediğinin bir resmini sunar ve algoritmanın, öğeleri arabelleklere besleyen K hunilerinin karekökü ile yinelemeli olarak oluşturulduğunu açıklar; K hunisi için çıktı. Konuşmacı ayrıca b-ağaçları, sıralı dosya bakımı ve öncelik kuyrukları gibi önbellekten habersiz başka birçok algoritma ve veri yapısı olduğundan bahseder ve izleyicileri bunlar hakkında çevrimiçi daha fazla bilgi edinmeye davet eder.

[MetaQuotes]

Ders 16. Belirleyici Olmayan Paralel Programlama

Ders 16. Belirleyici Olmayan Paralel Programlama

Bu video, deterministik ve deterministik olmayan paralel programlama ile ilgili çeşitli kavramları tartışmaktadır. Konuşmacı, anormal davranışlara ve zor hata ayıklamaya yol açabileceğinden, determinizmden kaçınmanın önemini vurgular. Determinizmi yönetme stratejileri arasında sabit değerler, kayıt tekrarı, analiz araçları, kapsülleme ve birim testi yer alır. Mutekslerin kullanımı, dönmeye karşı verim, girene karşı girmeyen ve adile karşı adil olmayan dahil olmak üzere ayrıntılı olarak araştırılır. Konuşmacı ayrıca paralel programlama bağlamında bağlam değiştirme kavramına ve "kayak kiralama sorununa" değiniyor. Bölüm, çok çekirdekli işlemcilerde performans mühendisliğinin temel ilkelerini tartışarak sona eriyor.

Videonun ikinci kısmı, paralel programlamadaki kilitlenme sorununu ele alıyor ve bunu önlemek için, bekleme döngüsü olmamasını garanti eden mutekslerin doğrusal sıralaması gibi çözümler sunuyor. Ek olarak, konuşmacı kritik bir bölgeyi tüm güncellemeleri aynı anda yapan bir işlem olarak temsil ederek atomikliği sağlayan işlemsel bellek kavramını tanıtıyor. Ardından video, küresel bir kilide ihtiyaç duymadan kilitlenmeleri ve açlığı önlemek için sonlu bir sahiplik dizisine sahip kilit tabanlı bir yaklaşım ve bir yayın sıralaması gerektiren yöntem kullanan bir algoritma sunar. Son olarak, birden çok kilidin aynı anda bir kilit edinmeye çalışmasını önleyen ve performans sorunlarını önleyen algoritma yayın sıralama ve yeniden alma açıklanmaktadır.

• 00:00:00 Bu bölümde öğretim görevlisi, programlamada determinizm kavramını ve bunun paralel hesaplama ile nasıl ilişkili olduğunu tanıtıyor. Bir program, her yürütmede her bellek konumu aynı değer dizisiyle güncelleniyorsa ve program her zaman aynı şekilde davranıyorsa deterministiktir. Deterministik programlar, tekrarlanabilir olma avantajına sahiptir ve hata ayıklamalarını kolaylaştırır. Öğretim görevlisi, hata ayıklaması zor olan anormal davranışlar sergileyebileceklerinden, asla deterministik olmayan paralel programlar yazmamanın önemini vurgular. Bununla birlikte, pratikte, paralel hesaplamada determinizmden kaçınmak zor olabilir.
  
  
• 00:05:00 Bu bölümde konuşmacı, deterministik olmayan paralel programlamayı ve bunun bazen daha iyi performansa yol açabileceğini, ancak yine de gerekmedikçe kaçınılması gerektiğini tartışıyor. Konuşmacı, bu şekilde bir program yazmanız gerekiyorsa, belirlenemezliği yönetmek için bir test stratejisi tasarlamanızı önerir. Belirlenimsizliğin kapatılması, rasgele sayılar için aynı çekirdeğin kullanılması veya aksi takdirde rasgele değişebilecek program girdileri için sabit değerler sağlanması strateji örnekleri arasında yer alır. Konuşmacı, programda determinizmin neden olduğu hataları ele almanın bir yolunun olmasının önemini vurguluyor.
  
  
• 00:10:00 Bu bölümde konuşmacı, deterministik olmayan programlamayla başa çıkmak için kayıt tekrarı, determinizmsizliği kapsülleme, deterministik bir alternatifi ikame etme, analiz araçlarını kullanma ve birim testi gibi stratejilerden bahsediyor. Konuşmacı, koddaki hataları yakalama şansını artırmak için belirlenemezliği kontrol etmenin önemini vurguluyor. Konuşmacı ayrıca, deterministik olmayan programlamanın nasıl ele alınacağını göstermek için bir hash tablosunda karşılıklı dışlama ve atomikliğin kullanımına ilişkin bir örnek sağlar.
  
  
• 00:15:00 Bu bölümde, konuşmacı aynı konuma erişen paralel talimatların nasıl yarış hatalarına yol açabileceğini ve sistemin bütünlüğünü bozabileceğini tartışıyor. Standart çözüm, bazı talimatları atomik hale getirmektir, yani sistemin geri kalanı tarafından tamamen yürütülmüş veya hiç yürütülmemiş olarak görülürler. Bunu başarmak için, kilitleme ve kilit açma üye işlevlerine sahip bir nesne olan karşılıklı dışlama kilidi veya muteks kilidi kullanılır. Her yuva, bir muteks kilidi ve yuva bağlamına bir işaretçi kafası olan bir yapıya dönüştürülür, bu da listeye erişmeden önce kilitleme ve kilit açma işlevlerinin kullanılmasına izin verir, böylece sistemin doğruluğu sağlanır.
  
  
• 00:20:00 Bu bölümde video, atomikliği uygulamak için mutekslerin kullanımını ve bunun belirlilik yarışlarıyla nasıl bir ilişkisi olduğunu araştırıyor. Mutex kilitleri, kritik bölümlerin atomik olmasını sağlayabilir, ancak elde edilen kod, bazı durumlarda istenebilecek bir belirlilik yarışı nedeniyle deterministik değildir. Video, veri yarışları ile kararlılık yarışları arasındaki farkı anlamanın önemini vurguluyor ve veri yarışlarını basitçe ortadan kaldırmanın, kodda hiçbir hata olmadığı anlamına gelmediğini belirtiyor. Kodda yanlış pozitifleri veya eksik yarış hatalarını önlemek için belirlenemezliği tespit etmenin bir yolunun olması önemlidir.
  
  
• 00:25:00 Bu bölümde konuşmacı, veri yarışı olmamasının kodda hiç hata olmadığı anlamına gelmediğini açıklıyor. Hiçbir veri yarışı kodun olumlu yönleri olmasa da, atomiklik sağlamak için kilitleme örneği atomiklik ihlaline yol açabilir. Ayrıca, iki paralel işlemin aynı değere erişmesi gibi iyi huylu yarışlar meydana gelebilir, bu da aynı sonuca yol açabilir, ancak bazı mimarilerde yanlış değerlere de yol açabilir. Konuşmacı, bazı insanlar iyi huylu ırkları zararsız olarak görse de, onları tanımlamanın ve bunlardan kaçınmanın hala gerekli olduğunu savunuyor.
  
  
• 00:30:00 Bu bölümde, konuşmacı, özellikle birden fazla işlem aynı konumda değer ayarlamaya çalıştığında meydana gelebilecek yarış koşullarından kaynaklanan, deterministik olmayan programlamanın tehlikelerini açıklıyor. Konuşmacı, kasıtlı yarışlara izin veren ancak doğru kullanılmadığı takdirde tehlikeli olabilen "İpek" kavramını tanıtıyor. Yarışların karmaşıklığı, hata ayıklamayı zorlaştırabilir ve doğru kodu algılamaya yardımcı olmayı amaçlayan araçları karıştırabilir. Konuşmacı ayrıca, mutekslerin ve parametrelerinin uygulanmasının, verim verme veya dönme gibi davranışlarını nasıl etkileyebileceğini de tartışır.
  
  
• 00:35:00 Bu bölümde, video paralel programlamadaki mutekslerin üç temel özelliğini açıklıyor: dönene karşı verim veren, tekrar girene karşı tekrar girmeyen ve adile karşı adil olmayan. Döndürme ve verim verme kavramı, bir iş parçacığının boşta durmayacağı ve sürekli olarak bir kilide erişimi kontrol etmeyeceği, bunun yerine daha verimli bir yürütme için işletim sistemine kontrol vereceği fikridir. Yeniden giren muteks, zaten bir kilidi tutan bir iş parçacığının onu tekrar almasına izin verirken, yeniden giriş yapmayan kilitler, iş parçacığı zaten sahip olduğu bir muteksi yeniden almaya çalışırsa kilitlenir. Son olarak, adil mutex, kilitlenmeyi en uzun süre bekleyen thread'in önce kilitlenmesini sağlayarak açlık sorununun önüne geçer. Video ayrıca, montaj dilinde basit bir dönen muteksin uygulanmasını sağlar.
  
  
• 00:40:00 Bu bölümde video, paralel programlamada muteks kullanımını ve neden sadece muteks almak yerine exchange komutunun kullanıldığını tartışıyor. Takas işleminin bir hakka benzediği ve bir hakkın ifa edilebilmesi için üzerinde bulunduğu kasanın diğer kasalar üzerinde hükümsüz kılınması ve değiştirilmiş veya münhasır durumda tutulması gerektiği anlatılmaktadır. Bu, bellek ağında trafik oluşturur ve işlemi yavaşlatır. Öte yandan, değişim talimatı kullanılarak, önbellek satırları paylaşımlı duruma getirilir, böylece süreç daha hızlı tutulur ve daha az trafik üretilir.
  
  
• 00:45:00 Bu bölümde, konuşmacı dönen bir muteks ile veren bir muteks arasındaki farkı tartışıyor. Dönen bir mutekste, program kilidi açılacak muteksin olup olmadığını kontrol etmeye devam ederken, verimli bir mutekste, program kontrolü işletim sistemine verir ve bu da onun başka bir şey programlamasına izin verir. Konuşmacı, rekabetçi muteks adı verilen ve hem dönen bir muteks hem de verimli bir muteks amacına ulaşan başka bir muteks türü olduğunu not eder. Konuşmacı ayrıca, bekleyen dizileri bilgilendirmek için mesaj iletmeyi veya kesintileri kullanmayı araştırıyor, ancak daha basit çözümün karşılıklı dışlama mekanizması kullanmak olacağını belirtiyor.
  
  
• 00:50:00 Bu bölümde, konuşmacı, işletim sisteminin mevcut işlemcilerdeki iş parçacıkları arasında ne sıklıkta geçiş yaptığı olan bağlam değiştirme kavramını açıklamaktadır. Tipik olarak, sistem saniyede yaklaşık 100 kez içerik değiştirme yapar, yani her bir geçiş yaklaşık 10 milisaniye sürer. Bununla birlikte, bu, basit bir talimatın yürütme süresinden daha büyük bir mertebeden daha fazladır, yani iş parçacığı geri gelip bir kilit alma şansına sahip olmadan önce yürütülebilecek birçok talimat vardır. Bu sorun, eğirme ve akma kombinasyonu kullanılarak çözülebilir. Konuşmacı bunu Teori literatüründe "kayak kiralama sorunu" olarak adlandırıyor.
  
  
• 00:55:00 Bu bölümde video, spor ekipmanı satın alma veya kiralama örneğini kullanarak belirli bir görev için ekipman satın alma veya kiralama kararı verme sürecini tartışıyor. Konuşmacı, izleyicileri kiralamaya karşı satın alma maliyetlerini düşünmeye teşvik eder ve maliyet satın alma maliyetine eşit olana kadar kiralamayı ve ardından satın almayı önerir. Video aynı zamanda bağlam değiştirme süresi kavramını, disk erişim süresini ve aynı anda birden çok kilidi tutarken kilitlenme sorununu da araştırıyor. Genel olarak, bu bölüm, çok çekirdekli işlemcilerde performans mühendisliğinin temel ilkelerini kapsar.
  
  
• 01:00:00 Bu bölümde konuşmacı, iki iş parçacığının her ikisinin de diğer iş parçacığı tarafından gerekli olan kaynakları tutması ve performans kaybına neden olması durumu olan kilitlenmeyi açıklıyor. Kilitlenme için üç temel koşul vardır: karşılıklı dışlama (kaynaklar üzerinde münhasır denetim), önlememe (bitene kadar tutulan kaynaklar) ve döngüsel bekleme (bir sonraki tarafından tutulan kaynakları bekleyen iş parçacıkları döngüsü). Bu kısıtlamalardan herhangi birinin kaldırılması, kilitlenme sorununu çözebilir. Konuşmacı, kilitlenme sorununu göstermek için Tony Hoare tarafından Edsger Dijkstra'nın bir sınav sorusuna dayanan bir hikaye olan "Yemek Felsefecileri"ni kullanıyor. Hikaye, bir masanın etrafında oturan filozofların, her bir erişte tabağının iki yemek çubuğunun arasına yerleştirildiği yemek çubuklarıyla erişte yemesini ve erişteleri yemek için iki yemek çubuğuna ihtiyaç duymalarını içerir. Filozoflar eriştelerini yemek için soldaki ve sağdaki çubukları kaparlar. Ancak, hepsi soldaki yemek çubuğunu kaldırırsa, sonunda açlıktan ölürler.
  
  
• 01:05:00 Bu bölümde, konuşmacı paralel programlamada kilitlenme konusunu tartışır ve kilitlenmeden kaçınırken önleme dışılığı garanti eden bir çözüm sunar: mutekslerin doğrusal sıralaması. Programcılar, her muteksi numaralandırarak ve sayısal sıralarına göre stratejik olarak kilitleyerek, bir bekleme döngüsünün (kilitlenme için gerekli koşul) oluşamayacağını garanti edebilir. Bununla birlikte, programcıları, çalışma zamanı sisteminin kilitleri Silk'te kapsüllemesinin farkında olmaları konusunda uyarıyor, çünkü bu kilitler aracılığıyla ek belirlenimsizlik getirmek sorunlara yol açabilir. Paralel programlar tasarlarken dikkatli düşünmenin önemini vurgulayarak, tek bir kilitle kilitlenmenin oluşabileceği bir örneği paylaşıyor.
  
  
• 01:10:00 Bu bölümde, konuşmacı işlemsel bellek konusuna giriyor; bu, kilitleri belirtmeye gerek kalmadan atomikliğin dolaylı olarak gerçekleştiği veritabanı işlemlerine sahip olmayı içeren araştırma düzeyinde yeni bir teknik. Konuşmacı, işlemsel belleğin eşzamanlı grafik hesaplamada nasıl yararlı olduğuna dair bir örnek veriyor, yani iki düğümün aynı anda ortadan kaldırılmasının atomiklik ihlallerine neden olduğu Gauss eleme. İşlemsel belleğin arkasındaki fikir, kritik bölgeyi bir işlem olarak temsil etmektir ve taahhütte bulunulduktan sonra, kritik bölgedeki tüm bellek güncellemeleri aynı anda gerçekleşmiş gibi görünür.
  
  
• 01:15:00 Bu bölümde konuşmacı, işlemsel bellekte çakışma çözümü, çekişme çözümü, ileriye doğru ilerleme ve verimlilik konularını tartışır. Küresel bir kilide ihtiyaç duymadan kilitlenmeleri ve açlığı önlemek için sonlu bir sahiplik dizisine sahip kilit tabanlı bir yaklaşım ve bir yayın sıralaması gerektiren yöntem kullanan bir algoritma sunarlar. Algoritma, bir işlem iptal edildiğinde geri alma veya atomik işleme izin vermek için okur ve yazar. Kilit dizisi, bir sağlama işlevinin eşlendiği bir konumu kilitlemek için kullanılır ve kilitlerin adil bir şekilde alınmasına olanak tanır. Bu algoritma, performanstan ödün vermeden veya kilitlenmelere neden olmadan eşzamanlı işlemlere izin verir.
  
  
• 01:20:00 Bu bölümde, konuşmacı yayın sıralama ve yeniden alma adlı bir algoritmayı tartışıyor. Algoritma, açgözlülükle bir bellek konumunun kilidini almaya çalışarak çalışır ve bir çakışma ortaya çıkarsa, işlem, tuttuğu kilitleri serbest bırakmadan geri döner. Daha sonra algoritma, erişmeye çalıştığı konumun indeksinden daha büyük indekslere sahip tüm kilitleri serbest bırakır. Daha sonra istenen kilidi alır ve son olarak serbest bırakılan kilitleri sıralı bir sırayla alır. Bu işlem, işlem başarılı olana kadar tekrarlanır. Algoritma, birden fazla kilidin aynı anda bir kilit almaya çalışmasını engelleyecek şekilde tasarlanmıştır, bu da performans sorunlarına neden olabilir.

[MetaQuotes]

Ders 17. Kilitsiz Senkronizasyon

Ders 17. Kilitsiz Senkronizasyon

Charles Leiserson, bir YouTube videosunda kilitsiz senkronizasyon kavramını araştırıyor. Sıralı yürütmeyi sağlamak için küresel bir doğrusal talimat düzenine duyulan ihtiyacı gösteren bir örnek sağlar ve kilit kullanmanın zorluklarından ve potansiyel sorunlarından kaçınarak sıralı tutarlılık yoluyla karşılıklı dışlamanın nasıl elde edilebileceğini tartışır. Leiserson, Peterson'ın algoritmasını, eşzamanlı süreçlerin müdahalesi olmadan kritik bölümlere erişmek için yalnızca yükleme ve depolama işlemlerini kullanan bir çözüm olarak sunar. Video ayrıca, donanımın yeniden sıralanması nedeniyle bellek yoluyla senkronizasyonun zorluklarını ve diğer talimatlarla göreli sıralamayı sürdürmek için bellek çitleri kavramını kapsar. Leiserson, paralel makineler için sıralı tutarlılığı desteklemenin donanım tasarımcıları için yararlı olduğunu ancak elde etmenin zor olduğunu savunuyor.

Videonun ikinci bölümünde, paralel programlarda hataların önlenmesinde bellek parmaklıklarının ve senkronizasyon talimatlarının kullanımı anlatılmaktadır. Konuşmacı, bellek çitlerini örtülü veya açık bir şekilde uygulamanın farklı yollarını ve bir işlemcinin farklı yönleri üzerinde çalışan farklı ekipler arasında dikkatli mühendislik ve koordinasyonun önemini araştırıyor. Ayrıca öğretim görevlisi, yalnızca sabit alan kullanarak n-thread kilitlenmeden bağımsız karşılıklı dışlama algoritmalarının mutekslerini uygulamak için C11 dil standardındaki kilitsiz algoritmanın bir parçası olarak CAS talimatlarının kullanımını tartışır. Charles Leiserson, çok iş parçacıklı bir sistemde kilit kullanma sorununu ve bunun yerine CAS kullanmanın çözümünü açıklıyor, çünkü kilide uzun süre tutunan bir iş parçacığı potansiyel olarak aynı kaynağa erişmeyi bekleyen diğer iş parçacıklarını engelleyebilir. Ek olarak video, karşılaştır ve değiştir ile ilgili potansiyel ABA sorununu vurgular ve konuyla ilgilenenleri kilitsiz algoritmalar hakkında daha fazla bilgi edinmeye teşvik eder.

• 00:00:00 ve talimatları, tüm talimatların küresel bir doğrusal düzenini oluşturmak için serpiştirilir. Teorik açıdan en önemli bellek modeli olan sıralı tutarlılık bellek modelinin arkasındaki fikir budur. Bellek modellerini anlamak önemlidir çünkü kilitlerin olmadığı durumlarda paralel programların davranışı bellek modeline bağlıdır. Derste sunulan bir örnek, kullanılan bellek modeline bağlı olarak kodlarını paralel olarak yürüttükten sonra iki işlemcinin her ikisinin de 0 değerine sahip olmasının mümkün olup olmadığını sorarak bu noktayı açıklar.
  
  
• 00:05:00 Bu bölümde Charles Leiserson, yürütmenin sıralı olması için yüklerin ve depoların bazı küresel doğrusal düzene uyması gerektiği durumlarda kilitsiz senkronizasyon kavramını tartışıyor. Oluşabilecek farklı yürütme yollarını ve donanımın her istediğini nasıl yapabileceğini göstermek için çeşitli değerleri serpiştirme örneğini kullanır. Ayrıca, değerleri serpiştirmenin birçok farklı yolu olsa da, yürütmenin tutarlı olması için yükler ve depolar doğrusal bir sıra izliyormuş gibi görünmesi gerektiğini açıklıyor. Nihayetinde Leiserson, her iki değerin de sıfır olmasıyla biten hiçbir yürütme olmadığı sonucuna varır ve modern bilgisayarların hiçbirinin sıralı tutarlılık sağlamadığını not etmek ilginçtir.
  
  
• 00:10:00 Bu bölümde, komutlar ve sıraları arasındaki ilişkinin, sağ ok bağlantısı, işlemci sırası ve komutların sıralanması arasındaki doğrusal ilişkinin anlaşılmasını içeren sıralı tutarlılık kavramı tartışılmaktadır. Ek olarak, karşılıklı dışlama, sıralı tutarlılık düşünülerek ve yüklerin ve depoların kullanımı aracılığıyla paylaşılan veri yapısının uygulanmasıyla, ağır hizmet yönergeleri veya kilitler kullanılmadan gerçekleştirilebilir. Ders notları, test etme ve ayarlama veya karşılaştırma ve değiştirme gibi özel işlemleri kullanan yöntemleri açıklar, ancak sunulan çözüm, kilitlenmeler veya kilitler kullanılırken ortaya çıkan diğer kötü şeyleri önler.
  
  
• 00:15:00 Bu bölümde Charles Leiserson, Peterson'ın eş zamanlı bir programda yalnızca yükleme ve depolama işlemlerini kullanarak karşılıklı dışlamayı sağlamaya yönelik algoritmasını açıklıyor. Algoritma, iki eşzamanlı sürecin, Alice ve Bob'un, bir dizi değişken ve sıra alma mekanizması kullanarak birbirlerine müdahale etmeden kod yürütmesine izin verir. Kod, aynı anda yalnızca bir işlemin kritik bir bölüme girebilmesini ve paylaşılan bir kaynağı değiştirebilmesini sağlar. Kilitlerden farklı olarak, Peterson'ın algoritması bir kilidin alınmasına veya serbest bırakılmasına dayanmaz ve bunun yerine karşılıklı dışlamayı sağlamak için yükleri ve depoları kullanır.
  
  
• 00:20:00 Bu bölümde, konuşmacı kritik bölümde kilit kullanmadan karşılıklı dışlamayı başarmak için Peterson'ın algoritmasını tartışıyor. Her seferinde yalnızca bir kişinin kritik bölüme girebileceğini ve algoritmanın, kritik bölüme girmek isteyen birinin, gitmek isteyen tek kişiyse girebilmesini sağladığını açıklıyor. Konuşmacı daha sonra, hem Alice hem de Bob'un kendilerini kritik bölümde bulduklarını varsaymayı ve bir çelişki türetmeyi içeren algoritmanın bir kanıtını sunar. Kanıt, "daha önce olur" ilişkisine ve yürütülen talimatların program sırasına dayanır.
  
  
• 00:25:00 Bu bölümde konuşmacı, kilitsiz senkronizasyon işlemini açıklar. Talimat zincirleri oluştururlar ve senkronizasyon hatalarını önlemek için bunların doğru sırada gerçekleşmesini sağlarlar. Bir gösteri olarak paylaşılan bir kaynağa erişmek isteyen Bob ve Alice örneğini kullanırlar. Senkronizasyon sırasında mühendislerin dikkatli olmaları ve doğru sırada gerçekleştiklerinden emin olmak için "olaylardan önce olanları" gözden geçirmeleri gerektiğini açıklıyorlar.
  
  
• 00:30:00 Bu bölümde, Charles Leiserson model denetimi kavramını ve bunun ağ, güvenlik ve önbellek protokollerini analiz etmede kullanımını tartışıyor. Ardından, açlıktan ölme özgürlüğünü garanti eden ancak ikiden fazla işlemle çalışmayan Peterson algoritmasının özelliklerini açıklamaya devam ediyor. Leiserson ayrıca, bellek yoluyla senkronizasyonun zorluklarını ve modern işlemcilerde rahat bellek tutarlılığına ve senkronizasyonu doğru yapmada zorluğa yol açan sıralı tutarlılık eksikliğini araştırıyor.
  
  
• 00:35:00 Yükleme gecikmesiyle ilgili sorunlara yol açmadan talimatları yeniden sıralamak güvenli mi? İkinci kısıtlama, komutlar arasında veri bağımlılığı olmadığı, yani komutların verileri paylaşmadığı veya bellekte aynı konumu kullanmadığı durumdur. Bu durumda yeniden sıralama yönergeleri, performansı artırabilir ve aşırı yük gecikmesini karşılayabilir, çünkü yük daha önce yapılabilir ve sonuç beklenirken diğer işler yapılabilir. Donanım düzeyindeki bu kavramları anlamak, yazılım hakkında akıl yürütmeye ve performansı optimize etmeye yardımcı olabilir.
  
  
• 00:40:00 Bu bölümde Charles Leiserson, senkronizasyonda kilitler olmadan yeniden sıralama kavramını açıklıyor. Eşzamanlılık olmadığı sürece, özellikle işlemci çalışırken veya talimat akışında baloncuklar olduğunda, yeniden sıralamanın güvenli olduğunu açıklıyor. Bunun nedeni, modern işlemcilerde donanımın verileri bir arabellekte depolaması ve doğrudan bellek sistemine giderek yükleri baypas etmesidir. Ancak, yüklenen şey mağazalardan biriyse, bu atlama, doğrulukla ilgili sorunlara yol açabilir.
  
  
• 00:45:00 Bu bölümde Charles Leiserson, donanımın yeniden sıralanmasının nasıl gerçekleştiğini ve neden sıralı tutarlılığı karşılamadığını ve x86'nın sıralı tutarlılıktan daha zayıf olan toplam depolama sırası adı verilen bir bellek tutarlılık modeline nasıl sahip olduğunu açıklıyor. Toplam mağaza düzenine ilişkin kurallar, yüklerle birlikte yüklerin hiçbir zaman yeniden sıralanmamasını, yüklerin harici işlemciler tarafından aynı sırada görülmesini, mağazaların hiçbir zaman mağazalarla birlikte yeniden sıralanmamasını ve yüklerin yalnızca önceki depolarla farklı bir konuma yeniden sıralanmasını, ancak önceki yüklerle yeniden sıralanmasını içerir. aynı konum. Kilit talimatları ve bellek sıralaması toplam bir düzene uyar.
  
  
• 00:50:00 Bu bölümde, konuşmacı talimatı yeniden sıralamanın nasıl sıralı tutarlılığı ihlal edebileceğini ve yanlış değerlerle sonuçlanabileceğini tartışır. Yeniden sıralama hem donanımda hem de derleyicide gerçekleşebilir ve kilitleme komutlarının diğer komutlardan önce taşınmayacağını bilmek önemlidir. Konuşmacı ayrıca, farklı bir adrese olması durumunda yüklerin mağazalardan önce gidebileceğini de belirtiyor. Yeniden sıralamanın tehlikesi, belirli yeniden sıralamalar meydana gelirse tamamen alt üst edilebilecek olan Peterson'ın algoritmasında gösterilmiştir. Bu nedenle, bellek yoluyla eşitleme yaparken bu sorunlardan kaçınmak için deterministik kod yazmak önemlidir.
  
  
• 00:55:00 Bu bölümde, Charles Leiserson, paralel ve eşzamanlı kod yazarken, bir mağazanın önünde belirli bir yükün oluşmasından kaçınmanın önemli olduğu yeniden sıralama konusunu tartışıyor. Bu tür senaryoların üstesinden gelmek için mühendisler, diğer komutlarla göreli sıralamayı koruyan, ancak artan karmaşıklık ve potansiyel hatalar pahasına bellek çitleri sunar. Leiserson ayrıca paralel makinelerin sıralı tutarlılığı desteklemesinin faydalı olduğunu, ancak bunun donanım tasarımcıları için başarılması gereken bir zorluk olduğunu savunuyor.
  
  
• 01:00:00 Bu bölümde konuşmacı, paralel programların hatalarla karşılaşmasını önlemede bellek çitlerinin ve senkronizasyon talimatlarının önemini tartışıyor. Konuşmacı, açık bir şekilde bir talimat olarak veya dolaylı olarak kilitleme ve değiş tokuş gibi diğer senkronizasyon talimatları yoluyla olduğu gibi, hafıza çitlerinin uygulanabileceği farklı yolları açıklar. Bununla birlikte, bir bellek çitinin bir programı gerçekten yavaşlatabileceği durumlar vardır; bu da, bir işlemcinin farklı yönleri üzerinde çalışan farklı ekipler arasındaki dikkatli mühendislik ve koordinasyonun önemini gösterir. Ek olarak konuşmacı, derleyicinin uzaktaki değişkenleri optimize etmesini ve paralel kodda hatalara neden olmasını önlemek için uçucu değişkenlerin ve derleyici çitlerinin kullanılmasını önerir.
  
  
• 01:05:00 Bu bölümde öğretim görevlisi, C11 dil standardında kilitsiz senkronizasyonu tartışır. Standart, kilitlenmeden bağımsız karşılıklı dışlama algoritması için bellek çiti veya atomik karşılaştırma ve takas gibi pahalı işlemlerin kullanılmasını gerektiren, nesnelerin atomik olarak bildirilmesine izin veren zayıf bir bellek modeli tanımlar. Burada, CAS talimatı (Karşılaştır ve Değiştir) kilitsiz algoritmanın bir parçası olarak incelenir. Talimat, bellekteki değerin eski değerle aynı olup olmadığını kontrol eder ve yeni değerle değiştirmeden önce tümü atomik olarak yapılır. CAS'ın kullanımı, yalnızca sabit alan kullanan n-iş parçacıklı kilitlenme içermeyen karşılıklı dışlama algoritmalarının mutekslerinin uygulanmasına izin verir. True değerini elde edene kadar dönen bir kilit talimatı, birisinin kilidi tuttuğunu belirten true ile yer değiştirmek için kullanılır.
  
  
• 01:10:00 Bu bölümde Profesör Charles Leiserson, senkronizasyon sorunlarını çözmek için karşılaştır ve değiştir (CAS)'nin nasıl kullanılacağını açıklıyor. CAS'ın kilit olarak nasıl kullanılacağını gösteriyor ve bir öğrencinin sunduğu koddaki bir hatayı düzeltiyor. Daha sonra bir dizideki değerlerin toplamını hesaplamak için kullanılan ve bir yarış durumuna yol açan yanlış bir kod sunar. Mutex kilitlerini tipik bir çözüm olarak tanıtıyor ve kilidi aldıktan sonra bir iş parçacığının değiştirilerek diğer iş parçacıklarının kilidi beklemesine ve dolayısıyla ilerlemenin engellenmesine yol açmasının olası sorununu açıklıyor.
  
  
• 01:15:00 Bu bölümde Charles Leiserson, çok iş parçacıklı bir sistemde kilit kullanma problemini ve bunun yerine CAS kullanmanın çözümünü açıklıyor. Kilitlerle, bir iş parçacığı kilidi uzun süre tutabilir ve aynı kaynağa erişmeyi bekleyen diğer iş parçacıklarını engelleyebilir. Bununla birlikte, CAS ile, eski sonucu depolamak için eski ve yeni değişkenlere sahipken bir geçici hesaplandıktan sonra x yükünün ardından x deposu gelir ve yeni bir değer üretmek için geçici sonucu eski değere ekler. eski değer değişmediyse değiştirilir. Charles ayrıca karşılaştır ve değiştir ile ilgili ABA sorunundan bahsediyor ve konuyla ilgilenenleri kilitsiz algoritmalar hakkında daha fazla bilgi edinmeye teşvik ediyor.

[MetaQuotes]

Ders 18. Etki Alanına Özgü Diller ve Otomatik Ayarlama

Ders 18. Etki Alanına Özgü Diller ve Otomatik Ayarlama

Bu videoda, MIT'deki EECS bölümünden Profesör Saman Amarasignhe, performans mühendisliğinde etki alanına özgü dilleri (DSL'ler) kullanmanın ve otomatik ayarlamanın faydalarını tartışıyor. Genel amaçlı dillerde tanımlanması zor olan alana özgü alanları yakalayan ve programcıların daha iyi performans için alan uzmanlarının bilgisinden yararlanmalarına olanak tanıyan DSL'lerin önemini vurguluyor. Singh, grafik bölümleme ve hesaplamada grafiğin şeklinin önemi dahil olmak üzere DSL'leri kullanarak grafik işlemlerinin optimizasyonunu tartışıyor. Görüntü işleme için hızlı kod optimizasyonu ve makineler arasında taşınabilirlik sağlayan DSL Halide'yi tanıtıyor. Halide'nin Google ve Adobe gibi çeşitli sektörlerde kullanımını tartışıyor. Son olarak, paralellik, yerellik ve gereksiz çalışmaya odaklanırken kodu optimize etmede farklı yaklaşımlarla deneme yapmanın önemini vurguluyor.

Video ayrıca performans mühendisliğinin zorluklarından ve bir programın verimli çalışması için en uygun parametreleri bulmadan bahsediyor. Konuşmacı, otomatik ayarlamanın, optimum değerleri bulmak için geniş parametre alanını otomatik olarak arayarak bu sorunu çözebileceğini öne sürüyor. Kapsamlı aramanın pratik olmayabileceğini ve buluşsal tabanlı çözümlerin optimal olmayabileceğini belirtiyor. Kabul edilebilir değerler alanı tanımlayan ve performans sonuçlarına göre yinelenen otomatik ayarlama, en uygun çözümleri bulma sürecini hızlandırabilir. Konuşmacı ayrıca, kapsamlı aramadan daha verimli ve etkili programlar üretebilen Try için programların oluşturulmasında otomatik ayarlamanın uygulanmasını tartışıyor.

• 00:00:00 Bu bölümde, MIT'de EECS bölümünde profesör olan Profesör Saman Amarasignhe, alana özgü diller ve otomatik ayarlama hakkında konuşuyor. Bu dillerin, genel amaçlı bir dilde tanımlanması zor olan belirli alana özgü alanları yakaladıkları için mühendislik faydaları olduğunu açıklıyor. Etki alanına özgü dillerin anlaşılması ve sürdürülmesi çok daha kolaydır ve programcının gerçekten iyi performans elde etmek için alan uzmanlarının bilgisinden yararlanmasına olanak tanır. Ek olarak, doğru bir şekilde oluşturulursa, alana özgü bir dil, alt düzey kararı derleyiciye bırakarak optimizasyon sürecini çok daha basit hale getirebilir.
  
  
• 00:05:00 Bu bölümde konuşmacı, performans mühendisliğinde etki alanına özgü dillerin (DSL'ler) kullanımını tartışıyor. Mümkün olduğunda performansın derleyiciye bırakılmasını teşvik ederler ve grafik işleme için üç farklı programlama dili/çerçevesi sunarlar: Graffiti, Halide ve OpenTuner. Grafiklerin Google aramalarından öneri motorlarına kadar her yerde olduğuna dikkat çekiyorlar ve Google'ın web sayfalarını sıralamak için kullandığı PageRank algoritmasını daha derinlemesine araştırıyorlar. PageRank algoritması, bir web sayfasının komşularına bakar ve etkilerine göre yeni bir sıralama hesaplayarak performans mühendisliğinde grafik işlemenin önemini gösterir.
  
  
• 00:10:00 Bu bölümde konuşmacı, büyük miktarda veriyi işlemeyi ve grafiğin tamamı için hesaplamaları yinelemeyi içerebilen grafik algoritmalarını tartışıyor. Performans için kodu optimize etmek üzere bir DSL kullanılabilir. Grafik işleme için kullanılan algoritmaların türü, tüm grafiğin hesaplamaya katıldığı topolojiye dayalı algoritmaları ve işlemenin grafiğin küçük bir bölgesi veya parçası üzerinde yapıldığı veriye dayalı algoritmaları içerir. Grafik tersine çevirmenin birden çok yolu vardır ve her yolun farklı sonuçları vardır.
  
  
• 00:15:00 Bu bölümde, büyük bir grafiğin daha küçük parçalara bölündüğü grafik bölümlendirme konusu ele alınmaktadır. Bir grafiği bölümlemenin avantajı, paralelliğe izin vermesi ve aynı zamanda iyi bir yerellik sağlamasıdır; bu, üzerinde çalışılan düğümlerin önbelleğe sığacak kadar küçük olduğu anlamına gelir. Grafik bölümleme, güç yasası ilişkisine sahip oldukları için sosyal ağ grafikleri üzerinde de bir etkiye sahiptir. Bu, belirli düğümlerin diğerlerinden daha fazla bağlantıya veya daha büyük bir etkiye sahip olduğu ve bu grafikleri işlerken, önemleri nedeniyle belirli bağlantılara ve düğümlere daha fazla dikkat edilmesi gerektiği anlamına gelir.
  
  
• 00:20:00 Bu bölümde, konuşmacı bir grafiğin şeklinin hesaplamadaki önemini, özellikle bir grafiğin boyutunun ve konumunun paralellik algoritmalarının verimliliğini nasıl etkileyebileceğini tartışıyor. Belirli bir algoritma için en iyi performansı elde etmek için paralellik, yerellik ve gereken ekstra çalışma gibi faktörler dikkatli bir şekilde dengelenmeli ve grafiğin türüne, algoritmanın türüne ve kullanılan donanıma göre doğru yöntem seçilmelidir. Bu faktörleri daha iyi optimize etmek için sabit algoritmayı işleme yöntemlerinden ayırmak için alana özgü bir dil geliştirildi.
  
  
• 00:25:00 bu bölümde, konuşmacı alana özgü dillerin (DSL'ler) daha yüksek düzeyde kod yazmak için nasıl kullanılabileceğini tartışıyor, bu da kodu daha basit ve daha zarif hale getiriyor. Farklı algoritmalara ve DSL'lerin bunları hesaplamanın basit bir yolunu nasıl sağladığına dair örnekler veriyorlar. Ek olarak, konuşmacı paralel işlemeye izin verse bile mümkün olan en iyi hızı elde etmek için DSL programlamasının nasıl optimize edilebileceğini açıklıyor. Kod, grafikteki veya makinedeki değişikliklere göre değişebilir, ancak algoritma aynı kalır. Konuşmacı, DSL'lerin programlamada basitlik sağlarken optimize edilmiş programlar oluşturacak kadar güçlü olmasının önemini vurguluyor.
  
  
• 00:30:00 Bu bölümde konuşmacı, yoğun düzenli yapılarla görüntü işlemeye odaklanan başka bir alana özgü dili, Halide'yi tartışıyor. Halide, optimize edilmiş performans elde etmek için gereken programlama miktarını azaltmaya yardımcı olur ve programın farklı makineler arasında taşınabilirliğini artırır. Konuşmacı, Halide'nin nasıl çalıştığını göstermek için üçe üç bulanık bir örnek sağlar. Halide, çeşitli tekniklerin farklı kombinasyonları aracılığıyla performansı optimize etme açısından daha önce tartışılan grafik diline benzer bir modele sahiptir.
  
  
• 00:35:00 Bu bölümde konuşmacı, etki alanına özgü dillerin (DSL'ler) kullanımını ve kod performansını optimize etmek için otomatik ayarlamayı tartışıyor. Geçerli bir C koduna kıyasla Halide adlı bir DSL kullanarak daha hızlı çalışan bir görüntü filtresi örneği sağlıyor. Halide, yürütülmekte olan saf işlevlerin ardışık düzeninin basit optimizasyonuna olanak tanıyan algoritmanın programdan ayrılmasını sağlar. Son olarak, konuşmacı, mevcut bilgi işlem kaynaklarından en iyi performansı elde etmek için yerellik, paralellik ve fazla çalışma arasında bir ödün verilmesi gerektiğini vurgular.
  
  
• 00:40:00 Bu bölümde konuşmacı görüntü işleme söz konusu olduğunda yerelliğin önemini tartışıyor. Büyük bir görüntüyü işlerken, önbelleğe sığmayacağından tüm görüntü üzerinde çalışan filtreleri aynı anda uygulamak verimli olmaz. Bunun yerine, konuşmacı görüntüyü daha küçük bölümlere ayırmayı ve her bölüme yerellik ve paralelliğe odaklanarak filtreler uygulamayı önerir. Bu, bir zamanlama çerçevesi kullanarak ve hesaplama bant genişliğini ve depolama ayrıntı düzeyini optimize ederek elde edilebilir. Ayrıca, daha iyi yerellik ve paralellik elde etmek için biraz gereksiz çalışma gerektirebilir.
  
  
• 00:45:00 Bu bölümde, konuşmacı Halide'nin kullanımına odaklanarak Etki Alanına Özgü Dilleri ve otomatik ayarlamayı tartışıyor. Halide, kitaplık işlevlerini birbirine kaynaştırabilir; bu, kitaplıkları çağırmaktan daha hızlıdır çünkü daha fazla yer vardır. Konuşmacı, Halide'nin ikili filtre hesaplaması ve segmentasyon algoritmaları gibi hesaplama süreçlerini nasıl optimize edebileceğini gösterir. Bir örnekte, elle optimize edilmiş kitaplıkları çağıran MATLAB'de yazılmış bir segmentasyon algoritması, Halide'de yazıldığında 70 kat daha hızlıydı. Halide, Google'ın önemli bir parçasıdır ve Android telefonlara entegre edilmiştir ve Google Glass'ta kullanılmıştır.
  
  
• 00:50:00 Bu bölümde, konuşmacı ön uç işleme için Halide kullanmanın etkinliğini ve farklı endüstrilerde nasıl yaygın bir şekilde kullanılmaya başladığını tartışıyor. Halide, önceki sürümlere göre %4-5'lik bir hız artışına sahiptir ve bu, indirilen video sayısı göz önüne alındığında Google için önemli bir değerdir. Adobe ayrıca tüm Photoshop filtrelerinin Halide'de yazıldığını duyurdu. Snapdragon görüntü işlemcisi ve Intel de Halide kullanmaya başlıyor. Konuşmacı ayrıca Halide ve Graph'ın optimizasyonu otomatik hale getirebilme ve performans mühendisinin işini kolaylaştırma açısından nasıl benzerlikler paylaştığını tartışıyor. Ancak, algoritmik optimizasyon söz konusu olduğunda, otomatikleştirmeyi zorlaştıran, belirli bağlamsal bilgi gerektiren daha üst düzey bir değişikliktir. Bununla birlikte, programlanmış diller gibi araçlar, kullanıcılara farklı yaklaşımları deneme ve daha iyi performans elde etme seçeneği sunar.
  
  
• 00:55:00 Bu bölümde, konuşmacı modern bilgisayar sistemlerinin karmaşıklığını ve kodu optimize etmenin tek bir doğru yolunun olmadığını tartışıyor. Farklı yaklaşımlar denemenin önemini ve önbelleklerin, yerelliğin ve paralelliğin önemini vurgularlar. Ayrıca, biyoloji ve fizik gibi çeşitli alanlardaki insanların, kodun karmaşıklığı nedeniyle programları yeterince hızlı yazamadıkları için araştırma yapmak yerine kodu optimize etmek için nasıl çok zaman harcadıklarını da tartışıyorlar. Konuşmacı, insanların zamanlarının çoğunu bilgisayar korsanlığı yaparak ve soyutlama yaparak geçirdikleri alanları bulmanın araştırma için keşfedilecek ilginç bir alan olabileceğini öne sürüyor. Genel olarak, programları optimize etmek için çalışılacak alan paralellik, yerellik ve gereksiz çalışmayı içerir ve bu alanda oynamak performans mühendisleri için çok önemlidir.


• 01:00:00 Bu bölümde konuşmacı, bir programın en iyi şekilde çalışması için doğru parametreleri bulmayı içeren performans mühendisliğinin zorluklarını tartışıyor. Bellek tahsisi ve blok boyutu gibi ayarlanabilen çok sayıda parametre olduğunu, ancak her program için her parametre için doğru değerleri belirlemenin zor olabileceğini açıklıyor. Ancak konuşmacı, otomatik ayarlamanın, optimum değerleri bulmak için geniş parametre alanını otomatik olarak arayarak bu sorunu çözebileceğini öne sürüyor. Belirli durumlar için sabit kodlama kuralları içeren buluşsal tabanlı çözümlerin çoğu zaman işe yarayabileceğini ancak her zaman optimal olmayabileceğini açıklıyor. Konuşmacı ayrıca, modelin tüm önemli faktörleri hesaba katmadığı ve bunun yetersiz sonuçlara yol açabileceği için sistemin modellerini oluşturmanın sorunlu olabileceğini belirtiyor.
  
  
• 01:05:00 Bu bölümde, konuşmacı değişen teknoloji veya gelişen gereksinimler karşısında en uygun çözümleri bulmanın zorluklarını tartışıyor. Programcıların çözümlerine rehberlik etmek için kullandıkları, genellikle artık geçerli olmayabilecek yönergelere veya pratik kurallara dayanan çeşitli "buluşsal yöntemler" olduğunu belirtiyor. Bir seçenek kapsamlı aramadır, ancak olası permütasyonların çok sayıda olduğu düşünüldüğünde bu pratik olmayabilir. Bunu ele almak için konuşmacı, arama alanını budamak ve en uygun çözümleri daha hızlı bulmak için otomatik ayarlamanın kullanılmasını önerir. Otomatik ayarlama, kabul edilebilir değerler alanı tanımlamayı, test edilecek bir değeri rastgele seçmeyi ve ardından performans sonuçlarına göre yinelemeyi içerir. OpenTuner, bu yinelemeli süreci hızlandırmak için tepe tırmanıcılar ve rastgele arama gibi bir dizi teknik kullanan bir çerçeve örneğidir.
  
  
• 01:10:00 Bu bölümde, konuşmacı otomatik ayarlama kavramını ve Try için programların oluşturulmasında nasıl uygulanabileceğini tartışıyor. İlgili grafikleri ve ritmi anlayarak, ayrıntılı aramadan daha verimli ve etkili bir program oluşturmak için otomatik ayarlama kullanılabilir. Bu yöntem, programları iki saatten daha kısa sürede ve bazı durumlarda başlangıçta mümkün olan en iyi program olduğu düşünülenden bile daha iyi üretebildi.

[MetaQuotes]

Ders 19. Leiserchess Codewalk

Ders 19. Leiserchess Codewalk

"19. Leiserchess Codewalk" adlı bu YouTube videosunda Helen Xu, rakip takımın şahını vurmak veya şahınızı vurmak amacıyla iki takım tarafından oynanan bir oyun olan Lesierchess'in kurallarını açıklıyor. Oyunda iki tür hamle vardır, temel ve swat hareketleri ve rakibin en son hamlesini geri alırsa bir hamleyi geçersiz kılan bir Ko kuralı. Xu, Fisher zaman kontrol yöntemi, Forsythe-Edwards Notasyonu, Bulut otomatik test cihazı ve proje organizasyonu, Elo derecelendirmelerini kullanarak botları değerlendirme ve karşılaştırma, hareket oluşturma, statik değerlendirme ve alfa-beta gibi arama algoritmaları dahil olmak üzere oyunu oynamanın çeşitli yönlerine dalıyor. ilke değişimi, alt ağaç budama ve yer değiştirme tabloları. Ayrıca programı optimize etmek için test altyapısının önemini ve tahtadaki her kareyi parçanın türüne ve rengine göre değerlendiren buluşsal yöntemleri içeren eval.c dosyasını tartışıyor.

Konuşmacı aynı zamanda oyunun lazer kapsama yönüne de girerek, doğru bir ifade kullanarak oyuncunun rengine dayalı bir konum için olası tüm hareketleri üretmenin karmaşık sistemini açıklıyor. Ayrıca, koddaki doğruluğun önemini ve bunun nasıl test edileceğini açıklayarak, performans optimizasyonundan önce doğruluğu sağlamak için gösterimin dönüştürülmesini önerirler. Konuşmacı ayrıca, kullanıcıların tabloları ve komutları istedikleri gibi düzenlemelerine izin veren ve izleyicilere ölü kodun temizleneceği ve diğer hataların düzeltilmesi için rapor edilmesi gerektiği konusunda güvence veren Leiserchess UCI arayüzü tarafından sağlanan büyük esnekliği tartışıyor.

• 00:00:00 Bu bölümde Helen, Lesierchess oyununun kurallarını ve nasıl oynanacağını anlatıyor. Oyun turuncu ve eflatun olmak üzere iki takım tarafından oynanır ve her takımın yedi piyonu ve bir şahı vardır. Oyunun amacı, rakip takımın şahını vurmak veya şahınızı vurmaktır. Oyunda temel ve swat hareketleri olmak üzere iki tür hamle vardır. Oyun ayrıca, rakibin en son hamlesini sadece rakip takımın olduğu yere geri dönerek geri alırsa, bir hamleyi geçersiz kılan bir Ko kuralına sahiptir. Her takım tarafından bir piyon zaplanmadan 50 hamle yapılırsa, aynı konum tekrarlanırsa veya iki takım berabere kalmayı kabul ederse beraberlik olur.
  
  
• 00:05:00 Bu bölümde konuşmacı, leiserchess'te kullanılan Fisher zaman kontrol yöntemini açıklar. Her oyuncu bir başlangıç zaman bütçesi ve bir zaman artışı ile başlar. Kullanılan örnekte her oyuncu 60 saniye ile başlar ve hamlesini bitirdiğinde fazladan 0,5 saniye alır. Ancak gerçek zaman sınırı herhangi bir şey olabilir. Konuşmacı daha sonra seyirciden mandalina için F5'te karşı saldırılardan kaçınırken piyonu vurması için hamleler önermesini isteyerek nasıl leiserchess oynanacağını gösterir. Ancak konuşmacı, rakibin içini açabileceği için safça tüm taşları öldürmek gibi oyunun incelikleri konusunda uyarıyor.
  
  
• 00:10:00 Bu bölümde Helen Xu, Forsythe-Edwards Notasyonunu, hata ayıklama amaçları için yararlı olan ve kişinin belirli bir konuma kolayca geri dönmesine izin veren bir dize kullanarak bir satranç konumunu temsil eden bir araç olarak tartışıyor. Ayrıca satranç oyunlarının günlüklerini nasıl okuyacağını, her hamleyi ve bunlara karşılık gelen açıklamaları nasıl parçalayacağını da açıklıyor. Ayrıca, sınıftaki diğer takımlarla botları test etmek için hücum sunucusunu nasıl kullanacağını ve diğer takımlara nasıl meydan okuyacağını ve oynanan maçları nasıl görüntüleyeceğini gösteriyor.
  
  
• 00:15:00 Bu bölümde Helen Xu, Lesierchess için Bulut otomatik test edicisini ve proje organizasyonunu tartışıyor. Hücum sunucusu aynı anda yalnızca bir oyuna izin verirken, Bulut otomatik test cihazı, her kullanıcının tercihine göre özelleştirilebilen bir zaman kontrolünde birden fazla oyunu ve ikili dosyayı çalıştırabilir. Depodaki proje organizasyonu doc, auto tester, pgnstates, testler, player ve webgui dizinlerini içerir. Otomatik test cihazı, değişiklikleri yerel olarak test etmek için kullanılan bir Java yerel otomatik test cihazıdır, testler dizininde ise otomatik test için yapılandırmalar belirtilebilir. Helen Xu ayrıca Lesierchess tarafından otomatik test cihazıyla arabirim oluşturmak için kullanılan bir iletişim protokolü olan evrensel göğüs arabirimini (UCI) de sunar.
  
  
• 00:20:00 Bu bölümde konuşmacı, sıfır toplamlı oyunlarda göreceli beceri düzeyine dayalı bir derecelendirme sistemi olan Elo derecelendirmeleri kullanılarak botların nasıl ölçüleceğini ve karşılaştırılacağını tartışıyor. Elo derecelendirmesi yalnızca zamana değil, aynı zamanda UCI kullanılarak aranan saniye başına düğüm sayısına da dayalıdır. Konuşmacı daha sonra oyunu oynama hakkında, örneğin hareketler oluşturma, tahta gösterimi ve pozisyonu saklamak için kullanılan yapı gibi daha fazla ayrıntıya dalar. Ek olarak hareket, parça tipini, yönü, kareden, ara kareyi ve iki kareyi içeren 28 bit kullanılarak temsil edilir. Referans yerleştirme, tahtayı yineleyerek ve tüm hareketleri o belirli parçadan üreterek, sıranın kimde olduğuna bağlı olarak tüm hareketleri oluşturur. Konuşmacı, değiştirilmiş hareket oluşturmanın her konumdan aynı hareketleri döndürmesini sağlamak için perft hata ayıklama işlevinin kullanılmasından bahseder.
  
  
• 00:25:00 Bu bölümde konuşmacı, buluşsal yöntemler kullanarak bir konuma dayalı bir puan oluşturan statik değerlendirme aracılığıyla bir hareketin iyi olup olmadığını nasıl belirleyeceğini tartışır. Sezgiler şaha, piyonlara ve mesafeye odaklananları içerir ve bir konumun iyi olup olmadığını belirlemeye yardımcı olabilir. Konuşmacı ayrıca oyun oynama programlarının oyunu oynamak ve değerlendirmeye dayalı olarak en iyi hamleyi seçmek için arama ağaçlarını nasıl kullandığından bahsediyor. Düğüm sayısını azaltmak için konuşmacı, değerlendirilen düğüm miktarını artırabilecek ve daha iyi performansa yol açabilecek sessizlik araması ve min-maks araması hakkında ayrıntılara giriyor.
  
  
• 00:30:00 Bu bölümde konuşmacı, alfa beta pencereli bir düğümden arama sırasında kullanılan alfa beta adlı algoritmayı tartışıyor. Aramanın değeri alfanın altına düşerse, hareket yeterince iyi değildir ve aramaya devam edersiniz. Beta, esasen bir tarafın maksimize etmeye, diğerinin ise minimuma indirmeye çalıştığı anlamına gelir. Bu nedenle, değer beta'nın üzerine düşerse, o zaman bir beta kesmesi oluşturursunuz çünkü rakip, çok iyi olacağı için bu hamleyi yapmanıza izin vermez. Konuşmacı daha sonra, ilk hareketin en iyisi olduğunu varsayan ilke varyasyon aramasını açıklar ve siz de geri kalan hamlelerde daha kötü olduklarını doğrulamak için sıfır pencere araması olarak da adlandırılan keşif aramasını çalıştırırsınız. Bu arama yöntemi, alfa-beta algoritmasının bir varyasyonudur.
  
  
• 00:35:00 Bu bölümde minimaks arama algoritmalarında alt ağaç budama kavramı ele alınmaktadır. Alt ağaç budamasının ardındaki fikir, şimdiye kadar bulunan en iyi puandan daha düşük puanlara sahip alt ağaçları kaldırmaktır. Bu, değerlendirilen düğüm sayısını azaltır ve arama sürecini hızlandırır. Rakip de en iyi hamleyi arar ve oyuncunun puanlarını en aza indirmeye çalışır. Oyuncunun puanını en üst düzeye çıkarmak ile rakibin puanını en aza indirmek arasındaki denge çok önemlidir ve amaç, oyuncu için iyi olan ve aynı zamanda rakibin izin vereceği bir hamle bulmaktır.
  
  
• 00:40:00 Bu bölümde Helen Xu, en soldaki alt ağacın en iyi yol olduğu varsayımının yapıldığı ve varsayım doğruysa erken çıkışların alındığı ana varyasyon budama kavramını açıklıyor. Varsayım yanlışsa, tüm alt ağaç aranmalıdır. İzci araması, varsayımları doğrulamak için ilk geçişlerle birlikte, bunu yinelemeli olarak daha düşük alt ağaçlara uygulamak için kullanılır. Bu yöntem, budamayı geliştirir ve oyun ağacının çoğunu sıfır pencere aramasıyla işler.
  
  
• 00:45:00 Bu bölümde, Leiserchess programı için arama optimizasyonlarını öğreniyoruz. En önemli optimizasyonlardan biri, gereksiz aramalardan kaçınarak zaman kazandıran, daha önce karşılaşılan konumları saklamak için bir transpozisyon tablosunun kullanılmasıdır. Diğer optimizasyonlar arasında, her konum için benzersiz hash'ler oluşturmak üzere Zobrist hashing'in kullanılması, yeniden hesaplanması gerekmemesi için iyi hareketleri saklamak için öldürücü hareket tablosu ve alfa puanını artırmayacak hamleleri keşfetmeyi atlamak için boşuna budama yer alır. Oyunun başında önceden hesaplanmış konumları saklamak ve aramada zaman kazanmak için daha iyi bir açılış kitabının uygulanması da önerilir.
  
  
• 00:50:00 Bu bölümde konuşmacı, önceden hesaplanabilen kitapların açılması ve oyun sonu veritabanları dahil olmak üzere bir satranç programını optimize etmek için bazı faydalı araçları tartışıyor. Hata ayıklama sorunları olmadan yenilik yapabilmek ve ilerleme kaydedebilmek için test etmek ve test için iyi bir altyapıya sahip olmak önemlidir. Paralel programlamada transpozisyon tablolarının kullanılması, test amacıyla bunların kapatılabilmesini önemli kılar ve test sırasında sabit derinlikli aramalar yapılması önerilir. Genel olarak, iyi bir test altyapısına sahip olmak, ilerleme kaydetmek ve önemli hata ayıklama sorunlarından kaçınmak için çok önemlidir.
  
  
• 00:55:00 Bu bölümde, konuşmacı Leiserchess projesindeki eval.c dosyasını ve boyutu ve karmaşıklığı nedeniyle ilk bakışta nasıl bunaltıcı görünebileceğini tartışıyor. Bununla birlikte, kullanıcılar buna daha aşina hale geldikçe, uygun boyutta bir kod parçasını kullanma konusunda güven kazanacaklardır. eval.c dosyası, tahtadaki her kareyi parçanın türüne ve rengine göre değerlendiren p arasında, p orta, k yüz ve k agresif gibi buluşsal yöntemler içerir. Buluşsal yöntem arasındaki p, bir piyonun her iki şah arasında olup olmadığını belirlerken, p merkezi, piyonun tahtanın merkezine ne kadar yakın olduğuna bağlı olarak bir bonus verir. k yüz ve k agresif buluşsal yöntemler, şahın yönüne ve rakip ile tahta kenarlarına olan mesafesine bağlı olarak bonuslar verir.
  
  
• 01:00:00 Bu bölümde konuşmacı, oyunun karmaşık bir yönü olan lazer kapsamını açıklıyor. Lazer kapsamı, oyuncunun rengine bağlı olarak belirli bir konumun olası tüm hareketlerini oluşturur. Daha sonra bir hareket listesi sunar ve konuşmacı bu haritanın işlevini nasıl yerine getirdiğini bir while-true ifadesiyle detaylandırır. Lazer yolu, yolu çizerken bazı piyonlardan seker ve her kare için mesafeyi artırır. Harita oluşturulduktan sonra işlem tekrarlanır ve mesafe lazerden olan gerçek mesafeye bölünür. Bu karmaşık sistem, tahtadaki her bir parçayı bulmak için değerlendirme yönteminde gerekli yinelemeleri optimize eder, bu da süreci yavaşlatır ve konuşmacı, tahtayı farklı şekilde temsil etmenin ve her iki dönüştürme işlevinin de aynı sonucu verdiğini iddia etmenin iyi bir yol olduğunu ekler. optimizasyon kararları
  
  
• 01:05:00 Videonun bu bölümünde, konuşmacılar kodda doğruluğu korumanın önemini ve bunun nasıl test edileceğini tartışıyor. Bir sunumdan diğerine dönüştürmenin süreci yavaşlatabileceğini ancak performans için optimize etmeden önce doğruluğu sağlamak için gerekli olduğunu açıklıyorlar. Doğruluğu test etmenin bir yolu, düğüm sayılarını takip etmek ve değişiklik yaptıktan sonra aynı kaldıklarından emin olmaktır. Ayrıca Lesierchess.c'de kodun nasıl çalıştırılacağını ve UCI arabiriminin nasıl gösterileceğini gösterirler; Son olarak, buluşsal yöntemler tablosunun üzerinden geçerler ve otomatik test cihazı için değerlerin nasıl belirleneceğini açıklarlar.
  
  
• 01:10:00 Bu bölümde konuşmacı, Leiserchess oyununun UCI arabirimi aracılığıyla tabloları ve komutları düzenlemek için sağladığı büyük esnekliği tartışıyor. Bu, kullanıcıların yeni buluşsal yöntemler de dahil olmak üzere istedikleri tüm komutlara erişmesine ve bunları uygulamasına ve ayrıştırma ve uygulama üzerinde kontrole sahip olmasına olanak tanır. Bazı ölü kodlar olmasına rağmen, profesör izleyicilere bunun temizleneceği ve diğer hataların düzeltilmesi için bildirilmesi gerektiği konusunda güvence verir. Son olarak, projenin her dakika eğlenceli olmayabileceğini, ancak genel olarak bolca keyif sağladığını belirtiyor.

[MetaQuotes]

Ders 20. Spekülatif Paralellik ve Leiserchess

20. Spekülatif Paralellik ve Leiserchess

"20. Spekülatif Paralellik ve Leiserchess" başlıklı bu YouTube videosunda eğitmen, esasen belirli görevlerin paralel olarak gerçekleştirilebileceğini ve daha hızlı kodla sonuçlanabileceğini önceden tahmin eden spekülatif paralellik kavramını tanıtıyor. Ancak konuşmacı, bu kodun deterministik olmadığı ve yalnızca gerektiğinde kullanılması gerektiği konusunda uyarılırken, daha iyi bir seri kodun kullanılabileceği durumlarda kullanılmaması konusunda da uyarıda bulunuyor. Videonun önemli bir kısmı, arama süresini optimize etmek için oyun ağacının budanmasını içeren paralel alfa-beta aramalarının tartışılması etrafında dönüyor ve ayrıca arama algoritmalarının değerlendirme sürecinde, özellikle döngüden ve durgunluktan kaçınmak için kullanılan farklı veri yapıları ve buluşsal yöntemlerden bahsediyor. aramak. Video aynı zamanda yinelemeli derinleştirmenin faydalarına ve bunun aramalar için daha iyi hamle sıralamasına nasıl yol açtığına değinirken aynı zamanda aynı taşlarla satranç tahtasındaki her konum için benzersiz bir karma değeri içeren arama algoritmalarında kullanılan bir optimizasyon tekniği olan Zobrist hashing'i tartışıyor.

Bu video aynı zamanda satranç motorları için transpozisyon tabloları, geç hamle azaltma ve hamle oluşturmak için bitboard kullanımı gibi çeşitli optimizasyon tekniklerini tartışıyor. Konuşmacı ayrıca programcılara bir hareketin lazerin yolunu etkileyip etkilemediğini değerlendirmelerini ve "lazer kapsamı"nın peşinden gitmelerini tavsiye ettiği "spekülatif paralellik ve Leiserchess" konusundan da bahsediyor. Konuşmacı, eski temsilleri kodda bırakmayı ve değişiklikleri test etmek için programları kullanmayı önerir. Ayrıca Leiserchess'te bir lazerin Kral'a ne kadar yakın olduğunu ölçmek için bir buluşsal yöntem geliştirdiler. Daha fazla optimizasyon önerisi, rakibin oyuncunun lazerine olan yakınlığını değerlendirmenin daha iyi bir yolunu bulmayı ve hareket sıralamasını optimize etmeyi içerir. Son olarak, kodu uygun şekilde yeniden düzenlemenin ve test etmenin önemi tartışılmaktadır.

• 00:00:00 Bu bölümde eğitmen, kodu optimize etmenin ve daha hızlı çalışmasını sağlamanın bir yolu olarak spekülatif paralellik kavramını tanıtıyor. Bu, doğası gereği seri olsalar bile belirli görevlerin paralel olarak gerçekleştirilebileceğini tahmin etmeyi içerir ve bu, tahminin yanlış olduğu ortaya çıkarsa bazı boşa çabalara neden olabilir. Eğitmen, bir toplamın eşiklenmesine ilişkin bir örnek sağlar ve kısmi toplam bir eşiği aşarsa erken çıkarak basit bir optimizasyon gösterir, ancak bu, kodu yavaşlatabilecek öngörülebilir bir dal sağlar.
  
  
• 00:05:00 Bu bölümde, konuşmacı paralel çalışırken iç döngüye çok fazla ekleme sorununun nasıl azaltılacağını tartışıyor. Şerit madenciliğinin, n yineleme döngüsünü, dört yinelemeden oluşan bir iç döngü ile dört yinelemeden oluşan bir n döngüsüyle değiştirmek için kullanılabileceğini ve aynı zamanda maliyeti en aza indirmek için her dördüncü yinelemede eşiğin aşılıp aşılmadığını kontrol etmek için kullanılabileceğini açıklıyorlar. kontrol. Kısa devreli bir döngüyü paralel hale getirmek için, konuşmacı, koda bir iptal bayrağı ekler ve bunu, toplamın bir sınırdan büyük olup olmadığını ve bayrağı doğru olarak ayarlamadan önce iptal edilip edilmediğini tekrar tekrar kontrol etmek için kullanır. Bayrağı ayarlamadan önce kontrol ederek, bir kararlılık yarışından kaçınırlar ve gerçek paylaşım yarışlarını engellerler.
  
  
• 00:10:00 Bu bölümde video, bir programın paralel çalışma gerçekleştirmesi gerekeceğini tahmin etmesi ve önleyici olarak çalışacak şekilde ortaya çıkması durumu olan spekülatif paralelliği tartışıyor. Bu kod, deterministik değildir ve yalnızca gerektiğinde performans amacıyla kullanılmalıdır. İptal bayrağını sıfırlamak ve paralellik için çok az başka fırsat olmadığı ve buna ihtiyaç duyulması ihtimali yüksek olmadığı sürece spekülatif işler üretmemek esastır. Video, daha iyi bir seri kodun kullanılabileceği durumlarda spekülatif paralellik kullanımına karşı uyarıda bulunuyor çünkü bu yaklaşım genellikle hızlanma olmaksızın daha fazla çalışmaya yol açıyor. Son olarak, paralellik için çalışmanın gereksiz olma ihtimalinin kullanılan işlemci sayısından az olması gerektiğini özetleyen bir teoreme başvurulur.
  
  
• 00:15:00 Bu bölümde tartışma, arama süresini optimize etmek için oyun ağacının budanmasını içeren paralel alfa-beta aramaları etrafında dönüyor. Burkhardt Manin ve öğrencileri, en iyi sıralı bir ağaçta her düğümün derecesinin ya 1 ya da maksimum olduğunu gözlemlediler. Fikirleri, en iyi hamlenin, ilk çocuk bir beta kesintisi oluşturamadığında seçildiğini tahmin etmekti. Bu, kalan çocukların herhangi bir iş kaybı olmadan paralel olarak aranmasını sağlar. Koddaki buluşsal yöntemler, daha sığ bir derinlikte olsa bile en iyi hareketi seçmek için genç kardeşlerin ağırlık algoritmasını kullanmak gibi işlerin doğru sırayla yapılmasını sağlamaya yardımcı olur. Algoritma, gereksiz oldukları ortaya çıktığında alt hesaplamaları da iptal eder.
  
  
• 00:20:00 Videonun bu bölümünde konuşmacı, paralelleştirmede iptal edilen ataları kontrol etmek ve iş israfını önlemek için periyodik olarak ağaca tırmanma mekanizmasını tartışıyor. Ağacı kaldırmanın bir maliyeti olduğu için ne sıklıkta kontrol edileceğini belirlemek için bir sayaç veya vudu parametresi olmasını önerirler. Konuşmacı ayrıca, paralelleştirmede yarışlara neden olabilecek transpozisyon tablosu gibi aramada kullanılan veri yapılarından da bahsediyor. Veri yarışlarını önlemek için her çalışan için çoğaltmayı veya kilitlemeyi önerirler. Son olarak, konuşmacı, daha kolay hata ayıklamak için spekülasyonu ve kodun diğer deterministik olmayan kısımlarını kapatmanın bir yolunu öneriyor.
  
  
• 00:25:00 Bu bölümde konuşmacı, 1999'da Dünya Bilgisayar Satranç Şampiyonası'nı neredeyse kazanan bir programdan bahsediyor. Herkesin kabul ettiği bir kural değişikliği önerdiler ama sonra ünlü IBM bilgisayarı Deep Blue'ya kaybettiler. Sandia Ulusal Laboratuarlarında 1824 düğümlü bir süper bilgisayar üzerinde çalışıyorlardı ve tek kayıpları Deep Blue'ya oldu. Programı yavaşlatacağı için tabloya erişim için kilitler eklemeden programlarında aktarma tablosunda bir yarış olmasına izin vermeye karar verdiler. Bir yarışın seçecekleri değeri ve sonunda turnuvanın sonucunu etkileme oranlarının düşük olduğunu hesapladılar.
  
  
• 00:30:00 Videonun bu bölümünde konuşmacı, satranç yapay zekasında karar vermek için önemli olan üç veri yapısını tartışıyor. İlki, belirli bir kod derinliğinde en iyi hareketleri takip eden ve doğası gereği tekrarlayıcı olma eğiliminde olan "öldürücü" sezgiseldir. İkincisi, tüm düşük sıralı hareketleri istatistiksel verilere dayalı olarak sıralayan "en iyi hamle" tablosudur. Her iki veri yapısı da paylaşılır ve kodu paralelleştirirken düzgün bir şekilde yönetilmesi gerekir. Nihai veri yapısı, oyunun başındaki en iyi hamleleri önceden hesaplayan açılış kitabıdır. Bununla birlikte, konuşmacı açılış kitabına göre daha az asılı meyve olduğunu ve istatistiksel olarak çoğu oyunun bir açılış kitabının faydalı olması için yeterince uzun sürmediğini öne sürüyor.
  
  
• 00:35:00 Bu bölümde konuşmacı, takımların en güçlü satranç oynayan botları yaratmaya çalıştığı bir oyun olan Leiserchess'te açılış kitapları oluşturma stratejisini tartışıyor. Konuşmacı, bazı takımların harika bir başlangıçla kazanmalarını sağlayan güçlü bir açılış kitabı oluşturarak başarılı olduklarını belirtiyor. Ayrıca, her iki taraf için ayrı açılış defterleri tutmanın, her ikisi için birer kitap kullanmaktansa daha etkili olduğunu öne sürüyorlar. Ek olarak konuşmacı, öngörülebilirliği önlemek için koda hafif bir rastgelelik eklemenizi önerir, ancak beta bir sırasında bunun için optimize etmenin gerekli olmadığı konusunda uyarır. Son olarak, zaman kontrolünün süresi dolana kadar farklı derinliklerde arama yapmayı içeren yinelemeli derinleştirme stratejisini önerirler. Konuşmacı, her derinlikte yapılan iş miktarının katlanarak arttığı, ancak önemli bilgilerin ilk birkaç derinlikte biriktiği için bunun iyi bir strateji olduğunu belirtiyor.
  
  
• 00:40:00 Bu bölümde video, yinelemeli derinleştirmenin faydalarını ve bunun aramalar için daha iyi hareket sıralamasına nasıl yol açtığını ele alıyor. Yinelemeli derinleştirmeden geçerek, yer değiştirme tablosu tüm ara konumlar için en iyi hareket sıralama bilgisini saklayabilir ve budamayı daha derin bir derinlikte daha etkili hale getirir. Ayrıca yinelemeli derinleştirme yaparak zaman kontrolü için iyi bir mekanizma sağlar. Video aynı zamanda oyun veritabanına ve bir oyunsonu veritabanı oluşturmanın neden faydalı olduğuna değinirken aynı zamanda basit bir boole değeri yerine çiftleşmeye olan mesafeyi depolayarak bir oyunsonu veritabanında döngüden nasıl kaçınılacağını tartışıyor.
  
  
• 00:45:00 Bu bölümde, konuşmacı, arama algoritmalarının değerlendirme sürecinde, özellikle döngülü ve sessiz aramadan kaçınmada kullanılan farklı buluşsal yöntemleri tartışıyor. Konuşmacı, mevcut mesafeden bir eksik olan bir kazanma mesafesi arayarak kazanma mesafesini korumanın ve bisiklete binmekten kaçınmanın öneminden bahseder. Kullanılan başka bir buluşsal yöntem, hareketsiz oturmanın genellikle bir hareket yapmak kadar iyi olmadığı hareket budama ve bir konum hiçbir şey yapmamanın bile bir galibiyetle sonuçlanacak kadar iyi olduğu durumlarda aramayı basitleştirmek için boş hareketin uygulandığı hareketsiz budamadır. . Konuşmacı ayrıca Satrançta Zoogs Wang'ı ve yalnızca bir zorunlu hamle olduğunda Satranç yalan aramasında hamle uzantılarının nasıl kullanıldığını tartışır.
  
  
• 00:50:00 Bu bölümde konuşmacı, aslında bir dag (yönlendirilmiş asiklik grafik) olan bir arama algoritmasında transpozisyon tablosunun kullanımından bahsediyor çünkü aynı konuma transpoze hareketlerle ulaşılabilir. Transpozisyon tablosu, aynı konumun tekrar aranmasını önlemek amacıyla bir hareketin değerini oluşturmak için aranan derinlik tarafından belirlenen kalite puanlarını saklar. Tam bir aramaya izin vermeyeceğinden ve saklanan değerin doğruluğu daha az olabileceğinden, çok düşük kaliteli hareketler kullanmamak çok önemlidir. Ek olarak, montaj ilişkisine ulaşmak için derinlikten çok büyük bir sayı çıkarılarak hesaplanan montaj ilişkisi konumlarını saklamak için özel kod kullanılır. Arama algoritmalarında kullanılan bir optimizasyon tekniği olan Zobrist hashing, tahtadaki her pozisyon için aynı parçalarla benzersiz bir hash değeri içeren tartışılmıştır.
  
  
• 00:55:00 Bu bölümde Profesör Leiserson, bir satranç tahtasındaki farklı taşların konumunu temsil eden bir karma işlevini verimli bir şekilde güncellemek için kullanılan Zobrist karma kavramını açıklıyor. Hash işlevi, parça türü, sıra, sütun ve yönün farklı kombinasyonlarına karşılık gelen bir rasgele sayılar tablosu oluşturmayı içerir. Hash işlevi, tüm parçaların değerlerinin ve oryantasyonlarının XOR'unu alarak hash'i hesaplamak için XOR işlemlerini kullanır. Zobrist hashing, kalan parçalar için hash elde etmek üzere kaldırılan parçanın değerini XORing yaparak hash işlevinden parçaları çıkarmak için XOR özelliğinden yararlanır. Bu, yapılan herhangi bir hareket için yalnızca iki XOR işlemiyle hash işlevinin ucuz ve verimli bir şekilde güncellenmesine izin verir.
  
  
• 01:00:00 Bu bölümde konuşmacı, satranç motorları için çeşitli optimizasyon tekniklerini tartışıyor. Bir hamlenin Zobrist anahtarının, skorunun, kalitesinin ve sınır tipinin kayıtlarını saklayan ve eski hamleleri yaşlandıran yer değiştirme tablosundan bahsediyor. Ek olarak, zaman kazanmak için daha az umut verici hamlelerin daha az derinlemesine araştırıldığı geç hamle azaltma konseptinden bahsediyor. Konuşmacı ayrıca tahtanın temsilinden ve bit tahtalarını kullanmanın, bitleri kaydırma ve sayma gibi işlemleri verimli bir şekilde gerçekleştirmek için bit hileleri kullanarak hareket oluşturmayı ve diğer satranç kavramlarını nasıl hızlandırabileceğinden bahsediyor.
  
  
• 01:05:00 Bu bölümde konuşmacı "spekülatif paralellik ve Leiserchess" konusunu tartışıyor. Bir lazerle uğraşırken yapılabilecek ana optimizasyonlardan birinin, bir hareketin lazerin yolunu etkileyip etkilemediğini değerlendirmek olduğunu açıklıyor. Ek olarak, konuşmacı gerçekten pahalı olduğu için "lazer kapsamı" peşinden gitmeyi öneriyor. Ayrıca programcılara eski temsili kodda bırakmalarını ve şeylerin eşdeğer olduğunu söyleyen iddialarda bulunmalarını ve herhangi bir değişiklik yapıp yapmadıklarını anlamak için Perfectiy gibi programları kullanmalarını tavsiye ediyor. Son olarak, lazeri Kral'a yaklaştırmak açısından programın nasıl çalışması gerektiğini ve oyundaki konumun önemini tartışıyor.
  
  
• 01:10:00 Bu bölümde konuşmacı, Leiserchess'te bir lazerin rakibin şahına ne kadar yaklaştığını ölçmek için geliştirdikleri yeni buluşsal yöntemi tartışıyor. Her hareketi, lazerin şahtan uzaklığını hesaplayarak, uzaklaştığı her konum için bir tane ve rakipten sekerse ekstra bir değer sayarak değerlendirirler. Her kareye ulaşabilecekleri minimum sayıyı alırlar ve şahın yakınında olmanın ne kadar iyi olduğunu ölçmek için bir çarpan kullanırlar. Hepsini toplarlar ve değeri bir piyonun kesri olarak temsil etmek için sihirli bir sabit çarpanı ile çarparlar. Ortaya çıkan sayı, ortalama olarak yaklaşık dörde kadar değişmektedir.
  
  
• 01:15:00 Bu bölümde konuşmacı, satranç motorunun verimliliğinin artırılabileceği çeşitli yolları tartışıyor. Mevcut yöntem hesaplama açısından pahalı olduğundan, bir öneri, rakibin oyuncunun lazerine olan yakınlığını değerlendirmenin daha iyi bir yolunu bulmaktır. Optimizasyonun başka bir alanı da, özellikle gözden geçirilecek çok sayıda hamle varsa, pahalı olabilen hamleleri sıralamaktır. Konuşmacı, yalnızca ilgili hareketlerin sıralanması ve gereksiz sıralamanın önlenmesi için sıralamayı optimize etmenin bir yolunu bulmayı önerir. Konuşmacı ayrıca tahta için temsilleri değiştirmenin sancılı bir süreç olabileceğinden, ancak bit tahtası temsilinin daha verimli olabilecek alternatifleri olduğundan bahseder.
  
  
• 01:20:00 Bu bölümde video, kodu bozmadan değişikliklerin doğru yapıldığından emin olmak için kodu yeniden düzenlemenin ve düzgün bir şekilde test etmenin önemini tartışıyor. Konuşmacı, kapsamlı yeniden düzenleme olmadan pano temsilini değiştirmeyi kolaylaştırmak için değiştirmeden önce bir işlev çağrısına yeniden düzenleme panosu erişimlerini önerir. Değişikliklerin doğru olduğundan ve kodu bozmadığından emin olmak için uygun testler de önemlidir ve öngörülemezliği önlemek için kodu belirleyici yapmak önemlidir. Konuşmacı ayrıca, John Bentley tarafından yapılacak bir dersin bir ünlüyle tanışmak ve alan hakkında daha fazla bilgi edinmek için değerli bir fırsat olduğunu belirtiyor.