WWW.KNIGA.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Книги, пособия, учебники, издания, публикации

 


Введение в параллельные

методы

Якобовский Михаил Владимирович

проф., д.ф.-м.н.

зав. сектором «Программного проф. кафедры суперкомпьютеров

обеспечения многопроцессорных и квантовой информатики

систем и вычислительных сетей» ВМК МГУ им. М.В.Ломоносова

Института прикладной математики

им. М.В.Келдыша Российской академии

наук

mail: lira@imamod.ru web: http://lira.imamod.ru Метод конвейерного параллелизма kn T1 (kn) = c kn Tp (kn) = c + ?

p Введение в параллельные методы Москва, 2013 г. © Якобовский М.В.

Метод конвейерного параллелизма kn n T1 (kn) = c kn Tp (kn) = c + k s p p 1 S p (kn) = p E p (kn) = s s 1+ 1+ c c Введение в параллельные методы Москва, 2013 г. © Якобовский М.В.

Метод конвейерного параллелизма for(t=0; ttmax; t+=dt) { fnew[0]=g(t);

for(i=1; in; i++) fnew[i]= fnew[i-1]+f[i] for(i=0;in;i++) f[i] = fnew [i] fnew[i] } f[i] 0 1 2 3 4 5 6 Введение в параллельные методы Москва, 2013 г. © Якобовский М.В.

Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор Введение в параллельные методы Москва, 2013 г. © Якобовский М.В.

Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор Введение в параллельные методы Москва, 2013 г. © Якобовский М.В.

Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор Введение в параллельные методы Москва, 2013 г. © Якобовский М.В.

Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор Учет стартовых и финальных затрат Учет стартовых и финальных затрат Максимальная степень параллелизма:

Максимальное ускорение:

Простые методы построения параллельных алгоритмов:

– Статическая балансировка • геометрический параллелизм – Динамическая балансировка • диффузная балансировка загрузки d=a[i]+b[i]+r;

r=d/10;

c[i]=r;

Последовательное распространение разряда переноса на четырёх процессорах • Спекулятивное вычисление двух сумм • Спекулятивное вычисление двух сумм • Потребность в суперкомпьютерах высока • Эффективность использования суперкомпьютеров низка:

– Использование каждого ядра последовательной программой составляет проценты и доли процентов – Обмены, синхронизация и другие дополнительные операции ещё снижают эффективность параллельной программы • Есть минимальный объем вычислений на процессорное ядро, определяющий число используемых ядер • За счет многопроцессорности сложно сокращать время моделирования физического процесса, но можно повышать сложность решаемых задач, например за счет увеличения размеров изучаемых объектов Дозвуковая аэродинамическая Скорость потока 10–120 м/с Диаметр сопла 7 м Длина рабочей части 13 м Мощность вентилятора http://www.tsagi.ru/rus/base/t Суперкомпьютер СКИФ МГУ «ЧЕБЫШЁВ»





• Пиковая производительность 60 TFlop/s Мощность комплекса 0.72 МВт http://parallel.ru/cluster/skif_msu.html Тетраэдральные сетки 108 узлов Использование адаптивной сетки Обтекание профиля NACA (M=0.85, Re=104) под нулевым углом атаки:

Поле продольной скорости Фрагмент сетки Круглое пятно примеси 0. 0. 0. 0. 0. 0. 0. 0. 0. Слева – ??круглое?? пятно примеси 0. 0. 0. 0. 0. 0. 0. 0. 0. Слева – круглое пятно примеси 0. 0. 0. 0. 0. 0. 0. 0. 0. Адаптивные декартовы сетки Вначале сетка состоит из одной прямоугольной ячейки Каждая ячейка может быть разделена на четыре ячейки одинакового размера Если ячейки когда-то составляли одну ячейку, то они могут быть объединены обратно Каждая ячейка хранит величину, описывающую среднее значение неизвестной функции в пределах ячейки (метод конечных объёмов) При данных предположениях сетку удобно хранить в виде четверичного дерева:

Дополнительные ограничения на размеры ячеек:

