diff options
author | Nunigan <michaelschmid13@hotmail.com> | 2021-08-02 08:15:28 +0200 |
---|---|---|
committer | Nunigan <michaelschmid13@hotmail.com> | 2021-08-02 08:15:28 +0200 |
commit | bd4c62c3e9de5b1fd5fbd1422bdac8843a928897 (patch) | |
tree | 7e3a451e565c146b2e46b4c40999e39421e903e6 /buch/papers/multiplikation/loesungsmethoden.tex | |
parent | update (diff) | |
parent | update (diff) | |
download | SeminarMatrizen-bd4c62c3e9de5b1fd5fbd1422bdac8843a928897.tar.gz SeminarMatrizen-bd4c62c3e9de5b1fd5fbd1422bdac8843a928897.zip |
Merge branch 'master' of https://github.com/Nunigan/SeminarMatrizen
Diffstat (limited to 'buch/papers/multiplikation/loesungsmethoden.tex')
-rwxr-xr-x | buch/papers/multiplikation/loesungsmethoden.tex | 53 |
1 files changed, 51 insertions, 2 deletions
diff --git a/buch/papers/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index 8e3369d..b25462a 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -295,9 +295,58 @@ Die Implementation kann Algorithmus \ref{multiplikation:alg:winograd} entnommen \end{algorithmic} \end{algorithm} -\subsection{Weitere Algorithmen} +\subsection{Basic Linear Algebra Subprograms (BLAS)} + +die gebr\"uchlichen Methode f\"ur die Anwendung einer optimierten Matrizenmultiplikation ist die Verwendung einer Subrutine aus den \textit{Basic Linear Algebra Subprograms (BLAS)} \cite{multiplikation:BLAS}. +Die meisten Numerischen Bibliotheken von High-Level Skriptsprachen wie \texttt{Matlab}, \texttt{NumPy (Python)}, \texttt{GNU Octave} oder \texttt{Mathematica} ben\"utzen eine Form von \textit{BLAS}. + +\textit{BLAS} sind dabei in drei unterschiedliche Levels aufgeteilt. + +\begin{itemize} + \item Level 1 + \begin{itemize} + \item Operationen der Art: $\mathbf{y} \leftarrow \alpha \mathbf{x}+\mathbf{y}$ + \item Dieses Level hat $\mathcal{O}(n)$ karakteristik + \end{itemize} + \item Level 2 + \begin{itemize} + \item Operationen der Art: $\mathbf{y} \leftarrow \alpha \mathbf{A}\mathbf{x}+\beta \mathbf{y}$ + \item Dieses Level hat $\mathcal{O}\left(n^2\right)$ karakteristik + \end{itemize} + \item Level 3 + \begin{itemize} + \item Operationen der Art: $\mathbf{C} \leftarrow \alpha \mathbf{A}\mathbf{B}+\beta\mathbf{C}$ + \item Dieses Level hat $\mathcal{O}\left(n^3\right)$ karakteristik + \end{itemize} +\end{itemize} + +Die \textit{BLAS} sind auf die modernen Computer Prozessoren optimiert und k\"onnen dank einer ausgek\"ugelter Verwedung der Speicher Architektur zur erheblichen Leistungoprimierung f\"uhren. + + +\subsubsection{General Matrix Multiplication (GEMM)} + +Die \textit{Double-GEMM} ist in \cite{multiplikation:DGEMM} definiert als: + +\textit{DGEMM performs one of the matrix-matrix operations} +$$ + C := \alpha \cdot op( A )\cdot op( B ) + \beta \cdot C, + $$ + \textit{where op( X ) is one of} +$$ +op( X ) = X \quad \text{ or } \quad op( X ) = X^T, +$$ + \textit{alpha and beta are scalars, and A, B and C are matrices, with op( A ) + an m by k matrix, op( B ) a k by n matrix and C an m by n matrix. + } + +Die Implementaion von $\alpha\mathbf{A}\mathbf{B} + \beta \mathbf{C} = \mathbf{C}$, wobei $\alpha = 1.0$ und $\beta = 0.0$ in der \texttt{C}-Version von \textit{BLAS}, ist als +\begin{lstlisting}[style=multiplikationC] +cblas_dgemm(CblasRowMajor, CblasNoTrans, CblasNoTrans, + m, n, k, 1, A, m , B, k, 0, C, m); +\end{lstlisting} +definiert. + -\textcolor{red}{TODO: BLAS} \section{Implementation} \rhead{Implementation} |