Лекции по "Программированию"

 

Наиболее эффективной является архитектура с топологией "толстого дерева" (fat-tree). Архитектура "fat-tree" (hypertree) была предложена Лейзерсоном (Charles E. Leiserson) в 1985 году. Процессоры локализованы в листьях дерева, в то время как внутренние узлы дерева скомпонованы во внутреннюю сеть. Поддеревья могут общаться между собой, не затрагивая более высоких уровней сети.

 

 
Рисунок 5 -   Кластерная архитектура "Fat-tree"

 

Поскольку способ соединения процессоров  друг с другом больше влияет на производительность кластера, чем тип используемых в ней процессоров, то может оказаться более целесообразным создать систему из большего числа дешевых компьютеров, чем из меньшего числа дорогих. В кластерах, как правило, используются операционные системы, стандартные для рабочих станций, чаще всего свободно распространяемые (Linux, FreeBSD), вместе со специальными средствами поддержки параллельного программирования и балансировки нагрузки. При работе с кластерами, так же, как и с MPP-системами, используют так называемую Massive Passing Programming Paradigm – парадигму программирования с передачей данных (чаще всего – MPI). Умеренная цена подобных систем оборачивается большими накладными расходами на взаимодействие параллельных процессов между собой, что сильно сужает потенциальный класс решаемых задач.

 

 
Рисунок 6 -  Кластерная архитектура "Fat-tree" (вид сверху на предыдущую схему)

 

Лекция № 6. Основные принципы построения матричных и конвейерных вычислительных систем. Ассоциативные процессоры. Конвейерные процессоры. Матричные процессоры.  Коммуникационные процессоры

 

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

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

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

 

Рисунок 1 -  Схема ассоциативной системы

 

Ассоциативные системы  относятся к классу: один поток  команд – множество потоков данных (SIMD = Single Instruction Multiple Data). Эти системы  включают большое число операционных устройств, способных одновременно по командам управляющего устройства вести обработку нескольких потоков данных. В ассоциативных вычислительных системах информация на обработку поступает от ассоциативных запоминающих устройств (АЗУ), характеризующихся тем, что информация в них выбирается не по определенному адресу, а по ее содержанию.

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

Обработка команды может  быть разделена на несколько основных этапов, назовем их микрокомандами. Выделим основные пять микрокоманд:

- выборка команды; 

- расшифровка команды; 

- выборка необходимых  операндов; 

- выполнение команды; 

- сохранение результатов.

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

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

Во многих вычислительных системах наряду с конвейером команд используются и конвейеры данных.

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

Одной из наиболее высокопроизводительных вычислительных конвейерных систем считается СRАY. В этой системе конвейерный принцип обработки используется в максимальной степени. Имеется и конвейер команд, и конвейер арифметических и логических операций. В системе широко применяется совмещенная обработка информации несколькими устройствами. Максимальная пиковая производительность процессора может составлять 12 GFLOPS.

В настоящее время  созданы однокристальные векторно-конвейерные  процессоры, основными компонентами которых являются скалярный процессор  и 8 идентичных векторных устройств, суммарная производительность которых составляет 64 GFLOPS. На их основе построена система SX-6 компании NEC.

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

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

 

Рисунок 2 -  Структура матричной вычислительной системы

 

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

Сама идея создания процессоров, предназначенных  для оптимизации сетевой работы и при этом достаточно универсальных  для программной модификации, родилась в связи с необходимостью устранить различия в подходах к созданию локальных сетей (различные подходы к архитектуре сети, классификации потоков и т.д.). Несомненно, истинной причиной бума сетевых процессоров стало ускорение темпов развития рынка. Когда рынок движется на «Internet-скорости», поставщики оборудования уже не могут тратить по два года на разработку специализированных микросхем для реализации конкретных сетевых функций. Эти два года (и вложенные деньги) будут потрачены зря, если рынок за это время уйдет в другом направлении. Выход один – разрабатывать процессоры, которые поставщики оборудования могут внедрить и выпустить в новом продукте в течение нескольких месяцев. Бум сетевых процессоров, окончательно оформившийся в середине 1999 г., не был кратким, и в последующие годы индустрия развивалась крайне бурно.

 

Лекция № 7. Типы простых коммутаторов, используемые в коммуникационных средах вычислительных систем. Простые коммутаторы. Простые коммутаторы с временным разделением. Простые коммутаторы с пространственным разделением. Составные коммутаторы.  Коммутатор Клоза

 

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

Простые коммутаторы. Типы простых коммутаторов:

- с временным разделением;

- с пространственным разделением.

Достоинства: простота управления и высокое быстродействие. Недостатки: малое количество входов и выходов.

Примеры использования:

- простые коммутаторы с временным разделением используются в системах SMP Power Challenge от SGI,

- простые коммутаторы с пространственным разделением (Gigaplane) используются в семействе Sun Ultra Enterprise.

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

 

 
Рисунок 1 -  Общая схема шинной структуры

 

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

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

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

- назначение каждому  устройству уникального приоритета (статического или динамического);

- использование очереди запросов FIFO;

- выделение фиксированных временных интервалов каждому устройству.

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

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

Фиксированные временные  интервалы. Все устройства по порядку получают одинаковые временные интервалы для осуществления передачи. Если устройство не имеет данных для передачи, то интервал тем не менее следующему устройству не предоставляется.