WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |   ...   | 24 |

Поясним идею алгоритма на примере двумерной задачи (1) при отсутствии функциональных ограничений (2), т.е. для прямоугольной области Q = D.

Согласно многошаговой схеме, min f (y) = min min f (y1, y2 ). (5) yQ a1 y1b1 a2 y2bВведем функцию f ( y1) = min f (y1, y2 ). (6) a2 y2 bКак следует из (5), решение исходной задачи (1) может быть получено посредством минимизации одномерной функции f ( y1), т.е.

решения одномерной подзадачи f ( y1) min, y1 [a1,b1]. (7) При этом каждое вычисление значения функции f ( y1) в точке yпредставляет собой решение новой одномерной подзадачи (y1 фиксировано) f (y1, y2 ) min, y2 [a2, b2 ] (8) * Предположим, что, решая задачу (8) для некоторого y1, мы уже * провели решения аналогичных задач для y1 и y1 таких, что y1< y1 < y1и y1– y1<, где >0 – некоторый параметр, задающий «меру близости» задач (8), соответствующих координатам y1 и y1. Предлагает* ся начинать решение задачи (8) для y1 не с самого начала, а с некоторого исходного информационного множества, которое строится на основе значений целевой функции, полученных при оптимизации одномерных функций f (y1, y2 ) и f (y1, y2 ) и рассматриваемых как * приближенные значения функции f ( y1, y2 ). Методология построения такого множества может быть различной. Для примера рассмотрим один из способов его конструирования.

В схеме характеристических алгоритмов в качестве информационного множества поиска рассматривается набор:

k k = {( y1, z1),..., (yk, z )}, (9) где yi, 1 i k, являются координатами проведенных испытаний, а величины zi, 1 i k, – значениями минимизируемой функции в соответствующих точках yi. В качестве такого начального информационного множества для задачи * f (y1, y2 ) min, y2 [a2,b2 ] (10) можно выбрать множество k* k * * = {( y1*, z1*),...,( y2, z )}, (11) k в котором i * i i i y2* = ( y1 - y1)(2 - y2 ) /( y1 - y1) + y2, (12) i i 2 = min y2 - y2j, 1 jk i i i i i i zi* = (y2* - y2 )(i - z ) /( 2 - y2 ) + z (13) i i = f ( y1, 2 ), i i а величины y2, z,1 i k, и y2j,1 j k, относятся к информационным множествам (9):

k k k = {( y1, z1),..., ( y2, z )}, k k k = {( y1, z1),...,( y2, z )}, полученным при решении одномерных задач (8) для y1 и y1 соответi i ственно, причем пара ( 2, z ) k.

Введение информационного множества (11) позволяет заменить * i вычисление значений функции f ( y1, y2 ) в точках y2*, 1 i k построением приближенных величин zi*, полученных на основе линейной аппроксимации (12), (13). Построив информационное множество (11), можно продолжить решение задачи (10) характеристическим методом оптимизации. При этом метод будет вычислять функцию * f (y1, y2 ) в меньшем числе точек по сравнению с ситуацией, когда он решает задачу (10) «с чистого листа», ибо в предложенной схеме алгоритм обладает апостериорной информацией (11), т.е. считает, что в i точках y2*, 1 i k значения уже известны.

Вычислительные эксперименты, выполненные на классе сложных двухмерных функций [4], подтверждают эффективность предложенного подхода, обеспечившего существенное сокращение количества поисковых испытаний. При этом наблюдается рост эффективности при увеличении требуемой точности решения задачи. Параллельная реализация, использующая асинхронные алгоритмы из [5], подтвердила теоретические результаты относительно ускорения, достигаемого при использовании рассмотренной рекурсивной схемы редукции размерности.

Литература 1. Стронгин Р.Г. Численные методы в многоэкстремальных задачах.

Информационно- статистический подход. М.: Наука, 1978.

2. Strongin R.G., Sergeyev Ya.D. Global optimization with non-convex constraints: Sequential and parallel algorithms, Kluwer Academic Publishers, Dordrecht, Netherlands, 2000.

3. Strongin R.G., Sergeyev Ya.D., Grishagin V.A. Parallel Characteristical Algorithms for Solving Problems of Global Optimization // Journal of Global Optimization,10, 1997. P. 185–206.

4. Гришагин В.А. Операционные характеристики некоторых алгоритмов глобального поиска. В сб.: Проблемы статистической оптимизации. Зинатне, Рига, 1978. C. 198–206.

5. Sergeyev Ya.D., Grishagin V.A. Parallel asynchronous global search and the nested optimization scheme, Journal of Computational Analysis & Applications, 3(2), 2001. P.123–145.

СПЕЦКУРС «ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ:

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

