Глава 2 АРХИТЕКТУРА ЭВМ ДЛЯ ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛЕНИЙ

Преимуществом использования языков программирования высокого уровня является универсальность программ и их простая переносимость между различными компьютерами (разумеется, если на этих компьютерах имеется необходимое программное обеспечение, компиляторы). Обычно, в повседневной жизни программиста ситуация близка к идеальной – имеется компилятор, порождающий эффективный исполняемый код. В этом случае можно надеяться на то, что при грамотном и аккуратном программировании вычислительная программа будет обладать хорошими показателями по быстродействию. В применении языков низкого уровня (ассемблеров) здесь нет необходимости. Но бывает и так, что программисту требуется знание устройства компьютера и принципов (и даже деталей) его работы. Если речь идет о большом проекте, когда расчет требует суток и недель процессорного времени, оптимизация программы, увеличивающая ее быстродействие даже на несколько процентов, может сэкономить часы процессорного времени и ощутимое количество денежных средств на оплату услуг вычислительного центра. Можно привести следующий пример. При разработке программ для параллельных ЭВМ часто используются специализированные библиотеки, позволяющие организовать обмен данными между отдельными подзадачами и их синхронизацию. Для эффективной организации обмена данными необходимо знать, как происходит пересылка информации между процессорами, какова ее скорость и т.д. В вычислительной науке используются три термина, связанные с устройством электронно-вычислительной машины. Архитектура компьютера – это описание компонент компьютера и их взаимодействия. Организация компьютера – это описание конкретной реализации архитектуры, ее воплощения "в железе". Компьютеры CRAY, например, имеют сходную архитектуру. С точки зрения программиста у них одинаковое число внутренних регистров, используемых для временного хранения данных, одинаковый набор машинных команд, одинаковый формат представления данных. Организация же компьютеров Cray разных моделей может существенно различаться: у них может быть разное число процессоров, разный размер оперативной памяти, разное быстродействие и т.д. Третий термин – это схема компьютера, детальное описание его электронных компонент, их соединений, устройств питания, охлаждения и других. Программисту довольно часто требуется знание архитектуры компьютера, реже его организации и никогда – схемы компьютера.

2.1 Классификация Флинна

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

• SISD (Single Instruction Stream – Single Data Stream) – один поток команд и один поток данных;
• SIMD (Single Instruction Stream – Multiple Data Stream) – один поток команд и множество потоков данных;
• MISD (Multiple Instruction Stream – Single Data Stream) – множество потоков команд и один поток данных;
• MIMD (Multiple Instruction Stream – Multiple Data Stream) – множество потоков команд и множество потоков данных.

Рассмотрим эту классификацию более подробно

2.1.1 SISD компьютеры

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

2.1.2 SIMD компьютеры

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

2.1.3 MISD компьютеры

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

2.1.4 MIMD компьютеры

Эта категория архитектур вычислительных машин наиболее богата, если иметь в виду примеры ее успешных реализаций. В нее попадают симметричные параллельные вычислительные системы, рабочие станции с несколькими процессорами, кластеры рабочих станций и т.д. Уже довольно давно появились компьютеры с несколькими независимыми процессорами, но вначале на таких компьютерах был реализован только параллелизм заданий, то есть на разных процессорах одновременно выполнялись разные и независимые программы. Разработке первых компьютеров для параллельных вычислений были посвящены проекты под условным названием CM* и C.MMP в университете Карнеги (США). Технической базой для этих проектов были процессоры DEC PDP-11. В начале 90-х годов именно MIMD компьютеры выходят в лидеры на рынке высокопроизводительных вычислительных систем.

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

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

2.2.1 Конвейер

