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

Существуют несколько классов таких протоколов:

1. Протоколы на основе справочника (directory based). Информация о состоянии блока физической памяти содержится только в одном месте, называемом справочником (физически справочник может быть распределён по узлам системы).

2. Протоколы наблюдения (snooping). Каждый кэш, который содержит копию данных некоторой части физической памяти, имеет также соответствующую копию служебной информации (биты состояния). Контроллеры кэш-памятей обмениваются между собой служебной информацией о состоянии блока данных.

Задачей протокола когерентности кэш-памяти является координация доступа к разделяемым блокам памяти. Кэш-памяти процессоров обмениваются информацией для того, чтобы определить какой процессор в настоящий момент является собственником данных. Одним из наиболее полных протоколов является протокол MOESI (Modified, Owned, Exclusive, Shared, Invalid), в котором доступ процессора к блоку данных определяется состоянием этого блока и типом запроса. Работа данного протокола описывается поведением конечного автомата с 5 состояниями. На верхнем уровне абстракции проверка правильности работы сводится к моделированию поведения автомата и контролю корректности его состояний и не представляет существенной сложности. Однако, детализация работы протокола в реальном устройстве приводит к значительным усложнениям полученной картины. Так, даже для простейшего протокола типа MSI (однопроцессорная система) имеем 11 состояний (8 из которых переходных), 13 возможных событий и 21 действие.

1. Типы внутренних связей.

Сети обмена делятся на три типа: шины, статические сети, динамические сети.

Быстродействие сети обмена определяется быстродействием узлов и связей между ними, параметры последних определяются: пропускной способностью непрерывного потока данных и максимальным количеством самых маленьких пакетов, которые можно передать за единицу времени (время передачи пакета нулевой длины, задержка). Некоторые сетевые интерфейсы:

Технология Mbyte/s Задержка (мкс)

Fast Ethernet 12.5 156

Gigabit Ethernet 125 33

Myrinet 245 6

SCI 400 1.5

Шины

Система связи ПЭ через коммутирующую общую шину отличаются от других схем простотой, однако ее производительность ограничивается необходимостью обеспечивать в любой момент времени не более одного запроса на передачу информации. Общая шина с центральным коммутатором обеспечивает арбитраж запросов процессоров на передачу информации - выделение одного из запросов на доступ к шине и обеспечение монопольного права на владения шиной на все время требуемого обмена. Шины - пропускная способность 100 Мбайт/с для 2 -20 ПЭ (Multimax). Число процессоров в таких системах всегда ограничено.

Статические сети

Статические сети имеют жестко фиксированные соединения, вход и выход зафиксированы без возможности переключения. Наиболее простой топологией сети является линейка – одномерная сетка. Для обеспечения передачи информации между несмежными узлам используются транзитные пересылки. Для цепочки из М узлов наиболее медленная пересылка есть пересылка между конечными ПЭ линейки и она потребует (М-1) транзитных пересылок. Число таких пересылок для любой статической топологии сети считается ее параметром и называется – диаметром сети. Если связать конечные ПЭ линейки, то такая топология - кольцо будет иметь меньший диаметр. Сети могут иметь вид: одномерный линейный массив, двумерное кольцо, звезда, сетка и гексагональный массив, дерево, трехмерное пол­ностью связанное хордовое кольцо, 3 -мерный куб, сети из циклически связанных 3-мерных кубов, D - мерный массив с топологией гиперкуба, тасовка (совершенная, обменная). Недостаток - необходимость маршрутизации транзитных сообщений. По топологии гиперкуба, каждое ПЭ связывается со своим ближайшем соседом в n мерном пространстве. У каждого узла в двумерном гиперкубе имеются два ближайших соседа, в трехмерном - три, в четырехмерном - четыре.

Динамические сети

Динамические сети - сети с возможностью динамического (коммутируемого) соединения узлов сети друг с другом. Особое место занимает полный коммутатор.

Полный коммутатор обеспечивает полную связность каждого узла в сети, причем, обеспечивает независимость (не блокируемость) пересылок. Недостаток: высокая стоимость аппаратуры и ограниченная размерность.

Перечисленные выше однокаскадные сети обмена содержат фиксированное число каскадов или один каскад переключателей. Многокаскадные сети могут быть получены комбинацией некоторых однокаскадных сетей и могут составить конкуренцию полному ком­мутатору. Например, стандартная сеть Клоша (Клоса) может иметь нечетное число каскадов и строится из сетей меньших размеров. Clos networks have three stages: the ingress stage, middle stage, and the egress stage. Each stage is made up of a number of crossbar switches (see diagram below), often just called crossbars. Each call entering an ingress crossbar switch can be routed through any of the available middle stage crossbar switches, to the relevant egress crossbar switch. A middle stage crossbar is available for a particular new call if both the link connecting the ingress switch to the middle stage switch, and the link connecting the middle stage switch to the egress switch, are free. Clos networks are defined by three integers n, m, and r. n represents the number of sources which feed into each of r ingress stage crossbar switches. Each ingress stage crossbar switch has m outlets, and there are m centre stage crossbar switches. There is exactly one connection between each ingress stage switch and each middle stage switch. There are r egress stage switches, each with m inputs and n outputs. Each middle stage switch is connected exactly once to each egress stage switch.

1. Статические и динамические коммуникаторы.

См Вопрос 34.

1. Параметры статических коммутационных сетей.

См Вопрос 34.

1. Топологии линейки, решетки, пирамиды.

