Классификация параллельных вычислительных систем

Введение

Классификация М. Флинна

Другие классификации

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

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

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

В самом деле, вспомним открытый в 1869 году Д.И.Менделеевым периодический закон. Выписав на карточках названия химических элементов и указав их важнейшие свойства, он сумел найти такое расположение, при котором четко прослеживалась закономерность в изменении свойств элементов, расположенных в каждом столбце и в каждой строке. Теперь, зная положение какого-либо элемента в таблице, он мог с большой степенью точности описывать его свойства, не проводя с ним никаких непосредственных экспериментов. Другим, поистине фантастическим следствием, явилось то, что данный закон сразу указал на несколько "белых пятен" в таблице и позволил предсказать существование и свойства неизвестных до тех пор элементов. В 1875 году французский ученый Буабодран, изучая спектры минералов, открыл предсказанный Менделеевым галлий и впервые подробно описал его свойства. В свою очередь Менделеев, никогда прежде не видевший данного химического элемента, не только смог указать на ошибку в определении плотности, но и вычислил ее правильное значение.

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

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

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

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

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

Классификация М. Флинна

По-видимому, самой ранней, наи­более известной и распространенной является классификация структур вычислительных сис­тем, предложенная в 1966 году М. Флинном. Классификация базируется на понятии потока, под которым понимается последовательность команд или данных, обрабатываемая процессором. На основе числа потоков команд и потоков данных М. Флинн выделял четыре класса структур.

SISD (Single Instruction stream/Single Data stream) – одиночный поток команд и одиночный поток данных

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

SIMD (Single Instruction stream/Multiple Data stream) – одиночный поток команд и множественный поток данных. В структурах по­добного рода сохраняется один поток команд, включающий, в отличие от предыдущего класса, векторные команды. Это позволяет выполнять одну арифметическую операцию сразу над многими данными, например, над элементами вектора. Способ выполнения векторных операций не оговарива­ется, поэтому обработка элементов вектора может производиться либо про­цессорной матрицей, как в ILLIAC IV, либо с помощью конвейера, как, на­пример, в вычислительной системе Сгау-1.

MISD (Multiple Instruction stream/Single Data stream) – множественный поток команд и одиночный поток данных. Определение подра­зумевает наличие в структуре многих процессоров, обрабатывающих один и тот же поток данных. Однако, ни М. Флинн, ни другие специалисты в области структуры вычислительных систем до сих пор не смогли представить убе­дительный пример реально существующей вычислительной системы, по­строенной на данном принципе. Ряд исследователей относят конвейерные машины к данному классу, однако это не нашло окончательного призна­ния в научном сообществе. Будем считать, что пока данный класс пуст.

MIMD (Multiple Instruction stream/Multiple Data stream) – множественный поток команд и множественный поток данных. Этот класс предполагает, что в вычислительной системе есть несколько процессоров, объединенных в единый комплекс и работающих каждый со своим потоком команд и данных.

Рассмотрим подробнее каждый класс.

Класс SISD

В SISD, как уже говори­лось, входят однопроцессорные последовательные вычислительные системы типа персональных компьютеров. Однако, в этот класс можно включить и векторно-конвейерные вычислительные системы, если рассматривать вектор как одно неделимое данное для соответствующей команды. В таком случае в этот класс попадают и такие системы, как Сгау-1 и все последующие однопроцессорные модели векторной линии (как фирмы Сгау, так и других фирм).

Класс SIMD

Бесспорными представителями класса SIMD считаются матрицы процессо­ров: ILLIAC IV, ICL DAP, Goodyear Aerospace MPP, Connection Machine 1, ПС 2000 и т. п. В таких вычислительных системах одно управляющее устройство контролирует множество процессорных элементов. Каждый процессорный элемент полу­чает от устройства управления в каждый фиксированный момент времени одинаковую команду и выполняет ее над своими локальными данными. Для классических процессорных матриц никаких вопросов не возникает. Однако в этот же класс можно включить и векторно-конвейерные вычислительные системы, напри­мер, Сгау-1. В этом случае каждый элемент вектора надо рассматривать как отдельный элемент потока данных.

Класс MIMD

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

Предложенная схема классификации вплоть до настоящего времени является самой применяемой при начальной характеристике той или иной вычислительной системы. Если говорится, что вычислительная система принадлежит классу SIMD или MIMD, то сразу становится понятным базовый принцип ее работы (один или много потоков команд, что эквивалентно один или много процессоров), и в некоторых случаях этого бывает достаточно. Однако видны и явные недостатки. В ча­стности, некоторые заслуживающие внимания структуры, например dataflow и векторно-конвейерные вычислительные системы, четко не вписываются в дан­ную классификацию. Другой недостаток – это чрезмерная заполненность класса MIMD. Необходимо средство, более избирательно систематизи­рующее структуры, которые по М. Флинну попадают в один класс, но совершенно различные по числу процессоров, природе и топологии связей между ними, по способу организации оперативной памяти и, конечно же, по техноло­гии программирования.

Другие классификации вычислительных систем

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

классификация Фенга;

классификация Хендлера;

классификация Шнайдера;

классификация Скилликорна;

классификация Хокни;

классификация Шора;

классификация Джонсона;

классификация Дункана;

классификация Дазгупты;

классификация Базу;

классификация Кришнамарфи.

Все названные классификации были предложены в 80-х годах 20-го века (последние – в 1988 - 1990 г.г.). Естественно, все эти классификации базировались на анализе обширной номенклатуры разработанных еще в 70-е и 80-е годы 20-го века вычислительных систем.

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

В настоящее время интерес к классификации вычислительных систем существенно снизился.

Основными параметрами классификации современных параллельных вычислительных систем являются:

количество процессоров (один/много);

тип операционной системы (одна операционная система/много операционных систем);

архитектура процессоров/узлов (скалярная/векторная);

организация оперативной памяти (разделяемая, физически общая или распределенная);

вид коммуникационной подсистемы между активными компонентами системы и механизма обмена.