Ситкевич Т.А., Сюрин В.Н. Параллельные вычислительные среды

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

Министерство образования Республики Беларусь

УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

«ГРОДНЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМЕНИ ЯНКИ КУПАЛЫ»

Т.А.Ситкевич, В.Н.Сюрин

ПАРАЛЛЕ ЛЬНЫЕ

ВЫЧИСЛИТЕ ЛЬНЫЕ СРЕДЫ

Учебно-мет одическое пособие

по одноименному спецкурсу

для студентов специализации

Н 02.02.08 – Интеллектуальные системы

специальности Н 02.02.00 – Радиофизика

Гродно 2001

УДК 681(075.8)

ББК 32

Рецензенты: профе ссор, доктор технических наук

А.С.Ключников;

доцент, кандидат физико-математических

наук Н.Н.Иванов.

Рекомендовано советом физико-технического факуль тета ГрГУ.

Ситкевич Т.А., Сюрин В.Н.

Параллельные вычислительные среды:

П Уч.-метод. пособие – Гродно:ГрГУ, 2001. – 114 с.

УДК 681(075.8)

ББК 32

Аннотация

ВВЕДЕНИЕ

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

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

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

мирования, и новые концепции в технологии, архитектуре и

организации ЭВМ привели к созданию таких систем, способ-

ных выполнять большое число параллельных преобразов аний.

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

реальностью и б удет создано программное обеспечение, по-

зво ляющее достигнуть мак симального соотношения эффек тив-

ности и стоимости, они, несо мненно, дадут импу льс новым

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

стные методы и расширить об ласти прило жений. На сего дняш-

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

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

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

бы использова ть все преимущества предлагаемых параллель-

ных архитект ур, необходимо решить мног о сло жных проб лем

в об ласти язык ов программирования и компилят оров.

Спецкурс «Параллельные вычислительные среды» по-

священ изучению состояния дел в области систем парал-

лельной обработки информации, существующих методов

распараллеливания вычислений и параллельных алгорит-

мов вычислений, основных принципов построения ПВС и

программирования в них.

В течение последних 20-30 лет пристальное внимание

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

данных и теории сложности алг оритмов. Дело в том, чт о даль-

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

более быстрых ЭВМ станет со временем либо невоз мо жным,

либо эк оно мически невыго дным. Наиболее естественным тогда

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

ЭВМ. Имея р процессоров, мы мо ж ем по лучить значительное

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

р раз). Однак о после многих лет рабо ты и после того, как было

получено большое число превосх о дных теоретических рез у ль-

тат о в , параллельные вычисления триумфа не достигли. Основ-

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

1. Все реализованные параллельные системы применялись

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

ренним параллелизмо м». Так, например, систем а наб лю дения

РЕРЕ производит слежение за нек от орым к о личеством воздуш-

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

торой он рабо тает независимо от других процессоров и одно-

временно с ними. Но иссле дования пок азали, что таких зада ч

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

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

2. У ма тематик ов есть обыкнов ение при отсутствии у них