Наиболее простой топологией сети является линейка – одномерная сетка. Для обеспечения передачи информации между несмежными узлам используются транзитные пересылки. Для цепочки из М узлов наиболее медленная пересылка есть пересылка между конечными ПЭ линейки и она потребует (М-1) транзитных пересылок. Решетка –таблица, в которой узлы связаны только со своими соседями вверх и вниз – то есть матрица. Удобно для решения и представления задач с изображением и другими пространственными задачами, где решение тесно связано с решением соседних по пространству частей. Деревья имеют хорошую структуру для большого числа задач, в которых информация сортируется, сравнивается или каким-либо образом уплотняется и реорганизуется, а также где она запоминается, извлекается или передается. Матрицы имеют хорошую структуру для локальной передачи информации.

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

1. Топология гиперкуба.

Двоичный гиперкуб - распространенная, хорошо масштабируемая и очень удачная топология (рис. 25). В ней 2k процессоров организованы в k-мерный гиперкуб. У каждого процессора k непосредственных соединений (k = log2N), максимальное расстояние между узлами k. Для адресации узлов в гиперкубе каждому узлу присваивается идентификационный номер (ID). Двоичное представление ID соседних узлов отличается одним разрядом. Алгоритм пересылки сообщения от одного узла к другому основан на побитовом сравнении двоичных представлений ID текущего узла и адресата. Для каждого процессора легко определить всех его соседей - они отличаются лишь значением какого-либо одного разряда в двоичном представлении ID. Каждая грань k-мерного гиперкуба является гиперкубом размерности k-1. См. также Таненбаум, стр 43.

1. Согласование сеточных топологий со структурой гиперкуба.

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

1. Перекрестный коммутатор.

Crossbar switches have a characteristic matrix of switches between the inputs to the switch and the output of the switch. If the switch has M inputs and N outputs, then a crossbar has a matrix with M x N cross-points or places where there the "bars" "cross". A given crossbar is a single layer, non-blocking switch. Collections of crossbars can be used to implement multiple layer and/or blocking switches. Дополнительно см. Вопрос 34.

1. Многокаскадные коммутационные сети.

Сначала см. Вопрос 34.

Источник 1: Среди традиционных сетей особое положение занимают сети, базирующиеся на большом числе идентичных ключевых элементов. Это сети с многокаскадными связями (MIN – Multistage Interconnection Network). Идеология таких сетей используется при построении коммутаторов ATM. Из таких сетей наиболее известной является Delta Banyan (Batcher-switch). Эта сеть содержит регулярную структуру N*N переключателей с двух направлений на два. Сеть содержит log2N число каскадов, каждый из которых имеет N/2 переключателей. Для управления маршрутизацией сообщений в этой сети необходимо log2N бит информации. Схема 4-каскадной сети Delta-2 приведена на рис.

Источник 2: Многокаскадные сети основаны на использовании 2х2 перекрестных переключателей - коммутаторов. В таких сетях на одном конце находятся процессоры, на другом - процессоры или другие узлы, а между ними располагаются переключатели. При передаче информации от узла к узлу переключатели устанавливаются таким образом, чтобы обеспечить требуемое соединение. На приведена схема соединения "омега", являющейся сетью с блокировкой, в которой один маршрут передачи данных может заблокировать другие маршруты. Для соединения n процессоров с n модулями памяти требуется (n/2)*log2n переключателей.

Матричный коммутатор обеспечивает полную связность, т.е. любой процессорный элемент (ПЭ) может связаться с любым другим процессорным элементом или модулем памяти (МП). Естественно, в ситуации, когда два процессора захотят работать с одним модулем памяти, один из них будет заблокирован. На пересечении линий располагаются элементарные точечные переключатели, которые разрешают или запрещают передачу информации. Недостаток - большой объем необходимого оборудования и, как следствие, ограниченная масштабируемость системы. Для связи n процессоров с n модулями памяти необходимо n*2 элементарных переключателей.

1. Пиковая производительность.

Оценка производительности вычислительных систем имеет два аспекта: оценка пиковой производительности – номинального быстродействия системы и получение оценок максимальной - “реальной” производительности. Если номинальная(пиковая, предельная) оценка однозначно определяется техническими параметрами оборудования, то вторая характеристика указывает производительность системы в реальной среде применения. Для оценки производительности вычислительных систем в ТОР500 используются обозначения Rpeak – пиковая, предельная производительность и Rmax – максимальная производительность при решении задачи Linpack.

Наиболее абстрактной единицей измерения производительности микропроцессоров является тактовая частота ПК, частота тактового генератора (clock rate,). Любая операция в процессоре не может быть выполнена быстрее, чем за один такт (период) генератора. Итак, минимальное время исполнения одной логической операции (переключение транзистора) - один такт. Тактовая частота измеряется в Герцах – число тактов в секунду.

Другой обобщенной мерой производительности ПК может служить число команд, выполняемые в единицу времени. Для вычислителей фон-Нейманновской архитектуры скорость выполнения команд уже может быть параметром, который может быть использован для оценки времени выполнения программы. Этот параметр - MIPS (Million Instruction Per Second)- миллион операций (команд, инструкций ЭВМ)/сек. Так как время выполнения различных команд может различаться, то данных параметр сопровождался разного вида уточнениями (логических команд, заданной смеси команд и т.д.), а также наиболее известной здесь мерой в 1 MIPS – это производительность вычислителя VAX 11/780. Итак, данный параметр также достаточно условен.