Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Каскадная схема суммирования

Читайте также:
  1. II. СТРУКТУРНО-ЛОГИЧЕСКАЯ СХЕМА ИЗУЧЕНИЯ ДИСЦИПЛИНЫ
  2. А) блиц-схема
  3. Анализ опыта социально-педагогической работы (примерная схема)
  4. БАНКОВСКАЯ СХЕМА
  5. Билет2 Функциональная схема компьютера. Основные устройства компьютера и их функции.
  6. Блог 5-вопрос. Технология логического устройства компьютера. Схема фон Неймана
  7. Блок-схема (технологические элементы,типы)
  8. Блок-схема курса
  9. В более наглядном виде я графически изобразила основные элементы конфликта в приложении1 схема б.
  10. Вниманию учащихся предлагается схема.

Параллелизм алгоритма суммирования становится возможным только при ином способе построения процесса вычислений, основанном на использовании ассоциативности операции сложения. Получаемый новый вариант суммирования (известный в литературе как каскадная схема) состоит в следующем (см. рис. 4.2):

· на первой итерации каскадной схемы все исходные данные разбиваются на пары и для каждой пары вычисляется сумма значений,

· далее все полученные суммы пар также разбиваются на пары и снова выполняется суммирование значений пар и т.д.

Данная вычислительная схема может быть определена как граф (пусть )

,

Рис. 4.2. Каскадная схема алгоритма суммирования

где есть вершины графа ( - операции ввода, - операции первой итерации и т.д.), а множество дуг графа определяется соотношениями:

.

Как можно оценить, количество итераций каскадной схемы оказывается равным величине

,

а общее количество операций суммирования

совпадает с количеством операций последовательного варианта алгоритма суммирования. При параллельном исполнении отдельных итераций каскадной схемы общее количество параллельных операций суммирования является равным

.

Как результат, можно оценить показатели ускорения и эффективности каскадной схемы алгоритма суммирования

где есть необходимое для выполнения каскадной схемы количество процессоров.

Анализируя полученные характеристики, можно отметить, что время параллельного выполнения каскадной схемы совпадает с оценкой для паракомпьютера в теореме 2 (см. раздел 2). Однако при этом эффективность использования процессоров уменьшается при увеличении количества суммируемых значений

.




Дата добавления: 2015-04-11; просмотров: 23 | Поможем написать вашу работу | Нарушение авторских прав

1 | <== 2 ==> | 3 | 4 | 5 | 6 | 7 |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав