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

 

MIT 6.172 Performance Engineering of Software Systems, Güz 2018 - 1. Giriş ve Matris Çarpımı



1. Giriş ve Matris Çarpımı

Öğretim görevlisi, "1. Giriş ve Matris Çarpımı" başlıklı bu YouTube videosunda, performans mühendisliğinin önemini ve zaman içinde nasıl geliştiğini tartışıyor. Konuşmacı, matris çarpımı örneğini kullanarak, kodlama tekniklerinin ve makine özelliklerinin performansı nasıl büyük ölçüde etkileyebileceğini gösterir. Tartışma, döngü sırası, önbellek kullanımı ve paralel programlama gibi konuları kapsar. Konuşmacı ayrıca farklı işlemciler ve aritmetik hesaplamalar için kodu optimize etmenin yollarını da keşfediyor. Genel olarak video, performans mühendisliği dünyasına ve onun modern bilgisayar sistemlerindeki pratik uygulamalarına ilişkin değerli içgörüler sağlar.

  • 00:00:00 Bu bölümde öğretim görevlisi performans mühendisliğinin önemini ve neden çalışıldığını tartışır. Yazılım geliştirme söz konusu olduğunda performans her zaman birinci öncelik değildir. Bununla birlikte, hesaplamanın para birimidir ve programlama kolaylığı, güvenlik ve doğruluk gibi istenen diğer özellikleri satın almak için kullanılır. Performans düşüşü yazılımların kullanılamaz hale gelmesine neden olabilir ve insanların bilgi işlem sistemleriyle ilgili temel şikayeti çok yavaş olmalarıdır. Bu nedenle, performans içsel bir değere sahip olmasa da, geliştiricilerin önemsediği şeylere katkıda bulunur.

  • 00:05:00 Bu bölümde konuşmacı, bilgi işlemde performans mühendisliğinin tarihini ve sınırlı makine kaynakları nedeniyle yoğun performans mühendisliğinin ilk günlerinden, çip yoğunluklarının her iki yılda bir iki katına çıktığı ve bekleyen Moore Yasası dönemine geçişi tartışıyor. donanımın yetişmesi, yazılımı optimize etmekten daha faydalıydı. Ancak konuşmacı, gücü azaltarak saat hızlarının artmasına izin veren Dennard ölçeklendirmesinin 2004 yılında sona erdiğini ve bu nedenle performans mühendisliğine olan ihtiyacın her zamankinden daha önemli olduğunu belirtiyor. Konuşmacı, bilgisayar bilimcileri Donald Knuth, Bill Wolfe ve Michael Jackson'dan okunabilir kodun önemi ve erken optimizasyona karşı uyarılar hakkında alıntılar içerir.

  • 00:10:00 Bu bölümde konuşmacı, performansı ölçeklendirmek için çok çekirdekli işlemcilerin geliştirilmesiyle sonuçlanan güç yoğunluğu nedeniyle 2000'lerin başında ulaşılan saat hızı sınırlarını tartışıyor. Ancak bu, performansın artık ücretsiz olmadığı ve endüstrinin daha önce yaptığı bir şey olmayan paralel programlama gerektirdiği anlamına geliyordu. Bu noktadan itibaren, yazılımın etkili olabilmesi için yeni donanım yapılandırmalarına uyum sağlaması gerekiyordu ve bunun sonucunda yazılım geliştirme işlerinde performansa daha fazla odaklanıldı.

  • 00:15:00 Bu bölümde konuşmacı, modern donanımı verimli bir şekilde kullanan yazılım yazmayı öğrenmenin pratik ve teorik önemini açıklayarak başlar. Daha sonra, iyi çalışılmış matris çarpma problemini kullanarak bir performans mühendisliği örneği sunarlar, kullanacakları makineyi paralel işleme, önbellek boyutu ve bellek kapasitesi gibi özellikleri ve yetenekleri dahil tartışırlar ve bir açıklama ile bitirirler. matris çarpımı için Python'un temel kodu. Konuşmacı, makinenin gücünü ve onun yeteneklerini kullanan eğlenceli projelerin potansiyelini vurguluyor.

  • 00:20:00 Bu bölümde öğretim görevlisi, matris çarpımı bağlamında Python, Java ve C++ performansını tartışır. Ders, Python'un yaklaşık 21.000 saniyelik çalışma süresiyle büyük matris çarpımı için çok yavaş olduğunu, Java'nın daha hızlı olduğunu ve Python'a göre neredeyse dokuz kat daha fazla hızlanma ürettiğini ve C++'nın yaklaşık 1.100 saniyelik çalışma süresiyle en hızlısı olduğunu gösteriyor. Java'dan iki kat, Python'dan 18 kat daha hızlıdır.

  • 00:25:00 Bu bölümde, konuşmacı Python gibi yorumlanan diller, C gibi derlenmiş diller ve bytecode'a derlenen ve sonra yorumlanan Java gibi diller arasındaki performans farklarını tartışır. Python gibi yorumlayıcılar çok yönlü ancak yavaştır, oysa C gibi derleyiciler performansı optimize etmek için donanım ve makine yönergelerinden yararlanır. Java'da kullanılanlar gibi JIT derleyicileri, yalnızca en sık çalıştırılan kod parçalarını derleyerek performansın bir kısmını kurtarır. Konuşmacı, Python'un performans modelini anlamanın zor olduğunu, bu nedenle kursta performans karşılaştırmaları için C'yi kullanacaklarını belirtiyor. Ancak, Python gibi yönetilen dillerde performans mühendisliğini tartışacakları bir konuk dersi olacak.

  • 00:30:00 Bu bölümde, matris çarpımında performans için döngü sırasının önemi tartışılmaktadır. Döngülerin sırası, çalışma süresini etkileyen önbellek konumunu etkiler. Matrisler, C'de satır ana düzeninde ve Fortran'da sütun ana düzeninde bellekte düzenlenir. ijk siparişi için erişim modeli, C için iyi bir uzamsal konuma sahiptir, ancak B için zayıf bir uzamsal konuma sahiptir. "cachegrind" aracı, kod için kayıp oranlarını belirlemek için kullanışlıdır ve derleyici bayraklarını ayarlamak gibi basit değişiklikler de performansı artırabilir.

  • 00:35:00 Bu bölümde, konuşmacı bir makineden daha iyi performans elde etmek için kodun nasıl optimize edileceğini tartışıyor. -O2 veya -O3 gibi iyi bir optimizasyon bayrağı seçmek önemlidir, ancak bazen daha düşük bir optimizasyon bayrağı aslında koda bağlı olarak daha iyi optimizasyon sağlayabilir. Ek olarak, çok çekirdekli işlemciler ipek altyapı kullanılarak paralel döngülerle kullanılabilir ve bu da 18 çekirdekte neredeyse 18x hızlanma sağlar. Konuşmacı, dış döngüleri paralelleştirmenin, programı gerçekten yavaşlatabilen iç döngüleri paralelleştirmekten daha etkili olduğunu vurgular. Bununla birlikte, önbellek eksiklikleri ve vektörleştirilmiş yönergelerin etkili bir şekilde kullanılmaması gibi optimizasyon için hala fırsat kaynakları vardır.

  • 00:40:00 Bu bölümde konuşmacı, önbellekteki verileri mümkün olduğunca yeniden kullanmak için hesaplamayı yeniden yapılandırarak önbellek kayıplarının nasıl daha iyi yönetileceğini tartışıyor. Döşeme şeması kullanılarak, matrisler daha küçük alt matrislere bölünür ve gereken bellek erişimi sayısını azaltmak için bloklar halinde çarpılır. Konuşmacı, alt matrislerin boyutunu belirlemek için bir ayarlama parametresinin gerekli olduğunu açıklıyor ve optimum değeri bulmanın en iyi yolunun deney yapmak olduğunu öne sürüyor. Bu yaklaşım sayesinde konuşmacı, aynı boyuttaki ayak izini hesaplamak için gereken bellek erişimi sayısını önemli ölçüde azaltmanın mümkün olduğunu ve hesaplamayı daha verimli hale getirmenin mümkün olduğunu gösteriyor.

  • 00:45:00 Bu bölümde konuşmacı, matris çarpımını gerçekleştirirken engelleme veya döşeme kullanmanın gelişmiş önbellek kullanımı ve daha hızlı çalışma süresi gibi faydalarını tartışıyor. Çiplerin sahip olduğu farklı önbellek düzeylerini ve programcıların kodlarını her bir önbellek düzeyi için optimize etmek üzere ayar parametrelerini nasıl kullanabileceklerini açıklarlar. Ancak, ayarlama işlemi önbelleğin her düzeyinde daha karmaşık hale gelir ve kodun okunması ve anlaşılması zorlaşabilir. Konuşmacı, daha küçük alt problemleri yinelemeli olarak çözmek için paralel programlamayı kullanan bir böl ve fethet yaklaşımı önerir. Bu yöntem önbellek kullanımını iyileştirse de, işlev çağrılarının ek yükü hesaplamayı yavaşlatarak akıllı performans mühendisliğine duyulan ihtiyacı vurgular.

  • 00:50:00 Bu bölümde, konuşmacı böl ve fethet tekniğini kullanarak matris çarpımını optimize etmeyi ve algoritmayı kullanmak için eşiği ayarlamayı tartışıyor. Eşiğin belirli bir sayının altında olduğu durumlar için bir temel durum belirlenir ve algoritma sıradan matris çarpımını kullanır. Temel durum için en iyi değerin 32 olduğu bulundu, bu da 1,3 saniyelik bir çalışma süresi ve %12'lik en yüksek performansla sonuçlandı. Ek olarak, konuşmacı, verileri tek bir talimatta, çoklu veri formatında işleyen vektör donanımını kullanarak vektörleştirme kavramını tanıtıyor. Konuşmacı, vektörleştirme raporlarını kullanmak, belirli mimariler için bayraklar ve derleyicinin ilişkilendirmeleri yeniden sıralamasına olanak tanıyan hızlı matematik bayrağı dahil olmak üzere vektörleştirmeyi optimize etmenin farklı yollarını ana hatlarıyla belirtir. Mimariye özgü ve hızlı matematik kullanımı, herhangi bir derleyici vektörleştirici kullanıldığında performansı iki katına çıkarır.

  • 00:55:00 Videonun bu bölümünde, konuşmacı aritmetik hesaplamalar için kullanılan çeşitli bit boyutlarını tartışıyor, 64 bit doğrusal cebir hesaplamaları için en yaygın olanı. Ayrıca, performansı artırmak için AI uygulamalarında daha düşük hassasiyetli aritmetiğin kullanılabileceğini belirtiyorlar. Konuşmacı, %41'e varan en yüksek performans ve yaklaşık 50.000'lik bir hızlanma sağlayan vektör talimatları ve AVX esaslarının kullanımı hakkında konuşmaya devam ediyor. Matris çarpımında elde edilenlere benzer performans iyileştirmelerinin diğer alanlarda görülmeyebileceğine dikkat çekiyorlar, ancak bu ders öğrencilere kendi başlarına nasıl önemli performans iyileştirmeleri elde edeceklerini öğretecek. Ek olarak, kurs, GPU'lar veya diğer alanlardan ziyade çok çekirdekli hesaplamaya odaklanacaktır.
1. Introduction and Matrix Multiplication
1. Introduction and Matrix Multiplication
  • 2021.10.06
  • www.youtube.com
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Charles LeisersonView the complete course: https://ocw.mit.edu/6-172F18YouTube Pl...
 

Ders 2. Çalışmayı Optimize Etmek İçin Bentley Kuralları



2. Çalışmayı Optimize Etmek İçin Bentley Kuralları

Bu YouTube videosu, bilgisayar programları için çeşitli optimizasyon tekniklerini tartışıyor. İşi optimize etmeye yönelik Bentley kuralları tanıtılır ve optimizasyonlar veri yapıları, döngüler, mantık ve işlevler olarak gruplandırılır. Kodlama değerleri, veri yapısını büyütme, ön hesaplama, önbelleğe alma ve seyrek matrisleri kullanma gibi farklı teknikler tartışılır. Konuşmacı ayrıca grafikler, mantık optimizasyonu ve grafik programlarında çarpışma algılama optimizasyonu için seyrek matris gösterimi kullanmanın faydalarına da değiniyor. Bu optimizasyon tekniklerini uygulamak, programların çalışma sürelerini azaltarak onları daha verimli hale getirmeye yardımcı olur.

