Wyniki wyszukiwania - BazTech

1

Evaluation of Open-Source Linear Algebra Libraries targeting ARM and RISC-V Architectures

Fibich Christian, Tauner Stefan, Rössler Peter, Horauer Martin

Annals of Computer Science and Information Systems

|

2020

|

Vol. 21

663--672

EN

Basic Linear Algebra Subprograms (BLAS) has emerged as a de-facto standard interface for libraries providing linear algebra functionality. The advent of powerful devices for Internet of Things (IoT) nodes enables the reuse of existing BLAS implementations in these systems. This calls for a discerning evaluation of the properties of these libraries on embedded processors. This work benchmarks and discusses the performance and memory consumption of a wide range of unmodified open-source BLAS libraries. In comparison to related (but partly outdated) publications this evaluation covers the largest set of opensource BLAS libraries, considers memory consumption as well and distinctively focuses on Linux-capable embedded platforms (an ARM-based SoC that contains an SIMD accelerator and one of the first commercial embedded systems based on the emerging RISC-V architecture). Results show that especially for matrix operations and larger problem sizes, optimized BLAS implementations allow for significant performance gains when compared to pure C implementations. Furthermore, the ARM platform outperforms the RISC-V incarnation in our selection of tests.

2

Optymalizacja obliczeń rekurencyjnych na komputerach wektorowych i równoległych

Stpiczyński P.

Studia Informatica

|

2008

|

Vol. 29, nr 3B

1-184

PL

W monografii zaprezentowano nowe, efektywne metody realizacji liniowych obliczeń rekurencyjnych na współczesnych komputerach wektorowych i równoległych. Na początku sformułowano nowe blokowe algorytmy, opierając się na metodach algebry liniowej. Dzięki temu możliwa stała się implementacja algorytmów, dobrze wykorzystująca możliwości oferowane przez współczesne procesory, poprzez użycie operacji zdefiniowanych w ramach biblioteki BLAS, zawierającej podstawowe podprogramy algebry liniowej. W dalszym ciągu pokazano, jak zrównoleglić wprowadzone algorytmy na komputery równoległe z pamięcią wspólną przy użyciu standardu OpenMP oraz komputery z pamięcią rozproszoną i klastry przy użyciu standardu MPI. Druga część monografii pokazuje przykładowe zastosowania wprowadzonych algorytmów blokowych i równoległych do rozwiązywania ważnych problemów obliczeniowych, takich jak wyznaczanie wartości liniowych filtrów rekurencyjnych, interpolacja trygonometryczna, numeryczne odwracanie transformaty Laplace'a oraz obliczanie wartości wielomianów. Podano również nowy oszczędny sposób reprezentacji macierzy trójkątnych i symetrycznych w obliczeniach rozproszonych. Wszystkie zaprezentowane w monografii algorytmy zostały zaimplementowane i przetestowane na różnych systemach komputerowych. Podano wyniki eksperymentów i wnioski potwierdzające wysoką efektywność algorytmów. W rozdziale 1 omówione są podstawowe zagadnienia związane ze współczesnymi architekturami komputerów dużej mocy obliczeniowej. Przedstawiono wykorzystywane w pracy metody analizy algorytmów, formalnie definiowano problem liniowych obliczeń rekurencyjnych oraz zaprezentowano w skrócie najważniejsze znane metody jego rozwiązania. Rozdział 2 opisuje efektywną metodę wektoryzacji obliczeń rekurencyjnych. Rozdziały 3 i 4 pokazują metodę, pozwalającą na wykorzystanie operacji macierzowych oraz jej zrównoleglenie na komputery z pamięcią wspólną i rozproszoną. Rozdział 5 omawia zastosowanie wprowadzonych we wcześniejszych rozdziałach metod dla szybkiego wyznaczania liniowych filtrów rekurencyjnych. W rozdziale 6 omawiane jest zastosowanie algorytmów z poprzednich rozdziałów do rozwiązania problemu wyznaczania sum trygonometrycznych oraz optymalizacji numerycznego wyznaczania odwrotności transformanty Laplace'a. Rozdział 7 omawia algorytm szybkiego obliczania wartości wielomianów, bazujący na metodzie przedstawionej w rozdziale 2, wraz z jego analizą numeryczną. Na koniec w rozdziale 8 podajemy nową metodę rozmieszczenia danych dla problemu rozwiązywania układów równań liniowych o macierzach trójkątnych, która pozwala na oszczędniejsze wykorzystanie pamięci oraz konstrukcję szybszych algorytmów.

