Высокопроизводительные парал. вычисления на кластерных системах. Воеводин (2005) (1186026), страница 42
Текст из файла (страница 42)
Полученное ПО управления кластером будет использовано для эффективного решения задач управления ВУЗом[5].Литература1. Гергель, В.П. Основы параллельных вычислений для многопроцессорных вычислительных систем. Учебное пособие / В. П. Гергель,Р. Г. Стронгин – Нижний Новгород: Изд-во ННГУ, 2003. – 184с.2. Антонов, А.В. Эффективная организация параллельных распределенных вычислений на основе кластерной технологии. Диссертация на соискание ученой степени кандидата технических наук. Пенза, 2005. – 172 с.3.
Othman, O., O'Ryan, C., Schmid,t D.C. Strategies for CORBA middleware-based load balancing // IEEE DS Online, 2001. V. 2, № 3.3. Князьков В.С., Потапов А.А. Методика оценки трудоемкости реализации матричных мультипроцессорных систем. – Пенза, Изд-во ПГУ, Сб.тез. АПНО–2003. Т.
2. 2003. – С. 400–402.4. Потапов, А.А., Попов, К.В. Корпоративные информационные системы в информационной образовательной среде. Ж. «Педагогическая информатика» №3.ИСПОЛЬЗОВАНИЕ ЧИСЕЛ РАСШИРЕННОЙ ТОЧНОСТИ ВРЕАЛИЗАЦИИ ИНДЕКСНОГО МЕТОДА ПОИСКА ГЛОБАЛЬНО-ОПТИМАЛЬНЫХ РЕШЕНИЙА.В. Сысоев, С.В. СидоровНижегородский государственный университет им. Н.И. ЛобачевскогоПроцессы принятия решений играют важную роль во многих сферах производственной деятельности человека. Одной из типичных моделей таких процессов является модель в виде задачи оптимизации.
Вобщем случае эта модель представляет собой набор функционалов,определенных на пространстве параметров, с помощью которых описывается ситуация принятия решения. При этом целью часто являетсяглобальный оптимум одного – в однокритериальном случае – или нескольких – в многокритериальном – функционалов.
Нередко такженайденное решение должно удовлетворять некоторым заданным функциональным условиям, которые понимаются как ограничения. Типичным способом решения указанных задач являются различные численные методы, основанные на итерационных процедурах вычислениявходящих в задачу функционалов в точках области поиска, выбираемых согласно некоторым правилам.208Простейший подобный метод состоит в вычислении функционаловзадачи во всех точках некоторой чаще всего регулярной сетки в области изменения параметров. Однако с ростом размерности, то есть с увеличением числа учитываемых параметров, описывающих ситуациюпринятия решения, использование «полного перебора» становится бесперспективным в силу экспоненциального роста числа точек расчета.Более эффективные методы поиска обычно основываются на некоторой дополнительной информации о характере входящих в задачуфункционалов (непрерывность, дифференцируемость, липшицевость,…).
При этом часто имеющая место существенная вычислительнаятрудоемкость функционалов требует для нахождения оптимума приреалистичных временных затратах использования параллельных вычислений в программных реализациях этих методов.Одним из таких эффективных методов поиска глобального оптимума в многомерных многоэкстремальных задачах является индексныйметод [1], важное достоинство которого состоит в возможности создания эффективной параллельной модификации [2]. Вместе с тем прииспользовании аппаратно поддерживаемых вещественных типов данных реализация индексного метода [3] сталкивается с некоторыми существенными ограничениями.
В данной работе обсуждается характерэтих ограничений, а также пути их преодоления в виде использованиячисел расширенной точности.Необходимость использования чисел расширенной точностиИндексный метод позволяет находить глобально-оптимальное решение в многомерных задачах оптимизации с ограничениями.
Приэтом одним из основных идейных моментов метода является использование редукции размерности на основе кривых Пеано, в результатечего итерации метода фактически выполняются на отрезке [0, 1] вещественной оси, а для вычисления значений функционалов осуществляется построение образа точки. Проблема состоит в том, что для достижения высокой точности решения по каждой координате в исходномN-мерном пространстве на отрезке [0, 1] требуется точность в 2N разбольшая. Таким образом, если за m обозначить точность построенияразвертки (то есть погрешность найденного решения по каждой координате будет составлять 1/2m+1), то на отрезке [0, 1] потребуется точность в 2Nm.При использовании для хранения точки испытания типа double,мантисса которого имеет 52 бита, максимально возможная точность209ограничена условием Nm < 52.
Учитывая, что минимальным значениемm, дающим разумную точность в исходном N-мерном пространствеявляется 10, применение прямой реализации индексного метода ведет кограничению на размерность задачи порядка 5.Выходом из указанной ситуации является использование чиселрасширенной (произвольной) точности для представления точек наотрезке [0, 1].Проблемы использования чисел расширенной точностиВозможности работы с числами расширенной точности реализованы во многих библиотеках. В частности в работе были проанализированы такие библиотеки как GMP, MAPM, WinNTL. Общим недостатком всех подобных библиотек является уменьшение на два-три порядка скорости выполнения даже простейших арифметических операций всравнении с типом double, что было подтверждено численнымиэкспериментами.
Прямое использование одной из указанныхбиблиотек в реализации индексного метода привело к замедлениюпроцесса поиска глобального оптимума в 500 раз. Следующиместественным шагом стало максимально возможное уменьшениеиспользования чисел расширенной точности в операциях метода.Использование чисел типа double для вычислениядробных степеней от расстояний между точкамиОдной из широко используемых и весьма трудоемких операций виндексном методе является операция возведения в дробную степень, аименно в степень 1/N возводится расстояние между двумя точками изотрезка [0, 1].
Как будет показано ниже, данная операция может бытьвыполнена с использованием типа double без существенной потериточности.Пусть Ext – тип данных с расширенной точностью.Рассмотрим пример,Ext m = 0.999999999999999999999; // любое ”большое” число цифрdouble d, res1, res2;res1 = m.pow(1.0 / 10.0).toDouble();res2 = pow(m.toDouble(), 1.0 / 10.0);Зададимся вопросом, насколько значение res1 отличается от res2?Рассмотрим числа, целая часть которых не превышает 9, доказательство обобщается и на противный случай, но оно менее наглядно.Представим рациональное число x в виде:210∞x = ∑ ai ⋅ 10 −i .i =0После преобразования x1 = x.toDouble получим:14x1 = ∑ ai ⋅ 10 −i .i =0Возведя x и x1 в степень (1/N) и взяв логарифм от отношения степеней, получим:14∞⎛⎞1log(ρ1 ρ 2 ) = ⋅ log ⎜⎜1 + ∑ ai ⋅ 10 −i ∑ ai ⋅ 10 −i ⎟⎟ ,Ni =0⎝ i =15⎠где1N1N⎛ ∞⎞⎛ 14⎞ρ1 = ( x1 )1 N = ⎜⎜ ∑ ai ⋅ 10 −i ⎟⎟ , ρ 2 = ( x2 )1 N = ⎜⎜ ∑ ai ⋅ 10 −i ⎟⎟ .⎝ i =0⎠⎝ i =0⎠Далее, нетрудно показать, что1114Log (ρ1 ρ 2 ) = Log (1 + 0,00000000000001 1,0) = ⋅ Log (1 + (1 10) ).NNВзяв от обеих частей экспоненту и разложив правую часть в рядТейлора, получим, что максимальная разница между ρ1 и ρ2 не превышает 10−14.
Таким образом, вычисление дробных степеней в типе double не ухудшает качество вычисления расстояний.РезультатыРассуждения, показанные в предыдущем разделе, позволяют всеоперации возведения в дробную степень в реализации индексного метода выполнять в типе double, что обеспечивает существенный выигрыш в скорости.
С учетом указанной замены вычислений удалось добиться замедления работы индексного метода с использованием чиселрасширенной точности в 10 раз по отношению к реализации, использующей только тип double. При этом ограничение Nm < 52 превращается в 2Nm < 10308 (10−308 – минимальное число, представимое в типеdouble), что дает примерную оценку Nm < 1000.Выполненная реализация была протестирована на модельных задачах, в частности функции Растригина с размерностью N от 10 до 12 иточностью построения развертки m от 10 до 15.Работа была поддержана грантом Нидерландской Организации211Научных исследований (NWO) № 047.016.014 и грантом РоссийскогоФонда Фундаментальных Исследований № 04-01-89002-HBO_a.Литература1.
Strongin R.G., Sergeev Ya.D. (2000). Global optimization with nonconvex constraints: Sequential and parallel algorithms. Kluwer Academic Publisher, Dordrecht.2. Гергель В.П., Стронгин Р.Г. Параллельные вычисления в задачахвыбора глобально-оптимальных решений для многопроцессорных кластерных систем // Современные методы математического моделирования /Сб. лекций Всероссий. молодежной школы международ. конф. «Математическое моделирование». Самара.
2001. С. 46–55.3. Sysoyev A.V. (2004). Program system of parallel computations for solving the tasks of global-optimum choice // VI International Congress on Mathematical Modeling / Book of abstracts. P. 62.СРАВНЕНИЕ ТРЕХ ПОДХОДОВ К ПОСТРОЕНИЮПАРАЛЛЕЛЬНЫХ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ НАПРИМЕРЕ НЕКОТОРЫХ ЗАДАЧ ФУНКЦИОНАЛЬНОЙОПТИМИЗАЦИИ И ГЕНЕТИЧЕСКОГОПРОГРАММИРОВАНИЯС.В. ТимченкоТомский государственный университетсистем управления и радиоэлектроникиВ последние годы при решении различных задач оптимизации ипоиска стали широко применяться различные адаптивные процедуры,среди которых особую популярность завоевали эволюционные и, в томчисле, генетические алгоритмы (ГА) и эволюционные стратегии (ЭС).В той или иной мере, они основаны на эволюционных процессах вбиологических популяциях, развивающихся поколение за поколением,подчиняясь законам естественного отбора и принципу «выживаетсильнейший» (точнее, наиболее приспособленный).Чрезвычайно важным свойством как ГА, так и ЭС является их естественный внутренний параллелизм.
При этом, по сравнению с градиентными методами, различие во времени расчета целевой функции приразличных значениях ее параметров не оказывает влияния на эффективность распараллеливания (эти времена могут отличаться на порядки– например, если можно определить, что точка в пространстве поиска212не отвечает наложенным ограничениям, не вычисляя целевую функцию или вычисляя ее только частично).Основная идея большинства параллельных алгоритмов заключается в том, что бы разбить задачу на (сравнительно) небольшие подзадачи и решать их совместно, используя многопроцессорную вычислительную систему. Стратегия «разделяй и властвуй» может быть реализована большим количеством способов. Одни из них лучше подходятдля систем с массовым параллелизмом (MPP), другие для небольшихпараллельных систем.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
