Всеволод Сергеевич Бурцев Параллелизм вычислительных процессов и развитие архитектуры суперэвм м, 1997

1. 
   Johnson G.M. Exploiting Parallelizm in Computational Science. North-Holland, Future Generation Computer Systems, 1989, 5, pp 319-337.
   
2. 
   Van der Steen Aad J. Overview of Recent Supercomputers. The Netherlands, Academic Computing Centre Utrecht, 1994, 47 p.
   
3. 
   Бурцев B.C. Система массового параллелизма с автоматическим распределением аппаратных средств суперЭВМ в процессе решения задачи. Юбилейный сборник трудов институтов Отделения информатики, вычислительной техники и автоматизации РАН, Москва, 1993, том II, стр 5-27.
   
4. 
   Бурцев B.C. Тенденции развития высокопроизводительных систем и многопроцессорные вычислительные комплексы. Москва, 1977, 28 стр. (Препринт ИТМ и ВТ АН СССР)
   
5. 
   Бурцев B.C., Кривошеев Е.А., Асриэли В.Д., Борисов П.В., Трегубое К.Я. Векторный процессор МВК "Эльбрус-2". СуперЭВМ, 1989, сборник научных трудов ОВМ АН СССР.
   
6. 
   Отчет по ОСВМ. ВЦКП РАН, 1992.
   

В.С.Бурцев

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

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

Как известно [1], для решения целого ряда проблемных задач требуется производительность 10¹¹-10¹³ оп/с при работе с общей оперативной памятью объемом в 10⁹-10¹⁰ слов. При современном состоянии развития вычислительной техники для решения этих задач потребуется сотни параллельно работающих процессоров.

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

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

Попробуем на базе имеющихся в настоящее время общеизвестных суждений и эмпирических данных создать некую систему качественных сравнительных оценок вычислительных средств в интересах как системных программистов, так и программистов-пользователей. В настоящее время в промышленном выпуске существуют всего три архитектуры вычислительных средств: однопроцессорные машины, включая векторные конвейерные; многопроцессорные системы и многомашинные вычислительные комплексы [2]. В первую очередь дадим сравнительные оценки основных особенностей трех структур. Безусловно, с точки зрения простоты загрузки этих структур однопроцессорные машины имеют неоспоримое преимущество перед остальными. Действительно, и последовательные, и параллельные алгоритмы вычислительных процессов без особой изобретательности программиста достаточно эффективно выполняются на однопроцессорных машинах. Исключение составляют векторные конвейерные системы, для которых необходимо, чтобы количество параллельных вычислительных процессов выполняемой задачи, включая векторные, было больше коэффициента конвейеризации системы Ск, где Ск - глубина конвейеризации системы, измеряемая числом команд, одновременно находящихся в системе и выполняющихся на различных уровнях ее конвейера.

Для загрузки многопроцессорной системы к алгоритму необходимо предъявить определенные требования параллелизма вычислительного процесса, а именно: количество параллельно выполняемых процессов Р должно быть больше числа параллельно работающих процессоров системы на протяжении всего времени выполнения задачи. Необходимо отметить, что обмен данными между процессами в этих системах происходит посредством обычного обращения процессоров к общему ОЗУ, а общая синхронизация по данным реализуется на уровне специальных команд [3].

29




В.С.Бурцев. Новые подходы к оценке качества вычислительных средств

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

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

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

Так, для однопроцессорных машин такими параметрами являются производительность процессора (Ппр), пропускная способность канала процессор-ОЗУ (Епр), объем ОЗУ (Q) и пропускная способность ОЗУ-внешняя память Е (последняя ограничивается в основном скоростью внешней памяти). Максимальная производительность однопроцессорной машины, как правило, ограничивается частотными характеристиками используемой элементной базы и соединений. Как правило, для всех систем выполняется следующее соотношение: Ппр=RЕпр, где R - процент обращений процессора к ОЗУ из всех обращений его за данными. Подразумевается, что большая часть обращений за данными идет в сверхоперативную память процессора (быстрые регистры, КЭШ и т.д.).Учитывая, что среднее число обращений за данными на одну операцию равно 2, а процент обращений к ОЗУ колеблется от 0,8 до 0,98 в зависимости от структуры задачи, можно с достаточной для наших рассуждений точностью считать Ппр=Епр, где Ппр имеет размерность Mflops, a Епр - MB/s. Поэтому, если мы не располагаем значениями Епр, можно определять их через Ппр. Производительность векторных конвейерных процессоров в дополнение к этому зависит от глубины конвейеризации, реализованной в процессоре. Опыт конструирования этих процессоров и анализ реальных задач показывает, что увеличение производительности процессора за счет конвейеризации не выше одного порядка.

