3.2.2. Параллельные сумматоры.
Параллельные сумматоры получили свое название по названию параллельных кодов, которые они обрабатывают. Разряды сумматора соединены последовательно по цепи распространения переноса. Используются способы ускорения распространения переноса (сумматоры со сквозным, параллельным, групповым и условным переносом).
3.2.3. Матричные умножители
Матричный л-разрядный умножитель повторяет структуру матрицы конъюнкций произведения (МКП) и содержит матрицу из п2 конъюнкторов, вычисляющих конъюнкции разрядов множимого и множителя, и схему сложения конъюнкций на матрице из n2-2n полных двоичных сумматоров и n полусумматоров.
Для п=4 МКП V{18} =А {14}*В{14} и схема сложения матричного умножителя показаны на рис. 5. Конъюнкции МКП обозначены двухразрядным кодом, составленным из разрядов множимого и множителя. Сумматоры матрицы названы конъюнкциями, которые поступают на их первый вход (этот вход не показан). Другие конъюнкции выделены пунктиром. Для сумматоров показаны выходы суммы s и переноса р. Полные сумматоры выделены жирной рамкой.
3.2.4. Матричные делители.
Деление чисел в матричных ВУ выполняется по алгоритмам с восстановлением и без восстановления остатка.
Исходными данными в форматах с фиксированной точкой являются делимое А{12п} и делитель B(1n}. Результат операции — частное — вычисляется итеративно. На i-й итерации, i=1 n, используются два числа — удвоенный результат предыдущей итерации, дополненный на месте младшего разряда (n+i)-м разрядом числа (для первой итерации — часть А{1п} делимого) и делитель. Обработка n-разрядных чисел выполняется в дополнительном коде в (n+1)-разрядной сетке.
На итерации деления с восстановлением остатка вычисляется разность чисел. Перенос-заем из (п+1)-то разряда разности является разрядом частного. Результатом итерации является первое число или разность соответственно при нулевом или единичном значениях разряда частного. Результат последней итерации является остатком операции деления.
На итерации деления без восстановления остатка результатом является разность или сумма чисел соответственно при единичном или нулевом значениях разряда частного, вычисленного на предыдущей итерации (на первой итерации — инверсии кода знака частного). Перенос-заем из (п+1)-го разряда результата итерации является разрядом частного. Остатком операции деления является результат последней итерации, увеличенный в случае отрицательного значения на делитель.
Билет №110. Использование конвеерного параллелизма в архитектуре специализированных ЭВМ.
В основе векторной обработки данных лежит векторизация вычислений, в процессе которой меняется постановка вычислительной задачи преобразованием множества скалярных операций в векторную форму. Данные структурируются в массивы, над которыми выполняются векторные операции, предусматривающие обработку элементов по единым командам. Для выполнения векторных операций в состав ЭВМ включаются матричные или векторные процессоры.
Векторные процессоры используют конвейерный принцип организации вычислений. Конвейер представляет собой последовательно соединенные участки, состоящие из комбинационного преобразователя и регистра, запоминающего результат вычислений в конце такта. С каждым тактом информация переходит из предыдущих участков конвейера в следующие, претерпевая соответствующие преобразования.
Различают линейные конвейеры, соединяющие участки в единую цепочку вычислений, и нелинейные конвейеры, допускающие опережающие и обратные связи между участками. Конвейерные ВУ могут быть однофункциональными, а также многофункциональньми со статической (до вычислительного процесса) или динамической (в процессе вычислений) настройкой на различные задачи. Перенастройка конвейера может осуществляться изменением соединения участков или изменением операций, выполняемых отдельными участками.
Одной из проблем построения конвейера является согласование задержек комбинационных преобразователей различных участков для их работы по единой тактовой частоте. Для понижения частоты работы участка используется его параллельное дублирование. Для согласования задержек вычислений применяется буферизация, которая обеспечивает задержку данных на заданное количество тактов дополнительно введенными участками, состоящими только из регистров.
К
онвейер
характеризуется временем запуска, т.
е. количеством тактов вычисления первого
результата и пропускной способностью
— количеством результатов, вычисленных
за единицу времени.
Принцип возможного распарараллеливания может быть и таким: В целях достижения наивысшего быстродействия выполнение самих векторных операций конвейеризируется, причём может иметься несколько арифметических конвейеров (линий) а отдельные у-ва (позиции) конвейерной линии могут, в свою очередь, содержать конвейеры для выполнения возложенных на них подфункций. Пример с-мы с конвеерно-векторной организацией – процессоры Cray.
Билет №111. Заготовка результата в архитектуре специализированных ЭВМ.
Заготовка результатов является методом распараллеливания вычислений, который направлен на сокращение времени выполнения операции за счет заготовки множества возможных результатов при неполной информации об операндах этой операции. Недостающая информация является условием снятия неопределенности над множеством операндов или множеством заготовленных результатов.
Альтернативой методу заготовки результатов является последовательный метод — естественная последовательность выполнения операций, при которой вычисления осуществляются после получения всех операндов. В обоих методах можно выделить три составляющих действия: определение условия, выбор, выполняемый над множеством операндов или возможных результатов, и сама операция. В последовательном методе составляющие действия выполняются последовательно. При заготовке результатов операция выполняется многократно и одновременно с вычислением условия. Далее следует выбор результата. Совмещение процессов вычисления условия и заготовки результатов снижает время выполнения операции. Затраты оборудования, как правило, сохраняются в части определения условия и имеют тенденцию уменьшаться и расти в составляющих выбора и выполнения операции соответственно.
Заготовку результата можно разделиь на 3 этапа
Получение входных данных
Выполнение одновременного вычисления результатов для всех возможных вариантов
Выбор и выдача нужного результата
В однотактном сумматоре с фиксированной точкой операция сложения выполняется с последовательным вычислением переноса от младших разрядов к старшим. Для ускорения вычислений к сумматору возможно применить многоуровневую заготовку результатов.
Для этого сумматор разбивается на k секций по n/k разрядов. Каждая секция (кроме первой) дублируется для заготовки двух результатов для случаев нулевоги и единичного значений переноса из предыдущей секции. Секции объединяются в пары. Переносы на выходах младших (продублированных) секций пары служат для выбора переносов в старших секциях пары. Действия по определению условий и вычислению возможных результатов предыдущих уровней заготовки совмещаются с действиями-, по вычислению возможных результатов и выбору следующих уровней. Укрупнение секций объединением в пары продолжается на каждом уровне заготовки результатов вплоть до получения единой секции, на выходах которой выбраны переносы для каждой исходной секции сумматора. Эти переносы используются для выбора результатов суммы с выходов исходных продублированных секций.
Пример
Задано построить n-разрядный однотактный сумматор с многоуровневой заготовкой результатов при разбиений устройства на k секциий для n = 8, k=4. Описать принадлежность элементов схемы различным составляющим всех уровней заготовки результатов.
Схема однотактного сумматора показана на рис. 3. Она содержит двухразрядные сумматоры 1-7, одноразрядные 8-12 и двухразрядные 13-15 коммутаторы.
Сумматор 1 принадлежит первой секции. Он вычисляет двухразрядный код суммы, поступающий на выход устройства и разряд переноса. Остальные сумматоры объединены в пары 2 и 3, 4 и 5, б и 7, составляющие вторую, третью и четвертую секции. Первый и второй сумматоры пары заготавливают двухразрядные коды суммы и разряды переносов для случаев нулевого и единичного значений входного переноса. На коммутаторе 8 под управлением переноса с выхода первой секции выбирается один из двух переносов, полученных на выходах второй секции.
На коммутаторах 9 и 10 под управлением двух заготовленных переносов с выходов третьей секции выбирается пара переносов из двух переносов с выходив четвертой секции.
На коммутаторах 11 и 12 под управлением переноса с выхода второй секции выбираются переносы с выходов третьей и четвертой секций. На двухразрядных коммутаторах 13-15 под управлением вычисленных переносов выбираются заготовленные разряды суммы.
Опишем принадлежность элементов схемы различным составляющим уровней заготовки результатов.
На элементах 1-10 выполняется первый уровень заготовки результатов: на сумматорах 1-5 вычисляются разряды переносов, которые являются условиями выбора, на сумматорах 2, 3 и 6, 7 заготавливаются возможные варианты разрядов переносов и на одноразрядных коммутаторах 8-10 выполняется выбор разрядов переносов,
На элементах 4, 5 и 8-12 выполняется второй уровень заготовки результатов: на одноразрядном коммутаторе 8 вычисляется разряд переноса, что относится к определению условия выбора, на сумматорах 4, 5 и одноразрядных коммутаторах 9, 10 осуществляется заготовка результатов — определяются возможные варианты разрядов переносов — и на одноразрядных коммутаторах 11, 12 осуществляется выбор разрядов переноса.
На элементах 1-8 и 11-15 выполняется третий уровень заготовки результатов: на сумматоре 1 и одноразрядных коммутаторах 8, 11, 12 вычисляются разряды переносов, являющиеся условиями выбора, на сумматорах 2-7 заготавливаются возможные варианты двухразрядных кодов сумм, а на двухразрядных коммутаторах 13-15 выполняется выбор кодов сумм.
Для построенного однотактного сумматора метод заготовки результатов уменьшает время вычислений в 1.5 раза при удвоении затрат оборудования.
Билет №112. Машины потоков данных.
Машины потоков данных. Тема контрольной работы: Программирование на языке Денниса.
Машины потоков данных организуют естественный процесс распараллеливания вычислений. Основными элементами машины являются память для хранения команд, множество процессоров и сети для пересылки команд в процессоры и результатов вычислений в команды. Программа в потоковой машине представляется множеством команд, содержащих код операции, сигнальные биты, а также поля для записи операндов а адрес, по которому результат операции пересылается в следующую команду. Команда помечается готовой к исполнению, если заполнены поля операндов и свободно место для пересылки результата. Готовые команды посылаются на выполнение в свободные процессоры.
Программа для потоковых машин составляется на языке Денниса и имеет вид графического изображения структуры вычислительного процесса с использованием специальных символов — блоков и соединяющих их линий со стрелками для указания направлений передачи данных. Различают два типа блоков: тип "link", служащий для размножения данных, и тип "actor", используемый для выполнения операций. Блок "link" имеет один вход и множество выходов, а блок "actor"— множество входов и один выход. Кроме того обозначаются точки ввода исходных данных — переменных, констант и управляющих бит. Передача числовой и управляющей информации показывается по-разному: сплошными и пунктирными линиями соответственно.
Ниже приводится изображение точек ввода исходных данных (рис. 7), блока типа "link" (рис. 8) и различных блоков типа "actor": символа выполнения операции "сложение" (рис. 9), символа сравнения "меньше либо равно" (рис. 10), символов вентилей "Т" и "F", (рис. 11), а также символа смесителя (рис. 12).
Символы для описания точек ввода исходных данных
Символ выполнения операции имеет один или два входа операнда (соответственно для унарной и бинарной операции), возможно управляющий вход и выход результата.
Символ сравнения имеет два входа для сравниваемых операндов и выход результата сравнения, который является битом управления.
Вентили "Т" и "F" пропускают операнд со входа на выход соответственно при истинном и ложном значении на управляющем входе.
Смеситель имеет два входа операнда, обозначенные символами "Т" (истинно) и "F" (ложно), а также управляющий вход и выход результата. При истинном значении управляющего входа на выход пропускается операнд со входа "Т", а в противном случае — со входа "F". Команда, реализующая данный блок, готова к исполнению при наличии управляющего бита и операнда, соответствующего значению этого бита.
Операндами могут быть как числовые данные, так и управляющие биты. Передача в качестве операндов управляющих бит показывается пунктирными линиями.
Пример выполнения задания
Задано: составить на языке Денниса программу вычисления суммы отрицательных чисел потока данных А.
Программа показана на рис. 13. Она содержит точку ввода переменной А, две точки ввода управляющих битов Начало и Конец, две точки ввода константы "0", два блока "link", а также блоки "actor" сравнения, выполнения операции сложения, два вентиля "Т" и смеситель.
Программа работает следующим образом.
В точку ввода переменной поступает поток данных А. Каждое данное А размножается на первом блоке "link" для выдачи в два направления: на вход операнда блока сравнения и вход операнда первого вентиля "Т".
Блок сравнения принимает в качестве второго операнда константу "О", проверяет условие 0 > А и формирует на выходе бит управления, принимающий единичное значение при выполнении условия и нулевое значение — в противном случае.
Первый вентиль "Т" под управлением вычисленного бита управления пропускает на выход отрицательные переменные А.
Блок выполнения операции и смеситель образуют накапливающий сумматор. Управляющий вход смесителя подключен к точке ввода управляющего бита Начало, который принимает истинное значение перед поступлением потока данных А и ложное значение в процессе вычислений. Под управлением истинного значения смеситель пропускает на выход начальное нулевое значение накапливаемой суммы . Выход блока сложения размножается на втором блоке "link" для выдачи суммы в обратную связь накапливающего сумматора и на вход операнда второго вентиля "Т". Управляющий вход этого вентиля подключен к точке ввода управляющего бита Конец, который принимает ложное значение в процессе обработки потока данных А и истинное значение по его окончанию. Под управлением бита Конец второй вентиль выдает накопленную сумму S на выход программы.
Билет №113. Машины потоков данных.
Машины потоков данных. Тема контрольной работы: Программирование на языке Денниса.
Машины потоков данных организуют естественный процесс распараллеливания вычислений. Основными элементами машины являются память для хранения команд, множество процессоров и сети для пересылки команд в процессоры и результатов вычислений в команды. Программа в потоковой машине представляется множеством команд, содержащих код операции, сигнальные биты, а также поля для записи операндов а адрес, по которому результат операции пересылается в следующую команду. Команда помечается готовой к исполнению, если заполнены поля операндов и свободно место для пересылки результата. Готовые команды посылаются на выполнение в свободные процессоры.
Программа для потоковых машин составляется на языке Денниса и имеет вид графического изображения структуры вычислительного процесса с использованием специальных символов — блоков и соединяющих их линий со стрелками для указания направлений передачи данных. Различают два типа блоков: тип "link", служащий для размножения данных, и тип "actor", используемый для выполнения операций. Блок "link" имеет один вход и множество выходов, а блок "actor"— множество входов и один выход. Кроме того обозначаются точки ввода исходных данных — переменных, констант и управляющих бит. Передача числовой и управляющей информации показывается по-разному: сплошными и пунктирными линиями соответственно.
Ниже приводится изображение точек ввода исходных данных (рис. 7), блока типа "link" (рис. 8) и различных блоков типа "actor": символа выполнения операции "сложение" (рис. 9), символа сравнения "меньше либо равно" (рис. 10), символов вентилей "Т" и "F", (рис. 11), а также символа смесителя (рис. 12).
Символы для описания точек ввода исходных данных
Символ выполнения операции имеет один или два входа операнда (соответственно для унарной и бинарной операции), возможно управляющий вход и выход результата.
Символ сравнения имеет два входа для сравниваемых операндов и выход результата сравнения, который является битом управления.
Вентили "Т" и "F" пропускают операнд со входа на выход соответственно при истинном и ложном значении на управляющем входе.
Смеситель имеет два входа операнда, обозначенные символами "Т" (истинно) и "F" (ложно), а также управляющий вход и выход результата. При истинном значении управляющего входа на выход пропускается операнд со входа "Т", а в противном случае — со входа "F". Команда, реализующая данный блок, готова к исполнению при наличии управляющего бита и операнда, соответствующего значению этого бита.
Операндами могут быть как числовые данные, так и управляющие биты. Передача в качестве операндов управляющих бит показывается пунктирными линиями.
Пример выполнения задания
Задано: составить на языке Денниса программу вычисления суммы отрицательных чисел потока данных А.
Программа показана на рис. 13. Она содержит точку ввода переменной А, две точки ввода управляющих битов Начало и Конец, две точки ввода константы "0", два блока "link", а также блоки "actor" сравнения, выполнения операции сложения, два вентиля "Т" и смеситель.
Программа работает следующим образом.
В точку ввода переменной поступает поток данных А. Каждое данное А размножается на первом блоке "link" для выдачи в два направления: на вход операнда блока сравнения и вход операнда первого вентиля "Т".
Блок сравнения принимает в качестве второго операнда константу "О", проверяет условие 0 > А и формирует на выходе бит управления, принимающий единичное значение при выполнении условия и нулевое значение — в противном случае.
Первый вентиль "Т" под управлением вычисленного бита управления пропускает на выход отрицательные переменные А.
Блок выполнения операции и смеситель образуют накапливающий сумматор. Управляющий вход смесителя подключен к точке ввода управляющего бита Начало, который принимает истинное значение перед поступлением потока данных А и ложное значение в процессе вычислений. Под управлением истинного значения смеситель пропускает на выход начальное нулевое значение накапливаемой суммы . Выход блока сложения размножается на втором блоке "link" для выдачи суммы в обратную связь накапливающего сумматора и на вход операнда второго вентиля "Т". Управляющий вход этого вентиля подключен к точке ввода управляющего бита Конец, который принимает ложное значение в процессе обработки потока данных А и истинное значение по его окончанию. Под управлением бита Конец второй вентиль выдает накопленную сумму S на выход программы.
№113. Ассоциативные системы
АС относятся к ОКМД. Они имеют большое число операционных устройств способных одновременно по командам одного управляющего устройства вести обработку нескольких потоков данных. АС можно представить как систему обладающую следующими свойствами:
данные находящиеся в памяти выбираются на основании их содержимого
операции преобразования данных могут осуществляться над несколькими множествами операндов при помощи одной команды
Т
ИВВ АЗУ АЛУ
Т
ак
как ассоциативная память (АС) является
основой в
АС, то структура АС м.б. классифицирована на основе АП
Рассмотрим работу АП
УУ
Рг АП
Рг АП СС Рг ИА
Рг АП – регистр ассоциативных признаков
Рг М – р-р маски; Рг ИА – р-р индикаторов памяти
СС – схема сравнения
|
Я 0 |
|
…….. |
|
Я n |
Выборка информации из АП: в РгАП из УУ подаётся код признака искомой информации в некотором источнике. Код может иметь несколько разрядов. Если код используется полностью, то он без изменений подаётся на СС, если есть ненужные разряды, то они маскируются в РгМ. (Перед началом работы все биты РгИА=1) После этого производится опрос первого разряда всех ячеек и содержимое сравнивается с первым разрядом РгАП. Если содержимое первого разряда какой-то ячейки не совпадает с содержимым РгАП, то соответствующий этой ячейке разряд в РгИА сбрасывается в 0. Если совпадает там остаётся 1. Затем операция повторяется со следующими разрядами, пока не пройдут все разряды РгАП. Т.о. после окончания опроса в РгИА в состоянии 1 останутся те разряды, которые соответствуют ячейкам содержащим информацию совпадающую с информацией записанной в РгАП. Время поиска в АЗУ зависит только от числа разрядов признаков и от скорости опроса разрядов, но не зависит от числа ячеек. Запись информации в АП происходит без указания номера ячейки, поэтому один из разрядов любой ячейки обычно используется для индикации её занятости. В этом случае при записи в АЗУ новой информации в РгАП записывается 0 и в первую незанятую ячейку пишем информацию. АЗУ позволяет быстро и просто сформировать несколько потоков идентичной информации.
С точки зрения структуры АС входят в класс ОКМД и в свою очередь могут быть разбиты на 4 категории в соответствии с организацией, процессом сравнения в АП:
Полностью параллельная – логика сравнения может быть предусмотрена в каждом ячейке-разряде каждого слова(высокая скорость, но громоздкая аппаратура) или же каждой группе ячеек, которые представляют код символа при фиксированном числе разрядов в коде.
Поразрядно последовательная – операции выполняются каждый момент времени только над одним разрядным срезом всех слов. Они также называются пословно – параллельные.
Пословно последовательная – представляет собой аппаратную реализацию простого программного цикла для поиска. Уменьшается время декодирования команды, так как требуется только одна команда для выполнения команды поиска. НИЗКАЯ СКОРОСТЬ.
Блочно – ориентированная АС компромисс между 2 и 3. Система RAPID:
УУ, диск с головкой на тракт и память с логикой сравнения символа. Обмен между диском и памятью осуществляется строками, состоящими из кодов символов.