Geri Dön

On the analysis and evaluation of sparse hybrid linear solvers

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

PDF İndir

  1. Tez No: 520102
  2. Yazar: AFRAH NAJIB ABDULLAH FAREA
  3. Danışmanlar: PROF. DR. MUSTAFA SERDAR ÇELEBİ
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2018
  8. Dil: İngilizce
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Bilişim Enstitüsü
  11. Ana Bilim Dalı: Hesaplamalı Bilimler ve Mühendislik Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 117

Özet

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.

Özet (Çeviri)

A matrix is called sparse if many of its entries are zero. Such types of matrices are generated from discretization problems of many fields like numerical simulations, Fluid Dynamics, Graph theory, Optimization problems, Signal processing, Finance, industry, Linear Programming, Electromagnetics, 2D/3D and many other real-world applications. In general, we call a matrix sparse if we could exploit the sparsity of its elements in terms of memory storage and computation. Different sparse matrix formats are proposed which lead to huge memory and computation savings. Similarly, solving large sparse linear systems becomes increasingly important as a kernel task for such scientific applications. Furthermore, recent years witnessed huge and complex development in modern microprocessor architecture and hardware in general. Besides, the parallel computing methods and languages has shown a kind maturation in solving real-world problems especially, the development of Message Passing Interface (MPI). Consequently, many algorithms and software packages have emerged to exploit the new developments in hardware and software alike. For instance, the development in the hierarchy of memory and computation nodes leads to developing new blocking algorithms which accommodate the small cache memory of modern architecture and increase the floating-point performance. In general, there are two broad categories for solving linear systems mathematically: direct and iterative methods. Direct methods can give high accurate results (10−30) and are more suitable for small problems (current direct methods can solve up to a couple of millions of equations) because of the memory consumption they require (for example, they can not solve large sparse 3D problems which may generate hundreds of millions of unknowns). Besides, they have limited parallel scalability. Preconditioned iterative methods, on the other hand, are more robust, require less memory and easier to parallelize. However, they are problem dependent and can converge faster with good preconditioning methods. These methods are the methods of choice when an approximate solution of the problem is sought. Our focus in this thesis is the parallel software packages used for solving large sparse linear systems. We investigated the various methods and techniques for solving sparse linear systems and concentrate on the open source hybrid approaches as they are more flexible and well-suited the hierarchal structure of modern computers. The word hybrid has different meanings. Hybrid in programming means combining OpenMP and MPI so they work for shared and distributed memory. Hybrid in hardware means working on CPU and GPU. Hybrid in algorithms means combining direct and iterative methods. So, our focus is on the third meaning; combining direct and iterative algorithms in order to get more efficient methods for solving sparse matrices. Therefore, throughout this dissertation, when we mention the word hybrid, we mean direct/ iterative methods. Hybrid solvers are the latest research in developing robust and scalable methods for solving sparse linear systems. These methods combine direct and iterative approaches in certain ways, mostly using Schur complement framework, with the aim of getting the desired features of both direct and iterative methods especially the speed and low memory consumption of the iterative methods and the robustness of the direct methods. Most sparse hybrid solvers use the so called 'Schur complement framework' to combine direct and iterative methods. In this framework, the original matrix is divided into 2×2 block matrices. This approach is also known as sub-structuring domain decomposition method. Graph theory algorithms are responsible for ordering the global matrix and getting such block structure. The first block is a large block diagonal square matrix. Each diagonal block, called internal subdomain, is factorized using direct methods. The second and third block are the interfaces. If the matrix is symmetric, these interface blocks are transpose of each other. The fourth block is a square matrix called Schur complement matrix. This matrix has many desired features well-suited for iterative methods. It has smaller size than the original matrix and it is better conditioned than the original matrix. If the original matrix is symmetric positive definite, this Schur matrix will inherit this property and thus Conjugate Gradient can be used. Although Schur matrix is better conditioned than the original matrix, preconditioning the matrix before applying iterative method is necessary for faster convergence. The factorized internal subdomains are used to get an approximation of the Schur complement matrix and used as a preconditioner. Solving large sparse linear systems can take days even with algorithmic hybrid approaches if performed in sequential. Schur complement framework is more appealing for parallel programming. With increasing development of hardware and supercomputers, these systems can be solved efficiently within few seconds. However, existing algorithms should be modified to accommodate the parallel environment constrains such as scalability and load balancing. PDSLin and Maphys are the best existing public domain Schur-complement based hybrid solvers. They are based on different preconditioning methods which is a crucial ingredient in any iterative solver. PDSLin uses an approximation of the Schur complement as a precontitioner which gives a global view of the domain problem. Maphys uses an approximation of the local assembled Schur matrix which makes the solver more scalable. In our experiments, we thoroughly examined these solvers, test them on different matrix types and compare their results with the state-of-art Superludist direct solver. We also investigated the effect of tuning preconditioning input parameters on PDSLin and Maphys with increasing number of processors. Developed at Lawrence Berkeley National Laboratory (LBNL) by two distinguishing researchers in parallel linear algebra Ichitaro Yamazaki and X. Sherry Li; PDSLin solver is very robust and scales very well with increasing number of processors. However, it is very sensitive to the input parameters especially sparsifying tolerances which is not good. PDSLin is a powerful solver but has a lot of bugs and still needs a lot of work. Our results show that Maphys solver is more stable with the input values than PDSLin and gives better results. PDSLin results are unpredictable and sometimes fails with the slightest change of the input values. Maphys performance is better than both PDSLin and Superlu-dist in terms of time consumption and memory. Besides, the two-level parallelism of PDSLin is more robust than multithreading of Maphys. The serial partitioning time of Maphys is significant in many cases of our experiments and thus it is better to change into a parallel graph partitioner in Maphys than using a sequential partitioner. Sometimes the partitioning time is larger than summation of the other solution steps of Maphys and this is clearly shown in Audik and Freescale cases. Maphys solver also scales very well with increasing number of processors. Our conclusion is that sparse hybrid solvers are more flexible because they have different components and each component can be substituted to accommodate the problem at hand. The developers of the solvers we considered have already aware of this feature and this is clearly seen through the different methods they integrated within their solvers. For example, PDSLin uses either MUMPS or Superlu-dist as a direct method which are different approches of factorizing matrices. Similarly, Maphys uses either MUMPS or PASTIX which also are also different. Using two level parallelism can make hybrid solvers work efficiently and scalable up to thousand number of processors. In this level, Processors are distributed into levels and work concurrently and independently. This method alleviates the problem of increasing Schur complement size. However, load balancing is a challenging problem in this method. Hybrid solvers consume much less amount of memory than either pure direct or iterative methods.

