62 lines
3.9 KiB
Markdown
62 lines
3.9 KiB
Markdown
|
# Лабораторная работа 5. Параллельное умножение матриц
|
|||
|
|
### Задание на лабораторную работу
|
|||
|
|
Кратко: реализовать умножение двух больших квадратных матриц.
|
|||
|
|
|
|||
|
|
Подробно: в лабораторной работе требуется сделать два алгоритма: обычный и параллельный. В параллельном алгоритме предусмотреть ручное задание количества потоков, каждый из которых будет выполнять умножение элементов матрицы в рамках своей зоны ответственности.
|
|||
|
|
***
|
|||
|
|
### Описание работы
|
|||
|
|
Обычный алгоритм реализован в методе `multiplySequential`:
|
|||
|
|
```
|
|||
|
|
public static int[][] multiplySequential(int[][] m1, int[][] m2) {
|
|||
|
|
int size = m1.length;
|
|||
|
|
int[][] res = new int[size][size];
|
|||
|
|
for (int i = 0; i < size; i++) {
|
|||
|
|
for (int j = 0; j < size; j++) {
|
|||
|
|
for (int k = 0; k < size; k++) {
|
|||
|
|
res[i][j] += m1[i][k] * m2[k][j];
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
return res;
|
|||
|
|
}
|
|||
|
|
```
|
|||
|
|
Параллельный алгоритм реализован в методе `multiplyParallel`:
|
|||
|
|
```
|
|||
|
|
public static int[][] multiplyParallel(int[][] m1, int[][] m2, int threadCount) throws InterruptedException {
|
|||
|
|
int size = m1.length;
|
|||
|
|
int[][] res = new int[size][size];
|
|||
|
|
ExecutorService executor = Executors.newFixedThreadPool(threadCount);
|
|||
|
|
for (int i = 0; i < size; i++) {
|
|||
|
|
int r = i;
|
|||
|
|
executor.submit(() -> {
|
|||
|
|
for (int j = 0; j < size; j++) {
|
|||
|
|
for (int k = 0; k < size; k++) {
|
|||
|
|
res[r][j] += m1[r][k] * m2[k][j];
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
});
|
|||
|
|
}
|
|||
|
|
executor.shutdown();
|
|||
|
|
executor.awaitTermination(Long.MAX_VALUE, TimeUnit.MILLISECONDS);
|
|||
|
|
|
|||
|
|
return res;
|
|||
|
|
}
|
|||
|
|
```
|
|||
|
|
В методе создается пул потоков с помощью `ExecutorService` и указанным количеством потоков `threadCount`.
|
|||
|
|
Затем для каждой строки матрицы m1, создается задача, которая будет выполняться параллельно в отдельном потоке.
|
|||
|
|
Каждый поток берет на себя определенную строку матрицы m1 и умножает ее на соответствующие столбцы матрицы m2, результат умножения записывается в соответствующую ячейку результирующей матрицы res.
|
|||
|
|
Так каждый поток работает над своей зоной ответственности в матрицах и выполняет умножение независимо от других потоков.
|
|||
|
|
|
|||
|
|
|
|||
|
|
***
|
|||
|
|
### Результаты
|
|||
|
|
***Результат работы***
|
|||
|
|
|
|||
|
|
|
|||
|
|
На матрицах размером 100x100 последовательный алгоритм справляется быстрее параллельного, а на матрицах размером 300x300 и 500x500 наоборот - параллельный алгоритм справляется быстрее последовательного.
|
|||
|
|
|
|||
|
|
***Вывод:*** при небольших размерах матриц использование параллельного алгоритма дает проигрыш в производительности использованию последовательного алгоритма. Параллельное умножение матриц будет эффективнее, если размер матриц достаточно большой.
|
|||
|
|
|
|||
|
|
### Ссылка на видео:
|
|||
|
|
https://drive.google.com/file/d/1jnSD5FNua2payHZc3k18vfhxaAN31Q4A/view?usp=sharing
|