архитектура параллельных вычислений. АПВ УМКД+++. Учебнометодический комплекс дисциплины csse 43057 Паралелльные и облачные вычисления
 Скачать 1 Mb.
|
Закон АмдалаВ идеальном случае система из n процессоров могла бы ускорить вычисления в n раз. В реальности достичь такого показателя по ряду причин не удается. Главная из этих причин заключается в невозможности полного распараллеливания ни одной из задач. Как правило, в каждой программе имеется фрагмент кода, который принципиально должен выполняться последовательно и только одним из процессоров. Это может быть часть программы, отвечающая за запуск задачи и распределение распараллеленного кода по процессорам, либо фрагмент программы, обеспечивающий операции ввода/вывода. Можно привести и другие примеры, но главное состоит в том, что о полном распараллеливании задачи гово-рить не приходится. Известные проблемы возникают и с той частью задачи, кото-рая поддается распараллеливанию. Здесь идеальным был бы вариант, когда параллельные ветви программы постоянно загружали бы все процессоры системы, причем так, чтобы нагрузка на каждый процессор была одинакова. К сожалению, оба этих условия на практике трудно реализуемы. Таким образом, ориентируясь на параллельную ВС, необходимо четко сознавать, что добиться прямо пропорционального числу процессоров увеличения производительности не удастся, и, естественно, встает вопрос о том, на какое реальное ускорение можно рассчитывать. Ответ на этот вопрос в какой-то мере дает закон Амдала. Джин Амдал (Gene Amdahl) -- один из разработчиков всемирно известной системы IBM 360, в своей работе, опубликованной в 1967 году, предложил формулу, отражающую зависимость ускорения вычислений, достигаемого на многопроцессорной ВС, от числа процессоров и соотношения между последовательной и параллельной частями программы. Показателем сокращения времени вычислений служит такая метрика, как «ускорение». Напомним, что ускорение S-- это отношение времени Ts, затрачиваемого на проведение вычислений на однопроцессорной ВС (в варианте наилучшего последовательного алгоритма), ко времени Тр решения той же задачи на параллельной системе (при использовании наилучшего параллельного алгоритма):  Оговорки относительно алгоритмов решения задачи сделаны, чтобы подчеркнуть тот факт, что для последовательного и параллельного решения лучшими могут оказаться разные реализации, а при оценке ускорения необходимо исходить именно из наилучших алгоритмов. Проблема рассматривалась Амдалом в следующей постановке (рисунок 7.1). Прежде всего, объем решаемой задачи с изменением числа процессоров, участвующих в ее решении, остается неизменным. Программный код решаемой задачи состоит из двух частей: последовательной и распараллеливаемой. Обозначим долю операций, которые должны выполняться последовательно одним из процессоров, через f, где 0f1 (здесь доля понимается не по числу строк кода, а по числу реально выполняемых операций). Отсюда доля, приходящаяся на распараллеливаемую часть программы, составит 1-f. Крайние случаи в значениях f соответствуют полностью параллельным (f=0) и полностью последовательным (f=1) программам. Распараллеливаемая часть программы равномерно распределяется по всем процессорам. С учетом приведенной формулировки имеем:  В результате получаем формулу Амдала, выражающую ускорение, которое мо-жет быть достигнуто на системе из n процессоров:  Формула выражает простую и обладающую большой общностью зависимость. Характер зависимости ускорения от числа процессоров и доли последовательной части программы показан на рисунке 7.2. Если устремить число процессоров к бесконечности, то в пределе получаем:  Это означает, что если в программе 10% последовательных операций (то есть f=0,1), то, сколько бы процессоров ни использовалось, убыстрения работы программы более чем в десять раз никак ни получить, да и то, 10 -- это теоретическая верхняя оценка самого лучшего случая, когда никаких других отрицательных факторов нет. Следует отметить, что распараллеливание ведет к определенным издержкам, которых нет при последовательном выполнении программы. В качестве примера таких издержек можно упомянуть дополнительные операции, связанные с распределением программ по процессорам, обмен информацией между процессорами [4]. Закон ГустафсонаРешая на вычислительной системе из 1024 процессоров три больших задачи, для которых доля последовательного кода f лежала в пределах от 0,4 до 0,8%, Джон Густафсон из NASA Ames Research получил значения ускорения по сравнению с однопроцессорным вариантом, равные соответственно 1021,1020 и 1016. Согласно закону Амдала для данного числа процессоров и диапазона f, ускорение не должно было превысить величины порядка 201. Пытаясь объяснить это явление, Густафсон пришел к выводу, что причина кроется в исходной предпосылке, лежащей в основе закона Амдала: увеличение числа процессоров не сопровождается увеличением объема решаемой задачи. Реальное же поведение пользователей существенно отличается от такого представления. Обычно, получая в свое распоряжение более мощную систему, пользователь не стремится сократить время вычислений, а, сохраняя его практически неизменным, старается пропорционально мощности ВС увеличить объем решаемой задачи. И тут оказывается, что наращивание общего объема программы касается главным образом распараллеливаемой части программы. Это ведет к сокращению значения f. Примером может служить решение дифференциального уравнения в частных производных. Если доля последовательного кода составляет 10% для 1000 узловых точек, то для 100 000 точек доля последовательного кода снизится до 0,1%. Сказанное иллюстрирует рисунок 7.3, который отражает тот факт, что, оставаясь практически неизменной, последовательная часть в общем объеме увеличенной программы имеет уже меньший удельный вес. Было отмечено, что в первом приближении объем работы, которая может быть произведена параллельно, возрастает линейно с ростом числа процессоров в системе. Для того чтобы оценить возможность ускорения вычислений, когда объем последних увеличивается с ростом количества процессоров в системе (при посто-янстве общего времени вычислений), Густафсон рекомендует использовать выра-жение, предложенное Е. Барсисом (Е. Barsis):  Данное выражение известно как закон масштабируемого ускорения или закон Густафсона (иногда его называют также законом Густафсона-Барсиса). В заключение отметим, что закон Густафсона не противоречит закону Амдала. Различие состоит лишь в форме утилизации дополнительной мощности ВС, возникающей при увеличении числа процессоров [4]. Контрольные вопросы: Параллельное программирование. Производительность. Алгоритмы синтеза параллельных программ. Централизованные алгоритмы балансировки нагрузки. Закон Амдала. Закон Густафсона- Барсиса. Лекция №10. Оценка архитектуры Workload-Driven Оценка в однопроцессорной системе. Оценка производительности архитектуры Workload-Driven. План лекции: Оценка архитектуры Workload-Driven. Оценка в однопроцессорной системе. В основе этой концепции лежит сравнительная оценка возможностей однопроцессорных ЭВМ, многомашинных и многопроцессорных систем. Рассмотрим некоторую стандартную однопроцессорную ЭВМ, которую обозначим через [р+т]9где р и т - ее стандартные процессор и оперативная память соответственно. Пусть теперь Р -процессор с удвоенной производительностью по сравнению с р, а Л/- оперативная память с удвоенными емкостью и пропускной способностью каналов по сравнению с т. Рассмотрим, кроме стандартной ЭВМ, однопроцессорную ЭВМ со стандартным процессором р и удвоенной памятью М и однопроцессорную ЭВМ с процессором удвоенной производительности Р и удвоенной памятью А/, которые обозначим через [р+М] и [Р+М] соответственно. Наконец, рассмотрим совокупность двух стандартных ЭВМ, которую обозначим через [2(р+т)], и/двухпроцессорную систему, состоящую из двух стандартных процессоров р и общей для них оперативной памяти удвоенной емкости А/, которую обозначим через [2р+М]. Результаты сравнительной оценки четырех последних системных структур приведены в таблице 4.1.В этой таблице использованы следующие условные обозначения для качества системных структур по указанным в таблице критериям: • 0 - обычные возможности, • 1- улучшенные возможности, • 2 - самые лучшие возможности; Которые обеспечиваются рассматриваемыми структурами (оценки 0,1и 2 не содержат смыслового значения конкретных чисел). Из данных таблицы видно, что двухпроцессорная конфигурация [2р + М] обладает некоторыми преимуществами в определенных областях, однако надо иметь в виду, что ер производительность не достигает удвоенной производительности конфигурации [р+т],т. е. производительности конфигурации [Р+Л4]. Следует отметить, что двухпроцессорная конфигурация с общей памятью [2р I М} равноценна другим конфигурациям или превосходит их по критериям критической готовности, выполнения особо трудоемких заданий и работы в условиях кратковременных перегрузок, т. е. при пиковых нагрузках. Недостаток этой конфигурации по критерию частоты перезапуска системы является следствием повышенной сложности ее операционной системы и других управляющих механизмов, что может приводить к необходимости относительно более частых перезапусков, Наконец, меньшая надежность хранения данных в такой конфигурации по сравнению с парой продублированных машин  Приведенные качественные сравнительные оценки относятся к таким системам, для которых не ставится цель достижения сверхвысокопроизводительной обработки информации. В последнем случае, начиная с некоторого уровня производительности, обработку могут обеспечить только те или иные параллельные системы В современных однопроцессорных ЭВМ могут предусматриваться четыре уровня комплексирования: • на уровне процессоров для синхронизации и управления, • на уровне каналов ввода-вывода при помощи адаптеров, • на уровне оперативной памяти (за счет возможностей много входовой памяти), • на уровне внешней памяти. При этом может допускаться любая или некоторые комбинации уровней комплексирования. При комплексировании на уровне оперативной памяти основной является двухпроцессорная конфигурация, хотя возможны конфигурации с большим числом процессоров. Исторически первыми были созданы однопроцессорные системы, хотя идеи параллелизма обработки информации возникли практически одновременно с идеями построения самих вычислительных машин. Так, еще в середине прошлого века Ч. Бэббидж отмечал возможность совмещения длинных серий идентичных вычислений. 4.2. Многомашинные комплексы Многомашинный вычислительный комплекс (ММВК) - комплекс, включающий в себя две или более ЭВМ (каждая из которых имеет процессор, ОЗУ, набор периферийных устройств и работает под управлением собственной операционной системы), связи между которыми обеспечивают выполнение функций, возложенных на комплекс. Цели, которые ставятся при объединении ЭВМ в комплекс, могут быть различными, и они определяют характер связей между ЭВМ. Чаще всего основной целью создания ММВК является или увеличение производительности, или повышение надежности, или одновременно и то и другое. Однако при достижении одних и тех же целей связи между ЭВМ могут существенно различаться. По характеру связей между ЭВМ комплексы можно разделить на три типа: • косвенно-, или слабосвязанные; • прямосвязанные; • сателлитные. В косвенно-, иди слабосвязанных, комплексах ЭВМ связаны друг с другом только через внешние запоминающие устройства (ВЗУ). Для обеспечения таких связей используются устройства управления ВЗУ с двумя и более входами. В косвенно-связанных комплексах связь между ЭВМ осуществляется только на информационном уровне. Обмен информацией осуществляется в основном по принципу «почтового ящика», т.е. каждая из ЭВМ помещает в общую внешнюю память информацию, руководствуясь собственной программой, и соответственно другая ЭВМ принимает эту информацию, исходя из своих потребностей. Такая организация связей обычно используется в тех случаях, когда ставится задача повысить надежность комплекса путем резервирования ЭВМ. В этом случае ЭВМ, являющаяся основной, решает заданные задачи, выдает результаты и постоянно оставляет в общем ВЗУ всю информацию, необходимую для продолжения решения с любого момента времени. Вторая ЭВМ, являющаяся резервной, может находиться в состоянии ожидания, с тем чтобы в случае выхода из строя основной ЭВМ по сигналу оператора начать выполнение функций, используя информацию хранимую в общем ВЗУ основной ЭВМ. При такой связи может быть несколько способов организации работы комплекса. 1.Резервная ЭВМ находится в выключенном состоянии (ненагруженный резерв) и включается только при отказе основной ЭВМ. Естественно, для того чтобы резервная ЭВМ начала выдавать результаты вместо основной, потребуется определенное время, которое определяется временем, необходимым для включения ЭВМ, вхождением ее в режим, а также временем, отводимым для проверки ее исправности. Это время может быть достаточно большим. Такая организация возможна, когда система, в которой работает ЭВМ, не критична по отношению к некоторым перерывам или остановкам в процессе решения задач. Это обычно имеет место в случаях, когда ЭВМ не выдает управляющую информацию. 2. Резервная ЭВМ находится в состоянии полной готовности и в любой момент может заменить основную ЭВМ (нагруженный резерв», причем либо не решает никаких задач, либо работает в режиме самоконтроля, решая контрольные задачи. В этом случае переход в работе от основной к резервной ЭВМ может осуществляться достаточно быстро, практически без перерыва в выдаче результатов. Однако следует заметить, что основная ЭВМ обновляет в общем ВЗУ информацию, необходимую для продолжения решения, не непрерывно, а с определенной дискретностью, поэтому резервная ЭВМ начинает решать задачи, возвращаясь на некоторое время назад. Такая организация допустима и в тех случаях, когда ЭВМ работает непосредственно в контуре управления, а управляемый процесс достаточно медленный и возврат во времени не оказывает заметного влияния. При организации работы по первому и второму вариантам ЭВМ используются нерационально: одна ЭВМ всегда простаивает. Простоев можно избежать, загружая ЭВМ решением каких-то вспомогательных задач, не имеющих отношения к основному процессу. Это повышает эффективность системы - производительность практически удваивается. 3. Для того чтобы полностью исключить перерыв в выдаче результатов, обе ЭВМ, и основная и резервная, решают одновременно одни и те же задачи, но результаты выдает только основная ЭВМ, а в случае выхода ее из строя результаты начинает выдавать резервная ЭВМ. При этом общее ВЗУ используется только для взаимного контроля. Иногда такой комплекс дополняется устройством для сравнения результатов с целью контроля. Если при этом используются три ЭВМ, то возможно применение метода голосования, когда окончательный результат выдается только при совпадении результатов решения задачи не менее чем от двух ЭВМ. Это повышает и надежность комплекса в целом, и достоверность выдаваемых результатов. Разумеется, в этом варианте высокая надежность и оперативность достигается весьма высокой ценой -увеличением стоимости системы. Следует обратить внимание, что при любой организации работы в слабосвязанном ММВК переключение ЭВМ осуществляется либо по командам оператора, либо с помощью дополнительных средств, осуществляющих контроль исправности ЭВМ и вырабатывающих необходимые сигналы. Кроме того, быстрый переход в работе с основной на резервную ЭВМ возможен лишь при низкой эффективности использования оборудования. Существенно большей гибкостью обладают прямосвязанные ММВК. В прямо связанных комплексах существуют три вида связей: • общее ОЗУ (ООЗУ); • прямое управление, иначе связь процессор - процессор; • адаптер канал - канал (АКК). Связь через общее ОЗУ гораздо сильнее связи через ВЗУ. Хотя первая связь также носит характер информационной связи и обмен информацией осуществляется по принципу «почтового ящика», однако, вследствие того что процессоры имеют прямой доступ к ОЗУ, все процессы в системе могут протекать ссущественно большей скоростью, а разрывы в -выдаче результатов при переходах сосновной ЭВМ на резервную сокращаются до минимума. Недостаток связи, через общее ОЗУ заключается в том, что при выходе из строя ОЗУ, которое является сложным электронным устройством, нарушается работа всей системы. Чтобы этого избежать, приходится строить общее ОЗУ из нескольких модулей и резервировать информацию. Это, в свою очередь, приводит к усложнению организации вычислительного процесса в комплексе и в конечном счете к усложнению операционных систем. Следует отметить также и то, что связи через общее ОЗУ существенно дороже, чем через ВЗУ. Непосредственная связь между процессорами, канал прямого управления, может быть не только информационной, но и командной, т. е. по каналу прямого управления один процессор может непосредственно управлять действиями другого процессора. Это, естественно, улучшает динамику перехода от основной ЭВМ к резервной, позволяет осуществлять более полный взаимный контроль ЭВМ. Вместе с тем передача сколько-нибудь значительных объемов информации по каналу прямого управления нецелесообразна, так как в этом случае решение задач прекращается: процессоры ведут обмен информацией. Связь через адаптер канал - канал в значительной степени устраняет недостатки связи через общее ОЗУ ивместе с тем почти не уменьшает возможностей по обмену информацией между ЭВМ по сравнению с общим ОЗУ. Сущность этого способа связи заключается в том, что связываются между собой каналы двух ЭВМ с помощью специального устройства -адаптера. Обычно это устройство подключается к селекторным каналам ЭВМ. Такое подключение адаптера обеспечивает достаточно быстрый обмен информацией между ЭВМ, при этом обмен может производиться большими массивами информации. В отношении скорости передачи информации связь через АКК мало уступает связи через общее ОЗУ, а в отношении объема передаваемой информации - связи через общее ВЗУ. Функции АКК достаточно просты: это устройство должно обеспечивать взаимную синхронизацию работы двух ЭВМ и буферизацию информации при ее передаче, однако большое разнообразие режимов работы двух ЭВМ и необходимость реализации этих режимов существенно усложняет устройство АКК. Прямосвязанные комплексы позволяют осуществлять все способы организации ММВК, характерные для слабосвязанных комплексов. Однако за счет некоторого усложнения связей эффективность комплексов может быть значительно повышена. В частности, в прямо-связанных комплексах возможен быстрый переход от основной ЭВМ к резервной и в тех случаях, когда резервная ЭВМ загружена собственными задачами. Это позволяет обеспечивать высокую надежность при высокой производительности. В реальных комплексах одновременно используется не один вид связи между ЭВМ, а два или более. В том числе очень часто в прямо-связанных комплексах присутствует и косвенная связь через ВЗУ. Для комплексов с сателлитными ЭВМ характерным является не способ связи, а принципы взаимодействия ЭВМ. Структура связей в сателлитных комплексах не отличается от связей в обычных ММВК: чаще всего связь между ЭВМ осуществляется через АКК Особенностью же этих комплексов является то, что в них, во-первых, ЭВМ существенно различаются по своим характеристикам а во-вторых, имеет место определенная соподчиненность машин и различие функций, выполняемых каждой ЭВМ. Одна из ЭВМ, основная, является, как правило, высокопроизводительной и предназначается для основной обработки информации. Вторая, существенно меньшая по производительность, называется сателлитной или вспомогательной ЭВМ. Ее назначение - организация обмена информацией основной ЭВМ с периферийными устройствами, ВЗУ, удаленными абонентами, подключенными через аппаратуру передачи данных к основной ЭВМ Кроме того, сателлитыая ЭВМ может производить предварительную сортировку информации, преобразование ее в форму, удобную для обработки на основной ЭВМ, приведение выходной информации к виду, удобному для пользователя, и др. Сателлитная ЭВМ, таким образом, избавляет основную высокопроизводительную ЭВМ от выполнения многочисленных действий, которые не требуют ни большой разрядности, ни сложных операций, т. е. операций, для которых большая, мощная ЭВМ не нужна. Более того, с учетом характера выполняемых сателлитной машиной операций она может быть ориентирована на выполнение именно такого класса операций и обеспечивать даже большую производительность, чем основная ЭВМ. Некоторые комплексы включают в себя не одну, а несколько сателлитных ЭВМ, при этом каждая из них ориентируется на выполнение определенных функций: например, одна осуществляет связь основной ЭВМ с устройствами ввода - вывода информации, другая -связь с удаленными абонентами, третья организует файловую систему и т. д. Появление в последнее время дешевых и простых микро-ЭВМ в немалой степени способствует развитию сателлитных комплексов. Сателлитные комплексы решают только одну задачу: увеличивают производительность комплекса, не оказывая заметного влияния на показатели надежности. Подключение сателлитных ЭВМ принципиально возможно не только через АКК, но и другими способами, однако связь через АКК наиболее удобна. Контрольные вопросы: Оценка архитектуры Workload-Driven Оценка в однопроцессорной системы. Оценка производительности архитектуры Workload-Driven. Литература: Кудин А.В., Линёв А.В., Архитектура и операционные системы параллельных вычислительных систем. Нижний Новогород, 2007. 73с. El-Rewini H. Abd-El-Barr M. Advanced Computer Architecture and Parallel Proccesing. Wiley-Interscience, 2005. Dubois M., Annavaram M., Stenstrom P. Parallel Computer Organization and Design, Cambridge University Press, UK, 2010. Xingfu Wu, Performance Evaluation, Prediction and Visualization of Parallel Systems, Springer Science & Business Media, 2012. 319 c. Лекция №11. Проектирование мультипроцессоров на основе Snoop. Широковещательный Snoop-запрос. Когерентность протоколов на основе Snoop. План лекции: Проектирование мультипроцессоров на основе Snoop. Когерентность протоколов на основе Snoop. Наличие кэш-памяти в ПЭ создает проблему, называемую Наличие кэш-памяти в ПЭ создает проблему, называемую непротиворечивостью кэшей. Она состоит в том, что ПЭ, который считывает строку из кэш-памяти другого ПЭ, не должен получать устаревшие данные. Возможность считыва-  Рис. 18.3. Обобщенная структура мультипроцессора с шинной организацией ния устаревших данных обусловлена тем, что отдельные ПЭ мультипроцессора работают без тесного взаимодействия друг с другом. Для решения этой проблемы предложено много различных алгоритмов. Все алгоритмы строятся на том, чтобы не допустить одновременного появления разных вариантов одной и той же строки в разных блоках кэш-памяти. Для этого с помощью контроллера отслеживаются все запросы шины, поступившие от других ПЭ и других блоков кэш-памяти, и в критических случаях предпринимаются необходимые действия. Такая организация взаимодействия кэша называется кэш-памятью с отслеживанием (Snooping Caches). Набор правил, которые выполняются кэш-памятью, ПЭ и основной памятью, чтобы предотвратить появление различных вариантов данных в нескольких блоках кэш-памяти, называется протоколом когерентности кэширования. Сквозное кэширование. Это самый пр остой протокол когерентности кэширования. Для понимания его сути в табл. 18.1 приведено четыре случая: кэш-попадание и кэш-промах при чтении и записи. Таблица 18.1
Чтение. При наличии затребованного слова в кэше (кэш-попадание) ПЭ получает его. Если же ПЭ пытается считать слово, которого нет в кэш-памяти (кэш-промах), контроллер загружает из основной (общей) памяти в кэш-память строку, содержащую это слово. В дальнейшем данные считываются из кэш-памяти. Запись. При обновлении слова, находящегося в кэш-памяти (кэш-попадание), происходит его запись в кэш и в основную память. В случае кэш-промаха при записи слово, которое было изменено, записывается в основную память. Строка, содержащая нужное слово, не загружается в кэш-память. Таким образом, в результате всех операций записи записываемое слово обязательно проходит через основную память, чтобы информация в основной памяти всегда обновлялась. Протокол сквозного кэширования с отслеживание м. Обозначим: кэш-1 – активный кэш, выполняющий операции чтения/записи; кэш-2 – кэш с отслеживанием, или отслеживающий кэш. Рассмотрим операции чтения/записи активного кэша-1 с точки зрения кэша-2 с отслеживанием для удаленного запроса (крайняя правая колонка в табл. 18.1). Чтение. Если нужная строка содержится в кэше-1, запроса шины не происходит, поэтому кэш-2 не знает о результативных считываниях из кэша-1. Если при считывании произошел промах кэша-1, он запрашивает шину, чтобы получить нужную строку из основной памяти. Кэш-2 видит это, но остается пассивным. Запись. Если процессорный элемент ПЭ с кэшем-1 записывает слово, то всегда (как в случае промаха, так и в случае попадания): • кэш-1 запрашивает шину; • кэш-2 проверяет у себя наличие записываемого слова. Рассмотрим два возможных случая: записываемое слово в кэше-2 отсутствует. Кэш-2 рассматривает это как промах отдаленной памяти и ничего не предпринимает. Отметим, что в табл. 18.1 промах удаленной памяти означает, что слово не присутствует в кэш-памяти отслеживаемого ПЭ, при этом не имеет значения, было ли это слово в кэш-памяти инициирующего ПЭ или нет. Таким образом, один и тот же запрос может быть результативным логически и промахом для отслеживаемого ПЭ и наоборот; • записываемое слово в кэше-2 присутствует. При отсутствии каких-либо действий кэш-2 будет содержать устаревшие данные. Поэтому строка (элемент) кэш-памяти, содержащая измененное слово, помечается как недействительная и удаляется из кэш-памяти. Каждый кэш отслеживает все запросы шины, и всякий раз после записи слова его нужно обновитьв кэш-памяти инициатора запроса, в основной памяти и удалить из всех других кэшей. Следовательно, неправильные варианты слова исключаются. Процессорный элемент с кэша-2 может прочитать слово, записанное ПЭ в кэш-1, на следующем цикле. В этом случае кэш-2 считает слово из обновленной основной памяти. В этот момент кэш-1, кэш-2 и основная память содержат идентичные копии этого слова. Если какой-нибудь процессор произведет запись, то другие кэши очистятся, а основная память обновится. Протокол MESI. Этот протокол именуется по первым буквам названий следующих четырех состояний: • Modified – элемент кэш-памяти действителен; основная память недействительна; копий элемента не существует; • Exclusive – основная память обновлена; никакой другой кэш не содержит эту строку; • Shared – основная память обновлена; несколько кэшей могут содержать данную строку; • Invalid – элемент кэш-памяти содержит недействительные данные. Протокол MESI относится к протоколам с обратной записью и базируется на протоколе однократной записи. Каждый элемент кэш-памяти может находиться в одном из указанных выше четырех состояний. При загрузке ПЭ все элементы кэш-памяти помечаются буквой I (Invalid) как недействительные. Чтение. При первом считывании из основной памяти нужная строка А вызывается в кэш-память ПЭ1 и, поскольку это единственная копия в кэш-памяти, строка помечается как Е (Exclusive) (рис. 18.4, а). Отметим, что, если записываемая строка находится в состоянии Е, никакого сигнала о недействительности на шину не передается, так как известно, что других копий нет. При последующих считываниях ПЭ1 использует эту строку А и не использует шину. Другой элемент, ПЭ2, может вызвать ту же строку и поместить ее в свою кэш-память, но при отслеживании исходный ПЭ1 узнает, что он уже не единственный держатель строки, и объявляет, что у него есть копия. Обе копии помечаются состоянием S (Shared) (см. рис. 18.4,б). При последующих чтениях кэшированных строк в состоянии S элемент ПЭ2 не использует шину и не меняет состояние элемента.  Рис. 18.4. Протокол MESI Запись. Рассмотрим два случая: • если ПЭ2 производит запись в строку А своего кэша, находящуюся в состоянии S, то эта строка переходит в состояние М (Modified) (см. рис. 18.4,0). При этом строка не записывается в основную память. Однако ПЭ2 помещает на шину сигнал недействительности I (Invalid), сообщающий другим ПЭ, что нужно отбросить свои копии; • если ПЭ2 производит запись в строку А своего кэша, находящуюся в состоянии Е (Exclusive), то сигнал Е не выставляется, поскольку никакой другой кэш не содержит эту строку и основная память обновлена. Чтение после записи. При считывании элементом ПЭЗ из ПЭ2 строки, находящейся в состоянии М (рис. 18.4^), элемент ПЭ2 знает, что копия этой строки в основной памяти недействительна. Поэтому ПЭ2 должен записать строку в основную память и выставить на шину для ПЭ3 сигнал ожидания. После того как строка будет записана в память, ПЭ3 вызывает из памяти копию этой строки. В обоих кэшах строка помечается символом S (см. рис. 18.4,г), после чего ПЭ2 записывает эту строку снова, что делает недействительной копию в кэш-памяти ПЭЗ. Запись после чтения. Если процессорный элемент ПЭ2 производит запись в строку А из строки, которая была считана в ПЭЗ, то строка в ПЭ2 помечается М как модифицированная, а в ПЭЗ становится недействительной (рис. 18.4,d). Запись после записи. Процессорный элемент ПЭ 1 производит запись в строку А своего кэша сразу после того, как строка А была записана в ПЭ2. Процессорный элемент П Э2 видит действия ПЭ1 и передает ему сигнал, что нужно подождать до тех пор, пока строка не будет записана в основную память. Когда это действие закончится, ПЭ2 помечает собственную копию строки как недействительную (I), поскольку он знает, что ПЭ1 собирается изменить ее. Возникает ситуация, в которой ПЭ1 производит запись в некэшированную строку. Если применяется политика write allocate, строка будет загружаться в кэш-память и помечаться как М (рис. 18.4,0). В противном случае строка записывается в основную память, а в кэш-памяти не сохраняется. Контрольные вопросы: . Проектирование мультипроцессоров на основе Snoop. Широковещательный Snoop-запрос. Когерентность протоколов на основе Snoop. Литература: Кудин А.В., Линёв А.В., Архитектура и операционные системы параллельных вычислительных систем. Нижний Новогород, 2007. 73с. El-Rewini H. Abd-El-Barr M. Advanced Computer Architecture and Parallel Proccesing. Wiley-Interscience, 2005. Dubois M., Annavaram M., Stenstrom P. Parallel Computer Organization and Design, Cambridge University Press, UK, 2010. Xingfu Wu, Performance Evaluation, Prediction and Visualization of Parallel Systems, Springer Science & Business Media, 2012. 319 c. Лекция №12. Масштабируемые высокопроизводительные системы с распределенной памятью. Многоядерные процессоры и проблемы параллельной обработки. Симметричная мультипроцессорность. Основные классы современных параллельных компьютеров. Многоядерность и одновременная многопотоковость. План лекции: Многоядерные процессоры и проблемы параллельной обработки. Симметричная мультипроцессорность. Основным параметром классификации паралелльных компьютеров является наличие общей (SMP) или распределенной памяти (MPP). Нечто среднее между SMP и MPP представляют собой NUMA-архитектуры, где память физически распределена, но логически общедоступна. Кластерные системы являются более дешевым вариантом MPP. При поддержке команд обработки векторных данных говорят о векторно-конвейерных процессорах, которые, в свою очередь могут объединяться в PVP-системы с использованием общей или распределенной памяти. Все большую популярность приобретают идеи комбинирования различных архитектур в одной системе и построения неоднородных систем. При организациях распределенных вычислений в глобальных сетях (Интернет) говорят о мета-компьютерах, которые, строго говоря, не представляют из себя параллельных архитектур. Более подробно особенности всех перечисленных архитектур будут рассмотрены далее на этой странице, а также в описаниях конкретных компьютеров - представителей этих классов. Для каждого класса приводится следующая информация: краткое описание особенностей архитектуры, примеры конкретных компьютеров, перспективы масштабируемости, типичные особенности построения операционных систем, наиболее характерная модель программирования (хотя возможны и другие). Примечание. На данной странице рассматриваются наиболее типичные классы архитектур современных параллельных компьютеров и супер-ЭВМ. (Не рассматриваются устаревшие и проектируемые архитектуры.) |