Высокопроизводительные парал. вычисления на кластерных системах. Воеводин (2005) (1186026), страница 17
Текст из файла (страница 17)
После этого номер итерации n увеличивается на единицу,количество испытаний k(n + 1) становится равным k(n) + p, пересчитывается оценка (10) и происходит переход к шагу 1.Предложенный метод относится к классу параллельных характеристических алгоритмов [5], и его сходимость к глобальному оптимуму обеспечивается условиями сходимости его последовательного прототипа [1, 2].Заметим, что в данной работе рассматривается синхронная схемаорганизации вычислений индексного метода, когда процессор, завершивший свое испытание, ожидает окончания работы остальных процессоров, участвующих в параллельной итерации метода.
Но в индексной схеме время работы каждого процессора неизбежно будет различным, даже если считать, что времена вычисления значений каждойфункции gj(y), 1 ≤ j ≤ m + 1 не отличаются ни между собой, ни от точки к точке, потому что процессор завершает испытания сразу, кактолько обнаруживает первое нарушенное ограничение, и остальныефункции задачи не вычисляет. Поэтому более эффективной представляется асинхронная реализация решающего правила индексного мето81да, когда точки испытаний формируются динамически по запросу освободившегося процессора, как это, например, реализовано в методах[6–8].Предположим теперь, что в схеме редукции (13) для решения одномерных задач (15) используется параллельный индексный метод спостоянным числом процессоров πi на всех итерациях метода, решающего одномерные задачи, связанные с координатой yi.Тогда для решения задачи (9), а, как следствие, и задачи (1)–(3)можно использовать вплоть доNΠ = ∏ πi(23)i =1параллельно работающих процессоров.
При этом многошаговая схемабудет генерировать до Π/πN одномерных подзадач оптимизации, решаемых одновременно.Если мы комбинируем многошаговую схему с одномерным параллельным алгоритмом, в котором условие остановки отлично от выполнения фиксированного одинакового числа итераций, тогда временавыполнения испытаний в параллельной итерации на i-м уровне одномерной оптимизации (1 ≤ i ≤ N – 1) будут неизбежно различны. Напомним, что вычисление целевой функции на всех уровнях, кроме последнего, состоит в решении новой оптимизационной подзадачи. Данный аспект также служит основанием для конструирования и исследования асинхронных алгоритмов индексной многомерной оптимизации.Работа выполнена при поддержке РФФИ (грант № 04-01-00455).Литература1.
Strongin R.G., Sergeyev Ya.D. Global optimization with non-convexconstraints: Sequential and parallel algorithms, Kluwer Academic Publishers,Dordrecht, Netherlands. 2000.2. Strongin R.G., Markin D.L. Minimization of multiextremal functionswith nonconvex constraints. Cybernetics 22, 1986. P. 486–493.3. Carr C.R., Howe C.W. Quantitative Decision Procedures in Managementand Economics. Deterministic Theory and Applications.
McGraw Hill, NewYork, 1964.4. Стронгин Р.Г. Численные методы в многоэкстремальных задачах.Информационно- статистический подход. М.: Наука, 1978.5. Strongin R.G., Sergeyev Ya.D., Grishagin V.A. Parallel CharacteristicalAlgorithms for Solving Problems of Global Optimization // Journal of GlobalOptimization, 10, 1997. P. 185–206.826. Sergeyev Ya.D., Grishagin V.A. Parallel asynchronous global search andthe nested optimization scheme, Journal of Computational Analysis & Applications, 3(2), 2001.
P. 123–145.7. Гришагин В.А., Филатов А.А. Параллельные рекурсивные алгоритмы многоэкстремальной оптимизации // Матер. II Международ. научнопрактического семинара «Высокопроизводительные параллельные вычисления на кластерных системах» / Под ред. проф. Р.Г. Стронгина. НижнийНовгород: Изд-во Нижегородского госуниверситета, 2002. С. 88–90.8. Гришагин В.А., Сергеев Я.Д. Эффективность распараллеливания характеристических алгоритмов глобальной оптимизации в многошаговойсхеме редукции размерности. // Матер.
IV Международ. научнопрактического семинара и Всероссийской молодежной школы «Высокопроизводительные параллельные вычисления на кластерных системах» /Под ред. члена-корр. РАН В.А.Сойфера. Самара: Изд-во Самарского научного центра РАН, 2004. С. 70–74.СВОБОДНЫЙ ПАРАЛЛЕЛЬНЫЙ ОТЛАДЧИКНА ОСНОВЕ GNU DDDА.В. Гришин, А.Л. КурылевНижегородский государственный университет им.
Н.И. ЛобачевскогоА.В. Коновалов, А.Г. ПегушинЗАО «Интел А/О», Нижний НовгородПод отладкой в узком смысле обычно понимают деятельность, начинающуюся с обнаружения факта ошибки, и заканчивающуюся непосредственным моментом ее исправления. Общепринято, что отладкапараллельных программ является значительно более ресурсоемкимпроцессом, чем отладка последовательных. Выразительным примеромздесь может служить работа [4], наглядно иллюстрирующая тот факт,что даже в очень небольших программных структурах ошибки могутскрываться десятилетиями.
Попытаемся коротко проанализироватьпричины такой ситуации, обращая внимание на деятельность программиста в процессе отладки.Отладка начинается с изучения симптомов ошибки (например, неправильный ответ, аварийное завершение программы и др.), но в нетривиальных случаях ошибка находится не там, где проявляется симптом.
Это значит, что для успешной отладки необходимо (неоднократно) отвечать на вопрос «А как же мы сюда попали?». Удивительно, но83современные отладчики не предоставляют инструментов, позволяющих упростить эту важнейшую операцию.На выручку приходят средства журналирования, подтверждая утверждение, что лучшее средство отладки – оператор печати. В параллельной отладке перед программистом открывается целое новое измерение: необходимо осознать, чем «сейчас» заняты другие параллельные процессы и как, в свою очередь, они пришли в это состояние. Повидимому, векторные часы адекватно моделируют интуитивное представление о «сейчас» [10], но излишне говорить, что распростран енные MPI-ориентированные продукты их не поддерживают.Инструментальные средства отладкиОсознание сообществом системных программистов трудности параллельной отладки привело к созданию ряда инструментов, ее облегчающих.
Подобного рода инструменты можно разделить на три категории:1) средства отладки, использующие особенности интерфейса MPI.MPI является достаточно высокоуровневым механизмом межпроцессного взаимодействия (по сравнению с сокетами Беркли или общей памятью), что позволяет автоматически обнаруживать целый ряд ошибок, таких, как неправильный тип данных при широковещанииMPI_Bcast или некорректная операция во время редукции MPI_Reduce.Последнее время это направление развивается весьма бурно [8], [9],[11];2) средства отладки эффективности (Jumpshot и др., см. обзор в[1]). Обычно их рассматривают только как вспомогательные средстваоптимизации, однако серьезная отладка существенно облегчается возможностью изучать общую структуру программы. Особенно в этойдеятельности оказываются полезны виды отображения, производныеот диаграмм Гантта. Еще одна область применения этих средств приотладке – анализ ситуаций, когда ошибки в программе маскируютсясредствами восстановления, присутствующими в этой программе.
Врезультате все тесты проходят, и только по аномалии производительности можно понять, что ошибка все-таки есть [7];3) традиционные последовательные отладчики, обобщенные дляпараллельной работы (Etnus TotalView, Allinea DDT, TDB проекта«Скиф»). Часто их называют параллельными отладчиками, однако всвое время отладчики на уровне исходного текста [6] были революционным явлением как раз потому, что программист видел в отладчикеименно то, на чем он программировал, а не машинные команды. В этом84смысле, не смотря на стремление к естественному представлениюSIMD программ в виде единого исходного текста и различных для разных процессов обрабатываемых данных и развитый аппарат групповыхконтрольных точек, средства описываемой группы пока не вышли науровень «вижу работу в тех терминах, в каких программировал».Осмысленное сравнение разнородных программных средств неможет проводиться без учета человеческой психологии.
Наиболее многочисленной и наиболее страдающей группой пользователей параллельных машин являются прикладные программисты (специалисты впредметных областях, использующие параллельные вычисления какеще один инструмент решения своих задач, и по возможности не желающие изучать устройство инструмента) [5]. И здесь третья категорияинструментов находится вне конкуренции: интегрированные средыпрограммирования сделали использование отладчиков прозрачным иповсеместным. Неплохи шансы и первой категории, до той поры, покаошибки ищутся автоматически. Необходимо понимать, что с расширением круга ошибок простота использования исчезнет – если гонки (ситуации асинхронности) и легко находить автоматически (по трассе,либо сравнивая прогоны), то их присутствие во многих популярныхкаркасах параллельных программ делает просто показ всех гонок бессмысленным.
Мощным средством поиска потенциальных ошибок является сравнительная отладка [2].Исходя из вышеизложенного, было предложено реализовать привычные базовые возможности параллельных отладчиков в разрабатываемом свободном диалоговом отладчике. Это позволит создать сообщество пользователей, во-первых, и разработать расширяемый программный продукт с возможностью добавления инструментов высокоуровневого анализа параллельной структуры (это позволит превратитьотладчик в полноценное средство параллельной отладки), во-вторых.Свободный диалоговый отладчикВесьма реалистичная структура диалогового параллельного отладчика изложена в [3].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
