Вопрос про parfor

olish

Есть задача:
Оцените, насколько этот алгоритм можно выполнить быстрее, чем последовательный, если число процессоров мультипроцессора = N, время выполнения одного оператора присваивания (A[i][j]=....) равно 1, временами выполнения остальных операторов можно пренебречь.
[code]
 float A[ L1 ][ L2 ];
 struct condition s[ L1 ][ L2 ];
 
 for ( i = 0; i < L1; i++) // Цикл 1
     for ( j = 0; j < L2; j++)
     { clear( s[ i ][ j ]) }
 
 for ( j = 0; j < L2; j++) // Цикл 2
     { post( s[ 0 ][ j ]) }
 
 parfor ( i = 1; i < L1-1; i++) // Цикл 3
     for ( j = 1; j < L2-1; j++)
     {
     wait( s[ i-1 ][ j ]);
     A[ i ][ j ] = (A[ i-1 ][ j ] + A[ i+1 ][ j ] + A[ i ][ j-1 ] + A[ i ][ j+1 ]) / 4;
     post( s[ i ][ j ]);
     }
[/code] <-- что с парсером?
По ссылке выше утверждается, что алгоритм будет работать за время L1 * L2 - N * L2 (ассимптотически, при условии, что Li >> N) - то есть не намного быстрее, чем последовательный.
В рассуждениях предполагается, что строки будут раздаваться процессорам блоками: первому процессору первые L1/N строк, второму следующие и т.д.
Если же выдать строки другим образом: первому строки с номерами 1, N+1, 2*N+1 и т.д, второму строки 2, N+2, 2* N+2 и т.д., то простой будет только при старте и при финише. При больших Li время работы составит L1 * L2 / N, то есть намного быстрее, чем последовательный.
Это действительно так и в разборе ошибка, или же тут хитрости с терминологией и parfor обязан раздавать итерации процессорам именно тем способом, который описан по ссылке?

Vlad128

а что это вообще за parfor? Да, указанное разделение — дубовое, тут надо по одной строчке выдавать, но это вы и сами поняли.

olish

Ну я всего лишь к экзамену по РОС готовлюсь, так что не особо разбираюсь в предмете :D
О parfor знаю только общие понятия, что он может итерации выполнять не последовательно, а паралельно в разных нитях. По каким правилам итерации будут распределяться между нитями - не знаю (но подозреваю, что компилятор/ОС не может "интеллектуально" проанализировать код и понять, какое распределение в данном случае будет оптимальным).
По ссылке выше сказано "Parfor - это цикл, витки которого распределяются между нитями (или процессами)".
В официальных лекциях вообще это понятие не вводится, сразу начинает использоваться.

Vlad128

ну судя по решению распределяет он подряд.

Innysa

Итерационное пространство делится на равные последовательные доли судя по результатам.

Innysa

Судя по всему это какой-то диалект плюсов Compositional C++. Вменяемой документации как-то сразу не находится
Оставить комментарий
Имя или ник:
Комментарий: