Высокопроизводительные парал. вычисления на кластерных системах. Воеводин (2005) (1186026), страница 7
Текст из файла (страница 7)
Можно выделять из всех преобразований системы целенаправленных эквивалентных преобразований кнеобходимым формам.Например, рассмотрим аксиому (A → B)•C = A → B•C [7]. Сложность правой части равна Cп = max{C(A), C(B)} + C(C), сложностьлевой части Cл = max{C(A), C(B) + C(C)}. Очевидно Cп > Cл. Такимобразом, одним из возможных вариантов целенаправленных преобразований может быть преобразование к форме с минимальным временем параллельного вычисления.ЗаключениеВ настоящее время созданы основные блоки интегрированной программной среды, которая позволит существенно повысить эффективность и качество функциональных параллельных программ на этапе ихпроектирования. Разрабатывается метод графического анализа проектирования функциональных программ.Литература1.
Бажанов С.Е., Воронцов М.М., Кутепов В.П., Шестаков Д.А.Структурный анализ и планирование процессов параллельного выполнения функциональных программ. Известия РАН. Теория и системы управления, 2005, №6. С. 131–146.2. Бажанов С.Е., Кутепов В.П., Шестаков Д.А. Разработка и реализация системы функционального параллельного программирования на вы30числительных системах // Докл. междунар. научн. конф. «Суперкомпьютерные системы и их применение» SSA’2004. Минск: ОИПИ НАН Беларуси, 2004.3.
Бажанов С.Е., Кутепов В.П., Шестаков Д.А. Язык функционального параллельного программирования и его реализация на кластерных системах. Программирование, 2005, №5. С. 18–51.4. Барский А.Б. Планирование параллельных вычислительных процессов. М.: Машиностроение, 1980.5. Головкин Б.А. Расчет характеристик и планирование параллельныхвычислительных процессов.
М.: Радио и связь, 1983.6. Кутепов В.П. Организация параллельных вычислений на системах.М.: МЭИ, 1988.7. Кутепов В.П. Языки параллельных алгоритмов. Учебное пособиепо курсу «Стурктуры вычислительных машин и систем». М.: МЭИ, 1978.8. Кутепов В.П., Бажанов С.Е. Функциональное параллельное программирование: язык, его реализация и инструментальная среда разработки программ. // Матер. IV Международ. научно-практического семинара иВсероссийской молодежной школы. Самара. 2004.9. Кутепов В.П., Шестаков Д.А.
Анализ структурной сложностифункциональных программ и его применение для планирования их параллельного выполнения на вычислительных системах. Высокопроизводительные параллельные вычисления на кластерных системах // Матер. IVМеждунар. научно-практического семинара и Всероссийской молодежнойшколы.
Самара. 2004.ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ГЛОБАЛЬНОЙОПТИМИЗАЦИИ С АДАПТИВНЫМ ПОРЯДКОМПРОВЕРКИ ОГРАНИЧЕНИЙК.А. БаркаловНижегородский государственный университет им. Н.И ЛобачевскогоДанная работа продолжает развитие нового подхода к минимизации многоэкстремальных функций при невыпуклых ограничениях (см.[1]−[6]), получившего название индексного метода глобальной оптимизации.Рассмотрим многомерную задачу условной глобальной оптимизации видаϕ∗ = ϕ(y∗) = min{ϕ(y): y∈D, gj (y) ≤ 0, 1 ≤ j ≤ m},31D = {y ∈ RN: −2−1 ≤ ii ≤ 2−1, 1 ≤ I ≤ N}.Данная задача рассматривается в предположении, что целевая функцияϕ(y) и левые части ограничений gj, 1 ≤ j ≤ m, являются липшицевымифункциями с соответствующими константами Lj, 1 ≤ j ≤ m + 1.Используя кривые типа развертки Пеано y(x), однозначно отображающие отрезок [0, 1] на N-мерный гиперкуб DD = {y ∈ RN: −2−1 ≤ yi ≤ 2−1, 1 ≤ I ≤ N} = {y(x): 0 ≤ x ≤ 1},исходную задачу можно редуцировать к следующей одномерной задаче:ϕ(y(x∗)) = min{ϕ(y(x)): x ∈ [0, 1], gj(y(x)) ≤ 0, 1 ≤ j ≤ m}.В работе [3] предложена идея одновременного использованиямножества кривых такого типа, что сводит многомерную задачу к нескольким связанным одномерным задачам.
Каждая из одномерных задач решается на отдельном процессоре, причем процессоры обмениваются результатами итераций, что соответствует распараллеливаниюрешения исходной задачи. Достоинство этой схемы состоит в том, чтонабор одномерных задач, порождаемых одновременным применениеммножества разверток, более полно передает информацию о метрических свойствах исходной многомерной задачи.В соответствии с правилами индексного метода каждая итерация,называемая испытанием в соответствующей точке области поиска,включает последовательную проверку выполнимости ограничений задачи в этой точке. При этом обнаружение первого нарушенного ограничения прерывает испытание и инициирует переход к точке следующей итерации. В силу того, что левые части ограничений gj, 1 ≤ j ≤ m,являются липшицевыми функциями, ограничение, нарушенное в некоторой точке области поиска, не будет выполняться и в некоторой окрестности этой точки.
В таком случае (для сокращения числа проверок)может оказаться полезным начинать испытания в точках этой окрестности с анализа выполнимости указанного ограничения. В свете сказанного представляется целесообразным построить алгоритм глобальной оптимизации, допускающий изменение порядка проверки ограничений с учетом информации, получаемой в ходе поиска решения. Вработе [5] был предложен последовательный алгоритм с переменнымпорядком проверки ограничений.Новое предложение, применительно к многомерным задачам, состоит в обобщении решающих правил последовательного алгоритма из[5] на случай многих процессоров и заключается в том, что для каждой32точки итерации x i адаптивно определяется свой порядок проверкиограниченийH(xi) = {ji1, …, jim, ji,m+1}, 0 ≤ I ≤ k,как перестановка номеров из базовой нумерации ограниченийH = {1, 2, …, m, m + 1}.Это позволяет начинать проверку с ограничения, для которого более вероятно нарушение в выбранной точке очередной итерации.
Темсамым форсируется завершение итерации при меньших вычислительных затратах. При этом возникает потребность как в новых правилахсопоставления индексов точкам итераций (эти индексы определяютиспользование выражений для определения интервала, в котором будетпроводиться следующая итерация), так и в специальной процедуре,формирующей порядок проверки ограничений в точке очередного испытания.Для предложенного параллельного алгоритма с адаптивным порядком проверки ограничений проведено теоретическое исследованиеусловий сходимости.Работа выполнена при финансовой поддержке РФФИ (код проекта04-01-00455).Литература1.
Стронгин Р.Г. Численные методы в многоэкстремальных задачах.М.: Наука, 1978.2. Стронгин Р.Г. Поиск глобального оптимума. М.: Знание, 1990.3. Стронгин Р.Г. Параллельная многоэкстремальная оптимизация сиспользованием множества разверток // Ж. вычисл. матем. и матем. физ.1991. Т.31. №8. С. 1173–1185.4. Стронгин Р.Г., Баркалов К.А. О сходимости индексного алгоритма взадачах условной оптимизации с ε-резервированными решениями // Математические вопросы кибернетики.
М.: Наука, 1999. С. 273–288.5. Баркалов К.А., Стронгин Р.Г. Метод глобальной оптимизации садаптивным порядком проверки ограничений // Ж. вычисл. матем. и матем.физ. 2002. Т.42. №9. С. 1338–1350.6. Strongin R.G., Sergeyev Ya.D. Global optimization with non-convexconstraints. Sequential and parallel algorithms. Kluwer Academic Publishers,Dordrecht, 2000.33ABOUT MARS METHOD AND PARALLEL INDEX METHODINTEGRATIONK.A. BarkalovUniversity of Nizhny Novgorod, Nizhny Novgorod, RussiaV.L. MarkineDelft University of Technology, Delft, The NetherlandsIntroductionIn this paper an integration of the Multipoint Approximation based onResponse Surface fitting (MARS) method (developed and used in DelftUniversity of Technology) and parallel index method (PIM) of global optimization (developed in Nizhny Novgorod State University) is discussed.
Anew point is that PIM is used to solve the approximation problems, whichare generated by MARS method.MARS methodConsider the optimization problem in general form:F∗ = min{F0(y): y ∈ D, Fj(y) ≤ 1, j = 1, …, M},D = {y ∈ RN: Ai ≤ yi ≤ Bi, I = 1, …, N},(1)where F0 is the objective function; Fj(y), j = 1, …, M are the constraints; y= [y1, …, yN]T is the vector of design variables; Ai and Bi are the side limits,which define lower and upper bounds of the i-th design variable.Components of the vector y represent various parameters of a structure,such as geometry, material, stiffness and damping properties, which can bevaried to improve the design performance.
Depending on the problem underconsideration the objective and constraint functions can describe variousstructural and dynamic response quantities such as weight, reaction forces,stresses, natural frequencies, displacements, velocities, accelerations, etc.Cost, maintenance and safety requirements can be used in the formulation ofthe optimization problem as well. The objective function provides a basisfor improvement of the design whereas the constraints impose some limitations on behaviour characteristics of a structure.The optimization problem (1) can be solved using a conventionalmethod of mathematical programming. However, for systems with manydegrees of freedom the finite element analysis can be time consuming.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
