1. Принцип конвейерной обработки данных. Последовательные конвейеры. Ассоциативные процессоры

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

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

1) Выбор команд из ОП

2) Декодирование

3) Определение адреса и выборка операнда

4) Выполнение операции

    Конвейерная обработка увелич. Пропускную способность процессора но не сокращает время выполнения отдельной команды.

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

1) структурные - когда аппаратные средства не могут поддерживать все возможные команды и режимы сообщения.

2) По данным - когда выполнение одной команды зависит от предыдущей

3) По управлению - ...

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

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

2. Принцип конвейерной обработки данных. Векторные конвейеры. Ассоциативные процессоры

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

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

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

4. Характеристика архитектуры UMA.

     UMA архитектура предполагает наличие одной (реже двух или более) общей шины к которой подключены несколько процессоров. Доступ к любому элементу данных происходит единообразно, и, поэтому, данная архитектура имеет название “единообразный доступ к памяти”. Недостатком такой архитектуры является очень плохая масштабируемость, при увеличении числа процессоров прирост производительности уменьшается, так как увеличиваются времена ожидания для доступа к общей шине. Практически, ВС с такой архитектурой не содержат более 32 процессоров. Увеличение задержек объясняется тем, что одновременно с шиной может работать только один процессор. Если некоторый процессор занял шину для какой-либо операции, например, для чтения из памяти, другие процессоры должны ожидать своей очереди.

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

       Противоположностью UMA архитектуре можно считать архитектуру MPP – вычислительная система с распределённой между процессорами памятью (distributed memory). Эта архитектура предполагает соединение полнофункциональных компьютеров быстрой сетью.

_________________________________________________________________________________________________________

6. PVP архитектура

          PVP (Parallel Vector Process) - параллельная архитектура с векторными процессорами. 
Основным признаком PVP-систем является наличие специальных векторно-конвейерных процессоров, в которых предусмотрены команды однотипной обработки векторов независимых данных, эффективно выполняющиеся на конвейерных функциональных устройствах. Как правило, несколько таких процессоров (1-16) работают одновременно с общей памятью (аналогично SMP) в рамках многопроцессорных конфигураций. Несколько таких узлов могут быть объединены с помощью коммутатора (аналогично MPP). Поскольку передача данных в векторном формате осуществляется намного быстрее, чем в скалярном (максимальная скорость может составлять 64 Гб/с, что на 2 порядка быстрее, чем в скалярных машинах), то проблема взаимодействия между потоками данных при распараллеливании становится несущественной. И то, что плохо распараллеливается на скалярных машинах, хорошо распараллеливается на векторных. Таким образом, системы PVP архитектуры могут являться машинами общего назначения (general purpose systems). Однако, поскольку векторные процессоры весьма дороги, эти машины не будут являться общедоступными. Наиболее популярны 3 машины PVP архитектуры:

1.  SMP архитектура.
2.  NUMA архитектура.
3.  MPP архитектура.

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

1.  производить векторизацию вручную, цель - перевести задачу в матричную форму. При этом, в соответствии с длиной вектора, размеры матрицы должны быть кратны 128 или 256.
2.  работать с векторами в виртуальном пространстве, разлагая искомую функцию в ряд и оставляя число членов ряда, кратное 128 или 256.

         За счет большой физической памяти (доли терабайта), даже плохо векторизуемые задачи на PVP системах решаются быстрее, на системах со скалярными процессорами. 
______________________________________________________________________________________________________________

9. Классификация архитектур МПВС по Флинну. Характеристика класса SISD (ОКОД).

Single Instruction Single Data) – одиночный поток команд, одиночный   поток данных (последовательные компьютеры фон Неймана). К этому классу относятся последовательные компьютерные системы, которые имеют один центральный процессор, способный обрабатывать только один поток последовательно исполняемых инструкций. Примерами компьютеров с архитектурой SISD являются большинство рабочих станций Compaq, Hewlett-Packard и Sun Microsystems.  Это обычные      скалерные, однопроцессорные системы.        

Помимо RISC и CISC компьютеров, архитектура SISD породила еще и      машины с суперскалярной обработкой. Смысл которой – наличие в      аппаратуре средств, позволяющих одновременно выполнять две и более      скалярные операции, т.е. команд обработки пары чисел (например,      процессоры DEC серии Alpha).

______________________________________________________________________________________________________________

12. Классификация архитектур МПВС по Флинну. Характеристика класса MIMD (MКОД).

MIMD (Multiple Instruction Multiple Data) – множественный поток команд и множественный поток данных.

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

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

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

3.Классификация МПВС.

-По типам процессов (однородные, не однородны)

