Реферат: Механизм когерентности обобщенного кольцевого гиперкуба с непосредственными связями

Министерство образования Российской Федерации

Марийский государственный технический университет

Факультет ФИВТ

Кафедра ИВС

Механизмкогерентности обобщенного кольцевого гиперкуба с непосредственными связями

ПОЯСНИТЕЛЬНАЯЗАПИСКА

к курсовой работе по дисциплине

ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕСИСТЕМЫ.

Выполнил:

студентгруппы ВМ-42 Трохимец Г.М.

<img src="/cache/referats/15671/image001.gif" v:shapes="_x0000_s1029"><img src="/cache/referats/15671/image002.gif" v:shapes="_x0000_s1028"> (дата) (подпись)

<img src="/cache/referats/15671/image003.gif" v:shapes="_x0000_s1030"><img src="/cache/referats/15671/image004.gif" v:shapes="_x0000_s1027">Проверил: к.т.н., доцент Власов А.А.

(дата) (подпись)

<img src="/cache/referats/15671/image005.gif" v:shapes="_x0000_s1026"> Оценка:

г. Йошкар-Ола

2002г.

Аннотация

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

Оглавление

TOC o «1-1» «Заголовок3;2; Название;1» Введение… PAGEREF _Toc12641438 h 4

Техническое задание… PAGEREF _Toc12641439 h 5

1. Общая часть… PAGEREF _Toc12641440 h 6

1.1. Механизмыподдержания когерентности… PAGEREF _Toc12641441 h

1.2. Механизмы неявной реализации когерентности… PAGEREF _Toc12641442 h

1.2.1. Однопроцессорный подход… PAGEREF _Toc12641443 h

1.2.2. Многопроцессорный подход… PAGEREF _Toc12641444 h

1.2.2.1. Сосредоточенная память… PAGEREF _Toc12641445 h

1.2.2.2. Физически распределенная память… PAGEREF _Toc12641446 h

1.3. КС типа обобщенного кольцевого гиперкуба… PAGEREF _Toc12641447 h

1.3.1. Расчет основных параметров… PAGEREF _Toc12641448 h

2. Алгоритмы механизма когерентностидля обобщенного кольцевого гиперкуба PAGEREF _Toc12641449 h 17

2.1 Операция чтения… PAGEREF _Toc12641450 h

2.2 Операция записи… PAGEREF _Toc12641451 h

Заключение… PAGEREF _Toc12641452 h 20

Список литературы… PAGEREF _Toc12641453 h 21

Введение

Многопроцессорную ВСможно рассматривать как совокупность процессоров, подсоединенных кмногоуровневой иерархической памяти. При таком представлении коммуникационнаясреда, объединяющая процессоры и блоки памяти, составляет неотъемлемую частьиерархической памяти. Структурно-технические параметры коммуникационной средыопределяют характеристики многоуровневой памяти.

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

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

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

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

Техническое задание

1.

Изучитьмеханизмы поддержания когерентности.

2.

Рассмотреть КС типа обобщенный кольцевойгиперкуб.

3.

Составить алгоритм механизма когерентности КСтипа обобщенный кольцевой гиперкуб с непосредственными связями.

1. Общая часть

1.1.

Механизмы реализациикогерентности могут быть как явными, так и неявными для прикладногопрограммиста.

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

Явное размещение данных; явноеуказание доступа к данным. Программист явно задает действия по поддержкекогерентности памяти посредством передачи данных, программируемой сиспользованием специальных команд «послать»(send)и «принять»(receive).Каждый процессор имеет свое собственное адресноепространство (память ВС распределена), а согласованность элементов данныхвыполняется путем установления соответствия между областью памяти,предназначенной для передачи командойsend,и областью памяти, предназначенной для приема данных командойreceive,в другом блоке памяти.

Неявное размещениеданных;неявное указание доступа к данным. В ВС с разделяемой памятью механизмреализации когерентности прозрачен для прикладного программиста, и в программахотсутствуют какие-либо другие команды обращения к памяти, кроме команд«чтение»(load)и«запись»(store).Используется единое физическое пространство или виртуальный адрес. АрхитектураВС с разделяемой памятью имеет много привлекательных черт:

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

• создание приложенийв привычных программных средах;

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

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

Явное размещение данных с указанием разделяемыхмодулями страниц; неявное указание доступа к данным посредством командload, store.

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

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

1.2. Механизмы неявной реализации когерентности

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

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

1.2.1. Однопроцессорный подход

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

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