Videonun ikinci kısmı, döngü kaldırma, döngülerde nöbetçilerin kullanımı, döngü açma ve füzyon ve işlev satır içi dahil olmak üzere çeşitli optimizasyon teknikleri kategorilerini kapsar. Konuşmacı erken optimizasyona karşı tavsiyede bulunur ve doğruluğu korumanın ve regresyon testi kullanmanın önemini vurgular. Video ayrıca üretkenliği artırmaya ve hedeflere verimli bir şekilde ulaşmaya yönelik altı adımlı bir kılavuz olan Bentley İşi Optimize Etme Kurallarını da özetliyor. Bu kurallar, net hedefler belirlemeyi, görevleri parçalara ayırmayı, planlamayı ve organize etmeyi, görevlere öncelik vermeyi, dikkat dağıtıcı unsurları en aza indirmeyi ve kişinin yaklaşımını düzenli olarak gözden geçirmeyi ve ayarlamayı içerir.

  • 00:00:00 Bu bölümde, öğretim görevlisi bilgisayar programlarında işi optimize etme kavramını tanıtıyor ve bir programın işini azaltmanın performansını nasıl iyileştirebileceğini açıklıyor. Ayrıca verimli programlar yazmak üzerine bir kitap yazan John Lewis Bentley'in adını taşıyan Bentley'in işi optimize etmeye yönelik kurallarından da bahsediyor. Optimizasyonlar dört kategoride gruplandırılmıştır: veri yapıları, döngüler, mantık ve işlevler ve öğretim görevlisi kurs boyunca bir dizi mini derste 22 kuralın tamamını ele almayı planlıyor. Bir programın çalışmasını azaltmak, çalışma süresini iyileştirmek için iyi bir buluşsal yöntem olsa da, bilgisayar donanımının karmaşık doğası, bunun her zaman çalışma süresinde bir azalmaya dönüşmediği anlamına gelir; kurs.

  • 00:05:00 Videonun bu bölümünde konuşmacı, bir makine sözcüğünde birden fazla veri değeri depolamak ve veri değerlerini daha az bit gerektiren bir gösterime dönüştürmek için veri yapılarını paketleme ve kodlama kavramını tartışıyor. Bellekte taşınacak şeylerin sayısını azaltarak, bir programın çalışma süresini azaltmak için iyi bir buluşsal yöntem haline gelir. Konuşmacı, belirli bir tarih için ay, yıl veya günü getirmeyi kolaylaştırmak için daha az bit kullanarak tarihleri depolamak için kodlama örnekleri sağlar. Konuşmacı, yapılandırılmış verileri depolamak ve daha erişilebilir hale getirmek için C'deki bit alanları olanaklarını kullanmayı önerir. Bu temsil, biraz daha fazla bit gerektirir, ancak yapı içindeki belirli veri değerlerine erişimde çok daha etkilidir.

  • 00:10:00 Bu bölümde, video üç optimizasyon tekniğini tartışıyor. İlk teknik, değerleri sıralı tamsayılar olarak kodlamaya veya daha hızlı erişim için paketinden çıkarmaya karar vermektir. İkinci teknik, bir veri yapısına bilgi eklemenin ortak işlemleri optimize edebildiği veri yapısı büyütmedir. Bir örnek, iki listenin eklenmesini daha verimli hale getirmek için tek bağlantılı bir listeye kuyruk işaretçisi eklemektir. Üçüncü teknik, görev açısından kritik zamanlarda hesaplamaları yapmaktan kaçınmak için hesaplamaları önceden yapmak olan ön hesaplamadır. Bir örnek, onları kullanan programı hızlandırmak için binom katsayılarını önceden hesaplamak için Pascal üçgenini kullanmaktır.

  • 00:15:00 Bu bölümde konuşmacı, özyinelemeli bir formül ve C kodu kullanarak Pascal üçgeninin önceden nasıl hesaplanacağını tartışıyor. Özyinelemeli formülün seçme işlevini çağırmayı ve çalışma zamanında bir döngü kullanarak tablonun önceden nasıl hesaplanacağını açıklarlar. Ek olarak, programın yürütülmesi sırasında zaman kazandıran kaynak koduna tablo değerlerini koyarak tablonun derleme zamanında nasıl başlatılacağını tartışırlar. Son olarak, programın yürütülmesi sırasında erişilebilen 10'a kadar binom katsayılarının örnek bir tablosunu sağlarlar.

  • 00:20:00 Bu bölümde, konuşmacı, büyük sabit değerler tablolarını bir programa manuel olarak yazmaktan kaçınmanın bir yolu olarak meta programlama kavramını tanıtıyor. Gerekli kodu üreten bir program yazılarak, sıkıcı görev otomatik olarak yapılabilir. Konuşmacı, örnek olarak bir Python kod parçası sağlar. Son zamanlarda erişilen sonuçları bir önbellekte saklayarak maliyetli hesaplamaları tekrarlamaktan kaçınmanın bir tekniği olarak önbelleğe alma konusu da tanıtılır. Verilen örnek, önbelleğin a ve b değerleri ile birlikte önceki hipotenüsleri önceden depoladığı karekök operatörünü kullanarak bir dik üçgenin hipotenüsünü hesaplamaktır. Hipotenüs işlevi önce giriş değerlerinin önbellektekilerle eşleşip eşleşmediğini kontrol eder ve öyleyse, karekökü yeniden hesaplamak zorunda kalmadan önbelleğe alınan değeri döndürür.

  • 00:25:00 Bu bölümde, konuşmacı bir programda çalışmayı optimize etmek için önbelleğe alma kavramını tartışıyor. Yaygın olarak hesaplanan değerleri bir önbellekte depolayan programlar, aynı değerleri tekrar tekrar hesaplamak zorunda kalmadan zamandan tasarruf edebilir. Donanım aynı zamanda önbelleğe alma işlemi yaparken, yazılım da bunu yapabilir; örneğin, en son hesaplanan 1.000 değeri depolayan 1.000 boyutunda bir önbellek. Aynı değerler tekrar tekrar hesaplanırsa, optimizasyon bir programı yaklaşık %30 hızlandırabilir. Konuşmacı daha sonra, o girdinin sıfır öğeleri üzerinde hesaplama yapmaktan kaçınmak ve böylece hesaplama süresinden tasarruf etmek için bir girdideki seyrekliği kullanma fikrini sunar. Bunu bir matris vektör çarpımı örneğiyle gösteriyorlar ve matrislerin çarpımını hızlandırabilen sıkıştırılmış seyrek Satır (CSR) veri yapısını tanıtıyorlar.

  • 00:30:00 Bu bölümde konuşmacı, Sıkıştırılmış Seyrek Sıra (CSR) formatını kullanarak seyrek matrislerin depolama ve hesaplama verimliliğinin nasıl optimize edileceğini tartışıyor. CSR biçimi, bir matrisin sıfır olmayan öğelerini üç dizide saklar: değerler dizisi, sütunlar dizisi ve satırlar dizisi. Konuşmacı, bir satırın uzunluğunun nasıl hesaplanacağını ve CSR formatını kullanarak matris-vektör çarpmasının nasıl gerçekleştirileceğini açıklar. Sıfır olmayan öğelerin sayısı N^2'den önemli ölçüde azsa, CSR formatı yoğun matris temsilinden daha fazla alan verimli olabilir. Bununla birlikte, nispeten yoğun matrisler için, yoğun matris gösterimi daha az yer kaplayabilir. Konuşmacı, CSR formatını kullanarak matris-vektör çarpımını gerçekleştirmek için bir kod örneği sağlar.

  • 00:35:00 Bu bölümde eğitmen, bir grafiği temsil etmek için seyrek bir matris kullanmanın faydalarını ve genişlik öncelikli arama ve PageRank gibi klasik grafik algoritmalarını daha verimli bir şekilde çalıştırmak için nasıl kullanılabileceğini tartışıyor. Seyrek grafik temsili iki diziden oluşur: her tepe noktasının derecesinin ardışık ofsetler arasındaki fark alınarak elde edilebildiği ofsetler ve kenarlar. Kenarların ağırlığı ayrıca ayrı bir dizide saklanabilir veya önbellek konumunu iyileştirmek için kenarlarla serpiştirilebilir. Bu bölüm, çalışma süresini azaltmak için derleme sırasında sabit ifadeleri değerlendiren özellikle sabit katlama ve yayma olmak üzere mantık optimizasyonlarına kısa bir girişle sona erer.

  • 00:40:00 Videonun bu bölümünde konuşmacı, sürekli katlama ve yayma, ortak alt ifade eleme ve cebirsel kimliklerden yararlanma dahil olmak üzere kod için farklı optimizasyon tekniklerini tartışıyor. Derleyici, derleme zamanında sabitleri tanımlayarak bunları değerlendirebilir ve çalışma süresi boyunca zamandan tasarruf edebilir. Ortak alt ifade eleme, sonucu ileride kullanmak üzere saklayarak aynı ifadeyi birden çok kez hesaplamaktan kaçınmaya olanak tanır. Cebirsel kimliklerden yararlanmak, daha pahalı ifadeleri daha ucuz alternatiflerle değiştirmeyi içerir. Konuşmacı, derleyicinin bu optimizasyonları uygulamada genellikle iyi olmasına rağmen, derleyicinin bunu otomatik olarak yapmadığı durumlar için bunları bilmenin yine de önemli olduğunu vurgular.

  • 00:45:00 Videonun bu bölümünde, konuşmacı iki optimizasyon tekniğini tartışıyor. Birincisi, kareköklerden kaçınmak için cebirsel özdeşlikler kullanarak hesaplama açısından pahalı olan karekök operatörünün kullanımını azaltmaktır. İkinci optimizasyon tekniği, bir dizinin negatif olmayan tamsayılar içerdiği ve dizideki değerlerin toplamının bir karşı kontrol edilmesi gerektiği durumda, sonuç öğrenilir öğrenilmez bir dizi testi durdurmayı içeren kısa devredir. limit. Optimizasyon, dizideki tüm öğelere bakma ihtiyacını ortadan kaldırabilir ve programın yürütülmesini hızlandırabilir, ancak testin ne zaman kısa devre yapılabileceği sıklığına bağlı olarak mantıklı bir şekilde kullanılmalıdır.

  • 00:50:00 Bu bölümde video, kısa devre yapan mantıksal operatörler kavramını ve bunların kodu optimize etmedeki faydalarını tartışıyor. Çift ve işareti ve çift dikey çubuk, argümanın yalnızca bir tarafını değerlendirerek zamandan ve kaynaklardan tasarruf sağlayabilen, kısa devre yapan mantıksal işleçlerdir. Ayrıca video, testlerin başarı sıklıklarına ve yürütme maliyetlerine göre sipariş edilmesini önerir. Bu yaklaşım, daha ucuz testler zaten başarısız olursa, pahalı testleri atlamak için kısa devreden faydalanabilir. Son olarak, video, bir sonuç zaten biliniyorsa bir programdan erken çıkmak için kontrolleri kullanarak hızlı bir yol oluşturma fikrini tanıtıyor. Bunun bir örneği, diğer çarpışma koşullarını kontrol etmeden önce iki topun sınırlayıcı kutularının kesişip kesişmediğini kontrol etmektir.

  • 00:55:00 Bu bölümde Bentley, grafik programlarında çarpışma tespiti için testleri optimize etmenin yollarını tartışıyor. Çarpışma için daha pahalı olan testi gerçekleştirmeden önce sınırlayıcı kutuların kesişip kesişmediğini belirlemek için bir hızlı yol testi önerir. Bu test, her koordinattaki farkın mutlak değerinin kontrol edilmesini ve iki yarıçapın toplamından büyük olup olmadığının kontrol edilmesini içerir. Bentley ayrıca, testleri tek bir anahtar deyimiyle veya hatta tablo aramalarıyla birleştirmenin performansı büyük ölçüde artırabileceğini belirtiyor. Genel olarak, bu optimizasyonlar birçok uygulama ve grafik programı için faydalı olabilir.

  • 01:00:00 Bu bölümde video, döngülerle ilgili üçüncü optimizasyon kategorisini ele alıyor. Tartışılan ilk döngü optimizasyonu, döngü gövdesi boyunca her seferinde döngü değişmez kodunu yeniden hesaplamaktan kaçınmayı içeren kaldırmadır. Bir ifadeyi her yinelemede yeniden hesaplamak yerine bir kez hesaplayıp bir değişkende saklayarak çalışma süresinden tasarruf edebilir. İkinci döngü optimizasyonu, sınır koşullarının işlenmesini ve döngü çıkış testlerini işleme mantığını basitleştirmek için veri yapılarına yerleştirilen özel kukla değerler olan koruyucuların kullanılmasıdır. Programı dizide iki ek giriş kullanacak şekilde değiştirerek, döngünün her yinelemesinde yalnızca bir denetim gerçekleştirmesi gereken bir nöbetçi kullanılabilir.

  • 01:05:00 Bu bölümde, konuşmacı kodu optimize etmek için iki teknik tartışıyor: sınır koşulları ve döngü açma. Sınır koşulları için, giriş dizisinin tüm öğeleri sıfır olduğunda özel durumu verimli bir şekilde işlemek için bir döngünün nasıl değiştirileceğini gösterir. Dizinin sonuna boş bir öğe ekleyerek ve bir taşma olup olmadığını kontrol ederek, kod ne zaman durması gerektiğini algılayabilir. Döngü açma için iki tür açıklıyor: tam ve kısmi. Daha büyük döngü boyutları nedeniyle tam döngü açma nadir olsa da, kısmi döngü açma, birkaçını tek bir döngüde birleştirerek bir döngünün yineleme sayısını azaltır; bu, yürütülen kontrol akışı talimatlarının sayısını azaltarak performansı artırabilir.

  • 01:10:00 Bu bölümde, eğitmen loop unrolling ve loop fusion optimizasyonlarını tartışıyor. Döngü açma, bir döngünün birden çok yinelemesini tek bir yinelemede birleştirmeyi içerir, böylece döngü denetimi yükünü azaltır ve daha fazla derleyici optimizasyonu sağlar. Ancak, çok fazla açma yönerge önbelleğini kirleterek performansı olumsuz etkileyebilir. Öte yandan döngü füzyonu, aynı dizin aralığındaki birden çok döngüyü tek bir döngüde birleştirerek döngü denetimi ek yükünü azaltır ve önbellek konumunu iyileştirir. Eğitmen ayrıca, boş döngü gövdeleri üzerinde döngü yinelemelerinin yürütülmesini önlemek için döngü sınırlarını değiştirerek boşa giden yinelemelerin ortadan kaldırılmasını tartışır.

  • 01:15:00 Bu bölümde Bentley, işlev optimizasyonlarını, özellikle de bir işlev çağrısının ek yükünden kaçınmak için satır içi oluşturma kavramını tartışıyor. Derleyici, bir işlevi statik satır içi olarak bildirerek, işleve yapılan çağrıyı işlevin gövdesiyle değiştirmeye çalışacak ve bu da ayrı bir işlev çağrısı ihtiyacını ortadan kaldıracaktır. Makrolar da bunu yapabilirken, satır içi işlevler daha yapılandırılmıştır ve tüm bağımsız değişkenlerini değerlendirerek bir makronun pahalı bir ifadeyi koda birden çok kez yapıştırma riskini ortadan kaldırır. Bentley erken optimizasyona karşı tavsiyede bulunur ve geliştiricileri önce programlarının doğru olduğundan emin olmaya ve doğruluğu korumak için regresyon testini kullanmaya teşvik eder. Son olarak, birçok optimizasyon seviyesinin derleyici tarafından otomatikleştirilebileceğine ve montaj kodunun kontrol edilmesinin bu tür optimizasyonları ortaya çıkarabileceğine dikkat çekiyor.

  • 01:20:00 Bu bölümde, Çalışmayı Optimize Etmeye Yönelik Bentley Kuralları, altı adımdan oluşan bir dizi halinde özetlenmiştir. Bu kurallar, net hedefler belirlemek, görevleri daha küçük parçalara bölmek, planlamak ve organize etmek için zaman ayırmak, görevlere öncelik vermek, dikkat dağıtıcı unsurları en aza indirmek ve yaklaşımınızı düzenli olarak gözden geçirip ayarlamaktan oluşur. Bu yönergeleri izleyerek üretkenliğinizi artırabilir ve hedeflerinize daha verimli bir şekilde ulaşabilirsiniz. Ek olarak, bu stratejileri günlük rutininize dahil etmek, güçlü bir iş ahlakını korumanıza ve hedeflerinize odaklanmanıza yardımcı olabilir.
2. Bentley Rules for Optimizing Work
2. Bentley Rules for Optimizing Work
  • 2019.09.23
  • www.youtube.com
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Julian ShunView the complete course: https://ocw.mit.edu/6-172F18YouTube Playlist...
 

Ders 3. Bit Hack'leri



3. Bit Hack'leri

Bu YouTube videosu, ikili temsil, ikinin tümleyeni, bitsel operatörler, geçici değişken olmadan değişkenleri takas etme ve kod optimizasyonu dahil olmak üzere çeşitli bit işleme konularını kapsar. Video, if-else deyimlerini kullanmadan en az iki tam sayıyı bulma ve geçici bir değişken kullanmadan iki tam sayının yerini değiştirme gibi çeşitli bit numaralarını gösterir. Konuşmacı, öngörülemeyen dalları tartışır ve öngörülebilir dalların kullanılamadığı durumlar için dalsız minimum bit hilesi sunar ve bölme gibi maliyetli işlemleri basit bitsel işlemlerle değiştirerek bit korsanlarının kodu nasıl optimize edebileceğini gösterir. Video ayrıca de Bruijn dizisini ve bunun N Queens problemi gibi problemlerin çözümündeki uygulamasını tartışıyor.

İkinci kısım, bit vektörlerini kullanarak N Queens problemini çözmeyi ve bir ikili kelimedeki 1 bit sayısını verimli bir şekilde saymayı tartışır. N Queens problemini uygulamak için geri izleme kullanılır ve tahtayı verimli bir şekilde temsil etmek için bit vektörleri kullanılır. N Queens probleminde bir kraliçeyi güvenli bir şekilde yerleştirmek için üç kontrol açıklanır ve en önemsiz 1 biti yinelemeli olarak eleyerek bir kelimedeki 1 bit sayısını saymak için bir yöntem sunulur. Ek olarak, 1 bit sayısını saymak için tablo arama ve kayıt manipülasyonunun kullanımı tartışılmaktadır. Video, kelime uzunluğunun log tabanı ikisiyle orantılı bir performansa sahip 1 biti saymaya yönelik bir böl ve fethet yaklaşımının bir gösterimiyle sona erer. Daha fazla öğrenme için kaynaklar da sağlanmaktadır.

  • 00:00:00 Bu bölümde, kelimelerin ikili temsilini ve bunlardan tamsayı değerlerinin nasıl hesaplanacağını öğreniyoruz. Ayrıca, işaretli tamsayılar için ikisinin tümleyen temsilini ve tamamı sıfırlar ve hepsi birler kelimesinin özel hallerini de öğreniyoruz. Ayrıca, X'in birler tümleyeni için önemli bir özdeşlik ve ikinin tümleyen gösteriminde X'in negatifiyle olan ilişkisini görüyoruz.

  • 00:05:00 Bu bölümde sunum yapan kişi Birler Tümleyenini ve Birler Tümleyenine 1 ekleyerek bir sayının negatifinin nasıl elde edileceğini açıklar. Ayrıca, büyük ikili sabitleri temsil etmek için onaltılık sayıların kullanımının üzerinden geçiyor ve onaltılık ile ikili arasında dönüştürme için bir tablo veriyor. Video daha sonra C++'daki bitsel işleçlerin üzerinden geçer ve bunların mantıksal ve, mantıksal veya, özel veya ve sola ve sağa kaydırma işlemleri için nasıl kullanılacağına ilişkin örnekleri gösterir.

  • 00:10:00 Bu bölümde video, C'de bitsel işleçler kullanılarak uygulanabilen çeşitli yaygın deyimleri tartışır. Bir örnek, bir X sözcüğündeki durum bitini, ardından bir VEYA veya DEĞİL ve ardından bir kaydırma kullanarak ayarlamak veya temizlemektir. VE sırasıyla. Başka bir örnek, istenen bitlerin konumlarında birler ve başka bir yerde sıfırlar olan bir maske oluşturarak, ardından maskeyi X ile AND yaparak ve çıkarılan bitleri sağa kaydırarak bir X kelimesinden bir bit alanı çıkarmaktır. Video ayrıca, bu hileleri kullanmanın özellikle sıkıştırılmış veya kodlanmış verilerle çalışırken yararlı olabileceğinden de bahsediyor.

  • 00:15:00 Bu bölümde video, bazı bit hileleri kullanarak geçici bir değişken kullanmadan iki tamsayının nasıl değiş tokuş edileceğini tartışıyor. Kod, X'i X'e XOR Y'ye, ardından Y'yi X XOR Y'ye ve son olarak X'i X XOR Y'ye eşit olarak ayarlamayı içerir. Bu işe yarar çünkü XOR kendi tersidir ve ilk satır, X'teki bitlerin olduğu birlerle bir maske oluşturur. ve Y farklıdır, bu daha sonra Y'de X'ten farklı olan bitleri çevirmek için kullanılır. Bu, geçici bir değişken kullanılmadan değiş tokuşa izin verir. Video ayrıca bu hilelerle çalışırken güvenliği sağlamak için maskelemenin önemini vurguluyor.

  • 00:20:00 Bu bölümde, konuşmacı iki bit hackini tartışıyor. İlk hack, geçici bir değişken kullanmadan iki değişkeni takas etme yöntemidir. Hack, iki değişken arasında farklılık gösteren bitleri çevirmek için XOR ve bir maske kullanmayı içerir. Bu hack harika olsa da, zayıf talimat seviyesi paralelliği nedeniyle değişkenleri değiştirmenin en etkili yolu değildir. İkinci hack, şube yanlış tahmininden dolayı performans sorunlarına neden olabilecek if-else deyimlerini kullanmadan en az iki tam sayıyı bulmanın bir yoludur. Bunun yerine konuşmacı, tamsayıları karşılaştırmak ve dallanma olmadan minimumu hesaplamak için bitsel işlemlerin nasıl kullanılacağını gösterir.

  • 00:25:00 Bu bölümde, konuşmacı kod optimizasyonunu ve iki sıralanmış diziyi birleştiren bir alt programda "restrict" anahtar sözcüğünün kullanımını tartışıyor. İşlem, iki yeşil dizinin bir mavi dizide birleştirildiği bir örnekle açıklanmaktadır. Koddaki her dalın tahmin edilebilirliği de tartışılır, birinci dal tahmin edilebilirken ikincisi tahmin edilemez.

  • 00:30:00 Bu bölümde video, programlamadaki öngörülebilir ve öngörülemeyen dalları tartışıyor ve öngörülemeyen dal sorununa bir çözüm olarak dalsız minimum bit hilesini tanıtıyor. İşin püf noktası, a ve b'nin ilk elemanı arasındaki karşılaştırma sonucunu saklamak için "comp" adlı bir değişken kullanmayı ve bir bit hilesi kullanarak a ve b'nin minimumunu almayı içerir. Daha sonra minimum değer C'ye yerleştirilir ve A veya B'nin değeri "comp" değerine göre artırılır veya azaltılır. Video, hilenin bazı durumlarda işe yaramayacağını, ancak derleyicinin ne yaptığını anlamanın yararlı olduğunu ve kelimeler için birçok bit hack'inin vektörler için bit ve word hack'lerine kadar uzanabileceğini ve bu hileler hakkında bilgi sahibi olmayı faydalı kıldığını belirtiyor.

  • 00:35:00 Bu bölümde, video bit hack'lerini ve bunların programlamadaki faydalarını tartışıyor. Verilen örnek, bölme kullanmadan daha hızlı işlemlere izin veren modüler toplama için küçük bir numaradır. Z'yi X ve Y'nin toplamına ayarlayarak ve ardından N'den küçük veya büyük olup olmadığını kontrol ederek, program, aralık içindeyse Z'yi veya Z eksi N'nin sonucunu tekrar aralığa getirmek için döndürebilir. Program, minimuma benzer bir mantık kullanır ve dalın yanlış tahmin edilmesine neden olabilecek öngörülemeyen bir dala sahiptir. Verilen başka bir örnek, N'yi azaltarak, bitsel olarak veya N'nin farklı değerlerle sağa kaydırıldığı işlemleri gerçekleştirerek ve ardından sonunda artırarak bit manipülasyonunu kullanarak bir değeri ikinin en yakın katına yuvarlamanın bir yoludur.

  • 00:40:00 Videonun bu bölümünde, konuşmacı iki bitlik manipülasyon problemlerini tartışıyor. İlk problem, verilen bir n değerinden büyük olan ikinin en küçük kuvvetini bulmayı içerir. Konuşmacı, n eksi bir bitin logaritmasının ayarlandığını garanti etmek için zaten ikinin bir kuvvetiyse, bit manipülasyonunu kullanarak ve n'yi azaltarak bunun nasıl başarılacağını açıklar. İkinci problem, bir X kelimesindeki en az anlamlı olanın maskesini hesaplamayı içerir ve konuşmacı, sonucu X'e ayarlayarak ve bitsel ve negatif X ile işlemi kullanarak bunun nasıl başarılacağını açıklar. Konuşmacı ayrıca indeksi bulmak için kod sunar. X'i bir sabitle çarparak ve sonucu bir tabloda arayarak bitin. Bölüm, konuşmacının bit manipülasyonunu içeren bir matematik sihri yapmasıyla sona erer.

  • 00:45:00 Bu bölümde, bir YouTube videosu, bir grubun kartlar ve bir zille sihirbazlık numarası yaptığını gösteriyor. Oyuncu, seyircilerin zihnini okuduğunu iddia ediyor ve onlardan kartları dağıtmadan önce desteyi kesmelerini istiyor. Oyuncu, her kişinin kartının rengini ve numarasını tahmin eder ve görünüşe göre başarılı olur. Yeteneklerini "harika bir tulum" ve sihirli bir şapka takmanın yanı sıra bir zille havayı temizlemeye bağlıyorlar.

  • 00:50:00 Bu bölümde, de Bruyne dizisini ve 2'nin log tabanı 2'nin hesaplanmasıyla ilişkisini öğreniyoruz. De Bruyne dizisi, K uzunluğundaki her olası bit dizisinin tam olarak oluştuğu döngüsel bir bit dizisidir. dizide bir alt dize olarak bir kez. Bir dönüştürme tablosu kullanarak, de Bruyne dizi sabitini 2'nin kuvvetiyle çarpabilir ve 2'nin gücünün log 2 tabanını hesaplamak için dizinin başında görünen alt dizgiyi çıkarabiliriz. Diziyi sola kaydırarak ve sonra bakarak Dönüştürme tablosundaki alt dizgenin başlangıç konumunu yukarı kaydırarak, daha önce gösterilen kart numarasını çözen, başladığımız tamsayının log tabanı 2'yi belirleyebiliriz.

  • 00:55:00 Bu bölümde konuşmacı, olası her n-bit dizisini tam olarak bir kez içeren bir ikili alfabenin döngüsel dizisi olan de Bruijn dizisini tartışıyor. Dizi, N Queens problemi gibi problemleri çözmek için kullanılabilir ve bir sihir numarası kullanılarak üretilebilir. Konuşmacı ayrıca bir de Bruijn dizisinin bir alt dizisinin sola kaydırmadan sonraki konumunu belirlemek için bit numarasının nasıl çalıştığını da açıklıyor. Bu küçük numaranın performansı, çarpma ve tablo arama performansıyla sınırlıdır, ancak artık onu hesaplamak için bir donanım talimatı vardır.

  • 01:00:00 Bu bölümde, konuşmacı, iki vezir birbirini tehdit etmeyecek şekilde bir NxN satranç tahtasına N satranç veziri yerleştirmeyi içeren N Vezir problemini tartışır. Sorun genellikle kraliçelerin sıra sıra yerleştirildiği ve geçerli bir konum bulunamadığında programın geri gittiği geri izleme kullanılarak uygulanır. Tahtanın farklı temsilleri de tartışılır, en kompakt olanı üç bitlik bir vektör setidir. Aşağı vektör, her sütundaki kraliçelerin varlığını saklar, sol köşegen vektörü, her sol köşegendeki kraliçelerin varlığını saklar ve sağ köşegen vektörü, her sağ köşegendeki kraliçelerin varlığını saklar. Bit vektörlerinin kullanılması, algoritmanın daha verimli bir şekilde uygulanmasına izin verir.

  • 01:05:00 Bu bölümde, bit vektörlerini kullanarak bir n-queens probleminde bir vezir yerleştirmek için bir konumun güvenli olup olmadığını kontrol etme süreci açıklanmaktadır. Üç kontrol, konumla aynı satırda, aynı sütunda ve aynı köşegende hali hazırda bir vezir olup olmadığını kontrol etmeyi içerir. Bu yöntem etkilidir ve üç kontrolü de geçerse bir kraliçenin güvenli bir şekilde yerleştirilebileceğini garanti eder. Tartışılan başka bir sorun, bir X sözcüğündeki 1 bitin sayısını saymayı içeren nüfus sayımıdır. Sunulan yöntem, X'teki en az anlamlı 1 biti sıfır olana kadar tekrar tekrar ortadan kaldırır ve gereken yineleme sayısı, sayıyla orantılıdır. X'te 1 bit.

  • 01:10:00 Bu bölümde konuşmacı, bir ikili sözcükteki 1 bit sayısını verimli bir şekilde saymak için tablo aramanın kullanımını tartışır. Tablo arama yöntemi, her 8 bitlik sözcükteki birlerin sayısını saklayan 256 boyutunda bir tablo oluşturmayı ve ardından ikili sözcükteki her 8 bitlik alt dize için sayıya bakmayı içerir. Konuşmacı, bu yöntemin performansının, tabloya erişmek için gereken bellek işlemleri nedeniyle tıkandığını belirtiyor. Konuşmacı, yazmaçları kullanarak 1 bit sayısını saymanın üçüncü bir yolunu sunarak devam eder; burada maskeler oluştururlar ve belleğe erişmeden ikili bir sözcükteki birlerin sayısını saymalarına izin veren özel yönergeleri yürütürler. Sunum yapan kişi, bu yöntemin nasıl çalıştığını açıklamak için bir örnek üzerinden gider.

  • 01:15:00 Bu bölümde konuşmacı, performansın sözcük uzunluğunun log iki tabanı W ile orantılı olduğu paralel bir böl ve fethet yöntemi kullanarak bir girdi sözcüğündeki 1'lerin sayısının nasıl sayılacağını gösterir. Modern makinelerin çoğunun, kodlanabilecek her şeyden daha hızlı olan, derleyici içselleri aracılığıyla erişilebilen, içsel bir pop sayımı talimatına sahip olduğuna dikkat çekti. Ancak bu, kodu farklı makinelerde daha az taşınabilir hale getirebilir. Konuşmacı, bit hileleri hakkında daha fazla bilgi edinmek için bir web sitesi, bir ders kitabı, bir satranç programlama web sitesi ve Hacker's Delight adlı bir kitap dahil olmak üzere bazı kaynaklar sağlar.