• Задан максимально допустимый размер ячеек • Задан минимально допустимый размер ячеек • Размеры соседних ячеек должны различаться не более, чем в 2 раза Сравнение с равномерной сеткой На рисунках показаны результаты решения простейшей задачи переноса на равномерной (слева) и адаптивной (справа) сетках с одинаковым числом ячеек (4096 штук). Скорость переноса направлена под углом 45° к линиям сетки; начальное условие показано пунктиром Адаптивная сетка Решение двумерной задачи фильтрации нефтеводяной смеси в области с неоднородной проницаемостью скважина, нагнетающая воду, в северовосточном углу — добывающая Решение двумерной задачи фильтрации нефтеводяной смеси в области с неоднородной проницаемостью скважина, нагнетающая воду, в северовосточном углу — добывающая Пакетный режим исполнения и отладки приложений Процедуры авторизованного доступа к удаленным системам Высокая динамика изменения конфигурации суперкомпьютеров Несоизмеримость ресурсов рабочей станции пользователя и суперкомпьютера Статическая балансировка загрузки • Критерии декомпозиции • Инкрементный алгоритм декомпозиции • Иерархическая обработка больших сеток Простое разбиение на 32 домена Рациональное разбиение Рациональное разбиение Критерии декомпозиции графов • Равномерное распределение суммарного веса узлов/рёбер • Минимизация максимального веса исходящих из домена ребер • Минимизация суммарного веса разрезанных ребер • Минимизация максимальной степени доменов • Обеспечение связности доменов • Обеспечение связности множества внутренних узлов доменов Критерии декомпозиции графов • Равномерное распределение суммарного THREAD веса узлов/рёбер исходящих из домена ребер • Минимизация суммарного веса разрезанных ребер • Минимизация максимальной степени доменов • Обеспечение связности доменов Критерии декомпозиции графов • Равномерное распределение суммарного веса узлов/рёбер • Минимизация максимального веса исходящих из домена ребер • Минимизация суммарного веса разрезанных ребер • Минимизация максимальной степени доменов • Обеспечение связности доменов • Обеспечение связности множества внутренних узлов А.Н. Андрианов, А.В. Жохова, Б.Н. доменов Критерии декомпозиции графов • Равномерное распределение суммарного веса узлов/рёбер • Минимизация максимального веса исходящих из домена ребер • Минимизация суммарного веса разрезанных ребер • Минимизация максимальной степени доменов • Обеспечение связности доменов • Обеспечение связности множества внутренних узлов доменов • Разрезать решетку 5 х 5 на 4 части Декомпозиция сетки из 25 узлов на 4 части • Декомпозиция решетки 5 х 5 на 4 домена • Дисбаланс 9/4=2. • Декомпозиция решетки 5 х 5 на 4 домена Декомпозиция сетки 25х25 на 7 частей Пакеты декомпозиции графов Chaco Bruce Hendrickson ParMETIS George Karypis PARTY Robert Prais, et al.

JOSTLE Chris Walshaw, et al.

SCOTCH Francois Pellegrini Иерархический алгоритм Огрубление Огрубление графа Декомпозиция пакетом Metis Hilbert-curve ordering This ordering can be built by simple recursive procedure.

When mesh changes locally, Hilbert curve changes locally too.

It cannot be used for parallel computations due to chain dependence of elements.

Декомпозиция по кривой Гильберта Сетка предварительно разбивается Вершины макрографа на большое число микродоменов, распределяются по процессорам образующих макрограф Разбиение тетраэдральной сетки, содержащей 2108 узлов, вычисления производились на кластере СКИФ МГу (1250 4-хядерных процессоров, 60 TFlop/s) число вершин в домене среднее число связей с соседними доменами число некомпактных Треугольная сетка из 75790 вершин (пространство вокруг крыла) результат геометрической декомпозиции на 5 групп (в дальнейшем каждый процессор считывает свою группу вершин) Фрагмент треугольной сетки из результат геометрической результат перераспределения Результат локального разбиения сетки из 75790 вершин Результат сбора плохих групп доменов и их повторного Инкрементный алгоритм декомпозиции Инкрементный алгоритм декомпозиции Инкрементный алгоритм декомпозиции Инкрементный алгоритм декомпозиции Редуцирование доменов один домен свободные вершины Инкрементный алгоритм, Dm= Инкрементный алгоритм, Dm= Kmetis, Dm= Стратегии балансировки загрузки Wij - вычислительная нагрузка, ассоциированная с узлом сетки i на шаге j Динамическая балансировка загрузки © Якобовский Москва, 2012 г.

Москва, 2013 г.

Динамичекая балансировка Компьютер пользователя на порядки слабее суперкомпьютера 1 Pflops 100 G Визуализация сеточных данных • Расчет • Запись результатов VISIT ParaView Огрубление поверхностей Ошибка 3.54 бинарный без компрессии без огрубления 10^9 узлов - 113 354 035 байт – Зависимость коэффициента сжатия от числа усеченных бит 1. 0. 0. 0. Экзафлопсный барьер: проблемы и решения Виктор Горбунов, Леонид Эйсымонт Открытые системы :: Платформы, http://www.osp.ru/os/2010/05/13003034/ Заключение Время однопроцессорных вычислительных систем прошло.

