Стронгин Р.Г (ред.) Высокопроизводительные параллельные вычисления на кластерных системах

Подождите немного. Документ загружается.

261

шаблонов (TES - template-based evolutionary synthesis) [9] на языке

программирования C, стратегии также задавались на этом языке.

Параллельная реализация генетического алгоритма оптимизации

стратегий биржевой торговли выполнена на основе распараллеливания

по данным [10] с использованием библиотеки MPI в системе НКС-160

(160 процессоров Itanium 2). Распараллеливание по данным в

решаемой задаче сводится к равномерному распределению популяции

по процессорам системы, которое минимизирует взаимодействия и

позволяет получить почти линейное ускорение (см. Табл.1, где

приведены результаты для оптимизации стратегии с EMA для акций

ГАЗПРОМа при числе процессоров N, размере популяции на каждом

процессоре Pop, времени исполнения T(сек.), полученном ускорении

Sp и доходности

N Pop T(сек.) Sp

1 16000 18700 1 5.712

2 8000 9350 2 5.932

4 4000 4680 3.996 5.712

8 2000 2340 7.991 6.904

16 1000 1166 16.038 6.879

24 667 784 23.85 6.904

32 500 583 32.075 6.879

36 444 518 36.1 6.533

40 400 467 40.043 6.904

48 333 389 48.072 6.742

Таблица 1

Используемый генетический алгоритм позволил найти значения

параметров торговых стратегий, обеспечивающие увеличение функции

суммарной доходности (на 14% - 250% для различных индикаторов,

см. Табл.2) по сравнению с известными ранее [1, 3, 6].

Тип акции \ Индикатор EMA MACD RSI ROC

ГАЗПРОМ 204% 14% 38% 12%

РАО ЕС России 167% 15.7% 151% 14%

NIKKEI 219% 38% 250% 21%

DJIA 41% 35,6% 31% 16%

Таблица 2. Увеличение суммарной доходности торговых стратегий

Заключение

Представленый подход к оптимизации торговых стратегий,

основанный на индикаторах технического анализа, эволюционных

262

вычислениях и темплейтах, был успешно применен для поиска

свободных параметров стратегий с целью максимизации функции

суммарной доходности. Параллельная реализация генетического

алгоритма оптимизации стратегий биржевой торговли позволяет

получить почти линейное ускорение и увеличить значения функции

суммарной доходности. Дальнейшее развитие данного подхода будет

направлено на эволюционный синтез [9] новых торговых алгоритмов,

правил и

стратегий с использованием комбинаций нескольких

индикаторов, поиском новых функций для анализа ценовых рядов и

исследованием новых подходов для распараллеливания.

Литература

1. Achelis S.B. Technical analysis from A to Z. Chicago: Probus.

1996.

Артемьев С.С., Якунин М. Математическое и статистическое

моделирование на фондовых рынках. - Новосибирск:

ИВМиМГ СО РАН, 2003.

LeBeau Ch., Lucas D.W. Computer analysis of the futures market,

New-York: IRWIN, 1992.

Weissman R.L. Mechanical Trading Systems, Hoboken, New

Jersey: John Wiley and Sons, Inc., 2005.

Salov V. Modeling maximum trading profits with C++ : new

trading and money management concepts, Hoboken, New Jersey:

John Wiley and Sons, Inc., 2007.

Blau W. Momentum, Direction and Divergence, Hoboken, New

Jersey: John Wiley and Sons, Inc., 2001.

Goldberg D.E. Genetic Algorithms, in Search, Optimization and

Machine Learning. Reading, MA: Addison-Wesley, 1989.

Koza J. Genetic Programming. Cambridge: The MIT Press,1992.

Monakhov O., Monakhova E. Evolving Templates for Synthesis of

Scientific Algorithms. Computational Technologies. N6, 2005,

p.3-12.

10.

Монахов О.Г., Монахова Э.А. Параллельные системы с

распределенной памятью: структуры и организация

взаимодействий. Новосибирск: Изд-во СО РАН, 2000.

263

ПРЕОБРАЗОВАНИЕ ЦИКЛОВ ВЫЧИСЛЕНИЯ

РЕКУРРЕНТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

В.В. Мялицин

Пензенский государственный университет

Введение

Значительная часть времени при выполнении программ

приходится на циклы. Поэтому наибольшее внимание при

преобразовании алгоритмов программ уделяется их оптимизации.

Простые и эффективные методы преобразования циклических

конструкций внедрены в оптимизирующие компиляторы языков

программирования высокого уровня. Для многопроцессорных

вычислительных систем используются специальные преобразователи,

выполняющие распараллеливание алгоритмов программ и, в том

числе, циклических конструкций

. Однако преобразование

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

существующими средствами малоэффективно и часто требует

специальной аппаратной поддержки.

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

конструкций

Известны различные методы преобразований циклических

конструкций с целью приведения их к виду, в котором тело нового

цикла может выполняться несколькими вычислительными

устройствами одновременно.

Широко используются метод динамического определения

параллелизма [1], метод гиперплоскостей и координатный метод [2]. В

качестве составной части этих методов используются операции, не

связанные с параллелизацией, такие как: перестановка, слияние и

распределение циклов, переупорядочивание операторов и раскрутка

[3].

Эффективным и распространённым преобразованием циклических

конструкций на одном вычислительном устройстве является раскрутка

цикла [3]. Требуемые для вычисления значений операции чтения и

записи переменных снижают общую производительность. Раскрутка

циклов заключается в дублировании тела циклической конструкции и

сокращении числа итераций, что позволяет добиться значительного

уменьшения количества операций

чтения и записи и получить

264

очевидный выигрыш сокращения времени выполнения циклической

конструкции. При использовании данного преобразования необходимо

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

заменены выражениями, вычисляющими требуемые значения при

учёте изменения значения переменной цикла. С увеличением глубины

раскрутки растёт и производительность, приближаясь в пределе к

некоторому значению. В общем случае помимо раскрученного

цикла

необходима организация дополнительного цикла, осуществляющего

вычисления для остатка итераций.

Известны методы преобразования циклов, основанные на

выявлении параллелизма по графу информационной зависимости.

Одним из таких методов является анализ динамического графа

зависимости данных [1]. Метод предполагает построение графа,

показывающего зависимости вычисления порождаемых переменных

от множества используемых переменных, где порождаемая

переменная – это элемент массива

, который появляется в левой

стороне арифметического выражения, а используемая – в правой.

Выявленное отсутствие зависимости вычислений по данным позволяет

построить схему одновременного вычисления групп переменных.

Недостатком метода является лишь выявление отсутствующих

зависимостей вычислений по данным и невозможность

преобразования последовательности вычислений для уменьшения

числа этих зависимостей.

Другие методы преобразования циклических конструкций [2], в

которых производится анализ циклов по графу информационных

зависимостей – метод гиперплоскостей и координатный метод.

Метод гиперплоскостей подразумевает возможное преобразование

циклов определённого вида, в которых имеется возможность

одновременного порождения нескольких переменных из некоторого

множества других переменных. В работе [2] приведён пример

вычислений одного из циклов такого вида, где вычисление

переменных, лежащих на одной и

той же плоскости, можно

производить одновременно, используя множество вычислительных

устройств. Автор работы [2] предложил общий подход к

преобразованию циклических конструкций данного типа (вычисления

в которых можно представить параллельными плоскостями), который

был использован при проектировании компилятора языка Fortran для

системы параллельных вычислений ILLIAC IV. Координатный метод в

отличие от метода гиперплоскостей предполагает синхронизацию

265

вычислений тела цикла (группы переменных) на множестве

вычислительных устройств, что подразумевает наличие аппаратной

поддержки синхронизации вычислений.

Недостаток метода гиперплоскостей заключается в применении

его только для циклических конструкций с простым определением

параллельных плоскостей одновременных вычислений. Недостатком

координатного метода является невозможность его применения в

системах, не имеющих аппаратной поддержки синхронизации

вычислений.

Метод преобразования циклов вычисления рекуррентных

последовательностей

Формирование рекуррентной последовательности подразумевает

вычисление элементов последовательности из некоторой совокупности

предыдущих элементов этой последовательности или из одного

элемента.

Алгоритм вычисления значений элементов последовательности

легко реализуется циклической конструкцией. Полученный алгоритм

можно распараллелить, используя раскрутку и координатный метод.

Однако эффективность данного преобразования невысока, так как

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

Автором предложен

новый метод преобразования циклов,

подразумевающий изменение алгоритма вычисления элементов

некоторой последовательности - распараллеливание алгоритма во

время компиляции прикладной программы, написанной на языке

высокого уровня или языке описания формул, таком как: язык системы

MathCAD или язык НОРМА [3]. При этом учитывается количество

вычислительных устройств многопроцессорного или многомашинного

комплекса.

Достоинством предложенного метода является то, что

преобразованные циклические конструкции могут выполняться

параллельно, то есть одновременно и независимо (без синхронизации)

на нескольких вычислительных устройствах.

Преобразование заключается в замене исходной зависимости

вычисления очередного элемента последовательности на совокупность

зависимостей таким образом, чтобы можно было вычислить К новых

значений из К предыдущих значений и чтобы подсчитанные К новых

значений использовать

для подсчёта К значений на следующей

266

итерации циклической конструкции, то есть происходит

формирование новых зависимостей.

В новом методе используется стандартное оптимизирующее

преобразование – раскрутка, что позволяет реорганизовать

циклические конструкции вычисления рекуррентных

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

выполняться одновременно и независимо (без синхронизации

вычислений) на разных вычислительных устройствах.

Технический результат, достигаемый предложенным методом,

заключается в уменьшении

количества операций, выполняемых

последовательно, и, соответственно, времени выполнения циклической

конструкции. Сокращение времени решения задач осуществляется

одновременным вычислением групп порождаемых переменных

несколькими вычислительными устройствами.

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

Преобразование циклических конструкций вычисления

рекуррентных последовательностей легко показать на примерах таких

задач, как: вычисление количества зёрен на шахматной доске и числа

Фибоначчи.

В известной сказке за оказанную услугу было попрошено столько

зерна пшеницы, сколько необходимо для заполнения шахматной доски

по правилу: «На каждой следующей клетке должно быть вдвое больше

зёрен». Количество

зёрен на очередной клетке зависит от числа зёрен

на предыдущей клетке, то есть это рекуррентная последовательность.

Алгоритм вычисления легко реализуется циклической конструкцией.

Граф информационной зависимости показывает, что вычисления

элементов можно выполнить только последовательно.

Однако возможно преобразование зависимости таким образом,

чтобы можно было вычислить количество зёрен на клетке, отстоящей

через одну.

То есть получить зависимость чётного элемента

последовательности от предыдущего чётного элемента, и то же для

нечётных элементов последовательности. Теперь вычисления можно

производить одновременно для чётных и нечётных элементов,

используя, например, два вычислительных устройства.

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

получить зависимость вычислений для трёх, четырёх и большего

количества вычислительных устройств. Преобразование

циклической

конструкции выполняется по шагам:

267

 раскрутка цикла - это дублирование тела цикла, сокращение

числа итераций, замена переменных цикла на выражения;

 сокращение числа операций в теле цикла, приведение

нескольких циклов к одному, размещение до цикла

операторов вычисления значений первых элементов.

Другой интересный пример – числа Фибоначчи. Это тоже

рекуррентная последовательность, где очередной элемент является

суммой двух предыдущих. Граф информационной зависимости

вычисления чисел Фибоначчи показывает, что вычисления элементов

можно выполнить так же, как

в предыдущем примере, только

последовательно.

Используя известные методы - раскрутку и координатный метод,

предложенный в работе [2], можно преобразовать цикл вычисления

чисел Фибоначчи к виду, допускающему одновременное вычисление

двух элементов последовательности из двух предыдущих элементов

последовательности. Координатный метод предполагает вычисление

каждого из двух чисел на собственном вычислительном устройстве и

их синхронизацию перед выполнением

следующей итерации цикла.

Однако, используя предложенное преобразование циклических

конструкций, цикл вычисления чисел Фибоначчи можно

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

по два новых значения из двух значений, полученных на предыдущей

итерации, независимо и одновременно.

Эффективность предложенного метода преобразования циклов

Эксперименты на четырёхпроцессорном кластере Регионального

центра суперкомпьютерных вычислений Пензенского

государственного университета подтвердили прогноз по сокращению

времени вычислений преобразованных циклических конструкций.

Кластер состоит из двух узлов, на каждом из которых находятся два

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

могут обрабатывать данные в специально выделенной общей памяти

одновременно. При использовании двух процессоров

для

рассмотренных примеров было достигнуто двукратное сокращение

времени выполнения преобразованных циклических конструкций с

учётом того, что общее число вычисляемых элементов

последовательности было кратно четырём, то есть не требовалась

268

организация дополнительного цикла, осуществляющего вычисления

для остатка итераций.

Уменьшить время выполнения циклов вычисления рекуррентных

последовательностей можно даже в вычислительных системах с

разделяемой памятью при условии, что время вычислений на

однопроцессорной системе превышает сумму времени выполнения

вычислений на нескольких вычислительных устройствах и времени

обмена данными для объединения полученных результатов

вычислений каждого

процессорного элемента.

Предложенный метод позволяет выполнить преобразование

значительного числа сложных циклических конструкций,

содержащихся в алгоритмах настоящих программ. Использование

предложенного преобразования в препроцессорах стандартных языков

программирования или специальных компиляторах с языков описания

позволит получить более эффективные алгоритмы решения

прикладных задач.

Литература

1. Yong Z., Jiahua Q. Dynamic Detection of Parallelism in PASCAL-

like Program.

Lamport Leslie. The Parallel Execution of DO Loops/ //

Communications of ACM, Number 2, Volume 17, 1974.

Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. –

СПб.: БХВ-Петербург, 2004. – 608 с.: ил.

ЭФФЕКТИВНОЕ ИСПОЛЬЗОВАНИЕ РЕСУРСОВ

ВЫЧИСЛИТЕЛЬНОГО КЛАСТЕРА

В.В. Мялицин

Пензенский государственный университет

Введение

Прогресс в области сетевых технологий обусловил популярность

вычислительных кластеров [1]. Эти вычислительные системы

считаются самыми недорогими и простыми в организации. Они

распространены в большинстве образовательных и коммерческих

учреждений, на промышленных предприятиях. Простой

вычислительный кластер может быть совокупностью компьютеров,

объединенных в рамках некоторой сети для решения одной задачи.

269

Однако при проектировании вычислительного кластера для

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

ресурсной базы и алгоритма решения: необходимо оценить объём

вычислительной работы и определить количество вычислительных

устройств, при котором время решения будет наименьшим, что

позволит максимально эффективно использовать имеющиеся ресурсы.

Определение оптимального количества вычислительных устройств

является нетривиальной задачей, так как

время решения задачи

зависит от множества факторов: количества оперативной памяти на

узлах кластера, производительности дисков и коммуникационной

среды и, наконец, программной реализации алгоритма решения задачи.

Определение оптимального количества процессоров в

кластере

По закону Амдала время решения задачи складывается из двух

составляющих: времени выполнения последовательных операций и

времени выполнения параллельных операций с учётом числа

процессорных элементов [2]. Однако при решении задач на

вычислительных кластерах ко времени фактического решения

прикладной задачи добавляется время выполнения дополнительных

операций, необходимых для обмена информацией между

вычислительными устройствами, то есть

накладные расходы.

Накладные расходы систем кластерного типа могут превысить

вычислительные затраты. Они напрямую зависят от аппаратных

характеристик вычислительной системы: скорости передачи данных

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

элементов и объёма памяти, а также от заложенного в алгоритме числа

передаваемых сообщений для решения задачи.

Таким образом, в системах кластерного типа при

решении задачи

необходимо учитывать время, затрачиваемое на обмен информацией

между вычислительными системами. Часто это время зависит от

количества используемых вычислительных устройств и

представляется сложной зависимостью, уникальной для каждого

конкретного случая – алгоритма и аппаратной платформы.

Увеличение количества используемых вычислительных устройств,

с одной стороны, позволяет сократить время решения задачи за счёт

одновременной обработки

нескольких блоков информации, но, с

другой стороны, растущее количество передаваемых сообщений в

кластерной системе производит обратный эффект.

270

Таким образом, для решения конкретной задачи на

вычислительном кластере существует оптимальное, с точки зрения

времени выполнения, число вычислительных устройств, так как

накладные расходы с ростом числа процессорных элементов

увеличиваются и в какой-то момент станут сопоставимы с

вычислительными расходами.

Автором предложена методика определения оптимального

количества процессоров, которая предполагает анализ реализации

аппаратно-программного обеспечения. По результатам анализа

составляется зависимость времени выполнения задачи от величин,

характеризующих решение задачи на многопроцессорной кластерной

системе, с учётом отклонения экспериментального значения времени

решения задачи от теоретического значения.

В предложенной методике этими величинами считаются три

значения времени: время выполнения последовательных участков

алгоритма, время параллельных вычислений и время, необходимое

для

обмена сообщениями по коммуникационной среде с учётом её

особенностей.

Методика определения количества вычислительных устройств,

при котором время решения задач будет минимальным, позволяет

последовательным приближением определить оптимальное число

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

результаты проведённых экспериментов.

Поскольку неизвестных величин – три, то необходимо провести

как минимум три эксперимента при

разном числе процессоров. На

основе полученных экспериментальных данных составляется система

уравнений времени решения задачи с отклонениями практических

результатов от теоретических прогнозов. Коэффициенты (величины,

составляющие время решения задачи) находятся с учётом того, что все

они положительны, и из условия минимума суммы квадратов

отклонений. Полученные значения коэффициентов подставляются в

формулу зависимости, и строится

график зависимости времени

решения задачи от числа используемых вычислительных устройств, по

которому определяется точка перегиба – оптимальное количество

устройств. Для уточнения количества процессоров проводится

эксперимент с использованием нового количества процессоров.

Полученное значение времени решения задачи добавляется в систему

уравнений, и снова определяются коэффициенты. После получения

новых значений и построения графика определяется

новая точка