Многопроцессорная система имеет следующие основные параметры: число процессоров N, производительность процессора Ппр, пропускная способность коммутатора между процессорами и ОЗУ Ек, пропускная способность ОЗУ-внешняя память Е. Во многих случаях Ек = NEnp = NПпр

30

31

Епр/Е ≤ Ко при объеме памяти ОЗУ Q, (1)

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

Действительно, если неравенство (1) не выполняется, то через определенное время производительность однопроцессорной машины будет определяться не величиной Епр, а Е, то есть пропускной способностью внешних устройств. Для того, чтобы этого не случилось, программист должен разбивать задачу на такие локальные части, для которых в объеме ОЗУ, равном Q, средний процент переиспользования адресов локальной части задачи, подкаченной в ОЗУ, превосходил величину Ко. Назовем величину Ко коэффициентом локализации. Естественно, чем больше объем памяти однопроцессорной машины Q, тем легче выполнить это требование. Поэтому условия выполнения неравенства (1) должны зависеть определенным образом от объема оперативной памяти. Примем некоторый объем ОЗУ Од, определенный практикой, за достаточный для локализации данных в ОЗУ. В этом случае для машин с памятью Q, меньшей Qд, усложняется проблема локализации данных, что может быть учтено соотношением (Qд/Q + 1), уточняющим неравенство (1):

Епр (Qд/Q + 1)/Е≤Ко (2)

В многопроцессорных системах условия обеспечения процессоров данными описывается подобным соотношением, в котором Епр заменяется величиной пропускной способности коммутатора процессоров - ОЗУ Ек (Ек = NEnp = NПпр). Предполагается, что все N процессоров имеют равную производительность Ппр и пропускную способность Епр. Тогда:

Кмп ≥ Ек (Qд/Q + 1)/Е

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

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

Р≥ N,

где Р - число параллельно выполняемых процессов.

32

В.С.Бурцев. Новые подходы к оценке качества вычислительных средств

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

Рис.1. Схема узла Cray T3D.

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

Кму ≥ NyEпp (Qд/Qy + 1)/Еу

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

Ny - количество процессоров в узле,

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

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

33

Рис.2. Схемы коммутации микропроцессоров в многомашинных комплексах.

В настоящее время реализованы следующие системы связей в многомашинных комплексах: "точка-точка", плоская матрица, трехмерная коммутация и система связей "гиперкуб" (Рис.2). Возможной характеристикой топологии связи может быть параметр, определяющий среднее число узлов передачи информации от узла к узлу. Так для системы "точка-точка" этот параметр b равен 1,

34

В.С.Бурцев Новые подходы к оценке качества вычислительных средств

для транспьютерных связей b= 1/2 (рассматриваются транспьютерные

замкнутые системы), для трехмерной коммутации b = 3/4 (Cray T3D и Т3Е), для гиперкуба b= l/2 1og₂N (Ncube 2). Для конкретных систем эти формулы могут несколько корректироваться, однако порядок зависимости параметра b от N останется тем же, и при сравнении многомашинных комплексов он должен быть учтен в определении величины Еу. В этом случае неравенство (2) уточниться следующим образом:

Кму ≥ NyEnp b (Qд/Qy + 1)/Еу (3)

Условие загрузки многомашинного комплекса при взаимодействии с внешней памятью может быть описано следующим соотношением:

Км ≥ Емк (Qд/Qм +1)/E,

где Емк - пропускная способность всех коммутаторов системы, которая может определяться суммарной производительностью комплекса Пм = NПпp = NEпp, Qm - общий объем памяти комплекса, Qм = NQy. Условие загрузки многомашинного вычислительного комплекса при обеспечении требуемого уровня параллелизма вычислительного процесса совпадает с аналогичным условием для многопроцессорного комплекса:

Р > N

35

В.С.Бурцев. Новые подходы к оценке качества вычислительных средств

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

