The serial-parallel summation method, scalability: различия между версиями
Перейти к навигации
Перейти к поиску
| [досмотренная версия] | [досмотренная версия] |
ASA (обсуждение | вклад) |
ASA (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
{{level-i}} | {{level-i}} | ||
| − | Основные авторы описания: [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|3]]) | + | Основные авторы описания: [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|3]]) |
= Ссылки = | = Ссылки = | ||
| − | [ | + | [https://gitlab.srcc.msu.ru/alex-teplov/Scalability/blob/master/arraysum/arraysum.c Исследованная реализация алгоритма на языке C]. |
= Локальность данных и вычислений = | = Локальность данных и вычислений = | ||
| Строка 15: | Строка 15: | ||
== Масштабируемость реализации алгоритма == | == Масштабируемость реализации алгоритма == | ||
| − | [[file:Масштабируемость производительность ссумирования элементов массива.png|thumb|center|700px| | + | [[file:Масштабируемость производительность ссумирования элементов массива.png|thumb|center|700px|Рисунок 1. Параллельная реализация Суммирования элементов массива Максимальная производительность. ]] |
| − | [[file:Масштабируемость суммирования элементов массива Эффективность.png|thumb|center|700px| | + | [[file:Масштабируемость суммирования элементов массива Эффективность.png|thumb|center|700px|Рисунок 2. Параллельная реализация суммирования элементов массива Максимальная эффективность. ]] |
| − | + | Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма: | |
| − | + | * число процессоров [2 : 256] | |
| − | * | + | * размер вектора [80000000:320000000] |
| − | * | + | Эффективность выполнения реализации алгоритма |
| − | + | * Минимальная эффективность 0,00004% | |
| − | + | * Максимальная эффективность 0,0037% | |
| − | * | + | Оценка масштабируемости |
| − | * | + | * По числу процессов: -9.432e-07 – при увеличении числа процессов эффективность уменьшается на рассмотренной области изменений параметров запуска, однако, в целом уменьшение не интенсивное. Это объясняется тем, что при увеличении числа процессов сильно возрастает доля накладных расходов на организацию схемы сдваивания суммирования, однако, так как общая эффективность составляет доли процента интенсивность сильная только при переходе от работы процессов в рамках одного физического узла к использованию коммуникационной сети. В остальной области рассмотренных значений параметров запуска эффективность близка к 0 в силу того, что на каждый процесс приходится чрезвычайно малая доля вычислений. Больше полезного времени уходит на организацию работы процессов. |
| − | + | * По размеру задачи: 1.881e-06 – при увеличении размера задачи эффективность в целом очень незначительно увеличивается по рассматриваемой области. Это объясняется общим увеличением вычислительной сложности задачи в связи с увеличением размерности. Однако вычислительная сложность алгоритма <math>(N-1)</math>не позволяет существенно увеличить долю времени затрачиваемую на вычисления. | |
| − | + | * По двум направлениям: -1.423e-07 – при рассмотрении увеличения как вычислительной сложности, так и числа процессов по всей рассмотренной области значений эффективность уменьшается, однако интенсивность уменьшения эффективности небольшая. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров несущественная говорит о том, что на поверхности присутствуют области с очень интенсивным изменением эффективности на участке 2-16 процессов, но очень малые по площади. На остальной поверхности изменения эффективности незначительны и находятся на приблизительно одном и том же уровне. | |
| − | * | ||
| − | * | ||
| − | * | ||
= Динамические характеристики и эффективность реализации алгоритма = | = Динамические характеристики и эффективность реализации алгоритма = | ||
Текущая версия на 15:06, 8 июля 2022
Основные авторы описания: А.М.Теплов (раздел 3)
Содержание
1 Ссылки
Исследованная реализация алгоритма на языке C.
2 Локальность данных и вычислений
2.1 Локальность реализации алгоритма
2.1.1 Структура обращений в память и качественная оценка локальности
2.1.2 Количественная оценка локальности
3 Масштабируемость алгоритма и его реализации
3.1 Масштабируемость алгоритма
3.2 Масштабируемость реализации алгоритма
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
- число процессоров [2 : 256]
- размер вектора [80000000:320000000]
Эффективность выполнения реализации алгоритма
- Минимальная эффективность 0,00004%
- Максимальная эффективность 0,0037%
Оценка масштабируемости
- По числу процессов: -9.432e-07 – при увеличении числа процессов эффективность уменьшается на рассмотренной области изменений параметров запуска, однако, в целом уменьшение не интенсивное. Это объясняется тем, что при увеличении числа процессов сильно возрастает доля накладных расходов на организацию схемы сдваивания суммирования, однако, так как общая эффективность составляет доли процента интенсивность сильная только при переходе от работы процессов в рамках одного физического узла к использованию коммуникационной сети. В остальной области рассмотренных значений параметров запуска эффективность близка к 0 в силу того, что на каждый процесс приходится чрезвычайно малая доля вычислений. Больше полезного времени уходит на организацию работы процессов.
- По размеру задачи: 1.881e-06 – при увеличении размера задачи эффективность в целом очень незначительно увеличивается по рассматриваемой области. Это объясняется общим увеличением вычислительной сложности задачи в связи с увеличением размерности. Однако вычислительная сложность алгоритма [math](N-1)[/math]не позволяет существенно увеличить долю времени затрачиваемую на вычисления.
- По двум направлениям: -1.423e-07 – при рассмотрении увеличения как вычислительной сложности, так и числа процессов по всей рассмотренной области значений эффективность уменьшается, однако интенсивность уменьшения эффективности небольшая. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров несущественная говорит о том, что на поверхности присутствуют области с очень интенсивным изменением эффективности на участке 2-16 процессов, но очень малые по площади. На остальной поверхности изменения эффективности незначительны и находятся на приблизительно одном и том же уровне.