-по способу управления (централизованные, децентрализованные)

-По принципу структуры

-количество потоков данных, количество потоков команд.

10. Классификация архитектур МПВС по Флинну. Характеристика класса MISD (MКMД).

MISD (Multiple Instruction Single Data) – этот класс долгое время пустовал, более того, в литературе вы встретите утверждение, что этот класс не представляет практического интереса. Это объясняется тем, что не существовало примеров практической реализации систем, в которых одни и те же данные обрабатывались бы большим числом процессоров. Теперь ситуация изменилась, для MISD найдена адекватная организация ВС – распределенная мультипроцессорная система с общими данными. Наиболее простой пример такой ВС – обычная локальная сеть ПК, работающая с единой базой данных, когда много процессоров обрабатывают один поток данных.

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

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

______________________________________________________________________________________________________________

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

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

Используют два вида работы с ОС:

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

2) На каждом модуле работает UNIX- подобная ОС. Взаимодействие между модулями обеспечивает интерфейс передачи данных .

преимущества MPP

- Высокая масштабируемость (каждый процессор использует свою локальную ОП )

недостатки

- Каждый процессор может использовать ограниченный объем ОП

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

______________________________________________________________________________________________________________

8. Типы мультипроцессорных ОС

Возможны различные варианты организации данных мультипроцессорных ОС. Ниже будут рассмотрены три из них.
Каждому CPU — свою ОС. Простейший способ организации мультипроцессорных ОС состоит в том, чтобы статически разделить ОЗУ по числу CPU и дать каждому CPU свою собственную память с собственной копией ОС. В результате n CPU будут работать как n независимых компьютеров. В качестве очевидного варианта оптимизации можно позволить всем CPU совместно использовать код ОС и хранить только индивидуальные копии данных на рисунке. Квадратики, помеченные словом Data, означают персональные данные ОС для каждого CPU.

Мультипроцессоры типа «хозяин-подчиненный»

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

Симметричные мультипроцессоры

Другая модель, представляющая собой симметричные мультипроцессоры (SMP, Symmetric Multiprocessor), позволяет устранить перекос предыдущей модели. Как и в предыдущей схеме, в памяти находится всего одна копия ОС, но выполнять ее может любой CPU. При системном вызове на CPU, обратившемся к системе с СВ, происходит прерывание с переходом в режим ядра и обработкой СВ. Модель симметричного мультипроцессора показана на рис

7. Характеристика архитектуры NUMA

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

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

      Ключевым понятием многопроцессорных архитектур является узел - вычислительная система, состоящая из одного или нескольких процессоров, имеющая оперативную память и систему ввода-вывода. Узел характеризуется тем, что на нем работает единственная копия операционной системы (ОС).

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

1.  соединения внутри микропроцессора и соединения процессор - кэш;
2.  соединения кэш - основная память;
3.  соединения основная память - сеть или основная память - сетевой кэш;
4.  соединения узел - узел;

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

В целом доступ к данным в NUMA происходит через следующие элементы

1.  удалённый узел
2.  сетевой кэш (находится между сетью и узлом)
3.  основная память
4.  локальный кэш (находится между памятью и процессором)
5.  процессор
   __________________________________________________________________________________________________________

5.SMP-архитектура параллельных вычислительных систем

SMP (symmetric multiprocessing) – симметричная многопроцессорная архитектура. Главной особенностью систем с архитектурой SMP является наличие общей физической памяти, разделяемой всеми процессорами.
Память служит, в частности, для передачи сообщений между процессорами, при этом все вычислительные устройства при обращении к ней имеют равные права и одну и ту же адресацию для всех ячеек памяти. Поэтому SMP-архитектура называется симметричной. Последнее обстоятельство позволяет очень эффективно обмениваться данными с другими вычислительными устройствами. SMP-система строится на основе высокоскоростной системной шины (SGI PowerPath, Sun Gigaplane, DEC TurboLaser), к слотам которой подключаются функциональные блоки типов: процессоры (ЦП), подсистема ввода/вывода (I/O) и т. п. Для подсоединения к модулям I/O используются уже более медленные шины (PCI, VME64). Основные преимущества SMP-систем:

1.  простота и универсальность для программирования. Архитектура SMP не накладывает ограничений на модель программирования, используемую при создании приложения: обычно используется модель параллельных ветвей, когда все процессоры работают независимо друг от друга. Однако можно реализовать и модели, использующие межпроцессорный обмен. Использование общей памяти увеличивает скорость такого обмена, пользователь также имеет доступ сразу ко всему объему памяти. Для SMP-систем существуют довольно эффективные средства автоматического распараллеливания;
2.  простота эксплуатации. Как правило, SMP-системы используют систему кондиционирования, основанную на воздушном охлаждении, что облегчает их техническое обслуживание;
3.  относительно невысокая цена.

