Архитектура вычислительных систем

    Задание 11 

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

    Single Instruction Multiple Data (SIMD), - одиночный поток инструкций -множественный поток данных.

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

    Перспективным представителем класса SIMD является архитектура VLIW (очень длинное командное слово). Одна инструкция в такой системе  команд представляет собой кортеж из нескольких RISC инструкций, которые  независимы по данным между собой. VLIW процессору не нужно проверять инструкции кортежа на выявление структурных зависимостей, зависимостей по данным или по управлению. Теперь эти функции возложены на компилятор. Процессор сразу может переходить к фазе исполнения. Такие блоки, как динамический планировщик, станции резервации и т.д., здесь упразднены. Высвободившиеся ресурсы (транзисторы) перераспределяются для повышения производительности системы (увеличиваются размеры кешей, буферов BTB и TLB). Таким образом, процессор и компилятор обеспечивают хороший уровень параллелизма команд. Один из самых мощных VLIW процессоров – Intel Itanium 2. 
 
 
 
 
 
 
 

    Задание 31 

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

    Опишем  предикацию более подробно. 

    Если  в исходной программе встречается  условное ветвление (по статистике - через  каждые 6 команд), то команды из разных ветвей помечаются разными предикатными регистрами (команды имеют для этого предикатные поля), далее они выполняются совместно, но их результаты не записываются, пока значения предикатных регистров неопределены.  Когда, наконец, вычисляется условие ветвления, предикатный регистр, соответствующий "правильной" ветви, устанавливается в 1, а другой  - в 0. Перед записью результатов процессор будет проверять предикатное поле и записывать результаты только тех команд, предикатное поле которых содержит предикатный регистр, установленный в 1. 

    Регистры IA-64: 

    - 128 64-разрядных регистров общего назначения (целочисленных)

    - 128 80-разрядных регистров вещественной  арифметики.

    - 64 1-pазpядных пpедикатных pегистpов. 

    Напомним, что наличие большого числа регистров  названо John Crawford в числе основных черт EPIC. Действительно, 128 - много по сравнению с 8 регистрами общего назначения семейства x86. Но, например, MIPS R10000 содержит 64 целых и 64 вещественных 64-разрядных регистров.   

    Формат  команды IA-64: 

    - идентификатор команды,

    - три 7-разрядных поля операндов  - 1 приемник и 2 источника (операндами могут быть только регистры, а их - 128=2^7)

    - особые поля для вещественной  и целой арифметики

    - 6-разрядное предикатное поле (64=2^6) 

    Команды IA-64 упаковываются (группируются) компилятором в "связку" длиною в 128 pазpядов. Связка содеpжит 3 команды и шаблон, в котоpом будут указаны зависимости между командами (можно ли с командой к1 запустить параллельно к2, или же к2 должна выполниться только после к1) , а также между другими связками (можно ли с командой к3 из связки с1 запустить параллельно команду к4 из связки с2).   

    Перечислим  все варианты составления связки из 3-х команд: 

    i1 ||  i2  ||   i3    - все  команды исполняются паpаллельно 

    i1 & i2  ||  i3   - сначала i1, затем  исполняются паpаллельно i2 и i3 

    i1 ||  i2 &  i3  - паpаллельно исполняются i1 и i2, после них -  i3 

    i1 & i2 &  i3  - последовательно  исполняются  i1, i2, i3 

       

    Одна  такая связка, состоящая из трех команд, соответствует набору из трех функциональных устройств процессора. Процессоры IA-64 могут содержать разное количество таких блоков, оставаясь при этом совместимыми по коду. Ведь благодаря тому, что в шаблоне указана зависимость и между связками, процессору с N одинаковыми блоками из трех функциональных устройства будет соответствовать командное слово из N*3 команд ( N связок ). Таким образом должна обеспечиваться масштабируемость IA-64. Несомненно, это красивая концепция. К сожалению, IA-64 присущи и некоторые недостатки.   

    - Tom R. Halfhill в статье журнала BYTE предполагает ([7]), что без перекомпиляции код с одного процессора семейства IA-64 не будет эффективно исполняться на другом.

    - Уже упомянутый Jerry Huck отметил ([3]), что в IA-64 можно произвольно  (блоками по 3) увеличивать количество  функциональных устройств, но  при этом число регистров должно оставаться неизменным.

    - Также Jerry Huck предупредил, что  размер кода для IA-64 будет больше, чем для RISC процессоров, потому  что на 3 команды IA-64 приходится 128 bit, а длина RISC команды обычно  равна 32 bit, то есть, в 128 битах  содержатся 4 команды RISC. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    Задание 51 

    Различия  между систолическими ВС и вычислительными системами с обработкой по принципу волнового фронта в том, что ВС с систолической структурой относятся к классу SIMD, а с обработкой по принципу волнового фронта к классу MIMD. 

    Вычислительные  системы с систолической  структурой 

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

    В основе схемы лежит ритмическое  прохождение двух потоков данных x_i и у, навстречу друг другу. Последовательные элементы каждого потока разделены одним тактовым периодом, чтобы любой из них мог встретиться с любым элементом встречного потока. Если бы они следовали в каждом периоде, то элемент x_i никогда бы не встретился с элементамиy y_i+l, y_i+3... Вычисления выполняются параллельно в процессорных элементах, каждый из которых реализует один шаг в операции вычисления скалярного произведения (IPS, Inner Product Step) и носит название IPS-элемента (рис. 13.16).

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

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

    - вычислительный процесс в систолических структурах представляет собой непрерывную и регулярную передачу данных от одного ПЭ к другому без запоминания промежуточных результатов вычисления; 

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

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

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

    - алгоритмы функционирования позволяют  совместить параллелизм с конвейерной  обработкой данных;

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

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

Вычислительные  системы с обработкой по принципу волнового фронта  

    Интересной  разновидностью систолических структур являются матричные процессоры волнового  фронта (wavefront array processor), иногда называемые также волновыми или фронтальными.

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

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

    Концепцию массива процессоров волнового  фронта проиллюстрируем на примере  матричного умножения.

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