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

На правах рукописи

МЯЛИЦИН Вадим Владимирович

ПРЕОБРАЗОВАНИЕ ЦИКЛИЧЕСКИХ КОНСТРУКЦИЙ ДЛЯ МНОГОПРОЦЕССОРНЫХ СИСТЕМ КЛАСТЕРНОГО ТИПА С УЧЕТОМ КОЛИЧЕСТВА ВЫЧИСЛИТЕЛЬНЫХ УСТРОЙСТВ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Г

Автореферат диссертации на соискание ученой степени кандидата технических наук

ПЕНЗА 2008

1111111111111111111111

□□31ВТ4Э5

Работа выполнена на кафедре «Математическое обеспечение и применение ЭВМ» государственного образовательного учреждения высшего профессионального образования «Пензенский государственный университет»

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

Шашков Борис Дмитриевич

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

Гергель Виктор Павлович;

кандидат технических наук Антонов Александр Викторович

Ведущая организация - ООО научно-производственная фирма «КРУГ», г Пенза

Защита диссертации состоится « /5» М&Л 200ffr , в «-/f » часов, на заседании диссертационного совета Д 212.186.01 в государственном образовательном учреждении высшего профессионального образования «Пензенский государственный университет» по адресу. 440026, г Пенза, ул Красная, 40.

С диссертацией можно ознакомиться в библиотеке государственного образовательного учреждения высшего профессионального образования «Пензенский государственный университет» Автореферат размещен на сайте университета www pnzgu ru

Автореферат разослан « 9 » gwpg/uЯ 200J г.

Ученый секретарь

диссертационного совета

доктор технических наук,

профессор

Гурин Е. И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Сокращение времени решения сложных научно-технических задач является стимулом совершенствования вычислительной техники. Оно достигается применением оптимизирующих преобразований к выявленным «недоброкачественным» участкам программного кода, начиная с оптимизации на уровне исходного языка, заканчивая машинно-зависимой оптимизацией

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

Преобразованием на разных уровнях представления алгоритмов занимаются как зарубежные, так и российские специалисты. Среди работ наших ученых самыми значимыми являются труды Воеводина В. В. и Воеводина Вл. В. по оптимизирующим преобразованиям программного кода для однопроцессорных систем. Кроме того, ими разработана система V-Ray для оптимизации выполнения циклических конструкций на многопроцессорных системах Широко известны статьи и патенты сотрудников ЗАО «Московский Центр SPARC-технологий» (МЦСТ), работающих с корпорацией Sun MicroSystems в области высокоуровневой оптимизации циклов в перспективных компиляторах. Среди зарубежных ученых наиболее значимые работы в области оптимизации программ для многопроцессорных систем опубликовали Lamport L и Ramamoorthy С Такие крупнейшие корпорации, как Intel, ЮМ, Sun MicroSystems, разрабатывают оптимизаторы кода, проводят исследования в области построения многопроцессорных систем и патентуют новые решения в области анализа и оптимизации алгоритмов и программ для различных типов вычислительных систем, в том числе параллельных.

Для многопроцессорных вычислительных систем широко применяется автопараллелизация - автоматическая параллелизация циклов, в которых нет зависимости данных.

Сложности при распараллеливании возникают с циклами, в которых присутствуют различные зависимости данных. Преобразование циклических конструкций с неявной зависимостью данных, например вычисление рекуррентных последовательностей, существующими средствами либо невозможно, либо малоэффективно даже при использовании специальной аппаратной поддержки.

Применение специализированных вычислительных комплексов позволяет ускорить решение некоторых классов задач за счет аппаратной реализации операций. Однако специализация резко ограничивает область применения таких систем Напротив, простая в организации архитектура вычислительной системы кластерного типа оказывает влияние на время решения задач Накладные расходы, связанные с пересылкой сообщений, могут перекрыть эффект от использования множества вычислительных устройств.

Применение кластерных вычислительных систем связано с рядом проблем. Известно, что на время решения задачи в кластере влияет количество используемых процессоров При проектировании вычислительного кластера для конкретной прикладной задачи требуется предварительный анализ ресурсной базы и реализации алгоритма, необходимо оценить объем вычислительной работы и определить количество вычислительных устройств, при котором время решения будет наименьшим, что позволит максимально эффективно использовать имеющиеся ресурсы.

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

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

Целью диссертационной работы является повышение эффективности использования ресурсов многопроцессорных систем кластерного типа посредством преобразования программного кода, в частности преобразования циклических конструкций, используемых при реализации алгоритмов прикладных задач.

Для достижения поставленной цели в диссертационной работе решаются следующие задачи.

- анализ и исследование существующих преобразований программ для многопроцессорных систем кластерного типа;

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

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

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

Объект исследования - вычислительные системы кластерного типа и циклические конструкции прикладных программ, представленные на языках программирования высокого уровня. К исследуемым конструкциям относятся циклы вычисления рекуррентных последовательностей и циклы с использованием индексных множеств.

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

Научная новизна работы состоит в следующем:

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

- предложен способ преобразования циклических конструкций с использованием индексных множеств, который позволяет трансформировать исходный алгоритм программы в более эффективный с точки зрения времени его выполнения на вычислительной системе с общей памятью и аппаратной синхронизацией вычислений;

- предложена методика определения количества вычислительных устройств, необходимых для решения задачи на многопроцессорной системе кластерного типа за наименьшее время с учетом дополнения формулы Амдала, что позволяет оценить влияние количества вычислительных устройств и коммуникационной среды на время решения задачи.

Практическая ценность. Разработанные способы преобразования циклических конструкций при интегрировании их в системы оп-

тимизирующей компиляции или специализированные программные комплексы по анализу и преобразованию пользовательских программ в соответствии с требованиями конкретных вычислительных систем позволят сократить время выполнения ряда программ Разработанные способы не зависят от аппаратных платформ и языков реализации алгоритмов, что дает возможность распространить их использование на максимально широкий класс процессорных архитектур и языков программирования.

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

Решение задачи преобразования циклических конструкций вычисления рекуррентных последовательностей и циклов с использованием индексных множеств, а также задачи определения оптимального с точки зрения времени ее решения количества вычислительных устройств имеет существенное значение для повышения эффективности использования ресурсов многопроцессорных систем кластерного типа

Реализация и внедрение результатов работы. При проведении исследования было разработано программное обеспечение, содержащее алгоритм прикладной задачи преобразования информации, который заключается в решении систем линейных уравнений и реализован с использованием вложенных циклических конструкций. Результаты работы были внедрены в изделия, разработанные в рамках ОКР на ФГУП «Пензенский научно-исследовательский электротехнический институт», о чем свидетельствует акт о внедрении

Апробация работы. Результаты работы докладывались на VI Международной научно-технической конференции «Новые информационные технологии и системы» (июнь 2004 г.), 5-й Международной конференции молодых ученых и студентов «Актуальные проблемы современной науки» (сентябрь 2004 г.), X Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании» (апрель 2005 г); Всероссийской научной конференции студентов, аспирантов и молодых ученых «Наука Технологии Инновации» (декабрь 2005 г ), XI и XII международных откры-

тых научных конференциях «Современные проблемы информатизации в моделировании и программировании» (ноябрь 2005 г. - январь 2006 г, ноябрь 2006 г. - январь 2007 г ), V Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (февраль - март 2007 г.); Седьмой международной конференции-семинаре «Высокопроизводительные параллельные вычисления на кластерных системах» (ноябрь 2007 г.). Основные результаты работы опубликованы в журналах. «Прикладная информатика» № 3 за 2006 г, «Научно-технические ведомости Санкт-Петербургского государственного политехнического университета» № 3 за 2007 г В работах, опубликованных в соавторстве, личное участие автора заключается в определении проблем, постановке задач, разработке теоретических положений и непосредственном участии во всех этапах исследования

