Главная
База знаний "Allbest"
Программирование, компьютеры и кибернетика
Параллельные вычислительные системы
Параллельные вычислительные системы
Классификация параллельных вычислительных систем. Существенные понятия и компоненты параллельных компьютеров, их компоненты. Особенности классификаций Хендера, Хокни, Флинна, Шора. Системы с разделяемой и локальной памятью. Способы разделения памяти.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 18.07.2012 |
| Размер файла | 331,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Филиал Нижегородский
Курсовая работа
По дисциплине:
Вычислительные системы
Тема:
Параллельные вычислительные системы
Студента
Белоус Михаил Владимирович
Содержание
- Введение
- 1. Классификация параллельных вычислительных систем
- 2. Системы с разделяемой и локальной памятью
- Заключение
- Глоссарий
- Список использованных источников
Введение
О том, что где-то существуют некие мистические "очень мощные" компьютеры слышал, наверное, каждый. В самом деле, не так давно было много разговоров о поставке в Гидрометеоцентр России могучих компьютеров фирмы Cray Research. В ноябре 1999 года состоялось официальное открытие Межведомственного суперкомпьютерного центра, который в настоящий момент имеет компьютер с 768 процессорами. Опять же, если компьютер с именем Deep Blue обыграл самого Гарри Каспарова, то он, согласитесь - и здесь интуиция Вас не подвела, ну никак не может быть простой персоналкой.
Для многих подобные компьютеры так и остаются тайной за семью печатями, некой TERRA INCOGNITA, с которой ассоциации всегда связаны с чем-то большим: огромные размеры, большие задачи, крупные фирмы и компании, невероятные скорости работы или что-то иное, но обязательно это будет "на грани", для чего "обычного" явно мало, а подойдет только "супер", суперкомпьютер или супер-ЭВМ. В этом интуитивном восприятии есть изрядная доля истины, поскольку к классу супер-ЭВМ принадлежат лишь те компьютеры, которые имеют максимальную производительность в настоящее время.
Быстрое развитие компьютерной индустрии определяет относительность данного понятия - то, что десять лет назад можно было назвать суперкомпьютером, сегодня под это определение уже не попадает. Например, производительность персональных компьютеров, использующих Pentium-III/500MHz, сравнима с производительностью суперкомпьютеров начала 70-х годов, однако по сегодняшним меркам суперкомпьютерами не являются ни те, ни другие.
В любом компьютере все основные параметры тесно связаны. Трудно себе представить универсальный компьютер, имеющий высокое быстродействие и мизерную оперативную память, либо огромную оперативную память и небольшой объем дисков. Следуя логике, делаем вывод: супер-ЭВМ это компьютеры, имеющие в настоящее время не только максимальную производительность, но и максимальный объем оперативной и дисковой памяти (вопрос о специализированном ПО, с помощью которого можно эффективно всем этим воспользоваться, пока оставим в стороне).
Так о чем же речь и какие суперкомпьютеры существуют в настоящее время в мире? Вот лишь несколько параметров, дающих достаточно красноречивую характеристику машин этого класса. Компьютер ASCI WHITE, занимающий первое место в списке пятисот самых мощных компьютеров мира, объединяет 8192 процессора Power 3 с общей оперативной памятью в 4 Терабайта и производительностью более 12 триллионов операций в секунду.
Супер-ЭВМ и сверхвысокая производительность: зачем?
Простые расчеты показывают, что конфигурации подобных систем могут стоить не один миллион долларов США - ради интереса прикиньте, сколько стоят, скажем, лишь 4 Тбайта оперативной памяти? Возникает целый ряд естественных вопросов: какие задачи настолько важны, что требуются компьютеры стоимостью несколько миллионов долларов? Или, какие задачи настолько сложны, что хорошего Пентиума не достаточно? На эти и подобные им вопросы хотелось бы найти разумные ответы.
Для того чтобы оценить сложность решаемых на практике задач, возьмем конкретную предметную область, например, оптимизацию процесса добычи нефти. Имеем подземный нефтяной резервуар с каким-то число пробуренных скважин: по одним на поверхность откачивается нефть, по другим обратно закачивается вода. Нужно смоделировать ситуацию в данном резервуаре, чтобы оценить запасы нефти или понять необходимость в дополнительных скважинах.
2500 миллиардов арифметических операций для выполнения одного лишь расчета! А изменение параметров модели? А отслеживание текущей ситуации при изменении входных данных? Подобные расчеты необходимо делать много раз, что накладывает очень жесткие требования на производительность используемых вычислительных систем.
1. Классификация параллельных вычислительных систем
Архитектуры параллельных компьютеров могут значительно отличаться друг от друга. Рассмотрим некоторые существенные понятия и компоненты параллельных компьютеров. Параллельные компьютеры состоят из трех основных компонент:
· процессоры;
· модули памяти;
· коммутирующая сеть.
Можно рассмотреть и более изощренное разбиение параллельного компьютер на компоненты, однако, данные три компоненты лучше всего отличают один параллельный компьютер от другого. Процессоры осуществляют обработку информации, работая параллельно. Модули памяти хранят данные для обработки, промежуточные и конечные результаты. Коммутирующая сеть обеспечивает связь процессоров с другими процессорами или памятью. Коммутирующая сеть собственно и создает параллельный компьютер, без нее речь могла бы идти лишь о совокупности компьютеров.
Классификация по числу потоков команд/данных.
Это одна из первых классификаций, ссылки на которую наиболее часто встречаются в литературе, была предложена М. Флинном в конце 60-х годов прошлого века. Она базируется на понятиях двух потоков: команд и данных.
SISD (Single Instruction Single Data). Такую архитектуру имеют все однопроцессорные системы.
MISD (Multiple Instruction Single Data). Эта архитектура не получила распространения, хотя формально может существовать. М. Флинн не смог привести ни одного примера реально существующей системы, работающей на этом принципе. Некоторые авторы в качестве представителей такой архитектуры называют векторно-конвейерные компьютеры, однако такая точка зрения не получила широкой поддержки. Считается, что есть только один представитель данного семейства - мультипроцессор C. mpp университета Карнеги-Мелон. Но он может работать как в MISD, так и в MIMD режимах, причем, второй считается штатным.
SIMD (Single Instruction Multiple Data). Кузьминский М. Архитектура S2MP - свежий взгляд на cc-NUMA // М.: Открытые системы, 2007г, 357 с. SIMD компьютер (рисунок 1) имеет N идентичных синхронно работающих процессоров, N потоков данных и один поток команд.
Каждый процессор обладает собственной локальной памятью. Сеть, соединяющая процессоры, обычно имеет регулярную топологию.
Рисунок 1. SIMD-архитектура.
MIMD (Multiple Instruction Multiple Data). Антонов А.С. Введение в параллельные вычисления, М.: Изд-во МГУ, 2002, 346 с. MIMD компьютер имеет N процессоров, N потоков команд и N потоков данных. Каждый процессор функционирует под управлением собственного потока команд. Схема MIMD-модели показана на рисунке 2.
Рисунок 2. MIMD-архитектура.
SISD-машины Кузьминский М. Векторно-параллельные суперкомпьютеры NEC // М.: Открытые системы, 2003 г, 246 с. являются обычными последовательными вычислительными устройствами, а MISD-машины не производятся. Поэтому параллельные компьютеры могут относится лишь к двум категориям. Конечно, такая классификация не отображает всего многообразия современных систем с параллельной обработкой данных, а скорее определяет, является система параллельной или нет. Для более детального описания параллельных систем применяют более сложные системы классификации.
Классификация по организации памяти. Антонов А.С. Введение в параллельные вычисления, М.: Изд-во МГУ, 2002, 346 с.
Другим свойством, различающим параллельные компьютеры, является способ доступа к модулям памяти, то есть имеет ли каждый процессор локальную память и обращается к другим блокам памяти, используя коммутирующую сеть, или коммутирующая сеть соединяет все процессоры с общей памятью. Исходя из способа доступа к памяти, различают следующие (довольно условные) типы параллельных архитектур:
Компьютеры с распределенной памятью (Distributed memory). Кузьминский М. Векторно-параллельные суперкомпьютеры NEC // М.: Открытые системы, 2003 г, 246 с. Каждый процессор имеет доступ только к локальной собственной памяти. Процессоры объединены в сеть (рисунок 3). Доступ к удаленной памяти возможен только с помощью системы обмена сообщениями.
Рисунок 3. Системы с распределенной памятью.
Компьютеры с общей (разделяемой) памятью (True shared memory). Кузьминский М. Архитектура S2MP - свежий взгляд на cc-NUMA // М.: Открытые системы, 2007г, 357 с. Каждый процессор компьютера обладает возможностью прямого доступа к общей памяти, используя общую шину (возможно, реализованную на основе высокоскоростной сети). В таких компьютерах нельзя существенно увеличить число процессоров, поскольку при этом происходит резкое увеличение числа конфликтов доступа к шине. Схема подобной системы приведена на рисунке 4.
Рисунок 4. Системы с разделяемой памятью.
В некоторых архитектурах каждый процессор имеет как прямой доступ к общей памяти, так и собственную локальную память (рисунок 5).
Рисунок 5. Системы с неоднородной памятью.
Компьютеры с виртуальной общей (разделяемой) памятью (Virtual shared memory). Мячев А.А. Спецификация многопроцессорных систем компании Intel // М.: Открытые системы, 2005, 336 с. В таких системах общая память как таковая отсутствует. Каждый процессор имеет собственную локальную память. Он может обращаться к локальной памяти других процессоров, используя "глобальный адрес". Если "глобальный адрес" указывает не на локальную память, то доступ к памяти реализуется по сети, соединяющей процессоры.
Системы с виртуальной разделяемой памятью имеют ту же схему, что и системы с распределенной памятью. Их отличие состоит в том, что в системах с виртуальной разделяемой памятью процессоры при необходимости взаимодействия не обмениваются сообщениями, а генерируют обращение к памяти другого процессора, как к своей. Обращение к "чужой" памяти идет на порядок (или даже более) медленнее.
В таких системах отдельную проблему представляет согласование кэшей всех процессоров. Этот вопрос будет рассмотрен ниже.
Классификация Хэндлера.
Предложена в 1977 году. В основу классификации В. Хендлер закладывает явное описание возможностей параллельной и конвейерной обработки информации вычислительной системой с помощью численных характеристик. При этом он намеренно не рассматривает различные способы связи между процессорами и блоками памяти и считает, что коммуникационная сеть может быть нужным образом сконфигурирована и будет способна выдержать предполагаемую нагрузку. Предложенная классификация базируется на различии между тремя уровнями обработки данных в процессе выполнения программ:
· уровень выполнения программы - опираясь на счетчик команд и некоторые другие регистры, устройство управления (УУ) производит выборку и дешифрацию команд программы;
· уровень выполнения команд - арифметико-логическое устройство компьютера (АЛУ) исполняет команду, выданную ему устройством управления;
· уровень битовой обработки - все элементарные логические схемы процессора (ЭЛС) разбиваются на группы, необходимые для выполнения операций над одним двоичным разрядом.
Например, процессор CDC 6600 имеет ЦПУ с десятью процессорами ввода/вывода. Один управляющий блок контролирует одно АЛУ с длиной слова 60 бит. АЛУ имеет 10 функциональных блоков, которые могут быть организованны в конвейер.10 процессоров ввода/вывода могут работать параллельно друг с другом и с ЦПУ. Каждый процессор ввода/вывода содержит 12-ти битное АЛУ. Структура такой вычислительной системы описывается следующим образом:
CDC 6600I/O = (10, 1,12),
CDC 6600main = (1, 1Ч10, 60),
CDC 6600 = (I/O processors) Ч (central processor) = (10, 1,12) Ч (1, 1 Ч10, 60).
Процессор Cray-1 - это 64-х битный процессор, его АЛУ имеет 12 функциональных блоков, восемь из которых могут быть связаны в конвейер, различные функциональные устройства имеют от 1 до 14 сегментов, которые также могут работать в конвейере. Описатель в этом случае будет иметь следующий вид:
Cray?1 = (1, 12Ч8, 64 *Ч (1?14)).
Классификация Джонсона.
Е. Джонсон предложил проводить классификацию MIMD архитектур на основе структуры памяти и реализации механизма взаимодействия и синхронизации между процессорами. Мячев А.А. Спецификация многопроцессорных систем компании Intel // М.: Открытые системы, 2005, 336 с.
По структуре оперативной памяти существующие вычислительные системы делятся на две большие группы: либо это системы с общей памятью, прямо адресуемой всеми процессорами, либо это системы с распределенной памятью, каждая часть которой доступна только одному процессору. Одновременно с этим, и для межпроцессорного взаимодействия существуют две альтернативы: через разделяемые переменные или с помощью механизма передачи сообщений. Исходя из таких предположений, можно получить четыре класса MIMD архитектур, уточняющих систематику Флинна:
GMSV: общая память - разделяемые переменные;
DMSV: распределенная память - разделяемые переменные;
DMPP: распределенная память - передача сообщений;
GMMP: общая память - передача сообщений.
Опираясь на такое деление, Джонсон вводит названия для некоторых классов. Так вычислительные системы, использующие общую разделяемую память для межпроцессорного взаимодействия и синхронизации, он называет системами с разделяемой памятью, например, CRAY Y-MP (по его классификации это класс 1). Системы, в которых память распределена по процессорам, а для взаимодействия и синхронизации используется механизм передачи сообщений он называет архитектурами с передачей сообщений, например NCube, (класс 3). Системы с распределенной памятью и синхронизацией через разделяемые переменные, как в BBN Butterfly, называются гибридными архитектурами (класс 2).
В качестве уточнения классификации автор отмечает возможность учитывать различные виды связи между процессорами: общая шина, переключатели, разнообразные сети и т.п.
Классификация Хокни.
Р. Хокни Мячев А.А. Спецификация многопроцессорных систем компании Intel // М.: Открытые системы, 2005, 336 с. - известный английский специалист в области параллельных вычислительных систем, разработал свой подход к классификации, введенной им для систематизации компьютеров, попадающих в класс MIMD по систематике Флинна.
Как отмечалось выше (см. классификацию Флинна), класс MIMD чрезвычайно широк, причем наряду с большим числом компьютеров он объединяет и целое множество различных типов архитектур. Хокни, пытаясь систематизировать архитектуры внутри этого класса, получил иерархическую структуру, представленную на рисунок 6.
Рисунок 6. Классификация Хокни.
Основная идея классификации состоит в следующем. Множественный поток команд может быть обработан двумя способами: либо одним конвейерным устройством обработки, работающем в режиме разделения времени для отдельных потоков, либо каждый поток обрабатывается своим собственным устройством. Первая возможность используется в MIMD компьютерах, которые автор называет конвейерными (например, процессорные модули в Denelcor HEP). Архитектуры, использующие вторую возможность, в свою очередь опять делятся на два класса:
MIMD компьютеры, в которых возможна прямая связь каждого процессора с каждым, реализуемая с помощью переключателя;
MIMD компьютеры, в которых прямая связь каждого процессора возможна только с ближайшими соседями по сети, а взаимодействие удаленных процессоров поддерживается специальной системой маршрутизации через процессоры-посредники.
Далее, среди MIMD машин с переключателем Хокни выделяет те, в которых вся память распределена среди процессоров как их локальная память (например, PASM, PRINGLE). В этом случае общение самих процессоров реализуется с помощью очень сложного переключателя, составляющего значительную часть компьютера. Такие машины носят название MIMD машин с распределенной памятью. Если память это разделяемый ресурс, доступный всем процессорам через переключатель, то такие MIMD являются системами с общей памятью (CRAY X-MP, BBN Butterfly). В соответствии с типом переключателей можно проводить классификацию и далее: простой переключатель, многокаскадный переключатель, общая шина.
Многие современные вычислительные системы имеют как общую разделяемую память, так и распределенную локальную. Такие системы автор рассматривает как гибридные MIMD c переключателем.
При рассмотрении MIMD машин с сетевой структурой считается, что все они имеют распределенную память, а дальнейшая классификация проводится в соответствии с топологией сети: звездообразная сеть (lCAP), регулярные решетки разной размерности (Intel Paragon, CRAY T3D), гиперкубы (NCube, Intel iPCS), сети с иерархической структурой, такой, как деревья, пирамиды, кластеры (Cm*, CEDAR) и, наконец, сети, изменяющие свою конфигурацию. Борисов М. UNIX-кластеры // М.: Открытые системы, 2005г, 237 с.
Заметим, что если архитектура компьютера спроектирована с использованием нескольких сетей с различной топологией, то, по всей видимости, по аналогии с гибридными MIMD с переключателями, их стоит назвать гибридными сетевыми MIMD, а использующие идеи разных классов - просто гибридными MIMD. Типичным представителем последней группы, в частности, является компьютер Connection Machine 2, имеющим на внешнем уровне топологию гиперкуба, каждый узел которого является кластером процессоров с полной связью.
Классификация Шора.
Классификация Дж. Шора, появившаяся в начале 1973 году, интересна тем, что представляет собой попытку выделения типичных способов компоновки вычислительных систем на основе фиксированного числа базисных блоков: устройства управления, арифметико-логического устройства, памяти команд и памяти данных. Дополнительно предполагается, что выборка из памяти данных может осуществляться словами, то есть выбираются все разряды одного слова, и/или битовым слоем - по одному разряду из одной и той же позиции каждого слова (иногда эти два способа называют горизонтальной и вертикальной выборками соответственно). Конечно же, при анализе данной классификации надо делать скидку на время ее появления, так как предусмотреть невероятное разнообразие параллельных систем настоящего времени было в принципе невозможно. Итак, согласно классификации Шора все компьютеры разбиваются на шесть классов, которые он так и называет: машина типа I, II и т.д.
Машина I - это вычислительная система, которая содержит устройство управления, арифметико-логическое устройство, память команд и память данных с пословной выборкой. Считывание данных осуществляется выборкой всех разрядов некоторого слова для их параллельной обработки в арифметико-логическом устройстве. Состав АЛУ специально не оговаривается, что допускает наличие нескольких функциональных устройств, быть может конвейерного типа. По этим соображениям в данный класс попадают как классические последовательные машины (IBM 701, PDP-11, VAX 11/780), так и конвейерные скалярные (CDC 7600) и векторно-конвейерные (CRAY-1).
Если в машине I осуществлять выборку не по словам, а выборкой содержимого одного разряда из всех слов, то получим машину II. Слова в памяти данных по прежнему располагаются горизонтально, но доступ к ним осуществляется иначе. Если в машине I происходит последовательная обработка слов при параллельной обработке разрядов, то в машине II - последовательная обработка битовых слоев при параллельной обработке множества слов.
Структура машины II лежит в основе ассоциативных компьютеров (например, центральный процессор машины STARAN), причем фактически такие компьютеры имеют не одно арифметико-логическое устройство, а множество сравнительно простых устройств поразрядной обработки. Другим примером служит матричная система ICL DAP, которая может одновременно обрабатывать по одному разряду из 4096 слов.
Если объединить принципы построения машин I и II, то получим машину III. Эта машина имеет два арифметико-логических устройства - горизонтальное и вертикальное, и модифицированную память данных, которая обеспечивает доступ как к словам, так и к битовым слоям. Впервые идею построения таких систем в 1960 году выдвинул У. Шуман, называвший их ортогональными (если память представлять как матрицу слов, то доступ к данным осуществляется в направлении, "ортогональном" традиционному - не по словам (строкам), а по битовым слоям (столбцам)). В принципе, как машину STARAN, так и ICL DAP можно запрограммировать на выполнение функций машины III, но поскольку они не имеют отдельных АЛУ для обработки слов и битовых слоев, отнести их к данному классу нельзя. Полноправными представителями машин класса III являются вычислительные системы семейства OMEN-60 фирмы Sanders Associates, построенные в прямом соответствии с концепцией ортогональной машины.
2. Системы с разделяемой и локальной памятью
На рисунке 7 показаны различные способы организации разделяемой памяти с упорядочением по возможному числу параллельно работающих процессоров.
Рисунок 7. Способы разделения памяти.
· Разделяемый кэш. Это самый простой способ организации многопроцессорной системы. Процессоры имеют не только общую память, но и общий кэш, с которым они соединены высокоскоростным коммутатором. Так как кеш является общим, то нет необходимости использовать сложные алгоритмы согласования данных. Но простота эта является лишь видимой, так как требуется дополнительный коммутатор, причем производительность его должна быть очень высокой, чтобы не слишком увеличивать латентность доступа к кэшу. Такие системы не выпускаются в настоящее время.
· Централизованная память. Первая возникшая проблема - большое число конфликтов при обращении к общей шине. Остроту этой проблемы удалось частично снять разделением памяти на блоки, подключение к которым с помощью коммутаторов позволило распараллелить обращения от различных процессоров. Однако и в таком подходе неприемлемо большими казались накладные расходы для систем более чем с 32-мя процессорами. Кроме того, для таких систем появляется проблема когерретности кэшей. Она заключается в том, что одна и та же ячейка памяти может содержаться в нескольких кэшах одновременно. Тогда ее модификация в одном из кэшей приводит к несогласованности кэшей - остальные кэши содержат неверное значение. Какое значение окажется в памяти, нельзя предсказать. Такое положение дел нельзя допустить, поэтому используются системы согласования кэшей.
· Разделяемая память. Такая схема ведет к неоднородности памяти с точки зрения каждого из процессоров. Обращения к локальной памяти процессора идут гораздо быстрее, чем к удаленной памяти.
Современные системы SMP архитектуры состоят, как правило, из нескольких однородных серийно выпускаемых микропроцессоров и массива общей памяти, подключение к которой производится либо с помощью общей шины, либо с помощью коммутатора.
Наличие общей памяти значительно упрощает организацию взаимодействия процессоров между собой и упрощает программирование, поскольку параллельная программа работает в едином адресном пространстве. Однако за этой кажущейся простотой скрываются большие проблемы, присущие системам этого типа. Все они, так или иначе, связаны с оперативной памятью. Дело в том, что в настоящее время даже в однопроцессорных системах самым узким местом является оперативная память, скорость работы которой значительно отстала от скорости работы процессора. Для того чтобы сгладить этот разрыв, современные процессоры снабжаются скоростной буферной памятью (кэш-памятью), скорость работы которой значительно выше, чем скорость работы основной памяти. В качестве примера приведем данные измерения пропускной способности кэш-памяти и основной памяти для персонального компьютера на базе процессора Pentium III 1000 Мгц.
В данном процессоре кэш-память имеет два уровня:
L1 (буферная память команд) - объем 32 Кб, скорость обмена 9976 Мб/сек;
L2 (буферная память данных) - объем 256 Кб, скорость обмена 4446 Мб/сек.
В то же время скорость обмена с основной памятью составляет всего 255 Мб/сек. Это означает, что для 100% согласованности со скоростью работы процессора (1000 Мгц) скорость работы основной памяти должна быть в 40 раз выше!
Очевидно, что при проектировании многопроцессорных систем эти проблемы еще более обостряются, так как память должна быть достаточно быстродействующей, чтобы обеспечивать данными сразу несколько процессоров. Помимо хорошо известной проблемы конфликтов при обращении к общей шине памяти возникла и новая проблема, связанная с иерархической структурой организации памяти современных компьютеров.
Мультипроцессорная когерентность кэш-памяти.
Проблема, о которой идет речь, возникает из-за того, что значение элемента данных в памяти, хранящееся в двух разных процессорах, доступно этим процессорам только через их индивидуальные кэши. Проблема когерентности памяти для мультипроцессоров и устройств ввода/вывода имеет много аспектов. Обычно в малых мультипроцессорах используется аппаратный механизм, называемый протоколом, позволяющий решить эту проблему. Такие протоколы называются протоколами когерентности кэш-памяти. Существуют два класса таких протоколов:
Directory based. Протоколы на основе справочника. Информация о состоянии блока физической памяти содержится только в одном месте, называемом справочником (физически справочник может быть распределен по узлам системы).
Snooping. Протоколы наблюдения. Каждый кэш, который содержит копию данных некоторого блока физической памяти, имеет также соответствующую копию служебной информации о его состоянии. Централизованная система записей отсутствует. Обычно кэши расположены на общей (разделяемой) шине и контроллеры всех кэшей наблюдают за шиной (просматривают ее) для определения того, не содержат ли они копию соответствующего блока.
В мультипроцессорных системах, использующих микропроцессоры с кэш-памятью, подсоединенные к централизованной общей памяти, протоколы наблюдения приобрели популярность, поскольку для опроса состояния кэшей они могут использовать заранее существующее физическое соединение - шину памяти.
Неформально, проблема когерентности памяти состоит в необходимости гарантировать, что любое считывание элемента данных возвращает последнее по времени записанное в него значение. Это определение не совсем корректно, поскольку невозможно требовать, чтобы операция считывания мгновенно видела значение, записанное в этот элемент данных некоторым другим процессором. Если, например, операция записи на одном процессоре предшествует операции чтения той же ячейки на другом процессоре в пределах очень короткого интервала времени, то невозможно гарантировать, что чтение вернет записанное значение данных, поскольку в этот момент времени записываемые данные могут даже не покинуть процессор. Вопрос о том, когда точно записываемое значение должно быть доступно процессору, выполняющему чтение, определяется выбранной моделью согласованного (непротиворечивого) состояния памяти и связан с реализацией синхронизации параллельных вычислений. Поэтому с целью упрощения предположим, что мы требуем только, чтобы записанное операцией записи значение было доступно операции чтения, возникшей немного позже записи и что операции записи данного процессора всегда видны в порядке их выполнения.
С этим простым определением согласованного состояния памяти мы можем гарантировать когерентность путем обеспечения двух свойств:
Операция чтения ячейки памяти одним процессором, которая следует за операцией записи в ту же ячейку памяти другим процессором получит записанное значение, если операции чтения и записи достаточно отделены друг от друга по времени.
Операции записи в одну и ту же ячейку памяти выполняются строго последовательно (иногда говорят, что они сериализованы): это означает, что две подряд идущие операции записи в одну и ту же ячейку памяти будут наблюдаться другими процессорами именно в том порядке, в котором они появляются в программе процессора, выполняющего эти операции записи.
Первое свойство очевидно связано с определением когерентного (согласованного) состояния памяти: если бы процессор всегда бы считывал только старое значение данных, то память была бы некогерентна.
Необходимость строго последовательного выполнения операций записи является более тонким, но также очень важным свойством. Представим себе, что строго последовательное выполнение операций записи не соблюдается. Тогда процессор P1 может записать данные в ячейку, а затем в эту ячейку выполнит запись процессор P2. Строго последовательное выполнение операций записи гарантирует два важных следствия для этой последовательности операций записи. Во-первых, оно гарантирует, что каждый процессор в машине в некоторый момент времени будет наблюдать запись, выполняемую процессором P2. Если последовательность операций записи не соблюдается, то может возникнуть ситуация, когда какой-нибудь процессор будет наблюдать сначала операцию записи процессора P2, а затем операцию записи процессора P1, и будет хранить это записанное P1 значение неограниченно долго. Более тонкая проблема возникает с поддержанием разумной модели порядка выполнения программ и когерентности памяти для пользователя: представьте, что третий процессор постоянно читает ту же самую ячейку памяти, в которую записывают процессоры P1 и P2; он должен наблюдать сначала значение, записанное P1, а затем значение, записанное P2. Возможно он никогда не сможет увидеть значения, записанного P1, поскольку запись от P2 возникла раньше чтения. Если он даже видит значение, записанное P1, он должен видеть значение, записанное P2, при последующем чтении. Подобным образом любой другой процессор, который может наблюдать за значениями, записываемыми как P1, так и P2, должен наблюдать идентичное поведение. Простейший способ добиться таких свойств заключается в строгом соблюдении порядка операций записи, чтобы все записи в одну и ту же ячейку могли наблюдаться в том же самом порядке. Это свойство называется последовательным выполнением (сериализацией) операций записи (write serialization). Вопрос о том, когда процессор должен увидеть значение, записанное другим процессором достаточно сложен и имеет заметное воздействие на производительность, особенно в больших машинах.
Имеются две методики поддержания описанной выше когерентности. Один из методов заключается в том, чтобы гарантировать, что процессор должен получить исключительные права доступа к элементу данных перед выполнением записи в этот элемент данных. Этот тип протоколов называется протоколом записи с аннулированием (write ivalidate protocol), поскольку при выполнении записи он аннулирует другие копии. Это наиболее часто используемый протокол как в схемах на основе справочников, так и в схемах наблюдения. Исключительное право доступа гарантирует, что во время выполнения записи не существует никаких других копий элемента данных, в которые можно писать или из которых можно читать: все другие кэшированные копии элемента данных аннулированы. Чтобы увидеть, как такой протокол обеспечивает когерентность, рассмотрим операцию записи, вслед за которой следует операция чтения другим процессором. Поскольку запись требует исключительного права доступа, любая копия, поддерживаемая читающим процессором должна быть аннулирована (в соответствии с названием протокола). Таким образом, когда возникает операция чтения, произойдет промах кэш-памяти, который вынуждает выполнить выборку новой копии данных. Для выполнения операции записи мы можем потребовать, чтобы процессор имел достоверную (valid) копию данных в своей кэш-памяти прежде, чем выполнять в нее запись. Таким образом, если оба процессора попытаются записать в один и тот же элемент данных одновременно, один из них выиграет состязание у второго (мы вскоре увидим, как принять решение, кто из них выиграет) и вызывает аннулирование его копии. Другой процессор для завершения своей операции записи должен сначала получить новую копию данных, которая теперь уже должна содержать обновленное значение.
Альтернативой протоколу записи с аннулированием является обновление всех копий элемента данных в случае записи в этот элемент данных. Этот тип протокола называется протоколом записи с обновлением (write update protocol) или протоколом записи с трансляцией (write broadcast protocol). Обычно в этом протоколе для снижения требований к полосе пропускания полезно отслеживать, является ли слово в кэш-памяти разделяемым объектом, или нет, а именно, содержится ли оно в других кэшах. Если нет, то нет никакой необходимости обновлять другой кэш или транслировать в него обновленные данные.
Разница в производительности между протоколами записи с обновлением и с аннулированием определяется тремя характеристиками:
Несколько последовательных операций записи в одно и то же слово, не перемежающихся операциями чтения, требуют нескольких операций трансляции при использовании протокола записи с обновлением, но только одной начальной операции аннулирования при использовании протокола записи с аннулированием.
При наличии многословных блоков в кэш-памяти каждое слово, записываемое в блок кэша, требует трансляции при использовании протокола записи с обновлением, в то время как только первая запись в любое слово блока нуждается в генерации операции аннулирования при использовании протокола записи с аннулированием. Протокол записи с аннулированием работает на уровне блоков кэш-памяти, в то время как протокол записи с обновлением должен работать на уровне отдельных слов (или байтов, если выполняется запись байта).
Задержка между записью слова в одном процессоре и чтением записанного значения другим процессором обычно меньше при использовании схемы записи с обновлением, поскольку записанные данные немедленно транслируются в процессор, выполняющий чтение (предполагается, что этот процессор имеет копию данных). Для сравнения, при использовании протокола записи с аннулированием в процессоре, выполняющим чтение, сначала произойдет аннулирование его копии, затем будет производиться чтение данных и его приостановка до тех пор, пока обновленная копия блока не станет доступной и не вернется в процессор.
Эти две схемы во многом похожи на схемы работы кэш-памяти со сквозной записью и с записью с обратным копированием. Также как и схема задержанной записи с обратным копированием требует меньшей полосы пропускания памяти, так как она использует преимущества операций над целым блоком, протокол записи с аннулированием обычно требует менее тяжелого трафика, чем протокол записи с обновлением, поскольку несколько записей в один и тот же блок кэш-памяти не требуют трансляции каждой записи. При сквозной записи память обновляется почти мгновенно после записи (возможно с некоторой задержкой в буфере записи). Подобным образом при использовании протокола записи с обновлением другие копии обновляются так быстро, насколько это возможно. Наиболее важное отличие в производительности протоколов записи с аннулированием и с обновлением связано с характеристиками прикладных программ и с выбором размера блока.
Реализация записи с аннулированием или обновлением.
Ключевым моментом реализации в многопроцессорных системах с небольшим числом процессоров как схемы записи с аннулированием, так и схемы записи с обновлением данных, является использование для выполнения этих операций механизма шины. Для выполнения операции обновления или аннулирования процессор просто захватывает шину и транслирует по ней адрес, по которому должно производиться обновление или аннулирование данных. Все процессоры непрерывно наблюдают за шиной, контролируя появляющиеся на ней адреса. Процессоры проверяют не находится ли в их кэш-памяти адрес, появившийся на шине. Если это так, то соответствующие данные в кэше либо аннулируются, либо обновляются в зависимости от используемого протокола. Последовательный порядок обращений, присущий шине, обеспечивает также строго последовательное выполнение операций записи, поскольку когда два процессора конкурируют за выполнение записи в одну и ту же ячейку, один из них должен получить доступ к шине раньше другого. Один процессор, получив доступ к шине, вызовет необходимость обновления или аннулирования копий в других процессорах. В любом случае, все записи будут выполняться строго последовательно. Один из выводов, который следует сделать из анализа этой схемы заключается в том, что запись в разделяемый элемент данных не может закончиться до тех пор, пока она не захватит доступ к шине.
В дополнение к аннулированию или обновлению соответствующих копий блока кэш-памяти, в который производилась запись, мы должны также разместить элемент данных, если при записи происходит промах кэш-памяти. В кэш-памяти со сквозной записью последнее значение элемента данных найти легко, поскольку все записываемые данные всегда посылаются также и в память, из которой последнее записанное значение элемента данных может быть выбрано (наличие буферов записи может привести к некоторому усложнению).
Однако для кэш-памяти с обратным копированием задача нахождения последнего значения элемента данных сложнее, поскольку это значение скорее всего находится в кэше, а не в памяти. В этом случае используется та же самая схема наблюдения, что и при записи: каждый процессор наблюдает и контролирует адреса, помещаемые на шину. Если процессор обнаруживает, что он имеет модифицированную "грязную" копию блока кэш-памяти, то именно он должен обеспечить пересылку этого блока в ответ на запрос чтения и вызвать отмену обращения к основной памяти. Поскольку кэши с обратным копированием предъявляют меньшие требования к полосе пропускания памяти, они намного предпочтительнее в мультипроцессорах, несмотря на некоторое увеличение сложности. Поэтому далее мы рассмотрим вопросы реализации кэш-памяти с обратным копированием.
Для реализации процесса наблюдения могут быть использованы обычные теги кэша. Более того, упоминавшийся ранее бит достоверности (valid bit), позволяет легко реализовать аннулирование. Промахи операций чтения, вызванные либо аннулированием, либо каким-нибудь другим событием, также не сложны для понимания, поскольку они просто основаны на возможности наблюдения. Для операций записи мы хотели бы также знать, имеются ли другие кэшированные копии блока, поскольку в случае отсутствия таких копий, запись можно не посылать на шину, что сокращает время на выполнение записи, а также требуемую полосу пропускания.
Чтобы отследить, является ли блок разделяемым, мы можем ввести дополнительный бит состояния (shared), связанный с каждым блоком, точно также как это делалось для битов достоверности (valid) и модификации (modified или dirty) блока. Добавив бит состояния, определяющий является ли блок разделяемым, мы можем решить вопрос о том, должна ли запись генерировать операцию аннулирования в протоколе с аннулированием, или операцию трансляции при использовании протокола с обновлением. Если происходит запись в блок, находящийся в состоянии "разделяемый" при использовании протокола записи с аннулированием, кэш формирует на шине операцию аннулирования и помечает блок как частный "private". Никаких последующих операций аннулирования этого блока данный процессор посылать больше не будет. Процессор с исключительной "exclusive" копией блока кэш-памяти обычно называется "владельцем" "owner" блока кэш-памяти.
При использовании протокола записи с обновлением, если блок находится в состоянии "разделяемый", то каждая запись в этот блок должна транслироваться. В случае протокола с аннулированием, когда посылается операция аннулирования, состояние блока меняется с "разделяемый" на "неразделяемый" или "частный". Позже, если другой процессор запросит этот блок, состояние снова должно измениться на "разделяемый". Поскольку наш наблюдающий кэш видит также все промахи, он знает, когда этот блок кэша запрашивается другим процессором, и его состояние должно стать "разделяемый".
Поскольку любая транзакция на шине контролирует адресные теги кэша, потенциально это может приводить к конфликтам с обращениями к кэшу со стороны процессора. Число таких потенциальных конфликтов можно снизить применением одного из двух методов: дублированием тегов, или использованием многоуровневых кэшей с "охватом" (inclusion), в которых уровни, находящиеся ближе к процессору являются поднабором уровней, находящихся дальше от него. Если теги дублируются, то обращения процессора и наблюдение за шиной могут выполняться параллельно. Конечно, если при обращении процессора происходит промах, он должен будет выполнять арбитраж с механизмом наблюдения для обновления обоих наборов тегов. Точно также, если механизм наблюдения за шиной находит совпадающий тег, ему будет нужно проводить арбитраж и обращаться к обоим наборам тегов кэша (для выполнения аннулирования или обновления бита "разделяемый"), возможно также и к массиву данных в кэше, для нахождения копии блока. Таким образом, при использовании схемы дублирования тегов процессор должен приостановиться только в том случае, если он выполняет обращение к кэшу в тот же самый момент времени, когда механизм наблюдения обнаружил копию в кэше. Более того, активность механизма наблюдения задерживается только когда кэш имеет дело с промахом.
Системы с локальной памятью.
Существуют два различных способа построения крупномасштабных систем с распределенной памятью. Простейший способ заключается в том, чтобы исключить аппаратные механизмы, обеспечивающие когерентность кэш-памяти, и сосредоточить внимание на создании масштабируемой системы памяти. Несколько компаний разработали такого типа машины. Наиболее известным примером такой системы является компьютер T3D компании Cray Research. В этих машинах память распределяется между узлами (процессорными элементами) и все узлы соединяются между собой посредством того или иного типа сети. Доступ к памяти может быть локальным или удаленным. Специальные контроллеры, размещаемые в узлах сети, могут на основе анализа адреса обращения принять решение о том, находятся ли требуемые данные в локальной памяти данного узла, или размещаются в памяти удаленного узла. В последнем случае контроллеру удаленной памяти посылается сообщение для обращения к требуемым данным.
параллельный компьютер вычислительная память
Заключение
Примеры использования параллельных вычислительных систем или суперкомпьютеров можно найти в разных областях промышленности, медицины, образования. Вот лишь небольшой список областей человеческой деятельности, где использование суперкомпьютеров действительно необходимо:
· автомобилестроение;
· нефте - и газодобыча;
· фармакология;
· прогноз погоды и моделирование изменения климата;
· сейсморазведка;
· проектирование электронных устройств;
· синтез новых материалов и многие, многие другие.
В 1995 году корпус автомобиля Nissan Maxima удалось сделать на 10% прочнее благодаря использованию суперкомпьютера фирмы Cray (The Atlanta Journal, 28 мая, 1995г). С помощью него были найдены не только слабые точки кузова, но и наиболее эффективный способ их удаления.
По данным Марка Миллера (Mark Miller, Ford Motor Company), для выполнения crash-тестов, при которых реальные автомобили разбиваются о бетонную стену с одновременным замером необходимых параметров, съемкой и последующей обработкой результатов, компании Форд понадобилось бы от 10 до 150 прототипов новых моделей при общих затратах от 4 до 60 миллионов долларов. Использование суперкомпьютеров позволило сократить число прототипов на одну треть.
Ещё один пример - это развитие одной из крупнейших мировых систем резервирования Amadeus, используемой тысячами агентств со 180000 терминалов в более чем ста странах. Установка двух серверов Hewlett-Packard T600 по 12 процессоров в каждом позволила довести степень оперативной доступности центральной системы до 99.85% при текущей загрузке около 60 миллионов запросов в сутки.
И подобные примеры можно найти повсюду. В свое время исследователи фирмы DuPont искали замену хлорофлюорокарбону. Нужно было найти материал, имеющий те же положительные качества: невоспламеняемость, стойкость к коррозии и низкую токсичность, но без вредного воздействия на озоновый слой Земли. За одну неделю были проведены необходимые расчеты на суперкомпьютере с общими затратами около 5 тысяч долларов. По оценкам специалистов DuPont, использование традиционных экспериментальных методов исследований потребовало бы около трех месяцев и 50 тысяч долларов и это без учета времени, необходимого на синтез и очистку необходимого количества вещества.
Увеличение производительности ЭВМ, за счет чего?
А почему суперкомпьютеры считают так быстро? Вариантов ответа может быть несколько, среди которых два имеют явное преимущество: развитие элементной базы и использование новых решений в архитектуре компьютеров.
Попробуем разобраться, какой из этих факторов оказывается решающим для достижения рекордной производительности. Обратимся к известным историческим фактам. На одном из первых компьютеров мира - EDSAC, появившемся в 1949 году в Кембридже и имевшем время такта 2 микросекунды (2*10-6 секунды), можно было выполнить 2*n арифметических операций за 18*n миллисекунд, то есть в среднем 100 арифметических операций в секунду. Сравним с одним вычислительным узлом современного суперкомпьютера Hewlett-Packard V2600: время такта приблизительно 1.8 наносекунды (1.8*10-9 секунд), а пиковая производительность около 77 миллиардов арифметических операций в секунду.
Что же получается? За полвека производительность компьютеров выросла более чем в семьсот миллионов раз. При этом выигрыш в быстродействии, связанный с уменьшением времени такта с 2 микросекунд до 1.8 наносекунд, составляет лишь около 1000 раз. Откуда же взялось остальное? Ответ очевиден - использование новых решений в архитектуре компьютеров. Основное место среди них занимает принцип параллельной обработки данных, воплощающий идею одновременного (параллельного) выполнения нескольких действий.
К сожалению, чудеса в нашей жизни совершаются редко. Гигантская производительность параллельных компьютеров и суперЭВМ с лихвой компенсируется стоимостью и сложностью их использования. Но даже вопросы, возникающие вокруг суперкомпьютеров, ставят в тупик. Например, простой пример и жизни: землекоп выкопает яму за один час. Как вы думаете, 60 землекопов выкопают яму за одну минуту? Так и в компьютере: начиная с некоторого момента, они будут просто мешать друг другу, не ускоряя, а замедляя работу.
Но все вопросы, сопровождающие суперкомпьютер, конечно же, решаются. Да, использовать суперкомпьютер сложнее, чем PC: нужны дополнительные знания и технологии, высококвалифицированные специалисты, более сложная структура информации. Написать эффективную параллельную программу сложнее, чем последовательную, да и вообще создание параллельного программного обеспечения для параллельных компьютеров - основная проблема суперкомпьютерных вычислений. Но без суперЭВМ сегодня не обойтись, и отрадно, что в нашей стране есть понимание необходимости развития этих технологий. В ноябре 2000 года в Президиуме РАН состоялось открытие межведомственного суперкомпьютерного центра. В процессе становления суперкомпьютерные центры в Дубне, Черноголовке, Институте прикладной математики им. М.В. Келдыша и т.п.
Создана и развивается линия отечественных суперкомпьютеров МВС-100. За рубежом также происходит интенсивное развитие суперкомпьютеров всех типов (векторные, кластерные и т.п.), и использование их практически во всех отраслях человеческой жизни. А иначе и нельзя, так как параллельные компьютеры и вычисления - не будущее, а реальность.
Глоссарий
|
Понятие |
Определение |
|
|
Архитектура вычислительной машины |
концептуальная структура вычислительной машины, определяющая проведение обработки информации и включающая методы преобразования информации в данные и принципы взаимодействия технических средств и программного обеспечения. |
|
|
Кластер |
группа компьютеров, объединённых высокоскоростными каналами связи и представляющая с точки зрения пользователя единый аппаратный ресурс. |
|
|
Когерентность кэша |
свойство кэшей, означающее целостность данных, хранящихся в локальных кэшах для разделяемого ресурса. |
|
|
Компьютерная память |
устройство хранения информации, запоминающее устройство - часть вычислительной машины, физическое устройство или среда для хранения данных, используемых в вычислениях, в течение определённого времени. |
|
|
Многопроцессорность |
мультипроцессорность, многопроцессорная обработка, - использование пары или большего количества физических процессоров в одной компьютерной системе. |
|
|
Оперативная память |
энергозависимая часть системы компьютерной памяти, в которой временно хранятся данные и команды, необходимые процессору для выполнения им операции. |
|
|
Параллельные вычисления |
такой способ организации компьютерных вычислений, при котором программы разрабатываются как набор взаимодействующих вычислительных процессов, работающих параллельно. |
|
|
Параллельные вычислительные системы |
это физические компьютерные, а также программные системы, реализующие тем или иным способом параллельную обработку данных на многих вычислительных узлах. |
|
|
Сеть передачи данных |
совокупность оконечных устройств (терминалов) связи, объединённых каналами передачи данных и коммутирующими устройствами (узлами сети), обеспечивающими обмен сообщениями между всеми оконечными устройствами. |
|
|
Суперкомпьютер |
вычислительная машина, значительно превосходящая по своим техническим параметрам большинство существующих компьютеров. |
|
|
Центральный процессор |
электронный блок либо микросхема - исполнитель машинных инструкций (кода программ), главная часть аппаратного обеспечения компьютера или программируемого логического контроллера. |
Список использованных источников
1. Антонов А.С. Введение в параллельные вычисления, М.: Изд-во МГУ, 2002, 346 с.
2. Борисов М. UNIX-кластеры // М.: Открытые системы, 2005г, 237 с.
3. Вычислительная техника и программирование / Под ред. А.В. Петрова - М.: Высшая школа, 2003, 385 с.
4. Демьяненко В.Ю. Программные средства создания и ведения баз данных. - М.: Финансы и статистика, 2001, 316 с.
5. Кузьминский М. Векторно-параллельные суперкомпьютеры NEC // М.: Открытые системы, 2003 г, 246 с.
6. Кузьминский М. Архитектура S2MP - свежий взгляд на cc-NUMA // М.: Открытые системы, 2007г, 357 с.
7. Локальные вычислительные сети: Справочник. В 3-х кн. / Под. ред. С.В. Назарова - М.: Финансы и статистика, 1994. - Т. Кн.1. - 208 с.
8. Ляхович В.Ф. Основы информатики. - Ростов-на-Дону: Феникс, 2006, 278 с.
9. Моначов В. Язык программирования Java и среда NetBeans. - 2-е изд. - СПб.: БХВ-Петербург, 2009. - 720 с.
10. Мячев А.А. Спецификация многопроцессорных систем компании Intel // М.: Открытые системы, 2005, 336 с.
Подобные документы
Параллельные вычислительные системы, их общая характеристика и функциональные особенности, оценка возможностей, внутренняя структура и взаимосвязь элементов, типы: одно- и многопроцессорные. Параллельная форма алгоритма, его представление и реализация.
контрольная работа [118,1 K], добавлен 02.06.2014Классификация вычислительных систем по способам взаимодействия потоков выполняемых команд и потоков обрабатываемых данных, их разновидности и функциональные особенности. Принципы расширения классификации Флинна. Виды топологии соединительной сети.
презентация [175,6 K], добавлен 11.10.2014Пути достижения параллелизма вычислений. Понятие и разновидности, а также сферы и особенности использования суперкомпьютеров. Параллельные вычисления как процессы решения задач, в которых могут выполняться одновременно несколько вычислительных операций.
презентация [8,3 M], добавлен 11.10.2014Математическая основа параллельных вычислений. Свойства Parallel Computing Toolbox. Разработка параллельных приложений в Matlab. Примеры программирования параллельных задач. Вычисление определенного интеграла. Последовательное и параллельное перемножение.
курсовая работа [1,1 M], добавлен 15.12.2010Понятие вычислительных систем, их классификация по различным признакам. Модели параллельных вычислений PGAS и APGAS. Разработка программного продукта для анализа информационных обменов в параллельных программах на языке IBM X10. Расчёт его себестоимости.
дипломная работа [1,6 M], добавлен 10.06.2013Вычислительные системы и программное обеспечение как важнейшие разделы информатики, условия перехода общества в информационную стадию развития. Развитие вычислительных систем и персональных компьютеров. Операционные системы и системы программирования.
реферат [906,9 K], добавлен 18.01.2011Знакомство с историей развития многопроцессорных комплексов и параллельных вычислений. Персональные компьютеры как распространенные однопроцессорные системы на платформе Intel или AMD, работающие под управлением однопользовательских операционных систем.
презентация [1,1 M], добавлен 22.02.2016Параллельные вычислительные системы как физические компьютерные и программные системы, реализующие параллельную обработку данных на многих вычислительных узлах. Типы параллелизма, отличительные особенности и условия применения, классификация архитектур.
реферат [280,6 K], добавлен 01.12.2010Главная задача компьютерной системы. Виртуальные адресные пространства нескольких программ. Классификация методов распределения памяти. Зависимость загрузки процессора от числа задач и интенсивности ввода-вывода. Схема функционирования кэш-памяти.
презентация [2,2 M], добавлен 14.11.2012Технология разработки параллельных программ для многопроцессорных вычислительных систем с общей памятью. Синтаксис, семантика и структура модели OpenMP: директивы, процедуры и переменные окружения. Распараллеливание по данным и операциям, синхронизация.
презентация [1,2 M], добавлен 10.02.2014
