Cooley-Tukey, scalability: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
ASA (обсуждение | вклад) |
ASA (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
Основные авторы описания: [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|1.2]]) | Основные авторы описания: [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|1.2]]) | ||
| − | + | = Программная реализация алгоритма: Cooley-Tukey, scalability = | |
Исследованная [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]] | ||
Версия 12:16, 1 июля 2022
Основные авторы описания: А.М.Теплов (раздел 1.2)
Содержание
1 Программная реализация алгоритма: Cooley-Tukey, scalability
Исследованная параллельная реализация алгоритма.
1.1 Локальность данных и вычислений
1.1.1 Локальность реализации алгоритма
1.1.1.1 Структура обращений в память и качественная оценка локальности
1.1.1.2 Количественная оценка локальности
1.2 Масштабируемость алгоритма и его реализации
1.2.1 Масштабируемость алгоритма
1.2.2 Масштабируемость реализации алгоритма
Набор и границы значений изменяемых параметров запуска реализации алгоритма:
- число процессоров [4, 8 : 64] с шагом 8;
- размер вектора [128 : 32768] с шагом равным степени двойки.
В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:
- минимальная эффективность реализации 0.000000002% (1.85994069951e-09%);
- максимальная эффективность реализации 0.00002% (2.07351573426e-05%).
На следующих рисунках приведены графики производительности и эффективности выбранной реализации алгоритма в зависимости от изменяемых параметров запуска.
Алгоритм в силу своих особенностей имеет крайне низкую эффективность параллельного выполнения, связанную с крайне малым объемом вычислений на каждый процесс. Из-за этого накладные расходы на организацию параллельного выполнения становятся доминирующими при выполнении алгоритма.
