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