Масштабування і розподіл підзадач по процесорах

Як і раніше в методі Фокса, для алгоритму Кэннона розмір блоків може бути підібраний так, щоб кількість базових підзадач співпадала з числом наявних процесорів. Оскільки об'єм обчислень в кожній підзадачі є однаковим, це забезпечує повне балансування обчислювального навантаження між процесорами.

Для розподілу підзадач між процесорами може бути застосований підхід, використаний в алгоритмі Фокса, — безліч наявних процесорів представляється у вигляді квадратних грат і розміщення базових підзадач () здійснюється на процесорах відповідних вузлів процесорних грат. Необхідна структура мережі передачі даних, як і раніше, може бути забезпечена на фізичному рівні при топології обчислювальної системи у вигляді грат або повного графа.

Аналіз ефективності

Перед проведенням аналізу ефективності слід зазначити, що алгоритм Кэннона відрізняється від методу Фокса тільки видом виконуваних в ході обчислень комунікаційних операцій. Як результат, використовуючи оцінки часу виконання обчислювальних операцій, приведених в п. 4.4, проведемо тільки аналіз комунікаційної складності алгоритму Кэннона.

Відповідно до правил алгоритму на етапі ініціалізації робиться перерозподіл блоків матриць і за допомогою циклічного зрушення матричних блоків по рядках і стовпцях процесорних грат. Трудомісткість виконання такої операції передачі даних істотним чином залежить від топології мережі. Для мережі із структурою повного графа усі необхідні пересилки блоків можуть бути виконані одночасно (тобто тривалість операції виявляється рівною часу передачі одного матричного блоку між сусідніми процесорами). Для мережі з топологією гіперкуба операція циклічного зрушення може потребувати виконання ітерацій. Для мережі з кільцевою структурою зв’язків необхідна кількість ітерацій виявляється рівною. Детальніше методи виконання операції циклічного зрушення розглянуті в розділі 3. Для побудови оцінки комунікаційної складності етапу ініціалізації використовується варіант топології повного графа. Час виконання початкового перерозподілу блоків може оцінюватися як:

(вираз визначає розмір блоків, що пересилаються, а коефіцієнт 2 відповідає двом виконуваним операціям циклічного зрушення).

Оцінимо тепер витрати на передачу даних між процесорами при виконанні основної частини алгоритму Кэннона. На кожній ітерації алгоритму після множення матричних блоків процесори передають свої блоки попереднім процесорам по рядках (для блоків матриці) і стовпцях (для блоків матриці) процесорних грат. Ці операції також можуть бути виконані процесорами паралельно і, тим самим, тривалість таких комунікаційних дій складає:

Оскільки кількість ітерацій алгоритму Кэннона являється рівним q, то з урахуванням оцінки (1.13) загальний час виконання паралельних обчислень може бути визначений за допомогою наступного співвідношення:

(у використовуваних виразах параметр визначає розмір процесорних грат).