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

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

1. 
   Предлагаемые дополнительные оценки различных архитектур вычислительных средств достаточно чутко реагируют на отклонения тех или иных систем и комплексов в сторону их специализации и дает возможность выявить диспропорцию в архитектуре вычислительных средств. Этим дополнительным тестом можно пользоваться как при выборе вычислительных средств, так и при их разработке.
   
2. 
   Анализ существующих архитектур говорит о том, что многомашинные вычислительные комплексы не способны решить целый ряд проблемных задач, требующих производительности в 10¹² и выше операций в секунду и оперирующих с большими объемами общих данных. Практически достаточная загрузка выходит за рамки человеческих возможностей. Многопроцессорные комплексы хотя и обеспечивают возможность обращения к общему ОЗУ, однако количество процессоров в этих комплексах имеет принципиальное физическое ограничение, не говоря уже о том, что загрузка таких комплексов с точки зрения синхронизации процессов, работающих с общими данными, представляется чрезвычайно сложным для программиста [2]. Все это говорит о том, что развитие вычислительных средств на базе фон-Неймановского принципа организации вычислительного процесса в настоящий момент претерпевает определенный кризис.
   
3. 
   Приведенный анализ вычислительных средств свидетельствует о том, что единственным эффективным путем дальнейшего развития вычислительных средств в направлении повышения их производительности является путь существенного увеличения производительности процессора (Ппр). Именно за счет увеличения этого параметра Cray T90 имеет наилучшие показатели.
   
4. 
   В то же самое время просматривается определенное насыщение в схемотехнических средствах проектирования микропроцессоров, состоящее в том, что при увеличении числа логических элементов (вентелей), в микропроцессорах не наблюдается пропорционального прироста его производительности или коэффициент прироста производительности существенно уменьшается [4].
   

1. 
   В.С.Бурцев. "О необходимости создания супер-ЭВМ в России" (в данной книге).
   
2. 
   В.С.Бурцев. "Система массового параллелизма с автоматическим распределением аппаратных средств суперЭВМ в процессе решения задачи". Юбилейный сборник трудов институтов ОИВТА РАН. М. 1995, т.2, с. 5-27.
   
3. 
   В.С.Бурцев. "Принципы построения многопроцессорных вычислительных комплексов "Эльбрус". М. 1977, ИТМиВТ, препринт N1.
   
4. 
   Ю.Затуливетер. " Компьютерные архитектуры: неожиданные повороты". HARD V SOFT. M. 1996, N 2, с. 89-94.
   

B.C. Бурцев

Построенная по принципу фон-Неймана однопроцессорная ЭВМ на скалярных операциях может достичь производительности 10⁸ оп/с, а на векторных -10⁹оп/с (Рис.1).

41

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

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

Процессор

Рис.1 Однопроцессорный комплекс.

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

Все это дает возможность при передовой современной технологии достичь максимальной производительности комплекса 10¹⁰ - 10¹¹ оп/с. Однако реальная его производительность, как правило, не превышает 10¹⁰ оп/с.

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

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

42
В.С.Бурцев. Выбор новой системы организации выполнения высокопараллельных вычислитель-ных процессов, примеры возможных архитектурных решений построения суперЭВМ

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

Рис.2 Многопроцессорный комплекс.

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

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

43

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

имеющие общую операционную систему для всех процессоров и памяти, называют многопроцессорными. Частным случаем этих двух архитектур являются однопроцессорные комплексы, иногда называемые машинами. Однопроцессорные комплексы могут включать в свою структуру векторные исполнительные устройства (например, CRAY 1). Таким образом, мы будем рассматривать три основные структуры вычислительных комплексов: однопроцессорные, многопроцессорные, многомашинные (Рис.1, 2, 3).

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

Постановку сложной задачи на суперЭВМ можно разбить на следующие взаимосвязанные этапы работ:

1. 
   Физическая постановка задачи.
   
2. 
   Выбор математического метода решения задачи.
   
3. 
   Разработка численных методов решения задачи.
   
4. 
   Программирование.
   

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

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

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

Проанализируем архитектуры различных суперЭВМ в отношении требований, предъявляемых к программам, разрабатываемым на четвертом этапе (Рис.1, 2, 3).