3. Bit Hacks
3. Bit Hacks
  • 2019.09.23
  • www.youtube.com
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Julian ShunView the complete course: https://ocw.mit.edu/6-172F18YouTube Playlist...
 

Anlatım 4. Assembly Dili ve Bilgisayar Mimarisi



Anlatım 4. Assembly Dili ve Bilgisayar Mimarisi

Bu video, montaj dili ve bilgisayar mimarisine kapsamlı bir genel bakış sağlar. Assembly dili, kod performansını optimize etmek için önemli bir arabirimdir ve bilgisayar mimarisini anlamak, Assembly dilinde uzmanlaşmak için çok önemlidir. Konuşmacı, x86 64 mimarisinin tarihini ve gelişimini, anahtar kayıtlarını, veri türlerini, bellek adresleme modlarını ve yığınlar, tamsayı ve ikili mantık, boole mantığı ve altyordamlar dahil komut seti mimarisini açıklar. Ayrıca, montaj dilinde sıfır ve işaret uzantısı gibi uzantıları ve çeşitli adresleme modlarını tartışırlar. Ayrıca videoda kayan nokta türleri, vektörler ve vektör birimleri, geleneksel ve SSE yönergeleri ile süper skala işleme, sıra dışı yürütme ve şube tahmini gibi bilgisayar mimarisi tasarım özellikleri tartışılıyor.

Video ayrıca, montaj dili ve bilgisayar mimarisi ile ilgili çeşitli konuları da kapsar. Ana temalardan biri, veri bağımlılıkları gibi tehlikelerin neden olduğu komut düzeyinde paralellik (ILP) ve ardışık düzen duraklarıdır. Konuşmacı, gerçek, anti ve çıktı veri bağımlılıklarını ve süper skalar işlemcilerin aynı anda birden fazla talimatı yürütmek için donanımdaki daha fazla paralellikten nasıl yararlanabileceğini tartışıyor. Bununla birlikte, tehlikelerden kaçınmak için mimarlar, yeniden adlandırma ve yeniden sıralama gibi stratejilerin yanı sıra bir dalın sonucunu tahmin etmek ve önceden yürütmek için spekülatif yürütme uygulamışlardır. Konuşmacı, dinleyicileri yazılım optimizasyonlarını daha iyi anlamak için bu yöntemleri anlamaya teşvik eder.

  • 00:00:00 Bu bölümde eğitmen, genellikle modern yazılım derslerinde yer almayan birleştirme dili ve bilgisayar mimarisi hakkında konuşur. Bu kavramları anlamak, kod performansını optimize etmek için gereklidir ve bunu yapmak için en iyi arayüz montaj dilidir. Kod derleme süreci, ön işleme, derleme, birleştirme ve bağlama dahil olmak üzere birkaç aşamadan oluşur. Assembly dili, makine kodunun insan tarafından daha okunabilir olmasını sağlayan anımsatıcı bir yapısıdır ve son yürütülebilir dosya, LD komutu kullanılarak bir bağlantı aşaması aracılığıyla üretilir.

  • 00:05:00 Bu bölümde konuşmacı, montaj ve makine kodunun yapı olarak çok benzer olduğunu, montajdaki OP kodlarının makine kodundaki belirli bit kalıplarına karşılık geldiğini açıklar. Konuşmacı, anımsatıcı, insan tarafından okunabilir montaj kodunu ortaya çıkaran, makine kodunun demonte edilmesini sağlayabilen ABS programını tanıtır. Konuşmacı daha sonra, derleyicinin ne yaptığını ve yapmadığını ortaya çıkarmak, derleyici hatalarında hata ayıklamak ve kaynağına erişimi olmayan bir programda tersine mühendislik yapmak da dahil olmak üzere, birinin neden derleme koduna bakmak isteyebileceğini tartışır.

  • 00:10:00 Bu bölümde, konuşmacı, bir derleyicinin x86 yönergeleriyle dilsel yapıları nasıl uyguladığını anlama, x86 derleme dilini okuyabilme ve genel derleme kalıplarının performans sonuçlarını anlamayı içeren, sınıf için beklentileri açıklar. Öğrenciler ayrıca gerekirse sıfırdan kod yazabilmeli ve bunun mümkün olduğu düzeyde ustalık kazanmalıdır. Konuşmacı daha sonra kayıtlar, yönergeler, veri türleri ve bellek adresleme modları dahil olmak üzere x86 64 komut seti mimarisine dalar. Anahtar kayıtları, genel amaçlı kayıtları ve aritmetik işlemleri izleyen ve taşıyan işaretler kaydını içerir. Talimat işaretçisi, donanıma bir montaj dili programındaki talimat dizisi boyunca rehberlik eder.

  • 00:15:00 Bu bölümde, konuşmacı x86 64 mimarisinin tarihini ve sınırlı belleğe sahip 16 bitlik kelime makinelerinden, daha fazla bellek kullanılabilir hale geldikçe indeksleme için daha geniş sözcüklere doğru gelişimini tartışıyor. Konuşmacı ayrıca vektörleştirme için xmm ve AVX kayıtları gibi vektör kayıtlarının eklenmesini ve bunların nasıl kullanıldığını açıklar. Ayrıca genel amaçlı kayıtlar konusuna ve işlevsel amaçlarının zaman içinde nasıl önemli ölçüde değiştiğine ancak tarihsel nedenlerden dolayı isimlerinin takılıp kaldığına değinirler. Ek olarak, konuşmacı, kısa kelimenin, 32 bitlik veya 64 bitlik kelimelerin alt ve üst yarısı için belirli yazmaçların aynı şeye nasıl takma ad verildiğini açıklar.

  • 00:20:00 Bu bölümde, konuşmacı x86 64 derleme dilinin temellerini ve nasıl çalıştığını açıklıyor. Kayıtların, kaydın hangi kısmına erişildiğine bağlı olarak farklı adları vardır ve bazılarının RSP'nin yığın işaretçisi olarak kullanılması gibi belirli amaçları vardır. Bir x86 64 talimat kodunun formatı, genellikle kaynak veya hedef olabilecek 0-3 işlenen içeren bir işlem koduna ve bir işlenen listesine sahip olmaktır. Konuşmacı, AT&T sözdizimi ile Intel sözdizimi arasındaki işlemlere atıfta bulunan farkı açıklar ve "hareket" ve "koşullu hareket" gibi yaygın işlem kodlarının bir listesini sağlar. Ek olarak, konuşmacı 32 bitlik bir değer kaydından 64 bitlik bir kayda geçerken işareti genişletmenin önemini açıklıyor.

  • 00:25:00 Bu bölümde konuşmacı, yığınlar, tamsayı aritmetiği, ikili mantık, boolean mantığı, atlamalar ve altyordamlar için yönergeler dahil olmak üzere, derleme dilindeki çeşitli komut türlerini tartışır. İşlem kodları, işlemin veri türünü açıklayan bir son ek veya bir koşul kodu ile artırılabilir. Örneğin, "işaret" içeren bir hareket, taşınmakta olan verinin 8 bayt veya 64 bitten oluşan dörtlü bir kelime olduğunu belirtir. x86 64 veri türleri ve bunların derleme ekleri de ele alınmış ve işaret uzantısının nasıl çalıştığını göstermek için örnekler verilmiştir. Assembly dilinde belirli işlem kodlarının ve anımsatıcıların varlığı veya yokluğu kafa karıştırıcı olabilir, ancak derleyicinin programı doğru bir şekilde yürütmek için bu talimatları anlaması gerekir.

  • 00:30:00 Bu bölümde konuşmacı, 32 bit işlemleri 64 bit işlemlere taşırken ortaya çıkan sıfır uzantısı ve işaret uzantısı gibi uzantıları tartışır. Ayrıca Intel komut setinin yeni komutların eklenmesiyle nasıl daha karmaşık hale gelebileceğinden de bahsediyorlar. Konuşmacı, koşullu atlamalarda ve koşullu hareketlerde kullanılan farklı koşul kodlarını ve sıfır bayrağı ve taşma bayrağı gibi bunlarla birlikte kullanılan bayrakları açıklamaya devam eder. Sıfır bayrağını kontrol eden belirli koşul kodlarının nedeni de tartışılmaktadır.

  • 00:35:00 Bu bölümde konuşmacı, Assembly dilinde farklı doğrudan ve dolaylı adresleme modlarını tartışıyor. Doğrudan adresleme modları, anlık, doğrudan bellek ve bir kayıt kullanmayı içerir. Dolaylı kayıt ve indeksli kayıt adresleme modları, adresi bir kayıtta sağlayarak veya adresi kaydırarak belleğe erişime izin verir. Konuşmacı, belleğe erişimin yavaş ve pahalı olabileceğini, bu nedenle, süreci hızlandırmak için mümkün olduğunda değerleri kayıtlara kaydetmenin önemli olduğunu belirtiyor. Ayrıca bellek erişimini optimize etmede önbelleğe almanın öneminden de bahsediyorlar.

  • 00:40:00 Bu bölümde video, yönerge işaretçisinin genel amaçlı bir kayıt defteri yerine verileri dizinlemek için kullanıldığı işaretçi göreli indekslemenin kullanımını tartışıyor. Ayrıca, bir taban işaretçisinden hassas bir şekilde indekslemeyi destekleyen karmaşık bir talimat olan taban indeksi ölçeği yer değiştirme adresleme yöntemi de tanıtılmıştır. Video, yazmaçları sıfırlamak için kullanılan XOR işlem kodu ve bitsel ve iki değeri hesaplayan ve kayıt bayraklarını koruyan test işlem kodu dahil olmak üzere bazı montaj dili deyimlerine genel bir bakış sağlar. Son olarak video, kodda kontrol akışını sağlayan atlama talimatlarına ve etiketlere değiniyor.

  • 00:45:00 Bu bölümde video, çeşitli komut setleri ve kayan nokta tarihçesi de dahil olmak üzere montaj dili ve bilgisayar mimarisini tartışıyor. x87 ve SSE dahil olmak üzere x86 komut setleri, tek ve çift duyarlıklı skaler kayan nokta aritmetiğini ve vektör komutlarını destekler. SSE komutları, derleme ve optimizasyondaki basitlikleri nedeniyle genellikle derleyiciler tarafından x87 yerine tercih edilir. Hizalama optimizasyonu gibi montajda işlem yapılmayan (nop) komutlarının kullanılma amacı da açıklanmaktadır.

  • 00:50:00 Bu bölümde konuşmacı, bilgisayar mimarisinde kullanılan kayan nokta türleri, vektörler ve vektör birimlerini tartışır. Konuşmacı, vektör birimlerinin çalışma şeklinin, işlemcinin tüm vektör birimlerine talimatlar vermesi olduğunu ve bunların her birine şerit adı verildiğini açıklıyor. Kulvarlar, tamsayı veya kayan nokta aritmetiğini içerir ve hepsi aynı şeyi yapar, yani aynı şeyi yapar. Aynı anda birkaç işlem yapabilirler ve tüm bunlar tek bir komutla yapılabilir. Konuşmacı, bazı mimarilerin vektör işlenenlerinin hizalanmasını gerektirdiğini, diğerlerinin ise bellekteki vektörleri değiştirebileceğini ve bunun da ikisi arasında bir performans farkına neden olduğunu açıklıyor. Ek olarak, sıra değiştirme, karıştırma ve dağıtma toplama gibi çapraz şeritli işlemleri destekleyen mimariler vardır.

  • 00:55:00 Bu bölümde, konuşmacı geleneksel ve SSE talimatları arasındaki farkları ve bunların nasıl kullanılabileceğini tartışıyor. Ayrıca, ymm'nin xmm yazmaçlarını kaydettiği ve bunları avx-512 ile 512 bit'e genişlettiği takma ad numarasından da bahsediyorlar. Daha sonra bilgisayar mimarisi, özellikle de beş aşamalı ardışık düzen ile 14 ila 19 ardışık düzen aşaması içeren modern bir işlemci arasındaki fark üzerine bir tartışmaya geçerler. Tartıştıkları tasarım özellikleri arasında vektör veya Donanım I, süper skalar işleme, sıra dışı yürütme ve şube tahmini yer alır, ancak zaman kısıtlamaları nedeniyle sıra dışı yürütmeyi derinlemesine incelemeyeceklerinden bahsederler.

  • 01:00:00 Videonun bu bölümünde eğitmen, komut düzeyi paralelliği (ILP) ve ardışık düzen durmalarını tartışır. ILP, verimi artırmak için birden fazla talimatı aynı anda yürütme fırsatları bulmayı içerir. Bununla birlikte, yapısal tehlike, veri tehlikesi veya kontrol tehlikesi gibi bir tehlike nedeniyle bir talimat yürütülemediğinde boru hattı duraklamaları meydana gelebilir ve en yaygın olanı veri tehlikeleridir. Gerçek bir bağımlılık, bir talimat bir yazma bağımlılığından sonra okuduğunda ortaya çıkarken, bir anti-bağımlılık, bir talimat bir konuma yazmak istediğinde ancak önceki talimatın değeri okumasını beklemek zorunda kaldığında ortaya çıkar. Derleyici, tehlikelerden kaçınmak için kodu optimize ederek boru hattı durmalarını azaltmaya çalışır.

  • 01:05:00 Bu bölümde, Assembly dilindeki veri bağımlılıkları kavramı ele alınmaktadır. Üç tür veri bağımlılığı vardır: true, anti ve output. Aritmetik işlemler, özellikle kayan noktalı aritmetik gibi karmaşık olanlar, daha uzun gecikme süresine sahiptir ve işlemcide bazen ayrı kayıtlara sahip ayrı işlevsel birimler gerektirir. Komut seviyesi paralelliğini artırmak için mimarlar, donanımda daha fazla paralellikten yararlanmak için döngü başına birden fazla talimat yayınlamak gibi teknikler uyguladılar.

  • 01:10:00 Bu bölümde video, Haswell'in talimatları mikro işlemler adı verilen daha basit işlemlere ayırma ve döngü başına dört adede kadar mikro işlem yayan örneğini kullanarak, süper skala işlemcilerin aynı anda birden çok yönergeyi nasıl yürütebileceğini açıklıyor. Video daha sonra, bağımlı olmayan talimatların sıra dışı yürütülmesine olanak tanıyan ve daha hızlı işlem sürelerine yol açan atlama ve kayıt yeniden adlandırma da dahil olmak üzere, işlemcileri talimatları sırayla yürütmekten kurtarmaya yönelik stratejileri detaylandırır. Bu stratejiler, bağımlılıkları takip etmeyi ve veri bağımlılıkları gibi tehlikeleri önleyecek şekilde kod yürütmeyi gerektirir.

  • 01:15:00 Bu bölümde konuşmacı, modern işlemcilerde veri tehlikelerinden kaçınmak için kullanılan iki önemli yöntem olan yeniden adlandırma ve yeniden sıralamayı tartışıyor. Konuşmacı ayrıca dal tahmininde bir dalın sonucunu tahmin etmek ve oyalanmayı önlemek için önceden yürütmek için kullanılan spekülatif uygulamadan da bahsediyor. Bununla birlikte, tahmin yanlışsa, hesaplamayı geri almak yaklaşık 15 ila 20 döngüye mal olacaktır. Konuşmacı, şube tahmincilerinin nasıl çalıştığından kısaca bahseder ancak bunun karmaşık olduğuna ve daha fazla çalışma gerektirdiğine işaret eder. Aceleyle biten sona rağmen, konuşmacı dinleyicileri, belirli yazılım optimizasyonlarının neden işe yarayıp yaramadığını anlamaya yardımcı olacak çeşitli yöntemleri anlamaya teşvik eder.
