Множення матриць при стрічковій схемі розділення даних

Розглянемо два паралельні алгоритми множення матриць, в яких матриці A і B розбиваються на безперервні послідовності рядків або стовпців (смуги).

Визначення підзадач

З визначення операції матричного множення виходить, що обчислення усіх елементів матриці С може бути виконано незалежно один від одного. Як результат, імовірний підхід для організації паралельних обчислень полягає у використанні у якості базової підзадачі процедури визначення одного елементу результуючої матриці С. Для проведення усіх необхідних обчислень кожна підзадача повинна містити по одному рядку матриці А і одному стовпцю матриці В. Загальна кількість отримуваних при такому підході підзадач виявляється рівним n2(по числу елементів матриці С).

Розглянувши запропонований підхід, можна відмітити, що досягнутий рівень паралелізму є в деякій мірі надмірним. Зазвичай при проведенні практичних розрахунків кількість сформованих підзадач перевищує число наявних процесорів і, як результат, неминучим є етап укрупнення базових завдань. У цьому плані може виявитися корисною агрегація обчислень вже на кроці виділення базових під задач. Для подальшого розгляду у рамках цього підрозділу визначимо базове завдання як процедуру обчислення усіх елементів одного з рядків матриці С. Такий підхід призводить до зниження загальної кількості підзадач до величини .

Для виконання усіх необхідних обчислень базовій підзадачі має бути доступним один із рядків матриці A та усі стовпці матриці B. Просте рішення цієї проблеми — це дублювання матриці B в усіх під задачах, але воно являється, як правило, неприйнятним в силу великих витрат пам’яті на зберігання даних. Як результат, організація обчислень має бути побудована так, щоб у кожен теперішній момент часу підзадачі містили лише частину цих, необхідних для проведення розрахунків, а доступ до іншої частини даних забезпечувався б за допомогою передачі повідомлень. Два можливі способи виконання паралельних обчислень подібного типу розглянуті далі у п. 3.2.