close

Вход

Забыли?

вход по аккаунту

?

шпоры сапр!!!!!(дополн)

код для вставкиСкачать
1. Уровни параллельной обработки. SIMD-модель вычислений. Пример структурной организации SIMD-вычислений. Пример структурной реализации SIMD-системы и пример графа Маркова для описания выч. процесса.
Уровни параллельных вычислений: заданий, программ, команд, битовый
1. Уровень заданий: Несколько независимых заданий одновременно выполняются на разных процессорах или ВМ, практически не взаимодействуя друг с другом. Этот уровень реализуется при использовании многозадачного режима обработки. Взаимодействия кратковременные или вообще отсутствуют
2. Уровень программ: Параллелизм на уровне программ возникает при разбиении данных на подмножества. Такое разделение принято называть декомпозицией области (domain decomposition), а параллелизм, возникающий при этом, НОСИТ название параллелизма данных. Подмножества данных назначаются разным вычислительным процессам, и называется этот процесс - распределением данных (data distribution). Процессоры выделяются определенным процессам либо по инициативе исполняемой программы, либо - операционной системы. На каждом процессоре может выполняться не более чем один процесс.3. Уровень команд: Параллелизм на уровне команд имеет место, когда выполнение нескольких команд или выполнение различных этапов одной команды перекрывается во времени. Этот общий принцип включает в себя два понятия: параллелизм и конвейеризацию. Эти термины отражают два различных подхода. При параллельных вычислениях в состав процессора входит несколько АЛУ и высокая производительность обеспечивается за счет одновременной работы всех этих АЛУ. Суть параллелизма смежных операций состоит в следующем. При исполнении программы довольно часто встречаются ситуации, когда исходные данные для некоторой операции (скажем, i-й по порядку) и условия ее выполнения вырабатываются не при исполнении предыдущей операции ((i-1)-й), а раньше - при исполнении, например, (i-2)- или (i-3)-й и т. д. операции. Если это так, то соответственно можно совместить время исполнения i-й операции с исполнением (i-1)-й или соответственно (i-2)-й и т. д. операций.
4. Битовый параллелизм: Битовый параллелизм реализуется на микро архитектурном уровне - на уровне отдельных операционных устройств: умножителей, сумматоров, вычислителей элементарных функций .... Если биты слова (операнда) обрабатываются один за другим, то такой тип вычислений называется бит - последовательной операцией. Если биты слова обрабатываются одновременно, то говорят о бит - параллельной операцией. Данный уровень параллелизма реализуется в АЛУ современных суперскалярных процессоров. Параллельно-конвейерный сумматор:
Гранулярность.К понятию уровня параллелизма тесно примыкает понятие гранулярности - отношение объема вычислений, выполненных в параллельной задаче, к объему коммуникаций (для обмена сообщениями). Выделяют три степени гранулярности:
● мелкозернистый параллелизм (coarse grained)
● среднезернистый параллелизм (medium grained)
● крупнозернистый (fine grained) параллелизм.
Крупнозернистый параллелизм: каждое параллельное вычисление достаточно независимо от остальных, причем требуется относительно редкий обмен информацией между отдельными вычислениями. Единицами распараллеливания являются большие и независимые программы, включающие тысячи команд. Этот уровень параллелизма обеспечивается операционной системой.
Среднезернистый параллелизм - единицами распараллеливания являются вызываемые процедуры, включающие в себя сотни команд. Обычно организуется как программистом, так и компилятором.
Мелкозернистый параллелизм - каждое параллельное вычисление достаточно мало и элементарно, составляется из десятков команд. Обычно распараллеливаемыми единицами являются элементы выражения или отдельные итерации цикла, имеющие небольшие зависимости по данным. Этот уровень параллелизма часто используется распараллеливающим (векторизующим) компилятором.
Эффективное параллельное исполнение вычислений требует искусного баланса между степенью гранулярности программ и величиной коммуникационной задержки, возникающей между разными гранулами. В частности, если коммуникационная задержка минимальна, то наилучшую производительность обещает мелкоструктурное разбиение программы. Это тот случай, когда действует
параллелизм данных. Если коммуникационная задержка велика (как в слабосвязанных системах), предпочтительней крупнозернистое разбиение программ.
Структура SIMD: В таких системах единое управляющее устройство контролирует множество процессорных элементов. Каждый процессорный элемент получает от устройства управления в каждый фиксированный момент времени одинаковую команду и выполняет ее над своими локальными данными. Для классических процессорных матриц никаких вопросов не возникает, однако в этот же класс можно включить и векторно-конвейерные машины, например, CRAY-1. В этом случае каждый элемент вектора надо рассматривать как отдельный элемент потока данных. Таким образом, SIMD-модель обеспечивает параллелизм вычислений на уровне данных. К этому классу относятся матричные вычислительные системы и ассоциативные вычислительные системы
Различают следующие виды параллелизма:
1) Параллелизм объектов (SIMD)
Граф маркова
2) Псевдопараллелизм (на уровне программ)(SISD)
3)Естественный параллелизм (данные независимы, программы независимы, одноврем. выполнение) Асинхронный тип: освободившийся ресурс м.б. использован для решения др. задачи, не дожидаясь окончания вычислений. Синхронный тип: освободившиеся ресурсы ждут окончания вычислений
4) Параллелизм ветвей (параллельно-исполняемые участки программ должны быть независимы по данным, по управлению, по памяти)
2. Уровни конвейерной обработки. MISD-модель вычислений. Пример структурной организации MISD-системы. Пример графа Маркова для описания выч. процесса
Уровни конвейерной обработки:
Арифметический - на уровне отдельного исполнительного устройства операционного блока процессора
Командный - на уровне группы исполнительных устройств операционной секции процессора
Макрокомандный - на уровне группы процессоров
В зависимости от реализованного в системе уровня конвейеризации ВМ или ВС определяют как арифметико-конвейерную, командно-конвейерную или макро конвейерную. 1. При арифметико-конвейерной обработке операция преобразования элемента данных разбивается на последовательность микроопераций, каждая из которых выполняется на отдельной ступени конвейера. В этом случае на каждой ступени выполняются операции на уровне элементарных операций над битами: сдвиг, сложение, логическое "И" и так далее. Пример - конвейерный сумматор с ПЗ: Структура 7-ступенчатого конвейерного сумматора конвейерной системы CRAY-1
2. При командно-конвейерной обработке в каждой ступени конвейера обеспечивается исполнение сложной операции над группой данных. В каждом сегменте конвейера реализуется исполнение функций на уровне выполнения команды типа сложение, умножение, делений, извлечение квадратного корня и так далее. Арифметический блок системы CRAY-13. При макроконвейерной обработке в ступенях конвейера обеспечивается исполнение набора команд над элементом потока данных, которых является некоторый массив данных. Таким образом, в каждой ступени конвейера выполняется решение фактически некоторой подзадачи. Макро конвейерный блок системы CRAY-1
Параллельная обработка данных имеет две разновидности: конвейеризацию и параллельность.
Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем так, чтобы каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Выигрыш в скорости обработки данных получается за счет совмещения прежде разнесенных во времени операций.
Параллельная обработка данных предполагает наличие нескольких функционально независимых устройств.
Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Получаем очевидный выигрыш в скорости обработки за счет совмещения прежде разнесенных во времени операций.
Типы конвейерных вычислений:
1) Независимые
2) Зависимые (связанные) конвейерные вычисления
MISD - Вычислительных машин такого класса практически нет и трудно привести пример их успешной реализации. Один из немногих - систолический массив процессоров, в котором процессоры находятся в узлах регулярной решетки, роль ребер которой играют межпроцессорные соединения. Все процессорные элементы управляются общим тактовым генератором. В каждом цикле работы каждый процессорный элемент получает данные от своих соседей, выполняет одну команду и передает результат соседям. Основной принцип систолической обработки заключается в том, чтобы выполнить все стадии обработки элементов данных, извлеченных из памяти, прежде чем снова поместить в память результат этой обработки. Ряд исследователей относят конвейерные машины к данному классу, однако это не нашло окончательного признания в научном сообществе. (ВМi - ступени конвейера)
граф Маркова
3. MISD-модель вычислений со статическим управлением. Пример структурной реализации MISD. Временная сложность вычислений.
Статическое управление вычислениями - настройка ступеней конвейера выполняется только при полном завершении вычислений во всех сегментах магистрали конвейера. Более простое устройство управления, но низкая скорость вычислений при частой перенастройке функций магистрали.
Диаграмма работы
- наихудшее, в общем виде Тобр=Тзап+(n-m)*(k*Твыч.ст.+Тнаст.ст.)+m* Твыч.ст.
m - количество операций без перенастройки, при частой перенастройке теряется смысл вставлять конвейер.Параллельная обработка данных имеет две разновидности: конвейерность и параллельность. Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем так, чтобы каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Выигрыш в скорости обработки данных получается за счет совмещения прежде разнесенных во времени операций.
Параллельная обработка данных предполагает наличие нескольких функционально независимых устройств. При использовании конвейерных процессоров с перенастройкой функций ступени различают:
1) статические конвейеры (одновременная перенастройка всех ступеней) и 2) конвейеры с динамическим управлением (перенастройка с совмещением вычислений в старших ступенях)
Статическое управление перенастройкой ступеней конвейера
Тф.н. - время функциональной настройки ступеней конвейера на необходимые операции
Время простоя - время, в течение которого вычислительные мощности системы не используются по прямому назначению.
Структурная схема
4. MISD-модель вычислений с динамическим управлением. Пример структурной реализации MISD. Временная сложность вычислений.
Динамическое управление вычислениями - настройка ступеней конвейера выполняется по мере завершения вычислений в сегментах магистрали - реализуется режим совмещения вычислений и настройки сегментов. Более сложное устройство управления, но более высокая скорость вычислений.
Диаграмма работы
наихудшее, в общем виде Тобр=Тзап+(k*Твыч.ст.+Тнаст.ст.)+(n-m-1)*( Твыч.ст.+Тнаст.ст.)+m* Твыч.ст. m - количество операций без перенастройки, при частой перенастройке теряется смысл вставлять конвейер.Параллельная обработка данных имеет две разновидности: конвейерность и параллельность.
Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем так, чтобы каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Выигрыш в скорости обработки данных получается за счет совмещения прежде разнесенных во времени операций.
Параллельная обработка данных предполагает наличие нескольких функционально независимых устройств.
При использовании конвейерных процессоров с перенастройкой функций ступени различают:
1) статические конвейеры (одновременная перенастройка всех ступеней) и 2) конвейеры с динамическим управлением (перенастройка с совмещением вычислений в старших ступенях)
Динамическое управление загрузкой ступеней конвейера
Тф.н. - время функциональной настройки ступеней конвейера на необходимые операции
Структурная схема
5. Уровни параллельной обработки. MIMD-модель вычислений. Структура и граф Маркова.
Уровни параллельных вычислений: заданий, программ, команд, битовый
1. Уровень заданий: Несколько независимых заданий одновременно выполняются на разных процессорах или ВМ, практически не взаимодействуя друг с другом. Этот уровень реализуется при использовании многозадачного режима обработки. Взаимодействия кратковременные или вообще отсутствуют
2. Уровень программ: Параллелизм на уровне программ возникает при разбиении данных на подмножества. Такое разделение принято называть декомпозицией области (domain decomposition), а параллелизм, возникающий при этом, НОСИТ название параллелизма данных. Подмножества данных назначаются разным вычислительным процессам, и называется этот процесс - распределением данных (data distribution). Процессоры выделяются определенным процессам либо по инициативе исполняемой программы, либо - операционной системы. На каждом процессоре может выполняться не более чем один процесс.3. Уровень команд: Параллелизм на уровне команд имеет место, когда выполнение нескольких команд или выполнение различных этапов одной команды перекрывается во времени. Этот общий принцип включает в себя два понятия: параллелизм и конвейеризацию. Эти термины отражают два различных подхода. При параллельных вычислениях в состав процессора входит несколько АЛУ и высокая производительность обеспечивается за счет одновременной работы всех этих АЛУ. Суть параллелизма смежных операций состоит в следующем. При исполнении программы довольно часто встречаются ситуации, когда исходные данные для некоторой операции (скажем, i-й по порядку) и условия ее выполнения вырабатываются не при исполнении предыдущей операции ((i-1)-й), а раньше - при исполнении, например, (i-2)- или (i-3)-й и т. д. операции. Если это так, то соответственно можно совместить время исполнения i-й операции с исполнением (i-1)-й или соответственно (i-2)-й и т. д. операций.
4. Битовый параллелизм: Битовый параллелизм реализуется на микро архитектурном уровне - на уровне отдельных операционных устройств: умножителей, сумматоров, вычислителей элементарных функций .... Если биты слова (операнда) обрабатываются один за другим, то такой тип вычислений называется бит - последовательной операцией. Если биты слова обрабатываются одновременно, то говорят о бит - параллельной операцией. Данный уровень параллелизма реализуется в АЛУ современных суперскалярных процессоров. Параллельно-конвейерный сумматор:
Гранулярность.К понятию уровня параллелизма тесно примыкает понятие гранулярности - отношение объема вычислений, выполненных в параллельной задаче, к объему коммуникаций (для обмена сообщениями). Выделяют три степени гранулярности:
● мелкозернистый параллелизм (coarse grained)
● среднезернистый параллелизм (medium grained)
● крупнозернистый (fine grai-ned) параллелизм.
Крупнозернистый параллелизм: каждое параллельное вычисление достаточно независимо от остальных, причем требуется относительно редкий обмен информацией между отдельными вычислениями. Единицами распараллеливания являются большие и независимые программы, включающие тысячи команд. Этот уровень параллелизма обеспечивается операционной системой.
Среднезернистый параллелизм - единицами распараллеливания являются вызываемые процедуры, включающие в себя сотни команд. Обычно организуется как программистом, так и компилятором.
Мелкозернистый параллелизм - каждое параллельное вычисление достаточно мало и элементарно, составляется из десятков команд. Обычно распараллеливаемыми единицами являются элементы выражения или отдельные итерации цикла, имеющие небольшие зависимости по данным. Этот уровень параллелизма часто используется распараллеливающим (векторизирующим) компилятором.
Эффективное параллельное исполнение вычислений требует искусного баланса между степенью гранулярности программ и величиной коммуникационной задержки, возникающей между разными гранулами. В частности, если коммуникационная задержка минимальна, то наилучшую производительность обещает мелкоструктурное разбиение программы. Это тот случай, когда действует
параллелизм данных. Если коммуникационная задержка велика (как в слабосвязанных системах), предпочтительней крупнозернистое разбиение программ.
Параллельная обработка данных имеет две разновидности: конвейерность и параллельность.
Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем так, чтобы каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Выигрыш в скорости обработки данных получается за счет совмещения прежде разнесенных во времени операций.
Параллельная обработка данных предполагает наличие нескольких функционально независимых устройств.
В соответствии с классификацией Флинна архитектуры вычислительных систем делятся на 4 класса:
SISD SIMD MISD MIMD
(пар-зм низкого уровня (пар-зм объектов) конвейеризация команд, сопроцессирование, совмещение обработки в-вв)
MIMD; МКМД
В такой системе параллельно работают несколько процессоров, которые одновременно выполняют параллельные участки алгоритма. Параллельными в смысле возможной обработки являются:
1.Паралллельные ветви алгоритмов.
2.Независимые участки линейного алгоритма.
3.Разветвляющиеся процессы.
4.Операции с циклами.
5.Многократное обращение к базам данных.
К этому классу относятся классические мультипроцессорные системы, системы управления потоком данных, редуционно-волновые системы. В системах класса МКМД в нескольких автономно работающих процессорах (машинах) производится обработка различных объектов данных под управлением различных команд. К этому классу относятся так же вычислительные системы МОКМД. Эти системы используют все типы параллелизма на информационном графе, поэтому они ориентированы на достижение максимальной производительности при решении множества задач. Во многих случаях, при разработке таких систем в качестве элементной базы используются стандартные промышленные микропроцессоры.
граф Маркова
6. Режимы обработки данных: групповой, независимый, смешанный с командным управлением вычислениями. Временная сложность вычислений.
Режим обработки данных - способ предоставления ресурсов системы для организации вычислений при решении задачи (исполнении программы).
Критерии классификации: По способу обработки потоков данных - групповая, независимая и комбинированная обработка.
По способу организации обслуживания запросов - по способу предоставления ресурсов системы для обслуживания заданий (бесприоритетное, приоритетное, циклическое, бригадное ...... обслуживание).
По способу предоставления ресурсов - организации режимов обслуживания пользователей.
По способу управления вычислениями.
Виды обработки данных:
1. независимая обработка данных
Такты обработки элемента потока данных <dj> на (tj) шаге вычислений в SISD-вычислителе под управлением команды <ij>. Команды для различных данных являются различными.2. групповая обработка данных, например, умножение константы на массив элементов
Обработка элементов <dj> одиночного потока данных на (tj) шаге вычислений в SISD-вычислителе под управлением общей для всех данных потока команды <i1>.3. комбинированная обработка данных
Обработка элементов <dj> одиночного потока данных на (tj) тактах вычислений в SISD-вычислителе под управлением команд <ij> , которые являются общими для групп данных.Традиционные режимы обработки данных: Однопрограммный или однозадачный режим; Много-программный или многозадачный режим; Параллельные режимы обработки данных; Конвейерные режимы обработки данных; Режимы обработки с теледоступом; РВ-режим (режим реального времени); Пакетный режим обработки данных.
Существует три типа организации управления вычислениями на аппаратном уровне: микропрограммное, потоковое и командно-потоковое.
1. Микропрограммное:
Т ТАКТА = ( t ВВОДА + t НАСТРОЙКИ + t ВЫЧИСЛЕНИЙ + t ВЫВОДА )
Т ОБРАБОТКИ = N ( Т ТАКТА )
N количество - элементов потока данных
Алгоритмическая универсальность - обеспечивается возможность реализации разнообразных типов вычислений - арифметических, логических, комбинаторных переборов.
Компактность аппаратных решений - использование для вычислений одних и тех же функциональных блоков в различных комбинациях.
Модифицируемость системы команд изменением состава и алгоритмов реализации микропрограмм.
Относительно низкая скорость вычислений.
2. Потоковое управление вычислениями
Т ТАКТА = ( t ВВОДА + t Н.КОМУТАТОРА + t СПЕЦВЫЧИСЛЕНИЙ + t ВЫВОДА )
Т ОБРАБОТКИ = N ( Т ТАКТА )
N количество - элементов потока данных
Высокая скорость вычислений за счет аппаратной реализации системы команд.
Низкие затраты времени на управление вычислительным процессом.
Невозможность модификации системы команд без конструктивной переработки аппаратной части.
Высокие аппаратные затраты на операционную часть.
Достаточно высокая стоимость реализации.
3. Потоково - микропрограммное управление
Т ТАКТА = ( t ВВОДА + t НАСТРОЙКИ + t ВЫЧИСЛЕНИЙ + t ВЫВОДА )
Т ОБРАБОТКИ = N ( Т ТАКТА )
N количество - элементов потока данных
Совмещает преимущества микропрограммного и потокового принципов управления вычислениями.
Более сложные схемы управления загрузкой устройств обработки данных с микропрограммным и потоковым механизмами реализации вычислений.
Необходим арбитраж состояний устройств обработки данных.
Высокие требования к скорости работы устройств управления вычислениями.
Высокая стоимость реализации.
Комбинированная обработка данных с микропрограммным управлением
Для n данных, есть m данных не требующих настройки функционального блока, таким образом Тобр=Тзап+n*Тобр+(n-m)*Тнастр
Диаграмма - смесь ниже идущих(влом рисовать)
Режим обработки данных - способ предоставления ресурсов системы для организации вычислений при решении задачи (исполнении программы).
Режим обслуживания пользователя - способ предоставления ресурсов системы пользователю.
1) Режим групповой обработки данных (режим массовых вычислений)
ПД - поток данных, ПК - поток команд. Например, умножение матрицы на const, сложение массива с const.
2) Режим независимой обработки
di : микроархитектурный уровень (бит, байт, слово, двойное слово), макроархитектурный уровень (вектор).
3) Смешанный режим
Существует три типа организации управления вычислениями на аппаратном уровне: командное, потоковое и командно-потоковое.
Командное:
а) независимая обработка
На рисунке: а) настройка k1, б) обработка d1, в) настройка k2, г) обработка d2.
,
где - время обработки n команд;
- время настройки на выполнение команды; - время обработки одной команды; - количество команд.
б) групповая обработка
На рисунке: а) настройка k1, б) обработка d1, в) обработка d2.
,
где - время обработки n команд;
- время настройки на выполнение команды; - время обработки одной команды; - количество команд.
7. Режимы обработки данных: групповой, независимый, смешанный с потоковым управлением вычислениями. Временная сложность вычислений.
Режим обработки данных - способ предоставления ресурсов системы для организации вычислений при решении задачи (исполнении программы).
Критерии классификации: По способу обработки потоков данных - групповая, независимая и комбинированная обработка.
По способу организации обслуживания запросов - по способу предоставления ресурсов системы для обслуживания заданий (бесприоритетное, приоритетное, циклическое, бригадное ...... обслуживание).
По способу предоставления ресурсов - организации режимов обслуживания пользователей.
По способу управления вычислениями.
Виды обработки данных:
1. независимая обработка данных
Такты обработки элемента потока данных <dj> на (tj) шаге вычислений в SISD-вычислителе под управлением команды <ij>. Команды для различных данных являются различными.2. групповая обработка данных, например, умножение константы на массив элементов
Обработка элементов <dj> одиночного потока данных на (tj) шаге вычислений в SISD-вычислителе под управлением общей для всех данных потока команды <i1>.3. комбинированная обработка данных
Обработка элементов <dj> одиночного потока данных на (tj) тактах вычислений в SISD-вычислителе под управлением команд <ij> , которые являются общими для групп данных.Традиционные режимы обработки данных: Однопрограммный или однозадачный режим; Много-программный или многозадачный режим; Параллельные режимы обработки данных; Конвейерные режимы обработки данных; Режимы обработки с теледоступом; РВ-режим (режим реального времени); Пакетный режим обработки данных.
Существует три типа организации управления вычислениями на аппаратном уровне: микропрограммное, потоковое и командно-потоковое.
1. Микропрограммное:
Т ТАКТА = ( t ВВОДА + t НАСТРОЙКИ + t ВЫЧИСЛЕНИЙ + t ВЫВОДА )
Т ОБРАБОТКИ = N ( Т ТАКТА )
N количество - элементов потока данных
Алгоритмическая универсальность - обеспечивается возможность реализации разнообразных типов вычислений - арифметических, логических, комбинаторных переборов.
Компактность аппаратных решений - использование для вычислений одних и тех же функциональных блоков в различных комбинациях.
Модифицируемость системы команд изменением состава и алгоритмов реализации микропрограмм.
Относительно низкая скорость вычислений.
2. Потоковое управление вычислениями
Т ТАКТА = ( t ВВОДА + t Н.КОМУТАТОРА + t СПЕЦВЫЧИСЛЕНИЙ + t ВЫВОДА )
Т ОБРАБОТКИ = N ( Т ТАКТА )
N количество - элементов потока данных
Высокая скорость вычислений за счет аппаратной реализации системы команд.
Низкие затраты времени на управление вычислительным процессом.
Невозможность модификации системы команд без конструктивной переработки аппаратной части.
Высокие аппаратные затраты на операционную часть.
Достаточно высокая стоимость реализации.
3. Потоково - микропрограммное управление
Т ТАКТА = ( t ВВОДА + t НАСТРОЙКИ + t ВЫЧИСЛЕНИЙ + t ВЫВОДА )
Т ОБРАБОТКИ = N ( Т ТАКТА )
N количество - элементов потока данных
Совмещает преимущества микропрограммного и потокового принципов управления вычислениями.
Более сложные схемы управления загрузкой устройств обработки данных с микропрограммным и потоковым механизмами реализации вычислений.
Необходим арбитраж состояний устройств обработки данных.
Высокие требования к скорости работы устройств управления вычислениями.
Высокая стоимость реализации.
Комбинированная обработка данных с потоковым управлением
Есть n данных, распределенных по m специализированным устройствам, n1 на первое, n2 на второе, n3 третье, nm на m, таким образом сумма равна n. А для каждого устройства подходят данные nk - всего данных, kk - данные не требующие коммутации, то есть идущие в группе. Считается что коммутации происходят при начатой обработке данных.
Тобр=Тзап+max(∑ni-ki*Тком+nк*Тобр)
Режим обработки данных - способ предоставления ресурсов системы для организации вычислений при решении задачи (исполнении программы).
Режим обслуживания пользователя - способ предоставления ресурсов системы пользователю.
1) Режим групповой обработки данных (режим массовых вычислений)
ПД - поток данных, ПК - поток команд. Например, умножение матрицы на const, сложение массива с const.
2) Режим независимой обработки
di : микроархитектурный уровень (бит, байт, слово, двойное слово), макроархитектурный уровень (вектор).
3) Смешанный режим
Существует три типа организации управления вычислениями на аппаратном уровне: командное, потоковое и командно-потоковое.
Потоковое: б) независимая обработка
а) групповая обработка
Tк - время коммутации 8. Режимы обработки данных: групповой, независимый, смешанный с комбинированным (потоково-командным) управлением вычислениями. Временная сложность вычислений.
Режим обработки данных - способ предоставления ресурсов системы для организации вычислений при решении задачи (исполнении программы).
Критерии классификации: По способу обработки потоков данных - групповая, независимая и комбинированная обработка.
По способу организации обслуживания запросов - по способу предоставления ресурсов системы для обслуживания заданий (бесприоритетное, приоритетное, циклическое, бригадное ...... обслуживание).
По способу предоставления ресурсов - организации режимов обслуживания пользователей.
По способу управления вычислениями.
Виды обработки данных:
1. независимая обработка данных
Такты обработки элемента потока данных <dj> на (tj) шаге вычислений в SISD-вычислителе под управлением команды <ij>. Команды для различных данных являются различными.2. групповая обработка данных, например, умножение константы на массив элементов
Обработка элементов <dj> одиночного потока данных на (tj) шаге вычислений в SISD-вычислителе под управлением общей для всех данных потока команды <i1>.3. комбинированная обработка данных
Обработка элементов <dj> одиночного потока данных на (tj) тактах вычислений в SISD-вычислителе под управлением команд <ij> , которые являются общими для групп данных.Традиционные режимы обработки данных: Однопрограммный или однозадачный режим; Много-программный или многозадачный режим; Параллельные режимы обработки данных; Конвейерные режимы обработки данных; Режимы обработки с теледоступом; РВ-режим (режим реального времени); Пакетный режим обработки данных.
Существует три типа организации управления вычислениями на аппаратном уровне: микропрограммное, потоковое и командно-потоковое.
1. Микропрограммное:
Т ТАКТА = ( t ВВОДА + t НАСТРОЙКИ + t ВЫЧИСЛЕНИЙ + t ВЫВОДА )
Т ОБРАБОТКИ = N ( Т ТАКТА )
N количество - элементов потока данных
Алгоритмическая универсальность - обеспечивается возможность реализации разнообразных типов вычислений - арифметических, логических, комбинаторных переборов.
Компактность аппаратных решений - использование для вычислений одних и тех же функциональных блоков в различных комбинациях.
Модифицируемость системы команд изменением состава и алгоритмов реализации микропрограмм.
Относительно низкая скорость вычислений.
2. Потоковое управление вычислениями
Т ТАКТА = ( t ВВОДА + t Н.КОМУТАТОРА + t СПЕЦВЫЧИСЛЕНИЙ + t ВЫВОДА )
Т ОБРАБОТКИ = N ( Т ТАКТА )
N количество - элементов потока данных
Высокая скорость вычислений за счет аппаратной реализации системы команд.
Низкие затраты времени на управление вычислительным процессом.
Невозможность модификации системы команд без конструктивной переработки аппаратной части.
Высокие аппаратные затраты на операционную часть.
Достаточно высокая стоимость реализации.
3. Потоково - микропрограммное управление
Т ТАКТА = ( t ВВОДА + t НАСТРОЙКИ + t ВЫЧИСЛЕНИЙ + t ВЫВОДА )
Т ОБРАБОТКИ = N ( Т ТАКТА )
N количество - элементов потока данных
Совмещает преимущества микропрограммного и потокового принципов управления вычислениями.
Более сложные схемы управления загрузкой устройств обработки данных с микропрограммным и потоковым механизмами реализации вычислений.
Необходим арбитраж состояний устройств обработки данных.
Высокие требования к скорости работы устройств управления вычислениями.
Высокая стоимость реализации.
Комбинированная обработка данных с комбинированным управлением
Есть n данных, распределенных по m специализированным устройствам, n1 на первое, n2 на второе, n3 третье, nm на m, таким образом сумма равна n. А для каждого устройства подходят данные nk - всего данных, kk - данные не требующие коммутации, то есть идущие в группе. Считается что коммутации происходят при начатой обработке данных.
Тобр=Тзап+max(∑ni-ki*Тком+nк*Тобр+(nк-кк)*Тнастр)
Режим обработки данных - способ предоставления ресурсов системы для организации вычислений при решении задачи (исполнении программы).
Режим обслуживания пользователя - способ предоставления ресурсов системы пользователю.
1) Режим групповой обработки данных (режим массовых вычислений)
ПД - поток данных, ПК - поток команд. Например, умножение матрицы на const, сложение массива с const.
2) Режим независимой обработки
di : микроархитектурный уровень (бит, байт, слово, двойное слово), макроархитектурный уровень (вектор).
3) Смешанный режим
Существует три типа организации управления вычислениями на аппаратном уровне: командное, потоковое и командно-потоковое.
Командно-потоковое:
КМ - коммуникация, ФН - функциональная настройка - дешифрация команды и определение устройств, необходимых для ее выполнения; Твв - время ввода - организация доступа к памяти и переброс данных для обработки.
- при отличной организации вычислений
9. Параллельные режимы обработки данных
Типы параллельной обработки: Конвейерная и векторная обработка, Совмещенная обработка, Обработка с параллелизмом ветвей, Обработка с параллелизмом объектов, Естественно-параллельная обработка.
1. Естественно-параллельная обработка: Задача относится к классу задач с естественным параллелизмом, если процесс ее решения сводится к совокупности независимых операций, таких как операции над многомерными векторами, операции над матрицами, решетчатыми функциями, либо над другими аналогичными объектами. Каждый из этих объектов может быть представлен совокупностью независимых элементов - многомерный вектор представим своими компонентами. Матрица - элементами матрицы, либо векторами, решетчатая функция - своими значениями на множестве дискретных значений аргумента и т. п. Процесс, обладающей свойством естественного параллелизма, может быть разбит на несколько одновременно выполняемых и независимых вычислительных подпроцессов, результаты выполнения которых могут быть использованы также независимо.
Асинхронная ЕПО Синхронная ЕПО2. Параллелизм независимых ветвей: Особенность вычислений с параллелизмом ветвей состоит в том, что при решении крупной задачи на тех или иных этапах вычислений могут быть выделены независимо вычисляемые части - ветви.
Последовательные выч| 5 независимых ветвей|Последовательные выч
Условия параллелизма независимых ветвей: 1) между ветвями отсутствуют функциональные связи, то есть ни одна из входных переменных для ветви У не является выходной переменной ветви Х, либо какой-нибудь ветви, зависящей от Х; 2) ветви независимы в программном отношении, то есть вычисления должны управляться разными подпрограммами; ветви должны быть взаимно независимы по управлению, то есть условие выполнения ветви У не должно зависеть от признаков, вырабатываемых при выполнении ветви Х или какой-либо другой ветви, зависящей от Х. 4) между ветвями нет связи по рабочим полям памяти, то есть ветви программы независимы, они не должны производить запись данных в одни и те же ячейки памяти;3.Вычисления с параллелизмом объектов: Задачи с параллелизмом множества объектов относятся к частному случаю задач с естественным параллелизмом - в этом случае выполняется обработка различных или однотипных объектов, но по одной и той же или почти одной и той же программе.
В отличие от задач с естественным параллелизмом, при решении задач с параллелизмом множества объектов чаще встречаются ситуации, когда отдельные участки вычислений должны выполняться различно для разных объектов. Программа обработки одна для всех массивов данных.4. Модель совмещенной обработки данных
Несколько вычислительных ресурсов ВМ или системы работают параллельно. Каждый ресурс выполняет независимую обработку элемента или группы элементов потока данных - реализуется одновременная обработка независимых подпотоков данных.
Реализуется при наличии нескольких вычислительных ресурсов, работающих под общим централизованном управлением в режиме временного совмещения, либо с применением децентрализованного управления.
При децентрализации управления вычислениями центральное управление выполняет функции арбитража загрузки вычислительных ресурсов и общую синхронизацию вычислений.СтруктураДиаграмма совмещенной обработки данных при расщеплении потока
Проблемы совмещенной обработки данных: Проблема нарушения логической структуры обрабатываемого потока данных, Проблема конфликтов в случае одновременной генерации результатов вычислений в нескольких ВМ. Проблема арбитража загрузки вычислительных ресурсов в динамике вычислений. Проблема баланса скорости вычислений в ВМ. Проблема среднесрочного планирования вычислений.5. Конвейерная обработка данных
Несколько вычислительных ресурсов ВМ или системы работают в режиме совмещения, но результаты вычислений являются взаимно зависимыми - каждый элемент потока данных последовательно обрабатывается в нескольких вычислительных ресурсах.
Обработка следующего элемента потока данных при конвейерных вычислениях начинается при наличии свободного вычислительного ресурса до окончания обработки предыдущего элемента потока.
Различают связные и несвязные конвейерыКонцепция конвейерной обработки данных:
Связные конвейерные вычисления
Обеспечивают высокую скорость вычислений за счет минимизации временных затрат на прием-передачу данных между сегментами конвейера.
Эффективны только при групповых вычислениях при статическом управлении вычислениями.
Высокая стоимость вычислений при использовании динамического управления вычислениями.Требуется точная балансировка скорости вычислений в ступенях конвейера и синхронизация операций межсегментных обменов данными.Диаграммы связанных конвейерных вычислений
Групповые вычисленияСмешанныеНезависимые
Несвязанная конвейерная обработка
Обеспечивается возможность изменения порядка загрузки вычислительных ресурсов.
Необходим арбитраж размещения данных в общедоступной буферной памяти.
Временные затраты из-за необходимости доступа к буферизированным данным в процессе цикла конвейерных вычислений.
Высокие затраты времени на управление вычислениями.
Высокая сложность планирования загрузки вычислительных ресурсов. Вместо буферной памяти возможно применение настраиваемой коммуникационной сети:
Управление вычислениями обеспечивается на уровне синхронизации приема-передачи данных между специализированными вычислительными модулями - сегментами магистрали.
При работе конвейера возможны эффекты перекосов:
А. При синхронизации вычислений с опережением возникают аппаратные ошибки в ступени конвейера - вычисления выполняются не полностью и на обработку в следующую ступень передаются результаты промежуточных вычислений.
В. При синхронизации вычислений с запозданием в соответствующую ступень до завершения в ней вычислений вводятся новые данные. В результате предыдущие данные исключаются из потока выходных результатов при высокой скорости вычислений в ступени.
Управление конвейерной обработкой данных вот такие собственно говоря варианты:)Статическое управление вычислениямиМикропрограммное управление вычислениями в ступениСтатическое управление вычислениямиПотоковое управление вычислениями в ступениСтатическое управление вычислениямиМикропрограммно - потоковое управление Динамическое управление вычислениямиМикропрограммное управление вычислениями в ступениДинамическое управление вычислениямиПотоковое управление вычислениями в ступениДинамическое управление вычислениямиМикропрограммно - потоковое управление 10. Многопрограммные и многозадачные режимы обработки данных. Методы планирования запуска задач в режиме совмещенных вычислений (двух и трехфазные режимы совмещенных вычислений).
Многопрограммные режимы обработки
В ВМ или системе одновременно решается несколько задач или исполняется несколько функционально независимых программ.
Задачам или программам предоставляются необходимые вычислительные ресурсы в определенном порядке.
При многопрограммных вычисления могут возникать конфликты между задачами за доступ к ресурсам.
Такие конфликты разрешаются либо на уровне операционной системы, либо на аппаратном уровне - соответствующими аппаратными механизмами - арбитрами конфликтов.
Многопрограммные вычисления без совмещения вычислений и временным квантованием
Однофазная модель многопрограммных вычислений с временным квантованием
 Задача исполняется в системе в течении определенного временного кванта.
 Если за выделенный квант задача полностью решается, то ее исполнение завершается.
 Если за выделенный временной квант задача полностью не решена - то задача снимается с исполнения до момента освобождения ресурсов системы.
 При вычислениях в "свой" квант задача монопольно владеет всеми вычислительными ресурсами.
 При вычислениях активен только один вычислительный ресурс.