Практика использования вычислительных средств выявила следующую закономерность соотношения объема памяти и производительности системы Q_п, которая сохраняется на протяжении всего времени существования дискретных вычислительных средств - на каждый миллион операций в секунду приходится порядка 100 тысяч слов памяти (≈ 0.5 MB). Естественно, чем больше память, тем удобнее программировать задачу и повышать загрузку процессоров. Поэтому можно ввести специальный коэффициент, учитывающий достаточность памяти: в однопроцессорной машине Коп = 0,5 Ппр/Q + 1; в многопроцессорной системе Кмпп = 0,5NПпp/Q + 1; для многомашинного комплекса Кммп = 0,5Пм/Qм + 1. В этих соотношениях Ппр имеет размерность Mflops, а память Q и Qm - MB.

В Таблице 1 приведены все соотношения, по которым могут быть дополнительно оценены комплексы с точки зрения возможности их эффективного использования на разнообразных задачах пользователя. Другими словами, эти соотношения характеризуют сложность программирования на тех или иных системах, имея в виду, что всегда есть стремление достичь максимальной производительности вычислительных средств на решаемой задаче. Чем меньшие значения имеют правые части этих соотношений, тем легче выполнить условие полной загрузки системы. Произведение этих коэффициентов может дать качественную характеристику всего комплекса по эффективности его использования на различных классах задач. Для такой интегральной оценки необходимо правильно выбрать значения Qд и Пэт, так как они могут влиять на весовые характеристики этих коэффициентов. Анализ решения больших задач показывает, что для многих из них локализация данных во многих случаях может быть выполнена на объеме памяти Qд = 1 GB. Величина Пэт, как уже говорилось, может быть выбрана исходя из средней производительности процессора сегодняшнего дня lGFlops.

Приведенные оценки качества вычислительных комплексов указывают только возможные принципы нового подхода к анализу вычислительных средств при их выборе для использования в тех или иных сферах деятельности. Неполнота приведенных соотношений заключается прежде всего в том, что при определении пропускной способности канала процессор - ОЗУ не учитываются особенности построения сверхоперативной памяти (быстрые регистры, КЭШ, различные буферные устройства и т.д.). При определении пропускной способности между ОЗУ и внешней памятью не учитываются реальные возможности внешних устройств и телекоммуникационных систем, выходящих на вычислительные средства, и т.д. Однако, принципы развития и уточнения этих оценок достаточно ясны и могут быть без труда найдены для каждого конкретного случая.

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

36




В.С.Бурцев. Новые подходы к оценке качества вычислительных средств

фирмами. В качестве примера приведем анализ некоторых современных многопроцессорных систем и многомашинных комплексов.

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

Рис.3. Структурная схема сервера AlphaServer 8400.

Примером последней структуры может служить многопроцессорный комплекс SPP-1200 фирмы Convex при коммутации микропроцессоров внутри кластеров (Hypernode) (Рис.4).

Рис.4. Структурная схема узла SPP 1200 фирмы Convex.

37

В.C.Бурцев. Новые подходы к оценке качества вычислительных средств

Многомашинные комплексы также отличаются структурой коммутатора: комплекс SP-2 имеет структуру коммутатора типа "точка-точка"; транспьютерные системы, выпускаемые НПО "Квант" (Россия) - структуру типа матрицы; в Cray T3D и ТЗЕ коммутатор организован по принципу трехмерного торроидального куба; а NCube 2 - по структуре гиперкуба. Особенности коммутации этих многомашинных комплексов в наших соотношениях учитываются коэффициентом b (Рис.2).

Результаты анализа многопроцессорных систем фирмы Convex (SPP-1200, SPP-2000), фирмы DEC (Server8400) и фирмы Cray (j916, C-90 и Т-90) приведены в Таблице 2.

Таблица 2. Многопроцессорные системы (распределяемая память)

Аналогичные данные для многомашинных комплексов сведены в Таблице 3. Таблица 3. Многомашинные комплексы (распределенная память)

Из таблиц видно, что каждая фирма хорошо чувствует недостатки своей системы и при последующей реализации устраняет их, улучшая тем самым оценочные коэффициенты. Так, фирма Convex улучшила обмен к ОЗУ кластера с внешней памятью и каналами телекоммуникации и увеличила производительность процессора. Фирма Cray существенно увеличила объем ОЗУ в узле,