4. Assembly Language & Computer Architecture
4. Assembly Language & Computer Architecture
  • 2019.09.23
  • www.youtube.com
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Charles LeisersonView the complete course: https://ocw.mit.edu/6-172F18YouTube Pl...
 

Ders 5. C'den Montaja



Ders 5. C'den Montaja

Videonun bu bölümünde, C kodunun bir derleyici kullanarak Assembly dilinde nasıl uygulandığı ile birlikte C'yi anlamanın önemi tartışılıyor. Odak noktası, özellikle LLVM IR'nin Linux x86 64 çağrı kuralında derlemeye nasıl çevrildiğidir. Sunucu, LLVM IR'nin temel bileşenlerini ve C programlama dilindeki yapıların LLVM IR'ye nasıl çevrildiğini açıklar. Video ayrıca sanal belleğin düzenini, birden çok işlev arasındaki işlev çağrılarını koordine etme sorununu ve Linux x86 64 çağırma kuralının tüm yığın çerçevelerini yönetmek için iki işaretçi (BP ve SP) kullanımını kapsar.

Video ayrıca C'den Assembly'ye programlamada kayıt durumlarını korumaya yönelik stratejileri, örneğin arayan kaydetme veya arayan kaydetme olarak kaydetme ve x86 çağırma kuralının iş israfını nasıl önlediğini açıklar. İşlev çağrılarının C ve derlemede nasıl çalıştığını, bağımsız değişkenleri ve yerel değişkenleri yığına kaydetme işleminin yanı sıra taban işaretçisi yerine yığın işaretçisini kullanmanın yaygın optimizasyonunu tartışıyor. Video ayrıca LV miR'yi derleme koduna kadar derleme, işlev girişini tartışma, kayıtları kaydetme, işleme koşulları ve bir kontrol akış grafiği kullanarak C kodunu derleme koduna dönüştürme sürecini de gösterir. Son olarak, sonuçları döndürmeden önce kayıtları geri yüklemek için kullanılan işlev epilogundan bahseder.

  • 00:00:00 Videonun bu bölümünde TB Shuttle, C'yi anlamanın derleme dili için önemini tartışıyor. Assembly dilinin C kodundan daha fazla kesinlik sağladığını ve bir program hakkında C kodundan anlaşılamayan ayrıntıları ortaya çıkarabileceğini belirtiyor. Derlemeye bakmak, geliştiricilerin bir programı optimize ederken derleyicinin ne yaptığını veya yapmadığını belirlemesine de izin verebilir. Ek olarak, belirli seviyelerde kodu optimize ederken yalnızca beklenmeyen davranışlar yaratacak ve bu hataların tespit edilmesini zorlaştıracak hatalar ortaya çıkabilir. Son olarak, montajı anlamak, geliştiricilerin montaj kodunu el ile değiştirmesine veya kodu tersine çevirmesine izin verebilir.

  • 00:05:00 Bu bölümde video, hangi derleme yönergelerinin kullanılacağına, C koşul ve döngülerinin nasıl uygulanacağına ve nasıl uygulanacağına ilişkin karmaşık kararlar vermek zorunda olan bir derleyicinin kullanımı aracılığıyla derleme dilinde C kodunun nasıl uygulandığını tartışır. işlev çağrılarını koordine edin. Çeviri sürecini anlamak için video, derleyicinin program hakkında mantık yürütmek için kullandığı basitleştirilmiş bir derleme olan LVM IR'yi tanıtıyor. Video daha sonra C programlama dilinde fonksiyonlar, koşullu ifadeler ve döngüler gibi yapıların LVM IR'ye nasıl çevrildiğini açıklar. Bu bölüm, LVM IR özniteliklerinden kısaca söz edilerek sona ermektedir.

  • 00:10:00 Bu bölümde, özellikle Linux x86 64 çağırma kuralında, LLVM ir'nin derlemeye nasıl çevrildiği sürecine odaklanılmaktadır. Sunum yapan kişi, LLVM ir hakkında kısa bir giriş yaparak, daha basit bir derleme versiyonuna benzeyen işlevlerin, yönergelerin ve kayıtların temel bileşenlerini açıklar. LLVM ir kayıtları, c değişkenlerine benzer ve adlarıyla ayırt edilirler ve her işlevin kendi yerel kayıt adı vardır. Sunucu, örnek bir kod parçacığında kayıtları vurgular ve LLVM'deki farklı temel bloklara atıfta bulunurken kayıtlar için sözdiziminin ele geçirildiğini not eder. Konuşma, bu sürecin Fibonacci sayılarını hesaplamak için basit bir kod için nasıl çalıştığına dair bir vaka çalışmasıyla sona eriyor.

  • 00:15:00 Bu bölümde konuşmacı, bir kayıt adı, bir eşit sembol, bir işlem kodu ve bir işlenen listesi içeren LV Mir komutlarının sözdizimini açıklar. Bazı komutlar yerel bir kayıtta saklanan bir değer döndürürken diğerleri bunu yapmaz. LV Mir komut seti, veri hareketleri, aritmetik ve mantık işlemleri ve kontrol akışı için yalnızca birkaç komut içerdiğinden x86'nınkinden daha küçüktür. LV Mir'de her şey, tamsayılar (belirli sayıda bit ile), kayan nokta türleri, işaretçi türleri, vektör türleri ve temel bloklar için etiket türleri dahil olmak üzere türler olarak gösterilir. Konuşmacı ayrıca LV Mir vektör işlemlerinin SSE veya AVX gibi görünmediğini, bunun yerine bir vektör türü üzerinde çalışan sıradan işlemler gibi göründüğünden bahseder.

  • 00:20:00 Bu bölümde video, C kodundaki işlem dizilerinin LLVM IR'ye nasıl çevrildiğini ve IR'de kodu yorumlamak için temel kuralları tartışır. Alıntı ayrıca LLVM IR'nin diziler ve yapılar gibi ilkel ve toplu türleri nasıl ele aldığını açıklar ve bir dizideki öğelere erişmenin bellekteki adresleri hesaplamayı nasıl içerdiğine ilişkin örnekleri gösterir. Ayrıca video, her iki dilde karşılık gelen dönüş ifadeleriyle birlikte C işlevlerinin LLVM IR'ye nasıl çevrildiğini açıklar.

  • 00:25:00 Bu bölümde video, C'deki işlev ve parametrelerin LV Mir'e nasıl çevrildiğini açıklar. LV Mir'deki işlevler, C'deki işlevlere benzer, ancak C parametreleri, LV Mir'deki parametre listeleri haline gelir. Ancak, LV Mir'i okumak zor olabilir, çünkü kayıtlar iyi isimlendirilmemiştir ve bu da deşifre etmeyi zorlaştırır. Video ayrıca, kontrol akışı yönergelerine dayalı olarak bölümlenmiş kod parçaları olan LV Mir'deki temel blokları da tartışıyor. Temel bloklar arasındaki bağlantılar dallanma komutları tarafından indüklenen kenarlara dayalıdır. Son olarak video, if-then-else ifadelerinin temel blokları tetikleyen ve akış kenarlarını kontrol eden koşullu dal yönergeleri haline geldiği LV Mir'deki koşullu ifadelere değiniyor.

  • 00:30:00 Bu bölümde videoda koşullu işlemler ve dalların LLVM IR'de nasıl çalıştığı anlatılmaktadır. İşlem, değişmez bir değer ile bir kayıtta depolanan ve bir bitlik bir tamsayı veya boole sonucu oluşturan bir değer arasındaki karşılaştırma ile başlar. Bu sonuç daha sonra, yüklemin doğru veya yanlış olması durumunda nereye gidileceğini gösteren iki temel blok etiketiyle birlikte koşullu bir dal eylemine iletilir. Bir işlenene sahip koşulsuz bir dal varsa, sonuç, belirli bir temel bloğa doğrudan atlamadır. Video ayrıca, koşullu bir ifade olduğunda kontrol akış grafiğinde baklava şeklinin nasıl oluşturulacağını gösterir ve C kodunda yazılmış bir döngü örneği sağlar.

  • 00:35:00 Bu bölümde video, döngü gövdesi ve döngü kontrolünü içeren bir C döngüsünün bileşenlerini tartışıyor. Döngü gövdesi her yinelemede yürütülürken, döngü kontrolü döngünün tüm yinelemelerini yönetir. AC döngüsü, kontrol akış grafiğinde bir döngü modeli üretir ve bu da LLVM ir'de bir döngü yapısı oluşturur. Video daha sonra döngü kontrolü için LLVM ir kodunu analiz eder, burada döngülerle uğraşırken yaygın olarak ortaya çıkan garip bir fie talimatı vardır. fie talimatı, kodun LLVM temsiliyle ilgili bir sorunu çözmeye çalışır, burada ben bir sürü farklı kayıt tarafından temsil edilir ve gerçekte nereye gittiğimi belirsizleştirir.

  • 00:40:00 Bu bölümde video, bir döngüdeki endüksiyon değişkeninin, döngü yinelemeleri boyunca değişkenin değişen değerleri nedeniyle yaptığı LLVM'deki çeşitli konumlara eşlenmesini tartışır. Bu, LLVM'de "statik tek atama" değişmezine yol açar; bu, her talimatın bir kaydın değerini yalnızca bir kez tanımladığı, bu da indüksiyon değişkenleri için bir sorun teşkil eder. "phi" komutu, kontrol akışının bir döngünün giriş noktasında nasıl birleştiğine bağlı olan bir kayıt değeri tanımlayarak bu sorunu çözer. Video ayrıca LLVM'deki öznitelikleri ve bunların "ekle" talimatına eklenen NSW özniteliği gibi LLVM yapıları için nasıl ekstra bilgi sağlayabileceklerini tartışır.

  • 00:45:00 Videonun bu bölümünde, derlemeye benzer ancak birçok yönden daha basit olan LLVM IR'ye odaklanılıyor, çünkü tüm hesaplanan değerler sıradan C değişkenleri gibi kayıt defterlerinde saklanıyor. LLVM IR, her değişkenin en fazla bir talimat tarafından yazıldığı statik tek atama paradigmasını kullanır. Videoda, süreçteki bazı ek karmaşıklıklar ile C kodunun LLVM IR'ye ve ardından derlemeye nasıl çevrileceği açıklanmaktadır. Derleyici, LLVM IR işlemleri için gereken gerçek derleme yönergelerini seçer, hangi genel amaçlı kayıtların kullanılacağına karar verir ve farklı kaynak dosyalar ile ikili kitaplıklar arasındaki işlev çağrılarını koordine eder. Tartışma daha sonra Linux x86 64 çağrı kuralına döner.

  • 00:50:00 Bu bölümde, bir program için sanal belleğin yerleşimi anlatılmaktadır. Sanal bellek, montaj kodunda birleştirici direktiflerinin kullanılmasıyla düzenlenen yığın ve yığın segmentleri gibi segmentlere bölünmüştür. Ek olarak, hafızayı tahsis eden ve değerleri depolayan space direktifi ve uzun segment gibi farklı depolama direktifleri tartışılır. Daha sonra, yerel değişkenlerin, işlev bağımsız değişkenlerinin, dönüş adresinin ve muhtemelen ara sonuçların saklanmasını içeren, işlev çağrılarını ve geri dönüşleri yönetmek için verilerin depolandığı yığın segmentine dikkat çekilir.

  • 00:55:00 Videonun bu bölümünde sunum yapan kişi, bazıları farklı dosyalardan veya kitaplıklardan gelebilen birden çok işlev arasında işlev çağrılarını koordine etme konusunu tartışıyor. Tüm işlevlerin birlikte iyi çalışmasını sağlamak için, tüm işlevlerin uyması gereken bir çağrı kuralı oluşturulmuştur. Linux x86 64 çağırma kuralı, her işlev somutlaştırması için tüm yığın çerçevelerini yönetmek üzere iki işaretçi (BP ve SP) kullanır. Bir çağrı talimatı yürütüldüğünde, IP'nin geçerli değeri, dönüş adresi olarak yığına itilir ve çağrı talimatı, program belleğindeki bazı işlevlerin adresine atlar. İade talimatı, çağrı talimatının işlemlerini geri alır ve arayanın yürütmesine geri dönmek için dönüş adresini yığından çıkarır. Aynı işlevi kullanmak isteyen birden çok işlev sorununu çözmek için
    yazmaçlar, çağırma kuralı, her işlevin hangi yazmaçları kullanabileceğine ilişkin kuralları ve işlev çağrıları yoluyla bu yazmaçları nasıl korumaları gerektiğini ayrıntılarıyla açıklar.

  • 01:00:00 Bu bölümde video, C'den Assembly'ye programlamada farklı işlevlerle çalışırken kayıt durumlarını korumaya yönelik stratejileri tartışıyor. Kullanılabilecek iki yöntemden bahseder; biri, arayanın bir aramayı başlatmadan önce kayıt durumunu kaydettiği, diğeri ise aranan kişinin tüm kayıt durumunu kaydettiği yerdir. x86 çağırma kuralı, işi boşa harcamaktan kaçınmak için bazı kayıtları callee-save ve diğerlerini arayan-save olarak belirterek her ikisini de içerir. Video ayrıca yığın belleğinin nasıl düzenlendiğini ve yığının nasıl büyüdüğünü araştırıyor. Son olarak, işlevlerin yığın belleğinin örtüşen bölümlerini nasıl kullanacağını koordine etmeyi tartışır.

  • 01:05:00 Bu bölümde, video bir işlev çağrısının C ve derlemede nasıl çalıştığını tartışıyor. C işlevini çağırmadan önce B işlevi, C işlevi için kayıt dışı bağımsız değişkenleri yerel değişkenlerinin altındaki kendi yığın belleğindeki ayrılmış bir bağlantı bloğuna yerleştirir. Negatif ofsetlerle bu argümanlara erişecek. C işlevi başladığında, B'nin yığın çerçevesi için temel işaretçiyi kaydeden ve yeni bir çerçeveye girdiği için BP'yi SP'ye eşitleyen bir işlev prologunu yürütür. Daha sonra yığında kendi yerel değişkenleri için alan ve ayrıca B'nin çağıranları veya çağırdığı şeyler için oluşturduğu herhangi bir bağlantı bloğu için kullanacağı alanı tahsis eder. Video ayrıca, derleyicinin BP'den kurtulabileceği ve bir genel amaçlı kayıt daha elde etmek için yığın işaretçisi RSP'ye dayalı tüm indekslemeyi yapabileceği ortak bir optimizasyondan bahsediyor.

  • 01:10:00 Bu bölümde, eğitmen izleyiciyi LV miR derleme sürecinden montaj koduna kadar götürür. İlk adım, global fib direktifi ve hizalama gibi bazı birleştirici direktiflerini kullanarak 'fib' fonksiyonunu global olarak erişilebilir bir fonksiyon olarak tanımlamayı içerir. Ardından, işlev prologu, var BP'lik bir itme kuyruğu ve RSP rbp'lik bir mafya kuyruğu ile kaydedilir. Derleme kodu ayrıca argümanı RTI işlevine taşımadan önce Kali-save kayıtları olan birkaç kaydı yığına iter ve onu RBX kaydına sincaplar. Son olarak, N değerinin ikiden küçük olup olmadığını kontrol etmek için bir karşılaştırma talimatı değerlendirilir ve eğer öyleyse, giriş değerini döndürür. Aksi takdirde, fib (n eksi bir) ve fib (n eksi iki)'yi hesaplamak için bir düz çizgi kodu kullanır, bunları toplar ve bu sonucu verir.

  • 01:15:00 Bu bölümde, video, karşılaştırma sonuçlarına bağlı olarak kodda bir sonraki adımda meydana gelen koşullu atlamaları ve değişen davranışları tartışır. JGE komutu, n 2'den büyük veya eşit olduğunda LLVM şube işleminin yanlış tarafı için etikete atlar, n 2'den küçük olduğunda ise işlemler işlemin gerçek tarafına karşılık gelir. LEA komutu aşağıdakiler için kullanılır: adres hesaplaması, taşıma işlemi işlev çağrısının sonucunu R14'e kaydederken. Bir sonraki talimat seti, n-2'nin değerini hesaplar, onu RDI'ye saklar ve ardından n-2'de fib'i çağırarak sonucu AX'imize döndürür. Son olarak, işlem AX'imize R14 ekler.

  • 01:20:00 Bu bölümde videoda C kodundan montaj koduna dönüşüm anlatılmaktadır. Konuşmacı, işlemin, kodu temsil etmek için kontrol akışı kenarlarıyla birbirine bağlanan temel bloklardan oluşan bir kontrol akış grafiği kullandığını açıklar. Ayrıca, derleme kodunda çağırma kurallarıyla uğraşmanın karmaşıklığından da bahsediyorlar. Sonsöz işlevi, sonucu döndürmeden önce yığın çerçevesindeki herhangi bir şeyden önce kayıtları geri yüklemek için kullanılır. Video, bölüm boyunca ele alınan ana konuları özetleyerek sona eriyor.
