Параллельные вычисления
 Скачать 1.75 Mb.
|
|
ой интервал (gap) между последовательными отправками или получениями сообщений в процессоре. • Р - число пар ‘процессор-память’. Единицей измерения времени является длительность основного цикла про- цессоров. Предполагается, что длина сообщений невелика, а сеть имеет ко- нечную пропускную способность. Модель LogP описывает свойства выполнения в коммуникационной сети, но абстрагируется от ее структуры. Таким образом она позволяет моделиро- вать взаимодействие в алгоритме, но не дает возможности промоделировать время локальных вычислений. Такое ограничение модели было принято по- - 17 - скольку, во-первых, при этом сохраняется простота модели и, во-вторых, ло- кальное (последовательное) время выполнения алгоритмов в процессорах не- сложно установить и без этой модели. Моделировать схемы из функциональных элементов с помощью парал- лельных машин с произвольным доступом (PRAM) позволяет теорема Брента ( * ). В качестве функциональных элементов могут выступать как 4 основных (осуществляющих логические операции NOT, AND, OR, XOR – от- рицание, логическое И, логическое ИЛИ и исключающее ИЛИ соответствен- но), более сложные NAND и NOR (И-НЕ и ИЛИ-НЕ), так и любой сложности. В дальнейшем предполагается, что задержка (propagation delay, т.е. время срабатывания – время, через которое предусмотренные значения сигналов появляются на выходе элемента после установления значений на входах) одинакова для всех функциональных эле- ментов. Рассматривается схема из функциональных эле- ментов (combinational circuit), состоящая из функциональных эле- ментов (combinational element), соединенных без образования циклов (предполагаем, что функциональные эле- менты имеют любое ко- личество входов, но ров- но один выход - элемент с несколькими выходами можно заменить не- сколькими элементами с единственным выходом), см. рис.1. Число входов определяет входную сте- пень (fan-in) элемента, а число входов, к которым подключен выход элемента - его выходной степенью (fan-out). Обычно предполагается, что входные степени всех используемых элементов ограничены сверху, выходные же сте- пени могут быть любыми. Под размером (size) схемы понимается количество элементов в ней, наибольшее число элементов на путях от входов схемы к * Кормен T., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. –М.: МЦНМО, 2001, -960 с. Рисунок 1 — Моделирование схемы размера 15, глубины 5 с двумя процессорами с помощью параллельной машины с произвольным доступом (PRAM - машина) - 18 - выходу элемента называется глубиной (depth) этого элемента (глубина схемы равна наибольшей из глубин составляющих ее элементов). Теорема Брента утверждает (доказательство в вышецитируемой работе), что при моделировании работы схемы глубиной d и размером п с ограничен- ными входными степенями элементов с использованием CREW-алгоритма на р процессорах достаточно (т.е. не выше) времени O(n/p+d). Выражение O(f) говорит, что скорость роста сложности алгоритма ограничена функцией f. На рис.1 приведен результат моделирования схемы размером (общее коли- чество процессоров) n=15 при глубине схемы (максимальное число элемен- тов на каждом из уровней глубины) d=5 с числом процессоров p=2 (одновре- менно моделируемые элементы объединены в группы прямоугольными об- ластями, причем для каждой группы указан шаг, на котором моделируются ее элементы; моделирование происходит последовательно сверху вниз в поряд- ке возрастания глубины, на каждой глубине по p штук за раз). Согласно тео- ремы Брента моделирования такой схемы на CREW-машине займет не более ceil(15/2+1)=9 шагов. Там же показано, что выводы Брента верны и для моделирования схем на EREW-машине (при условии, что выходные степени всех элементов также ограничены сверху). 1.2.3 Способы параллельной обработки данных, погрешность вычислений Возможны следующие режимы выполнения независимых частей про- граммы: • Параллельное выполнение - в один и тот же момент времени выполняется несколько команд обработки данных; этот режим вычислений может быть обеспечен не только наличием нескольких процессоров, но и с помощью конвейерных и векторных обрабатывающих устройств. • Распределенные вычисления – этот термин обычно применяют для указа- ния способа параллельной обработки данных, при которой используются несколько обрабатывающих устройств, достаточно удаленных друг от друга и в которых передача данных по линиям связи приводит к сущест- венным временным задержкам. При таком способе организации вычисле- ний эффективна обработка данных только для параллельных алгоритмов с низкой интенсивностью потоков межпроцессорных передач данных; таким образом функционируют, напр., многомашинные вычислительные комплексы (МВС), образуемые объединением нескольких отдельных ЭВМ с помощью каналов связи локальных или глобальных информаци- онных сетей. - 19 - Формально к этому списку может быть отнесен и многозадачный режим (режим разделения времени), при котором для выполнения процессов ис- пользуется единственный процессор (режим является псевдопараллельным, ибо реального ускорения выполнения не происходит); в этом режиме удобно отлаживать параллельные приложения (функционирование каждого процес- сора МВС имитируется отдельным процессом многозадачной ОС). Существует всего-навсего два способа параллельной обработки данных: собственно параллелизм и конвейерность [1-4]. Собственно параллелизм предполагает наличие p одинаковых устройств для обработки данных и алгоритм, позволяющий производить на каждом не- зависимую часть вычислений, в конце обработки частичные данные собира- ются вместе для получения окончательного результата. В это случае (пренеб- регая накладными расходами на получение и сохранение данных) получим ускорение процесса в p раз. Далеко не каждый алгоритм может быть успешно распараллелен таким способом (естественным условием распараллеливания является вычисление независимых частей выходных данных по одинаковым – или сходным – процедурам; итерационность или рекурсивность вызывают наибольшие проблемы при распараллеливании). Идея конвейерной обработки заключается в выделении отдельных эта- пов выполнения общей операции, причем каждый этап после выполнения своей работы передает результат следующему, одновременно принимая но- вую порцию входных данных. Каждый этап обработки выполняется своей частью устройства обработки данных (ступенью конвейера), каждая ступень выполняет определенное действие (микрооперацию); общая обработка дан- ных требует срабатывания этих частей (их число – длина конвейера) последо- вательно. Конвейерность (‘принцип водопровода’, акад. С.А.Лебедев, 1956) при вы- полнении команд имитирует работу конвейера сборочного завода, на кото- ром изделие последовательно проходит ряд рабочих мест; причем на каждом из них над изделием производится новая операция. Эффект ускорения дости- гается за счет одновременной обработки ряда изделий на разных рабочих местах. Ускорение вычислений достигается за счет использования всех ступеней конвейера для потоковой обработки данных (данные потоком поступают на вход конвейера и последовательно обрабатываются на всех ступенях). Кон- вейеры могут быть скалярными или векторными устройствами (разница со- стоит лишь в том, что в последнем случае могут быть использованы обраба- тывающие векторы команды). В случае длины конвейера l время обработ- ки n независимых операций составит 1 − + n l (каждая ступень срабатывает за единицу времени). При использовании такого устройства для обработки единственной порции входных данных потребуется время n × l и только для множества порций получим ускорение вычислений, близкое к l (именно в - 20 - этом проявляется свойственная конвейерным устройствам сильная зависи- мость производительности от длины входного набора данных). Производительность E конвейерного устройства определяется как ( ) ⎥⎦ ⎤ ⎢⎣ ⎡ × − + + = = n t n E τ σ τ 1 1 l , (1) где n – число выполненных операций, t – время их выполнения, τ - время такта работы компьютера, σ - время инициализации команды. Из рис.2 видно, что производительность конвейера асимптотически растет с увеличением длины n набора данных на его входе, стремясь к теоретиче- скому максимуму производительности τ 1 На основе реализации конвейера команд были созданы известные конструкции - со- ветская ЭВМ БЭСМ-6 (1957 ÷ 1966, разра- ботка Института Точной Механики и Вы- числительной Техники АН СССР - ИТМВТ) и английская машина ATLAS (1957 ÷ 1963); арифметический конвейер наиболее полно воплощен в cуперкомпью- тере CRAY-1 (1972 ÷ 1976), [7]. Существует ILP (Instruction Level Paral- lelism)-класс архитектур, характерным признаком которых является параллель- ность на уровне команды [4], к этому клас- су относятся суперскалярные и VLIW-процессоры. IPL-системы реализуют скрытый от пользователя параллелизм. Система команд суперскалярных процессоров не содержит указаний на (возможную) параллельность в обработке, обеспечить динамическую загруз- ку параллельных программ призваны компилятор и аппаратура микропро- цессора без вмешательства программиста. Архитектура современных микро- процессоров (типичный пример – процессоры серии DEC Alpha) изначально спроектирована в расчете на выполнение как можно большего числа инст- рукций одновременно (в некоторых случаях в порядке, отличном от исход- ной последовательности в программе; причем переупорядочение может быть выполнено и транслятором). Дальнейшим развитием суперскалярной архи- тектуры является мультитредовая, в соответствие с которой программа раз- Рисунок 2 — Производительность конвейерного устройства в функции длины входного набора данных - 21 - бивается (аппаратными и программными средствами) на совокупность тре- дов (единиц обработки информации – частей программы, исполнению кото- рых соответствует непрерывная область динамической последовательности инструкций); тред выполняется определенным процессорным элементом (со- ставной частью мультитредового процессора) параллельно с другими треда- ми [4]. Мультитредовые процессоры уже выпускаются – напр., сетевой мик- ропроцессор IPX1200 (фирма Level One, http://www.level1.com ), MTA (компа- ния Tera, http://www.tera.com ), кристалл для проекта Blue Gene петафлопного суперкомпьютера (фирма IBM). Архитектура сверхдлинного командного слова (VLIW - Very Long Instruc- tion Word) берет свое начало от параллельного микрокода, применявшегося еще на заре вычислительной техники, а также от суперкомпьютеров Control Data CDC6600 и IBM 360/91. VLIW-команды включают несколько полей (не- которые могут быть пустыми), отвечающих каждое за свою операцию, при- чем все они выполняются в едином цикле. В начале 70-х г.г. многие вычис- лительные системы оснащались дополнительными векторными сигнальными процессорами, использующими VLIW-подобные длинные инструкции, про- шитые в ПЗУ (обычно для выполнения быстрого преобразования Фурье и подобных вычислительных алгоритмов). Первыми настоящими VLIW-компьютерами стали мини- суперкомпьютеры, выпущенные в начале 80-х г.г. компаниями MultiFlow, Culler и Cydrome (опередившие свое время модели не имели коммерческого успеха). VLIW-компьютер компании MultiFlow 7/300 использовал два ариф- метико-логических устройства для целых чисел, два АЛУ для чисел с пла- вающей точкой и блок логического ветвления. Его 256-битное командное слово содержало восемь 32-битовых кодов операций. Модули для обработки целых чисел могли выполнять две операции за один такт 130 нсек, что при обработке целых чисел обеспечивало быстродействие около 30 MIPS. Можно было также комбинировать аппаратные решения таким образом, чтобы полу- чать или 256-битные или 1024-битные вычислительные машины. VLIW- компьютер Cydrome Cydra-5 использовал 256-битную инструкцию и специ- альный режим, обеспечивающий выполнение команд в виде последователь- ности из шести 40-битных операций, посему его компиляторы могли генери- ровать смесь параллельного кода и обычного последовательного. Еще один пример машин с VLIW-архитектурой – компьютер AP-120B фирмы Floating Point System (к 1980 г. было поставлено более 1’600 экземп- ляров, [1]). Команда AP-120B имела длину 64 разряда (6 групп, соответст- вующих 16-битной целочисленной арифметике, ‘плавающим’ вычислениям, управлением вводом/выводом, командам перехода и работы с оперативной памятью) и выполнялась за 167 нсек. Естественно, последовательность столь сложных команд генерируется специальным ‘высокоинтеллектуальным’ компилятором, выявляющим параллелизм в исходной программе и генери- - 22 - рующим VLIW-инструкции, отдельные поля которых могут быть выполнены независимо друг от друга (фактически параллельно). Необходимо упомянуть отечественные разработки – параллельную вычис- лительную машину М-10 (1973) и векторно-конвейерную М-13 (1984) М.А.Карцева (Научно-исследовательский институт вычислительных ком- плексов - НИИВК). Научной основой диссертации на соискание ученой степени доктора технических наук М.Карцева явилась создание первого этапа (1969 г.) СПРН (Системы Предупре- ждений о Ракетных Нападениях ), для чего многие десятки машин cсерии М4 были объединены в работавшую в реальном масштабе времени единую вычислительную сеть каналами длиною в тысячи километров (что, пожалуй, труднодоступно и совре- менному InterNet’у). На авторитетном совещании в конце 60-х г.г. рассматривалась перспективность двух подходов к созданию суперкомпьютеров – акад. С.А.Лебедев отстаивал однопроцес- сорный вариант максимального быстродействия (система ‘Эльбрус’), М.Карцев про- двигал многопроцессорную систему M-10 (полностью параллельная вычислительная система с распараллеливанием на уровнях программ, команд, данных и даже слов); акад. В.М.Глушков поддержал оба направления. Еще в 1967 г. М.Карцев выдвинул идею создания многомашинного комплекса ВК М-9 (проект ‘Октябрь’), построенного из вычислительных машин, специально разра- ботанных для совместной работы именно в таком комплексе; исследования показали, что производительность комплекса может достигнуть 10 9 операций в секунду (в то время заканчивалось проектирование БЭСМ-6 с производительностью 10 6 операций в секунду). Такая производительности достигалась разработкой новой структуры вычис- лительных машин – обрабатывались не отдельные числа, а группы чисел, представ- ляющие собой приближенные представления функций либо многомерные векторы. M- 10 разрабатывалась для СПРН и для общего наблюдения за космическим пространст- вом, однако М.Карцев добился разрешения на публикацию материалов о М-10. По его инициативе на М-10 были проведены особосложные научные расчеты по механике сплошной сред ы (в десятки раз быстрее, чем на ЕС-1040), впервые в мире получены данные по явлению к о ллапса в плазме (чего не удалось сделать учёным США на мощ- нейшей в то время CDC-7600). Важным этапом развития отечественных супер-ЭВМ является проект ‘Эльбрус-3’ (1991) и его современное развитие - процессор E2k (‘Эльбрус- 2000’, Б.А.Бабаян, http://www.elbrus.ru ), который является определенным эта- пом развития VLIW-технологии. Близка к описываемым подходам и совре- менная технология EPIC (Explicitly Parallel Instruction Computing), реали- зующая принципы явного параллелизма на уровне операций и широком ко- мандном слове (пример - разрабатываемый фирмами Intel и Hewlett Packard проект Merced и одна из его реализаций – процессор Itanium). Исключительно интересной (и почти забытой сейчас) является ‘модуляр- ная ЭВМ’ (использующая принципы системы счисления остаточных классов - СОК), построенная в начале 60-х г.г. для целей ПРО (И.Я.Акушский, Д.И.Юдицкий и Е.С.Андрианов) и успешно эксплуатирующаяся более 40 лет. - 23 - В СОК каждое число, являющееся многоразрядным в позиционной системе счисле- ния, представляется в виде нескольких малоразрядных позиционных чисел, являющих- ся остатками от деления исходного числа на взаимно простые основания. В традицион- ной позиционной двоичной системе выполнение операций (напр., сложение двух чи- сел) производится последовательно по разрядам, начиная с младшего; при этом обра- зуется перенос в следующий старший разряд, что определяет поразрядную последова- тельность обработки . Сама сущность СОК подталкивает к распараллеливанию этого процесса: все операции над остатками по каждому основанию выполняются отдельно и независимо и, из-за их малой разрядности, очень быстро. Малая разрядность остатков дает возможность реализовать табличную арифметику, при которой результат опера- ции не вычисляется каждый раз, но, однажды рассчитанный, помещается в запоми- нающее устройство и при необходимости из него считывается. Т.о. операция в СОК при табличной арифметике и конвейеризации выполняется за один период синхронизи- рующей частоты (машинный такт). Табличным способом в СОК можно выполнять не только простейшие операции, но и вычислять сложные функции, и также за один ма- шинный такт. В СОК относительно просто ввести функции контроля и исправления ошибок в процессе вычисления арифметических операций (особенно важно для рабо- тающих в критичных условиях ЭВМ). Модул |