1 Логические функции, Способы описания функций алгебры логики
Главная > Документ
| Информация о документе | |
| Дата добавления: | |
| Размер: | |
| Доступные форматы для скачивания: |
1) Логические функции, Способы описания функций алгебры логики.
Другие названия ФАЛ(функцией алгебры логики): логическая, булева или переключательная функция. В алгебре логики переменная может принимать одно из двух значений: True и False.
2 способа описания:
Словесный способ . Здесь все случаи, при которых функция принимает значения 0 или 1, опи- сываются словесно. Так, функцию «ИЛИ» со многими аргументами можно описать следующим обра- зом: функция принимает значение 1, если хотя бы один из аргументов принимает значение 1, иначе значение функции равна 0.
Табличный способ . Булева функция задается в виде таблицы истинности. В левой части таблицы истинности записываются все возможные n-разрядные двоичные комбинации аргументов,а в правой – значения функции на этих наборах. Таблица ис- тинности содержит 2n строк.
Числовой способ. Функция задается в виде последовательности десятичных эквивалентов тех наборов аргументов, на которых функция принимает значение 1. Например, двоичные наборы 010 и 101 имеют десятичные номера 2 и 5 соответственно.
Аналитический способ. Предполагает описание ФАЛ в виде алгебраического выражения, получаемого путем применения к аргументам операций булевой алгебры.
К
оординатный способ. При этом способе задания таблица истинности заменяется коорди- натной картой состояний, известной под названием карты Карно. Такая карта содержит 2n клеток по числу возможных наборов из n переменных.
Г
рафический, или геометрический способ. Булева функция задается с помощью n-мерного куба. Множество наборов, на которых определена функция n переменных, представляется верши- нами n-мерного куба. Отметив точками те вершины куба, в которых функция принимает единичное (либо нулевое) значение, получаем геометрическое представление функции.
2) Элементарные функции алгебры логики.
Алгебра логики (АЛ) является основным инструментом синтеза и анализа дискретных автоматов всех уровней.
Алгебра логики называют также Булевой алгеброй.
АЛ базируется на трёх функциях, определяющих три основные логические операции.
Функция отрицания (НЕ). f1 =`X
Функция логического умножения (конъюнкции). Функция логического умножения записывается в виде f2=X1·X2. Конъюнкцию называют функцией И, элемент, реализующий эту функцию, элементом И.
Логическое сложение (дизъюнкция). Функция логического сложения записывается в виде f3=X1 + X2. функцию дизъюнкции часто называют функцией ИЛИ.
3) Правила алгебры логики.
Правила эти определяются для двух возможных логических значений «1» (True) и «0» (False), а также трех базовых логических опе- раций: «НЕ», «И» и «ИЛИ. Базовые логические операции перечислены в порядке пониже- ния их приоритетности. Учет приоритетности операций позволяет сократить число скобок при записи логических выражений.
3
) дистрибутивность
4) Понятие логического базиса.
Логическим базисом называется минимальный необходимый набор логических функций, с помощью которых может быть реализовано логическое выражение любой сложности.
Функции И, ИЛИ, НЕ образуют основной логический базис.
«И-НЕ» (базис Шеффера)
«ИЛИ-НЕ» (базис Пирса или функция Вебба).
5) Аналитическое представление булевых функций.
При аналити- ческой записи ФАЛ представляется либо в виде логической суммы элементарных логических произ- ведений (дизъюнкции элементарных конъюнкций), либо в виде логического произведения элемен- тарных логических сумм (конъюнкции элементарных дизъюнкций). Первая форма записи носит на- звание дизъюнктивной нормальной формы (ДНФ), вторая – конъюнктивной нормальной формы (КНФ).
Элементарной конъюнкцией (элементарным логическим произведением) называют логическое произведение любого количества переменных (аргументов)
Дизъюнктивная нормальная форма (ДНФ) – это логическая сумма элементарных логических произведений
Минтерм (единичный набор функции) – это логическое произведение всех переменных, взятых с отрицанием или без.
Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ, состоящая из всех минтермов булевой функции. Для получения СДНФ на основе таблицы истинности необходимо:
1 )каждый из входных наборов, на которых булева функция принимает значение «1»,
представить в виде элементарного произведения (конъюнкции).
2 )полученные элементарные логические произведения объединить знаками логического сложения (дизъюнкции).
6) Минимизация логических функций и ее цели.
Проблема минимизации логических выражений проистекает из практических задач создания логических схем. В качестве исходной аналитической формы обычно рассматривают совершенные ДНФ и КНФ, которые во многих случаях оказываются излишне сложными, из-за чего их техническая либо программная реализация получается избыточной. Для упрощения СДНФ и СКНФ используются различные методы минимизации – преобразования логической функции с целью упрощения ее ана- литической записи.
7) Минимизация логических функций методом Квайна
1. Нахождение простых импликант
2. Составление импликантной матрицы и расстановка меток избыточности
3 
. Нахождение существенных импликант и исключение связанных с ними строк и столбцов
4. Определение и запись минимальной нормальной формы
8) Минимизация по методу Квайна – Мак-Класски
Метод Квайна – Мак-Класски отличается от метода Квайна только в той части, которая связана со способом нахождения простых импликант. Описанная модификация заменяет лишь первый шаг метода Квайна, при этом все последую- щие шаги производятся аналогично методу Квайна.
9) Минимизация логических функций методом Петрика.
Метод Петрика (Petrick) также имеет целью упрощение метода Квайна, но в части нахожде- ния всех тупиковых форм по импликантной матрице.
1
0) Минимизация логических функций методом карт Карно.
11) Минимизация частично определенных функций .
Наиболее удобно это производить с помощью карт Карно.
Принимаю * за 1 или 0.
12) Сигналы в цифровой схемотехнике.
Цифровой сигнал – это сигнал, который может принимать два значения, рассматриваемые как логическая «1» и логический «0». Устройства, работающие только с цифровыми сигналами, называ- ются цифровыми устройствами.
положительный сигнал (сигнал положительной полярности) – сигнал, активный уровень которого – логическая «1» («0» соответствует отсутствию сигнала);
отрицательный сигнал (сигнал отрицательной полярности) – сигнал, активный уровень которого – логический «0» («1» соответствует отсутствию сигнала);
13) Логические элементы и их графическое обозначение.
Логический элемент «НЕ» — противоположное значение сигнала.
Логический элемент «И» — всегда 1
Л
огический элемент «ИЛИ» -всегда 0
Л
огический элемент «И-НЕ» -0
Э
лемент «ИЛИ-НЕ» -1
14) Положительная и отрицательная логика.
Н
апряжения на входах и выходах логических элементов могут принимать два уровня: высо- кий (H – high) и низкий (L –low). Если высокий уровень соответствует логической «1», а низкий уро- вень – логическому «0», то принято считать, что логический элемент работает с положительной логи- кой. Если высокий уровень соответствует логическому «0», а низкий уровень – логической «1», то элемент работает с отрицательной логикой
15) Мультиплексоры и демультиплексоры.
Mультипле́ксор — устройство, имеющее несколько сигнальных входов, один или более управляющих входов и один выход. Мультиплексор позволяет передавать сигнал с одного из входов на выход; при этом выбор желаемого входа осуществляется подачей соответствующей комбинации управляющих сигналов.
Мультиплексоры могут использоваться для преобразования параллельного двоичного кода в последовательный. Мультиплексоры могут использоваться в, триггерных устройствах,
Д
емультиплексор Они обеспечивают подключение единственного входа к одному из m выходов. При необходимости увеличить число выходных каналов можно построить логическую струк- туру демультиплексорного дерева. мультиплексор можно построить на основе точно таких же схем логического «И», как и при построении мультиплексора.
16) Шифраторы и дешифраторы.
Шифратором (кодером) называется комбинационное логическое устройство для преобразо- вания n-разрядного унитарного кода в m-разрядный параллельный код.
Максимальное число входов шифраторов не превышает количества возможных комбинаций выходных сигналов (n Дешифратором (декодером) называют устройство с несколькими входами и выходами, у ко- торого определённым комбинациям входных сигналов соответствует активное состояние одного из выходо
Дешифратор называется полным , если число выходов равно максимально возможной разрядности выходного слова (
). Дешифратор называется неполным , если часть входных разрядов не используется (то есть число выходов меньше ).
они могут преобразовывать двоичный код в разные системы счисления
17) Преобразователи кодов.
Преобразователи кодов (конвертеры) обеспечивают перевод информации из одной формы в другую
Шифраторы, дешифраторы- преобразователи кодов.
18) Схемы контроля четности.
Простой и эффективный способ обнаружения ошибок при записи, чтении и передаче информации основан на допущении, что в каждый момент времени ошибка может возникнуть только в одном разряде, и проявляется она в лишней единице или в потере единицы. В обоих случаях число единиц в коде изменяется на одну.Если передаваемая кодовая комбинация содержит чётное число единиц по всем разрядам, а на конце линии передачи это число окажется нечётным, значит, появилась ошибка
На передающей стороне формируется контрольный, или паритетный бит. бит передаётся вместе с информацией.
Паритет может быть чётным или нечётным
В случае нечётного паритета контрольный бит формируется таким образом, чтобы сумма всех единиц в передаваемом коде, включая контрольный бит, была чётной. На практике нечётный паритет используется чаще, так как позволяет фиксировать полное пропадание информации
При проверке как чётности, так и нечётности в случае отсутствия ошибки на выходе схемы контроля обычно формируется логическая «1», а при ошибочном – логический «0».
19) Цифровые компараторы.
логическое устройство с двумя входами, на которые подаются два разных двоичных слова равной в битах длины и тремя двоичными выходами, на которые выдаётся сравнения входных слов, — первое слово больше второго, меньше или слова равны.
Компараторы широко используются в вычислительной технике, измерительной технике, радио- и проводной связи, бытовых приборах. Например, цифровые часы с будильником содержат цифровой компаратор, при совпадении текущего времени с заданным подается звуковой сигнал.
20) Полусумматор и одноразрядный полный сумматор.
Полусумматор позволяет вычислять сумму A+B , где A и B — это разряды двоичного числа,
Поскольку полусумматор не имеет входа для приёма единицы переноса, то он может быть использован только при сложении младших разрядов чисел. При сложении старших разрядов необ- ходимо использовать так называемый полный сумматор, который учитывает возможный перенос из предшествующего младшего разряда.
Полные сумматоры могут использоваться также для суммирования чисел в отрицательной логике.
На базе полных сумматоров можно реализовать сложение многоразрядных чисел, причём суммирование может быть либо последовательным, либо параллельным.
Сумматор может вычислять не только сумму, но и разность входных кодов, то есть работать в качестве вычитателя. Для этого нужно вычитаемое поразрядно инвертировать, а на вход переноса младшего разряда подать единичный сигнал.
21)Последовательные и параллельные многоразрядные сумматоры.
Используя одноразрядный сумматор, можно построить суммирующее устройство для сложения многоразрядных двоичных чисел. Различают многоразрядные последовательные и параллельные сумматоры.
Последовательный сумматор состоит из одноразрядного сумматора, на входы которого из сдвигающих регистров, хранящих слагаемые А и В, подаются по тактам разряд за разрядом коды этих чисел, начиная с младшего разряда
Недостатком последовательного сумматора является то, что выполнение операции сложения растягивается на множество тактов,
Значительно меньшее время выполнения операции имеет параллельный сумматор . В этом устройстве операция сложения производится одновременно во всех разрядах чисел
22) Программируемые логические устройства.
Программирование ПЛУ осуществляет пользователь – создатель электронной аппаратуры
В процессе программирования в схеме происходят обратимые и необратимые изменения ее началь- ной структуры
. Главное преимущество ПЛУ по сравнению с другими специализированными мик- росхемами – малое время создания нужного варианта схемы
Развитие ПЛУ идет по пути совершенствования их архитектуры и технологии, расширения возможностей и быстродействия, и все это при одновременном снижении потребляемой мощности.
Программируемые логические матрицы и Программируемая матричная логика
Программируемые логические матрицы представляют собой наиболее универсальный вари- ант ПЛУ. В них имеется возможность программировать как матрицу элементов «И», так и матрицу элементов «ИЛИ»
23) Понятие последовательностной схемы.
Последовательностными называют такие логические устройства, в которых выходной сигнал зависит не только от текущих входных логических значений, но и от тех, которые действовали на входе в предыдущие моменты времени
Последовательностная схема состоит как из логических, так и запоминающих элементов
Следовательно, здесь речь идет о хранении результатов воздействия последовательности входных сигналов в предыдущие такты. Поэтому последовательностные схемы называют также многотактными
В последовательностных схемах , как уже отмечалось, кроме логических элементов, обязательно содержатся также элементы памяти, способные хранить установленное состояние неограниченно долго, во всяком случае до следующего такта.
24) RS – триггеры.
RS-триггер – это элемент с двумя входами (S и R) и двумя выходами – прямым (Q) и инверсным (Q ).
триггер, который сохраняет своё предыдущее состояние при нулевых входах и меняет своё выходное состояние при подаче на один из его входов единицы.
RS-триггер используется для создания сигнала с положительным и отрицательным фронтами, отдельно управляемыми посредством стробов, разнесённых во времени.
Асинхронный RS-триггер (или RS-защелка) снабжен только двумя информационными входами: входом сброса R и входом установки S.
Синхронный RS-триггер может быть из получен асинхронного введением дополнительной логической схемы, которая формирует на его входах активные сигналы только при наличии дополнительного сигнала синхронизации на входе
Он имеет один информационный вход D и один тактирующий вход C.
запоминает состояние входа и выдаёт его на выход.
П
о сигналу синхронизации в D-триггер пере- писывается информация, в данный момент присутствующая на входе D. По определению такой триг- гер может быть только синхронным
информация на выходе остается неизменной вплоть до прихода следующего импульса синхронизации.
D-триггер можно образовать из любых RS- или JK-триггеров
26) JK – триггеры.
работает так же как RS-триггер, с одним лишь исключением: при подаче логической единицы на оба входа J и K состояние выхода триггера изменяется на противоположное
На базе JK-триггера возможно построить D-триггер или Т-триггер
Универсальный JK-триггер имеет два информационных входа J и K
Универсальность JK-триггера состоит в том, что он может выполнять функции RS-, Т- и D-триггеров.
Комбинированный JK-триггер отличается от универсального наличием дополнительных асинхронных входов S и R для предварительной установки триггера в определенное состояние (логической 1 или 0).
П
ри построении счетчиков возникает необходимость в триггере
имеет один информационный вход T.
Основное свойство T-триггера − деление входной частоты на 2
Очередное состояние Т- триггера определяется лишь его состоянием в предыдущем такте
28) DV – триггеры и TV – триггеры.
D
V-триггер представляет собой модификацию D-триггера
D-триггер с разрешаю-щим входом называют DV-триггером. При V= 1 он работает как D-триггер, а при V=0 сохраняет свое состояние.
Наличие V -входа расширяет функциональные возможности D-триггера , позволяя в нужные моменты времени сохранять информацию на выходах в течении требуемого числа тактов.
Асинхронные и синхронные TV-триггеры могут быть получены на базе JK-триггера
29) Двухступенчатые триггеры.
Двухступенчатый триггер состоит из двух последовательно соединенных ступеней, причем, каждая ступень содержит по синхронному RS-триггеру
Первая ступень – ведущая или М-секция принимает информацию с входных линий.
Состояние выходов ведущей ступени подается на вторую ступень – ведомую.S секция.
После снятия синхроимпульса приём информации в первую ступень триггера запрещается, а уже имеющаяся информация из первой ступени переписывается во вторую и появляется на выходе триггера.
30) Регистры хранения.
Регистром называется последовательностное устройство, предназначенное для записи, хране- ния и/или сдвига информации, представленной в виде многоразрядного двоичного кода.
Элементами структуры регистров является синхронные триггеры D-типа или JK-типа с дина- мическим или статическим управлением
Занесение информации в регистр называют операцией ввода или записи.
Выдачу информации внешним устройствам называют операцией вывода, или считыва- ния.
В параллельных регистрах информация заносится и считывается параллельно.(для хранения двоичной информации небольшого объёма в течение короткого промежутка времени)
В последовательных регистрах запись и считывание информации производится последова- тельно (разряд за разрядом), начиная со старшего либо младшего разряда регистра.
31) Сдвиговые регистры.
Различают два вида сдвигов: вправо и влево.
Сущность сдвига состоит в том, что с приходом каждого тактового импульса происходит пе- резапись содержимого каждого триггера в соседний триггер без изменения порядка следования еди- ниц и нулей.
Регистры сдвига обычно строятся на базе D- и JK-триггеров.
Регистр, позволяющий производить сдвиг информации в обоих направлениях, называется ре- версивным.
32) Двоичные счетчики с последовательным переносом.
К двоичным относятся счетчики, модуль счета которых равен целой степени числа 2.
Наиболее простую внутреннюю структуру имеют двоичные счетчики с последовательным переносом. В них переключение каждого последующего триггера может произойти только после пе- реключения предыдущего.
Главное достоинство счётчиков с последовательным переносом – простота схемы.
Основной недостаток – сравнительно низкое быстродействие, поскольку триггеры срабатывают последователь- но, один за другим.
33) Двоичные счетчики с параллельным переносом.
Время установления выходного кода счетчика можно уменьшить, если разрядные триггеры будут переключаться не последовательно, а одновременно. Для этого нужно отказаться от асинхрон- ных триггеров в пользу синхронных Т-триггеров и определить алгоритм переключения каждого раз- рядного триггера.
Срабатывание триггеров параллельного счётчика происходит синхронно, задержка переклю- чения всего счётчика равна задержке переключения одного триггера.
Если же для формирования сигнала переноса использовать инверсные выходы триггеров разрядов, счетчик будет вычитающим.
В схемном отношении счётчик с параллельным переносом сложнее счётчиков с последова- тельным переносом
34) Счетчики с произвольным коэффициентом пересчета.
Счетчики с коэффициентом пересчета строятся на основе двоичных счетчиков.
Принцип работы таких счетчиков заключается в исключении «лишних» устойчивых М состояний у двоичного счетчика с коэффициентом пересчета 2 n .
В счетчиках с произвольным порядком счета в процессе счета счетчик принимает состояния, не соответствующие его эквивалентному представлению в двоичном коде
35) Кольцевой счетчик и счетчик Джонсона.
Построены на базе регистров сдвига, где информационный вход первого триггера соединен с выходом последнего триггера. В результате триггеры регистра сдвига образуют замкнутое кольцо.
Если в один из триггеров регистра ввести логическую единицу, то эта единица с каждым так- товым импульсом будет переходить от одного триггера к другому, повторно возвращаясь в данную позицию с циклом, равным числу триггеров в кльце.
если одну из связей между триггерами сделать перекрёстной, то есть вход одного из триггеров соединить с инверсным выходом предыдущего триггера. Такие устройства называют счётчиками Джонсона.
Недостатки – повышенный расход триггеров и высокая вероятность сбоев
П
оследний недостаток устраняют введением корректирующей логиче- ской цепи, следящей за состоянием триггеров. При появлении ложных сигналов на вход подаются импульсы, исправляющие положение в новом цикле
36) Метрики параллельных вычислений.
Метрики параллельных вычислений — это система показателей, позволяющая оценить преимущества, получаемые при параллельном решении задачи на n процессорах, по сравнению с последовательным решением той же задачи на единственном процессоре.
n — количество процессоров, используемых для организации параллельных вычислений;
O(n) — объем вычислений, выраженный через количество операций, выполняемых n процессорами в ходе решения задачи;
T(n) — общее время вычислений (решения задачи) с использованием n процессоров.
По существу, можно выделить четыре группы метрик.
Первая группа характеризует скорость вычислений.( индексом параллелизма и ускорением.)
Вторую группу образуют метрики эффективность и утилизация
Третья группа метрик, — избыточность и сжатие
четвертую группу образует единственная метрика — качество
37) Законы Амдала и Густафсона.
Джин Амдал (Gene Amdahl) — один из разработчиков всемирно известной системы IBM 360.
Проблема рассматривалась Амдалом исходя из положения, что объем решаемой задачи с изменением числа процессоров, участвующих в ее решении, остается неизменным.
Такая постановка характерна для случаев, когда основным требованием является скорость вычислений, например, для задач, выполняемых в реальном времени
В случае, когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента
Не для всякой задачи имеет смысл наращивание числа процессоров в вычислительной системе.
Более того, если учесть время, необходимое для передачи данных между узлами вычислительной системы, то зависимость времени вычислений от числа узлов будет иметь максимум .
оказывается, что наращивание общего объема программы касается главным образом распараллеливаемой части программы
Некоторые нагрузки подобны газу: они расширяются для заполнения всей доступной вычислительной мощности.
Когда размер задачи увеличивается, параллельная часть расширяется быстрее последовательной.
38) Конвейеризация вычислений. Конвейер команд.
39) Типы конфликтов в конвейере команд.
Конфликтные ситуации в конвейере принято обозначать термином риск (hazard), а обусловлены они могут быть тремя причинами:
попыткой нескольких команд одновременно обратиться к одному и тому же ресурсу ВМ (структурный риск);
взаимосвязью команд по данным (риск по данным);
неоднозначностью при выборке следующей команды в случае команд, изменяющих последовательность вычислений (риск по управлению)
т.е. СУД (структурный, управлению, данным)
Структурный риск (конфликт по ресурсам) имеет место, когда несколько команд, находящихся на разных ступенях конвейера, пытаются одновременно использовать один и тот же ресурс, чаще всего — память
Риск по данным, в противоположность структурному риску — типичная и регулярно возникающая ситуация. («чтение после записи», «запись после чтения», «запись после записи»)
40)Методы решения проблемы условного перехода в конвейере команд.
Предсказание переходов на сегодняшний день рассматривается как один из наиболее эффективных способов борьбы с конфликтами по управлению.
Идея заключается в том, что еще до момента выполнения команды условного перехода или сразу же после ее поступления на конвейер делается предположение о наиболее вероятном исходе такой команды (переход произойдет или не произойдет). Последующие команды подаются на конвейер в соответствии с предсказанием
точность предсказания переходов должна быть выше 97,7%
При классификации схем предсказания переходов обычно выделяют два подхода: статический и динамический, в зависимости от того когда и на базе какой информации делается предсказание
Предсказание делается на этапе компиляции программы и в процессе вычислений уже не меняется.
В целом, динамические стратегии по сравнению со статическими обеспечивают более высокую точность предсказания
Учитывает (истории переходов)
41) Понятие суперконвейеризации.
Суперконвейеризация (термин впервые был применен в 1988 году) позволяет улучшить производительность процессора за счет повышения частоты, с которой команды подаются на конвейер и перемещаются по нему.
В обычном конвейере эта частота ограничена временем обработки в самой «медленной» ступени конвейера. В суперконвейере возможность увеличения частоты достигается путем выявления «медленных» ступеней и разбиения их на k меньших ступеней
К суперконвейерным относят процессоры, где таких ступеней больше шести.
П
ервым серийным суперконвейерным процессором считается MIPS R4000, конвейер команд 11 которого включает в себя восемь ступеней
42) Понятие суперскалярного процессора и его архитектура.
Суперскалярным (этот термин впервые был использован в 1987 году) называется центральный процессор (ЦП), который одновременно выполняет более чем одну скалярную команду.
Это достигается за счет включения в состав ЦП нескольких самостоятельных функциональных блоков, каждый из которых отвечает за свой класс операций и может присутствовать в процессоре в нескольких экземплярах
Суперскалярность предполагает параллельную работу нескольких функциональных блоков, что возможно лишь при одновременном выполнении нескольких скалярных команд. Последнее условие хорошо сочетается с конвейерной обработкой, при этом желательно, чтобы таких конвейеров было несколько, например два или три
В 
современных процессорах суперскалярность обычно совмещают с элементами суперконвейеризации. Одними из первых этот подход использовала фирма AMD в своих микропроцессорах Athlon и Duron, причем охватывал он не только конвейер команд, но и блок обработки чисел в форме с плавающей запятой
43) Переименование регистров в суперскалярных процессорах.
Когда команды выдаются и завершаются упорядоченно, каждый регистр в любой точке программы содержит именно то значение, которое диктуется программой. При неупорядоченной выдаче и завершении команд запись в регистры может происходить также неупорядоченно и отдельные команды, обратившись к какому-то регистру, вместо нужного получат «устаревшее» или «опережающее» значение.
Неупорядоченные выдачи/завершения могут привести к неверному результату.
Основная идея переименования регистров состоит в том, что каждый новый результат записывается в один из свободных в данный момент дополнительных регистров, при этом ссылки на заменяемый регистр во всех последующих командах соответственным образом корректируются.
44) Окно команд в суперскалярных процессора.
Окно команд обеспечивает отсрочку передачи команд на исполнение до момента готовности операндов, а также нужную очередность завершения команд и загрузки их результатов в физические регистры. Эта техника известна также под названием шелвинг (shelving).
Централизованное окно команд (scoreboard) представляет собой буферное запоминающее устройство, в котором хранится некоторое количество последних по времени извлеченных из памяти и декодированных команд, а также текущая информация о доступности ресурсов, привлекаемых для их исполнения
Распределенное окно команд. В варианте распределенного окна команд на входе каждого функционального блока размещается буфер декодированных команд, называемый накопителем команд или станцией резервирования
45) Организация памяти вычислительных систем.
В вычислительных системах, объединяющих множество параллельно работающих процессоров или машин, задача правильной организации памяти является одной из важнейших.
Различие между быстродействием процессора и памяти всегда было камнем преткновения в однопроцессорных ВМ.
Многопроцессорность ВС приводит еще к одной проблеме — проблеме одновременного доступа к памяти со стороны несколько процессоров.
В зависимости от того, каким образом организована память многопроцессорных систем, различают вычислительные системы с общей памятью и ВС с распределенной памятью .
В системах с общей памятью (ее часто называют также совместно используемой или разделяемой памятью) память ВС рассматривается как общий ресурс, и каждый из процессоров имеет полный доступ ко всему адресному пространству. имеет место как в классе SIMD, так и в классе MIMD
В варианте с распределенной памятью каждому из процессоров придается собственная память. Процессоры объединяются в сеть и могут при необходимости обмениваться данными, хранящимися в их памяти, передавая друг другу так называемые сообщения
Различие между общей и распределенной памятью — это разница в структуре виртуальной памяти, то есть в том, как память выглядит со стороны процессора
Различие между двумя системами памяти должно учитываться программистом, поскольку оно определяет способ взаимодействия частей распараллеленной программы.
46) Топология вычислительных систем.
Организация внутренних коммуникаций вычислительной системы называется топологией.
Топологию сети определяет множество узлов N, объединенных множеством каналов C. Связь между узлами обычно реализуется по двухточечной схеме
Коммуникационная система ВС представляет собой сеть, узлы которой связаны трактами передачи данных — каналами.
Понятие топологии широко используется при создании сетей. Одним из подходов к классификации топологий ЛВС является выделение двух основных классов топологий: широковещательные и последовательные.
В широковещательных топологиях ПК передает сигналы, которые могут быть восприняты остальными ПК. К таким топологиям относятся топологии: общая шина, дерево, звезда.
В последовательных топологиях информация передается только одному ПК. Примерами таких топологий являются: произвольная (произвольное соединение ПК), кольцо, цепочка.
Общая шина – это тип сетевой топологии, в которой рабочие станции расположены вдоль одного участка кабеля, называемого сегментом
Кольцо – это топология , в которой каждая станция соединена с двумя другими станциями, образуя кольцо
З
везда – это топология (рис. 3.4), в которой все рабочие станции присоединены к центральному узлу (например, к концентратору), который устанавливает, поддерживает и разрывает связи между рабочими станциями
47) Вычислительные системы класса SIMD: векторные ВС.
SIMD-системы были первыми вычислительными системами, состоящими из большого числа процессоров,
SIMD-системы во многом похожи на классические фон-неймановские ВМ: в них также имеется одно устройство управления, обеспечивающее последовательное выполнение команд программы. Различие касается стадии выполнения, когда общая команда транслируется множеству процессоров
Векторные вычислительные системы
При большой размерности массивов последовательная обработка элементов матриц занимает слишком много времени, что и приводит к неэффективности универсальных ВС для рассматриваемого класса задач. Для обработки массивов требуются вычислительные средства, позволяющие с помощью единой команды производить действие сразу над всеми элементами массивов — средства векторной обработки .
В средствах векторной обработки под вектором понимается одномерный массив однотипных данных
При размещении матрицы в памяти все ее элементы заносятся в ячейки с последовательными адресами, причем данные могут быть записаны строка за строкой или столбец за столбцом
Для повышения скорости обработки векторов все функциональные блоки векторных процессоров строятся по конвейерной схеме, причем так, чтобы каждая ступень любого из конвейеров справлялась со своей операцией за один такт
48) Вычислительные системы класса SIMD: матричные ВС.
Назначение матричных вычислительных систем во многом схоже с назначением векторных ВС — обработка больших массивов данных.
Матричный процессор интегрирует множество идентичных функциональных блоков (ФБ), логически объединенных в матрицу и работающих в SIMD-стиле.
Векторный процессор имеет встроенные команды для обработки векторов данных, что позволяет эффективно загрузить конвейер из функциональных блоков.
Не столь существенно, как конструктивно реализована матрица процессорных элементов — на едином кристалле или на нескольких.
49) Вычислительные системы класса SIMD: систолические ВС.
чтобы данные на своем пути от считывания из памяти до возвращения обратно ритмически проходили через как можно большее число процессорных элементов, подвергаясь максимально возможной обработке без занесения в память промежуточных результатов
Принцип систолических вычислений основан на циркуляции данных, как бы прокачиваемых процессорными элементами массива, подобно циркуляции крови в системе кровообращения под воздействием ритмических сокращений сердца
С каждым тактовым имульсом данные из памяти проталкиваются через массив ПЭ (Процессорный элемент)и с выхода этого массива вновь поступают в память.
Таким образом, систолическая структура — это однородная вычислительная среда из процессорных элементов, совмещающая в себе свойства конвейерной и матричной обработки
50)Вычислительные системы класса SIMD: ассоциативные ВС.
Однако, в отличие от матричных систем, обращение к данным производится не по адресам, где хранятся эти данные, а по отличительным признакам, содержащимся в самих данных
Ассоциативным процессором называют специализированный процессор, реализованный на базе ассоциативного запоминающего устройства (АЗУ), где, как известно, доступ к информации осуществляется не по адресу операнда, а по отличительным признакам, содержащимся в самом операнде.
Ассоциативная вычислительная система (АВС) представляет собой многопроцессорную ВС, объединяющую множество ассоциативных процессоров, процессор управления, процессор ввода/вывода и основную память
51) Вычислительные системы класса SIMD: ВС с архитектурой VLIW .
Архитектура с командными словами сверхбольшой длины или со сверхдлинными командами (VLIW, Very Long Instruction Word) известна с начала 80-х из ряда университетских проектов, но только сейчас, с развитием технологии производства микросхем, она нашла свое достойное воплощение
VLIW — это набор команд, организованных наподобие горизонтальной микрокоманды в микропрограммном устройстве управления.
Идея VLIW базируется на том, что задача эффективного планирования параллельного выполнения нескольких команд возлагается на «разумный» компилятор. Такой компилятор вначале исследует исходную программу с целью обнаружить все команды, которые могут быть выполнены одновременно
В процессе анализа компилятор может даже частично имитировать выполнение рассматриваемой программы
Длина сверхдлинной команды обычно составляет от 256 до 1024 бит.
VLIW-архитектуру можно рассматривать как статическую суперскалярную архитектуру. Имеется в виду, что распараллеливание кода производится на этапе компиляции, а не динамически во время исполнения.
То, что в выполняемой сверхдлинной команде исключена возможность конфликтов, позволяет предельно упростить аппаратуру VLIW-процессора, и, как следствие, добиться более высокого быстродействия.
52) Вычислительные системы класса MIMD: SMP -системы.
Технология SIMD исторически стала осваиваться раньше, чем MIMD, что и предопределило ее широкое распространение. В настоящее время наметился устойчивый интерес к MIMD-системам, которые обладают большей гибкостью, в частности могут работать и как высокопроизводительные однопользовательские системы, и как многопрограммные ВС, выполняющие множество задач параллельно. Кроме того, архитектура MIMD позволяет наиболее эффективно распорядиться всеми преимуществами современной микропроцессорной технологии и добиться наивысших показателей производительности.
В MIMD-системе каждый процессорный элемент (ПЭ) выполняет свою программу достаточно независимо от других ПЭ. В то же время ПЭ должны как-то взаимодействовать друг с другом. Различие в способе такого взаимодействия определяет условное деление MIMD-систем на ВС с разделяемой памятью и системы с распределенной памятью.
По мере возрастания требований к производительности и снижения стоимости микропроцессоров поставщики вычислительных средств как альтернативу однопроцессорным ВМ стали предлагать симметричные мультипроцессорные вычислительные системы, так называемые SMP-системы
SMP-система состоит из множества процессорных элементов, каждый из которых имеет равноправный доступ к логически единой памяти
Таким образом, в системе реализована концепция однородного доступа к памяти
Все процессорные элементы управляются единственным экземпляром операционной системы (ОС), загружаемой в совместно используемую память. ОС планирует распределение выполняемых заданий между процессорными элементами. Для этого ОС выделяет в процессах фрагменты (нити), и образует из этих фрагментов единую очередь. При освобождении какого-либо ПЭ (неважно, какого), ему сразу же передается очередной фрагмент из очереди
Все процессоры способны выполнять одинаковые функции;
53) Вычислительные системы класса MIMD: PVP -системы.
параллельные векторные системы PVP.
По своей сути — это SMP-системы, где роль процессорных элементов (ПЭ) исполняют векторно-конвейерные процессоры.
PVP-системы ориентированы на приложения из таких областей промышленности, как аэрокосмическая, автомобильная, электронная, химическая, энергетическая и т. П
Получаемый объектный код позволяет наилучшим образом использовать потенциал множества векторных процессорных элементов. Кроме того, нужно учитывать, что передача данных в векторном формате происходит на два порядка быстрее, чем в скалярном.
54) Вычислительные системы класса MIMD: NUMA -системы.
технология неоднородного доступа к памяти NUMA.
Технология NUMA считается одним из путей создания крупномасштабных вычислительных систем. В архитектуре NUMA память физически распределена, но логически общедоступна.
Это позволяет сохранить преимущества архитектуры с единым адресным пространством, а также ощутимо расширяет возможности масштабирования ВС.
Когда процессор инициирует доступ к памяти и нужная ячейка отсутствует в его локальной кэш-памяти, организуется операция выборки. Если нужная ячейка находится в локальной памяти, выборка производится с использованием локальной шины.
Узлы соединены посредством высокоскоростной сети, в роли которой чаще всего выступает коммутатор типа «кроссбар».
Вычислительная система управляется единой операционной системой
55) Вычислительные системы класса MIMD: MPP -системы.
Вычислительные системы с распределенной памятью, ( MPP ) в сущности, представляют собой совокупность взаимодействующих вычислительных машин, каждая со своей процессорной частью и основной памятью.
В отличие от ранее рассмотренных MIMD-систем, процессор узла имеет доступ только к своей локальной памяти и не имеет возможности напрямую обратиться к памяти другого узла.
каждый узел содержит сетевой адаптер, используемый для объединения узлов;
работа системы координируется главной ВМ (хост-компьютером), или одним из узлов, выполняющим роль главной ВМ
система хорошо масштабируется (до тысяч узлов);
вычисления представляют собой множество процессов, имеющих отдельные адресные пространства.
реализована модель распределенной памяти — доступ к памяти других узлов обеспечивается путем асинхронного обмена сообщениями;
56) Вычислительные системы класса MIMD: кластерные системы
но из самых современных направлений в области создания вычислительных систем — кластеризация.
Кластером называют группу взаимно соединенных вычислительных систем (узлов), работающих совместно и составляющих единый вычислительный ресурс, создавая иллюзию наличия единственной ВМ
Изначально перед кластерами ставились две задачи: достичь большой вычислительной мощности и обеспечить повышенную надежность ВС.
В первом приближении кластерную технологию можно рассматривать как развитие идей массовых параллельных вычислений. С другой стороны, многие черты кластерной архитектуры дают основание считать ее самостоятельным направлением в области MIMD-систем.
Узлы в кластерной системе объединены высокоскоростной сетью.
Неотъемлемая часть кластера — специализированное программное обеспечение (ПО), организующее бесперебойную работу при отказе одного или нескольких узлов. Такое ПО должно быть установлено на каждый узел кластера.
Если сигнал от некоторого узла не поступает, то узел считается вышедшим из строя; ему не дается возможность выполнять ввод/вывод,
Система “Чувак, ты там живой?”.
57) Вычислительные системы класса MIMD: ВС типа “ Constellation ”.
Constellation-система — это кластер, узлами которого служат SMP-системы.
В качестве отличительного признака выступает число процессорных элементов в узле. Изначально принималось, что система относится к Constellation-системам, если число узлов в кластере из SMP- систем меньше или равно количеству процессорных элементов в SMP-системе узла. больше (равно) 16.
Перспективность Constellation-систем обусловлена удачным сочетанием преимуществ распределенной памяти (возможности наращивания количества узлов) и разделяемой памяти (эффективного доступа множества ПЭ к памяти).
58) Вычислительные системы класса MIMD: ВС на базе транспьютеров.
Появление транспьютеров связано с идеей создания различных по производительности ВС (от небольших до мощных массивно-параллельных) посредством прямого соединения однотипных процессорных чипов. Сам термин объединяет два понятия — «транзистор» и «компьютер».
Транспьютер — это сверхбольшая интегральная микросхема, заключающая в себе центральный процессор, блок операций с плавающей запятой, статическое оперативное запоминающее устройство, интерфейс с внешней памятью и несколько каналов связи
Одна из важнейших отличительных черт транспьютера — каналы связи (линки), благодаря которым транспьютеры можно объединять, создавая вычислительные системы с различной вычислительной мощностью.
Одна из последовательных линий используется для пересылки данных, а вторая — подтверждений
Передача информации производится синхронно.
Особенности транспьютеров потребовали разработки для них специального языка программирования Occam
59) Вычислительные системы с нетрадиционной организацией вычислительного процесса: потоковые ВС.
В 
потоковой вычислительной модели для описания вычислений используется ориентированный граф, иногда называемый графом потоков данных (dataflow graph). Этот граф состоит из вершин (узлов), отображающих операции, и ребер или дуг, показывающих потоки данных между теми вершинами графа, которые они соединяют.
Операция в вершине выполняется лишь когда по дугам в нее поступила вся необходимая информация.
Таким образом, у каждой вершины может быть от одной до трех входящих дуг и одна или две выходящих. После активации вершины и выполнения операции результат передается по дуге к ожидающей вершине. Процесс повторяется, пока не будут активированы все вершины и получен окончательный результат. Одновременно могут быть активированы несколько вершин, при этом параллелизм в вычислительной модели выявляется автоматически.
В потоковых ВС программа вычислений определена потоковым графом, который хранится в памяти системы в виде таблицы. Каждая запись в таблице представляет одну вершину потокового графа
60) Вычислительные системы с нетрадиционной организацией вычислительного процесса: мультипотоковые ВС.
М
ультипотоковая модель совмещает локальность программы, характерную для фон- неймановской модели, с толерантностью к задержкам на переключение задач, характерным для потоковой архитектуры.
Мультипотоковая обработка сводится к потоковому выполнению нитей, в то время как внутри отдельной нити характер выполнения фон-неймановский.
Порядок обработки нитей меняется динамически в процессе вычислений, а последовательность команд в пределах нити определена при компиляции статически.
Существенное отличие мультипотоковой системы от обычной потоковой состоит в организации внутреннего управляющего конвейера, где последовательность выполнения команд задается счетчиком команд, как в фон-неймановских машинах. Иными словами, этот конвейер идентичен обычному конвейеру команд.
Существуют две формы мультипотоковой обработки: без блокирования и с блокированием
В модели без блокирования выполнение нити не может быть начато, пока не получены все необходимые данные. Будучи запущенной, нить выполняется до конца без приостановки
В варианте с блокированием запуск нити может быть произведен до получения всех операндов. Когда требуется отсутствующий операнд, нить приостанавливается (блокируется), а возобновление выполнения откладывается на некоторое время. Процессор запоминает всю необходимую информацию о состоянии и загружает на выполнение другую готовую нить. Модель с блокированием обеспечивает более мягкий подход к формированию нитей
61) Вычислительные системы с нетрадиционной организацией вычислительного процесса: ВС волнового фронта .
Волновые процессорные массивы сочетают систолическую конвейерную обработку данных с асинхронным характером потока данных
В качестве механизма координации межпроцессорного обмена в волновых системах принята асинхронная процедура связи с подтверждением (handshake)
Для проверки готовности соседа передающий процессор сначала направляет ему запрос, а данные посылает только после получения подтверждения о готовности их принять.
В систолических ВС фронты вычислений продвигаются по структуре синхронно, и представляют собой прямые линии. В волновых системах они могут быть изогнутыми кривыми, меняющими свою конфигурацию во времени в зависимости от задержек в отдельных ПЭ и моментов поступления данных на каждый ПЭ.
По сравнению с систолическими ВС массивы волнового фронта обладают лучшей масштабируемостью, проще в программировании и характеризуются более высокой отказоустойчивостью.
62) Вычислительные системы с нетрадиционной организацией вычислительного процесса: редукционные ВС.
В потоковой модели вершины вверху графа запускаются раньше, чем нижние. Это — нисходящая обработка.
Механизм управления по запросу состоит в обработке вершин потокового графа снизу вверх. (редукционные ВС)
Математическую основу редукционных ВС составляет лямбда-исчисление, а для написания программ под такие системы нужны так называемые функциональные языки программирования (FP, Haskell и др.)
В редукционной ВС вычисления производятся по запросу на результат операции.
Известны два типа моделей редукционных систем: строчная и графовая, отличающиеся тем, что именно передается в операцию (функцию) — скопированные значения данных или же только указатели мест хранения данных.
В строчной редукционной модели каждая запросившая вершина получает отдельную копию выражения для собственной оценки. Длинное строковое выражение рекурсивным образом сокращается (редуцируется) до единственного значения
В графовой редукционной модели выражение представлено как ориентированный граф. Граф сокращается по результатам оценки ветвей и подграфов. В зависимости от запросов возможно параллельное оценивание и редукция различных частей графа или подграфов
63) Оценка производительности ВС.
Выбор вычислительной системы (ВС) всегда начинается с выяснения того, насколько характеристики данной системы отвечают цели, для достижения которой система будет применяться.
Производительность ВС определяется через количество вычислительных услуг, обеспечиваемых системой в единицу времени.
Вопросы анализа и оценки производительности вычислительных систем относят к области теории вычислительных систем — разделу информатики, где с помощью математических методов исследуется поведение систем с целью прогнозирования их эффективности.
Целью анализа производительности является выяснение характера ее зависимости от особенностей аппаратной и программной составляющих вычислительной системы
Анализ обычно проводится на стадии проектирования или модернизации ВС, то есть, когда реальной системы либо еще нет, либо она существует в виде прототипа.
Анализ позволяет оценить производительность качественно, а оценка — количественно.
Источник