44

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

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

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

К > E₁/Е₂, где:

E₁ - средняя пропускная способность канала между процессорами и оперативной памятью;

Е₂ - средняя пропускная способность канала между оперативной и внешней памятью;

К - коэффициент локализации данных программы в объеме оперативной памяти, равном Q, или средний коэффициент переиспользования адресов данных в объеме оперативной памяти, равном Q на интервале ∆t (Рис.1).

На любом интервале времени At это неравенство должно удовлетворяться.

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

Принимая во внимание, что Е₂ ограничено возможностями внешних устройств и в перспективе будет достигать 1-10 млн. слов в секунду (в настоящее время 0,1-1 млн. слов в секунду) при производительности процессора в 1-10 млрд. слов в секунду, коэффициент К измеряется сотнями единиц. Поэтому указанное неравенство обеспечивается, как правило, только при больших объемах оперативной памяти, что требует, даже на однопроцессорном комплексе, немалой изобретательности программиста, а иногда и пересмотра первого, второго и третьего этапов постановки задачи.

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

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

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

d = b+c/k

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

1. 
   у = +,b,с;
   
2. 
   d = /,y,k.
   

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

Гораздо хуже обстоит дело с этой проблемой в многопроцессорных и многомашинных системах. Так, если в приведенном выше примере простые переменные b и с заменить на функции В и С, общие данные которых расположены в областях X и У, и предположить, что функции В и С могут параллельно выполняться на разных процессорах, вопрос о том, в какой временной последовательности функции В и С работали с общими данными, становится неопределенным. Синхронизация во времени этих двух вычислительных процессов осуществляется программистом при помощи специальных команд или операторов более высокого уровня. Обычно дело обстоит так, что, ужесточая синхронизацию процессов, программист, работающий на четвертом этапе, снижает параллелизм вычислений, а ослабляя синхронизацию процессов, увеличивает вероятность искажения вычислительного процесса. Кроме искажения счета в приведенном простом примере имеется возможность и полной блокировки вычислительного процесса. Так, если программа В, работая с данными X, обратилась к данным в области У в момент t₁, а программа С, работая с данными У с момента t₂, обратилась к данным X в момент t₃, где t₃>t₁>t₂, то программа В ждет данных X, а программа С - данных У, т.е. вычислительный процесс блокирован. В случае t₂>t₁ процесс прошел бы нормально.

46

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

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

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

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

В многомашинных комплексах требования постановки задачи несколько отличаются. Дело в том, что взаимодействие процессоров в многопроцессорном комплексе можно реализовать практически мгновенно - процессоры между собой могут взаимодействовать через канал чрезвычайно большой пропускной способности (процессор - оперативная память), где для временной синхронизации обмена используется оперативная память комплекса. В многомашинном комплексе вся задача размещается по N отдельным устройствам оперативной памяти каждого процессора (Qэbm), а взаимодействие между данными осуществляется по межмашинным связям. Даже в том случае, если бы удалось реализовать межмашинные связи каждой ЭВМ с каждой, задачу полного обмена информацией между ЭВМ можно было бы осуществлять в N раз медленнее, чем этот же обмен между оперативной памятью и процессором, суммарная производительность которого равна производительности всех ЭВМ многомашинного комплекса. Считается, что пропускная способность канала одной ЭВМ в словах не может быть больше производительности ее процессора (Рис.3).

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

47

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

Задача на всем протяжении ее выполнения должна быть разбита на N параллельно выполняемых участков с объемом данных по памяти, не превышающим Qэbm, и степенью локализации Кэвм > N.

Естественно, что для большинства вышеперечисленных задач при достаточно большом числе N (N > 1000), эти требования практически нереализуемы.

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

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

Однако, было бы неверным говорить, что "Connection machine", имеющая в своем составе более 64 тыс. микроЭВМ, nCUBE-2 или "CRAY-4", не имеет права на существование в области решения больших задач. Можно сказать только, что с увеличением числа ЭВМ или процессоров в комплексе, супер-ЭВМ становится все более специализированным комплексом, т.е. эффективно решает все меньший круг задач.

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

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