Не только суперкомпьютеры, но и современные персональные компьютеры, ноутбуки, планшеты, мобильные телефоны, основаны на многопроцессорных, многоядерных и других технологиях, предполагающих одновременное выполнение множества инструкций.

Для их полноценного использования необходима и разработка новых, логически простых алгоритмов, и знание базовых методов разработки параллельных алгоритмов и приложений.

• Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВПетербург, 2002.

• Якобовский М.В. Введение в параллельные методы решения задач:

Учебное пособие / Предисл.: В. А. Садовничий. – М.: Издательство Московского университета, 2013. – 328 с., илл. – (Серия «Суперкомпьютерное образование») ISBN 978-5-211-06382- • Грегори Р. Эндрюс - Основы многопоточного, параллельного и распределенного программирования. "Вильямс ", • Языки программирования. Редактор Ф.Женюи. Перевод с англ.

В.П.Кузнецова. Под ред. В.М.Курочкина. М:."Мир", Э. Дейкстра. Взаимодействие последовательных процессов.

http://khpi-iip.mipk.kharkiv.edu/library/extent/dijkstra/ewd123/index.html Ресурсы Internet • http://parallel.ru • http://top500.org • http://supercomputers.ru Якобовский М.В.

проф., д.ф.-м.н., зав. сектором «Программного обеспечения многопроцессорных систем и вычислительных сетей»

Института прикладной математики им. М.В.Келдыша Российской академии наук проф. кафедры суперкомпьютеров и квантовой информатики ВМК МГУ им. М.В.Ломоносова mail: lira@imamod.ru http://lira.imamod.ru



Похожие работы:

«Электронное периодическое издание Вестник Дальневосточного государственного технического университета 2011 год № 3/4 (8/9) 25.00.00 Науки о Земле УДК 622.023.001.57 В.С. Куксенко, М.А. Гузев, В.В. Макаров, И.Ю. Рассказов Куксенко Виктор Степанович – д.ф.-м.н., профессор, главный научный сотрудник лаборатории физики прочности (Физико-технический института им. А.Ф. Иоффе РАН, Санкт-Петербург). E-mail: victor.kuksenko@mail.ioffe.ru Гузев Михаил Александрович – член-корреспондент РАН, директор...»

«Федеральное агентство по образованию АМУРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ГОУВПО АмГУ УТВЕРЖДАЮ Зав. кафедрой МАиМ Т. В. Труфанова _ 2007 г. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ПО ДИСЦИПЛИНЕ для специальности 010501 – Прикладная математика Составитель: Н.Н. Кушнирук Благовещенск 2007 г. Печатается по решению редакционно-издательского совета факультета математики и информатики Амурского государственного университета Кушнирук Н.Н....»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ НОВОКУЗНЕЦКИЙ ИНСТИТУТ (ФИЛИАЛ) ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ КЕМЕРОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ УТВЕРЖДЕНО на заседании Ученого совета факультета информационных технологий НФИ КемГУ председатель Ученого совета В.О. Каледин.. 2013г. протокол №. ОТЧЕТ по результатам самообследования ООП специальности 010501.65 Прикладная...»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Амурский государственный университет Кафедра общей математики и информатики УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ ЭКОНОМЕТРИКА Основной образовательной программы по направлению подготовки 080100.62 – Экономика Благовещенск 2013 2 УМКД разработан старшим преподавателем кафедры ОМиИ Киселевой Аленой Николаевной Рассмотрен и рекомендован на...»

«УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ ГОМЕЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ ФРАНЦИСКА СКОРИНЫ УДК 004.7: 004.93: 004.942 ОЛИЗАРОВИЧ Евгений Владимирович МЕТОД И ТЕХНОЛОГИЯ ПОСТРОЕНИЯ СИСТЕМ ДИАГНОСТИКИ КОМПЬЮТЕРНЫХ СЕТЕЙ НА ОСНОВЕ РАСПОЗНАВАНИЯ ОБРАЗОВ Автореферат диссертации на соискание ученой степени кандидата технических наук по специальности 05.13.13 – Телекоммуникационные системы и компьютерные сети Гомель, 2009 Работа выполнена в учреждении образования Гомельский государственный университет...»

«Министерство образования и наук и Российской Федерации Ярославский государственный университет им. П. Г. Демидова Сборник аннотаций курсовых и квалификационных работ математического факультета Ярославль 2012 Сборник аннотаций курсовых и квалификационных работ математического факультета. Яросл. гос. ун-т им. П. Г. Демидова. Ярославль: ЯрГУ, 2012. Сборник содержит аннотации курсовых и квалификационных работ студентов и магистрантов математического факультета Ярославского государственного...»

