|
|
| (не показано 70 промежуточных версий этого же участника) |
| Строка 1: |
Строка 1: |
| Данный документ содержит описание схемы, по которой предлагается описывать свойства и структуру каждого алгоритма. Описание состоит из двух частей. В [[#ЧАСТЬ. Свойства и структура алгоритмов|первой части]] описываются собственно алгоритмы и их свойства, а [[#ЧАСТЬ. Программная реализация алгоритмов|вторая]] посвящена описанию особенностей их программной реализации с учетом конкретных программно-аппаратных платформ. Такое деление на части сделано для того, чтобы машинно-независимые свойства алгоритмов, которые определяют качество их реализации на параллельных вычислительных системах, были бы выделены и описаны отдельно от множества вопросов, связанных с последующими этапами программирования алгоритмов и исполнения результирующих программ.
| | Виктория Евстефеева, 416 группа. |
|
| |
|
| Общая схема описания алгоритмов имеет следующий вид:
| | [https://algowiki-project.org/ru/EM_Алгоритм_для_пуассон_трехточечного_распределения ЕМ алгоритм для пуассон-трехточечного распределения] |
| | |
| == Свойства и структура алгоритмов ==
| |
| | |
| | |
| Содержание [убрать]
| |
| 1 Свойства и структура алгоритмов
| |
| 1.1 Общее описание алгоритма
| |
| 1.2 Математическое описание алгоритма
| |
| 1.3 Вычислительное ядро алгоритма
| |
| 1.4 Макроструктура алгоритма
| |
| 1.5 Схема реализации последовательного алгоритма
| |
| 1.6 Последовательная сложность алгоритма
| |
| 1.7 Информационный граф
| |
| 1.8 Ресурс параллелизма алгоритма
| |
| 1.9 Входные и выходные данные алгоритма
| |
| 1.10 Свойства алгоритма
| |
| 2 Программная реализация алгоритма
| |
| 2.1 Особенности реализации последовательного алгоритма
| |
| 2.2 Локальность данных и вычислений
| |
| 2.3 Возможные способы и особенности параллельной реализации алгоритма
| |
| 2.4 Масштабируемость алгоритма и его реализации
| |
| 2.5 Динамические характеристики и эффективность реализации алгоритма
| |
| 2.6 Выводы для классов архитектур
| |
| 2.7 Существующие реализации алгоритма
| |
| 3 Литература
| |
| '''1 Свойства и структура алгоритмов[править]'''
| |
| | |
| 1.1 Общее описание алгоритма[[[править]]]
| |
| EM-алгоритм (англ. expectation-maximization) - алгоритм итерационного типа для численного решения задачи поиска экстремума целевой функции в разнообразных задачах оптимизации. В частности, алгоритм используется в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости.
| |
| | |
| Как правило, ЕМ-алгоритм применяется для решения задач двух типов.
| |
| 1. К первому типу можно отнести задачи, связанные с анализом действительно неполных данных, когда некоторые статистические данные отсутствуют в силу каких-либо причин.
| |
| 2. Ко второму типу задач можно отнести статистические задачи, в которых функция правдоподобия имеет вид, не допускающий удобных аналитических методов исследования, но допускающий серьезные упрощения, если в задачу ввести дополнительные «ненаблюдаемые» (скрытые, латентные) переменные. Примерами прикладных задач второго типа являются задачи распознавания образов, реконструкции изображений. Математическую суть данных задач составляют задачи кластерного анализа, классификации и разделения смесей вероятностных распределений.
| |
| | |
| 1.2 Математическое описание алгоритма[править]
| |
| | |
| 1.3 Вычислительное ядро алгоритма[править]
| |
| | |
| 1.4 Макроструктура алгоритма[править]
| |
| | |
| 1.5 Схема реализации последовательного алгоритма[править]
| |
| | |
| 1.6 Последовательная сложность алгоритма[править]
| |
| 1.7 Информационный граф[править]
| |
| 1.8 Ресурс параллелизма алгоритма[править]
| |
| | |
| 1.9 Входные и выходные данные алгоритма[править]
| |
| | |
| 1.10 Свойства алгоритма[править]
| |
| | |
| 2 Программная реализация алгоритма[править]
| |
| | |
| 2.1 Особенности реализации последовательного алгоритма[править]
| |
| | |
| 2.2 Локальность данных и вычислений[править]
| |
| 2.3 Возможные способы и особенности параллельной реализации алгоритма[править]
| |
| | |
| 2.4 Масштабируемость алгоритма и его реализации[править]
| |
| 2.5 Динамические характеристики и эффективность реализации алгоритма[править]
| |
| | |
| 2.6 Выводы для классов архитектур[править]
| |
| | |
| 2.7 Существующие реализации алгоритма[править]
| |
| | |
| 3 Литература[править]
| |
| ↑ http://www.machinelearning.ru/wiki/index.php?title=EM-алгоритм
| |
| Перейти ↑ Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.
| |
| Перейти ↑ Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.
| |
| Перейти ↑ Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.
| |
| Перейти ↑ Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.
| |