Линейная алгебра и мат. Статистика
жүктеу/скачать 294.26 Kb.
|
- Бұл бет үшін навигация:
- Эффективность
- Закон Амдала
- Классификация параллельных вычислительных систем
| Закон Амдала описывает способ, с помощью которого можно моделировать потенциальный выигрыш в производительности при параллельных вычислениях.
Ускорение и эффективность Ускорение (speedup), получаемое при использовании параллельного алгоритма для p процессоров, по сравнению с последовательным вариантом выполнения вычислений определяется величиной: т.е. как отношение времени решения задач на скалярном процессоре (оценка определяет время выполнения алгоритма при использовании одного процессора и представляет, тем самым, время выполнения последовательного варианта алгоритма решения задачи) к времени выполнения параллельного алгоритма (величина применяется для параметризации вычислительной сложности решаемой задачи и может пониматься, например, как количество входных данных задачи). Эффективность (efficiency) использования параллельным алгоритмом процессоров при решении задачи определяется соотношением: Величина эффективности определяет среднюю долю времени выполнения алгоритма, в течение которой процессоры реально задействованы для решения задачи. Закон Амдала Иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей. Джин Амдал сформулировал закон в 1967 году, обнаружив простое по существу, но непреодолимое по содержанию ограничение на рост производительности при распараллеливании вычислений: «В случае, когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента». Согласно этому закону, ускорение выполнения программы за счёт распараллеливания её инструкций на множестве вычислителей ограничено временем, необходимым для выполнения её последовательных инструкций. Закон Амдала показывает, что прирост эффективности вычислений зависит от алгоритма задачи и ограничен сверху для любой задачи с . Не для всякой задачи имеет смысл наращивание числа процессоров в вычислительной системе. Более того, если учесть время, необходимое для передачи данных между узлами вычислительной системы, то зависимость времени вычислений от числа узлов будет иметь максимум. Это накладывает ограничение на масштабируемость вычислительной системы, то есть означает, что с определенного момента добавление новых узлов в систему будет увеличивать время расчёта задачи. Классификация параллельных вычислительных систем Общая классификация архитектур ЭВМ по признакам наличия параллелизма в потоках команд и данных. Была предложена в 70-е годы Майклом Флинном (Michael Flynn). Все разнообразие архитектур ЭВМ в этой таксономии Флинна сводится к четырем классам: ОКОД — Вычислительная система с одиночным потоком команд и одиночным потоком данных (SISD, Single Instruction stream over a Single Data stream). ОКМД — Вычислительная система с одиночным потоком команд и множественным потоком данных (SIMD, Single Instruction, Multiple Data). Типичными представителями SIMD являются векторные архитектуры. МКОД — Вычислительная система со множественным потоком команд и одиночным потоком данных (MISD, Multiple Instruction Single Data). К классу MISD ряд исследователей относит конвейерные ЭВМ, однако это не нашло окончательного признания, поэтому можно считать, что реальных систем — представителей данного класса не существует. МКМД — Вычислительная система со множественным потоком команд и множественным потоком данных (MIMD, Multiple Instruction Multiple Data). Класс MIMD включает в себя многопроцессорные системы, где процессоры обрабатывают множественные потоки данных. Отношение конкретных машин к конкретному классу сильно зависит от точки зрения исследователя. Так, конвейерные машины могут быть отнесены и к классу SISD (конвейер — единый процессор), и к классу SIMD (векторный поток данных с конвейерным процессором) и к классу MISD (множество процессоров конвейера обрабатывают один поток данных последовательно), и к классу MIMD — как выполнение последовательности различных команд (операций ступеней конвейера) на множественным скалярным потоком данных (вектором). Распараллеливание алгоритмов Примеры задач, в которых используется распараллеливание: Одновременное выполнение операций ввода/вывода. Формирование и обнуление массива. Арифметические и логические операции над векторами и матрицами. Одновременное отслеживание ветвей в различных узлах дерева. Конвейерная обработка. Решение СЛАУ большого порядка. Параллельная сортировка. Поиск максимума/минимума функции. Наиболее желательными (даже скорее обязательными) признаками параллельных алгоритмов и программ являются: жүктеу/скачать 294.26 Kb. Достарыңызбен бөлісу:
|