«Предисловие к третьему изданию Международный консорциум Электронный университет Московский государственный университет экономики, статистики и информатики Евразийский открытый институт Т.И. Захарова Организационное поведение Учебно-методический комплекс Москва 2008 1 Организационное поведение УДК 65 ББК 65.290-2 З 382 Захарова Т.И. ОРГАНИЗАЦИОННОЕ ПОВЕДЕНИЕ: Учебно-методический комплекс. – М.: Изд. центр ЕАОИ. 2008. – 330 с. ISBN 978-5-374-00117-4 © Захарова Т.И., 2008 © Евразийский открытый...»

«Высшее профессиональное образование БАКАЛАВрИАТ В. Г. БАУЛА, А. Н. ТОМИЛИН, Д. Ю. ВОЛКАНОВ АрхИТеКТУрА ЭВМ И ОперАцИОННые среДы Учебник Допущено Учебно-методическим объединением по классическому университетскому образованию в качестве учебника для студентов высших учебных заведений, обучающихся по направлениям 010400 Прикладная математика и информатика и 010300 Фундаментальная информатика и информационные технологии 2-е издание, стереотипное УДК 004.2(075.8) ББК 32.973-02я73 Б291 Рецензент—...»

«Понятийный аппарат теории информатизации высшего образования Л. В. Нефедова Евразийский национальный университет имени Л. Н. Гумилева Астана, Казахстан Из множества вопросов теории информатизации высшего образования мы остановимся лишь на определении понятия информатизация высшего образования, выявлении его содержания. Следует сразу подчеркнуть, что основополагающие понятия в области информатизации образования вообще сегодня определяются достаточно разнообразно, а иногда и противоречиво. Это...»

«УДК 007:681.3 Поддержка баз данных с онтологическими зависимостями на основе дескриптивных логик Л. А. Калиниченко leonidk@synth.ipi.ac.ru Институт проблем информатики РАН Россия, г. Москва, 117333, ул. Вавилова, 44/2 Аннотация. В статье1 дан краткий анализ состояния работ в области онтологически базированных систем доступа к данным и их возможного влияния на развитие информационных систем и баз данных2. Обсуждены вопросы соотношения онтологического и концептуального моделирования и...»

«УСТАНОВОЧНАЯ СЕССИЯ I КУРСА ЗАОЧНОГО ОТДЕЛЕНИЯ Институт информационных коммуникаций и библиотек ДИСЦИПЛИНА, МАТЕРИАЛЫ К СЕССИИ СПЕЦИАЛИЗАЦИЯ Вопросы Отечественная История как наука. Отечественные научно-исторические школы и их представители. 1. история Исторические источники и их виды. • библиотечноФормационный и цивилизационный подходы к периодизации истории. Западная и 2. информационная восточная цивилизации. деятельность (зачет) Восточные славяне в древности, этапы образования государства....»

«Хорошко Максим Болеславович РАЗРАБОТКА И МОДИФИКАЦИЯ МОДЕЛЕЙ И АЛГОРИТМОВ ПОИСКА ДАННЫХ В INTERNET/INTRANET СРЕДЕ ДЛЯ УЛУЧШЕНИЯ КАЧЕСТВА ПОИСКА Специальность 05.13. 17 – Теоретические основы информатики АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Новочеркасск – 2014 2 Работа выполнена на кафедре Информационные и измерительные системы и технологии ФГБОУ ВПО ЮРГПУ(НПИ) им М.И. Платова. Научный руководитель Воробьев Сергей Петрович кандидат...»

«Итоги научной деятельности Елабужского института КФУ за 2013 год Монографии (индивидуальные и коллективные), изданные: – зарубежными издательствами: 1. Зуева Г.А. Урбанофлора Елабуги в оценке экологического состояния города / Г.А. Зуева, Е.А. Афонина: Монография. – LAP Lambert Academic Publishing, Saarbruecken, Germany, 2013. – 110 с. 2. Капустина Т.В. Дифференциальная геометрия в среде Mathematica. Млнография: LAP Lambert Academic Publishing, Saarbruecken, Germany, 2013. -176 с. 3. Разживин...»