Технология создания сложных компьютерных моделей требует, чтобы эксперт в данной проблемной области ставил перед программистами задачу реализации их в виде программ для ЭВМ. С одной стороны, требуются специалисты, умеющие так сформулировать задачу в своей области деятельности, чтобы она, в принципе, допускала эффективную реализацию на современных высокопроизводительных ЭВМ.

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



Современный выпускник вуза с квалификацией «Учитель информатики» должен иметь достаточно четкие знания о параллельных вычислительных системах. В рамках подготовки бакалавров образования элементы этих знаний могут быть представлены в рамках дисциплины «Компьютерное моделирование», а при получении специальности «Учитель информатики» и обучении в магистратуре – в виде различных спецкурсов.

Спецкурсы, связанные с параллельными вычислениями, читаются в Пермском государственном педагогическом университете с года. Слушателями их становятся студенты последних курсов педагогического университета, проходящие обучение с основным профилем «информатика». Знакомство с основами программирования и компьютерного моделирования параллельных вычислительных систем осуществляется в рамках двух спецкурсов для студентов факультета информатики и экономики. Для студентов, обучающихся по специальности «Учитель информатики», автором разработан курс «Параллельные вычислительные системы». Студентам, получающим ученую степень магистра и квалификацию «Учитель информатики, преподаватель высшей школы», адресован разработанный автором курс «Программирование для параллельных вычислительных систем». Объем последнего из них в два раза больше, и содержание первого практически полностью включено в него. Общий материал, используемый при проведении занятий в рамках обоих спецкурсов, представлен в разработанном автором учебном пособии [1].

Основные цели и задачи спецкурса Спецкурс нацелен на решение следующих проблем:

• подготовка учителя информатики, готового знакомить учеников специализированных школ с основами параллельных технологий в рамках профильных курсов по информатике;

• углубление образования в области информатики;

• развитие практических навыков в компьютерном моделировании, информационной культуры.

Курс включает в себя как лекционную часть, так и лабораторную поддержку.

В лекционной части излагаются основные теоретические понятия и примеры ПВС, излагаются типичные подходы при программировании для таких систем.

Чрезвычайно важную роль в курсе играют лабораторные работы.

При их выполнении предусматривается следующие режимы (один из них или сочетание по выбору преподавателя): выполнение расчетов «вручную» с заполнением всех необходимых таблиц для промежуточных результатов; проведение расчетов в среде, имитирующей ПВС.

При выполнении лабораторных работ должен предусматриваться следующий режим: проведение расчетов в среде, имитирующей ПВС.

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

Иметь доступ к нескольким типам параллельных компьютеров – недешевое удовольствие, а использовать программы, моделирующие ПВС, на персональных компьютерах могут позволить себе все. Можно рекомендовать, например, бесплатно распространяемую среду MultiPascal [2].

Методологии программирования обычно иллюстрируются на сравнительно несложных задачах, например, требующих реализации отдельных алгоритмов из области линейной алгебры, вычисления определенных интегралов и т.д.[3] Все это можно сделать, используя компьютерное моделирование в Multi-Pascal. Так как разработка параллельных программ практического уровня сложности представляет собой многоэтапный технологический процесс, то, к сожалению, она не может быть продемонстрирована во всей полноте на таких задачах.

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

Содержание лекций Тема 1 – Введение в ПВС. Представляется важным в рамках данной темы дать ответы на следующие вопросы: Что такое суперЭВМ Зачем нужны суперкомпьютеры Чем определяются перспективы развития суперЭВМ Что делается в России по развитию суперкомпьютерных технологий Как устроены современные высокопроизводительные ЭВМ Как классифицируются компьютерные архитектуры Каковы основные концепции архитектуры высокопроизводительных вычислительных систем Что такое конвейер Какие процессоры называют суперскалярными Какие процессоры называют векторными Чем различаются векторные компьютеры между собой Какая оперативная память используется в современных ЭВМ Что такое разделяемая память Что такое распределенная память Как связаны между собой элементы параллельных вычислительных систем Что такое кластеры рабочих станций Как оценивается производительность вычислительных систем Тема 2 – Основные парадигмы параллельного программирования.

В рамках данной темы освещаются следующие вопросы: Каковы основные подходы к распараллеливанию вычислений Как реализуется параллелизм данных Какой набор операций является базовым Какие способы векторизации и распараллеливания программ применяются, чтобы оптимизировать трудовые затраты На что влияет применение разных языков программирования В чем различие и сходство между распараллеливанием и векторизацией программ Как реализуется параллелизм задач Какие виды операционных систем используются на параллельных вычислительных системах На каких принципах построены распределенные ОС Тема 3 – Программирование систем с разделяемой памятью. В рамках данной темы дают ответы на следующие вопросы: Какие операционные системы применяют на мультипроцессорных ЭВМ Что понимается под процессом Как организуется взаимодействие процессов Как планирование процессоров влияет на производительность мультипроцессорной системы Как в среде Multi-Pascal моделируются многопроцессорные компьютеры с разделяемой памятью Как в MultiPascal реализуется блокирующее порождение процессов в системах с разделяемой памятью Как в Multi-Pascal реализуется неблокирующее порождение процессов в системах с разделяемой памятью Как в Multi-Pascal решается проблема взаимодействия процессов в системах с разделяемой памятью Тема 4 – Программирование систем с распределенной памятью.





