Загрузка...Многопроцессорные системы с общей памятью
Многопроцессорные системы с общей памятью
Для увеличения производительности в состав вычислительной системы может вводиться несколько процессоров, способных функционировать параллельно во времени и независимо друг от друга и вместе с тем взаимодействовать между собой и с другим оборудованием системы. Вычислительные системы, содержащие несколько процессоров, связанных между собой и с общим для них комплектом внешних устройств, называются мультипроцессорными системами (МПС).
Производительность МПС увеличивается по сравнению с однопроцессорной системой за счет того, что мультипроцессорная организация создает возможность для одновременной обработки нескольких задач или параллельной обработки различных частей одной задачи.
В ряде случаев требуется обеспечить непрерывность функционирования системы во времени. Это означает, что отказ в любом устройстве ВС, в том числе и в процессоре, не должен приводить к катастрофическим последствиям, т.е. система должна сохранять работоспособность и после отказа. В таком случае все устройства ВС должны быть по крайней мере задублированы и система должна содержать не менее двух процессоров, т.е. строиться как МПС.
Наиболее существен в структурной организации МПС способ связи между процессорами и памятью системы. В этом аспекте МПС разделяются на МПС с памятью общей (полнодоступной) и индивидуальной (раздельной).
В МПС с общей памятью каждый из процессоров имеет доступ к любому модулю памяти, которые могут функционировать независимо друг от друга и в каждый момент времени обеспечивать одновременные обращения в целях записи или чтения слов информации, число которых определяется числом модулей. Конфликтные ситуации (обращение к одному и тому же модулю памяти) разрешаются коммутатором, начинающим обслуживать первым устройство с наибольшим приоритетом, например процессор с наименьшим номером. Каждый из процессоров может инициировать работу любого канала ввода-вывода.
Структура МПС с общей памятью наиболее универсальна: любая информация, хранимая в памяти системы, в равной степени доступна любому процессору и каналу ввода-вывода. Отрицательное свойство МПС с общей памятью — большие затраты оборудования в коммутаторах (эти затраты пропорциональны произведению числа устройств, подключенных к памяти, и числа модулей памяти).
В МПС с индивидуальной памятью каждый из процессоров обращается в основном к своему модулю памяти. Для обмена данными между подсистемами "процессор — модуль памяти" в процессорах предусмотрены блоки обмена, обеспечивающие передачу сегментов информации между общей памятью и модулем памяти. При этом блок обмена может работать как селекторный канал: операция обмена инициируется процессором, и передача данных выполняется с параллельной работой последнего. Принцип индивидуальной памяти позволяет исключить коммутаторы в интенсивно используемом канале "процессор — модуль памяти", вследствие чего увеличивается номинальное быстродействие процессоров и уменьшаются затраты оборудования по сравнению с системами с общей памятью. Отрицательным последствием разделения памяти между процессорами является потеря ресурсов быстродействия в процессе обмена информацией между модулями памяти и общей памятью системы. Потери возникают, во-первых, из-за возможных приостановок работы процессоров для ожидания моментов окончания обмена данными с общей памятью и, во-вторых, из-за дополнительной загрузки модулей памяти операциями обмена.
Если класс задач, решение которых возлагается на МПС, таков, что работа каждого процессора связана с использованием в основном ограниченного подмножества данных и обращение к остальным данным происходит сравнительно редко, то индивидуализация памяти приводит к экономии оборудования и обеспечивает высокое номинальное быстродействие процессоров в системе. В противном случае, когда каждый из процессоров почти равновероятно обращается к любому сегменту данных, МПС должна строиться по схеме с общей памятью, исключающей необходимость в обмене информацией между модулями памяти.
Классификация многопроцессорных систем
Многопроцессорные системы по классификации Флинна относятся к архитектурам типа MIMD(Multiple Instruction Multipl Data) с множественным потоком команд при множественном потоке данных (МКМД). В многопроцессорной системе каждый процессор выполняет свою программу достаточно независимо от других процессоров. Процессоры в ходе решения общей задачи должны связываться друг с другом в соответствии с графом взаимодействия её параллельных ветвей. Это вызывает необходимость более подробно производить классификацию систем типа MIMD.
В многопроцессорных системах с общей памятью (сильносвязанных) имеется память данных и команд, доступная всем процессорам. С общей памятью процессоры связываются с помощью коммуникационной среды, основой которой может быть либо общая шина (ОШ), либо множество шин (МШ), либо перекрёстный коммутатор (ПК).
В противоположность этому варианту в слабосвязанных многопроцессорных системах (машинах с распределённой памятью) вся память разделена между процессорами и каждый блок памяти доступен только локальному процессору. Память и процессор образуют фактически независимые вычислительные модули (вычислительные узлы), которые связываются между собой при помощи высокоскоростной сети обмена с коммутацией сообщений.
Сообщение – это блок информации, сформированный процессом-отправителем таким образом, чтобы он был понятен процессу-получателю. Сообщение состоит из заголовка фиксированной длины и набора данных определённого типа обычно переменной длины. В заголовок, как правило, включают следующую информацию:
• адрес — это поле, предназначенное для идентификации процессоров (вычислительных узлов), участвующих в процедуре обмена. Адрес процессора или вычислительного узла является уникальным и состоит из двух частей — адреса процессора — отправителя и адреса процессора — получателя;
• управляющие поля, в которые могут входить символы синхронизации, отмечающие начало и конец передаваемого блока (кадра) данных, символы, обозначающие тип данных, длину передаваемых данных и др.
В качестве топологической модели коммуникационной среды применяют линейные или кольцевые моноканалы, звездообразную конфигурацию, плоскую решётку, n- мерный тор, либо n- кубическую (гиперкубическую) сеть.
Базовой моделью вычислений на MIMD-системах является совокупность независимых процессов, время от времени обращающихся к разделяемым данным. Основана она на распределенных вычислениях, в которых программа делится на довольно большое число параллельных задач.
В настоящее время всё большее внимание разработчики проявляют к архитектурам типа MIMD. Это находит объяснение главным образом существованием двух факторов:
1) в архитектурах MIMD используются высокотехнологичные, дешёвые, выпускаемые массово микропроцессоры, что позволяет оптимизировать соотношение стоимость/производительность;
2) архитектура MIMD дает большую гибкость и при наличии соответствующей поддержки со стороны аппаратных средств и программного обеспечения, поскольку может работать и как однопрограммная система, обеспечивая высокопроизводительную обработку данных для одной прикладной задачи, и как многопрограммная, выполняющая множество задач параллельно, а также как некоторая комбинация этих возможностей.
Одной из отличительных особенностей многопроцессорной вычислительной системы является коммуникационная среда, с помощью которой процессоры соединяются друг с другом или с памятью. Топология коммуникационной среды настолько важна для многопроцессорной системы, что многие характеристики производительности и другие оценки выражаются отношением времени обработки к времени обмена, которые в общем случае зависят от алгоритмов решаемых задач и порождаемых ими вычислительных процессов.
Существуют две основные модели межпроцессорного обмена: одна основана на передаче сообщений, другая — на использовании общей памяти.
В многопроцессорных системах с общей памятью один процессор осуществляет запись в конкретную ячейку, а другой процессор производит считывание из этой ячейки памяти. Чтобы обеспечить согласованность данных и синхронизацию процессов, обмен часто реализуется по принципу взаимно исключающего доступа к общей памяти методом "почтового ящика".
В архитектурах с распределённой памятью непосредственное разделение памяти невозможно. Вместо этого процессоры получают доступ к совместно используемым данным посредством передачи сообщений по сети обмена. Эффективность схемы коммуникаций зависит от протоколов обмена, каналов обмена и пропускной способности памяти.
Такие системы часто называют системами с передачей сообщений. Каждый из этих механизмов обмена имеет свои преимущества. Для обмена в общей памяти это включает:
• совместимость с хорошо понятными и используемыми в однопроцессорных системах механизмами взаимодействия процессора с основной памятью;
• простота программирования, особенно это заметно в тех случаях, когда процедуры обмена между процессорами сложные или динамически меняются во время выполнения. Подобные преимущества упрощают конструирование компилятора;
• более низкая задержка обмена и лучшее использование полосы пропускания при обмене малыми порциями данных;
• возможность использования аппаратно управляемого кэширования для снижения частоты удаленного обмена, допускающая кэширование всех данных как разделяемых, так и неразделяемых.
Основные преимущества обмена с помощью передачи сообщений являются:
• аппаратура может быть более простой, особенно по сравнению с моделью разделяемой памяти, которая поддерживает масштабируемую когерентность кэш-памяти;
• процедуры обмена понятны, принуждают программистов (или компиляторы) уделять внимание обмену, который обычно имеет высокую, связанную с ним, стоимость.
Часто, в системах с общей памятью затраты времени на обмен не учитываются, так как проблемы обмена в значительной степени скрыты от программиста. Однако накладные расходы на обмен в этих системах имеются и определяются в основном конфликтами при доступе процессоров и других устройств к общим шинам и блокам основной памяти. Чем больше процессоров добавляется в систему, тем больше процессов соперничают при использовании одних и тех же данных и шины, что может привести к значительным задержкам хода вычислительного процесса и, следовательно, к потерям общей производительности. Причём с увеличением числа процессоров в системе возможно появление эффекта насыщения при котором рост числа процессоров не приведёт к росту производительности, и даже наоборот к её падению.
Модель системы с общей памятью очень удобна для прогаммирования, поскольку пользователь практически не задумывается о процедурах распараллеливания (они большей частью ложатся на компилятор) и процедурах взаимодействия параллельных процессов (они производятся аппаратными средствами посредством общей памяти).
В сетях с коммутацией сообщений по мере возрастания требований к обмену следует учитывать возможность перегрузки сети. Здесь межпроцессорный обмен связывает сетевые ресурсы: каналы, процессоры, буферы сообщений. Объем передаваемой информации может быть сокращен за счет тщательного разбиения задачи на параллельные ветви и тщательной диспетчеризации процесса их исполнения.
Таким образом, существующие MIMD-системы распадаются на два основных класса в зависимости от количества объединяемых процессоров, которое определяет способ организации памяти и методику их межсоединений.
К первому классу относятся системы с разделяемой (общей) основной памятью (Shared Memory multiProcessing, SMP), объединяющие до нескольких (2-16) процессоров, число которых зависит от типа применяемой коммуникационной среды. Сравнительно небольшое количество процессоров в таких системах позволяет иметь одну централизованную общую память и зачастую объединить процессоры и память с помощью лишь одной шины. При наличии у процессоров кэш-памяти достаточного объема высокопроизводительная шина и общая память могут удовлетворить обращения к памяти, поступающие от нескольких процессоров.
Поскольку имеется единственная память с одним и тем же временем доступа, эти системы называют симметричными, а иногда — UMA (Uniform Memory Access). Симметричная архитектура предполагает однородность процессоров и единообразную схему их включения в многопроцессорную систему. Такой способ организации со сравнительно небольшой разделяемой памятью в настоящее время является наиболее популярным.
Структура подобной системы представлена на рис. 90.
Рис. 90. Архитектура многопроцессорной системы с разделяемой (общей) памятью.
Второй класс составляют крупномасштабные вычислительные системы с распределенной памятью. Подобные ВС получили название систем с массовым параллелизмом (Mass-Parallel Processing, MPP). Для того чтобы подключать в систему большое количество процессоров необходимо физически разделять основную память и распределять её между ними. В противном случае пропускной способности памяти просто может не хватить для удовлетворения запросов, поступающих от очень большого числа процессоров. Естественно при таком подходе также требуется реализовать связь процессоров между собой. На рис. 91 показана структура такой системы.
Рис. 91. Архитектура многопроцессорной системы с распределенной памятью.
Адресное пространство в таких системах состоит из отдельных адресных пространств, которые логически не связаны, и доступ к которым не может быть осуществлен аппаратно другим процессором. Фактически каждый модуль процессор-память представляет собой отдельный компьютер, поэтому такая структура в какой-то степени приближена к многопроцессорным системам.
MPP система менее эффективна с точки зрения пользователя из-за усложнённой процедуры программирования, которая связана с применением специальных коммуникационных библиотек для организации взаимодействия между вычислительными узлами (процессами). Необходимость же реализации модели распределенной памяти объясняется тем, что масштабируемость (способность системы к наращиванию числа процессоров) систем с общей памятью ограничена пропускной способностью памяти и коммуникационной среды.
Вообще распределение памяти между отдельными узлами системы имеет два главных преимущества. Во-первых, это эффективный с точки зрения стоимости способ увеличения пропускной способности памяти, поскольку большинство обращений могут выполняться параллельно к локальной памяти в каждом узле. Во- вторых уменьшается задержка обращения к локальной памяти из-за отсутствия конфликтов при доступе к ней. Поэтому совершенно естественно появление промежуточного класса систем, объединяющего достоинства первого и второго классов. Память в таких системах распределена по вычислительным узлам и одновременно является доступной для всех процессоров. Такие ВС называются системами с распределенной разделяемой (общей) памятью (DSM — Distributed Shared Memory), а иногда NUMA ( Non-Uniform Memory Access), поскольку время доступа зависит от расположения данных в подсистеме памяти (Рис. 92). Если данные находятся в локальной памяти местного вычислительного узла, то время доступа к ним минимально, если в локальной памяти удалённого вычислительного узла, то время доступа
увеличивается в несколько раз.
Рис. 92. Архитектура многопроцессорной системы с распределённой разделяемой памятью.
Хотя структурно DSM и MPP-системы сходны, однако технически они реализуются по-разному. В DSM-системах физически отдельные, распределённые по вычислительным узлам, устройства памяти могут представляться логически как единое адресное пространство, что означает, что любой процессор может выполнять обращения к любым ячейкам памяти, предполагая, что он имеет соответствующие права доступа.
Коммуникационная же среда и вовсе другая, так как она полностью соответствует структурам SMP-систем. Поскольку, в связи с принципами локальности, вычислительный процесс в основном развивается внутри вычислительного узла и редко обращается к удалённой памяти, что резко снижает объём передаваемых данных по коммуникационной среде, то масштабируемость таких систем повышается по сравнению с SMP-системами, и число процессоров может достигать 32-х.
Что касается устройств ввода/вывода и внешних запоминающих устройств, то они также как и память, либо распределяются по узлам, либо находятся в общем пользовании.
studopedia.org — Студопедия.Орг — 2014-2021 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.004 с) .
Многопроцессорность — Multiprocessing
Многопроцессорность использование двух или более центральные процессоры (ЦП) в пределах одного компьютерная система. [1] [2] Этот термин также относится к способности системы поддерживать более одного процессора или способности распределять задачи между ними. Есть много вариантов этой базовой темы, и определение многопроцессорности может варьироваться в зависимости от контекста, в основном в зависимости от того, как определены процессоры (несколько ядер на одной умри, несколько штампов в одном пакет, несколько пакетов в одном системный блок, так далее.).
Согласно некоторым он-лайн словарям, мультипроцессор компьютерная система, имеющая два или более блоки обработки (несколько процессоров) каждый обмен основная память и периферийные устройства для одновременной обработки программ. [3] [4] В учебнике 2009 года многопроцессорная система определяется аналогично, но при этом отмечается, что процессоры могут совместно использовать «часть или всю системную память и средства ввода-вывода»; это также дало тесно связанная система как синоним. [5]
На Операционная система уровень многопроцессорность иногда используется для обозначения выполнения нескольких одновременных процессы в системе, где каждый процесс выполняется на отдельном процессоре или ядре, в отличие от одного процесса в любой момент. [6] [7] При использовании с этим определением многопроцессорность иногда противопоставляется многозадачность, который может использовать только один процессор, но переключать его во временных отрезках между задачами (т.е. система разделения времени). Однако многопроцессорность означает истинное параллельное выполнение нескольких процессов с использованием более чем одного процессора. [7] Многопроцессорность не обязательно означает, что один процесс или задача используют более одного процессора одновременно; период, термин параллельная обработка обычно используется для обозначения этого сценария. [6] Другие авторы предпочитают называть методы операционной системы как мультипрограммирование и зарезервируйте срок многопроцессорность для аппаратного аспекта наличия более одного процессора. [2] [8] В оставшейся части статьи многопроцессорность обсуждается только в аппаратном смысле.
В Таксономия Флинна, мультипроцессоры, как определено выше, являются MIMD машины. [9] [10] Поскольку термин «мультипроцессор» обычно относится к сильно связанным системам, в которых все процессоры совместно используют память, мультипроцессоры не являются всем классом машин MIMD, который также содержит передача сообщений мультикомпьютерные системы. [9]
Содержание
Предыстория
Возможно, первое выражение идеи многопроцессорности было написано Луиджи Федерико Менабреа в 1842 г., около Чарльз Бэббиджс аналитическая машина (в переводе Ада Лавлейс): «машина может быть задействована так, чтобы давать несколько результатов одновременно, что значительно сократит весь объем процессов». [11]
Ключевые темы
Симметрия процессора
В многопроцессорность В системе все процессоры могут быть одинаковыми или некоторые могут быть зарезервированы для специальных целей. Комбинация оборудования и Операционная система Соображения дизайна программного обеспечения определяют симметрию (или ее отсутствие) в данной системе. Например, соображения аппаратного или программного обеспечения могут потребовать, чтобы только один конкретный ЦП отвечал на все аппаратные прерывания, тогда как вся остальная работа в системе может быть распределена между ЦП поровну; или выполнение кода режима ядра может быть ограничено только одним конкретным ЦП, тогда как код пользовательского режима может выполняться в любой комбинации процессоров. Многопроцессорные системы часто легче спроектировать, если наложены такие ограничения, но они, как правило, менее эффективны, чем системы, в которых используются все процессоры.
Системы, которые одинаково относятся ко всем процессорам, называются симметричная многопроцессорная обработка (SMP) системы. В системах, где не все процессоры равны, системные ресурсы могут быть разделены несколькими способами, включая асимметричная многопроцессорность (ASMP), неравномерный доступ к памяти (NUMA) многопроцессорность и сгруппированный многопроцессорность.
Многопроцессорная система ведущий / ведомый
В многопроцессорной системе главный / подчиненный главный ЦП управляет компьютером, а подчиненный ЦП выполняет назначенные задачи. Процессоры могут быть совершенно разными по скорости и архитектуре. Некоторые (или все) процессоры могут иметь общую шину, каждый также может иметь частную шину (для частных ресурсов) или они могут быть изолированы, за исключением общего канала связи. Точно так же процессоры могут совместно использовать общую RAM и / или иметь частную RAM, к которой другой процессор (ы) не может получить доступ. Роли ведущего и ведомого могут меняться от одного процессора к другому.
Ранним примером многопроцессорной системы ведущий / ведомый является Tandy / Radio Shack. TRS-80 Модель 16 настольный компьютер, выпущенный в феврале 1982 г., на котором выполнялась многопользовательская / многозадачная Xenix операционная система, версия UNIX от Microsoft (называемая TRS-XENIX). Модель 16 имеет 3 микропроцессора, 8-битный Зилог Z80 Процессор работает на частоте 4 МГц, 16 бит Motorola 68000 ЦП работает на частоте 6 МГц и Intel 8021 в клавиатуре. Когда система была загружена, Z-80 был ведущим, а процесс загрузки Xenix инициализировал ведомый 68000, а затем передал управление 68000, после чего ЦП сменили роли, и Z-80 стал ведомым процессором, который отвечал за все Операции ввода-вывода, включая диск, связь, принтер и сеть, а также клавиатуру и встроенный монитор, в то время как операционная система и приложения выполнялись на процессоре 68000. Z-80 можно было использовать и для других задач.
Ранее TRS-80 Модель II, который был выпущен в 1979 году, также можно было рассматривать как многопроцессорную систему, поскольку в ней были как ЦП Z-80, так и Intel 8021 [12] микропроцессор в клавиатуре. Модель 8021 сделала Model II первой настольной компьютерной системой с отдельной съемной легкой клавиатурой, соединенной одним тонким гибким проводом, и, вероятно, первой клавиатурой, в которой использовался выделенный микропроцессор, оба атрибута позже были скопированы годами позже Apple и IBM. .
Инструкции и потоки данных
В многопроцессорной обработке процессоры могут использоваться для выполнения одной последовательности инструкций в нескольких контекстах (одна инструкция, несколько данных или SIMD, часто используемые в векторная обработка), несколько последовательностей инструкций в одном контексте (несколько инструкций, отдельные данные или MISD, используемый для избыточность в отказоустойчивых системах и иногда применяется для описания конвейерные процессоры или Hyper Threading) или несколько последовательностей инструкций в разных контекстах (несколько инструкций, несколько данных или MIMD).
Связь процессора
Многопроцессорная система с сильной связью
Сильно связанные многопроцессорные системы содержат несколько процессоров, подключенных на уровне шины. Эти процессоры могут иметь доступ к центральной разделяемой памяти (SMP или UMA) или может участвовать в иерархии памяти как с локальной, так и с общей памятью (SM) (NUMA). В IBM p690 Regatta — это пример высокопроизводительной SMP-системы. Intel Xeon процессоры доминировали на рынке мультипроцессоров для бизнес-ПК и были единственным основным вариантом x86 до выпуска AMDс Opteron линейка процессоров в 2004 году. Обе серии процессоров имели собственный встроенный кэш, но обеспечивали доступ к общей памяти; процессоры Xeon через общий канал, а процессоры Opteron через независимые каналы к системе ОЗУ.
Чип-мультипроцессоры, также известные как многоядерный вычисления, включают более одного процессора, размещенного на одном кристалле, и могут рассматриваться как наиболее экстремальная форма тесно связанной многопроцессорной обработки. Системы мэйнфреймов с несколькими процессорами часто тесно связаны.
Слабосвязанная многопроцессорная система
Слабосвязанные многопроцессорные системы (часто называемые кластеры) основаны на нескольких автономных одно- или двухпроцессорных товарные компьютеры соединены высокоскоростной системой связи (Гигабитный Ethernet обычное дело). Linux Кластер Беовульф является примером слабо связанный система.
Сильно связанные системы работают лучше и физически меньше, чем слабосвязанные системы, но исторически требовали больших начальных инвестиций и могут обесценивать быстро; узлы в слабосвязанной системе обычно представляют собой недорогие стандартные компьютеры, которые могут быть переработаны как независимые машины после выхода из кластера.
Потребляемая мощность также является важным фактором. Сильно связанные системы обычно намного более энергоэффективны, чем кластеры. Это связано с тем, что можно добиться значительной экономии, спроектировав компоненты для совместной работы с самого начала в сильно связанных системах, тогда как в слабосвязанных системах используются компоненты, которые не обязательно предназначались специально для использования в таких системах.
Слабосвязанные системы могут запускать разные операционные системы или версии ОС в разных системах.
Многопроцессорные системы с общей памятью
Объектом рассмотрения является многопроцессорная вычислительная система (МПВС) с общей многомодульной памятью (рисунок). В ее состав входят N процессоров (ЦП) (P) с кэш-памятью (CM), M модулей общей памяти (MM) и коммутаторов K. Число модулей памяти (МП) не превышает число процессоров (M ≤ N).
В такой МПВС возникает конфликт в том случае, когда обращение двух или более ЦП идет одновременно к одному МП [1]. При этом очередность обслуживания определяется службой приоритетов арбитра (AR), входящего в состав коммутатора. Существует три различные приоритета арбитра: фиксированный, циклический и случайный [2–5].
В общем случае, вместо некоторых ЦП стоят устройства ввода/вывода (УВВ) со своими контроллерами прямого доступа к памяти (ПДП или КПДП). Они, как и процессоры, являются активными элементами МПВС. УВВ со своими КПДП можно рассматривать как ЦП ввода-вывода. Каждый МП делается секционированным. Число секций модуля памяти определяется размером блока кэш-памяти (обычно 4 слова). Способ формирования адресов самих МП описан в [6].
Назначение рассматриваемой МПВС – решение стационарного потока задач, состоящего из набора задач нескольких типов. Предполагается, что команды обработки задач заранее записаны в ММ. Данные для каждой задачи поступают через определенное УВВ через фиксированные интервалы времени. Каждая задача характеризуется своим графом, представленным в ярусно-параллельной форме (ЯПФ). Каждый сегмент графа задачи выполняется на одном из ЦП. Сегменты графа могут выполнятся параллельно при наличии свободных ЦП.
Рис. 1. Структура МПВС с общей многомодульной памятью: AR – арбитр; CM – кэш-память; K – коммутатор; MM – модуль общей памяти; P – процессор
Сегмент считается готовым к выполнению, если есть все необходимые данные для его решения. Для распределения готовых к выполнению сегментов задач по ЦП отводится один управляющий процессор (УЦП). Остальные процессоры – рабочие процессоры (РЦП) – предназначены для решения сегментов задач.
Целью построения модели МПВС является определение, справляется ли заданная МПВС с потоком задач, а также определение минимального числа ЦП, необходимого для решения заданного потока задач.
Модель какой-либо системы состоит из набора моделей ее элементов и правил их взаимодействия. Выбор элементов определяется требуемой степенью детализации. Правила взаимодействия моделей должны отражать реальные взаимодействия элементов системы на выбранном уровне детализации [7]. Модель элемента системы может находиться в каком-либо состоянии. Состоянию модели элемента соответствует определенный процесс в соответствующем элементе системы. Число состояний модели определяется числом выполняемых действий соответствующим элементом системы. Модель может переходить из одного состояния в другое, что означает переход элемента системы от выполнения одного действия к другому. Смена состояний модели называется событием. В отличие от реального перехода элемента системы от одного действия к другому, длительность события принимается равной нулю. Алгоритм смены состояний модели элемента определяется алгоритмом функционирования элемента системы.
Каждая модель элемента характеризуется набором своих состояний, алгоритмом смены состояний и уникальным идентификатором, определяющим эту модель элемента в модели системы [8, 9, 10]. Состояние модели всей системы в конкретный момент времени характеризуется набором состояний моделей ее элементов в этот момент. Для учета длительности состояний моделей элементов в модель системы вводится счетчик текущего времени. Значение счетчика может быть выражено в реальных единицах времени, например, в секундах, минутах и так далее, но может быть выражено и в модельных единицах времени. В последнем случае, должно быть установлено соответствие между реальными единицами времени и модельными.
Событие может сопровождаться передачей сообщения другим моделям элементов МПВС. Сообщение должно содержать уникальный идентификатор, характеризующий тип этого сообщения и параметры.
Моделируемыми элементами системы в нашем случае являются: РЦП с кэш-памятью, УП, УВВ и ММ с коммутатором и арбитром. ММ с коммутатором и арбитром – единый элемент в модели, т.к. характеризуются единым набором состояний, определяемым арбитром. Управляющий ЦП получает сигналы от УВВ об окончании записи входных данных задачи и сигналы об окончании решения сегментов от рабочих ЦП. Функциями управляющего ЦП являются выбор готового к выполнению сегмента, выбор свободного ЦП и назначение выбранного сегмента на свободный ЦП. Назначение заключается в отправке сигнала рабочему ЦП с указанием номера задачи и сегмента.
Рабочий ЦП решает назначенный на него сегмент задачи и отправляет сигнал УП об окончании решения сегмента задачи. Для построения алгоритма решения задачи рабочим ЦП приняты следующие допущения:
– РЦП считывает из ММ в кэш соответствующую прикладную программу решения сегмента не распределено в процессе его решения, а перед решением;
– РЦП считывает входные данные сегмента из ММ в кэш-память не распределено в процессе его решения, а перед решением;
– запись результатов в общую память (ОП) осуществляется только после решения сегмента.
Время считывания программы можно определить из следующих предположений. Пусть команда выполняется в среднем за 2 такта. Тогда количество выполняемых команд Nвып за время решения сегмента вычисляется по выражению
, (1)
где 
– время решения сегмента, 
– длительность одного такта.
Число считываемых команд из ОП меньше этого значения, так как одни и те же команды могут, находясь в кэш-памяти, выполняться несколько раз (например, в цикле). Для вычисления числа считываемых из ОП команд введем коэффициент цикличности КЦИКЛ (например, 2). Тогда число считываемых из ОП команд NСЧИТ вычисляется по выражению
. (2)
Если предположить, что средняя длина команды равняется одному слову, то это значение Nсчит будет равно числу считываемых слов.
Команды и входные данные сегмента считываются блоками. Последовательно идущие блоки располагаются в различных МП, доступом к каждому управляет соответствующий арбитр, входящий в состав коммутатора. Время, необходимое арбитру для выбора кандидата для передачи в МП, принято равным нулю.
Приход задач в МПВС осуществляется через УВВ. Задача каждого типа приходит через определенное УВВ, т.е. распределение задач по УВВ осуществляется статически. Перед записью новых входных данных УВВ считывает результаты решения предыдущей задачи. Взаимодействие УВВ с ОП осуществляется по словам в режиме ПДП на частоте работы ОП. Время TIN, требуемое для записи новых входных данных задачи объёмом 
слов, определяется по выражению
. (3)
Время TOUT , требуемое для считывания результатов решения задачи объёмом VOUT слов, определяется по выражению
. (4)
Таким образом, можно построить имитационную модель МПВС с общей многомодульной памятью, используя допущения, принятые для рабочих ЦП и используя выражения 1–4 для определения времен состояний моделей элементов МПВС.
Linux и симметричная многопроцессорная система (исходники)
Быстродействие системы Linux вы можете увеличить разными способами, и один из наиболее популярных — увеличить производительность процессора. Очевидное решение — использовать процессор с большей тактовой частотой, но для любой технологии существует физическое ограничение, когда тактовый генератор просто не может работать быстрее. При достижении этого предела вы можете использовать гораздо лучший подход и применить несколько процессоров. К сожалению, быстродействие имеет нелинейную зависимость от совокупности параметров отдельных процессоров.
Прежде чем обсуждать применение многопроцессорной обработки в Linux, давайте взглянем на ее историю.
Один поток команд, один поток данных (SISD — Single Instruction, Single Data) — типичная однопроцессорная архитектура. Многопроцессорная архитектура Много потоков команд, много потоков данных (MIMD — Multiple Instruction, Multiple Data) содержит отдельные процессоры, оперирующие независимыми данными (параллелизм управления). Наконец, Один поток команд, много потоков данных (SIMD — Single Instruction, Multiple Data) имеет ряд процессоров, оперирующих разнотипными данными (параллелизм данных).
Многопроцессорная обработка зародилась в середине 1950-х в ряде компаний, некоторые из которых вы знаете, а некоторые, возможно, уже забыли (IBM, Digital Equipment Corporation, Control Data Corporation). В начале 1960-х Burroughs Corporation представила симметричный мультипроцессор типа MIMD с четырьмя CPU, имеющий до шестнадцати модулей памяти, соединенных координатным соединителем (первая архитектура SMP). Широко известный и удачный CDC 6600 был представлен в 1964 и обеспечивал CPU десятью подпроцессорами (периферийными процессорами). В конце 1960-х Honeywell выпустил другую симметричную мультипроцессорную систему из восьми CPU Multics.
В то время как многопроцессорные системы развивались, технологии также шли вперед, уменьшая размеры процессоров и увеличивая их способности работать на значительно большей тактовой частоте. В 1980-х такие компании, как Cray Research, представили многопроцессорные системы и UNIX®-подобные операционные системы, которые могли их использовать (CX-OS).
В конце 1980-х с популярностью однопроцессорных персональных компьютеров, таких как IBM PC, наблюдался упадок в многопроцессорных системах. Но сейчас, двадцать лет спустя, многопроцессорная обработка вернулась к тем же самым персональным компьютерам в виде симметричной многопроцессорной обработки.
Джин Амдаль (Gene Amdahl), компьютерный архитектор и сотрудник IBM, разрабатывал в IBM компьютерные архитектуры, создал одноименную фирму, Amdahl Corporation и др. Но известность ему принес его закон, в котором рассчитывается максимально возможное улучшение системы при улучшении ее части. Закон используется, главным образом, для вычисления максимального теоретического улучшения работы системы при использовании нескольких процессоров (смотри Рисунок 1).
Используя уравнение, показанное на Рисунке 1, вы можете вычислить максимальное улучшение производительности системы, использующей N процессоров и фактор F , который указывает, какая часть системы не может быть распараллелена (часть системы, которая последовательна по своей природе). Результат приведен на Рисунке 2.
Верхняя линия на Рисунке 2 показывает число процессоров. В идеале это то, что вы хотели бы увидеть после добавления дополнительных процессоров для решения задачи. К сожалению, из-за того что не все в задаче может быть распараллелено и есть непроизводительные издержки в управлении процессорами, ускорение оказывается немного меньше. Внизу (лиловая линия) — случай задачи, которая на 90% последовательна. Лучшему случаю на этом графике соответствует коричневая линия, которая изображает задачу, которая на 10% последовательна и, соответственно, на 90% — параллелизуема. Даже в этом случае десять процессоров работают совсем не намного лучше, чем пять.
Архитектура SMP — одна из тех, где два или более идентичных процессоров соединены друг с другом посредством разделяемой памяти. У всех них одинаковый доступ к разделяемой памяти (одинаковое время ожидания доступа к пространству памяти). Противоположностью ей является архитектура неоднородного доступа к памяти (NUMA — Non-Uniform Memory Access). Например, у каждого процессора есть своя собственная память и доступ к разделяемой памяти с разным временем ожидания.
Ранние SMP системы Linux были слабосвязанными многопроцессорными системами, то есть построенными из нескольких отдельных систем, связанных высокоскоростным соединением (таким как 10G Ethernet, Fibre Channel или Infiniband). Другое название такого типа архитектуры — кластер (смотрите Рисунок 3), для которого популярным решением остается проект Linux Beowulf. Кластеры Linux Beowulf могут быть построены из доступного оборудования и обычного сетевого соединения, такого как Ethernet.
Построение систем со слабосвязанной многопроцессорной архитектурой просто (спасибо проектам вроде Beowulf), но имеет свои ограничения. Создание большой многопроцессорной сети может потребовать значительных мощностей и места. Более серьезное препятствие — материал канала связи. Даже с высокоскоростной сетью, такой как 10G Ethernet, есть предел масштабируемости системы.
Сильносвязанная многопроцессорная обработка относится к обработке на уровне кристалла (CMP — chip-level multiprocessing). Представьте слабосвязанную архитектуру, уменьшенную до уровня кристалла. Это и есть идея сильносвязанной многопроцессорной обработки (также называемой многоядерным вычислением). На одной интегральной микросхеме несколько кристаллов, общая память и соединение образуют хорошо интегрированное ядро для многопроцессорной обработки (смотрите Рисунок 4).
|
Рисунок 4. Сильносвязанная архитектура многопроцессорной обработки
В CMP несколько CPU связаны общей шиной с разделяемой памятью (кэш второго уровня). Каждый процессор также имеет свою собственную быстродействующую память (кэш первого уровня). Сильносвязанная природа CMP позволяет очень короткие физические расстояния между процессорами и памятью и, вследствие этого, минимальное время ожидания доступа к памяти и более высокую производительность. Такой тип архитектуры хорошо работает в многопоточных приложениях, где потоки могут быть распределены между процессорами и выполняться параллельно. Это называется параллелизм на уровне потоков (TPL — thread-level parallelism).
Принимая во внимание популярность этой многопроцессорной архитектуры, многие производители выпускают устройства CMP. В Таблице 1 приведены некоторые популярные варианты с поддержкой Linux.
Таблица 1. Выборка устройств CMP
| Производитель | Устройство | Описание |
|---|---|---|
| IBM | POWER4 | SMP, два CPU |
| IBM | POWER5 | SMP, два CPU, четыре параллельных потока |
| AMD | AMD X2 | SMP, два CPU |
| Intel® | Xeon | SMP, два или четыре CPU |
| Intel | Core2 Duo | SMP, два CPU |
| ARM | MPCore | SMP, до четырех CPUs |
| IBM | Xenon | SMP, три Power PC CPU |
| IBM | Cell Processor | Асимметричная многопроцессорная обработка (ASMP —Asymmetric multiprocessing), девять CPU |
Для того чтобы использовать SMP с Linux на совместимом с SMP оборудовании, необходимо правильно настроить ядро. Опция CONFIG_SMP должна быть включена во время настройки ядра, чтобы ядро знало об SMP. Если такое ядро будет работать на многопроцессорном хосте, вы сможете определить количество процессоров и их тип с помощью файловой системы proc.
Сначала вы получаете число процессоров из файла cpuinfo в /proc, используя grep . Как видно из Листинга 1, вы используете опцию — счетчик ( -c ) строк, начинающихся со слова processor . Приведено также содержимое файла cpuinfo . В качестве примера взята материнская плата Xeon на двух кристаллах.
Когда только появился Linux 2.0, поддержка SMP состояла из основной системы блокировки, которая упорядочивала доступ в системе. Позднее небольшой прогресс в поддержке SMP был, но только с ядром 2.6 наконец проявилась вся сила SMP.
Ядро 2.6 представило новый 0(1) планировщик, который включал лучшую поддержку для систем SMP. Ключевой была возможность балансировать нагрузку на все доступные CPU, по мере сил избегая переключения процессов между процессорами для более эффективного использования кэша. Что касается производительности кэша, вспомните из Рисунка 4, что когда задача взаимодействует с одним CPU, перемещение ее на другой требует вовлечения кэша. Это увеличивает время ожидания доступа к памяти задачи, пока ее данные находятся в кэше нового CPU.
|
Ядро 2.6 сохраняет пару runqueue для каждого процессора (истекший и активный runqueue). Каждый runqueue поддерживает 140 приоритетов, из которых 100 используется для задач в реальном времени, а остальные 40 для пользовательских задач. Задачам даются отрезки времени для выполнения, а когда они используют свое время, они перемещаются из активного runqueue в истекший. Таким образом осуществляется равноправный доступ к CPU для всех задач (блокировка только отдельных CPU).
С очередью задач на каждом CPU работа может быть сбалансирована, давая взвешенную нагрузку всех CPU в системе. Каждые 200 миллисекунд планировщик выполняет балансировку загрузки, чтобы перераспределить задания и сохранить баланс в комплексе процессоров.
В ядре Linux была проделана большая работа для развития SMP, но операционной системы, самой по себе, недостаточно. Вспомните, что сила SMP заключается в TLP. Отдельные монолитные (одно-поточные) программы не могут использовать SMP, но SMP может использоваться в программах, которые состоят из многих потоков, которые могут быть распределены между ядрами. Пока один поток ожидает выполнения операции I/O, другой может делать полезную работу. Таким образом, потоки работают, перекрывая время ожидания друг друга.
Потоки стандарта Portable Operating System Interface (POSIX) (интерфейс переносимой операционной системы) являются прекрасным способом построить поточные приложения, которые могут использовать SMP. Потоки стандарта POSIX обеспечивают механизм работы с потоками, а также общую память. Когда программа активизируется, создается некоторое количество потоков, каждый из которых поддерживает свой собственный стек (локальные переменные и состояние), но разделяет пространство данных родителя. Все созданные потоки разделяют это же самое пространство данных, но именно здесь кроется проблема.
Чтобы поддерживать многопоточный доступ к разделяемой памяти, требуются механизмы координирования. POSIX предоставляет функцию взаимного исключения для создания критических секций , которые устанавливают исключительный доступ к объекту (участку памяти) только для одного потока. Если этого не сделать, может повредиться память из-за несинхронизованных манипуляций, производимых несколькими потоками. Листинг 2 иллюстрирует создание критической секции с помощью взаимного исключения POSIX.
Листинг 2. Использование pthread_mutex_lock и unlock для создания критических секций
Если несколько потоков пытаются заблокировать семафор после начального вызова наверху, они блокируются, и их запросы ставятся в очередь, пока не выполнится вызов pthread_mutex_unlock .
Когда несколько ядер в процессоре работает параллельно для ядра ОС, желательно избегать совместного использования данных, которые специфичны для данного ядра процессора. По этой причине ядро 2.6 представило концепцию переменных для каждого ядра, которые связаны с отдельными CPU. Это позволяет объявлять переменные для CPU, которые наиболее часто используются именно этим CPU, что минимизирует требования блокировок и улучшает выполнение.
Определение переменных отдельного ядра производится при помощи макроса DEFINE_PER_CPU , которому вы передаете тип и имя переменной. Поскольку макрос поступает как l-value, здесь же вы можете инициализировать ее. В следующем примере (из ./arch/i386/kernel/smpboot.c) определяется переменная, представляющая состояние для каждого CPU в системе.
Макрос создает массив переменных, одну на каждый экземпляр CPU. Для получения переменной отдельного CPU используется макрос per_cpu вместе с функцией smp_processor_id , возвращающей текущий идентификатор CPU, для которого в данный момент выполняется программа.
Ядро предоставляет другие функции для блокировки каждого CPU и динамического выделения переменных. Эти функции можно найти в ./include/linux/percpu.h.
Когда частота процессора достигает своего предела, для увеличения производительности обычно просто добавляют еще процессоры. Раньше это означало добавить больше процессоров к материнской плате или объединить в кластер несколько независимых компьютеров. Сегодня многопроцессорная обработка на уровне кристалла предоставляет больше процессоров на одном кристалле, давая еще большее быстродействие путем уменьшения времени ожидания памяти.
Системы SMP вы найдете не только на серверах, но и на десктопах, особенно с внедрением виртуализации. Как многие передовые технологии, Linux предоставляет поддержку для SMP. Ядро выполняет свою часть по оптимизации загрузки доступных CPU (от потоков до виртуализованных операционных систем). Все, что остается, это убедиться, что приложение может быть в достаточной мере разделено на потоки, чтобы использовать силу SMP.
