Читайте также:
|
Получение асимптотически ненулевой эффективности может быть обеспечено, например, при использовании модифицированной каскадной схемы [18]. В новом варианте каскадной схемы все проводимые вычисления подразделяется на два последовательно выполняемых этапа суммирования (см. рис. 4.3):
· на первом этапе вычислений все суммируемые значения подразделяются на 
групп, в каждой из которых содержится 
элементов; далее для каждой группы вычисляется сумма значений при помощи последовательного алгоритма суммирования; вычисления в каждой группе могут выполняться независимо друг от друга (т.е. параллельно – для этого необходимо наличие не менее процессоров);
· на втором этапе для полученных сумм отдельных групп применяется обычная каскадная схема.
Рис. 4.3. Модифицированная каскадная схема суммирования
Для упрощения построения оценок можно предположить 
. Тогда для выполнения первого этапа требуется выполнение параллельных операций при использовании 
процессоров. Для выполнения второго этапа необходимо
параллельных операций для 
процессоров. Как результат, данный способ суммирования характеризуется следующими показателями:
, 
.
С учетом полученных оценок показатели ускорения и эффективности модифицированной каскадной схемы определяются соотношениями:
Сравнивая данные оценки с показателями обычной каскадной схемы, можно отметить, что ускорение для предложенного параллельного алгоритма уменьшилось в 2 раза (по сравнению с обычной каскадной схемой), однако для эффективности нового метода суммирования можно получить асимптотически ненулевую оценку снизу
.
Можно отметить также, что данные значения показателей достигаются при количестве процессоров, определенном в теореме 5 (см. раздел 2).
Дата добавления: 2015-04-11; просмотров: 48 | Поможем написать вашу работу | Нарушение авторских прав |