BE- Hesaplamalı Bilim ve Mühendislik Lisansüstü Programı
Bu topluluk için Kalıcı Uri
Hesaplamalı Bilim ve Mühendislik (HBM) Yüksek Lisans ve Doktora Programı İ.T.Ü. Bilişim Enstitüsü'nün Bilişim Anabilim Dalında açılan bir Programdır.
Gözat
Konu "Bilgisayar destekli hesaplama" ile BE- Hesaplamalı Bilim ve Mühendislik Lisansüstü Programı'a göz atma
Sayfa başına sonuç
Sıralama Seçenekleri
-
ÖgeDesigning A Fast Direct Sparse Matrix Solver For Multi-core Distributed Systems(Bilişim Enstitüsü, ) Tunçel, Mehmet ; Çelebi, M. Serdar ; 371565 ; Hesaplamalı Bilim Ve Mühendislik ; Computational Science and EngineeringBilimsel ve endüstriye yönelik birçok problemin çözümünde doğrusal denklem sistemleri ortaya çıkmaktadır. Diferansiyel denklemlerin büyük bir yer edindiği bu problemlerde, birçok kısmi diferansiyel denklemlerin bağlaşık (ing: coupled) çözülme ihtiyacından dolayı analitik çözümlerden çok sayısal yöntemler tercih edilmektedir. Sayısal yöntemlerle diferansiyel denklemlerin çözümü sonlu farklar ve sonlu elemanlar gibi birçok ayrıştırma yöntemi ile problemin sürekli uzaydan ayrık uzaya taşınmasını baz alır. Bu eşleme belli kafes (ing: mesh) noktalarında gerçekleştirilir ve sonucunda seyrek matrislerin katsayıları içerdiği doğrusal denklem sistemleri ortaya çıkmaktadır. Sayısal yöntemleri iki ana başlık içinden ifade edebiliriz. Bunlar belli bir adım basamağında kesin sonuca ulaşan doğrudan (ing: direct) yöntemler ve yaklaştırım ile hatayı her adımda azaltmayı hedefleyen yinelemeli (ing: iterative) yöntemlerdir. Yinelemeli yöntemlerin daha kolay programlanabilirliği hesaplamaların bilgisayar ortamında kullanımında ilk tercih olmasına neden olsa da, günümüz problemlerinin daha karmaşık bir yapıda olması yinelemeli yöntemlerin yaklaştırımını zorlaştırmaktadır. Bununla beraber, bir takım ön koşullandırıcı (ing:preconditioner) olarak adlandırdığımız yinelemeli yöntemlerde ele alınan problemden doğan katsıyalar matrisinin koşul sayısını (ing: condition number) düşürerek yakınsaklığını sağlayan ön uygulamalar ise her duruma cevap verememektedir. Bu nedenler doğrudan yöntemlerin programlanabilme kolaylığının yinelemeli yöntemler kadar olmamasına rağmen artık tercih edilebilir bir yöntem olarak görülmesine neden olmuştur. Günümüz yüksek başarımlı hesaplama teknolojilerindeki gelişmeler de doğrudan yöntemlerin daha geniş bir problem sahasına uygulanabilirliğini arttırmıştır. Seyrek matrislerin doğrudan yöntemlerde ki geleneksel faktorizasyon algoritmaları ile ele alınması, bellekteki direk olmayan adreslemelerden dolayı ciddi performans kayıplarına neden olmaktadır. Bu nedenle supernode yaklaşımı gibi bazı yöntemler bu problemin giderilmesi için ele alınmaktadır. Böylece bilgisayar işlemcileri daha etkin bir şekilde kullanılmış olur. Bunun diğer bir performans metriğini etkileyen faktörü ise tıkız (ing: dense) BLAS kütüphanelerinin kullanımıdır ki matris matris ve matris vektör çarpımları için optimize edilmiş rutinler içerirler. Seyrek matrislerin doğrudan yöntemler ile birlikte ele alınmasında dikkat edilecek noktalardan bir tanesi de faktorizasyon sırasındaki matristeki sıfır olan elemanların sıfır olmamasıdır. Çünkü seyrek matrisler tıkız olanlar gibi iki boyutlu dizilerde (n kare) değil , belleğin etkili kullanımı için daha az yer kaplayan üç ayrı dizide (yaklaşık 3n) saklanmaktadır. Kontrolsüz artış gösteren sıfır olmayan matris elemanlarının çoğalması ise algoritmaları olumsuz etkileyebilmekte ve hatta bellek yersizliğinden dolayı başarısız sonuçlayabilmektedir. Kısmi diferansiyel denklemlerin ayrıştırımında kafes noktalarının çözüm hassasiyetinin artırılması ihtiyacından dolayı sık olması veya hesaplama gerektirecek problem tanım alanının büyüklüğü nedeniyle çok büyük seyrek matrisler ortaya çıkmaktadır. Böyle denklem sistemlerinin tek bir hesaplama biriminde ele alınması ise donanımsal limitlerden dolayı imkansızdır. Çünkü çok büyük hesap yükü günlerce ve belki aylarca sonuçlanamayacak veyahut da bellek sınırlamasından dolayı hiç çalışamayacaktır. Bu nedenle böyle büyük problemlerin dağıtık sistemler ile ele alınması gerektir. Bu tezde, yukarıda bahsettiğimiz hususlar sonucu paralel çalışan dağıtık bellek sistemlerini kullanan doğrudan çözücüler dikkate alınmıştır. Bu çözücülerden Distributed SuperLU merkezde olarak testler gerçekleştirilmiş ve çıkan sonuçlar aynı zamanda paralel bir doğrudan çözücü olan SuperLU_MCDT (Multi-core Distributed SuperLU)'nin tasarımın da bazı donanımsal ve yazılımsal limitlerin açılması noktalarında katkı sağlamıştır. Tezin ilk kısmında örneklerle diferansiyel denklemlerin ayrıklaştırılması, bunun sonucunda çıkan seyrek matrislerin yinelemeli ve doğrudan yöntemler ile ele alınması karşılaştırılmış. Yapılan çalışmalar hakkında bilgi verilmiştir. İkinci kısımda ise seyrek matris algoritmalarının çıkışı ve gelişimi; günümüzdeki doğrudan yöntemleri kullanan çözücüler, Distributed SuperLU ve SuperLU_MCDT'nin buradaki yeri ve özellikleri anlatılmıştır. Doğrudan yöntemler için temel teşkil eden Gauss eliminasyon yönteminin ve basamak olduğu LU faktorizasyon yönteminin tıkız ve seyrek matrislerdeki matematiksel altyapısı ise üçüncü bölümde ele alınmıştır. Distributed SuperLU ve doğrudan yöntemleri kullanan çözücüler için kritik mekanizmalar dördüncü bölümde tek tek ele anlatılmıştır. Bu mekanizmaların işleyişi ve önemli noktaları paralel dağıtık bellek sistemleri tasarımı için gerekli yönleri açısından ele alınmıştır. Beşinci bölümde, testlerin hangi sistemlerde nasıl parametrelerle ele alındığına ve test sonuçlarının değerlendirilmesine yer verilmiştir. Son olarak ise bu çalışmadan elde ettiğimiz sonuçlar ve genel değerlendirilmesi yer almaktadır. Sonuç olarak şöyle diyebiliriz ki birçok bilimsel ve endüstriye ait problemlerin sonucunda seyrek doğrusal denklem sistemleri AX=B ortaya çıkmaktadır. Bu sistemlerin hızlı, gürbüz ve ölçeklenebilir algoritmalar ile çözülmesi çok önemlidir. Aynı zamanda bu algoritmalarının günümüz yüksek performanslı sistemlerin getirdiği kapasite ölçeklerine göre uyarlanması birçok algoritmik yapının daha verimli uygulanmasına olanak sağlayacaktır. Bütün matris desenleri için iyi performansı olan tek bir çözücünün olması mümkün gözükmemekle beraber, yeni yazılımsal ve donanımsal gelişmelere bağlı olarak bazı sınırlamaları aşan yeni bir algoritma (Superlu_MCDT) sunuyoruz. Bu algoritma ile çok çekirdekli işlemciye sahip dağıtık sistemlerin avantajlarından mümkün oldukça yüksek yararlanmaya çalıştık. Nodlar arası haberleşme yükü ve nod içi bellek gereksimi önemli bir yere sahiptir ve bu yükü yeni algoritmamız olan SuperLU_MCDT ile bir miktar kaldırmış olduk. SuperLU_MCDT'nin geliştirilmesi yanında çalışmakta olduğumuz kısımlar: satır permütasyon matrisinin paralel bir algoritma ile elde edilmesi, otomatik olarak ayar parametrelerinin belirlenmesi, MPI + OpenMP hibrit programının geliştirilmesi ve çok çekirdekli işlemciler için geliştirilen paralel doğrusal cebir kütüphanesinin SuperLU_MCDT ye eklenmesidir. Bunun yanında GPU (Grafik İşleme Ünitesi, ing: Graphichs Processing Unit) ile heterojen dağıtık sistemlerde SuperLU_MCDT'nin uygulanması da yapmayı planladığımız çalışmalardandır.