5. C to Assembly
5. C to Assembly
  • 2019.09.23
  • www.youtube.com
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Tao B. SchardlView the complete course: https://ocw.mit.edu/6-172F18YouTube Playl...
 

Ders 6. Çok Çekirdekli Programlama



Ders 6. Çok Çekirdekli Programlama

Bu video ders, çok çekirdekli programlamayı ve Moore Yasası nedeniyle çok çekirdekli işlemcilerin ortaya çıkışını ve saat frekanslarının ölçeklendirilmesinin sonunu tartışıyor. Konuşmacı, işlemcilerin karşılaştığı güç yoğunluğu sorununu ve bunun Moore Yasasına ayak uydurmak için çiplere birden çok çekirdeğin eklenmesine nasıl yol açtığını açıklıyor. Ders ayrıca, paralel programlama için soyutlamalar sağlayan Pthreads, TBB, OpenMP ve Silk gibi paylaşılan bellek donanımlarındaki ve eşzamanlılık platformlarındaki önbellek tutarlılık protokollerinin temellerini de kapsar. Her platformun artıları ve eksileri tartışılır ve Fibonacci programlarının uygulama örnekleriyle gösterilir. Video, çok çekirdekli programlamaya ve programcıların karşılaştığı zorluklara ve çözümlere kapsamlı bir genel bakış sağlar.

Video ayrıca, paralel işlemeyi ele alan bir soyutlama aracı olan Silk'in çeşitli yönlerini de kapsar. Konuşmacı, döngüler için iç içe ipek, montaj kodu oluşturma, indirgeyicileri kullanarak indirgeme, programlayıcı ve performans için optimize etme gibi konuları tartışır. Ayrıca, Silk ekosistemine ve sırasıyla hata ayıklama ve ölçeklenebilirliği analiz etmeye yönelik silk sanitizer ve silk scale gibi ilgili araçlara genel bir bakış sağlarlar. Ana çıkarım, çok çekirdekli işlemciler için paralel programlar yazmanın zor olabileceğidir, ancak Silk, karmaşık görevleri verimli bir şekilde ele alarak süreci basitleştirir ve programcılara kodlarının yürütülmesi üzerinde daha fazla kontrol sağlar.

  • 00:00:00 Bu bölümde eğitmen çok çekirdekli programlamayı ve çok çekirdekli işlemcilerin ortaya çıkış nedenlerini tartışır. Bir çipe sığabilen transistör sayısının her iki yılda bir ikiye katlandığını iddia eden Moore yasasının gelişiyle ve 2004'ten 2005'e kadar saat frekanslarının ölçeklendirilmesinin sona ermesiyle, yarı iletken satıcıları, üzerinde birden çok işlemci çekirdeği bulunan yongalar üretmeye başladı. Bunun nedeni, artık bir çip üzerindeki tek çekirdeklerin frekansını artırmanın mümkün olmaması ve bu nedenle paralel işlemeye izin veren bir tasarım modeline geçmeyi gerekli kılmasıdır. Eğitmen ayrıca bir çip üzerindeki transistör sayısı ile işlemcinin maksimum frekansı arasındaki ilişkiyi de açıklığa kavuşturur.

  • 00:05:00 Bu bölümde, konuşmacı, artan saat frekansının güç yoğunluğunun katlanarak artmasına neden olduğu, işlemcilerin karşılaştığı güç yoğunluğu sorununu tartışıyor. Bu, Moore Yasasına ayak uydurmak ve güç yoğunluğu sınırlarını aşmamak için çiplere birden fazla çekirdeğin eklenmesine yol açtı. Konuşmacı daha sonra çip çok işlemcili olarak bilinen soyut çok çekirdekli mimariyi tanıtıyor ve P iş parçacıkları, winAPI iş parçacıkları, Intel iş parçacıkları gibi farklı eşzamanlılık platformlarını kullanan çok çekirdekli makinelerde paralel programlar programlamak için donanım zorlukları ve yazılım çözümleri üzerine dersleri özetliyor. yapı taşları, openmp ve benzeri artı.

  • 00:10:00 Bu bölümde, konuşmacı çok çekirdekli programlamada önbelleklerin nasıl çalıştığını açıklıyor. Bir işlemci, ana bellekten önbelleğine bir değer yüklediğinde, gelecekte tekrar erişmesi gerekebileceği ihtimaline karşı bu değeri önbellekte tutacaktır. Başka bir işlemci aynı değeri yüklemek isterse, ana belleğe kadar gitmek yerine ilk işlemcinin önbelleğinden de alabilir. Ancak, bir işlemci kendi önbelleğindeki değeri güncelleyerek başka bir işlemcinin önbelleğindeki değeri eski hale getirdiğinde bir sorun ortaya çıkar. Önbellekler arasında tutarlılığı sağlamak için önbellek satırlarını üç olası durumla (M, S ve I) etiketleyen MSI protokolü, bu soruna yönelik temel bir çözümdür.

  • 00:15:00 Bu bölümde ders, paylaşılan bellek donanımındaki önbellek tutarlılık protokollerinin temellerini, özellikle de bir işlemcinin önbelleğindeki bir önbellek satırında yapılan değişikliklerin diğer önbelleklerin aynı satırın kopyalarını nasıl geçersiz kılabileceğini tartışır. Ders, basit bir protokolü tanıtıyor ve pratikte diğer daha karmaşık protokollerin nasıl var olduğunu açıklıyor. Donanım, birden çok işlemci aynı önbellek satırını değiştirdiğinde çakışmaların yönetilmesinden sorumludur, ancak bu bir "geçersiz kılma fırtınasına" neden olabilir ve performansı yavaşlatabilir. Ders ayrıca eşzamanlılık platformlarının bu karmaşıklıkları soyutlayabileceğini ve paralel programlamada senkronizasyon ve iletişime yardımcı olabileceğini belirtiyor.

  • 00:20:00 Bu bölümde konuşmacı, Fibonacci sayıları örneğini kullanarak farklı eşzamanlılık platformlarını tartışıyor. Fibonacci programı, Fibonacci sayılarını birden çok kez hesaplayan özyinelemeli bir algoritma kullanılarak uygulanır ve bu da onu zayıf bir algoritma yapar. İki özyinelemeli çağrı, tamamen bağımsız hesaplamalar oldukları için paralelleştirilebilir. İş parçacığı için standart bir API olan Pthreads, bu paralelleştirmeyi uygulamak için kullanılabilir.

  • 00:25:00 Bu bölümde konuşmacı, programlamada eşzamanlılığı etkinleştiren bir işlevler kitaplığı olan Pthreads'i tartışıyor. Pthreads, özel anlambilime sahip bir işlev kitaplığı kullanarak kodunuzda eşzamanlılık belirtmenize izin verdiği için kendin yap bir eşzamanlılık platformu sağlar. Pthreads'teki her iş parçacığı, bir işlemcinin soyutlamasını uygular ve gerçek makine kaynaklarına çoğullanır. Pthreads ayrıca iç iş parçacığı koordinasyonunda yer alan protokolleri basitleştiren maskeler sağlar. Pthreads kitaplığı, pthread'in oluşturduğu yeni iş parçacığını depolayan ve tanımlayan pthread_create ve kodda devam etmeden önce iş parçacığının bitmesini bekleyen pthread_join gibi temel işlevlere sahiptir. Konuşmacı, Pthreads kullanarak bir Fibonacci serisinin nasıl uygulanacağını gösterir.

  • 00:30:00 Bu bölümde sunum yapan kişi, Fibonacci dizisini paralel olarak yürütmek için Pthreads kodunun uygulanmasını tartışıyor. Girdi boyutu yeterince küçükse, paralel iş parçacığı oluşturma maliyeti nedeniyle programı sırayla yürütmenin daha iyi olduğunu açıklıyorlar. Kod, giriş argümanını iş parçacığına sıralar ve onu argümanlar yapısında saklar. Sunum yapan kişi, Pthread oluşturma, Pthread birleştirme ve kodun özyinelemeli olarak iş parçacığı oluşturması gerekiyorsa çok daha karmaşık hale gelmesi gibi bazı dezavantajlarını tartışır. Ayrıca, bu kodun yalnızca bir iş parçacığı oluşturduğunu, dolayısıyla dört işlemcide çalıştırılırsa mümkün olan maksimum hızlandırmanın iki olduğunu belirtiyorlar.

  • 00:35:00 Videonun bu bölümünde Pthreads ile ilgili konular ve Fibonacci dizisinin kodu ele alınmıştır. Bir iş parçacığı oluşturmanın yüksek yükü, kaba taneli eşzamanlılık ile sonuçlanır ve ölçeklenebilirlik sorunu, iki çekirdeğin aynı miktarda iş yapmamasıdır. Fibonacci mantığı tek bir işlev içinde güzel bir şekilde kapsüllenmediği için kod modülerlikten de yoksundur, bu da bakımını ve değiştirilmesini zorlaştırır. Kod ayrıca, derlemede kod yazmak zorunda kalmaya benzer olan bağımsız değişken sıralaması nedeniyle karmaşık hale gelir. Video daha sonra Intel tarafından bu sorunlara çözüm sağlamak için geliştirilen bir kitaplık olan Threading Building Blocks'u (TBB) tanıtıyor.

  • 00:40:00 Bu bölümde video, programcıların doğrudan iş parçacıklarıyla uğraşmak zorunda kalmadan yerel iş parçacıklarını ve iş çalma algoritmasını kullanmasına izin vermek için tasarlanmış bir C++ kitaplığı olan Intel İş Parçacığı Yapı Taşları (TBB) kitaplığının kullanımını tartışıyor. TBB yükü, görevleri belirleyerek bunları iş parçacıkları arasında dengeler, kod yazmayı daha basit hale getirir ve POSIX iş parçacıklarını kullanmaktan daha iyi performans gösterir. Video, TBB kullanarak bir Fibonacci programının uygulanmasına ilişkin bir örneği gösterir ve bunun, birden çok işlemci arasında daha fazla paralellik ve ölçeklenebilirlik sağlayarak yinelemeli olarak alt görevleri nasıl oluşturduğunu gösterir. TBB ayrıca döngü paralelliği, veri toplama ve yazılım ardışık düzeni için şablonların yanı sıra paylaşılan verilere güvenli eşzamanlı erişim için eşzamanlı konteyner sınıfları sağlar.

  • 00:45:00 Bu bölümde, konuşmacı eşzamanlılık sorununa iki dilsel çözüm sunuyor: OpenMP ve Silk. OpenMP, hangi kod parçalarının paralel olarak çalışması gerektiğini belirtmek için derleyici pragmalarını kullanarak C ve C++ ile Fortran'a dilsel uzantılar sağlayan bir belirtimdir. Döngü paralelliğini, görev paralelliğini ve boru hattı paralelliğini destekler ve birçok zamanlama ve veri paylaşım yönergesinin yanı sıra senkronizasyon yapılarına sahiptir. Konuşmacı, Pthreads veya TBB kullanmaktan daha basit ve daha iyi performans gösteren Fibonacci'nin OpenMP'de uygulanmasına bir örnek sunuyor. OpenMP, birçok özellik sağladığı ve kodu basitleştirdiği için paralel programlar yazmak için popüler bir çözümdür.

  • 00:50:00 Bu bölümde konuşmacı, eklem ve vektör paralelliğini destekleyen ve kanıtlanmış bir şekilde iş çalan programlayıcı içeren ipek programlama platformunu tartışıyor. Program ayrıca kodu global değişkenlerle paralel hale getirmek için bir hiper nesne kitaplığına sahiptir ve serigrafi yarış dedektörü ve ipek görünümü adı verilen ölçeklenebilirlik analizcisi gibi programlama araçlarıyla birlikte gelir. Konuşmacı ayrıca, sınıfta silk plus kullanmayacak olsalar da, diğer tüm ipek uygulamalarından daha temel derleyicisine göre daha iyi kod üreten, taper LLVM olarak bilinen daha iyi bir derleyici kullanacaklarını da belirtiyor.

  • 00:55:00 Bu bölümde silk spawn ve silk sync deyimlerinin paralel yürütmeyi sağlamak için kullanımı örnekler üzerinden tartışılmaktadır. İlk örnek, fib of n-2 yürütülürken onu çağıran işleve paralel olarak yürütülebileceğini öne süren silk spawn ve silk sync deyimlerini içeren Fibonacci için salt coat'tur. Ancak çalışma zamanı sistemi, bu görevlerin paralel olarak çalıştırılıp çalıştırılmayacağına karar verir. Tartışılan başka bir örnek, silk for deyiminin, yinelemeli olarak yinelemeli olarak ikiye bölen derleyiciye paralel olarak bir for döngüsü yürütmek için kullanıldığı ve aralık paralel yürütülemeyecek kadar küçük olana kadar silk spawn ve silk sync deyimleri kullandığı döngü paralelliğidir. Doğru sonuçlar için iterasyonların bağımsız olduğunu garanti etmek önemlidir ve bunun için ipek kullanmak bazı ek masraflar ekler.

  • 01:00:00 Bu bölümde video, döngüler için iç içe ipek kullanımını ve clang derleyicisinde bir bayrak kullanarak derleme kodu oluşturmanın ayrıntılarını tartışıyor. Silk for döngüsü kullanan değerlerin toplamı için örnek kod, birden çok işlemci aynı bellek konumuna yazdığında, belirlilik yarışı sorununu gündeme getirir. Silk, indirgeyici makroları kaydederken ve kaydını kaldırırken belirli bir değişken için toplama işlevini işleyen hiper nesneler olan indirgeyicilerin kullanımıyla bu sorunu giderir. Bu, çok çekirdekli programlamada ortaya çıkabilen indirgeme sorunuyla başa çıkmanın bir yoludur ve kullanım için mevcut olan diğer birçok indirgeme işleciyle birlikte.

  • 01:05:00 Bu bölümde, konuşmacı Silk'teki indirgeyicileri tartışıyor - çağrışımsal bir ikili işlem ve bir özdeşlik unsuru olan cebirsel yapılar. Silk, toplama, çarpma, min, maks ve XOR dahil olmak üzere önceden tanımlanmış birkaç indirgeyiciye sahiptir ve kendi azaltıcınızı tanımlayabilirsiniz. Silk'in faydalarından biri, programın her zaman geçerli bir seri yorumunun olması, hata ayıklamayı kolaylaştırması ve görevleri dengelemek için bir iş çalma programlama algoritması kullanarak programı izleyen ve mevcut işlemci çekirdeklerine eşleyen bir çalışma zamanı programlayıcısına sahip olmasıdır. eşit olarak. Diğer eşzamanlılık platformlarının aksine, Silk'in planlayıcısı teorik olarak verimlidir.

  • 01:10:00 Bu bölümde, konuşmacı Silk kaynak kodunun nasıl derleneceği, paralel ve seri performansın nasıl derleneceği ve silk sanitizer ve silk gibi araçları kullanarak hata ayıklama sorunları dahil olmak üzere çok çekirdekli programlama için Silk ekosistemine üst düzey bir genel bakış sunar. ölçek. Ayrıca seri programı performans için optimize etmenin önemini ve Silk'in programlayıcısının program yürütme sırasında farklı görevleri nasıl yerine getirebileceğini vurguluyorlar. Buna ek olarak, konuşmacı ipek ölçeğin bir kodun yararlanabileceği maksimum işlemci sayısını nasıl belirleyebileceğini ve ölçeklenebilirliği analiz etmek için onu yararlı bir araç haline getirdiğini açıklıyor.

  • 01:15:00 Bu bölümde, konuşmacı çok çekirdekli programlamayla ilgili dersten çıkarılan önemli çıkarımları özetler. Çoğu modern işlemcinin birden fazla çekirdeğe sahip olduğunu ve bunun da yüksek performans için paralel programlar yazmayı gerekli kıldığını açıklıyorlar. Ancak, bu tür programları yazmak zor olabilir, Silk burada devreye girer. Bu araç, işlemci çekirdeklerini programlayıcıdan soyutlar ve senkronizasyon, iletişim protokolleri ve yük dengeleme ile ilgilenir. Konuşmacı ayrıca, öğrencilerin Silk kullanarak kendi paralel ekran koruyucularını uygulayacakları gelecekteki bir projeden de bahseder.
