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

ЭЛЕКТРОННЫЕ УЧЕБНЫЕ РЕСУРСЫ И МЕТОДИКА " * ИХ ИСПОЛЬЗОВАНИЯ В ОБУЧЕНИИ

УДК 004

Е.А. Еремин

О ВЫБОРЕ ПОДХОДА К ПОСТРОЕНИЮ КОМПЬЮТЕРНОЙ ПОДДЕРЖКИ ДЛЯ ИЗУЧЕНИЯ МНОГОПРОЦЕССОРНЫХ СИСТЕМ

Рассмотрены принципы организации многопроцессорных вычислительных систем и на основе проведенного анализа разработано и реализовано учебное программное обеспечение под название «Е14». С его помощью можно изучать наиболее важные черты современных систем параллельной обработки информации, а также производить оценку эффективности параллельных алгоритмов. Особое внимание уделено преемственности изучения материала: тема о мультипроцессорной архитектуре служит логическим продолжением и развитием изучаемых ранее разделов о классической архитектуре традиционных компьютеров. Предложенное ПО может быть использовано для поддержки самых разнообразных курсов, связанных с параллельными вычислениями.

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

Введение

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

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

= 5

© Еремин Е.А. • 2014

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

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

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

Способы построения многопроцессорных систем

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

Многомашинные и многопроцессорные системы

Существует несколько вариантов объединения вычислительных устройств для параллельных вычислений. Во-первых, можно распределить задачу между множеством компьютеров, которые соединены сетью; в результате получится многомашинный комплекс. Во-вторых, современные процессоры (начиная с Pentium и выше [9]) имеют встроенные аппаратные средства для организации многопроцессорных (мультипроцессорных) систем. Наконец, в-третьих, многие модели современных многоядерных процессоров фактически представляют из себя несколько процессоров, собранных в одном корпусе.

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

Системы с одинаковыми/неодинаковыми процессорами

Большинство многоядерных процессоров состоят из нескольких одинаковых ядер, ни одно из которых не имеет специальных возможностей для управления другими ядрами. В частности, именно такие процессоры производит «законодатель мод» в мире микропроцессоров фирма Intel. Часто такие системы называют симметричными.

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

Очевидно, что изучение такой организации параллельных вычислений весьма сложно, ибо требует не только понимания устройства самого многоядерного процессора, но и знания основ работы многозадачных операционных систем, причем далеко не самых простых. Данный вывод подтверждается результатами работы [8], где разработана методика изучения принципов работы многоядерных процессоров. Предлагаемый учебный программный комплекс, изображенный на рис. 1, в цитируемой статье, настолько сложен, что пока реализован не полностью. В любом случае, если такой крупный вуз, как Московский государственный институт радиотехники, электроники и автоматики может себе позволить подобную учебную систему, для остальных нужно что-нибудь более скромное и простое.

Существуют ли альтернативные решения? Да, существуют. Несколько фирм (Sony, IBM и Toshiba) предложили процессор принципиально иной организации - Cell (полное официальное название - Cell Broadband Engine - CBE) [10]. Его планировалось внедрить в игровые приставки, но эта часть проекта оказалась неудачной. Тем не менее процессор реально был создан. Более того, IBM, основываясь на архитектуре CBE, выпустила более позднюю модель PowerXCell 8i, которая в несколько раз быстрее своей предшественницы обрабатывала вещественные числа двойной точности. Высокая производительность PowerXCell 8i привлекла внимание разработчиков суперкомпьютеров, и многие современные суперкомпьютеры (включая находящийся в МГУ «Ломоносов», занимавший на 20 июля 2014 г. 42-е место в мировом рейтинге суперкомпьютеров) содержат блоки на основе этих процессоров.

Существенным отличием архитектуры Cell является то, что он состоит из главного процессора (PPE - PowerPC Processor Element, который, кстати говоря, сам является дву-ядерным!) и восьми подчиненных (SPE - Synergistic Processor Element). Для нас существенным является то, что главный процессор распределяет вычислительную работу, так что вся задача решается непосредственно внутри процессора. Подчеркнем, что программу по распределению работ на выделенном центральном процессоре можно сделать гораздо проще, чем ОС для симметричного многоядерного процессора, особенно если речь идет о несложных учебных задачах. Именно это обстоятельство склоняет нас к выбору такой архитектуры для нашего учебного ПО.

Объективности ради следует заметить, что одна из главных причин неудачи проекта Cell применительно к игровым приставкам состояла в сложности программирования. Мы попытаемся преодолеть этот недостаток путем упрощения системы команд для применяемых процессоров. Для простоты изучения можно дополнительно сделать систему команд главного и подчиненных процессоров одинаковыми. Более того, в качестве процессоров предлагается применить ту же самую учебную модель процессора [4], которая ис-

пользовалась студентами ранее [7] при изучении классической архитектуры с единственным процессором.

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

Системы с общей/раздельной памятью