Недостатки:

1.  системы с общей памятью плохо масштабируются.

_______________________________________________________________________________________________________________

11. Классификация архитектур МПВС по Флинну. Характеристика класса SIMD (OКMД).

SIMD ((Single Instruction Multiple Data) – характеризуются наличием одиночного потока команд, но множественного потока данных.Эти системы обычно имеют большое количество процессоров, в пределах от 1024 до 16384, которые могут выполнять одну и ту же инструкцию относительно разных данных в жесткой конфигурации. Единственная инструкция параллельно выполняется над многими элементами данных. Другим подклассом SIMD-систем являются векторные компьютеры. Векторные компьютеры манипулируют массивами сходных данных подобно тому, как скалярные машины обрабатывают отдельные элементы таких массивов. Это делается за счет использования специально сконструированных векторных центральных процессоров. Когда данные обрабатываются посредством векторных модулей, результаты могут быть выданы на один, два или три такта частот генератора (такт частот генератора является основным временным параметром системы)

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

При описании процедур MPI будем пользоваться словом OUT для обозначения "выходных" параметров, т.е. таких параметров, через которые процедура возвращает результаты.

_______________________________________________________________________________________________________________
15. Соединение процессоров в кластерной системе. Метрики параллельных вычислений. Закон Амдала.
В кластерной системе связь процессоров между собой выполняется за счет использования сетевых технологий на базе шинной технологии или коммутаторов. Критерием является расстояние между процессорами.

Сейчас используются топологии « плоские играть » , гиперкуб , кольцо , толстое дерево , OPEN MP , MPI .

Метрики параллельных вычислений - это система показателей для

оценки преимуществ параллельного решения задачи на n процессорах при

сравнению с ее последовательным решением на одном процессоре .

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

- Индекс параллелизма P ( n ) = O ( n ) / T ( n ) ;

- Ускорение S ( n ) = T (1) / T ( n ) .2

Ко второй группе относятся:

- Эффективность E ( n ) = S ( n ) / n = T (1 ) / ( n T ( n )) , которая оценивает

целесообразность наращивания числа процессоров за счет

определение доли ускорения , приходящаяся на один процессор ;

- Утилизация U ( n )) = O ( n ) / ( n T ( n )) , которая учитывает вклад каждого

процессора в виде количества выполняемых им операций за единицу

времени.

К третьей группе относятся :

- Избыточность R ( n ) = O ( n ) / O ( 1 ) , которая отражает степень соответствия

между программным и аппаратным параллелизмом ;

- Сжатие C ( n ) = O (1) / O ( n ) = 1 / R ( n ) .

К четвертой группе относятся :

- Качество

Закон Амдала определяет потенциальное ускорение алгоритма при увеличении числа процессоров

Где - ускорение программы (как отношение к ее начального времени работы), - доля которую можно выполнять параллельно,-количество процессоров.

Закон Амдала показывает, что увеличение эффективности вычислений зависит от алгоритма задачи и ограничен для любой задачи, в которой количество последовательных вычислений не равна нулю. небольшая часть программы не поддающееся параллелизации ограничит общее ускорение от распараллеливания
______________________________________________________________________________________________________________
14.Характеристика кластеров
Кластер - это два или более компьютеров, называемых узлами, соединенные с помощью сетевых технологий на базе шинной технологии или коммутаторов и представляется пользователем как единый информационно - вычислительный ресурс. Узлами могут быть серверы рабочие станции, персональные компьютеры. Цель построения кластеров:

1) увеличение масштабируемости за счет аппаратной, программной и информационной совместимости.

2) повышение надежности и готовности системы в целом.

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

3) увеличение суммарной производительности (прямая зависимость от производительности ЭВМ)

4) эффективное перераспределение загруженности на аппаратном, системном уровнях . Чем больше уровней объединены кластерной технологией , тем выше масштабируемость и управляемость.

5) эффективность управления и контроль работы системы

Варианты построения кластеров :

класс 1 - построены из стандартных недорогих доступных компонентов.

класс 2 - кластер строится на уникальных компонентов, обеспечивающих высокую производительность

Конфигурации кластеров :

- Системы высокой избыточности ?

- Системы высокопроизводительных вычислений - предназначены для параллельных вычислений.

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

3.Классификация МПВС.
- за типами процесів (однорідні, не однорідні)
-за способом управління (централізовані, децентралізовані)
–по принципу структури
-кількість потоків даних, кількість потоків команд.