Sparse hibrit doğrusal çözücülerinin analizi ve değerlendirilmesi

Birçok girdisinin sıfır olması durumunda bir matris seyrek olarak adlandırılır. Bu tür matrisler, sayısal simülasyonlar, Akışkanlar Dinamiği, Grafik Teorisi, Optimizasyon Problemleri, Sinyal İşleme, Finans, Endüstri, Doğrusal Programlama, Elektromanyetik, 2D / 3D ve diğer pek çok gerçek uygulama gibi birçok alanın ayrıklaştırma problemlerinden kaynaklanır. Genelde, bellek depolama ve hesaplama açısından öğelerinin seyrekliginden yararlanabilirsek ona seyrek matris diyoruz. Büyük bellek ve hesaplama tasarruflarına yol açan farklı seyrek matris formatları önerilmiştir. Benzer şekilde, büyük sparse lineer sistemlerin çözümü, bu tür bilimsel uygulamalar için bir çekirdek görevinde olduğundan giderek önem kazanmaktadır. Dahası, son yıllarda modern mikroişlemci mimarisinde ve genel olarak donanımda büyük ve karmaşık gelişmeler yaşandı. Ayrıca, paralel hesaplama yöntemleri ve dilleri, gerçek dünyadaki problemleri çözmede, özellikle Mesaj Geçiş Arayüzü (MPI) geliştirilmesinde bir çeşit gelişme göstermiştir. Sonuç olarak birçok algoritma ve yazılım paketi donanımda yeni gelişmelere kapı açtı. Örnek verilecek olunursa, bellek ve hesaplama düğümlerinin hiyerarşisindeki gelişme, modern mimarinin küçük önbelleği barındıran ve floating point performansını arttıran yeni engelleme algoritmalarının geliştirilmesini sağlar. Genel olarak, doğrusal sistemleri matematiksel olarak çözmek için iki ana kategori vardır: doğrudan ve yinelemeli yöntemler. Doğrudan yöntemler yüksek doğrulukta sonuçlar verebilir (10−30) ve ihtiyaç duydukları düşük hafıza tüketimi nedeniyle (son yıllarda doğrudan yöntemler birkaç milyon odf denklemini çözebilir) problemler için daha uygundur (örneğin, Büyük Sparse 3D problemlerini çözemezler). Bunun yanında paralel boyutlandırmayı sınırlar. Öte yandan Preconditioned iterasyon yöntemleri daha sağlıklıdır, daha az bellek gerektirir ve paralelleştirilmesi daha kolaydır. Ancak, bunlar problem bağımlıdırlar ve iyi preconditioning metodlarla daha hızlı yakınsanabilir. Bu tezdeki odak noktamız, büyük Sparse lineer sistemlerini çözmek için kullanılan paralel yazılım paketleridir. Spars lineer sistemlerin çözümü için çeşitli yöntemler ve teknikler araştırdık ve modern bilgisayarların hiyerarşik yapısı daha esnek ve uygun oldukları için açık kaynaklı hibrit yaklaşımlara yoğunlaştık. Hibrit kelimesinin farklı anlamları vardır. Programlamada hibrit, OpenMP ve MPI dillerini birleşimi anlamına gelmektedir çünkü paylaşımlı ve distrübe edilmiş hafızayı çalıştırabilirler. Donanımda ise hibrit, CPU ve GPU'nun birlikte çalışmasıdır. Hibrit algoritmada doğrudan ve iteratif yöntemleri birleştirmek anlamına gelir. Odak noktamız olan algoritma hibriti; daha verimli bir yöntem oluşturmak için doğrudan ve iteratif yöntemleri birleştirir. Bu nedenle, bu tez boyunca hibrit sözcüğünden bahsettiğimizde, doğrudan ve yinelemeli yöntemleri birlikte kastetmiş olacağız. Çoğu seyrek hibrit çözümleyicileri "Schur complement framework" yöntemini kullanır. Buradaki amaç doğrudan ve iteratif metodları birleştirmektir. Bu çerçevede, orijinal matris 2 × 2 blok matrisine ayrılmıştır. Grafik teorisi algoritmaları matrisin düzenlenmesi ve bu blok yapısının elde edilmesine yarar. İlk blok büyük bir blok köşegen kare matrisidir. Her diagonal blok iç alt domain olarak adlandırılır ve direk metodlar kullanılarak çarpanlarına ayrılırlar. İkinci ve üçüncü bloklar "interface"lerdir. Eğer matris simetrik ise bu interface bloklar birbirlerinin transpozesidir. Dördüncü blok Schur komplement matris olarak adlandırılan kare bir matristir. Bu matris asıl matristen daha küçüktür ve kullanmak için daha uygundur. Eğer asıl matris SPD matris ise Schur komplement matris de SPD matristir. Aynı zamanda Schur matris kullanmak asıl matrisi kullanmaktan daha kolaydır. Matrisi daha önceden preconditioning etmek daha hızlı bir yakınsama için gereklidir. Çarpanlarına ayrılmış iç alt domainler Schur complement matris yaklaşımı ve precondition yapmak için kullanılır. Büyük seyrek lineer sistemlerini çözmek sekansiyel olarak çalıştırıldığında, algoritmik hibrit yaklaşımlarla bile günler alabilir. Schur tamamlayıcı çerçeve paralel programlama için daha fazla tercih edilir. Donanım ve süper bilgisayarların gelişmesiyle birlikte, bu sistemler birkaç saniye içinde verimli bir şekilde çözülebilir. Ancak, var olan algoritmalar ölçeklenebilirlik ve yük dengesi gibi paralel çevresel kısıtlamalara uyum sağlayabilmek için modifiye edilmelidir. PDSLin ve Maphys, mevcut en iyi hibrit çözücü tabanlı açık kod Schurcomplement'dir. Bu çözücüler üzerinde derinlemesine inceleme yaptık, bunları farklı matris türlerinde test ettik ve sonuçlarını son teknoloji Superlu-dist doğrudan çözücüsü ile karşılaştırdık. Sonuç olarak, seyrek hibrit çözücüler daha esneklerdir çünkü farklı bileşenlere sahiplerdir ve her bileşen mevcut probleme uyarlanabilecek şekilde diğerinin yerine geçirilebilir. İki seviyeli paralellik kullanmak, hibrit çözücülerin verimli olmasını ve bin adet işlemci sayısına kadar ölçeklenebilir olmasını sağlayabilir. Hibrit çözücüler, doğrudan veya iteratif yöntemlerden çok daha az miktarda bellek kullanılır. Büyük seyrek lineer sistemlerini çözmek sekansiyel olarak çalıştırıldığında, algoritmik hibrit yaklaşımlarla bile günler alabilir. Schur tamamlayıcı çerçeve paralel programlama için daha fazla tercih edilir. Donanım ve süper bilgisayarların gelişmesiyle birlikte, bu sistemler birkaç saniye içinde verimli bir şekilde çözülebilir. Ancak, var olan algoritmalar ölçeklenebilirlik ve yük dengesi gibi paralel çevresel kısıtlamalara uyum sağlayabilmek için modifiye edilmelidir. PDSLin ve Maphys, mevcut en iyi hibrit çözücü tabanlı açık kod Schurcomplement'dir. Bu çözücüler üzerinde derinlemesine inceleme yaptık, bunları farklı matris türlerinde test ettik ve sonuçlarını son teknoloji Superlu-dist doğrudan çözücüsü ile karşılaştırdık. Sonuç olarak, seyrek hibrit çözücüler daha esneklerdir çünkü farklı bileşenlere sahiplerdir ve her bileşen mevcut probleme uyarlanabilecek şekilde diğerinin yerine geçirilebilir. İki seviyeli paralellik kullanmak, hibrit çözücülerin verimli olmasını ve bin adet işlemci sayısına kadar ölçeklenebilir olmasını sağlayabilir. Hibrit çözücüler, doğrudan veya iteratif yöntemlerden çok daha az miktarda bellek kullanılır Büyük seyrek lineer sistemlerini çözmek sekansiyel olarak çalıştırıldığında, algoritmik hibrit yaklaşımlarla bile günler alabilir. Schur tamamlayıcı çerçeve paralel programlama için daha fazla tercih edilir. Donanım ve süper bilgisayarların gelişmesiyle birlikte, bu sistemler birkaç saniye içinde verimli bir şekilde çözülebilir. Ancak, var olan algoritmalar ölçeklenebilirlik ve yük dengesi gibi paralel çevresel kısıtlamalara uyum sağlayabilmek için modifiye edilmelidir. PDSLin ve Maphys, mevcut en iyi hibrit çözücü tabanlı açık kod Schurcomplement'dir. Bu çözücüler üzerinde derinlemesine inceleme yaptık, bunları farklı matris türlerinde test ettik ve sonuçlarını son teknoloji Superlu-dist doğrudan çözücüsü ile karşılaştırdık. Sonuç olarak, seyrek hibrit çözücüler daha esneklerdir çünkü farklı bileşenlere sahiplerdir ve her bileşen mevcut probleme uyarlanabilecek şekilde diğerinin yerine geçirilebilir. İki seviyeli paralellik kullanmak, hibrit çözücülerin verimli olmasını ve bin adet işlemci sayısına kadar ölçeklenebilir olmasını sağlayabilir. Hibrit çözücüler, doğrudan veya iteratif yöntemlerden çok daha az miktarda bellek kullanılır.