EN

The aim of this monograph is to present the author's contribution to the fields of designing vector and parallel algorithms for solving problems based on linear recurrence computations and optimizing such software for modern vector and parallel computer architectures. In the first chapter, we give a concise overview of the fundamentals of modern computer architectures, performance analysis and methods for vector parallel programming. We also define the problem of solving linear recurrence systems and present some basic results which can be found in the literature. Chapter 2 describes the use of the Level 1 BLAS operation AXPY as a key to efficient vectorization of math order linear recurrence systems with constant coefficients. Applying the Hockney-Jesshope model of vector computations, we present the performance analysis of the algorithm. We also consider the influence of memory bank conflicts. The theoretical analysis is supported by the experimental results collected on two vector supercomputers manufactured by Cray. The aim of Chapter 3 is to present a new efficient BLAS-based algorithm for solving linear recurrence systems with constant coefficients, which can be easily and efficiently implemented on shared memory machines. The algorithm is based on Level 3 and Level 2 BLAS routines GEMM, GEMV and TRMV, which are crucial for its efficiency. The results of experiments performed on a various shared memory computers are also presented and discussed. The can be efficiently implemented on high performance message passing parallel and vector computers and clusters of workstations. In Chapter 4 we analyze the performance of the algorithm using two well known models: BSP and Hockney-Jesshope. Finally, we present the results of experiments performed of a Cray XI and two different clusters running under Linux. The aim of the chapters 5, 6 and 7 is to show that the introduced algorithms for solving linear recurrence systems can be applied for solving a number of problems which arise in scientific computing. In Chapter 5 we introduce a new BLAS-based algorithm for narrow-banded triangular Toeplitz matrix-vector multiplication and show how to evaluate linear recursive filters efficiently on distributed memory parallel computers. We apply the BSP model of parallel computing to predict the behavior of the algorithm and to find the optimal values of the method's parameters. The results of experiments performed on a cluster of twelve dual-processor Itanium 2 computers and Cray XI are also presented and discussed. The algorithm allows to utilize up to 30% of the peak performance of 24 Itanium processors, while a simple scalar algorithm can only utilize about 4% of the peak performance of a single processor. Next, we show that the performance of the algorithm for evaluating linear recursive filters can be increased by using new generalized data structures for dense matrices introduced by F. G. Gustavson. The results of experiments performed on Intel Itanium 2, Cray XI and dual-processor Quad-Core Xeon are also presented and discussed. In Chapter 6 we introduce a new high performance divide and conquer algorithm for finding trigonometric sums which can be applied to improve the performance of the Talbot's method for the numerical inversion of the Laplace Transform on modern computer architectures including shared memory parallel computers. We also show how to vectorize the first stage of the Talbot's method, namely computing all coefficients of the trigonometric sums used by the method. Numerical tests show that the improved method gives the same accuracy as the standard algorithm and it allows to utilize parallel processors. In Chapter 7 we show hot to apply our algorithms for polynomial evaluation. Finally, Chapter 8 presents the new data distribution of triangular matrices that provides steady distribution of blocks among processes and reduces memory wasting in comparison with the standard block-cyclic data layout that is used in the ScaLAPACK library for dense matrix computations. The new algorithm for solving triangular systems of linear equations is also introduced. The results of experiments performed on a cluster of Itanium 2 processors and Cray XI show that in some cases, the new method is faster than corresponding PBLAS routines PSTRSV and PSTRSM.

3

Rozwiązywanie układów równań metodą rozkładu WZ z wykorzystaniem bibliotek BLAS1 i BLAS2

Bylina B., Bylina J.

Studia Informatica

|

2004

|

Vol. 25, nr 1

57-67

PL

W artykule zaprezentowano strategię wyboru elementu podstawowego, efektywny blokowo-punktowy algorytm rozwiązywania układów równań liniowych metodą rozkładu WZ macierzy na czynniki z wyborem elementu podstawowego oraz szczegóły jego implementacji z wykorzystaniem bibliotek BLAS. Przedstawiony algorytm rozkładu WZ jest szybszy niż klasyczny rozkład sekwencyjny - również niż ten z włączoną optymalizacją kompilatora.

EN

In this article we want to present a strategy of pivoting, an efficient matrix-vector algorithm for solving linear systems by WZ matrix factorization with pivoting and details of its implementation with usage of BLAS libraries. The presented algorithm is faster than the seąuential one.