Отбор материала для данной темы, в силу своей сложности и ограниченности аудиторного времени на нее, вызывал наибольшие трудности. В текущем варианте спецкурса пришлось остановиться на рассмотрении следующих вопросов: В чем преимущества и недостатки распределенных систем по сравнению с централизованными ЭВМ Как в среде Multi-Pascal моделируются многопроцессорные компьютеры с распределенной памятью Как в Multi-Pascal задаются целевые платформы, относящиеся к системам с распределенной памятью Что такое коммуникационные порты Multi-Pascal Чем может быть полезно назначение процессов процессорам и как это сделать в Multi-Pascal Лабораторный практикум Каждая из лабораторных работ практикума представляет собой микроисследование. Разработанные задания лабораторных работ по моделированию ПВС предусматривают работу в бесплатно распространяемой среде Multi-Pascal. Эта среда позволяет, используя обычный персональный компьютер, имитировать вычисления на ПВС разных архитектур.

Как известно, простейшая модель, описывающая ускорение (коэффициент эффективности распараллеливания) S, которое теоретически достижимо на компьютере из N процессоров, может быть получена из закона Амдала:

S, f + (1- f ) N где f – доля участков в программе, которые не могут быть распараллелены. Крайние случаи в значениях f соответствуют полностью параллельным (f = 0) и полностью последовательным (f = 1) программам.

Используя профилировщик (или отладчик), можно оценить время выполнения на однопроцессорной машине последовательного участка программного кода (t) и всей программы (T). Тогда f = t/T и Smax =.

t T + (1 - t T ) N Реальная выгода от увеличения числа процессоров всегда меньше:

• во всех параллельных системах – из-за накладных расходов на порождение параллельных потоков;

• в системах с разделяемой памятью – в основном из-за ожиданий процессоров возможности получения доступа к памяти;

• в системах с распределенной памятью – в основном из-за задержек межпроцессорных коммуникаций.

При анализе результатов необходимо сравнивать результаты компьютерного моделирования в среде Multi-Pascal с предсказаниями такой простой математической модели. Где возможно, подбирать более реалистичную полуэмпирическую модель, включающую дополнительно 1 или 2 подгоночных параметров. Ввод параметров должен иметь достаточно правдоподобное обоснование.

Для ускорения проведения расчетов удобно использовать переназначение стандартных ввода-вывода.

Варианты заданий формируются требованием: использовать разные программы типовых алгоритмов (вычисления числа, перемножения матриц, метода Якоби и т.п.) и/или разные входные параметры (число расчетных точек, размер матриц и т.д.). Число вариантов – в зависимости от имеющихся в наличии готовых программ.

Лабораторная работа «Основы моделирования ПВС в среде MultiPascal» – это знакомство со средой Multi-Pascal.

Лабораторная работа «Моделирование ПВС с разделяемой памятью» включает два задания на моделирование вычислений на многопроцессорных компьютерах. Первое задание – это имитация монопольного доступа, второе – имитация коллективного доступа.

Лабораторная работа «Моделирование ПВС с распределенной памятью» в два раза больше предыдущей. Студентам предлагается четыре задания. Задание 1 – моделирование вычислений на многопроцессорных компьютерах монопольного доступа. Задание 2 – моделирование вычислений на кластерах монопольного доступа. Задание 3 – моделирование вычислений на многопроцессорных компьютерах заданной топологии. Задание 4 – моделирование вычислений на компьютерных кластерах заданной топологии.

Заключение Представленный в данной работе спецкурс помогает решить проблему подготовки учителя информатики, готового знакомить учеников специализированных школ с основами параллельных технологий в рамках профильных курсов по информатике. Это представляется важным, учитывая принципиальные отличия концепций оптимального программирования для параллельных вычислительных систем от популярных концепций для персональных ЭВМ. Данный спецкурс и разработанные к нему учебно-методические материалы прошли успешную апробацию в Пермском государственном педагогическом университете. Часть этих материалов апробируется в настоящее время в рамках спецкурсов по параллельным вычислениям, читаемых в Пермском государственном университете. Предварительный анализ нашего опыта показывает, что разработанный спецкурс полезен при подготовке не только учителей информатики, но бакалавров прикладной математики и информатики.

Разработка данного спецкурса была поддержана грантом Минобразования РФ в рамках проекта «Разработка учебно-программнометодического комплекса “Компьютерное математическое моделирование” для подготовки студентов педагогических вузов к профессиональной деятельности».

Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |   ...   | 24 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

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