Institute of Information Science - University of Miskolc

User Tools

Site Tools

Trace: • kovetelmenyek • xml-rpc_minta_feladat
muszaki_informatika:matrix_szorzas_gyorsitasa

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision		Previous revision
muszaki_informatika:matrix_szorzas_gyorsitasa [2025/02/12 10:15] – created knehezmuszaki_informatika:matrix_szorzas_gyorsitasa [2025/02/12 10:29] (current) – knehez
Line 61: Line 61:
 \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}
 \end{bmatrix}$$ \end{bmatrix}$$
 +
 +=== Mátrix szorzása blokkonként ===
 +
 +$$ C_{ij} = \sum_{k} A_{ik} \cdot B_{kj} $$
 +
 +Ahol minden C blokk a megfelelő A és B blokkok szorzataként adódik.
 +
 +Első blokk (C₁₁): $$C_{11} = A_{11} \cdot B_{11} + A_{12} \cdot B_{21}$$
 +$$ \begin{bmatrix} 1 & 2 \\ 5 & 6 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} +
 +\begin{bmatrix} 3 & 4 \\ 7 & 8 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$$
 +
 +Számoljuk ki az egyes részmátrixok szorzatát:
 +
 +$$ \begin{bmatrix} 1\cdot1 + 2\cdot0 & 1\cdot0 + 2\cdot1 \\ 5\cdot1 + 6\cdot0 & 5\cdot0 + 6\cdot1 \end{bmatrix} =
 +\begin{bmatrix} 1 & 2 \\ 5 & 6 \end{bmatrix}$$
 +
 +$$\begin{bmatrix} 3\cdot1 + 4\cdot0 & 3\cdot0 + 4\cdot1 \\ 7\cdot1 + 8\cdot0 & 7\cdot0 + 8\cdot1 \end{bmatrix} =
 +\begin{bmatrix} 3 & 4 \\ 7 & 8 \end{bmatrix}$$
 +
 +Összeadva:
 +$$ \begin{bmatrix} 1 & 2 \\ 5 & 6 \end{bmatrix} + \begin{bmatrix} 3 & 4 \\ 7 & 8 \end{bmatrix} = \begin{bmatrix} 4 & 6 \\ 12 & 14 \end{bmatrix}$$
 +
 +=== Végeredmény ===
 +
 +Hasonlóan számolva az összes blokkra ez lesz a végeredmény:
 +
 +$$ C =
 +\begin{bmatrix}
 +4 & 6 & 4 & 6 \\
 +12 & 14 & 12 & 14 \\
 +20 & 22 & 22 & 20 \\
 +28 & 30 & 30 & 28
 +\end{bmatrix} $$
 +
 +Miért gyorsabb ez a módszer?
 +  * Cache-hatékonyság: Egy blokk adatai könnyebben beleférnek a CPU gyorsítótárába.
 +  * Kevesebb memória-hozzáférés: A kisebb méretű részmátrixok többször felhasználhatók anélkül, hogy újra és újra be kellene tölteni a RAM-ból.
 +  * Jól párhuzamosítható: Az egyes blokkok párhuzamosan is számolhatók több CPU magon vagy GPU-n.
 +
 +**C** implementáció:
 +
 +<sxh c>
 +void multiplyMatricesBlocked(int A[N][N], int B[N][N], int C[N][N]) {
 +    // Eredménymátrix nullázása
 +    for (int i = 0; i < N; i++) {
 +        for (int j = 0; j < N; j++) {
 +            C[i][j] = 0;
 +        }
 +    }
 +
 +    // Blokkosított szorzás
 +    for (int bi = 0; bi < N; bi += BLOCK_SIZE) {
 +        for (int bj = 0; bj < N; bj += BLOCK_SIZE) {
 +            for (int bk = 0; bk < N; bk += BLOCK_SIZE) {
 +
 +                // Blokkon belüli műveletek
 +                for (int i = bi; i < bi + BLOCK_SIZE; i++) {
 +                    for (int j = bj; j < bj + BLOCK_SIZE; j++) {
 +                        for (int k = bk; k < bk + BLOCK_SIZE; k++) {
 +                            C[i][j] += A[i][k] * B[k][j];
 +                        }
 +                    }
 +                }
 +            }
 +        }
 +    }
 +}
 +</sxh>
muszaki_informatika/matrix_szorzas_gyorsitasa.1739355343.txt.gz · Last modified: 2025/02/12 10:15 by knehez