6. Multicore Programming
6. Multicore Programming
  • 2019.09.23
  • www.youtube.com
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Julian ShunView the complete course: https://ocw.mit.edu/6-172F18YouTube Playlist...
 

Ders 7. Irklar ve Paralellik



Ders 7. Irklar ve Paralellik

Video, Silk programlamadaki ırklar, paralellik ve hesaplama günleri ile ilgili bir dizi konuyu kapsar. Ele alınan bazı temel kavramlar, eş zamanlı yürütme için spawn ve sync deyimlerini, yarış koşullarından kaçınmanın önemini ve bunları belirlemek için Silk'in yarış detektörünü kullanmayı içerir. Video ayrıca bir programdaki paralellik miktarını ölçmenin yolları olarak Amdahl yasasını, iş yasasını ve yayılma yasasını ve hesaplamaların işini ve kapsamını analiz etme yollarını kapsar. Paralel sıralama algoritmalarının potansiyel hızlanma ve paralelliği ve çizelgeleme teorisi kavramı da açgözlü zamanlayıcı teoremine odaklanılarak tartışılmaktadır. Genel olarak video, Silk programlamada program performansını anlama ve optimize etme konusunda değerli bilgiler sağlar.

Video, temelde herhangi bir açgözlü planlayıcının T1/Tinfinity P^2'den büyük veya ona eşit olduğu sürece mükemmele yakın doğrusal hızlanmaya ulaştığını belirten açgözlü zamanlayıcı sınırının sonuçlarını açıklıyor. Bir iş çalma zamanlayıcısı kullanan ipek zamanlayıcı, işlemci sayısı T1/Tinfinity'den çok daha az olduğu sürece mükemmele yakın doğrusal hızlanma elde edebilir. Silk çalışma zamanı sistemi, hazır şeritlerden oluşan bir çalışma güvertesi sağlayarak çalışır ve güvertenin altını bir yığın gibi manipüle eder. Video aynı zamanda yığınların birden çok görüntüsünü paralel olarak sağlayan ve paralel işlev çağrılarını mümkün kılan Cactus Stack'i de tartışıyor. P işlemci yürütmesinin gerektirdiği yığın alanının üst sınırı, genellikle ihtiyaç duyulan gerçek miktardan çok daha gevşektir, çünkü her işlemcinin işi her çaldığında hesaplama grafiğinde sonuna kadar gitmesi gerekmeyebilir.

  • 00:00:00 Bu bölümde eğitmen, bir sonraki ev ödevi ve proje için önemli olacak olan İpek'te ırklar ve paralellik konusunu tanıtıyor. Silk'in ebeveyn ve çocuk işlevlerinin aynı anda yürütülmesine izin veren spawn ve sync ifadelerinin temelleri gözden geçirildi. Eğitmen ayrıca geçmiş örneklerde görüldüğü gibi feci sonuçlara yol açabilecek MIT politika üyeleriyle bir araya gelmenin ve kodda yarış koşullarından kaçınmanın önemini vurgulamaktadır. Bulması en zor yarış böcekleri, feci olaylara neden olanlardır ve geleneksel testler genellikle etkili değildir. Silk, koddaki olası yarış hatalarını belirlemeye yardımcı olacak bir araç sunar.

  • 00:05:00 Bu bölümde video, yarışların geliştiriciler için bulması en zor hatalardan biri olduğunu açıklıyor çünkü bu, yalnızca mantıksal olarak paralel kodlar aynı bellek konumuna eriştiğinde ve en az biri bir yazma işlemi kaydettiğinde nadir olaylarda meydana gelebilir. ona Örnek olarak video, iki paralel yol arasında paylaşılan yarış hatasının her zaman oluşmadığını göstermek için bir bağımlılık grafiği kullanan basit bir kodu gösterir. Yarış, her iki depo da aynı bellek konumuna yazdığında gerçekleşir ve bu, hangi yürütme yolunun tamamen önce yürütüldüğüne bağlı olarak farklı çıktılarla sonuçlanabilir.

  • 00:10:00 Bu bölümde konuşmacı, iki komutun aynı bellek konumuna erişmesi ve komutlardan en az birinin yazma işlemi olması durumunda meydana gelen ve programda deterministik olmayan davranışlara neden olan belirlilik yarışları kavramını açıklar. Konuşmacı, bir Silk for-loop yinelemelerinin bağımsız olmasını sağlamak ve bir Silk spawn deyimi ile karşılık gelen Silk sync deyimi arasındaki kodun da bağımsız olmasını sağlamak gibi, yarışlardan nasıl kaçınılacağına dair ipuçları verir. Konuşmacı ayrıca makinenin sözcük boyutunun önemli olduğunu ve standart olmayan türler kullanan paketlenmiş veri yapılarını okurken ve yazarken dikkatli olunması gerektiğini belirtiyor.

  • 00:15:00 Bu bölümde video, Silk platformunun bir programdaki olası yarış koşullarını belirlemeye yardımcı olabilecek "yarış dedektörü"nü tartışıyor. Araçlı bir program oluşturmak için '-f sanitized equal to silk' bayrağını kullanan Silk, hata ayıklama koduna yardımcı olan rahatsız edici yarışları bildirebilir ve yerelleştirebilir. Video ayrıca paralellik kavramını ve Silk yürütme modelinin yürütme sırasında hesaplamanın gelişimini göstermek için hesaplama grafiklerini nasıl kullandığını açıklıyor. Program performansını optimize etmeye ve iyileştirmeye çalışırken bu kavramların anlaşılması önemlidir.

  • 00:20:00 hesaplama gününde köşe türleri: ilk şerit, devam şeritleri, işlev çağrısı şeritleri ve son şeritler. İlk zincir yürütülecek ilk komutu içerir ve son zincir programda yürütülen son komutu içerir. Devam şeritleri, bir yumurtlama işleminin devamını temsil ederken, işlev çağrısı şeritleri, bir işlev çağrısının yürütülmesini temsil eder. Hesaplama dag'ının yürütme sırasında dinamik olarak ortaya çıktığını ve işlemciden habersiz olduğunu, yani çalışma zamanı sisteminin görevlerin çalışma zamanında işlemcilerle nasıl eşleneceğini çözdüğünü not etmek önemlidir. Özetle, hesaplama günü, bir programın paralelliğini ve eşzamanlılığını anlamak için güçlü bir araçtır.

  • 00:25:00 Bu bölümde, hesaplama günlerini ve bunların bir programdaki paralelliği analiz etmek için nasıl kullanılabileceğini öğreniyoruz. Hesaplama günü, programın farklı bölümleri arasındaki bağımlılıkları temsil eder ve yumurtlama kenarları, çağrı kenarları, dönüş kenarları ve devam kenarları dahil olmak üzere farklı türde kenarlara sahiptir. Bir programda ne kadar paralellik olduğunu analiz etmek için hesaplama günlerini kullanmak mümkündür ve paralellik miktarını ölçmek için Amdahl yasasını kullanırız. Sağlanan örnekte, sırayla yürütülmesi gereken yediden az düğüm vardır, bu da hesaplamada bir dereceye kadar paralellik olduğunu gösterir.

  • 00:30:00 Bu bölümde, paralel işlemede mümkün olan maksimum hızı belirlemenin bir yolu olarak Amdahl Yasası kavramı tanıtılmaktadır. Programın seri kesrinin 3/18 olduğu ve maksimum 6'lık bir hızlanma ile sonuçlandığı belirlenmiştir. Amdahl Yasası paralellik konusunda bir üst sınır sağlarken, pratik durumlarda genellikle çok gevşektir. İş kanunu ve yayılma kanunu, paralelliğin alternatif tanımları olarak tanıtıldı; iş kanunu, P işlemciler üzerindeki yürütme süresinin, programın çalışmasının P'ye bölünmesinden büyük veya eşit olduğunu ve yayılma kanunu yürütme süresinin olduğunu belirtir. P işlemcilerde en azından sonsuz sayıda işlemcide yürütme süresidir. Bu yasalar, çoğu durumda maksimum hızlanma konusunda Amdahl Yasasından daha iyi üst sınırlar sağlar.

  • 00:35:00 Bu bölümde, konuşmacı çalışmanın nasıl oluşturulacağını ve farklı hesaplamaların niceliklerini nasıl kapsayacağını tartışıyor. İki paralel hesaplamayı yürütürken, işin yine de bireysel hesaplamaların işinin toplamı olduğunu ve yayılmanın, bireysel hesaplamaların aralığının maksimumu olduğunu açıklıyorlar. Konuşmacı ayrıca P işlemcilerdeki hızlandırmayı tanımlar ve alt doğrusal, doğrusal ve süper doğrusal hızlandırmayı tartışır. Mümkün olan maksimum hızlanmanın, hesaplama boyunca adım başına ortalama iş miktarına eşit olan hesaplamanın paralelliğine eşit olduğunu belirtiyorlar. Genel olarak, bu bölüm hesaplamaların bileşimi ve paralelliklerinin nasıl ölçüleceği hakkında bilgi sağlar.

  • 00:40:00 Bu bölümde, konuşmacı bir hesaplama DAG'si ve bir paralel hızlı sıralama algoritması gibi örnekler kullanarak maksimum paralelliği hesaplamak için hesaplama işinin ve kapsamının nasıl analiz edileceğini tartışıyor. Konuşmacı, bir programın seri yürütülmesini analiz etmek ve programın paralel hızlanmasında üst sınırlar türetmek için derleyici araçlarını kullanan Silk Scale ölçeklenebilirlik çözümleyicisini tanıtıyor. Konuşmacı ayrıca, büyük hesaplamaların paralelliğini elle analiz etmenin sıkıcı olabileceğinden, ancak Silk Scale'in bu konuda yardımcı olabileceğinden bahsediyor.

  • 00:45:00 Bu bölümde video, paralel bir hesaplama çalıştırmanın ve gözlemlenen hızın yanı sıra yayılma ve çalışma yasalarından gelen sınırları gösteren bir grafik oluşturmanın sonuçlarını tartışıyor. Arsa, maksimum hızın yaklaşık 5 olduğunu gösteriyor ve bu da programdaki paralelliğin düşük olduğunu gösteriyor. Analiz, paralelliğin darboğazının bölümleme işlevini sırayla yürütmek olduğunu ve hızlı sıralamanın paralel sürümünün beklenen iş ve yayılma süresinin n log n mertebesinde olduğunu ortaya koymaktadır. Elde edilebilecek maksimum paralellik, çok yüksek olmayan log log n mertebesindedir. Paralelliği artırmak için, bölme işlevi paralelleştirilmelidir.

  • 00:50:00 Bu bölümde konuşmacı, kayda değer bir hız artışı görmek için bölme ve birleştirme sıralama algoritmalarında paralellik uygulamanın önemini tartışıyor. Bu algoritmaların paralel versiyonları, log kare n ile bağlı genel bir yayılmaya ve n bölü log n'nin yüksek bir paralelliğine sahiptir. Ek olarak, yüksek paralelliğe ve karşılık gelen sıralı algoritmanınkine asimptotik olarak eşit bir işe bağlı olan birçok başka pratik paralel algoritma vardır. Konuşmacı ayrıca zamanlama teorisi kavramını tanıtarak merkezi bir programlayıcının hesaplama DAG'lerini çalışma zamanında mevcut işlemcilere eşleyebileceğini, Silk programlamada ise dağıtılmış bir zamanlayıcının kullanıldığını açıklıyor. Hesaplamanın her adımında mümkün olduğu kadar çok şey yapan açgözlü bir zamanlayıcı örnek olarak kullanılmıştır.

  • 00:55:00 Bu bölümde, geleceği düşünmeden şimdiki zaman adımında mümkün olduğu kadar çok iş yapan açgözlü bir zamanlayıcı kavramı tanıtılmaktadır. En az P ipliğin hazır olduğu tam bir adım ve P'den daha az ipliğin hazır olduğu tamamlanmamış bir adım tanımlanır. İlk olarak 1968'de Ron Graham tarafından gösterilen ünlü teorem, açgözlü bir çizelgeleyici tarafından elde edilen zaman sınırının T1/P + T sonsuzdan küçük veya ona eşit olduğunu, T1'in iş olduğunu ve T sonsuzun açıklık olduğunu belirtir. Bu teoremin kanıtı sağlanır ve herhangi bir açgözlü planlayıcının optimal çalışma süresinin iki faktörü içinde başardığı gösterilir.

  • 01:00:00 Bu bölümde video, optimum planlayıcının iki faktörü içinde ulaşan açgözlü planlayıcı sınırının sonuçlarını açıklıyor. Sonuç, herhangi bir açgözlü planlayıcının, T1/Tinfinity P^2'den büyük veya eşit olduğunda mükemmele yakın doğrusal hızlanmaya ulaştığını belirtir; burada T1/P çarpı T sonsuz, işlemci sayısına kıyasla hesaplamadaki paralellik miktarını ölçer. mevcut. İpek programlayıcı, T1/P artı sıra T sonsuza eşit beklenen TP çalışma süresine sahip, çizelgelemenin ek yüklerini hesaba katmak için T sonsuzunun önünde Büyük O olan bir iş çalma zamanlayıcısı kullanır ve neredeyse-- işlemci sayısı T1/Tinfinity'den çok daha az olduğu sürece mükemmel doğrusal hızlanma. Silk çalışma zamanı sistemi, hazır şeritlerden oluşan bir çalışma güvertesi sağlayarak çalışır ve güvertenin altını bir yığın gibi manipüle eder. Silk Scale'deki enstrümantasyon, programdaki paralelliği belirlemek için işi ve yayılma terimlerini ölçmeye izin verir.

  • 01:05:00 Bu bölümde konuşmacı, işlemcilerde üreme ve paralellik kavramını tartışıyor. Bir işlemci bir işlevi çağırdığında, bu işlevin çerçevesini yığının en altına yerleştirdiğini ve yığının en altında çerçeveler oluşturabileceğini açıklıyorlar. Paralel olarak birden çok işlem gerçekleşebilir ve yumurtlamalardan ve çağrılardan geri dönüşler yapılabilir. İşçilerin yapacak işleri kalmadığında, başka bir işlemci destesinin tepesinden hırsızlık yaparlar. Ünlü teorem, işçilerin çok nadiren hırsızlık yaptığını ve neredeyse doğrusal bir hızlanma sağladığını belirtir. Konuşmacı ayrıca Silk'in C'nin işaretçiler için kurallarını desteklediğini, burada bir yığın alanına işaretçinin ebeveynden çocuğa geçirilebildiğini, ancak çocuktan ebeveyne geçirilemeyeceğini not eder.

  • 01:10:00 Videonun bu bölümünde konuşmacı, Silk programının ata hesaplama grafiğindeki bir görev tarafından görülebilen yığın olan Cactus Stack'i tartışıyor. Bu yığın, paralel işlev çağrılarını mümkün kılan yığınların birden çok görüntüsünü paralel olarak sağlar. Konuşmacı, Silk programı için gereken yığın alanının, programın seri yürütülmesi için gereken yığın alanı (S alt 1) alınarak ve kullanılacak işlemci sayısıyla (P) çarpılarak (S) bulunabileceğini açıklar. alt P ≤ P x S alt 1). Konuşmacı, bu kavramın üst düzey bir kanıtını sağlar ve P işlemci yürütmesi için gereken yığın alanı üzerindeki üst sınırın, her işlemcinin her seferinde hesaplama grafiğinde sonuna kadar gitmesi gerekmeyebileceğinden, genellikle gereken gerçek miktardan çok daha gevşek olduğunu not eder. zaman işi çalıyor.
7. Races and Parallelism
7. Races and Parallelism
  • 2019.09.23
  • www.youtube.com
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Julian ShunView the complete course: https://ocw.mit.edu/6-172F18YouTube Playlist...
 

Ders 8. Çok Kanallı Algoritmaların Analizi



Ders 8. Çok Kanallı Algoritmaların Analizi

Bu video, bölme ve fethetme yinelemelerini analiz etmek için ana yöntemi tartışır ve n'deki büyümelerini ve gereken işi belirlemek için n'nin log bazını B ile A'nın log B tabanını ve F of N'yi karşılaştırarak bunu çok iş parçacıklı algoritmalara uygular. Video, temel çok iş parçacıklı algoritmalar için çözümler içeren bir kopya kağıdı sunar ve iş ve yayılma analizi, iş verimliliği ve tane boyutu optimizasyonu yoluyla genel giderlerin üstesinden gelme gibi konuları kapsar. Teknik konuları iletirken empatinin önemi vurgulanır ve paralelliği artırmak ve çalışma süresini azaltmak için işi ve yayılmayı dengeleme aracı olarak DAG kavramı tanıtılır.

