 |
|
|
Архитектура Астрономия Аудит Биология Ботаника Бухгалтерский учёт Войное дело Генетика География Геология Дизайн Искусство История Кино Кулинария Культура Литература Математика Медицина Металлургия Мифология Музыка Психология Религия Спорт Строительство Техника Транспорт Туризм Усадьба Физика Фотография Химия Экология Электричество Электроника Энергетика |
Сравнение последовательных и параллельных алгоритмов
Для сравнения произвольных алгоритмов используем какой-либо исходный последовательный алгоритм, который получается из исходной задачи. Умножение матрицы 4х4 на вектор 4х1 с помощью 5 СП (систолических процессоров) и использованием матрицы, повёрнутой на 135 градусов, занимает 14 тактов: Буфер1 Буфер2 модель магазинной памяти (очереди)
Процессорное поле Рис. Модель памяти при вычислении умножения матрицы на вектор с помощью СП. Вычисления начнутся с СП, помеченного кружочком. Шестой СП – резервный. Матрица А записывается в следующем виде (как ленточная 5-диагональная матрица): Аппаратным способом умножение реализуется поворотом этой матрицы на 135 градусов. Таким образом, диагонали встают вертикально, и появляется возможность для каждого СП работать с одной диагональю. В указанной модели памяти значения из буфера1 каждый такт подаются по одному на СП, и далее по цепочке в фазе коммуникации между ними по стрелкам. На выходе из цепочки значения подаются каждый такт по одному в итоговые ячейки и там продвигаются. Схема продвижения данных по процессорам:
………………………………………………………………. и т.д. Всего при непосредственном подсчёте – 14 тактов.
Время передачи данных для задачи умножения матрицы 4х4 на вектор 4х1 Реализация умножения с накоплением: а -> рег1 b -> рег2 рег1 * рег2 -> c c -> рег1 S -> рег2 рег1 + рег2 -> S Итого (3 + 3) операции на умножение с накоплением. Критерии сравнения параллельных и последовательных алгоритмов: Абсолютное время выполнения
Ускорение вычислений
Потенциально возможное ускорение вычислений Для последовательного алгоритма используется 1 ПЭ, его ускорение будет 1. Для параллельного в данной задаче используется 5 ПЭ, и теоретически возможное максимальное ускорение – в 5 раз. Однако процессорное время используется не полностью, притом процессоры работают через один, поэтому на самом деле ускорение меньше.
Вычислим приблизительное ускорение параллельного алгоритма с 5 СП. Пусть:
(в процентах)
Тогда
то есть на малых данных преимущества параллельного алгоритма не сказываются. Качественный критерий
I –неправильный результат II – область оптимистического ускорения: алгоритм можно улучшить III – область нормального ускорения IV – область оптимистического ускорения: алгоритм можно улучшить
log25 = 2.3 (примерно), то есть полученный результат 1.8 находится в области пессимистического ускорения, и алгоритм можно улучшить.
Поиск по сайту: |
