ВУЗ:
Составители:
138
б)
Рис. 10.2 Граф-схема (а) и временная диаграмма (б) алгоритма
перемножения матриц для решетки подзадач 2×2
При разбиении матрицы на блоки следует, как обычно, стремиться к дос-
тижению высокой эффективности с учетом числа доступных процессоров. На-
пример, в наиболее простом случае, когда число процессоров представимо в
виде s=
2
, количество блоков в матрицах по вертикали и горизонтали целесооб-
разно принять одинаковым и равным
. При этом объем вычислений в каждой
подзадаче будет одинаковым, и при одинаковой производительности процессо-
ров будет достигаться полная балансировка вычислительной нагрузки между
ними.
Заметим, что в описанном алгоритме в ходе вычислений выполняются опе-
рации передачи блоков по строкам и столбцам решетки подзадач. Поэтому наи-
более целесообразной в данном случае является топология сети вычислитель-
ной системы в виде решетки или полного графа.
Определим вычислительную сложность описанного алгоритма. Будем по-
лагать, что все матрицы квадратные размера n×n, количество блоков по гори-
зонтали и вертикали одинаково и равно q. Таким образом, размер всех блоков –
k×k (k=n/q) процессоры образуют квадратную решетку и их количество равно
p=q
2
. Для простоты полагаем также, что n/q и n/s – целые числа.
Для выполнения описанного алгоритма перемножения матриц требуется q
итераций, в ходе которых каждый процессор перемножает свои текущие блоки
Страницы
- « первая
- ‹ предыдущая
- …
- 136
- 137
- 138
- 139
- 140
- …
- следующая ›
- последняя »
