ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ИНТЕРВАЛЬНОЙ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ Лозбень М.Е.

Презентация:



Advertisements
Похожие презентации
Стохастические интервальные подходы в задачах глобальной оптимизации Интервальный генетический алгоритм Н. В. Панов, С. П. Шарый Институт вычислительных.
Advertisements

Панов Н.В. КТИ ВТ CО РАН Новосибирск. Решатель Интервальные алгоритмы адаптивного дробления Классические алгоритмы Интервальные методы распространени.
Доработка контроллера памяти DDR2 SDRAM МП Эльбрус-S для МП Эльбрус-S2 Научный руководитель: Шерстнёв Андрей Кожин Алексей, ФРТК 513 гр.
Разработка контроллера обрабатываемых запросов кэш памяти третьего уровня микропроцессора "Эльбрус-4С+" Студент: Кожин Евгений, группа 713 Научный руководитель:
Сравнительный анализ некоторых методов композиции вычислительных подобластей студент: Данилин Александр научный руководитель: Илюшин Александр Иванович.
Выполнили: Мартышкин А. И. Кутузов В. В., Трояшкин П. В., Руководитель проекта – Мартышкин А. И., аспирант, ассистент кафедры ВМиС ПГТА.
Разработка интерфейса между системным коммутатором и контроллером памяти с использованием протокола AXI Выпускная квалификационная работа на соискание.
1 этап. Постановка задачи 2 этап. Анализ и исследование задачи 3 этап. Разработка алгоритма 4 этап. Разработка программы 5 этап. Тестирование и отладка.
Разработка кэша справочника для вычислительного комплекса на базе микропроцессора Эльбрус – 2S Студент : Петров Игорь, ФРТК, 613 группа Научный руководитель:
1 Разработка и анализ параллельных поисковых структур данных, не чувствительных к размеру кеша Акишев Искандер Рустемович Научный руководитель: Елизаров.
Дипломная работа Ивановой О.О., группа 545 Научный руководитель: д. ф.-м. н., профессор Терехов А.Н. Генерация кода по диаграмме активностей.
Разработка модулей коммутации данных в микропроцессоре « Эльбрус -4 С +» Выпускная квалификационная работа на соискание степени бакалавра студента 816.
Операционные системы тема: Задачи ос Блинов Никита 229 к
Московский физико-технический институт (государственный университет) Факультет радиотехники и кибернетики Кафедра информатики и вычислительной техники.
Язык Рефлекс – диалект Си для программирования ПЛК Зюбин В.Е. Тем.группа «Языки технологического программирования»
Выпускная квалификационная работа Исследование аппаратной предвыборки данных в кэш второго уровня микропроцессора Студент: Гребенкин А.П., 816 гр. Научный.
Параллельная реализация экономичных методов параболических задач.
1 Трус Мария Александровна ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ.
Разработка 4-х канального контроллера оперативной памяти DDR3 SDRAM с интерфейсом AXI Студент: Кожин А.С., ФРТК, 515 гр. Научный руководитель: д.т.н.,
Реализация распараллеливания программного комплекса расчета двумерных задач газовой динамики с помощью системы OST Научный руководитель: Илюшин А. И. Колмаков.
Транксрипт:

ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ИНТЕРВАЛЬНОЙ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ Лозбень М.Е.

ПОСТАНОВКА ЗАДАЧИ min f(x) = ? Задача глобальной доказательной (гарантированной) оптимизации вещественнозначной многомерной функции на брусе со сторонами, параллельными координатным осям

ЦЕЛЬ РАБОТЫ Разработка и реализация наиболее эффективного для распараллеливания алгоритма гарантированной глобальной оптимизации

1. Выбрать перспективную область. 2. Раздробить выбранную область на подобласти. 3. Вычислить интервальное расширение функции на полученных подобластях. ОПИСАНИЕ АЛГОРИТМА ИНТЕРВАЛЬНОГО ДРОБЛЕНИЯ

ВЫБОР ВЕДУЩЕГО БРУСА

1. Выбрать перспективную область. 2. Раздробить выбранную область на подобласти. 3. Вычислить интервальное расширение функции на полученных подобластях. ОПИСАНИЕ АЛГОРИТМА ИНТЕРВАЛЬНОГО ДРОБЛЕНИЯ

ДРОБЛЕНИЕ ВЕДУЩЕГО БРУСА Ведущий брус Брус - потомок f(x)

1. Выбрать перспективную область. 2. Раздробить выбранную область на подобласти. 3. Вычислить интервальное расширение функции на полученных подобластях. ОПИСАНИЕ АЛГОРИТМА ИНТЕРВАЛЬНОГО ДРОБЛЕНИЯ

ОТБРАКОВКА БРУСОВ I2I2 I1I1 f(x)

«НАИВНОЕ» РАСПАРАЛЛЕЛИВАНИЕ n независимых потоков исходная область разбивается на n подобластей на каждой подобласте в отдельном потоке запускается свой алгоритм потоки не взаимодействуют

«АДАПТИВНОЕ» РАСПАРАЛЛЕЛИВАНИЕ n потоков контроллер своя исходная область для каждого потока свой тип алгоритма для каждого потока тесное межпотоковое взаимодействие

«АДАПТИВНОЕ» РАСПАРАЛЛЕЛИВАНИЕ контроллер поток 1 поток 2поток 3 поток n решатель...

ПРЕДЫДУЩИЕ РЕАЛИЗАЦИИ схема параллельного алгоритма Сони Бернер (Journal of Global Optimization 9,1996 )

ОТБРАКОВКА БРУСОВ I2I2 I1I1 f(x)

МЕЖПОТОКОВОЕ ВЗАИМОДЕЙСТВИЕ общая переменная ошибка параллельной модификации данных синхронизованный доступ блокировка потоков неблокирующая конкурентная запись дополнительные синхронизации кэша выделенная логика контроллера сложность реализации

ОБЩАЯ ПЕРЕМЕННАЯ переменнаяпоток 1 поток 2 запись чтение

МЕЖПОТОКОВОЕ ВЗАИМОДЕЙСТВИЕ общая переменная ошибка параллельной модификации данных синхронизованный доступ блокировка потоков неблокирующая конкурентная запись дополнительные синхронизации кэша выделенная логика контроллера сложность реализации

СИНХРОНИЗОВАННЫЙ ДОСТУП переменная активный поток ждущие потоки блокировка обмен данными

МЕЖПОТОКОВОЕ ВЗАИМОДЕЙСТВИЕ общая переменная ошибка параллельной модификации данных синхронизованный доступ блокировка потоков неблокирующая конкурентная запись дополнительные синхронизации кэша выделенная логика контроллера сложность реализации

НЕБЛОКИРУЮЩАЯ КОНКУРЕНТНАЯ ЗАПИСЬ ядро кэш переменная в кэше переменная в кэше оперативная память переменная

МЕЖПОТОКОВОЕ ВЗАИМОДЕЙСТВИЕ общая переменная ошибка параллельной модификации данных синхронизованный доступ блокировка потоков неблокирующая конкурентная запись дополнительные синхронизации кэша выделенная логика контроллера сложность реализации

ВЫДЕЛЕННАЯ ЛОГИКА КОНТРОЛЛЕРА поток 1 поток 2 поток 3 поток 4 переменная потока 1 переменная потока 4 переменная потока 3 переменная потока 2 КОНТРОЛЛЕР итоговое состояние

РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТОВ Время поиска оптимума

СПАСИБО ЗА ВНИМАНИЕ! Докладчик : Михаил Лозбень Научный руководитель : Никита Панов