Типовая современнаяиерархия памятей для однопроцессорных ВС имеет следующую структуру:

• регистры 64 — 256слов со временем доступа 1 такт процессора;

• кэш 1 уровня — 8кслов с временем доступа 1—2 такта;

• кэш 2 уровня — 256кслов с временем доступа 3—5 тактов;

• основная память — до4 Гигаслов с временем доступа 12-55 тактов. Кэш имеет совокупность строк(cache-lines),каждая из которых состоитиз фиксированного количества адресуемых единиц памяти (байтов, слов) споследовательными адресами. Типичный размер строки:

16, 32, 64, 128, 256 байтов.

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

Это, так называемые,кэш-память с прямым отображением(direct-mapped ,cache),частично ассоциативная кэш-память(set-associative cache)и ассоциативнаякэш-память(fully associative cache).

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

1.2.2. Многопроцессорный подход

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

1.2.2.1. Сосредоточеннаяпамять

Рассмотрим реализацию одного из алгоритмов поддержкикогерентности кэшей, известного какMESI (Modified, Exclusive, Shared, Invalid) [б]. АлгоритмMES1представляет собой организацию когерентности кэшпамяти с обратнойзаписью. Этот алгоритм предотвращает лишние передачи данных между кэш-памятьюи основной памятью. Так, если данные в кэш-памяти не изменялись, то незачем ихпересылать. Зададим некоторые начальные условия и введем определения. Итак,каждый ВМ имеет собственную локальную кэш-память, имеется общая разделяемаяосновная память, все ВМ подсоединены к основной памяти посредством шины. Кшине подключены также внешние устройства. Важно понимать, что все действия сиспользованием транзакций шины, производимые ВМ и внешними устройствами, скопиями строк, как в каждой кэш-памяти, так и в основной памяти, доступны дляотслеживания всем ВМ. Это является следствием того, что в каждый момент нашине передает только один, а воспринимают все, подключенные к шине абоненты.Поэтому, если для объединения ВМ используется не шина, а другой типкоммутационной среды, то для работоспособности алгоритма MES1 необходимообеспечение вышеуказанного порядка выполнения транзакций. Каждая строкакэш-памяти ВМ может находиться в одном из следующих состояний:

М — строка модифицирована (доступна по чтению и записитолько в этом ВМ, потому что модифицирована командой записи по сравнению со строкой основной памяти);

Е — строка монопольно копированная (доступна по чтению изаписи в этом ВМ и в основной памяти);

S -строка множественно копированная или разделяемая (доступна по чтению и записи в этом ВМ, восновной памяти и в кэш-памятях других ВМ, в которых содержится ее копия);

1 — строка, невозможная к использованию (строка недоступна ни по чтению, ни по записи).

Состояние строки используется, во-первых, дляопределения процессором ВМ возможности локального, без выхода на шину, доступак данным в кэш-памяти, а, во-вторых, — для управления механизмом когерентности.

Для управления режимом работы механизма поддержкикогерентности используется битWT,состояние 1 которого задает режимсквозной (write-through)записи, а состояние 0 — режим обратной(write-back) записи вкэш-память.

Промах чтения в кэш-памяти заставляетвызвать строку из основной памяти и сопоставить ей состояние Е или S.Кэш-память заполняется только при промахах чтения. При промахе записитранзакция записи помещается в буфер и посылается в основную память припредоставлении шины.

Для поддержки когерентностистрок кэш-памяти при операциях ввода/вывода и обращениях в основную памятьдругих процессоров на шине генерируются специальные циклы опроса состояниякэш-памятей. Эти циклы опрашивают кэш-памяти на предмет хранения в них строки,которой принадлежит адрес, используемый в операции, инициировавшей циклыопроса состояния. Возможен режим принудительного перевода строки в состояние I,который задается сигналомINV.

1.2.2.2. Физически распределенная память

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

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

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

С каждой строкой в резидентном для нее модулесвязаны три ее возможных глобальных состояния:

1) «некэшированная», если копия строки ненаходится в кэше какого-либо другого модуля, кроме, возможно, резидентного дляэтой строки;

2) «удаленно-разделенная», если копии строкиразмещены в кэшах других модулей;

3) «удаленно-измененная», если строка измененаоперацией записи

в каком-либо модуле.

Кроме этого, каждая строка кэша находится в одном изтрех локальных состояний:

1) «невозможная к использованию»;