Термин "конвейер" в компьютерной архитектуре обозначает ... конвейер. Идея конвейера состоит в том, чтобы сложную операцию разбить на множество более простых, которые могут выполняться одновременно. При движении объектов по конвейеру на разных его участках выполняются разные операции, а при достижении каждым объектом конца конвейера он окажется полностью обработанным. Конвейеры применяются как при обработке команд, так и в арифметических операциях. Для эффективной реализации конвейера должны выполняться следующие условия: истема выполняет повторяющуюся операцию; эта операция может быть разделена на независимые части, степень перекрытия которых невелика; трудоемкость подопераций примерно одинакова. Количество подопераций называют глубиной конвейера. Важным условием нормальной работы конвейера является отсутствие конфликтов, то есть данные, подаваемые в конвейер, должны быть независимыми. В том случае, когда очередной операнд зависит от результата предыдущей операции, возникают такие периоды работы конвейера ("пузыри"), когда он пуст. Это еще одна проблема в работе конвейерных систем. Увеличение быстродействия, которое можно получить с помощью конвейера приблизительно дается следующей формулой: (n*d)/(n+d) где n – количество операндов, загружаемых в конвейер, d – глубина конвейера. Пусть требуется выполнить операцию сложения над двумя одномерными массивами по 200 элементов, причем выполнение сложения требует пять операций. В этом случае ускорение составит (200*5)/(200+5)=4.88. Разумеется, это идеальная ситуация, недостижимая в реальной жизни, в частности, считается, что нет "пузырей" и т.д. Это предполагает, как уже упоминалось, взаимную независимость данных. В конвейерах команд также могут возникать простои, источником которых является зависимость между командами. Такие ситуации возникают при наличии в циклах ветвлений, то есть условных операторов.

2.2.2 Суперскалярные процессоры

Суперскалярный процессор представляет собой нечто большее, чем обычный последовательный (скалярный) процессор. В отличие от последнего, он может выполнять несколько операций за один такт. Основными компонентами суперскалярного процессора являются устройства для интерпретации команд, снабженные логикой, позволяющей определить, являются ли команды независимыми, и достаточное число исполняющих устройств. В исполняющих устройствах могут быть конвейеры. Суперскалярные процессоры реализуют параллелизм на уровне команд. Примером компьютера с суперскалярным процессором является IBM RISC/6000. Тактовая частота процессора у ЭВМ была 62.5 МГц, а быстродействие системы на вычислительных тестах достигало 104 Mflop (Mflop – единица измерения быстродействия процессора – миллион операций с плавающей точкой в секунду). Суперскалярный процессор не требует специальных векторизующих компиляторов, хотя компилятор должен в этом случае учитывать особенности архитектуры.

2.2.3 Векторная обработка данных

Векторный процессор "умеет" обрабатывать одной командой не одно единственное значение, а сразу массив (вектор) значений. Пусть A1, A2 и P – это три массива, имеющие одинаковую размерность и одинаковую длину, и имеется оператор P=A1+A2 Векторный процессор за один цикл выполнения команды выполнит попарное сложение элементов массивов A1 и A2 и присвоит полученные значения соответствующим элементам массива P. Каждый операнд при этом хранится в особом, векторном регистре. Обычному, последовательному процессору пришлось бы несколько раз выполнять операцию сложения элементов двух массивов. Векторный процессор выполняет лишь одну команду! Разумеется, реализация такой команды будет более сложной, более подробное обсуждение этой проблемы содержится в третьей главе настоящего учебника. Очевидно, за счет векторизации можно надеяться (мы не случайно делаем здесь эту оговорку) получить высокую производительность. Кроме того, векторным ЭВМ присущи и другие интересные особенности. Количество команд, необходимых для выполнения одной и той же программы, использующей векторизуемые операции, меньше в случае векторного процессора, чем обычного, скалярного. Уменьшение потока команд позволяет снизить требования к устройствам коммуникации, в том числе между процессором и оперативной памятью компьютера. Другой момент заключается в том, что при соответствующей организации оперативной памяти данные в процессор будут передаваться на каждом такте, что дает значительный выигрыш в производительности компьютера. Следует заметить, что именно векторные ЭВМ были первыми высокопроизводительными компьютерами (мы упоминали уже векторный компьютер С.Крэя) и традиционно именно ЭВМ с векторной архитектурой называются суперкомпьютерами. Векторные компьютеры различаются тем, как операнды передаются командам процессора. Здесь можно выделить следующие основные схемы: из памяти в память – в этом случае операнды извлекаются из оперативной памяти, загружаются в арифметическое устройство и результат возвращается в оперативную память; из регистра в регистр – операнды вначале загружаются в векторные регистры, затем операнд передается в арифметическое устройство и результат возвращается в один из векторных регистров. Преимущество первой схемы заключается в том, что она дает возможность работать с векторами произвольной длины, тогда как во втором случае требуется разбиение длинных векторов на части, длина которых соответствует возможностям векторного регистра. С другой стороны, в первом случае имеется определенное время запуска между инициализацией команды и появлением в конвейере первого результата. Если конвейер уже загружен, результат на его выходе будет получаться в каждом такте. Примером ЭВМ с такой архитектурой являются компьютеры серии CYBER 200, время запуска у которых составляло до 100 тактов. Это очень большая величина, даже при работе с векторами длиной 100 элементов, вышеупомянутые компьютеры достигали лишь половины от своей максимально возможной производительности, и это их в конце концов и погубило. В векторных компьютерах, работающих по схеме регистр-регистр, длина вектора гораздо меньше. Для компьютеров серии Cray это 64. Но существенно меньшее время запуска позволяет добиться хороших показателей по быстродействию. Правда, если работать с длинными векторами, их приходится разбивать на части меньшей длины, что снижает быстродействие. Векторные компьютеры, работающие по схеме из регистра в регистр, в настоящее время доминируют на рынке векторных компьютеров и наиболее известными представителями являются машины семейства Cray, NEC, Fujitsu и Hitachi. Архитектура типичного векторного суперкомпьютера Cray следующая (в качестве примера рассмотрим старую модель Cray-1). Процессор имеет 8 векторных регистров, каждый из которых может хранить 64 слова по 64 бита каждое. Есть также 8 скалярных регистров для 64-битовых слов и 8 регистров для адресации для 20-битовых слов. Вместо кэш-памяти используются специальные регистры, управление которыми осуществляется программным путем из выполняющейся программы. Всего компьютер Cray-1 содержал до 12 конвейеризованных процессоров, имевших отдельные конвейеры для различных арифметических и логических операций. Скорость работы процессора строго согласована со скоростью работы оперативной памяти.