«ТЕХНИЧЕСКИЙ КОДЕКС ТКП 011-2005 (02140) УСТАНОВИВШЕЙСЯ ПРАКТИКИ ОРГАНИЗАЦИЯ И ПОРЯДОК ПРОВЕДЕНИЯ РАБОТ ПО ВЫБОРУ ИЗМЕРИТЕЛЬНОГО ОБОРУДОВАНИЯ АРГАНIЗАЦЫЯ I ПАРАДАК ПРАВЯДЗЕННЯ РАБОТ ПА ВЫБАРУ ВЫМЯРАЛЬНАГА АБСТАЛЯВАННЯ Издание официальное Минсвязи Минск ТКП 011-2005 УДК 389.14 МКС 17.020 КП 02 Ключевые слова: измерительное оборудование, метрологическая характеристика, тендер Предисловие Цели, основные принципы, положения по государственному регулированию и управлению в области технического...»

«2 3 СОДЕРЖАНИЕ Пояснительная записка 4с. Структура и содержание дисциплины 9с. Объем дисциплины и виды учебной работы 9с Тематический план лекций 10с Тематический план практических занятий и семинаров 10с Содержание лекций 11с Содержание практических занятий и семинаров 14с Критерии балльно-рейтинговой оценки знаний студентов 16с Самостоятельная работа студентов (аудиторная и внеаудиторная). 17с Учебно-методическое и информационное обеспечение дисциплины 20с Основная литература 20с...»

«Учреждение образования БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ МАКСИМА ТАНКА УДК 378.016:004.09 Жилинская Татьяна Степановна ФОРМИРОВАНИЕ ОСНОВ МЕДИАКУЛЬТУРЫ СТУДЕНТОВ ПРИ ОБУЧЕНИИ ИНФОРМАЦИОННЫМ ТЕХНОЛОГИЯМ (НА ПРИМЕРЕ СПЕЦИАЛЬНОСТИ КУЛЬТУРОЛОГИЯ) Автореферат диссертации на соискание ученой степени кандидата педагогических наук по специальности 13.00.02 – теория и методика обучения и воспитания (информатика) Минск, 2014 Работа выполнена в учреждении образования Белорусский...»

«ТЕХНИЧЕСКИЙ КОДЕКС ТКП 006–2005 (02140) УСТАНОВИВШЕЙСЯ ПРАКТИКИ ПОРЯДОК ПРОВЕДЕНИЯ МЕТРОЛОГИЧЕСКОЙ ЭКСПЕРТИЗЫ ТЕХНИЧЕСКОЙ ДОКУМЕНТАЦИИ ПАРАДАК ПРАВЯДЗЕННЯ МЕТРАЛАГIЧНАЙ ЭКСПЕРТЫЗЫ ТЭХНIЧНАЙ ДАКУМЕНТАЦЫI Издание официальное Минсвязи Минск ТКП 006-2005 УДК 389.14 МКС 17.020 КП 02 Ключевые слова: метрология, метрологическая экспертиза _ Предисловие Цели, основные принципы, положения по государственному регулированию и управлению в области технического нормирования и стандартизации установлены...»

«Российско-Американское сотрудничество по здравоохранению Проект Мать и Дитя Санкт-Петербургская государственная медицинская академия им. И.И.Мечникова Центральный научно-исследовательский институт организации и информатизации здравоохранения Министерства здравоохранения РФ Комитет по здравоохранению Администрации г.Санкт-Петербурга Медицинский Информационно-аналитический Центр г.Санкт-Петербурга Управление Здравоохранения Администрации Пермской Области Управление Здравоохранения Администрации...»

«Хорошко Максим Болеславович РАЗРАБОТКА И МОДИФИКАЦИЯ МОДЕЛЕЙ И АЛГОРИТМОВ ПОИСКА ДАННЫХ В INTERNET/INTRANET СРЕДЕ ДЛЯ УЛУЧШЕНИЯ КАЧЕСТВА ПОИСКА Специальность 05.13. 17 – Теоретические основы информатики АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Новочеркасск – 2013 2 Работа выполнена на кафедре Информационные и измерительные системы и технологии ФГБОУ ВПО ЮРГПУ(НПИ) им М.И. Платова. Научный руководитель кандидат технических наук, доцент...»

«Министерство сельского хозяйства Российской Федерации С-27 Светлов Н.М. Практикум по теории систем и системному анализу ФГОУ ВПО РГАУ–МСХА имени К.А. Тимирязева для студентов бакалавриата по направлениям Прикладная информатика в Кафедра экономической кибернетики экономике и Математические методы в экономике / Издательство ФГОУ ВПО РГАУ–МСХА имени К.А. Тимирязева. М., 2009. – 75 c. Рецензенты: профессор Е.В. Худякова (МГАУ имени В.П. Горячкина); профессор А.А. Землянский (РГАУ-МСХА имени К.А....»






 
© 2014 www.kniga.seluk.ru - «Бесплатная электронная библиотека - Книги, пособия, учебники, издания, публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.