2) «разделяемая», если.есть неизмененная копия, которая, возможно, размешаетсятакже в других кэшах;

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

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

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

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

Если глобальное состояние строки в резидентном модуле«некэшированная», то строка отсылается запросившему модулю, и этотмодуль продолжает приостановленные вычисления.

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

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

1.3. КС типа обобщенного кольцевого гиперкуба

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

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

Рис. 1

Каждый узел среды имеет 6 двунаправленных каналов ввода/вывода, которые используются вкачестве непосредственных связей с соседними узлами (Рис.1). Возможно,применение двух встречных однонаправленных каналов вместо одногодвунаправленного, что позволяет увеличить пропускную способность принезначительном увеличении аппаратных затрат. Каждый узел также имеет 6магистральных каналов ввода/вывода – по два в каждом измерении.Коммуникационный процессор производит прием/передачу информации по каналамввода/вывода, причем может использоваться как коммутация пакетов, так икоммутация каналов.

1.3.1. Расчет параметров

Рассчитаем оценки параметров кольцевого гиперкубапри n=3, m=3. Где n – количество измерений, а m – размерность.

1.

2.

S=2n = 6;

3.

4.

5.

2. Алгоритмы механизма когерентностидля обобщенного кольцевого гиперкуба

Для КС типа обобщенный кольцевой гиперкуба можнореализовать алгоритм механизма поддержания когерентности - DASH, описанный выше в п.1.2.2.2. Таккак узел гиперкуба можно подразумевать как ЦП разделенный на:

Операционный процессор

Коммутационный процессор

КЕШ

Выполняет все вычисления но не может связываться с другим процессором

Осуществляет связь с другими процессорами

Хранит копии строк <img src="/cache/referats/15671/image015.gif" v:shapes="_x0000_s1064 _x0000_s1063 _x0000_s1031 _x0000_s1032 _x0000_s1033 _x0000_s1034 _x0000_s1035 _x0000_s1036">

2.1 Операция чтения

НАЧАЛО

Запрос на чтение

Строка измененная или разделяемая

нет

да

Невозможна к использованию Запрос в резидентный модуль,«промах чтения”

Чтение <img src=»/cache/referats/15671/image016.gif" v:shapes="_x0000_s1254 _x0000_s1043 _x0000_s1041 _x0000_s1103 _x0000_s1037 _x0000_s1038 _x0000_s1039 _x0000_s1040 _x0000_s1042 _x0000_s1044 _x0000_s1045 _x0000_s1046 _x0000_s1047 _x0000_s1051 _x0000_s1048 _x0000_s1049 _x0000_s1052 _x0000_s1053 _x0000_s1054 _x0000_s1050">

Некешированная или удаленно-разделенная строка

Пересылка копии строки в запросивший модуль

нет

да

Строка «удаленно-измененная» Запрос «промах чтения» направляется в модуль содерж. изм. строку Пересылка данной строки в запросив. модуль и в резидентн. Установка состояния строки в «удаленно-рспределенная»

КОНЕЦ

2.2 Операция записи

нет

да

НАЧАЛО

Запрос на запись

нет

да

измененная

Запись

некешированная

Пересылка строки запросившему модулю Невозможна к использованию Запрос в резидентный модуль на захват строки

да

нет

Рассылка всем модулям, имеющим копию строки, запроса на перевод строки в состояние «невозможного к использованию»

КОНЕЦ

Заключение

В данной работе мы изучили механизмы поддержания когерентности.Алгоритмы их работы. Рассмотрели КС типа обобщенный кольцевой гиперкуб,рассчитали основные оценки параметров данного гиперкуба (Рис. 1). Болееподробно мы остановились на алгоритме DASH, который в наибольшей степени подходит к КС типа обобщенныйкольцевой гиперкуб. При построении алгоритма мы видим, что для данной КС снепосредственными связями, чем больше структура, тем дольше ожидание ЦП назапросы запрещения строки. Т.к. с увеличением структуры будет увеличиватьсядиаметр и до последнего узла сообщение будет доходить с большим опозданием, чтовызовет простой запросившего процессора.

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

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

1.

2.

«Коммутационные структуры икоммуникационные среды: Лабораторный практикум.» – Йошкар-Ола: МарГТУ, 2002.

3.

4.

5.

www.narod.nov.ru/par.html «Мультипроцессорнаякогерентность кеш-памяти»

еще рефераты

Еще работы по компьютерам и переферийным устройствам

Реферат по компьютерам и переферийным устройствам

Регистратор дискретных сигналов