2.2.5 Оперативная память

Характеристики оперативной памяти и особенности ее устройства являются важнейшим фактором, от которого зависит быстродействие компьютера. Ведь даже при наличии быстрого процессора скорость выборки данных из памяти может оказаться невысокой и именно эта невысокая скорость работы с оперативной памятью будет определять быстродействие компьютера. Время цикла работы с памятью tm обычно заметно больше, чем время цикла центрального процессора tc. Если процессор инициализирует обращение к памяти, она будет занята в течение времени tc+tm и в течение этого промежутка времени ни одно другое устройство, в том числе и сам процессор не смогут работать с оперативной памятью. Таким образом, возникает проблема доступа к памяти. Эта проблема решается специальной организацией оперативной памяти. Принята следующая классификация параллельных компьютеров по архитектуре подсистем оперативной памяти: системы с разделяемой памятью, у которых имеется одна большая виртуальная память и все процессоры имеют одинаковый доступ к данным и командам, хранящимся в этой памяти; системы с распределенной памятью, у которых каждый процессор имеет свою локальную оперативную память и к этой памяти у других процессоров нет доступа. Различие этих двух типов памяти проявляется в структуре виртуальной памяти, то есть памяти, как она "видна" процессору. Физически память обычно делится на части, доступ к которым может быть организован независимо. Различие между разделяемой и распределенной памятью заключается в способе интерпретации адреса. Это различие проще пояснить на следующем примере. Пусть один из процессоров выполняет команду вида load r1, i – "загрузить в регистр r1 данные из ячейки памяти i". Если команда выполняется на компьютере с разделяемой памятью, номер ячейки i имеет одинаковый смысл для всех процессоров, i является глобальным адресом. В случае системы с распределенной памятью, ячейка i разная для разных процессоров и в регистры r1 по этой команде будут загружены разные значения. Для программиста часто бывает важно знать тип оперативной памяти компьютера, на котором он работает. Ведь архитектура памяти определяет способ взаимодействия между различными частями параллельной программы. При выполнении на компьютере с распределенной памятью программа перемножения матриц, например, должна создать копии перемножаемых матриц на каждом процессоре, что технически осуществляется передачей на эти процессоры сообщения, содержащего необходимые данные. В случае системы с разделяемой памятью достаточно лишь один раз задать соответствующую структуру данных и разместить ее в оперативной памяти. Остановимся подробнее на раличных архитектурах подсистемы памяти.