нужной ЭВМ создав а ть абстрак тную машину (теоретическу ю

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

лизации. К сожалению, такая абстрактная машина ок азывает-

ся непрактичной, поск ольк у теоретическая модель предпола-

гает, что все р процессоров связаны с общей памятью бо льшо-

го объема. Т еоретически всегда, когда два или более процессо-

ров запрашив ают из памяти одно и то же слово, они мгновен-

но его получают. Однак о практически это почти недостижи-

мо. На практик е по добные ситуации иногда приводят к стран-

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

снижала свою производительность при добавлении новых

процессоров. Кро ме того, в теоретической модели число про-

цессоров не ограничено. Это, конечно, было бы неплох о, по-

тому что, например, параллельное перемно ж ение дв ух матриц

размера n x n треб ует порядк а n

процессоров. При довольно

«скромно м» n =100 по требовался бы миллион процессоров.

3. В о дной из первых параллельных систем, ILLIAC-1V,

каждый подчиненный процессор (ПП) имеет свою «локаль-

ную память». К сожалению, между данными, записанными в

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

ти, при к о торых из 64 ПП работает только один, а остальные

бездейств ую т. Эт у ситу ацию можно назвать «вырождением па-

раллельности в последов а тельность», и попытки уменьшить

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

хом.

4. Дово льно важной целью распараллеливания вычисле-

ний является достижение надежности и жив учести. Надеж-

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

неисправный блок и отключить его. По д живучестью систе-

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

после отключения неисправного блок а. ILLIAC и аналогич-

ные ему системы не обладаю т ни тем, ни другим свойство м:

если некоторый блок вышел из строя, то система сможет про-

должить рабо ту только после ег о замены или ремонта.

Т аким образом, в насто ящее время существ у ет доста т о ч-

но много нерешенных проб лем и задач в об ласти создания па-

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

и других не достатков, и дов ольно интенсивные иссле дов ания

в это м на правлении продолжаются.

НЕОБХОДИМОСТЬ ПОСТРОЕНИЯ ПВС.

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

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

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

рах одновременно, т.е. необ ходимость создания ПВС мо жно

обосновать следующими основными целями: более высокое

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

и живучесть, мод у льность.

Прежде чем перейти непосредственно к параллельным си-

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

С момента появления ЭВМ в 1940 г. их быстро действие стре-

мительно в озрастало. К со жалению, по ддержива ть такие же тем-

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

труднее и все дороже . Простой рас чет показывает, что мы, по-

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

ки данных, достижимой на цифровых вычислительных маши-

нах, – это следу ет из основных физических зак онов. Т аким об-

разом, если мы хотим и дальше повышать быстродействие,

нельзя расс читыв а ть то лько на сокращение времени срабатыв а-

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

сигнала, необ х одимо найти др уг ое решение проблемы. О дно из

возмо жных направ лений – это иметь в системе неск о лько про-

цессоров, работающих параллельно. Эта идея не нова. Еще в

1842 г. Манабреа писал: «... машина мо ж ет ... выраба тывать не-

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

общее время вычислений» [1]. Это равносильно параллельнос-

ти, но, та к как в наше время придумано мног о терминов, связан-

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

более детальному обсуждению параллельных систем, разобра ть-

ся в этой терминологии.

Когда г оворят об универсальной ЭВМ, рабо тающей в усло-

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

те льность». Этот тер мин обозначает число различных и не свя -

занных между собой заданий, которое процессор способен об-

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

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

(но соответственно увеличится и стоимость системы). Заметим,

что, хотя установив р отдельных ЭВМ, мы и получим увеличе-

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

задания любог о по льзова теля заметно не изменится.

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

муль типрограммирование. Идея состоит в обработк е неско ль-

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

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

устройства ввода-выво да могут работа ть о дновременно. Несмот-

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

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

раммирования – у меньшить общее время обработки несколь-

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

циент повышения быстродействия (к.п.б.)» (speedup), мы хо-

тим знать, во ско лько раз уменьшится время обработки о дног о

от дельног о задания.

Для того, чт обы еще больше разграничить эти понятия, сто-

ит подчеркнуть разницу между терминами одновре менность

(concurrency) и паралле лиз м (parallelism). Одновременность оз-

начает, что в один и тот же момент времени происходят никак

не связанные между собой события; например, данные переда-

ются с диск а на пе чатающее устройство в то время, как на про-

цессоре идет нек о т орая программа. Обработк а же всех разрядов

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

о дной и той же программы, – это параллелизм.

Различают пространственный и временной параллелизм. В

перво м случае мы имеем, например, неск олько «географичес-

ки» разнесенных процессоров, одновременно работающих над

разными част ями одног о и того же задания. Примером в торог о

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

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

Основное внимание при исследов ании возмо жностей со-

здания ПВС и рассмо трении уж е существующих мы будем уде-

лять увеличению к.п.б. (а не произво дительности) при помощи

пространственного параллелизма, достигаемого ценой умерен-

ных за трат.

Рассмотрим теперь вопросы ст оимости. Пок а все выпуска-

емые на продажу процессоры были «из поро ды динозавров»,

об ъе динение нескольких таких машин в одну систему обходи-

лось слишк о м дорог о. Более того, это было невыго дно пот ому,

что к.п.б., как оказалось, совсем не обяза тельно увеличив ается

пропорционально увеличению стоимости оборудования. Дело

в том, что в каждый данный мо мент времени с х емы приоритета

предоставляю т доступ к некоторо му б лок у памяти т о лько одно-

му из процессоров, поэтому неко т орые процессоры будут вы-

нуждены жда ть (так назыв аемый «конфлик т по памяти»). В ре-

зу льтате к.п.б. увеличится менее чем в р раз, в то время как ст о-

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

экономически невыгодным.

Соотношение между однопроцессорными и му ль типроцессор-

ными системами по показа телю стоимость/произво дительность

изменилось с появлением мини-ЭВМ. Мини-ЭВМ (и тем более

микро-ЭВМ), т.е., по сути своей, современные персональные ком-

пью теры, оказались по крайней мере на порядок более эффек тив-

ными по стоимости, чем большие машины. Есть целый ряд оче-

видных соображений, об ъясняющих причины этог о явления:

1.Про до лжающееся совершенствование полупрово д-нико-

вой технологии б лаг оприятств ует разработк е небольших ЭВМ.

Создание устройств памяти на БИС и кристаллов с арифмети-

ческими и логическими сх ем ами резко снизило стоимость про-

изводства минимашин. Процессоры большого объем а, рабо та

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

пе чивающих ускорение арифметических операций, предвари-

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

перекрытием по времени и т.д., гораздо в меньшей степени при-

способлены для применения современной технологии БИС.

2. Экономик а крупном асштабног о произво дств а. Наклад-

ные расходы на одну ЭВМ при об ъеме производств а от 10

до

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

произво дстве 50-100 бо льших о днопроцессорных вычислитель-

ных систем в го д.

3. При существ ующей по литик е цен стоимость разработки

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

полностью поглощается ст оимостью аппара туры. Ст оимость как

аппара т уры, так и программног о обеспечения (что доро же) скла-

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

последнее время они зна чительно снизились. Кроме того, даже

в случае традиционных ЭВМ массовая продажа этих машин

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

пе чение. Что же касается параллельных систем, то их окупае-

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

серийно выпуск аемые устройства на БИС. Проведенный анализ

пок азал, что по показа телю производительность/ст оимость му ль-

типроцессорные ЭВМ в 3-4 раза превосх о дят о днопроцессор-

ные ЭВМ, построенные на той же техно логической базе. Одна-

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

сти памяти.

В наст о ящее время идет быстрый процесс сниж ения цен на

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

еще бо лее актуальными. Так, например, стоимость системы

РЕРЕ, имеющей столько процессоров, что по количеств у мил-

лионов операций в секунду она сравнялась с большой однопро-

цессорной CDC 7600, составляет всег о 10% от стоимости пос-

ледней [1]. Создав аемые в насто ящее время параллельные сис-

темы обработки данных разрабатыв аю тся на основе микропро-

цессоров или устройств на СБИС в рамках новейших техноло -

гий и б удут еще более эф фективными по своей ст оимости.

Теперь перейдем к обсуждению модульности. Еще одна

причина, по к о т орой ПВС эк ономически выг одны, состоит в

следующем. До недавнего времени ЭВМ покупались и устанав-

ливались как некие единые устройства. Всякий раз, когда возни-

кала необх о димость в бо льшей ЭВМ с бо льшим быстро действи-

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

нов ую. В то же время использов ание ПВС позволяет наращи-

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

свойств о системы мо жно назв ать «спосо бностью к инкре мент-

но му наращиванию» или мод ульностью. Таким образом можно

создавать конкретную архитек тур у, наибо лее отве чающую нуж-

дам пользов а теля.

Но самым важным преимуществом ПВС является не ее к.п.б.

и не стоимостная эффек тивность, а надежность и живучесть,

что особенно важно при использов ании в области управления

реальными процессами. Отказ в системе управления реальным

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

ствия, чем в случае отк аза ЭВМ, работающей в условиях вычис-

лительного центра: это – нар ушение безопасности лю дей, ог-

ро мный материальный ущерб и потеря жизненно важной ин-

форм ации. Поэтому в данно м случае о чень важно, чт обы систе-

ма постоянно нах одилась в рабо чем состо янии и правильно фун-

кционировала.

Однопроцессорная ЭВМ надежна ровно на столько, на

сколько надежна ее самая «у язвимая» часть. Кроме того, отказ

о днопроцессорной ЭВМ – это ка тастрофа, в то время как при

отказе одного из процессоров в ПВС оставшиеся процессоры

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

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

дительностью. При отключении некот орой части ПВС времен-

но для технического обслужив ания либо при обнаруж ении в ней

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

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

жения быстро действия. Более тог о, всегда, когда это возм о жно,

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

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

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

других отказоне уст ойчивых системах. В таких системах аппара-

тура удваивается или утраивается, и все резуль таты сравнивают-

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

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

тельно, уменьшается ст оимостную эффективность.

Произво дительность, стоимостная эффективность, надеж-

ность и живучесть ПВС тесно связаны между собой. Например,

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

авиа транспорта увеличивает ее надежность, поэто му плата за

обслуживание мож ет быть увеличена, хотя цену надежности

определить очень трудно. Увеличение быстродействия ЭВМ,

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

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

быстродействие имеет свою цену.

Т аким образо м, ПВС имею т ряд преимуществ, но заметно-

го прогресса в об ласти построения параллельных систем не на-

бл юдается. Причины, по которым ПВС не пользую тся особой

популярностью, заключаю тся в сле дующем:

1. Инженерное дело по самой своей приро де консерва тив-