Виділення інформаційних залежностей

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

Можливий спосіб організації обчислень за таких умов полягає в застосуванні широко відомого алгоритму Фокса (Fox), — див, наприклад, Fox et al. (1987)Kumar et al. (1994).

Відповідно до алгоритму Фокса в ході обчислень на кожній базовій підзадачі() розташовується чотири матричні блоки:

• · блок матриці, що обчислюється підзадачею;
• · блок матриці, що розміщується в підзадачі перед початком обчислень;

· блоки, матриць і, що отримуються підзадачею в ході виконання обчислень.

Виконання паралельного методу включає:

· етап ініціалізації, на якому кожній підзадачі() передаються блоки, і обнуляються блоки в усіх підзадачах;

· етап обчислень, у рамках якого на кожній ітерації, здійснюються наступні операції:

— для кожного рядка,, блок підзадачі() пересилається в усі підзадачі того ж рядка грат; індекс, що визначає положення підзадачі в рядку, обчислюється відповідно до виразу:

де — це операція отримання залишку від цілочисельного ділення;

— отримані в результати пересилок блоки, кожної під задачі () перемножуються і додаються до блоку.

;

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

Для пояснення приведених правил паралельного методу на рис. 4.1 приведений стан блоків в кожній підзадачі в ході виконання ітерацій етапу обчислень (для грат підзадач).

Рис. 4.1. Стан блоків в кожній підзадачі в ході виконання ітерацій алгоритму Фокса.