2.2.5.1 Чередуемая память

Чередуемая память разделяется на банки памяти. Принято соглашение о том, что ячейка памяти с номером i находится в банке памяти с номером i mod n, где n – количество банков памяти. Таким образом, если имеется 8 банков памяти, то первому банку памяти будут принадлежать ячейки памяти с номерами 0, 8, 16, :, второму – 1, 9, 17, ... и т.д. Запросы к различным банкам памяти могут обрабатываться одновременно. При достаточном количестве банков памяти скорость обмена данными между памятью и процессором может быть близка к идеальному значению – одно машинное слово за один такт работы процессора. Ячейки памяти могут быть перенумерованы и непрерывным образом, то есть, скажем, в первом банке находятся ячейки с номерами от 0 до 255, во втором от 256 до 511 и т.д. В векторных компьютерах обычно используется первый способ адресации, а в многопроцессорных комплексах с разделяемой памятью – второй.

2.2.5.2 Разделяемая память

Простейший способ создать многопроцессорный вычислительный комплекс с разделяемой памятью – взять несколько процессоров, соединить их с общей шиной и соединить эту шину с оперативной памятью. Этот простой способ является не очень удачным, поскольку между процессорами возникает борьба за доступ к шине и если один процессор принимает команду или передает данные, все остальные процессоры вынуждены будут перейти в режим ожидания. Это приводит к тому, что начиная с некоторого числа процессоров, быстродействие такой системы перестанет увеличиваться при добавлении нового процессора. Несколько улучшить картину может применение кэш-памяти для хранения команд. При наличии локальной, то есть принадлежащей данному процессору кэш-памяти, следующая необходимая ему команда с большой вероятностью будет находиться в кэш-памяти. В результате этого уменьшается количество обращений к шине и быстродействие системы возрастает. Вместе с тем возникает новая проблема – проблема кэш-когерентности. Эта проблема заключается в том, что если, скажем, двум процессорам для выполнения различных операций понадобилось значение V, это значение будет храниться в виде двух копий в кэшпамяти обоих процессоров. Один из процессоров может изменить это значение в результате выполнения своей команды и оно будет передано в оперативную память компьютера. Но в кэшпамяти второго процессора все еще хранится старое значение! Следовательно, необходимо обеспечить своевременное обновление данных в кэш-памяти всех процессоров компьютера. Имеются и другие реализации разделяемой памяти. Это, например, разделяемая память с дискретными модулями памяти. Физическая память состоит из нескольких модулей, хотя виртуальное адресное пространство остается общим. Вместо общей шины в этом случае используется переключатель, направляющий запросы от процессора к памяти. Такой переключатель может одновременно обрабатывать несколько запросов к памяти, поэтому если все процессоры обращаются к разным модулям памяти, быстродействие возрастает. Одним из примеров успешно работающих вычислительных систем с разделяемой памятью является компьютер KSR-1 фирмы Kendall Square Research.

2.2.5.3 Распределенная память

В вычислительных системах с распределенной памятью оперативная память имеется у каждого процессора. Процессор имеет доступ только к своей памяти. В этом случае отпадает необходимость в шине или переключателе. Нет и конфликтов по доступу к памяти, так как каждый процессор работает только со своей собственной памятью. Нет присущих системам с разделяемой памятью ограничений на число процессоров, нет, разумеется, и проблемы с кэшкогерентностью. Но, с другой стороны, возникают проблемы с организацией обмена данными между процессорами. Обычно такой обмен осуществляется при помощи обмена сообщениямипосылками, содержащими данные. Для формирования такой посылки требуется время, для получения и считывания полученных данных тоже требуется определенное время. Эти дополнительные затраты времени – плата за все те преимущества, о которых шла речь. Программирование для систем с распределенной памятью – более сложная задача. Оно требует разбиения исходной вычислительной задачи на подзадачи, выполнение которых может быть разнесено на разные процессоры. Одним из наиболее известных компьютеров такого типа является вычислительная система CM-5 фирмы Thinking Machines. Она состоит из процессорных элементов, построенных на основе микропроцессора SPARC и соединенных сетью со специальной топологией типа "дерево". У каждого процессорного элемента имеется локальная память объемом 32 мегабайта. Пропускная способность шины больше у корня дерева и меньше у ее ветвей.