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