Benzer Tezler

  1. Tez No

    836741

    FLAGS framework and decentralized federated learning under device volatility

    FLAGS platformu ve cihaz dalgalanması durumunda merkeziyetsiz federe öğrenme

    AHNAF HANNAN LODHI

    Doktora

    İngilizce

    İngilizce

    2023

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKoç Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    PROF. DR. ÖZNUR ÖZKASAP

    YRD. DOÇ. DR. BARIŞ AKGÜN

  2. Tez No

    444479

    Yeni nesil Kinect kamera ile 3B ortamlarda nesne seçme

    Object selection with new generation Kinect camera in 3D enviroment

    ÖMER FARUK ÇANGIR

    Yüksek Lisans

    Türkçe

    Türkçe

    2016

    Bilim ve TeknolojiHacettepe Üniversitesi

    Bilgisayar Grafiği Ana Bilim Dalı

    PROF. DR. HAŞMET GÜRÇAY

  3. Tez No

    854254

    Hierarchical reinforcement learning in complex wargame environments

    Kompleks savaş oyunu ortamlarında hiyerarşik pekiştirmeli öğrenme

    KUBİLAY KAĞAN KÖMÜRCÜ

    Yüksek Lisans

    İngilizce

    İngilizce

    2024

    Astronomi ve Uzay Bilimleriİstanbul Teknik Üniversitesi

    Uçak ve Uzay Mühendisliği Ana Bilim Dalı

    DOÇ. DR. NAZIM KEMAL ÜRE

  4. Tez No

    873673

    On praxis and poiesis duality in digital virtual object representation: A thesis on consumer categories and objectness

    Dijital ve sanal nesnelerin temsilinde praxis ve poiesis ikiliği hakkında: Tüketici kategorileri ve nesnelliğe dair bir tez

    OGEDAY CELEP

    Doktora

    İngilizce

    İngilizce

    2024

    İşletmeThe University of Reading

    Pazarlama Ana Bilim Dalı

    DOÇ. DR. MICHAEL MOLESWORTH

  5. Tez No

    539245

    Finite element analysis in a cloud computing environment

    Başlık çevirisi yok

    NİTEL MUHTAROĞLU

    Doktora

    İngilizce

    İngilizce

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolÖzyeğin Üniversitesi

    Bilgisayar Bilimleri Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ İSMAİL ARI

Geri Dön