Designing A Fast Direct Sparse Matrix Solver For Multi-core Distributed Systems

thumbnail.default.alt
Tarih
Yazarlar
Tunçel, Mehmet
Süreli Yayın başlığı
Süreli Yayın ISSN
Cilt Başlığı
Yayınevi
Bilişim Enstitüsü
Institute of Informatics
Özet
Bilimsel 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.
Many scientific and industrial problems are described by partial differential equations (PDEs). Handling of numerical solution of PDEs has been producing sparse linear equation systems AX = B. Generally, two methods are most common used to solve linear equation systems in computational science. One of them is direct methods and another is iterative methods. Along with easily practicability of iterative methods which are sequence of improving approximate solutions, direct methods attempt to solve the problems with exact solution in the the absence of the rounding error. So direct methods are seen more appealing through developing capacity of high performance computing (HPC) systems. Direct solvers for sparse matrices have more different algorithmic mechanisms than for dense matrices because of the sparse matrix data structure and handling higher dimensional scientific problems. And parallel sparse direct solvers especially have another important issues like load balancing and scalability. In this thesis, we consider parallel scalable direct solvers. We examine the effectiveness of the Distributed SuperLU for multi-core distributed memory parallel machines among several variants of sparse direct solvers. Giving of background with general sparse direct solver algorithms, some important mechanisms have been mentioned separately in more detail. Advantages and limitations of the sparse direct solvers for distributed memory systems have been discussed. In our tests, scalability, tuning factors and constructions which needs further customization for various large sparse matrices have been separately examined. Although it is not possible to use only one direct solver for all pattern of matrices, we propose a new algorithm SuperLU_MCDT (Multi-core Distributed SuperLU) which can exceed some limitations with new hardware and software developments. Proposed SuperLU_MCDT is expected to take the fully advantage of multi-core distributed systems. Our studies show that the inter-node communication and intra-node memory requirements are critical and this existing overhead is partly removed with our new algorithm SuperLU_MCDT.
Açıklama
Tez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Bilişim Ensititüsü, 2013
Thesis (M.Sc.) -- İstanbul Technical University, Institute of Informatics, 2013
Anahtar kelimeler
Bilgisayar destekli hesaplama, Diferensiyel hesaplar, Paralel hesaplama, Sayısal hesaplama, Computer aided calculation, Differential calculus, Parallel computing, Numerical calculation
Alıntı