Известно [1-3], что системы для параллельных вычислений бывают с общей и с раздельной памятью. В первом случае все процессоры берут данные из единой, общей для всех памяти и туда же возвращают результаты. Теоретически это очень удобно, но, как мы увидим далее, на практике реализовать не так-то просто. Системы с раздельной памятью, где каждый процессор имеет собственную память, а обмен данными происходит непосредственно между самими процессорами, реализовать существенно легче. Зато появляются этапы передачи данных и результатов из одного блока памяти в другой, что сильно замедляет процесс обработки.

общая память

X

Рис. 1. Сложности работы с общей памятью

Поясним, почему могут возникать трудности в архитектуре с общей памятью. Начнем с парадоксального и несколько искусственного примера. Пусть в системе с общей памятью работают всего два процессора, и в данный момент времени один из них (Р1) «хочет» прибавить к ячейке с адресом £ число 2, а второй (Р2) к этой же самой ячейке -единицу (см. рис. 1). Для наглядности можно считать, что в ячейке S хранится счетчик некоторых объектов. Если предположить, что перед началом операции в рассматриваемой ячейке лежало число X, то какой результат получится после параллельного выполнения указанных команд? Логика требует, чтобы ответ был Х+3, т.е. Р1 прибавил 2 и Р2 добавил еще 1. Но если команды действительно выполняются одновременно, то с большой вероятностью обе инструкции получат из памяти число X, а потом первый процессор «насчитает» Х+2, а второй - Х+1. Дальше все определяется тем, какой из них обратиться к памяти позднее - таков и будет итоговый результат.

Даже если вычисления не так сильно взаимосвязаны, и процессоры Р1 и Р2 будут работать с разными ячейками, все равно при обращении к общей памяти возникнет задержка: одна микросхема физически не в состоянии ответить обоим процессорам одновременно. А значит, в системе появятся очередь и ожидание. Таким образом, заманчивая модель с общей памятью на практике оказывается не такой быстрой, как интуитивно кажется.

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

Сложности параллельного решения задач

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

Не каждый алгоритм выполняется параллельно

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

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

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

Пусть алгоритм допускает параллельное выполнение. Возьмем параллельное суммирование, которое обсуждалось выше, и попробуем его практически реализовать в системе с раздельной памятью. Предположим, что у нас имеется N процессоров, и количество чисел K для простоты делится на N нацело. Тогда каждому процессору достаточно просуммировать K/N слагаемых. Проблема заключается в том, что прежде чем любой из процессоров просуммирует «свои» числа, их надо предварительно скопировать в его память. Учитывая, что копирование требует почти столько же команд, сколько собственно суммирование, эффект от параллельности суммирования существенно упадет. Кроме того, завершив суммирование, каждый процессор должен вернуть результат вычислений главному процессору, который сложит все полученные значения. На все это также придется потратить время.

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

Взаимосвязанные вычисления необходимо синхронизировать

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

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

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

Преемственность изучения

Как уже отмечалось ранее, с точки зрения построения образовательных курсов удобно, когда при переходе от изучения обычного процессора к многоядерному студентам не приходится изучать новую систему команд. В нашем университете при изучении базовых принципов архитектуры использовалась учебная модель «Е97» [4, 5, 7]. Ее система команд минимальна, но тем не менее вполне достаточна для решения любой учебной задачи. Как оказалось, она вполне подходит и для того, чтобы «построить» учебный многоядерный процессор. При этом в его состав вошли 4 подчиненных (PPU - Peripheral Processor Unit) процессора и один главный (CPU - Central Processor Unit), каждый из которых практически идентичен процессору из «Е97». Предлагаемая многопроцессорная модель получила имя «Е14» как по количеству процессоров (1 главный и 4 периферийных), так и по году ее создания. Еще один аспект преемственности заключается в том, что для взаимодействия процессоров между собой использованы те же самые механизмы, что и при взаимодействии обычного одноядерного процессора с внешними устройствами.

Благодаря такому решению, изучение нового многоядерного процессора позволяет повторить и углубить следующие фундаментальные принципы ввода-вывода:

• обращение к внешним устройствам через порты;

• обмен данными через шину;

• механизм прямого доступа к памяти.

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

Учебная модель «Е14»

В результате подробного анализа базовых принципов параллельных устройств была создана и реализована в виде учебного программного обеспечения модель многопроцессорного компьютера «Е14». Ее основные характерные черты следующие.

Процессор «Е14» состоит из 5 взаимосвязанных процессоров - 1 центрального (CPU) и 4 периферийных (PPU1 - PPU4). Главный процессор распределяет вычислительные работы и руководит всеми периферийными процессорами, обеспечивая необходимую синхронизацию вычислений. При желании («в свободное время») его можно использовать для вычислений как и все остальные процессоры.

Все процессоры, образующие «Е14», полностью совместимы с учебной моделью «Е97».

Модель «Е14» позволяет имитировать две архитектуры: с общей и раздельной памятью (А1 и А2 слева и справа на рис. 2).

CPU

Р

Рис. 2. Модель «Е14»: имитация двух архитектур

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

Во втором случае доступ к памяти CPU периферийные процессоры PPU1 - PPU4 получают через шину, объединяющую все процессоры между собой. При таком способе

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