На защиту выносятся:

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

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

3 Дополненная формула Амдала с учетом обмена сообщениями между узлами многопроцессорной системы кластерного типа

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

Публикации. По теме диссертации опубликовано 11 работ, в том числе одна статья в издании, рекомендованном ВАК России

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка использованных источников из 101 наименования и трех приложений Работа содержит 131 страницу основного машинописного текста, 35 рисунков, 10 таблиц, 28 страниц приложений.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Рассмотрены распространенные оптимизирующие преобразования программ для однопроцессорных и многопроцессорных вычислительных систем.

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

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

Предлагаемые способы позволяют уменьшить количество операций, осуществляемых последовательно, и соответственно время выполнения циклической конструкции. Сокращение времени решения задач достигается за счет одновременного вычисления групп переменных несколькими вычислительными устройствами.

Уменьшение времени выполнения циклов достигается также в вычислительных системах с разделяемой памятью, когда время вычислений превышает время обмена данными для объединения результатов вычислений, полученных на каждом вычислительном устройстве.

Предложен способ преобразования циклических конструкций вычисления рекуррентных последовательностей Он предполагает изменение алгоритма вычисления элементов некоторого множества в теле цикла Вычисление очередного элемента множества выражается зависимостью, общей вид которой следующий-

~ [Л—>«,+! ]-3] 5

где 1>к> ]>. > 1, т. е (/ - к) > 1; (к - у) > 1 и т. д

Таким образом, элемент множества зависит (знак «~») от некоторой совокупности предыдущих элементов этого множества (или одного элемента). Выражение в квадратных скобках может в зависимости отсутствовать.

Очередной элемент множества 5|+( рассчитывается исходя из значений не более чем к предыдущих элементов множества.

Алгоритм вычисления значений элементов данного множества легко реализуется циклической конструкцией. Однако полученный алгоритм не поддается распараллеливанию на множество вычислительных устройств ни одним из известных способов. В результате анализа графа информационной зависимости этого алгоритма можно сделать вывод о том, что вычисление элементов множества производится последовательно

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

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

Преобразование заключается в замене исходной зависимости вычисления очередного элемента множества на совокупность зависимостей таким образом, чтобы можно было вычислить к новых значений из к предыдущих значений и подсчитанные к новых значений использовать для подсчета к значений на следующей итерации циклической конструкции.

Если вычислительная система имеет N процессоров, а очередное значение элемента множества зависит от к значений предыдущих элементов этого множества, то процессор с номером Р (начиная с нуля) будет вычислять значения следующих элементов множества:

31+к+Рк+№ 1 ^ 31+к-\+Рк+Ык 1 = 5/+/:-2+М+М-1 ¿и-У+Рк+Ык 1 ^

Я1+к+Рк+т 2 5 31+к-1+Рк+№ 21 Я1+к-2+Рк+№ 2 '->$г+\+Рк+№ 2 5

Я1+к+Рк+№¥ > Я1+к-1+Рк+тГ > Я1+к-2+Рк+МГ '—'¿/Н+Рк+МГ'

где один из элементов последней строки является последним элементом рассчитываемого множества. Значение ¥ определяется его индексом.

Иными словами, преобразование заключается в формировании новых зависимостей.

$1+к+Рк+Ш ~ Ярк+г+Л^Рк-н+к-хЫ • > ^/>¿+1+1] •]]> Я1+к-1+Рк+№ ~ 3Рк+1+к['3Рк+1+к-\[Л >5РЛ: + 1+1]—Б'

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

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

~ (задача о зернах на шахматной доске), (1) 81 ~ ,?,_2 (числа Фибоначчи), (2)

где - элементы множества (представляемые ячейками массива в памяти вычислительного устройства), зависимые от некоторых предыдущих элементов этого множества.

Для зависимости (1) преобразование циклической конструкции для двух вычислительных устройств (Р - номер устройства начиная с 0) проведено по шагам1

/ог(1Тй I =1,г < N,1 ++) /ог{ти = 1,кМ,1+ = 2) Раскрутка цикла

I { дублирование тела цикла,

—ч п г „ _». сокращение количества

— итераций, замена перемен-

ных цикла на выражения

}

Сокращение количества я[1] = 2* 5[0], операций в теле цикла,

/ог(1Ш I = 11 < N 1+ = 2) = 2 * приведение нескольких

=> «Г,+ 11 = 2*2*41«-11 => М(ти~2+Р,кМ, 1+ = 2) Циклов к одному, раз-1 -1 1 г 1 д * г - ?1 мещение до цикла опе-

[ог(т\1 = 2,1 < N,1+ = 2) = 4 г1> раторов вычисления

«[г +1] = 2 * 2 * ф -1], значений первых эле-

ментов

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

1 уст-во) for (int х=2,1<N;l+=2) S[l]=4*S [l-2] ;

2 уст—во) S [1]=2*S [0] ;

for (int 1 = 3;1<N,l+=2) S [i]=4*S [i-2] ;

В общем виде для устройства с номером Р (начиная с 0):

S [1] = 2*S [0] ,

for (int l=2+P;i<N,i+=2) S [i]=4*S [i-2],

И для трех вычислительных устройств-

1 уст-во) for (mt 1=3, 1<N,i+=3) S [l] =8*S [l-3] ,

2 уст-во) S[1]=2*S [0],

for (mt i=4;i<N;i+=3) S [i]=8*S[i-3];

3 уст-во) S[1]=2*S[0], S [2] =4*S [0] ;

for (mt i=5, i<N;i+=3) S[i]=8*S [i-3],

В общем виде для устройства с номером Р (начиная с 0):

S [1] =2*S [0] , S [2] =4*S [0] ;

for (mt i=3+P, i<N, l+=3) S [i]=8*S [1-3] ,

При использовании метода раскрутки и координатного метода, который разработал L Lamport, зависимость для примера (2) преобразуется следующим образом