Videoda ayrıca çok iş parçacıklı algoritmaların analizi, iş ve yayılmaya odaklanma ve mükemmele yakın doğrusal hızlanma elde etmek için yayılmayı en aza indirirken paralelliğin nasıl en üst düzeye çıkarılacağı tartışılıyor. Konuşmacı, iş parçacıklarına verilen görev sayısının yeterince fazla olduğu çok iş parçacıklı algoritmalara böl ve fethet yaklaşımını önerir ve zamanlama genel giderleri nedeniyle çok sayıda küçük görevin ortaya çıkmasına karşı uyarıda bulunur. Sunulan örnek kod, verimli ve berbat bir tane içerir. Konuşmacı ayrıca iki boyutlu kodlama ve indekslemede alt matrislerin nasıl temsil edileceğini tartışır ve performansı artırmak için bölme ve fethetme matrisi çarpma kodunda 'kısıtlama' kullanımının üzerinde durur.

  • 00:00:00 Bu bölümde eğitmen, öğrencilere böl ve fethet tekrarlarını ve bunları çözmek için ana yöntem adı verilen genel yöntemi hatırlatarak başlar. Yöntem yinelemelerle ve bunların T(n) = a*T(n/B) + F(n) biçimiyle ilgilenir; burada a bir sabittir, B bölme faktörüdür ve F(n) toplam iş miktarıdır. problemi n/B boyutunda alt problemlere bölmek. Öğrencilere özyineleme ağacı hatırlatılır ve her düzeyin n/B boyutunda alt problemlere nasıl bölündüğü, satırlar boyunca çalışma süresini topladıkları, ağacın yüksekliğini hesapladıkları ve bunu her düzeydeki alt problem sayısıyla çarptıkları (a ^k). Son olarak öğrenciler, A'nın n^log B tabanının algoritmanın toplam çalışma süresi olduğunu hesaplar.

  • 00:05:00 Bu bölümde, konuşmacı çok iş parçacıklı algoritmaları değerlendirirken n'deki büyümenin ve gereken çalışmanın nasıl belirleneceğini açıklıyor. Anahtar, n'nin log bazını B ile A'nın F of N'nin log tabanını karşılaştırmaktır. Konuşmacı üç olası durumu ele alır; Bu durumda, ağırlığın sabit kesri yapraklardadır, bu da cevabın A'nın log tabanı B'sine n olmasına yol açar. İkinci durum, log tabanı B n'nin yaklaşık olarak F of n'ye eşit olduğu durumdur. Bunun için fazladan bir kütüğü tutturursunuz ve cevap n üzeri log tabanı B logunun k artı 1 n'ye eşittir. Son olarak, üçüncü durum, bir log tabanı B'nin F of N'den çok daha az olduğu, yani F'nin polinomlar ve logaritmalar gibi bakacakları tüm fonksiyonlar tarafından tatmin edilen bir düzenlilik koşulunu karşılaması gerektiği anlamına gelir.

  • 00:10:00 Bu bölümde, konuşmacı bilgisayar biliminde yaygın olarak kullanılan temel çok izlekli algoritma çözümlerini içeren bir kopya kağıdı sunar. İlk algoritma, T(n) = T(n/2) + n, birinci duruma düştüğü için Θ(n^2) çözümüne sahiptir. İkinci algoritma, T(n) = T(n/2) + n^2logn, k = 0 ile ikinci duruma düştüğü için Θ(n^2logn) çözümüne sahiptir. Üçüncü algoritma için, T(n) = T(n/2) + n^2, birinci duruma denk geldiği için çözüm Θ(n^2)'dir. Dördüncü algoritma, T(n) = 2T(n/2) - n, ana yöntemin hiçbir durumu kapsamına girmediği ve Θ(n^2loglogn) çözümüne sahip olduğu için aldatıcıdır.

  • 00:15:00 Bu bölümde, konuşmacı Aqua Bazi yöntemini ve bunun çoğu programı analiz etmek için yeterli olan ana yöntemden nasıl daha karmaşık olduğunu tartışıyor. Daha sonra, dış döngünün paralelleştirildiği yerinde matris devrik koduyla bir paralel döngü örneği sağlarlar. Konuşmacı, verimli paralel işleme için yineleme alanını ve yük dengelemeyi doğru tanımlamanın önemini vurgular. Ayrıca, açık ipek derleyici ve çalışma zamanı sistemi tarafından döngülerin nasıl uygulandığını da açıklarlar.

  • 00:20:00 Bu bölümde konuşmacı, döngüyü iki parçaya bölmek ve tek öğeli bir yinelemeye ulaşana kadar her iki tarafta yinelemeli olarak çağırmak için böl ve fethet'i kullanan bir döngü için özyinelemeli bir programı açıklamaktadır. Bu hesaplamanın işi iş ve yayılma açısından analiz edilir, yaprak işi n kare mertebesindedir ve üst kısım teta n'dir, çünkü yapraklardan köke kadar her seviyede sadece n düğüm vardır. Açık ipek çalışma zamanı sisteminin bir ilkel döngüsü yoktur, bu nedenle döngüler etkili bir şekilde bu böl ve yönet yaklaşımına paralel olarak dönüştürülür.

  • 00:25:00 Bu bölümde, konuşmacı çok iş parçacıklı bir algoritmanın iş ve yayılma analizini tartışıyor. Tam ikili ağacın n yaprağının her biri için sabit iş yapıldığı için toplam işin Θ(n²) olduğunu açıklıyor. Döngü kontrolünün açıklığı log(n)'dir, bu da sonsuz sayıda işlemcinin görevi logaritmik zamanda tamamlayabileceği anlamına gelir. Ancak, hesaplamanın (n) doğrusal bir bileşeni olduğundan, toplam aralık Θ(n)'dir. Bu nedenle, paralellik, çoğu pratik sistem için iyi bir miktar olan Θ(n)'dir. Konuşmacı daha sonra iç döngünün de paralelleştirildiği senaryoyu araştırır ve ortaya çıkan iş miktarını tartışır.

  • 00:30:00 Videonun bu bölümünde, profesör paralel algoritmalarda iş verimliliği kavramını tartışıyor. Paralelleştirme algoritmaları işi değiştirmez, ancak büyük paralellik elde etmek için hesaplamanın kapsamını azaltması umulur. Bununla birlikte, bazen paralelleştirme daha fazla iş eklenmesine neden olabilir ve bu, orijinal algoritmaya kıyasla programı yavaşlattığı için sorunlu olabilir. İş verimli paralel algoritmalar, daha fazla iş eklemeden büyük paralellik elde etmek için aralığı azaltabildikleri için, profesörün öğretmekle ilgilendiği şeydir. Profesör, aynı soruları olan ancak sormaktan korkan başkalarına yardımcı olabileceğinden, öğrenme sürecinde soru sormanın ve hata yapmanın önemini vurgular. Öğrencileri, ilk %10'da olmasalar bile öğrenme sürecine katılmaya ve dahil olmaya teşvik eder.

  • 00:35:00 Bu bölümde teknik konular söz konusu olduğunda iletişimde empatinin önemi vurgulanmaktadır. Profesör, öğrencileri sınıfta işlenen materyale aşina olmayabilecek diğer kişilere karşı sabırlı olmaya teşvik eder. Çok iş parçacıklı algoritmaların analizine geçilerek, vektör toplama için bir böl ve fethet algoritması sunulmuş ve paralelliğin n bölü log n olduğu bulunmuştur. Paralellik ile işlemci sayısı arasındaki ilişki tartışılıyor ve profesör daha fazla paralelliğin daha iyi görünse de yalnızca belirli bir eşiğe kadar faydalı olduğunu vurguluyor.

  • 00:40:00 Bu bölümde konuşmacı, çok iş parçacıklı bir algoritmadaki ek yükün bir kısmını, özellikle de alt program çağrı ek yükünü optimize etmeyi tartışıyor. Derleyiciye, böl ve fethet sürecinin yapraklarında yığın başına en fazla G öğesi olduğunu öneren "tane boyutu" kavramını sunarlar. Bu, alt program yükünün tek bir G yinelemesinden ziyade amortismana tabi tutulmasına izin vererek daha iyi performans sağlar. Tane boyutu belirtilmezse, sistem ek yükü en aza indirmek için elinden gelenin en iyisini yapar. Konuşmacı, çalışmayı bu bağlamda analiz etmek için I, G ve s değişkenlerini parçalara ayırır ve paralel kontrol öğeleri olmadan orijinal koddaki çalışmayla karşılaştırır.

  • 00:45:00 Bu bölümde, konuşmacı çok iş parçacıklı algoritmaların analizinden ve modern, arızalı bir işlemcide döngü kontrolünün ne kadar ucuz olduğundan bahsediyor. Algoritmayı sonsuz sayıda işlemciyle yürütmek için gereken süre olan yayılmaya bakarlar ve genel maliyet ile yinelemelerin maliyetine karşı tartışırlar. Konuşmacı, aralığı yaprak sayısı ve her biri üzerinde yapılması gereken 's' olarak adlandırılan renkli işlemler açısından ayırır. Ayrıca tam bir ikili ağaçtaki iç düğümlerin sayısı ve yayılmayı hesaplamak için izlenen yollar hakkındaki soruları da yanıtlarlar.

  • 00:50:00 Bu bölümde, konuşmacı çok iş parçacıklı algoritmaların analizini, özellikle de DAG (yönlendirilmiş asiklik grafik) kavramını ve bunun algoritmanın yolunu nasıl etkilediğini tartışıyor. Paralel işlemeye izin vermek için DAG'nin farklı alt ağaçları arasında bağımsızlık ihtiyacını vurgularlar. Amaç, bu iki faktör zıt yönlerde çalıştığı için algoritmanın işini ve kapsamını dengelemektir. Anahtar, G'nin (paralellik miktarı) s bölü I'den (algoritmanın sıralı kısmı) çok daha büyük olmasıdır, bu da daha küçük bir ek yük ve daha hızlı işleme sağlar. Konuşmacı ayrıca bu kavramın bir uygulamasından da bahseder, ancak bunun ders dizisinde daha sonra tartışılacağını not eder.

  • 00:55:00 Bu bölümde, konuşmacı iki vektörü toplamak için bir for-döngüsü kullanan çok iş parçacıklı algoritmaların bir uygulamasını sunuyor. Döngü, seri vektör toplama işlemini gerçekleştirmek için V add adlı bir işleci kullanır ve döngü, G boyutunda bir vektör kullanarak G gruplarındaki toplamaları oluşturur. G'nin bire eşit olduğunu varsayarsak, döngülerin işi n mertebesindedir ve açıklık da sipariş Paralellik, n bölü n olan ve 1'e sadeleştiren işin yayılmaya oranı alınarak ölçülür. Konuşmacı, çok iş parçacıklı algoritmaları analiz etmenin amacının, çalışma süresini en aza indirmek için paralelliği artırmak ve yayılmayı azaltmak olduğunu vurgular ve tekniği vurgular. çok iş parçacıklı algoritmaları iyileştirmenin bir yolu olarak, hesaplamaları paralel hale getirmek için N uzunluğundaki bir döngünün çift iç içe bir döngü ile değiştirildiği şerit madenciliği olarak adlandırılır.

  • 01:00:00 Bu bölümde, konuşmacı çok iş parçacıklı algoritmaların performansını çalışma ve yayılma açısından analiz eder. Açıklık paydada olduğu için paralelliği en üst düzeye çıkarmak için açıklığın nasıl en aza indirileceğini tartışıyorlar. Mükemmele yakın doğrusal hızlanma isteniyorsa anahtar, işlemcilerden on kat daha fazla paralellik oluşturmaktır. Konuşmacı ayrıca gerekirse iş yükünü azaltmak için bazı paralelliklerden vazgeçilmesini öneriyor. Yeterli paralellik korunduğu sürece, bunu yapmak için tane boyutuyla oynamayı teşvik ederler.

  • 01:05:00 Bu bölümde, konuşmacı çok iş parçacıklı algoritmalarda böl ve fethet stratejilerinin kullanımını tartışıyor ve çok sayıda küçük görevi birbiri ardına oluşturmaya karşı tavsiyede bulunuyor. iyi. Genel olarak, iş parçacıklarına verilen görev sayısının yeterince büyük olduğu bir böl ve fethet yaklaşımı olmalıdır. Konuşmacı, zamanlama ek yüklerine dikkat edilmesi konusunda uyarır ve daha fazla yükü olan iç döngüler yerine dış döngüyü paralelleştirmeyi önerir. Burada sunulan örnek kodlar, çizelgelemenin yalnızca bir kez gerçekleştiği verimli bir kod ve ek yükün n kez gerçekleştiği berbat bir örnektir. Matris çarpımı, n bölü 2 ile n bölü 2 matrisin 8 çarpımını yaparak ve ardından iki n'ye n matrisi ekleyerek n'ye n matrisi çarpmak için bir böl ve fethet stratejisi kullanan çok iş parçacıklı bir algoritma örneği olarak kullanılır.

  • 01:10:00 Bu bölümde konuşmacı, özellikle C ve Fortran gibi diller için büyük satır ve sütun ana düzeninde olmak üzere iki boyutlu kodlama ve indekslemede alt matrislerin nasıl temsil edileceğini tartışıyor. Buradaki fikir, her iki boyutlu matrisin tek boyutlu bir matris olarak indekslenebileceği ve alt matrislerle uğraşırken, IJ öğesinin nerede olduğunu bilmek için uzun matrisin satır sayısı ve uzunluğunun eklenmesi gerektiğidir. Ayrıca, böl ve yönet'i uygularken, dört alt matrisin her birinin başlangıç köşelerini bilmek çok önemlidir. Son olarak, konuşmacı, derleyiciye hangi öğelerin diğer adla adlandırılıp adlandırılamayacağını söylemek için bölme ve fethetme matrisi çarpım kodunda 'kısıtlama' kullanılmasının altını çiziyor.

  • 01:15:00 Bu bölümde, konuşmacı matris çarpımı için çok iş parçacıklı bir algoritmayı tartışıyor. Algoritma, matrislerin yinelemeli olarak daha küçük alt matrislere bölünmesine dayanır ve her bir alt matris nihai sonucu elde etmek için yinelemeli olarak çarpılır. Konuşmacı, n'nin ikinin kuvveti olup olmadığını hızlı bir şekilde belirlemek için küçük bir numarayı vurgular ve matrislerin endekslenmesini basitleştirmek için bir makro kullanır. Algoritma, performansı artırmak için azaltılabilen yüksek paralellik sergiler. Diğer benzer algoritmalardan da bahsedilmektedir.
8. Analysis of Multithreaded Algorithms
8. Analysis of Multithreaded Algorithms
  • 2019.09.23
  • www.youtube.com
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Charles LeisersonView the complete course: https://ocw.mit.edu/6-172F18YouTube Pl...
 

Ders 9. Derleyicilerin Yapabilecekleri ve Yapamayacakları



Ders 9. Derleyicilerin Yapabilecekleri ve Yapamayacakları

Bu video, çeşitli örnekler kullanarak derleyicilerin kodu nasıl optimize edebileceğini tartışır. Derleyicilerin gereksiz depolama ve bellek referanslarını nasıl ortadan kaldırabileceklerini ve performansı artırmak için döngüleri nasıl optimize edebileceklerini açıklar.

Bu video ayrıca derleyici optimizasyon geçişleri kavramını ve bunların kod performansını iyileştirmek için nasıl kullanılabileceğini açıklar. Ayrıca, özellikle vektörleştirme açısından derleyicilerin sınırlamalarını tartışır. Derleyiciler, yalnızca koddaki işaretçilerin takma ad olmayacağını belirleyebilirlerse kodu vektörleştirebilirler. İşaretçiler takma ad yaparsa, derleyici kodu vektörleştiremez. Bir programcı olarak, kullanımları hakkında daha fazla bilgi sağlamak için işaretçilerinize açıklama ekleyerek derleyiciye yardımcı olabilirsiniz.

  • 00:00:00 Bu derste, Tao Schardl derleyicilerin neleri yapıp neleri yapamayacağını tartışıyor. Derleyici optimizasyonlarını incelemenin, geliştiricilerin optimizasyonlardan yararlanan kodu nasıl yazacaklarını ve derleyicinin zaten optimize edebileceği kodu manuel olarak optimize etmekten nasıl kaçınılacağını anlamalarına yardımcı olabileceğini açıklıyor.

  • 00:05:00 Derleyici büyük bir yazılım parçasıdır ve derleyicinin kendisinde hatalar olduğunda kesinlikle hata ayıklamaya yardımcı olabilir. Derleyicinin nerede hata yapmış olabileceğini veya derleyicinin yapması gerektiğini düşündüğünüz şeyi nerede yapmadığını anlamanıza yardımcı olur.

  • 00:10:00 Derleyici birçok iyileştirme yapabilir, ancak yapamadığı bazı şeyler vardır. Örneğin, her zaman hızlı bir yol oluşturamaz veya döngüleri optimize edemez.

  • 00:15:00 Derleyici, kodu optimize etmek için çok şey yapabilir, ancak iyi yapamadığı bazı şeyler vardır. Bir örnek, veri yapılarıdır - derleyici, işlevler hakkında olduğu gibi onlar hakkında da akıllı değildir. Bir diğeri döngülerdir - derleyici bunlar üzerinde bazı optimizasyonlar yapabilir, ancak kısıtlamalar vardır.

  • 00:20:00 Bu YouTube videosu, derleyicilerin daha karmaşık işlemleri değiştirmek için basit işlemleri nasıl kullanabileceğini açıklıyor. Örneğin, bir bölme işlemini değiştirmek için, bir derleyici sihirli bir sayı ile çarpabilir ve ardından sonucu değiştirebilir. Bu video aynı zamanda adres hesaplayıcının nasıl çalıştığını da açıklıyor.

  • 00:25:00 Video, örnek olarak basit bir "vex scale" işlevini kullanarak derleyicilerin kodu nasıl optimize edebileceğini tartışıyor. Kod, önce herhangi bir optimizasyon yapılmadan ve ardından çeşitli optimizasyonlar uygulanmış olarak gösterilir. Gösterilen optimizasyonlar, talimat sayısını azaltmayı, vektör talimatlarını kullanmayı ve sihirli sayıları kullanmayı içerir.

  • 00:30:00 Bu video, derleyicilerin gereksiz bellek işlemlerini ortadan kaldırarak kodu nasıl optimize edebileceğini tartışıyor. Özellikle, bir derleyicinin, değerleri bellekte depolama ihtiyacını ortadan kaldırarak iki skaler değeri çarpan bir işlevi nasıl optimize edebileceğini gösterir. Son olarak, bir derleyicinin yapı üzerinde çalışan bir işlevi, yapıyı bellekte saklama ihtiyacını ortadan kaldırarak nasıl optimize edebileceğini gösterir.

  • 00:35:00 Bu YouTube videosunda konuşmacı, derleyicilerin gereksiz depolama ve bellek referanslarını ortadan kaldırarak kodu nasıl optimize edebileceğini açıklıyor. Birden fazla alana sahip bir yapı örneğini kullanıyor ve adres hesaplamalarında yer alan matematiği dikkatli bir şekilde analiz ederek derleyicinin kodu nasıl optimize edebileceğini gösteriyor. Derleyici, her talimatın ne yaptığını anlayarak kodu optimize edebilir ve gereksiz işlemleri kaldırabilir.

  • 00:40:00 Derleyici, veri yapılarını ve skaler değerleri olabildiğince tamamen kayıtlar içinde depolamak ve mümkünse herhangi bir yerel depolama kullanmaktan kaçınmak için dönüştürmek için çok çalışır. İşlev çağrıları için, derleyici çağrı yönergesini ve çağrılan işlevin kodunu görür. Ardından, yukarıdaki koddaki işlevi daha da hızlı hale getirmeye çalışır.

  • 00:45:00 Derleyici, işlev çağrısı ek yükünden kaçınmak için kodu satır içi yapabilir ve ayrıca gereksiz işlemleri kaldırarak kodu optimize edebilir.

  • 00:50:00 Bu YouTube videosunda konuşmacı, bir derleyicinin bir işlevi satır içi yapamamasının üç ana nedeni olduğunu açıklıyor: işlev özyinelemeliyse, işlev farklı bir derleme birimindeyse veya işlev artabilirse kod boyutu ve zarar performansı. Konuşmacı ayrıca kendi programlarınızda işlev satır içi denetimi için bazı ipuçları verir.

  • 00:55:00 Bu video, programların daha hızlı çalışmasını sağlamak için derleyicilerin döngüleri nasıl optimize edebileceğini gösteriyor. Kod kaldırma veya döngü değişmez kod hareketi, performansı artırmak için kullanılabilecek bir optimizasyondur.

  • 01:00:00 Derleyici, bir dizi dönüştürme geçişi gerçekleştirerek kodu optimize edebilir. Bu geçişler, aynı adres hesaplamaları gibi özellikleri bulmak ve bunları daha verimli kodla değiştirmek için tasarlanmıştır.

  • 01:05:00 Derleyici, 'x' ve 'y' adreslerinin örtüşüp örtüşmediğini bilmemesine rağmen bu döngüyü vektörleştirebilir. Bunun nedeni, derlenen kodun yapısının girdi olarak verilen iki satırlık fonksiyondan daha karmaşık olmasıdır.

  • 01:10:00 Bu YouTube videosu, derleyicilerin neleri yapıp neleri yapamayacağını açıklıyor. Kod herhangi bir döngü içermiyorsa, derleyiciler kodu vektörleştirebilir. Ancak, kod döngüler içeriyorsa, derleyici yalnızca döngü vektör işlemleriyle doluysa kodu vektörleştirebilir. Döngü vektör işlemleriyle dolu değilse, derleyici kodu vektörleştiremez.

  • 01:15:00 Bir derleyicinin kodu vektörize edip edemeyeceği sorusu, bir dizi faktöre bağlı olduğu için zor bir sorudur. Özellikle, derleyicinin iki işaretçinin takma ad verip vermeyeceğini belirleyebilmesi gerekir ki bu zor bir görev olabilir. Bir programcı olarak, kullanımları hakkında daha fazla bilgi sağlamak için işaretçilerinize açıklama ekleyerek derleyiciye yardımcı olabilirsiniz.
