Cooley-Tukey, scalability: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [досмотренная версия] |
ASA (обсуждение | вклад) Нет описания правки |
ASA (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
Основные авторы описания: [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|1.2]]) | Основные авторы описания: [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|1.2]]) | ||
= | = Ссылки = | ||
Исследованная [https://gitlab.srcc.msu.ru/alex-teplov/Scalability/blob/master/Cooley-Tukey/fft.c параллельная реализация алгоритма]. | Исследованная [https://gitlab.srcc.msu.ru/alex-teplov/Scalability/blob/master/Cooley-Tukey/fft.c параллельная реализация алгоритма]. | ||
= Локальность данных и вычислений = | |||
== Локальность реализации алгоритма == | |||
=== Структура обращений в память и качественная оценка локальности === | |||
=== Количественная оценка локальности === | |||
= Масштабируемость алгоритма и его реализации = | |||
== Масштабируемость алгоритма == | |||
== Масштабируемость реализации алгоритма == | |||
Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма: | Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма: | ||
| Строка 30: | Строка 30: | ||
Алгоритм в силу своих особенностей имеет крайне низкую эффективность параллельного выполнения, связанную с крайне малым объемом вычислений на каждый процесс. Из-за этого накладные расходы на организацию параллельного выполнения становятся доминирующими при выполнении алгоритма. | Алгоритм в силу своих особенностей имеет крайне низкую эффективность параллельного выполнения, связанную с крайне малым объемом вычислений на каждый процесс. Из-за этого накладные расходы на организацию параллельного выполнения становятся доминирующими при выполнении алгоритма. | ||
= Динамические характеристики и эффективность реализации алгоритма = | |||
= Результаты прогонов = | |||
[[Категория:Статьи в работе]] | [[Категория:Статьи в работе]] | ||
[[En:Cooley-Tukey, scalability]] | [[En:Cooley-Tukey, scalability]] | ||
Версия от 09:20, 1 июля 2022
Основные авторы описания: А.М.Теплов (раздел 1.2)
Ссылки
Исследованная параллельная реализация алгоритма.
Локальность данных и вычислений
Локальность реализации алгоритма
Структура обращений в память и качественная оценка локальности
Количественная оценка локальности
Масштабируемость алгоритма и его реализации
Масштабируемость алгоритма
Масштабируемость реализации алгоритма
Набор и границы значений изменяемых параметров запуска реализации алгоритма:
- число процессоров [4, 8 : 64] с шагом 8;
- размер вектора [128 : 32768] с шагом равным степени двойки.
В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:
- минимальная эффективность реализации 0.000000002% (1.85994069951e-09%);
- максимальная эффективность реализации 0.00002% (2.07351573426e-05%).
На следующих рисунках приведены графики производительности и эффективности выбранной реализации алгоритма в зависимости от изменяемых параметров запуска.
Алгоритм в силу своих особенностей имеет крайне низкую эффективность параллельного выполнения, связанную с крайне малым объемом вычислений на каждый процесс. Из-за этого накладные расходы на организацию параллельного выполнения становятся доминирующими при выполнении алгоритма.