Напомним, что, как следует из общей теории, архитектура А2 работает медленнее, чем А1.

Независимо от выбранной архитектуры, программы для всех процессоров и все данные сначала загружаются из файла в память CPU. Одна из программ выделена как главная, и именно она запускается в CPU. Начав работу, эта программа обеспечивает перепись требуемых программ и данных в PPU1 - PPU4, а затем запускает эти программы на выполнение. Пока PPU1 - PPU4 заняты вычислениями, CPU либо просто дожидается их окончания, либо сам может выполнить некоторую долю вычислений. В любом случае CPU собирает результаты от всех процессоров и, если требуется, обрабатывает их (например, суммирует).

Заметим, что для удобства работы студентов в модели «Е14» использован тот же самый прием, что и в «Е97»: наиболее часто используемые подпрограммы хранятся в имитации постоянного запоминающего устройства (ПЗУ). Наличие готовых подпрограмм позволяет сократить программы студентов и сделать их написание заметно проще.

Студент наблюдает на экране картину, вид которой приводится на рис. 3.

Рис. 3 Общий вид программного обеспечения «Е14»

Интерфейс программы состоит из нескольких окон. Четыре окна (два слева и два справа) отображают содержимое PPU1 - PPU4, а центральное окно - CPU. Внизу в центре находится окно, с помощью которого можно анализировать содержимое памяти. В отличие от всех предыдущих окон, оно имеет некоторые органы управления, позволяющие отобразить память нужного участка ОЗУ у интересующего нас процессора.

Наконец, главное окно программы - пульт управления «Е14» - находится в центральной части экрана сверху. Оно позволяет студенту загружать, запускать и останавливать загруженную программу для «Е14», а также проводить некоторые отладочные манипуляции, например, замедлять скорость работы программы с целью рассмотреть, какие процессоры что делают.

В центральной части главного окна находятся цветные индикаторы, отображающие состояние каждого из процессоров: ожидание, счет, ввод или вывод данных. Длинный нижний индикатор показывает активность всей системы в целом: он зеленый, если работает хотя бы один из процессоров. В частности, на рис. 3 компьютер остановлен в тот момент, когда PPU4 еще не закончил ввод исходных данных, а остальные уже завершили этот шаг, причем PPU1 и PPU2 начали вычисления, а PPU3 еще не успел (все это легко видеть по цвету соответствующих индикаторов).

Под индикатором каждого из процессоров, а также под общим индикатором, отображается счетчик количества команд, которые выполнил каждый процессор и вся система. Приближенно можно считать, что каждая команда выполнялась примерно одинаковое время: для многих простых операций это предположение справедливо [5]. Тогда по этим данным можно судить о времени счета и, соответственно, об эффективности параллельных вычислений. В частности, можно загрузить программу и выполнить ее только в CPU, а затем запустить другую программу, производящую вычисления с участием PPU. Сравнение общего количества машинных команд, которое потребовалось выполнить по каждой из программ, покажет, есть ли ускорение вычислений за счет параллельности и во сколько раз.

Написанное учебное программное обеспечение в настоящее время проходит апробацию на занятиях со студентами II курса специальности «Информационные технологии в образовании».

Автор выражает благодарность А.Я. Куземину, профессору Харьковского национального университета радиоэлектроники, который на одной из конференций при обсуждении доклада про «Е97» предложил модифицировать модель на случай нескольких процессоров. Сейчас, наконец, его пожелание реализовано в виде описанной модели «Е14».

Список литературы

1. Барский А. Курс «Архитектура параллельных вычислительных систем». [Электронный ресурс]. -URL: http://www.intuit.ru/studies/courses/14277/80/lecture/2431?page=2#sect3.

2. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: BHV-Петербург, 2002. - 608 с.

3. Гергель В.П. Теория и практика параллельных вычислений. - М.: Интернет-Университет Информационных технологий; БИНОМ. Лаборатория знаний, 2007. - 424 с.

4. Еремин Е.А. Как работает современный компьютер. - Пермь: изд-во ПРИПИТ, 1997. - 176 с.

5. Еремин Е.А. Популярные лекции об устройстве компьютера. - СПб.: BHV-Петербург, 2003. - 272 с.

6. Еремин Е.А. Учебная модель компьютера как база для изучения информатики // Proceedings of the III International Conference "Information Research, Applications and Education" (iTECH 2005). - Sofia: FOI-COMMERCE, 2005. - P.165-169.

7. Могилев А.В., Пак Н.И., Хеннер Е.К. Информатика: учеб. пособие для студ. пед. вузов. - М.: Академия, 2012. - 848 с.

8. Семенов А.А. Многоядерная архитектура универсальной 32-ух разрядной учебной машины. [Электронный ресурс]. - URL: http://www.rae.ru/forum2011/153/1794.

9. Шагурин И.И., Бердышев Е.М. Процессоры семейства Intel P6. Архитектура, программирование, интерфейс. - М.: Горячая линия - Телеком, 2000. - 248 с.

10. Cell Broadband Engine Programming Handbook Including the PowerXCell 8i Processor. Version 1.12. -IBM, 2009. - 876 p.