9. What Compilers Can and Cannot Do
9. What Compilers Can and Cannot Do
  • 2019.09.23
  • www.youtube.com
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Tao B. SchardlView the complete course: https://ocw.mit.edu/6-172F18YouTube Playl...
 

Anlatım 10. Ölçme ve Zamanlama



Anlatım 10. Ölçme ve Zamanlama

Bu videoda konuşmacılar, doğruluğu etkileyebilecek dış etkenler de dahil olmak üzere hesaplamada ölçüm ve zamanlamanın çeşitli yönlerini tartışıyor. Modellere duyulan ihtiyacı ve verilerin net bir şekilde anlaşılmasını, hataları telafi etmek için varyansın azaltılmasını ve güvenilirliği sağlamak için uygun zamanlama çağrılarının kullanılmasını vurgularlar. Ayrıca performans modelleme, zamanlama çağrıları, donanım sayaçları ve simülatörler gibi araçları vurgularken, güç yasası ve deterministik olmayan faktörler gibi yazılım performansını doğru bir şekilde ölçmedeki zorlukları tartışırlar. Son olarak, doğru sonuçlar elde etmek için teknikler olarak nirengi ve uyarlama önererek tek bir araca güvenme konusunda uyarıda bulunuyorlar.

Konuşmacı, performans yazılımı mühendisliğinde güvenilir performans ölçümünün önemini açıklıyor. Performansı doğru bir şekilde ölçmek için istatistiklerin kullanılmasını önerir ve farklı bağlamlarda yararlı performans ölçümleri sağlayabilen ortalama gibi çeşitli özet istatistik türlerini tartışır. Oranların aritmetik ortalamasının alınmasının geçerli bir yaklaşım olmadığına işaret ediyor ve bunun yerine geometrik ortalamanın kullanılmasını öneriyor. Konuşmacı, programları karşılaştırırken verileri toplamanın doğru yolunu seçmenin önemini vurgular ve performansı daha doğru bir şekilde karşılaştırmak için birden fazla çalıştırmadan minimum veya %10 gibi düşük sıralı istatistiklerin alınmasını önerir. Konuşmacı ayrıca, kafa kafaya karşılaştırma ve istatistik elde etmek için bir model uydurma dahil olmak üzere performansı ölçmek ve karşılaştırmak için farklı metodolojileri tartışıyor, ancak modellemede aşırı uydurma konusu hakkında uyarıda bulunuyor. Genel olarak video, program performansını iyileştirmek için güvenilir performans ölçümünün önemini vurgulamaktadır.

  • 00:00:00 Bu bölümde, konuşmacı eski öğrencilerinden birinin kod sıralama üzerine yaptığı bir çalışmayı tartışıyor. Kod, zamanlama ölçümleri için saat alma zamanı rutinine erişim elde etmek için time.h başlık dosyasını kullanır. Bir sıralama rutini zamanlanır ve geçen süre hesaplanır ve yazdırılır. Ölçülen çalışma sürelerinin grafiği, sıralama rutininin çoğunlukla N log N büyümesini izlediğini, ancak ölçülen sürelerin en büyük diziler için bile yavaş olduğunu göstermektedir.

  • 00:05:00 Bu bölümde bir profesör, gözlemlenen veriler için bir modele sahip olmanın önemini tartışıyor. Ölçülen verilerin beklenenden önemli ölçüde saptığı bir örnek sunar ve öğrencilerden bu sapma için olası hipotezler önermelerini ister. Bazıları önbellek veya zamanlama hassasiyetiyle ilgili bir sorun olabileceğini düşünürken, profesör makinede çalışan ve sapmaya neden olan ilgisiz süreçler olabileceğine dikkat çekiyor. Bu durumda sorun, makinenin aynı anda birden fazla işlem tarafından kullanıldığı çoklu kiracılıktır. Profesör, kaliteli ölçümlere ve verilerin ne anlama geldiğine dair net bir anlayışa sahip olunması gerektiğini vurgular.

  • 00:10:00 Bu bölümde konuşmacılar hesaplamada ölçüm ve zamanlamayı ve dış faktörlerin ölçümlerin doğruluğunu nasıl etkileyebileceğini tartışırlar. Ölçüm sonuçlarını önemli ölçüde etkileyebilen sistem sıcaklığı ve güç tasarrufu teknikleri nedeniyle saat frekansı değişikliklerinin nasıl olabileceğine özellikle odaklanırlar. Hoparlörler, transistörlerin saat frekansını ve voltajını ayarlayarak gücü azaltan bir teknik olan dinamik frekans ve voltaj ölçekleme kavramını tanıtıyor. Hatalı sonuçlardan kaçınmak için ölçüm yaparken dış faktörleri göz önünde bulundurmanın çok önemli olduğunu vurguluyorlar.

  • 00:15:00 Bu bölümde konuşmacı, elektrik mühendislerinin kullandığı güç yasası nedeniyle yazılım performansını ölçmenin zorluklarını tartışıyor. Güç yasası, gücün CV kare F'ye eşit olduğunu belirtir; burada C dinamik kapasitans, V besleme voltajı ve F saat frekansıdır. Gücü ve ısıyı azaltmak için, frekans ve voltaj düşürülerek güçte kübik bir azalma elde edilebilir. Bu, yazılım performansını güvenilir bir şekilde ölçmek için bir zorluk teşkil eder ve konuşmacı, doğru ölçümler almak için gürültünün bir kısmından kurtularak sistemlerin sakinleştirilmesini önerir. Ayrıca, performans modelleme gibi yazılım performansını ölçmeye yönelik araçları da tartışırlar.

  • 00:20:00 Bu bölümde konuşmacı, özellikle performans mühendisliği bağlamında ölçüm ve zamanlama söz konusu olduğunda varyansı azaltmanın önemini tartışıyor. Değişkenliği azaltarak, sistematik ve rastgele ölçüm hatalarını telafi etmek ve programları karşılaştırmak için daha az deneme gerektirmek mümkündür. Konuşmacı ayrıca diğerlerinin yanı sıra arka plan işleri, kesintiler ve iş parçacığı yerleşimi dahil olmak üzere bilgisayar sistemlerindeki çeşitli değişkenlik kaynaklarına dikkat çekiyor. Son olarak, yüksek varyans sırasında ölçüm yapmak güvenilmez sonuçlara yol açabileceğinden, sistemde değişiklik yapmaya çalışmadan önce varyansı azaltmaya odaklanmanın önemini vurguluyor.

  • 00:25:00 Bu bölümde konuşmacı, işlemcilerdeki hyper-threading kavramından ve bulut sistemlerinde nasıl yanlış ölçümlere yol açabileceğinden bahsediyor. Hyper-threading, iki işlemci gibi görünen tek bir işlevsel birim üzerinden iki komut akışı çalıştırır, ancak aslında iki ayrı işlemci yerine yalnızca %20'lik bir hızlanma sağlar. Konuşmacı ayrıca, ölçüm sonuçlarını önemli ölçüde etkileyebilecek turbo boost ve sistemi sessizleştirme gibi diğer teknikleri de tartışıyor. Konuşmacı ve grubu, hyper-threading ve turbo boost'u kapatarak ve tüm iblisleri sakinleştirerek, minimum çalışma süresinden %1'den daha az yavaş, dikkate değer ölçüde güvenilir ölçümler elde etmeyi başardı.

  • 00:30:00 Bu bölümde konuşmacı, modern donanım üzerinde çalışan bir programın determinizmini etkileyebilecek çeşitli faktörlerden bahsediyor. Programı daha deterministik hale getirmek için alınabilecek bazı önlemler olmakla birlikte, deterministik olmayan unsurları tamamen ortadan kaldırmak mümkün değildir. Önbelleğe alma, kesintiler, iş parçacığı ve dal tahmini gibi program yürütme sırasında ortaya çıkabilecek deterministik olmayan faktörlerin çoğu deterministik süreçlerdir. Ancak donanımdaki rastgelelik kullanıcının kontrolü dışındadır ve bellek hatasına neden olabilir. Konuşmacı, kod hizalamanın program determinizminde bir fark yaratabileceğini ve kodda yapılan herhangi bir değişikliğin önbellek hizalamasında bir kaymaya neden olarak programın determinizmini etkileyebileceğini öne sürüyor.

  • 00:35:00 Bu bölümde konuşmacı, küçük değişikliklerin bir programın performansı üzerinde nasıl büyük bir etkiye sahip olabileceğini tartışıyor. Örneğin, bir bayt eklemek, ondan sonraki her şeyin doğrusal olarak etkilenmesine neden olabilir ve nokta o dosyalarının bağlayıcı komut satırında görünme sırasını değiştirmek, -OH- ve -O3 arasında gidip gelmekten daha büyük bir etkiye sahip olabilir. Bu sorunları ele almak için derleyiciler sorunu fark ediyor ve daha fazla uyum sağlıyor. LLVM, bir işlevdeki tüm işlevleri ve blokları hizalayabilen anahtarlara sahiptir, ancak hizalama programı yavaşlatabilir. Ayrıca, yürütülebilir dosyanın adı çağrı yığınında sona eren bir ortam değişkeninde sona erdiğinden, programın adı hızını etkileyebilir.

  • 00:40:00 Bu bölümde konuşmacı, time komutuyla programı harici olarak ölçmek, clock get time veya diğer yöntemleri kullanarak programa zamanlama çağrıları koymak, programı gdb ile kesmek dahil olmak üzere yazılım performansını ölçmek için çeşitli araç ve yöntemleri tartışır. hangi rutinin en çok zaman aldığını belirlemek, mükemmel araç setinde kullanılanlar gibi donanım ve işletim sistemi desteğinden yararlanmak veya daha derin bir anlayış elde etmek için daha yavaş bir hızda programı simüle etmek. Konuşmacı, time komutunu kullanırken geçen süre, kullanıcı süresi ve sistem süresi arasındaki farkı ve bunların işlemci tahsisi nedeniyle toplam süreye nasıl eklenemeyeceğini açıklar.

  • 00:45:00 Bu bölümde konuşmacı, duvar saati süresi, kullanıcı modunda harcanan işlemci süresi ve çekirdekte harcanan süre dahil olmak üzere farklı zamanlama ve ölçüm türlerini tartışır. Kullanım için önerilen zamanlama çağrısı, asla geriye doğru çalışmamayı garanti eden saat monoton seçeneği ile saat alma zamanıdır. Çalışması deterministik olmayan bir süre alsa da, RTIDTSC gibi farklı çekirdeklerde farklı cevaplar verebilen ve geriye doğru çalışabilen diğer zamanlayıcılardan daha güvenilirdir. Konuşmacı, günün saatini alma konusunda uyarır.

  • 00:50:00 Bu bölümde, konuşmacı clock_gettime kullanımı ve time komutuyla ölçüm dahil olmak üzere programlamada olayları ölçmenin ve zamanlamanın çeşitli yollarını tartışıyor. Zamanla tekniklerin değişebileceği ve mühendislerin uyum sağlaması gerekebileceği konusunda uyarıyorlar. Konuşmacı ayrıca basit bir profil oluşturma tekniği olarak kodu rastgele anlarda kesmeyi öneriyor ve Facebook gibi büyük şirketlerin bu yöntemi kullandığından bahsediyor. Ek olarak, konuşmacı donanım sayaçları fikrini ve bu sayaçlara işlem bazında erişim sağlayan livepFM4 kitaplığını tanıtıyor. Bir mühendisin her zaman cerrahi olarak hassas aletlere ihtiyaç duymayabileceğini ve bazen basit bir aletin bu iş için yeterli olabileceğini vurguluyorlar.

  • 00:55:00 Bu bölümde konuşmacı, donanım sayaçları ve simülatörler dahil olmak üzere ölçüm toplamanın farklı yollarını tartışıyor. Pek çok donanım sayacının yetersiz belgelendiği ve bazı araçların dört veya beşten fazla sayaç kullanılıyorsa bant genişliğini zaman-paylaşacağı konusunda uyarıyorlar. Simülatörler, tekrarlanabilirlikleri için övülür, ancak önbellekteki her şeyi modelleyemeyebilirler. Konuşmacı, doğruluğu sağlamak için üçgenlemeyi ve en az iki ölçüm kullanılmasını önerir. Ayrıca, verilerin yorumlanmasına rehberlik edecek bir performans modeline sahip olmanın önemini de vurguluyorlar.

  • 01:00:00 Bu bölümde, konuşmacı bir programın alınmasını, programda değişiklikler yapılmasını ve daha hızlı bir program üretmek için performansının ölçülmesini içeren performans yazılım mühendisliği sürecini açıklıyor. Ancak güvenilir performans ölçümü, sonuçları doğru bir şekilde ortaya koyan küçük değişiklikler yapmak için hayati önem taşır. Bu nedenle konuşmacı, neler olup bittiğine dair doğru bir resim elde etmek için istatistiklerin kullanılmasını önerir. Ayrıca, deterministik bir programın ham performansını ölçmeyi içeren bir bilmece sunuyor ve gürültüyü reddetmenin ve programın temel donanım performansını belirlemenin en iyi yolunun minimumu kullanmak olduğu sonucuna varıyor.

  • 01:05:00 Bu bölümde, farklı bağlamlarda yararlı performans ölçümleri sağlayabilen ortalama da dahil olmak üzere çeşitli özet istatistik türleri tartışılmaktadır. Web sunucularını değerlendirirken, CPU kullanımı ve toplam görev tamamlama süresi aritmetik ortalama kullanılarak ölçülebilirken duvar saati süresi ve yüzdelik davranış, istek memnuniyetini optimize etmek için daha alakalı olabilir. Ancak, A ve B programlarının performansının karşılaştırılması gibi oranları özetlerken aritmetik ortalamanın alınması, yaygın olarak yanlış kullanılsa da geçerli bir yaklaşım değildir. Bunun nedeni, videoda verilen örnekte gösterildiği gibi, oranların ortalamasının oranın kendisiyle aynı olmamasıdır.

  • 01:10:00 Bu bölümde konuşmacı, performans ölçülürken oranların ve araçların karşılaştırılmasıyla ilgili konuları tartışır. Oranların aritmetik ortalamasının alınmasının şüpheli sonuçlara yol açabileceğini ve geometrik ortalamayı kullanmanın daha iyi olduğunu gösteriyorlar. Ek olarak, oranları karşılaştırırken harmonik ortalamanın genellikle yararlı olduğunu belirtiyorlar. Programları karşılaştırırken verileri toplamanın doğru yolunu seçmenin önemi vurgulanır ve konuşmacı, performansı daha doğru bir şekilde karşılaştırmak için birden fazla çalıştırmadan minimum veya %10 gibi düşük sıralı istatistiklerin alınmasını önerir.

  • 01:15:00 Bu bölümde, konuşmacı performansı ölçmek ve karşılaştırmak için farklı metodolojileri tartışıyor. Bir yaklaşım, %10'luk en ucuz seçenekleri karşılaştırmak ve kesin kanıt sağlamasa da araçları karşılaştırmak için gürültü azaltma yapmaktır. Alternatif olarak, hangisinin daha sık kazandığını görmek için A ve B arasında bire bir karşılaştırma yapılabilir. Bu sayede sıfır hipotezi test edilebilir ve sapmanın anlamlı olup olmadığını belirlemek için p-değeri hesaplanabilir. Bu yöntem sosyal bilimlerde yaygın olarak kullanılır ve gürültülü ortamlarda faydalı olabilir. Son olarak, konuşmacı istatistik elde etmek için bir model uydurma fikrine kısaca değiniyor ve en küçük kareler yaklaşımının kullanımını tartışıyor.

  • 01:20:00 Bu bölümde, konuşmacı modellemede aşırı uydurma konusunu ve daha fazla temel fonksiyon eklemenin nasıl veri uydurmayı iyileştirebileceğini ve aynı zamanda aşırı uydurmaya yol açabileceğini tartışıyor. Çözüm, bir temel işlevi kaldırmak ve modelin kalitesini etkileyip etkilemediğini kontrol etmektir. Konuşmacı ayrıca ölçmenin Gurusu olarak bilinen Lord Kelvin'den de bahsediyor ve ölçmenin bilmek olduğunu ve ölçmezseniz geliştiremezsiniz. Video, konuşmacının Salı günü yapılacak bir sınavda şans dilemesiyle sona eriyor.
10. Measurement and Timing
10. Measurement and Timing
  • 2019.09.23
  • www.youtube.com
MIT 6.172 Performance Engineering of Software Systems, Fall 2018Instructor: Charles LeisersonView the complete course: https://ocw.mit.edu/6-172F18YouTube Pl...