Пример однофазной модели II уровня для многопрограммных вычислений
Диаграмма многопрограммных однофазных вычислений с квантованием по времени
Граф состояний однофазного вычислительного процесса
СМО модель режим многопрограммной обработки с квантованием по времени
СМО модель режима приоритетной многопрограммной однофазной обработки
СМО модель режима приоритетной многопрограммной однофазной обработки с динамической сменой приоритетов
Многопрограммные многофазные вычисления
Двухфазная модель многопрограммных вычислений допускает одновременное решение нескольких задач в режиме разделения ресурсов - вычисления с совмещениями.
Марковская модель многофазных вычислений
Многопрограммные 4-х фазные однопроцессорные вычисления
Одновременно активно работают 4 ресурса
Производительность и время реакции (решения)
Производительность ?
 Номинальная (пиковая) - максимальное количество операций в единицу времени, выполняемых в системе при полной загрузке всех ресурсов.
 Пользовательская - максимальное количество операций в единицу времени, выполняемых в системе при решении группы однотипных пользовательских задач.
 Системная - максимальное количество операций в единицу времени, выполняемых в системе при решении группы разнотипных пользовательских задач. Обычно измеряется на смеси эталонных общепризнанных задач.
Однопрограммный (однозадачный) режим обработки - все системные ресурсы предоставляются одной программе (задаче). Мультипрограммный (мультизадачный) режим - ресурсы системы совместно используются несколькими программами (задачами).
Многозадачный с совмещенной обработкой (Hyper-Threding)
Например, при М=8 максимальная загрузка системы достигается при выполнении 8 задач
Многопроцессорный метод планирования Джонсона
Он рассчитан на двухфазную модель организации вычислений, т.е. два ресурса могут работать активно одновременно.
F1→<ОП, Пр>, F2→<КВВ, ВЗУ> Метод дает 100% результат, не учитываются ограничения по памяти если ограничения то необходимо составлять карту памяти и смотреть укладывается ли данная очередь.
F1F2τ - трудоемкость вычислений (время)
смотрим min в F1, ставим в начало очереди, задача исключается из рассмотрения. В F2 ищем min и ставим в конец очереди, эта задача исключается. И т.д. Если минимумов несолько, то брать любой. J1τ11 (1)τ12(3)J2τ21 (2)τ22(4)...Jnτn1τn2Трехфазное планирование:
Считается, что в системе одновременно могут работать 3 группы устройств:
F1→<КВВ, Пр к>, F2→<ОП2, Пр д>, F3→<ОП1, Пр д>. F1*=F1+F2; F2*=F2+F3.
F1F2F3=>F1*F2*получили:
246351
←121334222143313447433164521233631344
Вообще про память:
Характеристики систем памяти
Место физического размещения - Процессорная память, внутренняя, память, внешняя память.
Емкость - Емкость ЗУ характеризуют числом битов либо байтов, которое может храниться в запоминающем устройстве. Для обозначения к словам "бит" или "байт" добавляют приставки: кило, мега гига, тера, пета, эха ( kilo, mega, giga, tera, peta, exa). Эти приставки означают умножение основной единицы измерений 103 106 109 1012 1015 и 1018 - соответствуют значениям достаточно близким к стандартным, но представляющим собой целую степень числа 2, то есть 210, 220, 230, 240, 250, 260(ваще чушь!)
Методы доступа
Быстродействие - Быстродействие ЗУ количественно оценивают временем доступа, длительностью цикла памяти или периодом обращения (Гц), скоростью передачи данных. Время доступа для памяти с произвольным доступом соответствует интервалу времени от момента поступления адреса до момента, когда данные заносятся в память или становятся доступными. Длительность цикла памяти или период обращения (Гц - применяется к памяти с произвольным доступом, для которой оно означает минимальное время между двумя последовательными обращениями к памяти. Скорость передачи - Это скорость, с которой данные могут передаваться в память или из нее.
Физический тип - Полупроводниковая память, Память на магнитных носителях, Память на оптических носителях, Память на магнитно-оптических носителях, Энергонезависимая память, Энергозависимая память.
Окно доступа - Количества бит или байт данных, передаваемых в память или выбираемых из памяти за одно обращение к памяти.
Иерархия запоминающих устройств - ппц старая иерархия
Четыре верхних уровня иерархии образуют внутреннюю память ВМ.
Нижние уровни - это внешняя или вторичная память. По мере движения вниз по иерархической структуре:
- уменьшается соотношение "стоимость/бит",
- возрастает емкость памяти,
- растет время доступа к данным,
- уменьшается частота обращения к памяти со стороны центрального процессора.
Принцип локальности по обращениюПространственная локальность программыПространственная локальность данныхВременная локальность данныхВ процессе выполнения программы с очень высокой вероятностью адрес очередной команды программы либо следует непосредственно за адресом по которому была считана текущая команда, либо расположен вблизи негоОбрабатываемые данные структурированы и хранятся в последовательных ячейках памяти.Программа содержит множество небольших циклов и подпрограмм, небольшие наборы команд, которые многократно повторяются в течение некоторого интервала времени
Из свойства локальности вытекает:
- программу разумно представить в виде последовательно обрабатываемых фрагментов или групп команд и данных ;
- помещая такие фрагменты в более быструю память, можно существенно снизить общие задержки на обращение, поскольку команды и данные, будучи один раз переданы из медленного ЗУ в быстрое, затем могут использоваться многократно и тогда среднее время доступа к ним в этом случае определяется уже более быстрым ЗУ;
- на каждом уровне иерархии информацию разумно разбивать на блоки, выступающие в качестве наименьшей информационной единицы, пересылаемой между двумя соседними уровнями иерархии;
- при доступе к командам и данным, например, для их считывания, сначала надо производить поиск в памяти верхнего уровня, а уже затем - в памяти следующего уровня.
Оценки эффективности организации памяти
Коэффициент попаданий(hit rate) - отношение числа обращений к памяти, при которых произошло попадание, к общему числу обращений к ЗУ данного уровня иерархии
Коэффициент промахов(miss rate) - отношение числа обращений к памяти, при которых имелся промах, к числу обращений к общему числу обращений к ЗУ данного уровня иерархии
Время обращения при попадании (hit time) - время, необходимое для поиска нужной информации в памяти верхнего уровня, плюс время для считывания данных
Потери на промах (miss penalty) - время, требуемое для замены блока в памяти более высокого уровня на блок с нужными данными, расположенный в ЗУ более низкого уровня.
Потери на промах включают в себя:
- время доступа (access time) - время обращения к первому слову блока при промахе,
- время пересылки (transfer time) - дополнительное время для пересылки оставшихся слов блока.
- время доступа обусловлено задержкой памяти более низкого уровня, в то время как время пересылки связано с полосой пропускания канала между ЗУ двух смежных уровней.
Основная память представляет собой единственный вид памяти, к которой ЦП обращаться непосредственно.
Информация, хранящаяся на внешних ЗУ, становится доступной процессору только после того, как будет переписана в основную намять.
Основную память образуют запоминающие устройства с произвольным доступом, которые реализуются в виде массива ячеек.
Обращение к любой ячейке занимает равное время и выполняется в произвольной последовательности.
Каждая ячейка имеет уникальный адрес.
Методы доступа к данным
Метод последовательного доступа - ЗУ с последовательным доступом ориентировано на хранение информации в виде последовательности блоков данных, называемых записями.
Адреса ячеек полей памяти в которых размещаются первые данные записей Записи имеют переменную длину.
Имя записи уникальное
Для доступа к нужному элементу (слову или байту) необходимо прочитать все предшествующие ему данные (ленточные ЗУ). Время доступа зависит от положения требуемой записи в последовательности записей на носителе информации и позиции элемента внутри данной записи.
Метод прямого доступа к данным
Каждая запись имеет уникальный адрес, указывающий место ее физического размещения на носителе информации.
Обращение осуществляется как доступ по определенному адресу к началу записи, а затем выполняется последовательный поиск ячейки хранящей данные внутри записи.
В результате время доступа к определенному блоку данных является величиной переменной.
Такой режим характерен для магнитных дисков.
Произвольный доступ к данным.
Каждая ячейка памяти имеет индивидуальный уникальный физический адрес.
Обращение к любой ячейке занимает одно и то же время и может производиться в произвольной очередности.
Примером могут служить запоминающие устройства основной памяти.
Основная память ЭВМ и систем:
Оперативные запоминающие устройства (ОЗУ) - RAM - Random Access Memory
Постоянные запоминающие устройства (ПЗУ) - ROM - Read-Only Memory
В полупроводниковых ЗУ применяются запоминающие элементы на основе: биполярных транзисторов; приборов со структурой "металл-окисел-полупроводник" (МОП-транзисторов); приборов со структурой "металл-нитрид-окисел-полупроводник" (МНОП); приборов с зарядовой связью (ПЗС); МОП-транзисторов с изолированным затвором и др.
Ассоциативный доступ
Этот вид доступа позволяет выполнять поиск ячеек, содержащих такую информацию, в которой значение отдельных битов совпадает с состоянием одноименных битов в заданном образце.
Сравнение осуществляется параллельно для всех ячеек памяти, независимо от ее емкости.
По ассоциативному принципу построены некоторые блоки кэш-памяти.
Векторный доступ
Выполняется одновременный произвольный доступ к нескольким ячейкам памяти - осуществляется параллельная выборка элементов вектора.
Ортогонально-векторный доступ
Ортогонально-векторные вычисления
Виртуальный адресный доступ
Виртуальная память представляет собой единое адресное пространство, в котором физическая ограниченность емкости основной памяти скрыта от программиста.
Для реализации виртуальной памяти необходимо разделить все адресное пространство памяти на части и организовать соответствующий обмен между основной и внешней памятью. При этом память разбивается на страницы и сегменты.
При разбиении на блоки виртуальное и реальное адресные пространства делятся на части фиксированной длины, называемые страницами.
Сегментный доступ к данным
Сегментацией называется разделение адресного пространства памяти на части (сегменты) по логическим признакам, устанавливаемым программистом. Обычно сегмент соответствует программе или подпрограмме и в отличие от страницы имеет переменную длину.
Виртуальный адрес состоит в этом случае из номера сегмента и относительного адреса в пределах сегмента и преобразуется в физический адрес по таблице сегментов.
Поскольку в каждом сегменте адресное пространство является линейным, виртуальное адресное пространство в целом оказывается двумерным.
С учетом того, что сегмент является логической единицей, можно организовывать защиту информации и управление для коллективного использования сегментированной информации.
Сегментно- страничная организация памяти
Расширение виртуального пространства влечет за собой увеличение таблицы страниц.
Одним из способов устранения этого неудобства служит многоуровневое разбиение на страницы.
Суть этого разбиения состоит в том, что одномерное виртуальное пространство подразделяется на два уровня - сегментов и страниц, а преобразование виртуального адреса производится по двухуровневой
таблице.
Это дает возможность обойтись без ведения таблицы неиспользуемых страниц и, следовательно, экономит объем памяти, выделяемый для таблицы страниц.
Стековый доступ к данным типа "очередь"
Стековый доступ типа "магазин"
Стековый доступ типа " дек "
Стековый доступ типа "бобслей"
Блочная организация памяти - вообще базовая конфигурация памяти
Организация микросхемы памяти
Блочная организация адресной оперативной памяти
Диаграмма чтения данных
11. Память с расслоением. Структурно-функциональная организация и принцип работы.
Ну и наконец то память с расслоением
Блочная организация адресной оперативной памяти с расслоением
Диаграмма работы памяти с расслоением
Размещение данных в памяти с расслоением
Логическая структура одномерного вектора Физическая структура одномерного вектора Такое размещение элементов вектора повысить скорость работы программы за счет сокращения времени доступа к данным при использовании в компьютере в качестве основной памяти - памяти с расслоением
Конфликты доступа в памяти с расслоением
● Если же запросы к одному и тому же банку следуют друг за другом, каждый следующий запрос должен ожидать завершения обслуживания предыдущего.
● Такая ситуация называется конфликтом по доступу.
● При частом возникновении конфликтов по доступу метод становится неэффективным.
● В этих случаях используется блочно-циклическая схема расслоения памяти - каждый банк делится на несколько модулей, адресуемых по круговой схеме.
Логическая организация данных
111101
1111011 скаляр.
11111101
01011011
11010 доступ
11111
101101
Скалярный доступ - доступ к одной ячейке памяти.
Векторный доступ - доступ к группе ячеек памяти.
Формат скалярной команды:
Скалярный доступ
Память с расслоением и перекрытием
12. Диагональная память. Структурно-функциональная организация и принцип работы.
Архитектура диагональной памяти
Размещение данных в диагональной памяти
Пример применения диагональной памяти
При такой схеме расположения элементов векторов в памяти доступ к разрядному срезу матричного массива выполняется путем организации одновременного доступа ко всем модулям памяти по одному и тому же адресу ячейки
Структура
Рг А - регистры адреса;
SM - сумматоры по модулю N;
МП - модули памяти;
БРг - буферные регистры;
СШД - системная шина данных.
Диагональная память с расслоением используется в векторных ВС.
Доступ по столбцам: сумматоры не срабатывают. № банка = количеству циклических сдвигов.
Доступ по строкам: включается суммирование по модулю.
А для скалярного доступа - данные размещаются со смещением
1) логическая организация2) физическая организация
0123Модуль 0a1a2a3a4Модуль 1b1b2b3b4Модуль 2c1c2c3c4Модуль 3d1d2d3d40123М0a1d2c3b4М1b1a2d3c4М2c1b2a3d4М3d1c2b3a4
Принцип работы
В результате "столбец-вектор" дает элементы с одинаковым индексом, а "строка-вектор" одинаковые элементы (ai).
Вообще про АЗУ
Применение АЗУ
● Сверхоперативная процессорная память
● Память глобальных переменных при вычислениях с параллелизмом ветвей
● Память локальных переменных при потоковых вычислениях
● Векторная сверхоперативная память
Организация адресного доступаКонцепция ассоциативного доступа
Многоуровневые АЗУ
13. Ассоциативная память на базе адресных ЗУ. Структурно-функциональная организация и принцип работы.
Структура
АМС - анализатор множества совпадений;
РгI - регистр индикации;
РгАрг - регистр аргумента;
СС - схема сравнения.
Принцип работы:
При необходимости выбора данных из памяти в УУ приходят соответствующие данные: аргумент(для сравнения), маска (запрет поиска по определенным строкам). Далее по командам УУ из памяти выбирается первый столбец и ССi сравнивает ее с битом аргумента (в случае побитового сравнения). В тех СС где совпало устанавливается единица. Если строка замаскирована - не участвует в сравнении (всегда в СС 0). Далее выполняется столько тактов, сколько нужно и в каждом: сравнение, если не совпал и в СС - 1, то сбрасывается в 0 , иначе если совпало и СС 1, то остается 1 , совпало и в СС 0 - ноль остается. В конце сравнения данные из всех СС передаются в АМС и там формируется номер строки, которую нужно выбрать. Дешифратор формирует адрес. При Небитовой организации памяти и сложных СС - за 1 такт происходит сравнение. При побитовом - за n тактов (n - длина строки).
14. Ассоциативно-регистровая память. Структурно-функциональная организация и принцип работы.
Князьков назвал это - Параллельные регистровое АЗУ(с русским у парня беда:))
Структурная организация и принцип работы ПР АЗУ
Принцип выполнения операции чтения данных в ПР АЗУ
Организация процесса выполнения операции чтения данных
Принцип выполнения операции записи данных в ПР АЗУ
Организация процесса записи данных в ПР АЗУ
Используется в качестве сверх оперативной памяти для обмена данными между процессорами в мультипроцессорной системе.
Структура
Главное отличие - быстрые регистры. Со сдвигом. Принцип работы такой же как выше)
Разрядно-последовательные регистровые АЗУ
Структурная организация и принцип работы РПР АЗУ
Принцип работы блока схем сравнения РПР АЗУ
Принцип выполнения операции чтения данных в РПР АЗУ
Другая структура
Организация выполнения операции чтение данных в РП АЗУ
Принцип работы РП АЗУ : запись данных
Принцип работы РП АЗУ : запись данных
Вариант генерации сигналов "ЗАПИСЬ" для регистров данных РП АЗУ
Ассоциативно-стековые ЗУ
Структурная организация АСТ ЗУ
Принцип выполнения ассоциативного операции чтения данных из АСТ ЗУ
Принцип выполнения операции стекового чтения данных в АСТ ЗУ
Принцип выполнения операции стекового чтения данных в АСТ ЗУ
Принцип выполнения операции ассоциативной замены (ввода) данных
Принцип выполнения операции ввода данных в начало списка
Предварительно выполняется модификация структуры данных. Сдвиг данных на одну позицию "ВНИЗ" . Затем - ввод нового данного в первую ячейку памяти АСТ ЗУ
15. Память с блочно-циклическим расслоением. Структурно-функциональная организация и принцип работы.
Блочно-циклическое расслоение памяти
Архитектура векторной памяти с расслоением - хз куда это присунуть, так то к вопросу не относится
Диаграмма работы векторной памяти с расслоением
Структура
БФ - буферные регистры;
ИМ - интерфейсный модуль;
М - модуль памяти.
В блочно-циклической схеме расслоения памяти каждый банк состоит из нескольких модулей, адресуемых по круговой схеме. Адреса между банками распределены по блочной схеме. Таким образом, адрес ячейки разбивается на три части: старшие биты определяют номер банка, следующая группа разрядов адреса указывает на ячейку в модуле, а младшие биты адреса выбирают модуль в банке.
Контроллеры памяти позволяют отдельным банкам работать совершенно автономно.
16. Блочно-ортогональная память. Структурно-функциональная организация и принцип работы.
Применяется в качестве локальной памяти в матричных процессорах и основной памяти в мультипроцессорных системах
Структура
ВШД - вертикальная шина данных;
ГШД - горизонтальная шина данных;
СШД - системная шина данных;
ША - шина адреса;
Дш - дешифратор;
ЦУУ - центральное устройство управления.формат команды:
Возможно 3 вида доступа:
а) скалярный (к данным расположенным в одном банке памяти)
б) горизонтально-векторный
в) вертикально-векторный 17. Матрично-регистровая память и дуальная память. Структурно-функциональная организация и принцип работы
Дуальная память
Дуальная или переключающаяся память организуется из двух или более блоков сверхбыстродействующей памяти с произвольным доступом, которые соединяются так, что пока один из блоков осуществляет обмен с ОП, другой остается подключенным к конвейеру и снабжает его данными. По окончании обменов буфера с ОП и конвейера с подключенным к нему буфером, связи этих буферов взаимно переключаются. Конвейер получает доступ к новой партии данных, а ОП получает возможность обмена данными с другим буфером
Двухпортовая память тоже не сюды но так
Матрично-регистровая память
Матрично-регистровая
Ввод информации осуществляется путем сдвига. Если в ЯП осуществляется обработка данных - то это операционная память
Используется при решении задач в рамке клеточной логики
Дуальная память
Применяется для скоростной загрузки векторных процессоров. (как правило локальная)
18. Память с распределенной логикой. Структурно-функциональная организация и принцип работы
- многофункциональная память
- оперативная память
Основная особенность: в ячейку вводится небольшое операционное оборудование.
yвых = yiyi-1 + xixi-1
xвых = yi v yi-1
sвых = xi v xi-1
yi - значение ЯП РЛ
РЛ - распределенная логика.
Структура ПМ определяется количеством ячеек и пространственной организацией канала ввода/вывода.
Структура ПМ определяется количеством ячеек и пространственной организацией канала ввода/вывода.
пример нахождения максимальной строки
Расширенное АЗУ - хз куды
Многофункциональная память - дополнительно из слайдов
19. Стековая память. Структурно-функциональная организация и принцип работы
ЭУЛ - элемент управляющий логикой
ЭУЛ --> ТрS (триггер состояний) + KC
20. Мультипроцессорные системы. Базовые архитектурные решения и особенности организации вычислений
Классификация:
По Флинну такие системы относятся к классу МКМД. В них каждый процессор выполняет свою программу достаточно независимо от других процессоров. В процессе решения задачи ПР должны связываться между собой в соответствии с графом взаимодействия ее частей. Это вызывает необходимость более подробно классификации МКМД систем. В настоящее время интерес к МКМД системам возрос так как:
В этих архитектурах используются высокотехничные массово производимые дешевые аппаратные средства что позволяет оптимизировать соотношении цена/стоимость.
Архитектура имеет большую гибкость и может работать как однопрограммная мощная система и как многопрограммная и как комбинации?
В основном разделение мультипроцессорных систем идет по принципу межпроцессорного обмена на системы с общей памятью, и системы с обменом сообщений.
Общая память +:
Совместимость с понятными механизмами взаимодействия ПР и ОП в однопроцессорных системах; простота программирования особенно при сложном обмене между ПР; более высокая скорость обмена; возможность кэширования.
Сообщения +:
Возможно упрощение аппаратуры, особенно по сравнению с архитектурами, поддерживающими масштабируемую когерентность кэш памяти; процедуры обмена понятны, и принуждают уделять им внимание.
У обоих конфигураций есть предел.
К первому классу относятся SMP системы(2-16 ПР), шинная топология, иногда называют UMA системами, однообразная схема включения.
Второй класс - крупномасштабные ВС с распределенной памятью. Или с массовым параллелизмом MPP. Для простоты подключения необходимо разделять основную память между узлами, соответственно необходимы связи между собой.
В общем распределение памяти имеет два главных преимущества:
Эффективный по стоимости способ управления пропускной способностью памяти. Уменьшается задержка из-за конфликтов доступа к памяти.
Совершенно естественно появление промежуточной архитектуры - где память распределена физически но является доступной для всех узлов. DSM - распределенная общая память или NUMA, так как время доступа зависит от того где эта ебаная память находится.
Хотя DSM MPP сходны но реализуются по разному, так как коммуникационная среда соответствует SMP системам
В мультипроцессорных системах все ресурсы общедоступны для процессов системы.
Архитектуры:
- с общей памятью (SMP, число ПР до 32)
- c передачей сообщений (MPP, число ПР > 120)
- мультикомпьютеры (100..500 м)
SMP MPP
Вычисления в SMP - механизм нитей (потоки, работающие в одной и той же виртуальной области памяти).
Вычисления в MPP - SPMD (одна и та же программа запущена на разных ПР).
UMA - Uniform Memory Access, доступ к различным модулям памяти выполняется одинаковым образом. Память делится на общую область и локальные разделы конкретных процессоров.
Память Пр1Память Пр2............................Общий раздел
NUMA - Non-Uniform Memory Access, доступ к памяти определяется её расположением по отношению к процессору. Общее виртуальное адресное пространство.
При распределении памяти СС-NUMA обеспечивается когерентность кэшей, что достигается введением в каждый узел справочника. Справочник содержит информацию о местоположении в системе каждой составляющей глобальной памяти, а также о состоянии кэшей. Такая система может насчитывать до 256 процессоров.
21. Многомашинные и метакомпьютерные системы. Базовые архитектурные решения и особенности организации вычислений
Многомашинные - кластера и метакомпьютеры
Кластера
У традиционных архитектур построения вычислительных систем, таких как SMP, MPP, векторных параллельных систем есть один ебаный недостаток - стоимость создаваемых систем, подчас недоступная для многих пользователей таких систем. Она оказывает очень высокой из-за усложнения аппаратных и программных составляющих системы, которые требуются для обеспечения высоких темпов роста производительности. Кластерные системы возникли как более дешевое решение проблемы недостатка вычислительных ресурсов, и основываются на использовании в своей архитектуре широко распространенных и относительно дешевых технологий, аппаратных и программных средств, таких как PC, Ethernet, Linux и т.д. Привлекательной чертой кластерных технологий является то, что они позволяют для достижения необходимой производительности объединять в единые вычислительные системы компьютеры самого разного типа, начиная от персональных компьютеров и заканчивая мощными суперкомпьютерами. С одной стороны, эти технологии используются как дешевая альтернатива суперкомпьютерам, c другой стороны, эти технологии используются для преодоления ограничений, присущих SMP системам и векторно-конвейерным компьютерам.
Кластер - это связанный набор полноценных компьютеров, используемый в качестве единого ресурса. Под понятием "полноценный компьютер" понимается завершенная компьютерная система, обладающая всем, что требуется для ее функционирования, включая процессоры, память, подсистему ввода/вывода, а также операционную систему, подсистемы, приложения и т.д. Обычно для этого годятся ПК или параллельные системы, которые могут обладать архитектурой SMP и даже NUMA. Кластеры являются слабосвязанными системами, связи узлов используется одна из стандартных сетевых технологий (Fast/Gigabit Ethernet, Myrinet) на базе шинной архитектуры или коммутатора. Поэтому они являются более дешевой в построении модификацией MPP архитектуры. Существует два подхода при создании кластерных систем:
* в единую систему объединяются полнофункциональные компьютеры, которые могут работать, в том числе, и как самостоятельные единицы, например, компьютеры учебного класса или рабочие станции лаборатории; * целенаправленно создается мощный вычислительный ресурс, в котором роль вычислительных узлов играют промышленно выпускаемые компьютеры, и тогда нет необходимости снабжать такие компьютеры графическими картами, мониторами, дисковыми накопителями и другим периферийным оборудованием, что значительно удешевляет стоимость системы. НАШ! :) В последнем случае системные блоки компьютеров, как правило, компактно размещаются в специальных стойках, а для управления системой и для запуска задач выделяется один или несколько полнофункциональных компьютеров, которые называют хост-компьютерами. Преимущества кластерной системы перед набором независимых компьютеров очевидны. Во-первых, система пакетной обработки заданий позволяет послать задание на обработку кластеру в целом, а не какому-нибудь отдельному компьютеру, что позволяет обеспечить более равномерную загрузку компьютеров. Во-вторых, появляется возможность совместного использования вычислительных ресурсов нескольких компьютеров для решения одной задачи.
Компьютеры, образующие кластер, - так называемые узлы кластера - всегда относительно независимы, что допускает остановку или выключение любого из них для проведения профилактических работ или установки дополнительного оборудования без нарушения работоспособности всего кластера. Каждый узел работает под управлением своей копии операционной системы, в качестве которой чаще всего используются стандартные операционные системы: Linux, NT, Solaris и т.п. Состав и мощность узлов может меняться даже в рамках одного кластера, давая возможность создавать неоднородные системы. Выбор конкретной коммуникационной среды определяется многими факторами: особенностями класса решаемых задач, необходимостью последующего расширения кластера и т.п. Возможно включение в конфигурацию специализированных компьютеров, например, файл-сервера, и, как правило, предоставлена возможность удаленного доступа на кластер через Internet.
Разработчики архитектур кластерных систем преследовали различные цели при их создании. Первой была фирма Digital Equipment с кластерами VAX/VMS. Целью создания этой машины было повышение надежности работы системы, обеспечение высокой готовности и отказоустойчивости системы. В настоящее время существует множество аналогичных по архитектуре систем от других производителей. Другой целью создания кластерных систем является создание дешевых высокопроизводительных параллельных вычислительных систем. Один из первых проектов, давший имя целому классу параллельных систем - кластер Beowulf - возник в центре NASA Goddard Space Flight Center для поддержки необходимыми вычислительными ресурсами проекта Earth and Space Sciences. Эта система оказалась очень удачной по отношению цена/производительность, поэтому такую архитектуру стали развивать и широко использовать в других научных организациях и институтах.
Метакомпьютинг
Новое направление в области ИТ - метакомпьютинг, главной движущей силой которого выступают высокопроизводительные приложения, требующие компьютерных архитектур с пиковыми на сегодняшний день техническими характеристиками и вызванные к жизни трудными, и наиболее значимыми для общества проблемами науки и инженерии. Метакомпьютинг можно обозначить как использование компьютерных сетей для создания распределенной вычислительной инфраструктуры национального и мирового масштаба. Сети, объединяющие высокопроизводительные компьютерные системы, могут стать средством организации вычислений следующего поколения.
Что собой представляет Internet известно сегодня любому - это множество соединенных друг с другом узлов, имеющих собственные процессоры, оперативную и внешнюю память, устройства ввода/вывода. Такая конструкция весьма напоминает многопроцессорную систему, в которой роль магистральных шин выполняет Сеть. Цель метакомпьютинга заключается в том, чтобы превратить аналогии в реальность - стереть барьеры между разнородными, пространственно распределенными вычислительными системами и образовать сверхкомпьютер или метакомпьютер, который для пользователей и программистов выступал бы в виде единой вычислительной среды, доступной с любого рабочего места (ПК или станции). Характеризуя метафору метакомпьютера, подчеркнем его виртуальность: он динамически организуется из географически распределенных ресурсов, временно делегированных фактическими владельцами. Отдельные установки, соединенные высокоскоростными сетями передачи данных, являются составными частями метакомпьютера и в то же время служат точками подключения пользователей (рисунок 1). В отличие от традиционного компьютера метакомпьютер имеет целый набор присущих только ему особенностей:
* метакомпьютер обладает огромными ресурсами, которые несравнимы с ресурсами обычных компьютеров. Это касается практически всех параметров: число доступных процессоров, объем памяти, число активных приложений, пользователей и т.д.;
* метакомпьютер является распределенным по своей природе. Компоненты метакомпьютера могут быть удалены друг от друга на сотни и тысячи километров, что неизбежно вызовет большую латентность и, следовательно, скажется на оперативности их взаимодействия;
* метакомпьютер может динамически менять свою конфигурацию. Какие-то компьютеры к нему присоединяются и делегируют права на использование своих ресурсов, какие-то отключаются и становятся недоступными. Но для пользователя работа с метакомпьютером должна быть прозрачна. Задача системы поддержки работы метакомпьютера состоит в поиске подходящих ресурсов, проверке их работоспособности, в распределении поступающих задач вне зависимости от текущей конфигурации метакомпьютера в целом;
* метакомпьютер неоднороден. При распределении заданий нужно учитывать особенности ОС, входящих в его состав. Разные системы поддерживают разные системы команд, форматы представления данных. Различные системы в разное время могут иметь различную загрузку, связь с ВС идет по каналам с различной пропускной способностью. Наконец, в состав метакомпьютера могут входить системы с принципиально различной архитектурой;
* метакомпьютер объединяет ресурсы различных организаций. Политика доступа и использование конкретных ресурсов может сильно меняться в зависимости от их принадлежности к той или иной организации. Метакомпьютер не принадлежит никому, поэтому политика его администрирования может быть определена лишь в самых общих чертах. Вместе с тем, согласованность работы огромного числа составных частей метакомпьютера предполагает обязательную стандартизацию работы всех его служб и сервисов.
Необходимо подчеркнуть принципиальную разницу метакомпьютерного подхода и программных средств удаленного доступа. В метакомпьютере этот доступ прозрачен - пользователь имеет полную иллюзию использования одной машины, но гораздо более мощной, чем та, что стоит на его столе. Он может работать с ней в рамках той же модели, которая принята на его персональном вычислителе.
- мультикомпьютерные системы, характеризуемые наличием в выч. узле ресурсов, сопоставимых с полнокровным компьютером
- кластерные ВС, характеризуемые определенным способом группировки выч. модулей
- метакомпьютеры - распределенные системы, выч. модули отдельно на значительных расстояниях.
КПД - канал прямого доступаРаспределённые вычисления - способ решения трудоёмких вычислительных задач с использованием двух и более компьютеров объединённых в сеть. Распределённые вычисления являются типом параллельных вычислений. Последний термин применяется для обозначения одновременного решения различных частей одной вычислительной задачи несколькими процессорами одного компьютера. В то время как оба типа обработки требуют, чтобы задача была сегментирована - разделена на секции, которые могли бы вычисляться одновременно, распределенное вычисление также требует, чтобы при разделение вычислительной задачи было учтено различие окружающих сред, на которых будут вычисляться различные секции задачи.
С появлением и бурным развитием Интернета всё большую популярность стала получать идея добровольного использования для распределённых вычислений компьютеров простых пользователей соединённых через Интернет.
Тенденции развития компьютерной индустрии определяются разнообразными факторами: научными открытиями, новыми промышленными технологиями, конъюктурой на финансовых рынках. В этой связи не стало исключением новое направление в области ИТ - метакомпьютинг, главной движущей силой которого выступают высокопроизводительные приложения, требующие компьютерных архитектур с пиковыми на сегодняшний день техническими характеристиками и вызванные к жизни трудными, и наиболее значимыми для общества проблемами науки и инженерии. Метакомпьютинг можно обозначить как использование компьютерных сетей для создания распределенной вычислительной инфраструктуры национального и мирового масштаба. Несмотря на то, что сегодня сети доказали свою беспрецедентную практическую полезность в качестве средства глобальной доставки различных форм информации, их потенциал раскрыт далеко не полностью. Сети, объединяющие высокопроизводительные компьютерные системы, могут стать средством организации вычислений следующего поколения.
Что собой представляет Internet известно сегодня любому - это множество соединенных друг с другом узлов, имеющих собственные процессоры, оперативную и внешнюю память, устройства ввода/вывода. Такая конструкция весьма напоминает многопроцессорную систему, в которой роль магистральных шин выполняет Сеть. Цель метакомпьютинга заключается в том, чтобы превратить аналогии в реальность - стереть барьеры между разнородными, пространственно распределенными вычислительными системами и образовать сверхкомпьютер или метакомпьютер, который для пользователей и программистов выступал бы в виде единой вычислительной среды, доступной с любого рабочего места (ПК или станции). Характеризуя метафору метакомпьютера, подчеркнем его виртуальность: он динамически организуется из географически распределенных ресурсов, временно делегированных фактическими владельцами. Отдельные установки, соединенные высокоскоростными сетями передачи данных, являются составными частями метакомпьютера и в то же время служат точками подключения пользователей. метакомпьютер обладает огромными ресурсами ; метакомпьютер является распределенным по своей природе ; метакомпьютер может динамически менять свою конфигурацию ; метакомпьютер неоднороден и тп
22. Системы с массовой параллельной обработкой. Базовые архитектурные решения и особенности организации вычислений
МРР системы относятся к классу систем МКМД - многопроцессорные системы. В них каждый процессор выполняет свою программу достаточно независимо от других процессоров. В процессе решения задачи ПР должны связываться между собой в соответствии с графом взаимодействия ее частей. В многопроцессорных системах с общей памятью(сильносвязанных) имеется память данных и команд, доступная всем процессорам. С общей памятью связываются посредством среды, основой которой может быть общая шина, множество шин, перекрестный коммутатор. В противоположность этому варианту в слабосвязанных многопроцессорных системах вся память разделена между процессорами и каждый блок памяти доступен только локальному процессору. Память и ПР фактически образуют вычислительный модуль, которые связываются между собой при помощи высокоскоростной сети обмена с коммутацией сообщений.
Сообщение это блок информации сформированный процессом отправителем таким образом, чтоб был понятен процессу получателю. Состоит из заголовка и набора данных. В заголовок входят адреса процессоров или вычислительных узлов, управляющие поля. В качестве модели топологии применяют статические формы.
В настоящее время интерес к МКМД системам возрос так как:
В этих архитектурах используются высокотехничные массово производимые дешевые аппаратные средства что позволяет оптимизировать соотношении цена/стоимость.
Архитектура имеет большую гибкость и может работать как однопрограммная мощная система и как многопрограммная и как комбинации?
В архитектурах с распределенной памятью непосредственное разделение памяти невозможно. Вместо этого ПР получают возможность доступа к совместно используемым данным посредством передачи сообщений по сети обмена. Эффективность схемы коммуникации зависит от среды, протоколов обмена, каналов обмена, пропускной способности памяти.
Сообщения +:
Возможно упрощение аппаратуры, особенно по сравнению с архитектурами, поддерживающими масштабируемую когерентность кэш памяти; процедуры обмена понятны, и принуждают уделять им внимание.
Часто в системах с общей памятью затраты времени на обмен не учитываются так как эта проблема скрыта от программиста, однако накладные расход на обмен в этих системах имеются и определяются в основном конфликтами по доступу к памяти, общей шине. В сетях с обменом сообщений по мере возрастания требований к обмену следует учитывать возможность перегрузки сети. Здесь межпроцессорный обмен связывает сетевые ресурсы: каналы, ПР, буферы сообщений. Объем передаваемой информации может быть сокращен за счет тщательного разбиения задачи на параллельные ветви и тщательного диспетчирования процесса их исполнения.
Второй класс - крупномасштабные ВС с распределенной памятью. Или с массовым параллелизмом MPP. Для простоты подключения необходимо разделять основную память между узлами, соответственно необходимы связи между собой. В противном случае ее пропускной способности просто не хватит для удовлетворения запросов поступающих от очень большого числа ПР, естественно при таком подходе также требуется реализовать связь процессоров между собой. Адресное пространство в таких системах состоит из отдельных адресных пространств, которые логически не связаны, и доступ к которым не может быть осуществлен аппаратно другим процессором. Фактически каждый модуль ПР-память представляет собой компутер. Поэтому такая модель в какой то степени приближена к многомашинным структурам. МРР-система менее эффективна с точки зрения пользователя из-за усложненной модели программирования, которая связана с применением специальных коммуникационных библиотек для организации взаимодействия между выч узлами. Необходимость реализации модели распределенной памяти объясняется тем, что Масштабируемость систем с общей памятью ограничена пропускной способностью памяти и коммуникационной среды.
В общем распределение памяти имеет два главных преимущества:
Эффективный по стоимости способ управления пропускной способностью памяти. Уменьшается задержка из-за конфликтов доступа к памяти.
Основным признаком, по которому ВС относят к архитектуре с массовой параллельной обработкой (MPP), служит число процессоров n. Обычно при n  120 считается, что система принадлежит к классу MPP. MPP системы относятся к подклассу слабо связанных ВС.
MPP системы обладают следующими характеристиками:
* физически распределенная память;
* стандартные микропроцессоры;
* наличие единственного управляющего устройства (процессора), распределяющего задания между множеством подчиненных ему устройств;
* сеть соединений с высокой пропускной способностью и малыми задержками;
* программа представляет собой множество процессов, имеющих отдельные адресные пространства
Большинство MPP систем имеют распределенную как физическую, так и виртуальную память. Однако распределение виртуальной памяти не является необходимым условием.
Преимуществами MPP систем в первую очередь является отсутствие конфликтов при доступе к распределенной памяти. Это обуславливает высокую производительность и масштабируемость (возможность, варьируя число ПЭ, создавать ВС различной производительности и стоимости). Тем не менее, в MPP системах существуют известные сложности с программированием и коммутацией. Достаточно трудно найти задачи, способные загрузить множество ПЭ. При программировании следует учитывать издержки, связанные с передачей большого объема данных по сети, и минимизировать их. Кроме того, возникает проблема переносимости между системами с различной архитектурой. Эффективность распараллеливания во многих случаях сильно зависит от деталей архитектуры MPP системы, например, топологии соединения ПЭ. Самой эффективной топологией является "каждый с каждым", однако в MPP системы с большим числом ПЭ это технически трудно реализуемо. Одна из самых важных характеристик суперкомпьютеров MPP-архитектуры, имеющих физически распределенную память, - так называемый диаметр системы (макс. длина, которая может понадобиться посланному сообщению, при прохождении из одного узла MPP-компьютера в другой). Длина измеряется, грубо говоря, количеством промежуточных узлов, которые надо миновать на пути к конечному узлу. Применяются топология двухмерной решетки, тора. Это позволяет уменьшить диаметр системы. Можно рассматривать в качестве примера - систолические системы.
23. Кластерные вычислительные системы
У традиционных архитектур построения вычислительных систем, таких как SMP, MPP, векторных параллельных систем есть один недостаток - стоимость создаваемых систем, подчас недоступная для многих пользователей таких систем - образовательных и научно-исследовательских организаций. Она оказывает очень высокой из-за усложнения аппаратных и программных составляющих системы, которые требуются для обеспечения таких темпов роста производительности. Кластерные системы возникли как более дешевое решение проблемы недостатка вычислительных ресурсов, и основываются на использовании в своей архитектуре широко распространенных и относительно дешевых технологий, аппаратных и программных средств, таких как PC, Ethernet, Linux и т.д. Использование массовых технологии в кластерных системах стало возможным благодаря значительному прогрессу в развитии компонентов обычных вычислительных систем, таких как центральные процессоры, операционные системы, коммуникационные среды.
Привлекательной чертой кластерных технологий является то, что они позволяют для достижения необходимой производительности объединять в единые вычислительные системы компьютеры самого разного типа, начиная от персональных компьютеров и заканчивая мощными суперкомпьютерами. С одной стороны, эти технологии используются как дешевая альтернатива суперкомпьютерам, c другой стороны, эти технологии используются для преодоления ограничений, присущих SMP системам и векторно-конвейерным компьютерам.
Кластер - это связанный набор полноценных компьютеров, используемый в качестве единого ресурса. Под понятием "полноценный компьютер" понимается завершенная компьютерная система, обладающая всем, что требуется для ее функционирования, включая процессоры, память, подсистему ввода/вывода, а также операционную систему, подсистемы, приложения и т.д. Обычно для этого годятся персональные компьютеры или параллельные системы, которые могут обладать архитектурой SMP и даже NUMA. Кластеры являются слабосвязанными системами, связи узлов используется одна из стандартных сетевых технологий (Fast/Gigabit Ethernet, Myrinet) на базе шинной архитектуры или коммутатора. Поэтому они являются более дешевой в построении модификацией MPP архитектуры. Существует два подхода при создании кластерных систем:
* в единую систему объединяются полнофункциональные компьютеры, которые могут работать, в том числе, и как самостоятельные единицы, например, компьютеры учебного класса или рабочие станции лаборатории; - Беовульф
* целенаправленно создается мощный вычислительный ресурс, в котором роль вычислительных узлов играют промышленно выпускаемые компьютеры, и тогда нет необходимости снабжать такие компьютеры графическими картами, мониторами, дисковыми накопителями и другим периферийным оборудованием, что значительно удешевляет стоимость системы. - в универе
В последнем случае системные блоки компьютеров, как правило, компактно размещаются в специальных стойках, а для управления системой и для запуска задач выделяется один или несколько полнофункциональных компьютеров, которые называют хост-компьютерами. Преимущества кластерной системы перед набором независимых компьютеров очевидны. Во-первых, система пакетной обработки заданий позволяет послать задание на обработку кластеру в целом, а не какому-нибудь отдельному компьютеру, что позволяет обеспечить более равномерную загрузку компьютеров. Во-вторых, появляется возможность совместного использования вычислительных ресурсов нескольких компьютеров для решения одной задачи.
Кластерные системы
Как уже было сказано раньше вычислительный кластер - это совокупность компьютеров, объединенных в рамках некоторой сети для решения одной задачи, которая для пользователя представляется в качестве единого ресурса. Такую концепцию кластера впервые предложила и реализовала в начале 80-х корпорация Digital Equipment, которая и по сей день развивает эту технологию
Понятие "единый ресурс" означает наличие программного обеспечения, дающего возможность пользователям, администраторам и прикладным программам считать, что имеется только одна сущность, с которой они работают - кластер. Например, система пакетной обработки кластера позволяет послать задание на обработку кластеру, а не какому-нибудь отдельному компьютеру. Более сложным примером являются системы баз данных. Практически у всех производителей систем баз данных имеются версии, работающие в параллельном режиме на нескольких машинах кластера. В результате приложения, использующие базу данных, не должны заботиться о том, где выполняется их работа. СУБД отвечает за синхронизацию параллельно выполняемых действий и поддержание целостности базы данных.
Компьютеры, образующие кластер, - так называемые узлы кластера - всегда относительно независимы, что допускает остановку или выключение любого из них для проведения профилактических работ или установки дополнительного оборудования без нарушения работоспособности всего кластера. В качестве вычислительных узлов в кластере обычно используются однопроцессорные персональные компьютеры, двух- или четырехпроцессорные SMP-серверы. Каждый узел работает под управлением своей копии операционной системы, в качестве которой чаще всего используются стандартные операционные системы: Linux, NT, Solaris и т.п. Состав и мощность узлов может меняться даже в рамках одного кластера, давая возможность создавать неоднородные системы. Выбор конкретной коммуникационной среды определяется многими факторами: особенностями класса решаемых задач, необходимостью последующего расширения кластера и т.п. Возможно включение в конфигурацию специализированных компьютеров, например, файл-сервера, и, как правило, предоставлена возможность удаленного доступа на кластер через Internet.
Цели создания кластерных систем
Разработчики архитектур кластерных систем приследовали различные цели при их создании. Первой была фирма Digital Equipment с кластерами VAX/VMS. Целью создания этой машины было повышение надежности работы системы, обеспечение высокой готовности и отказоустойчивости системы. В настоящее время существует множество аналогичных по архитектуре систем от других производителей. Другой целью создания кластерных систем является создание дешевых высокопроизводительных параллельных вычислительных систем. Один из первых проектов, давший имя целому классу параллельных систем - кластер Beowulf - возник в центре NASA Goddard Space Flight Center для поддержки необходимыми вычислительными ресурсами проекта Earth and Space Sciences. Эта система оказалась очень удачной по отношению цена/производительность, поэтому такую архитектуру стали развивать и широко использовать в других научных организациях и институтах.
Отказоустойчивые кластеры (кластеры класса VAX)
Для обеспечения надежности и отказоустойчивости вычислительных систем применяется множество различных аппаратурных и программных решений. Например, в системе может дублироваться все подверженные отказам элементы - источники питания, процессоры, оперативная и внешняя память. Такие отказоустойчивые системы с резервированием компонентов применяются для решения задач, в которых недостаточно надежности обычных вычислительных систем, оцениваемой в настоящий момент вероятностью безотказной работы 99%. В таких задачах требуется вероятность 99,999% и выше. Такую надежность можно достичь применяя отличные от приведенного выше методы повышения отказоустойчивости. В отличие от отказоустойчивых систем с избыточными компонентами, а также различных вариантов многопроцессорности, кластеры объединяют относительно независимые друг от друга машины, каждую из которых можно остановить для профилактики или реконфигурирования, не нарушая при этом работоспособности кластера в целом. Высокая производительность кластера и сведение к минимуму времени простоев приложений достигается благодаря тому, что: * в случае сбоя ПО на одном из узлов приложение продолжает функционировать или автоматически перезапускается на других узлах кластера; * выход из строя одного из узлов (или нескольких) не приведет к краху всей кластерной системы; * профилактические и ремонтные работы, реконфигурацию или смену версий программного обеспечения, как правило, можно осуществлять в узлах кластера поочередно, не прерывая работы других узлов.
Неотъемлемой частью кластера является специальное программное обеспечение, которое, собственно, и решает проблему восстановления узла в случае сбоя, а также решает другие задачи. Кластерное ПО обычно имеет несколько заранее заданных сценариев восстановления работоспособности системы, а также может предоставлять администратору возможности настройки таких сценариев. Восстановление после сбоев может поддерживаться как для узла в целом, так и для отдельных его компонентов - приложений, дисковых томов и т.д. Эта функция автоматически инициируется в случае системного сбоя, а также может быть запущена администратором, если ему, например, необходимо отключить один из узлов для реконфигурации.
Кластеры могут иметь разделяемую память на внешних дисках, как правило, на дисковом массиве RAID. Дисковый массив RAID - это серверная подсистема ввода- вывода для хранения данных большого объема. В массивах RAID значительное число дисков относительно малой емкости используется для хранения крупных объемов данных, а также для обеспечения более высокой надежности и избыточности. Подобный массив воспринимается компьютером как единое логическое устройство.
Узлы кластера контролируют работоспособность друг друга и обмениваются специфической "кластерной" информацией, например, о конфигурации кластера, а также передавать данные между разделяемыми накопителями и координировать их использование. Контроль работоспособности осуществляется с помощью специального сигнала, который узлы кластера передают друг другу, для того чтобы подтвердить свое нормальное функционирование. Прекращение подачи сигналов с одного из узлов сигнализирует кластерному программному обеспечению о произошедшем сбое и необходимости перераспределить нагрузку на оставшиеся узлы. В качестве примера рассмотрим отказоустойчивый кластер VAX/VMS.
Кластеры VAX/VMS
Компания DEC первой анонсировала концепцию кластерной системы в 1983 году, определив ее как группу объединенных между собой вычислительных машин, представляющих собой единый узел обработки информации. По существу VAX-кластер представляет собой слабосвязанную многомашинную систему с общей внешней памятью, обеспечивающую единый механизм управления и администрирования. VAX-кластер обладает следующими свойствами: * Разделение ресурсов. Компьютеры VAX в кластере могут разделять доступ к общим ленточным и дисковым накопителям. Все компьютеры VAX в кластере могут обращаться к отдельным файлам данных как к локальным. * Высокая готовность. Если происходит отказ одного из VAX-компьютеров, задания его пользователей автоматически могут быть перенесены на другой компьютер кластера. Если в системе имеется несколько контроллеров HSC и один из них отказывает, другие контроллеры HSC автоматически подхватывают его работу. * Высокая пропускная способность. Ряд прикладных систем могут пользоваться возможностью пар. выполнения заданий на нескольких компьютерах кластера. * Удобство обслуживания системы. Общие базы данных могут обслуживаться с единственного места. Прикладные программы могут инсталлироваться только однажды на общих дисках кластера и разделяться между всеми компьютерами кластера. * Расширяемость. Увеличение вычислительной мощности кластера достигается подключением к нему дополнительных VAX-компьютеров. * Работа VAX-кластера определяется двумя главными компонентами. Первым компонентом является высокоскоростной механизм связи, а вторым - системное программное обеспечение, которое обеспечивает клиентам прозрачный доступ к системному сервису. Физически связи внутри кластера реализуются с помощью трех различных шинных технологий с различными характеристиками производительности. Шина связи компьютеров CI (Computer Interconnect) работает со скоростью 70 Мбит/с и используется для соединения компьютеров VAX и контроллеров HSC с помощью коммутатора Star Coupler. Компьютеры VAX могут объединяться в кластер также посредством локальной сети Ethernet, используя NI - Network Interconnect (так называемые локальные VAX-кластеры), однако производительность таких систем сравнительно низкая из-за необходимости делить пропускную способность сети Ethernet между компьютерами кластера и другими клиентами сети. Также кластеры могут строиться на основе шины DSSI (Digital Storage System Interconnect). На шине DSSI могут объединяться до четырех компьютеров VAX нижнего и среднего класса. Каждый компьютер может поддерживать несколько адаптеров DSSI. Отдельная шина DSSI работает со скоростью 4 Мбайт/с (32 Мбит/с) и допускает подсоединение до 8 устройств. Системное программное обеспечение VAX-кластеров Для гарантии правильного взаимодействия процессоров друг с другом при обращениях к общим ресурсам, компания DEC использует распределенный менеджер блокировок DLM (Distributed Lock Manager). Очень важной функцией DLM является обеспечение когерентного состояния дисковых кэшей для операций ввода/вывода операционной системы и прикладных программ. Например, в приложениях реляционных СУБД DLM несет ответственность за поддержание согласованного состояния между буферами базы данных на различных компьютерах кластера. Задача поддержания когерентности кэш-памяти ввода/вывода между процессорами в кластере подобна задаче поддержания когерентности кэш-памяти в сильно связанной многопроцессорной системе, построенной на базе некоторой шины. Блоки данных могут одновременно появляться в нескольких кэшах и если один процессор модифицирует одну из этих копий, другие существующие копии не отражают уже текущее состояние блока данных. Концепция захвата блока (владения блоком) является одним из способов управления такими ситуациями. Работа с DLM связана со значительными накладными расходами. Накладные расходы в среде VAX/VMS могут быть большими, требующими передачи до шести сообщений по шине CI для одной операции ввода/вывода. Накладные расходы могут достигать величины 20% для каждого процессора в кластере.
24.Системы коммуникаций многопроцессорных ЭВМ и систем
Коммуникационная система ВС представляет собой сеть, узлы которой связаны трактами передачи данных. В роли узлов могу выступать процессоры, модули память, устройства ввода/вывода, коммутаторы либо несколько перечисленных элементов, объединенных в группу. Организация внутренних коммуникаций ВС называется топологией.
Топологию сети определяет множество узлов N, объединенных множеством каналов С. Связь между узлами обычно реализуется по двухточечной схеме. Любые два узла связанные каналом связи называются соседями или смежными узлами. Канал С соединяет узел-источник с узлом-получателем. Часто пары узлов соединят двумя каналами в разных направлениях. Канал характеризуется:
Шириной - числом сигнальных линий;
Частотой - скоростью передачи битов по каждой сигнальной линии;
Задержкой - временем передачи бита из Х в У
Для большинства каналов задержка находится в прямой зависимости от длины канала и скорости распространения сигнала(физической среды).
В зависимости от того, остается ли конфигурация сети неизменной, по крайней мере при выполнении задачи, различают сети со статической и динамической топологией. В статических конфигурация сети фиксирована, а в динамических может быть оперативно изменена в процессе вычислений с помощью программных средств.
Узел может быть приемником, передатчиком, коммутатором, в сетях с непосредственными связями узел одновременно терминальный и коммутатор и сообщения пересылаются напрямую, в сетях с косвенными связями сообщения передаются опосредованно с помощью выделенных коммутирующих узлов. Тремя важнейшими атрибутами сети являются:
Стратегия синхронизации
Стратегия коммутации
Стратегия управления
Синхронизация: синхронная и асинхронная. В синхронных сетях все действия жестко согласованы по времени, что обеспечивается за счет одного ГТИ, сигналы которого транслируются во все узлы. В асинхронных сетях ГТИ нет, а функции синхронизации распределены по всей системе, причем в разных частях часто используются свои ГТИ.
Коммутация: соединений и пакетов. Пакет - группа бит, для обозначения применяют также термин сообщение. В сетях с коммутацией соединений путем соответствующей установки коммутирующих элементов сеть устанавливает тракт от узла источника к узлу получателю, сохраняющийся пока доставляемый пакет не достигнет цели. Пересылка сообщений между узлами производится всегда по одному и тому же маршруту. Сети с коммутацией пакетов предполагают что сообщение само найдет нужный путь. Маршруты каждый раз могут быть иными. Пакет проходит по узлам сети, узел запоминает его в буферной памяти и делает вывод что с ним делать дальше. В зависимости от загруженности сети принимается решение о возможности немедленной пересылки пакета к следующему узлу и о его дальнейшем маршруте. Если тракты все заняты в буфере узла формируется очередь пакетов.
Управление. В некоторых сетях, особенно с переключением соединений, принято централизованное управление. Процессоры посылают запрос на обслуживание в единый контроллер сети, который производит арбитраж запросов с учетом заданных приоритетов и устанавливает нужный маршрут. - Шинная топология, Процессорные матрицы, вообще большинство. В схемах с децентрализованным управлением функции разделены по узлам сети. Вариант с централизацией проще реализуется, но расширение сети связано со значительными трудностями. Децентрализованные сети в плане подключения гибче, но взаимодействие в таких сетях значительно сложнее.
В ряде сетей взаимодействие осуществляется с помощью многих коммутаторов, но существуют сети с одним. Наличие большого числа позволяет использовать простые механизмы переключения, но увеличивает время передачи, подобные сети - многоступенчатые.
Описание сети:
Размер(N) - количество узлов
Число связей(I)
Диаметр(D) - минимальный путь между самыми отдаленными узлами
Порядок узла(d) - число связей узла в среднем, увеличение ведет к увеличению сложности коммутаторов и задержки, но также ведет к возможности реализации топологий с меньшим диавметром.
Пропускная способность(W) - количество информации в единицу времени
Задержка(T) - прохождения пакета через сеть
Связность(Q) - число связей, которые нужно удалить, чтобы сеть распалась на две непересекающиеся - характеристика устойчивости сети к повреждениям
Ширина бисекции(B) - срез разделяющий сеть примерно пополам - характеристика количества одновременно передаваемых пакетов
Полоса бисекции(b) - наименьшая полоса пропускания по всем бисекциям сети. - характеризует пропускную способность сети из одной половины в другую
Кардинальным вопросом при выборе топологии является определение следующего узла передачи сообщения. Основа маршрутизации - адреса узлов. В сущности функция маршрутизации и определяет сетевую топологию.
Функции:
Перестановка(гиперкуб)
Тасование(4)
Баттерфляй
Реверсирование
Сдвиг
ILLIAC4
Циклический сдвиг
Статические топологии:
Линейная топология, Кольцевые, звезда, дерево, решетка, полносвязная, гиперкуб, Динамические:
Кроссбар, Баньян, Омега, Дельта, Бенеша, Клоша, N-куб
Маршрутизация сообщений несколько способов:
Коммутация каналов - установка соединения и потом передача
С промежуточным хранением - при переходе от узла к узлу сохраняются и ретранслируются.
Виртуальная - расширений предыдущей, позволяет осуществлять переключения в сети.
Червячная - пакет растягивается неделимыми единицами по узлам сети - как бы прокладывая себе дорогу.
Документ
Категория
Разное
Просмотров
621
Размер файла
18 944 Кб
Теги
шпаргалки, шпоры, сапр
1/--страниц
Пожаловаться на содержимое документа