st =si-l +si-2>si+l -(st-1 + =2si-1 ~t~ si-2 •

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

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

s, =3s,_2 + 2^г„4,

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

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

В работе рассмотрены и другие более сложные примеры, представленные циклическими конструкциями на языке Си

for (mt 1=1; 1<N, l++) A[i] =С [i] *А[l-l] ;

for(mt i=N-l, i>0,1—)

A[i-1] =D[i+l]+A[l]*A[l+l]/В [l],

for(int 1=1;1<H;l++) A[i]=(A[l—1]+B[l])/С[l] ,

for (mt 1=1, 1<N, 1 + + ) A [l] =B [A [l-l] ] ;

Предлагаемый способ позволяет выполнить преобразование множества сложных циклических конструкций, содержащихся в алгоритмах прикладных программ Использование этого способа в препроцессорах стандартных языков программирования высокого уровня или специальных компиляторах с языков описания дает возможность получить более эффективные алгоритмы решения прикладных задач

Второй предложенный способ преобразует циклы с использованием индексных множеств. При рассмотрении циклических конструкций, в которых порождаемые {находящиеся в левой части выражения) переменные рассчитываются не по индексу - переменной цикла, а по более сложной зависимости, как правило, делают вывод, что распараллелить такие циклы невозможно. Однако в диссертационной работе показано, что при специальной аппаратной под держке это осуществимо.

Рассмотрено вычисление элементов множества со следующей зависимостью.

bSi = с,, где а, Ъ и с - множества элементов.

Порядок вычислений здесь имеет огромное значение, так что при kl=al,k2=aJ,kl=k2,i^ J в элемент bki =Ъкг записываются значения с, и сj. Причем в конечном итоге в Ькх должно быть значение сj, если j > i, или с, - в противном случае

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

Предложен способ преобразования рассмотренной циклической конструкции с использованием дополнительного множества (некоторого объема памяти) и аппаратной поддержки блокировок доступа к данным на время выполнения некоторого участка программного кода. Пример кода преобразования цикла с индексным множеством

Исходная циклическая конструкция-for (int l=0;i<»,l++) B[A[l]]=C[iJ ;

Преобразованный код программы:

for (mt 1=0; 1<N; 1++) IND[l] = (int)-lj for (mt i=0;i<N; i++) { // lock IND[A [l] ]

if (IND [A [i] ] < (int) l) { IND[A[l]]=i;B[A[l]]=C[l] , } // unlock IND[A[iJ]

}

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

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

Для действительно правильных вычислений в цикле - расчета элементов множества В - необходима аппаратная блокировка ячейки П>ГО[А[Ц] в позициях, указанных комментариями

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

Для получения эффекта от использования способа преобразования циклических конструкций с использованием индексного множества необходимо, чтобы количество итераций выполнения цикла было не менее количества задействованных вычислительных устройств. Условия, ограничивающие область применения данного преобразования, являются стандартными для циклических конструкций- в теле цикла не должны присутствовать операторы безусловных переходов, прерывания цикла, ввода-вывода или вызова подпрограмм, влияющих на формирование значений переменных.

Третья глава посвящена анализу процесса решения прикладных задач на кластерных вычислительных системах. Поскольку в вычислительных системах кластерного типа задача решается на узлах комплекса с использованием некоторого интерфейса обмена данными, например интерфейса передачи сообщений, то ко времени действительного решения прикладной задачи добавляется время выполнения дополнительных операций, необходимых для обмена информацией между вычислительными устройствами, т е. накладные расходы.

Время решения задачи в многопроцессорной системе кластерного типа складывается из нескольких составляющих:

- времени выполнения фрагментов задачи - Тс, которое не зависит от количества используемых для решения задачи устройств (оно

включает в себя время выполнения всех последовательных фрагментов задачи Тс и время передачи данных по сетевым соединениям Т5 ),

- времени выполнения параллельных фрагментов задачи одним вычислительным устройством - ТР;

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

Например, Гу' - время передачи результата на головной узел в задаче поиска элемента в некотором множестве, которое делится на равные части для вычислительных устройств (результат поиска содержится только в одном из фрагментов)

С учетом этого произведено дополнение формулы Амдала для многопроцессорных систем кластерного типа, что позволяет оценить влияние составляющих вычислительного процесса На время решения прикладных задач. По закону Амдала время решения задачи Тт определяется двумя составляющими временем выполнения последовательных операций Тс и временем выполнения параллельных операций ТР с учетом количества процессорных элементов т

Тт =ТС+^- или Тт +т—, (3)

т т

где х - время выполнения одной операции,

А^ - количество операций в последовательной части алгоритма, N■2 - количество операций в параллельной части алгоритма, т - количество вычислительных устройств

Для кластерных систем необходимо учесть обмен информацией между вычислительными устройствами. В формулу (3) добавлена компонента.

Т3=(т- 1)Г; =(т- 1)(тЛГ3 + ц>)М', где Щ-количество операций подготовки сообщения;

у - время передачи сообщения по коммуникационной среде;

М - количество передаваемых сообщений.

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

устройств или от каждого к каждому) так, что М может быть пропорционально тк, где к = 0 ..оо и называется коэффициентом размножения сообщений

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

Тт=(Тс+Т;) + ^- + (т-\)Т3, (4)

тп

где т > 1 и Тс = Т^

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

Формула (4) показывает, что, с одной стороны, увеличение количества используемых вычислительных устройств позволяет сократить время решения задачи за счет одновременной обработки нескольких блоков информации, но, с другой стороны, растущее количество передаваемых сообщений в кластерной системе производит обратный эффект

Таким образом, выдвигается предположение о том, что существует оптимальное с точки зрения времени выполнения количество вычислительных устройств кластерной системы для решения задачи, так как накладные расходы с ростом количества процессорных элементов увеличиваются и в какой-то момент станут сопоставимы с вычислительными затратами.

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

В диссертационной работе предложена методика определения количества вычислительных устройств многопроцессорной системы кластерного типа, необходимого для решения задачи за наименьшее время. В этой методике по результатам реализации аппаратно-программного обеспечения и алгоритма решения задачи составляется зависимость времени выполнения задачи от величин, характеризующих решение задачи на многопроцессорной кластерной системе Этими величинами считаются время выполнения последовательных участков алгоритма, время выпол-

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

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

Для решения данной задачи к, определяемое неравенствами Тк < Тк_\ и Тк< Тк+1, что соответствует точке перегиба на графике функции Тт, будет таким количеством вычислительных устройств, при котором время вычислений наименьшее.

Методика определения количества вычислительных устройств кластерной системы, при котором время решения задач будет наименьшим, опирается на методы обработки эмпирических данных и позволяет последовательным приближением определить к. На основе экспериментальных результатов составляется система уравнений следующего вида:

Ттх~ТС+ — + ~ + О , 1 1

Тт2 =ТС + — + Т8{тг -1 )тк2 + а , 2 т2

Тт„ - Тс + — + Т$(т„ - + °т„ > тп

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

Коэффициенты в зависимости определяются с учетом неравенств Тс>0,ТР >0,Г5>0 и условия минимума суммы квадратов отклонений

* 2 ¡=1

Полученные значения ТС,ТР,Т$ подставляются в формулу зависимости, строится график функции Тт, по которому определяется точка перегиба кх.

Для уточнения количества процессоров проводится эксперимент с использованием кх процессоров Полученное значение добавляется в систему уравнений, снова определяются коэффициенты зависимости ТС,ТР,Т5

Когда получены новые значения и построен график, определяется новая точка перегиба к2 Все описанные действия повторяются до

тех пор, пока \к2 -кг_х|<1.

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

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

В третьей главе также рассмотрены прикладные задачи обработки информации, связанные с ее изменением и восстановлением, и подход к их решению, основанный на использовании параллельных вычислительных систем и позволяющий уменьшить несоответствие вычислительной нагрузки при прямом и обратном преобразованиях информации (кодировании или сжатии данных, музыки и речи, видео и графической информации и восстановлении или распаковки их для просмотра или воспроизведения).

Подробно рассмотрены задача решения системы линейных уравнений и существующие алгоритмы ее решения на вычислительных системах кластерного типа.

В четвертой главе описано проведение экспериментов, подтверждающих получение эффекта от использования множества вычислительных устройств, по решению задач, обладающих внутренним параллелизмом, на вычислительных системах кластерного типа. Рассмотрена возможность сокращения времени решения прикладной задачи преобразования информации, заключающейся в решении систем линейных уравнений с заполненной матрицей Определено количество процессорных элементов, необходимых для достижения максимального сокращения времени вычисления задачи для ряда вычислительных систем кластерного типа

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

Эксперименты проводились на следующих аппаратных платформах

- 4-процессорном кластере Регионального центра суперкомпьютерных вычислений Пензенского государственного университета (РЦСВ ПТУ) с процессорами Alpha 21264, 666 МГц, общим объемом оперативной памяти 2 Гбайт, коммуникационной средой Ethernet 1 Гбиг/с;

- сетевом многомашинном комплексе компьютерной лаборатории Института информатики и вычислительной техники Пензенского государственного университета с процессорами Intel Pentium Celeron 1 ГГц и коммуникационной средой Ethernet 100 Мбит/с;

- 24-процессорном вычислительном кластере «LEO» научно-исследовательского вычислительного центра Московского государственного университета (НИВЦ МГУ) при Межведомственном су-перкомпыотерном центре с процессорами Intel Xeon 2660 МГц, общим объемом оперативной памяти на всех 12 узлах в 12 Гбайт, коммуникационной средой SCI D335 на топологии 2D-Top 3x4.

Полученные результаты подтвердили эффективность использования множества вычислительных устройств для решения систем линейных уравнений на кластерных вычислительных системах При этом условием для сокращения времени решения систем уравнений является их достаточный размер, а также производительность коммуникационной среды кластера При малом объеме задачи доля параллельных вычислений несущественна по сравнению с долей последовательных вычислений и временем обмена сообщениями между вычислительными устройствами кластера.

На основе полученных экспериментальных результатов сделан вывод о том, что существует возможность получения эффекта от одновременного выполнения фрагментов задачи, обладающей внутренним параллелизмом, на вычислительной системе кластерного типа.

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

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

Время передачи сообщений по коммуникационной среде составило небольшую долю от общего времени решения задачи Для расчета средних временных значений были использованы результаты экспериментов, проведенных на сетевом кластере лаборатории Пензенского государственного университета, с учетом минимального отклонения значений, полученных в результате эксперимента, от теоретических прогнозов.

РЕШЕНИЕ СИСТЕМЫ УРАВНЕНИЙ С128 НЕИЗВЕСТНЫМИ

2 4 6

Количество процессоров, шт

РЕШЕНИЕ СИСТЕМЫ УРАВНЕНИЙ С 296 НЕИЗВЕСТНЫМИ

Количество процессоров, вя

РЕШЕНИЕ СИСТЕМЫ УРАВНЕНИЙ С 512 НЕИЗВЕСТНЫМИ

РЕШЕНИЕ СИСТЕМЫ УРАВНЕНИЙ С 1024 НЕИЗВЕСТНЫМИ

2 4 6 8 10 Количество процессоров, шт

Количество процессоров, ил

Рисунок 1 - Результаты экспериментов При решении системы из 2048 уравнений было получено среднее время выполнения операций для данного кластера При этом время выполнения последовательных вычислений было около 17 с, время выполнения параллельных вычислений - около 1045 с Доля последовательных операций составила 1,6 %.

Зная долю последовательных операций, для других экспериментов произвели аналогичные расчеты с целью оценки средних значений времени решения задачи Расчеты показали, что доля времени передачи сообщений составляет менее 0,5 %.

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

В заключении перечислены основные результаты работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

1 В результате анализа известных преобразований программ, в частности преобразований циклических конструкций, в которых присутствуют зависимости данных, для многопроцессорных систем кластерного типа было выявлено, что эти преобразования недостаточно эффективны для некоторых типов циклов и существует возможность их усовершенствования

2 Предложен способ преобразования циклических конструкций вычисления рекуррентных последовательностей, т. е циклов вычисления элементов множества из значений предыдущих элементов этого же множества, отличающийся от известных способов тем, что исходную зависимость вычисления элементов последовательности заменяют на совокупность зависимостей, что позволяет ускорить выполнение циклических конструкций на многопроцессорной системе, так как полученные после преобразования независимые участки программы можно выполнять в нескольких потоках управления. Для рассмотренных в работе циклических конструкций время выполнения преобразованного программного кода сокращается пропорционально количеству применяемых вычислительных устройств При использовании двух процессоров одного узла кластерной системы время выполнения преобразованных циклических конструкций сокращается в два раза

3 Предложен способ преобразования циклов с использованием индексных множеств, который позволяет трансформировать исходный алгоритм программы в более эффективный с точки зрения времени его выполнения на вычислительной системе с общей памятью и аппаратной синхронизацией вычислений При использовании дополнительного объема памяти время выполнения циклических конструкций с использованием индексного множества на системе с общей памятью с тремя или более вычислительными устройствами сокращается не менее чем на 20 %.

4 Сформулированы основные критерии оценки параллельного вычислительного процесса, описано влияние его составляющих на время

решения прикладных задач в параллельных системах, дополнена формула Амдала для многопроцессорных систем кластерного типа с учетом обмена сообщениями между узлами по коммуникационной среде.

5 Предложена методика определения количества вычислительных устройств, необходимых для решения задачи на многопроцессорной системе кластерного типа за наименьшее время с учетом дополненной формулы Амдала, позволяющая оценить влияние количества вычислительных устройств и характеристик коммуникационной среды на время решения задачи, а также долю последовательных операций в алгоритме по результатам экспериментов

6 Получены экспериментальные значения времени решения прикладной задачи, заключавшейся в решении систем уравнений, на вычислительных системах кластерного типа Результаты экспериментов подтвердили сокращение времени решения задач пропорционально количеству вычислительных устройств, задействованных в многопроцессорных комплексах Определена зависимость времени выполнения задачи, заключающейся в решении систем уравнений, от ее размера при различном количестве используемых процессорных элементов

7 Получены экспериментальные результаты, подтверждающие существование такого количества процессорных элементов, при котором время решения задачи наименьшее. Для решения систем уравнений спрогнозировано время выполнения алгоритма при разных объемах обрабатываемой информации для вычислительных систем кластерного типа и оценены доля последовательных вычислений и доля операций передачи сообщений по коммуникационной среде, что позволило определить количество вычислительных устройств, при котором время решения задачи наименьшее Время решения системы из 1024 линейных уравнений методом Гаусса-Жордана на пятнадцати вычислительных устройствах сокращается более чем в 10 раз относительно времени решения той же задачи на одном вычислительном устройстве.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных ВАК России

1 Мялицин, В В Эвристика определения оптимального количества процессоров кластерной системы / В В Мялицин, Б Д Шашков// Научно-технические ведомости Санкт-Петербургского государственного политехнического университета -2007 -№3 - С 113-118.

Публикации в других изданиях

2 Мялицин, В В. Транспортная среда распределенных вычислений / В В Мялицин, Б. Д Шашков // Труды 5-й Международной конференции молодых ученых и студентов «Актуальные проблемы современной науки» -Самара, 2004 -Ч. 18-Б - С. 22-24

3 Мялицин, В. В Транспортная среда распределенных вычислений ROKS архитектура и технология работы / В В Мялицин, Б Д Шашков // Труды VI Международной научно-технической конференции - Пенза . Изд-во Пенз гос ун-та, 2004 - Ч 1 - С 62-69

4 Мялицин, В В Параллельные вычисления в помехоустойчивом кодировании / В. В Мялицин // Материалы Всероссийской научно-технической конференции студентов, молодых ученых и специалистов - Рязань Изд-во РГРА, 2005

5 Мялицин, В В. Эффективность параллельных вычислений в помехоустойчивом кодировании / В В Мялицин // Материалы Всероссийской научной конференции молодых ученых В 7 ч Ч 2 - Новосибирск Изд-во НГТУ, 2006 - С 62-64

6 Мялицин, В В Тенденции развития языковых средств описания задач / В. В Мялицин Н Современные проблемы информатизации в моделировании и программировании сб тр Вып 11 / под ред д-ра техн наук, проф О Я Кравца. - Воронеж Изд-во «Науч. книга», 2006 - С 247-250

7 Мялицин, В В Эффективность параллельной реализации алгоритмов помехоустойчивого кодирования Рида-Соломона / В В Мялицин, Б Д Шашков // Прикладная информатика - 2006 - № 3 - С 120-129

8 Мялицин, В В Моделирование параллельного вычислительного процесса / В В Мялицин // Современные проблемы информатизации в проектировании и телекоммуникациях сб тр Вып 12 / под ред д-ра техн наук, проф О Я Кравца - Воронеж . Изд-во «Науч книга», 2007 - С 307-309

9 Мялицин, В. В. Методика определения оптимального количества процессоров кластерной системы / В В Мялицин // Материалы V Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых -Томск Изд-воТПУ,2007.-С 433-434

10 Мялицин, В В Преобразование циклов вычисления рекуррентных последовательностей / В В. Мялицин // Высокопроизводительные параллельные вычисления на кластерных системах материалы Седьмой междунар конф -семинара ~Н Новгород Изд-во Нижегор гос ун-та,2007 -С 262-267

11 Мялицин, В В Эффективное использование ресурсов вычислительного кластера / В. В Мялицин // Высокопроизводительные параллельные вычисления на кластерных системах материалы Седьмой междунар конф -семинара ~Н Новгород : Изд-во Нижегор гос ун-та, 2007 - С 267-271

Мялицин Вадим Владимирович

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

Специальность 05 13 11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Редактор £ П Мухина Технический редактор Я А Вьялкова

Корректор Н А Сидельникова Компьютерная верстка Я Б Ивановой

ИД №06494 от 26 12 01

Сдано в производство 02 04 08 Формат 60x84'/16 Бумага писчая Печать офсетная Уел печ л 1,16 Заказ № 202 Тираж 100

Издательство Пензенского государственного университета 440026, Пенза, Красная, 40

Введение.

1 Оптимизация и распараллеливание программного кода.

1.1 Анализ и преобразование алгоритмов решения задач.

1.2 Оптимизация и оптимизирующие преобразования программ

1.3 Оптимизация и параллельная обработка данных.

1.4 Параллельная оптимизация циклов.

1.5 Рекуррентные программные циклы.

1.6 Выводы по главе.

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

2.1 Циклические конструкции.

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

2.3 Способ преобразования циклов с использованием индексных множеств.

2.4 Выводы по главе.

3 Решение задач на кластерных вычислительных системах.

3.1 Объем информации и количество вычислителей.

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

3.3 Оценка эффективности параллельных вычислений для задач обработки информации.

3.4 Выводы по главе.

4 Эффективность методики определения количества вычислительных устройств.

4.1 Использование методики для оценки стандартных пакетов.

4.2 Использование методики для оценки алгоритмов программ.

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

4.4 Применение методики для разрабатываемых программ.

4.5 Применение методики в практических задачах.

4.6 Выводы по главе.

Актуальность темы. Сокращение времени решения сложных научно-технических задач является стимулом совершенствования вычислительной техники. Оно достигается< применением оптимизирующих преобразований к выявленным "недоброкачественным" участкам прок граммного кода, начиная с оптимизации на уровне исходного языка, заканчивая машинно-зависимой оптимизации.

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

Преобразованием на- разных уровнях представления алгоритмов занимаются как зарубежные, так и российские специалисты. Среди достижений наших ученых самыми значимыми являются труды Воеводина В.В. и Воеводина Вл.В. [12] по оптимизирующим преобразованиям программного кода для однопроцессорных систем. Кроме того ими разработана система V-Ray [97] для оптимизации выполнения циклических конструкций на многопроцессорных системах. Широко известны статьи и патенты сотрудников ЗАО "Московский Центр SPARC-технологий" (МЦСТ) [68], сотрудничающих с корпорацией Sun MicroSystems в области высокоуровневой оптимизации циклов в перспективных компиляторах. Среди зарубежных ученых выдающиеся работы в области оптимизации программ для многопроцессорных систем опубликовали Lamport L. [94] и Ramamoorthy С. Такие крупнейшие корпорации, как Intel, IBM, Sun MicroSystems, разрабатывают оптимизаторы кода, проводят исследования в области построения многопроцессорных систем и патентуют новые решения в области анализа и оптимизации алгоритмов и программ для различных типов вычислительных систем, в том числе параллельных.

Постоянная нехватка должной аналитической поддержки со стороны языков программирования, компиляторов и операционных систем; в обеспечении эффективности процессов решения задач привела к созданию специализированных программных комплексов по анализу пользовательских программ и их преобразованию в^ соответствии с требованиями конкретных вычислительных систем. Указанные комплексы (некоторого* рода препроцессоры языков программирования высокого уровня), представляя; собой автономные программные системы, оказались удобным инструментом для выполнения; различных работ, когда программы одного вида нужно перевести в эквивалентные программы другого вида [12].

Одним из важнейших преобразований современных компиляторов* является автопараллелизация. Автопараллелизация. — это семейство оптимизирующих преобразований, позволяющих запускать последовательные независимые участки программы параллельно в нескольких потоках управления; Наиболее распространена;автоматическая параллели-зация циклов, в которых нет зависимости данных. Автопараллелизация позволяет эффективно использовать преимущества мультипроцессорных архитектур [68].

Сложности при распараллеливании возникают с циклами, в которых присутствуют различные зависимости данных. Преобразование циклических конструкций с неявной зависимостью данных, например вычисление рекуррентных последовательностей, существующими средствами либо невозможно, либо малоэффективно даже при использовании специальной аппаратной^ поддержки.

Применение специализированных вычислительных комплексов позволяет ускорить решение некоторых классов задач за счет аппаратной реализации операций. Однако специализация резко ограничивает область применения таких систем. Напротив, простая в организации архитектура вычислительной системы кластерного типа оказывает влияние на время решения задач. Накладные расходы, связанные с пересылкой сообщений, могут перекрыть эффект от использования множества вычислительных устройств.

Применение кластерных вычислительных систем связано с рядом проблем. Известно, что на время решения задачи в кластере влияет количество используемых процессоров [16]. При проектировании вычислительного кластера для конкретной прикладной задачи требуется предварительный анализ ресурсной базы и реализации алгоритма: необходимо оценить объем вычислительной работы и определить количество вычислительных устройств, при котором время решения будет наименьшим, что позволит максимально эффективно использовать имеющиеся ресурсы.

Определение оптимального количества вычислительных устройств нетривиально, так как время решения задачи зависит от множества факторов: количества оперативной памяти на узлах кластера, производительности дисков и коммуникационной среды и, наконец, программной реализации алгоритма решения задачи.

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

Целью диссертационной работы является повышение эффективности использования ресурсов многопроцессорных систем кластерного типа посредством преобразования программного кода, в частности преобразования циклических конструкций, используемых при реализации алгоритмов прикладных задач.

Для достижения поставленной цели в диссертационной работе решаются следующие задачи:

- анализ и исследование существующих преобразований программ для многопроцессорных систем кластерного типа;

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

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

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

Объект исследования - вычислительные системы кластерного типа и циклические конструкции прикладных программ, представленные на языках программирования высокого уровня. К исследуемым конструкциям относятся циклы вычисления рекуррентных последовательностей и циклы с использованием индексных множеств.

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

На защиту выносятся:

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

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

- дополненная формула Амдала с учетом обмена сообщениями между узлами многопроцессорной системы кластерного типа;

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

Методологическая основа работы.

В работе использованы графовые модели программ [12]:

- графы передач управления и информационные графы программ;

- графы зависимостей.

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

Научная новизна работы состоит в следующем:

- предложен способ преобразования циклических конструкций вычисления рекуррентных последовательностей, отличающийся от известных способов тем, что исходную зависимость вычисления элементов последовательности заменяют на совокупность зависимостей так, что циклические конструкции выполняются параллельно как последовательные независимые участки программы в нескольких потоках управления;

- предложен способ преобразования циклических конструкций, с использованием индексных множеств, который позволяет трансформировать исходный алгоритм программы в более эффективный с точки зрения времени его выполнения на вычислительной системе с общей памятью и аппаратной синхронизацией вычислений;

- предложена методика определения количества вычислительных устройств, необходимых для решения задачи на многопроцессорной системе кластерного типа за наименьшее время с учетом дополнения формулы. Амдала, что позволяет оценить влияние количества вычислительных устройств и коммуникационной среды, на время решения задачи.

Практическая ценность работы. Разработанные способы преобразования циклических конструкций при интегрировании их в системы оптимизирующей компиляции или специализированные программные комплексы по анализу и преобразованию пользовательских программ в соответствии с требованиями конкретных вычислительных систем позволят сократить время выполнения ряда программ. Разработанные способы не зависят от аппаратных платформ и языков реализации алгоритмов, что позволяет распространить их использование на максимально широкий класс процессорных архитектур и языков программирования.

На основании предложенной методики с точки зрения прикладных-, свойств задачи оценивается количество используемых вычислительных устройств, при которых достигается максимальное сокращение времени-, решения задачи, с целью выдвижения требований к архитектуре кластерной вычислительной системы.

Решение задачи преобразования циклических конструкций вычисления рекуррентных последовательностей и циклов с использованием индексных множеств, а также задачи определения оптимального с точки зрения времени решения задачи количества вычислительных устройств имеет существенное значение для повышения, эффективности использования ресурсов многопроцессорных систем кластерного типа.

Степень достоверности и обоснованности результатов.

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

Реализация и внедрение результатов работы.

При проведении исследования было разработано и реализовано программное обеспечение, содержащее алгоритм прикладной задачи преобразования информации, который заключается- в решении систем линейных уравнений и реализован с использованием вложенных циклических конструкций. Результаты работы были внедрены в изделия, разработанные в рамках ОКР на ФГУП "Пензенский научно-исследовательский электротехнический институт", о чем свидетельствует акт о внедрении, приведенный в приложении В. ю

Апробация результатов исследования.

Результаты работы докладывались на:

- VI Международной научно-технической конференции "Новые информационные технологии и системы" ("НИТиС-2004"), которая проводится Международной академией информатизации, Академией информатизации образования и Пензенским государственным университетом совместно с ОАО "ВолгаТелеком" (июнь 2004 г.);

- 5-й Международной конференции молодых ученых и студентов "Актуальные проблемы современной науки", которая проводится по инициативе Самарского государственного технического университета и Поволжской молодежной академии наук (сентябрь 2004 г.);

- X Всероссийской научно-технической конференции студентов, молодых ученых и специалистов "Новые информационные технологии в научных исследованиях и в образовании" (НИТ-2005), которая проводится Рязанской государственной радиотехнической академией-(апрель 2005 г.);

- Всероссийской научной конференции студентов, аспирантов и молодых ученых "Наука. Технологии. Инновации" (НТИ-2005), которая проводится Новосибирским государственным техническим университетом (декабрь 2005 г.);

- XI Международной открытой научной конференции "Современные проблемы информатизации в моделировании и программировании" (ноябрь 2005 г. - январь 2006 г.);

- XII Международной открытой научной конференции "Современные проблемы информатизации в проектировании и телекоммуникациях" (ноябрь 2006 г. - январь 2007 г.);

- V всероссийской научно-практической конференции студентов, аспирантов и молодых ученых "Молодежь и современные информационные технологии", которая проводилась на базе "Кибернетического центра" Томского политехнического университета (февраль - март 2007 г.);

- Седьмой Международной конференции-семинаре "Высокопроизводительные параллельные вычисления на кластерных системах", которая проводится Нижегородским государственным университетом (ноябрь 2007 г.).

Публикации.

По теме диссертации опубликовано 11 печатных работ, в том числе одна статья в издании, рекомендованном ВАК России.

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

Структура и объем работы.

Диссертация состоит из введения, четырех глав, заключения, списка использованных источников из 101 наименования и трех приложений. Работа содержит 131 страницу основного машинописного текста, 55 рисунков, 10 таблиц, 28 страниц приложений.

4.6 Выводы по главе

1. Получены экспериментальные значения времени решения прикладной задачи, заключавшейся в решении систем уравнений, на вычислительных системах кластерного типа, которые подтвердили сокращение времени решения задач пропорционально количеству вычислительных устройств, задействованных в многопроцессорных комплексах. В зависимости от программной реализации задачи и архитектуры вычислительной системы кластерного типа можно достичь сокращения времени вычислений пропорционально количеству вычислительных устройств.

2. Получены экспериментальные результаты, подтверждающие существование такого количества процессорных элементов, при котором время решения задачи наименьшее. В зависимости от объема задачи требуется разное количество вычислителей кластерной системы, причем последующее увеличение вычислительных устройств либо не уменьшает времени решения задачи, либо даже увеличивает его.

3. Спрогнозировано время выполнения алгоритма задачи решения систем уравнений при разных объемах обрабатываемой информации для вычислительных систем кластерного типа и оценены доля последовательных вычислений и доля операций передачи сообщений по коммуникационной среде, что позволило определить количество вычислительных устройств, при котором время решения задачи наименьшее. Время решения системы линейных уравнений из 1024 уравнений методом Га-усса-Жордана на пятнадцати вычислительных устройствах сокращается более чем в 10 раз относительно времени решения той же задачи на одном вычислительном устройстве.

4. Подтвеждена эффективность применения предложенной методики для стандартных и нестандартных программ, а также для специфических задач.

Заключение

В диссертационной работе были получены следующие результаты:

1. Проанализированы существующие преобразования программ, в частности преобразования циклических конструкций, в которых присутствуют зависимости данных, для многопроцессорных систем кластерного типа.

2. Предложен способ преобразования циклических конструкций вычисления рекуррентных последовательностей, то есть циклов вычисления элементов множества из значений предыдущих элементов этого же множества, отличающийся от известных способов тем, что исходную зависимость вычисления элементов последовательности заменяют на совокупность зависимостей, что позволяет ускорить выполнение циклических конструкций на многопроцессорной системе, так как полученные после преобразования независимые участки программы можно выполнять в нескольких потоках управления. Для рассмотренных в работе циклических конструкций время выполнения преобразованного программного кода сокращается пропорционально количеству используемых вычислительных устройств. При использовании двух процессоров одного узла кластерной системы время выполнения преобразованных циклических конструкций сокращается в два раза.

3. Предложен способ преобразования циклов с использованием индексных множеств, который позволяет трансформировать исходный алгоритм программы в более эффективный с точки зрения времени его выполнения на вычислительной системе с общей памятью и аппаратной синхронизацией вычислений. При использовании дополнительного объема памяти время выполнения циклических конструкций) с использованием индексного множества на системе с общей памятью с тремя или более вычислительными устройствами сокращается не менее чем на 20%.

4. Сформулированы основные критерии оценки параллельного вычислительного процесса, описано влияние его составляющих на время решения прикладных задач в параллельных системах, дополнена формула Амдала для многопроцессорных систем кластерного типа с учетом обмена сообщениями между узлами по коммуникационной среде.

5. Предложена методика определения количества вычислительных устройств, необходимых для решения задачи на многопроцессорной системе кластерного типа за наименьшее время с учетом дополненной формулы Амдала, позволяющая оценить влияние количества вычислительных устройств и характеристик коммуникационной среды на время решения задачи, а также долю последовательных операций в алгоритме по результатам экспериментов.

6. Получены экспериментальные значения времени решения прикладной задачи, заключавшейся в решении систем уравнений, на вычис1 лительных системах кластерного типа, которые подтвердили сокращение времени решения задач пропорционально количеству вычислительных устройств, задействованных в многопроцессорных комплексах. Определена зависимость времени выполнения задачи, заключающейся в решении систем уравнений, от ее размера при различном количестве используемых процессорных элементов.

7. Получены экспериментальные результаты, подтверждающие существование такого количества процессорных элементов, при котором время решения задачи наименьшее. Для задачи решения систем уравнений спрогнозировано время выполнения алгоритма при разных объемах обрабатываемой информации для вычислительных систем кластерного типа и оценены доля последовательных вычислений и доля операций передачи сообщений по коммуникационной среде, что позволило определить количество вычислительных устройств, при котором время решения задачи наименьшее. Время решения системы линейных уравнений из 1024 уравнений методом Гаусса-Жордана на пятнадцати вычислительных устройствах сокращается более чем в 10 раз относительно времени решения той же задачи на одном вычислительном устройстве.

1. Акулов О. А1., Медведев Н. В. Информатика: базовый курс: Учебник для студентов вузов, бакалавров, магистров, обучающихся по направлениям 552800, 65460 "Информатика и вычислительная техника" / O.A. Акулов, Н.В.Медведев. М.:.Омега-Л, 2004. - 552 с.

2. Амстронг (мл.), Дж. Секреты UNIX: 2-е изд.: Пер. с англ.: Уч. пос. -М!: Издательский дом "Вильяме", 2000. 1072 е., ил.

3. Андреев А., Воеводин Вл., Жуматий С. Кластеры и суперкомпьютеры — близнецы или братья? // Открытые системы. 2000. - № 5-6. -С.9-14.

4. Андрианов А.Н., Ефимкин К.Н., Задыхайло И.Б. Язык Норма. //ИПМ АН СССР. 1985. - Препринт № 165 - С. 1-34.

5. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологиии инструменты. М.: Вильяме, 2001. - 768 с. ■ ,»i *

6. Борзенко А. Суперкомпьютеры // Byte. — 2005. № 12.

7. Боэм Б. и др. Характеристики качества программного обеспечения: Пер. с англ. Е.К.Масловского. -М.: Мир, 1981.

8. Бурков В.Н., Заложнев А.Ю., Новиков Д.А. Теория графов в управлении организационными системами. -М.: Синтег, 2001. 124 с.

9. Вальковский В.А. Распараллеливание алгоритмов и программ. Структурный подход. М:: Радио и связь, 1989. - 176 е., ил.

10. Ю.Валях Е. Последовательно-параллельные вычисления: Пер. с англ. -М.: Мир, 1985.-456 е., ил.

11. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989. - 360 с.

12. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. -СПб.: БХВ-Петербург, 2004. 608 е.: ил.

13. Воеводин В.В. Суперкомпьютерная грань компьютерного мира Электронный ресурс.: http://www.storus.ru/education/parallel super6.htm Загл. с экрана.

14. И.Воеводин Вл. В. Суперкомпьютеры: вчера, сегодня, завтра // Наука и жизнь. 2000. - № 5. - С. 76-83.

15. Волков Д. Не всякая пальма первенства приносит плоды // Открытые системы. 2000. - № 7-8.

16. Лю Лян. Исследование эффективности параллельных вычислений на кластере Московского Энергетического Института (технического университета): автореферат дис. канд. техн. наук. М., 2007. — 20 с.

17. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. 2-е изд., перераб. и доп. - М.: Наука. Гл. ред. физ.-мат. лит. - 1987.-336 с.

18. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. М.: Радио и связь, 1983. - 272 е., ил.

19. Положительное решение на заявку №2006116411. Способ обработки трехкратно принятых комбинаций / Данилов Б.И., Мялицин В.В., Теркин И.М. Заявл. 12.05.2006; опубл. 27.11.2007.

20. Евреинов Э.В., Косарев Ю.Г. Однородные универсальные вычислительные системы высокой производительности. — Новосибирск: Наука, 1966.-308 с.

21. Изосимов A.B., Рыжко A.JI. Метрическая оценка качества программ. -М., МАИ, 1989.

22. Касперски К. Техника оптимизации программ. Эффективное использование памяти. — М.: BHV, 2003. 560 с.

23. Касьянов В.Н. Оптимизирующие преобразования программ. М.: Наука, 1988.-336 с.

24. Кениг Д., Штойян Д. Методы теории массового обслуживания: Пер. с нем. / Под ред. Г.П. Климова. М.: Радио и связь, 1981. - 128 е., ил.

25. Вальковский В.А. Распараллеливание циклов общего вида методом пирамид // Кибернетика. 1985. N 4. - С. 16-21.

26. Коваленко В.Н., Корягин Д.А. Вычислительная инфраструктура будущего // Открытые системы. — 1999. № 11-12. — С. 45-52.

27. Высокоскоростные вычисления. Архитектура, производительность, прикладные алгоритмы и программы суперЭВМ: Пер. с англ. /Под ред. Я.Ковалика. М.: Радио и связь, 1988. - 432 е.: ил.

28. Вальковский В.А. Параллельное выполнение циклов. Метод параллелепипедов // Кибернетика. — 1982. № 2. - С. 51-62.

29. Вальковский В.А. Параллельное выполнение циклов. Метод пирамид // Кибернетика. 1983. -№ 5. - С. 51-55.

30. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Изд-во "МЦНМО", 2001. - 960 с.

31. Кочур А. П. Супер-ЭВМ. М.: Знание, 1978. - 64 с.

32. Крюков В.А. Разработка параллельных программ для вычислительных кластеров и сетей // Информационные технологии и вычислительные системы. 2003. - №'1-2. - С. 42-59.

33. Кузин Л.Т. Основы кибернетики: В 2-х т. Т.2 Основы кибернетических моделей. Учеб. пособие для вузов. М.: Энергия, 1979. - 584 е., ил.

34. Кузьминский М., Волков Д. Современные суперкомпьютеры: состояние и перспективы // Открытые системы. — 1995. — № 6. — С. 33-40.

35. Кузьминский М., Мускатин A. Fast Ethernet в кластерах Beowulf // Открытые системы. 2001. - №7-8. - С. 17.

36. Сапронов А. Обзор некоторых пакетов измерения производительности кластерных систем. Электронный ресурс.: http://www.ixbt.com/cpu/clustering.shtml Загл. с экрана.

37. Легалов А. Построение параллельных алгоритмов // Открытые системы. 2004. - № 9. - С. 64-68.

38. Липаев В.В. Качество программного обеспечения. — М.: Финансы и статистика, 1983.

39. Любченко В. Параллельные сортировки: быстрее, проще. умнее // Открытые системы. 2004. - № 5.

40. Майерс Г. Искусство тестирования программ. — М.: Финансы и статистика, 1982.

41. Малышкин В. От последовательных вычислений к параллельным! Электронный ресурс.: http://www.sbras.nsc.ru/HBC/1999/ пЗ7/12l.html - Загл. с экрана.

42. Мастрюков М. Алгоритмы сжатия информации. Часть 7. Сжатие графической информации. // Монитор. 1994. — № 6. - С. 12-20.

43. Мялицин В.В. Методика определения оптимального количества процессоров кластерной системы: Материалы V всероссийской научно-практической конференции студентов, аспирантов и молодых ученых. Томск: Изд-во ТПУ, 2007. - 468 с. - С. 433^34.

44. Мялицин В.В. Параллельные вычисления в помехоустойчивом кодировании: Материалы всероссийской научно-технической конференции студентов, молодых ученых и специалистов. — Рязань: Изд-во РГРА, 2005.

45. Мялицин В.В. Тенденции развития языковых средств описания задач. Современные проблемы информатизации в моделировании и программировании: Сб. трудов. Вып. 11/ Под ред. д.т.н., проф. О.Я.Кравца.1

46. Мялицин В.В. Эффективность параллельных вычислений в помехоустойчивом кодировании: Материалы всероссийской научной конференции молодых ученых в 7-ми частях. Новосибирск: Изд-во НГТУ, 2006. - Ч. 2. - 250 с., - С. 62-64.

47. Мялицин В.В., Шашков Б.Д. Транспортная среда распределенных вычислений: Труды 5-й Международной конференции молодых ученых и студентов "Актуальные проблемы современной науки" Самара, 2004. -Ч. 18-Б - 108 с. - С. 22-24.

48. Мялицин В.В., Шашков Б.Д. Транспортная среда распределенных вычислений ЯОК8: архитектура и технология работы: Труды VI Международной научно-технической конференции Пенза: Изд-во ПГУ, 2004. - Ч. 1. - 268 е., ил. - С. 62-69.

49. Мялицин В.В., Шашков Б.Д. Эвристика определения оптимального количества процессоров кластерной системы // Научно-технические ведомости СПбГПУ. 2007. - № 3 - С.113—118.

50. Мялицин В.В., Шашков Б.Д. Эффективность параллельной реализации алгоритмов помехоустойчивого кодирования- Рида-Соломона //Прикладная информатика. 2006. - № 3 - С. 120-129.

51. Невдяев JI. Теория и практика цифровой обработки сигналов // Сети. 1998. -№ 7-8.

52. Носов В.А. Основы теории алгоритмов и анализа их сложности: Курс лекций. -М., 1992. 140 с.

53. Осмоловский С.А. Стохастические методы защиты информации. -М.: Радио и связь, 2003. 320 е.: ил.

54. Панкратьев С. Упаковка решает все. // Chip. 2003. - № 1.

55. Вычислительная техника в инженерных и экономических расчетах: Учеб. для вузов. 2-е изд., перераб. и доп. / Петров A.B., Алексеев

56. B.Е., Титов М.А. и др.; Под ред. A.B. Петрова. М.: Высш. шк., 1984 -320 е., ил.

57. Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984.-264 с.

58. Прангишвили И.В. и др. Параллельные вычислительные системы с общим управлением / И.В.Прангишвили, С.Я.Виленкин, И.Л.Медведев. М.: Энергоатомиздат, 1983. - 312 е., ил.

59. Робачевский А. Операционная система UNIX. СПб.: БХВ-Петербург, 2000. - 528с.: ил.

60. Русинович М. Возможности NTFS // Открытые системы. 2001. -№ 8. - С.31—35.

61. Саати Т.Л. Элементы теории массового обслуживания и ее приложения. М.: Изд-во "Советское радио", 1971. - 520 с.

62. Самойленко С.И. Помехоустойчивое кодирование. М.: Наука, 1966-240с.

63. Штейнберг Б .Я. Разбиение циклов для исполнения на суперкомпьютере со структурой перестраиваемого конвейера // Искусственный интеллект. Донецк, ДонДИШИ, Наука и Освита. 2002. - №3.1. C.331-338.

64. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.-455 е., ил.

65. Серебряный К.С. Методы высокоуровневой оптимизации циклов: дис. канд. техн. наук: 05.13.11 / Серебряный Константин Сергеевич. — М., 2004. 92 с. - Библиогр.: с. 83 - 88.

66. Скляр Б. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е испр.: Пер. с англ. М.: Издательский дом "Вильяме", 2003. — 1104 е.: ил. - Парал. тит. англ.

67. Спиряев О. Технологии защиты памяти в серверах HP // Byte.2005.-№8.-С. 58-63.

68. Математические модели и оптимизация вычислительных алгоритмов. Сборник трудов факультета вычислительной математики и кибернетики МГУ / Под ред. А.Н.Тихонова, А.А.Самарского М.: Изд-во МГУ, 1993.-254 с.

69. Химич А.Н., Попов A.B., Чистякова Т.В., Рудич О.В., Герасимова Т.А. Исследование блочно-циклических алгоритмов на семействе кластеров СКИТ // Проблемы программирования. Специальный выпуск.2006.-№2.-С. 177-183.

70. Филамофитский М. П. Система поддержки метакомпьютерных расчетов Х-СОМ: архитектура и технология работы // Вычислительные методы и программирование, том 5, N1. М.: Изд-во МГУ, 2004. — С.128—137.

71. Французов Д. Оценка производительности вычислительных систем // Открытые системы. 1996. - № 2. - С. 58-66.

72. Фролов A.B. Оптимизация размещения массивов в Фортран- программах на многопроцессорных вычислительных системах // Программирование. 1998. - № 3. - С. 70-80.

73. Хабибуллин Д. Сравнительный анализ архитектур систем параллельной обработки Электронный ресурс. : http://elics.ras.ru/info/ sei 4daq/ru/ 9.html Загл. с экрана.

74. Черноножкин С. Меры сложности программ (Обзор) // Системная информатика, № 5, Новосибирск: Наука, 1996, Вып. 5. с. 188-227.

75. Штейнберг Б.Я. Распараллеливание рекуррентных циклов с условными операторами // Автоматика и телемеханика1. — 1995. — № 9. — С.176-184.

76. Шнитман В. Системы Exemplar SPP1200 // Открытые системы. -1995.-№6.-С. 42-47.

77. Математическое "моделирование : Пер. с англ. / Под ред. Дж. Энд-рюса и Р.Мак-Лоуна. М.: Мир, 1979. - 277 с.

78. Мультипроцессорные системы и параллельные вычисления : Пер. с англ. / Под ред. Ф.Г. Энслоу. М.: Мир, 1976. - 383 е., ил.

79. Как ИТ-специалисты взяли международный банк, и что из этого вышло // Поиск. 2003. - № 5.

80. Официальный сайт проекта Beowulf Электронный ресурс. : http://www.beowulf.org Загл. с экрана.

81. Развитие архитектур баз данных// Открытые системы-1995.-№5.

82. Разработка оптимизирующих компиляторов для современных суперкомпьютеров Электронный ресурс. : http://parallel.ru/news/ kennedy compilers.html — Загл. с экрана.

83. Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре. Часть 1 // Кибернетика. — 1977. № 6. — С. 28-40.

84. Штейнберг Б.Я. Распараллеливание рекуррентных программных циклов // Информационные технологии. 2004. - № 4. - С. 16-23.

85. Blum W., Doallo R., Eigenmann R. Parallel programming with Polaris // Computer 1992. - Vol.29, N 12. - P. 78-82.

86. Dijkstra E. Go to Statement Considered Harmful//Commun. ACM. -1968. V.l 1, № 3, - p. 147-148.

87. Halstead M. Elements of Software Science/Elsevier, N.Y., 1977. (Русск. перевод: Холстед M.X. Начало науки о программах. М.: Финансы и статистика, 1981).

88. Kuck D.J., Kuhn R.H., Leasure В., Wolfe M. The structure of advanced retargetable vectorizer. Tutorial on Supercomputers: Designs and Applications. / K. Hwang New York: Ed. IEEE Press, 1984. - P. 163-178.

89. Lamport L. The Parallel Execution of DO Loops. // Communications of ACM, Number 2, Volume 17, 1974.

90. Lastovetsky A. mpC a Multi-Paradigm Programming Language for Massively Parallel1 Computers // CACM. - Volume 31, Number 2. - 1996. -P. 13-20.

91. Воеводин В. В. Математические модели и методы в параллельных процессах. — М.: Наука. 1986. - 296 с.

92. Yong Z., Jiahua Q. Dynamic Detection of Parallelism in PASCAL-like Program.

93. Евстигнеев В.А., Спрогис C.B. Векторизация программ // Векторизация программ: теория, методы, реализация. -М.:Мир,1991,- С.246-267.

94. Евстигнеев В.А., Мирзуитова И.А. Анализ циклов: выбор кандидатов на распараллеливание. Препринт № 58, ИСИ РАН, Новосибирск.: 1999.-41 с.

95. McCabe T.J., Butler C.W. Design Complexity Measurement and Testing. // Communications of ACM, Volume 32.