РАСПАРАЛЛЕЛИВАНИЕ ВЫЧИСЛЕНИЙ ТРАНСЦЕНДЕНТНЫХ

 
121 
очень  важно,  особенно  для  образовательных  и  научных  учреждений, 
которым часто суперкомпьютеры просто не доступны. 
В  работе  подробно  рассматривается  класс  задач,  связанных  с  ин-
тенсивным использованием блока вещественной арифметики, особен-
но  такие,  в которых значительную долю составляют вычисления эле-
ментарных математических функций. Эти задачи условно разделяются 
на два вида. Первый, наиболее часто встречающийся, составляют зада-
чи,  в  которых  происходит  обработка  достаточно  больших  массивов 
входных аргументов. Второй связан с приложениями, активно исполь-
зующими скалярные математические функции, в силу таких особенно-
стей алгоритма, как, например, рекурсивность.  
Подобная условная классификация весьма удачна в данном случае 
и позволяет сразу же увидеть важные особенности при распараллели-
вании  математических  функций.  В  большинстве  известных  сейчас 
платформ персональных ЭВМ и, в частности, платформ Intel Architec-
ture,  поддержка  вычислений  элементарных  и  трансцендентных  мате-
матических  функций  реализована  либо  в  интегрированном  математи-
ческом сопроцессоре, либо программной эмуляцией. Как в первом, так 
и во втором вариантах эти функции достаточно дешевы для того, что-
бы  заниматься  распараллеливанием  их  алгоритма,  даже  когда  вычис-
ления проводятся над векторами входных аргументов. С другой сторо-
ны,  обладая  кластером  независимых  машин  и  производя  вычисления 
над  вектором  аргументов,  мы  можем  тривиально  распараллелить  их, 
выдавая каждому узлу независимые входные значения и производя на 
каждом  из  них  полностью  независимые  вычисления.  Эффективность 
распараллеливания  в  таком  случае  может  достигать  теоретических 
100%  в  зависимости  от  скорости  обмена  между  узлами  и  «главной» 
машиной, сохраняющей результаты. Многое на этом этапе зависит от 
эффективности  прикладных  пакетов,  позволяющих  организовать  вы-
числения в сети, базирующихся на стандарте MPI. Если в составе кла-
стера  есть  многопроцессорные  узлы,  то  потери  можно  сократить  за 
счет использования в таких машинах общей памяти. В настоящее вре-
мя  для  таких  целей  может  быть  использован  стандарт OpenMP, под-
держиваемый  рядом  компиляторов,  в  том  числе  и  корпорации Intel, 
для языков Fortran и C/C++. Кроме того, можно исходный вектор ар-
гументов делить на некоторое подмножество входных векторов и вы-
давать каждый их них на отдельный узел. Для этого можно использо-

122 
вать любой подходящий алгоритм в зависимости от конкретной орга-
низации  кластера  и  с  учетом вычислительных возможностей каждого 
узла.  
Однако  такие  решения  не  помогут  приложениям,  основное  ма-
шинное время которых «съедают» скалярные вызовы математических 
функций.  Как  уже  было  отмечено,  трансцендентные  математические 
функции  дешевы  и  их  распараллеливание  неэффективно.  Действи-
тельно, для популярного процессора PentiumIII стоимость любой такой 
функции  не  превышает 100 процессорных  тактов  и  в  то  же  время  их 
частота достигает 1GHz. Понятно, что получить выигрыш путем заме-
ны  одного  компьютера  высокопроизводительной  вычислительной  се-
тью в данном случае возможно, лишь запустив несколько копий при-
ложения на разных узлах с различными параметрами, т.е. алгоритми-
ческое распараллеливание на уровне сети исключено.  
Возможность  использования OpenMP на  многопроцессорных  уз-
лах для распараллеливания скалярных функций следует, видимо, так-
же  считать  неэффективной  из-за  стоимости  накладных  расходов  на 
организацию  вычислений.  Тем  не  менее,  можно  пытаться  улучшить 
производительность,  используя  параллелизм  на  уровне  инструкций 
(Instruction Level Parallelism), повышая  таким  образом эффективность 
узлов  кластера  и  удешевляя  его  стоимость.  Это  тем более интересно, 
поскольку, улучшая работу отдельного узла для этого вида задач, мы 
также  автоматически  улучшаем  производительность  рассмотренных 
задач  первого  вида,  обрабатывающих  вектора  аргументов.  И  здесь 
важную роль могут играть архитектурные особенности используемых 
для построения кластера персональных машин.  
Большинство современных процессоров так или иначе используют 
технологии,  перекликающиеся  с  идеями  параллельной  организации 
вычислений. В данной работе сделан упор на современные платформы 
Intel Architecture (IA). Семейство 32х-битных процессоров этой архи-
тектуры (IA-32) имеет нескольких ярких черт подобного рода. Прежде 
всего, это наличие инструкций, работающих по принципу SIMD(Single 
Instruction Multiple Data), которые  позволяют  выполнять  однотипные 
операции над несколькими аргументами за одну команду. Так, напри-
мер, набор SSE содержит в себе операции сложения, вычитания и вы-
числения квадратного корня согласно стандарту IEEE-754 для 4 чисел 
в формате плавающей запятой с одинарной точностью, а SSE2 позво-

 
123 
ляет оперировать также 2 числам двойной точности. Другой характер-
ной  особенностью  является  возможность  так  называемого  динамиче-
ского запуска команд: процессор определяет зависимые инструкции и 
запускает  вне  очереди  следующие  команды,  не  дожидаясь  окончания 
выполнения  текущей  инструкции.  Это  позволяет  уменьшить  потери 
производительности из-за зависимого характера вычислений, особенно 
учитывая наличие аппаратного кэширования, а также многоступенча-
того  конвейера  исполнения  инструкций.  Еще  дальше  продвинуты  в 
этом направлении представители нового 64х-битного семейства IA-64. 
Система команд первого процессора этого семейства Itanium построе-
на по принципу EPIC (Explicitly Parallel Instruction Computing), дослов-
но, допускающая параллелизм в явном виде. Особенности архитекту-
ры  и  машинного  кода  данного  процессора  позволяют  выполнять  лю-
бые 2 независимые операции над числами с плавающей запятой, в том 
числе и SIMD-подобные инструкции. 
Все  эти  возможности  позволяют  повысить  эффективность  вычис-
лений  узлов  кластера,  основываясь  на  мелкозернистом  распараллели-
вании,  которое  в  данном  классе  задач  является  наиболее  выгодным 
подходом  и  практически  единственным,  позволяющим  добиться  за-
метных результатов в общем случае.  
В докладе авторы данной работы на основе опыта разработки ска-
лярных и векторных математических функций с использованием архи-
тектурных особенностей IA-32 и IA-64 приводят общий алгоритм для 
трансцендентных функций и подробно рассматривают возможности по 
его  распараллеливанию,  ограничения  общего  случая  и  дополнитель-
ные преимущества в случае обработки векторов данных. 

жүктеу/скачать 1,64 Mb.

Достарыңызбен бөлісу: