Виды аппаратных методов ускорения умножения: 1) Ускорение выполнения операций + и >> (за счет элементной базы и технологии) 2) Введение дополнительных цепей сдвига, которые за один такт могут производить сдвиг информации в регистрах сразу на несколько разрядов. 3) Совмещенные по времени операции + и >>. Классификация логических методов ускорения умножения. В основе логических методов УУ лежит целенаправленный анализ цифр множителя. Этот анализ позволяет исключить из процесса умножения ряд микроопераций сложения и сдвига. Анализу подвергается или 1 разряд или 2-3-4. 1) Метод, позволяющий уменьшить количество сложений 2) количество сдвигов. Если при выполнении умножения в множителе встречается группа 1, то вместо сложений, число которых равно количеству единиц в группе можно выполнить одно сложение и одно вычитание. Выполнить следующее: 1) множитель сдвигается до появления первой единицы. 2) производится вычитание множимого и сдвиг множителя до появления первого нуля. 3) производится прибавление множимого и вновь сдвигается множитель до появления первой единицы.
1. Модифицированный метод. а) 0001000 Если две группы нулей разделены единицей, в К-той позиции, то вместо выполнения в К n сложений в K+1 позиции достаточно выполнить толко сложение в К-ой позиции. б) 1110111 - достаточно только вычитание в К-ой позиции.
2. Анализ двух разрядов множителя. Если пара 00, то производится простой сдвиг на два разряда вправо суммы частичных произведений. Если 01, то к сумме частичных произведений прибавляется одинарное множимое и сумма частичных произведений сдвигается на два разряда вправо. При 10 прибавляетя удвоенное множимое и сумма частичных произведений сдвигается на два разряда вправо. При 11 из суммы частичных произведений вычитается одинарное множимое и сумма частичных произведений сдвигается на два разряда вправо. При обработке следующей пары следует учесть, что при 11 на следующем шаге надо прибавить к сумме одинарное множимое.
13. Деление дробных чисел
Сводится к многократному вычитанию сначала из делимого, а потом из остатков (эти остатки умножаются на основание системы счисления - 10).
Сравнение величины модуля делимого и делителя, а впоследствии и остатков в ЭВМ производится с помощью операции вычитания (с помощью знака разности). Умножение делимого, а впоследствии остатков от деления на основание системы счисления осуществляется сдвигом исходного числа влево на 1 разряд. Z = X / Y. X - делимое, Y -делитель.
14. Деление целых положительных чисел
Делимое всегда берется двойным словом - 2n. Делитель - n. Модули операндов формируют n-1 разрядную сумму, часть частного и n-разрядный остаток со своим знаком. Знак остатка должен совпадать со знаком делимого. При большей величине модуля делимого и малой делителя - случай некорректного деления => перед началом необходимо провести проверку на корректность деления. Z=|X|/|Y| < 2^(n-1). Проверку можно совместить с первым шагом деления. |X|-2^(n-1)|Y|<0. Если результат пробного вычитания >0, то |Z|>=2^(n-1), и деление невозможно. Если <0, то можно выполнить деление.
Алгоритм деления с неподвижным делителем с восстановлением остатка:
1. Берутся модули от делимого и делителя.
2. Исходное значение частичного остатка полагается равным старшим разрядам делимого
3. Частичный остаток удваивается путем сдвига на один разряд влево, при этом в освобождающийся при сдвиге младший разряд частичного остатка заносится очередная цифра делимого.
4. Из сдвинутого частичного остатка вычитается делитель и анализируется знак результата вычитания.
5. Очередная цифра модуля частного равна 1, если результат вычитания положителен, и 0, если отрицателен. В последнем случае значение остатка восстанавливается до того, которое было до вычитания
6. Пункты 3-5 последовательно выполняются для получения всех цифр модуля частного.
7. Знак частного плюс, если знаки делимого и делителя одинаковы, и минус в противном случае.
Алгоритм без восстановления остатка:
4. Из сдвинутого частичного остатка вычитается делитель, если остаток положителен, и к сдвинутому частичному остатку прибавляется делитель, если остаток отрицателен.
5. Очередная цифра модуля частного равна 1, если результат вычитания положителен и 0 если отрицателен.
18. Классификация аппаратных средств многопроцессорных вычислительных комлпексов (МПВК) по Ф.Г. Энслоу
Общая шина
Перекрестная коммутация
Многовходовые ОЗУ
Ассоциативные
Матричные, векторные
С конвейерной обработкой.
19. МПВК с общей шиной
Физическая или логическая (опр. методы передачи инфы по проводам). Все устр-ва в ней. Связь только между двумя устройствами. Малонадежны, делают дополнительную шину, кот-ую можно использовать для ускорения работы. Дост. - простота выполнения, доступ всех модулей к ОЗУ. Низкое быстродействие и надежность.
20. МПВК с перекрестной коммутацией
Три вида: 1) сетка - к ней все подключено 2) к каждому процессору добавляется своя память
3) отделяются процессоры ввода-вывода, в дополнительную матрицу. Они соединяется через процессор ввода-вывода.
Достоинства: обмен инфой по нескольким путям, эфф. Скорость передачи выше чем в первом случае, отсутствие проблем при || работе процссорв, упрощ. интерфейсы, отст. Конфликтов., возможность установления связи на любое длит. время, нарушение к-л не влечет выход всей системы.
Недостатки - сложность наращивание, дороговизна комм. матрицы.
21. МПВК с многовходовыми ОЗУ
1) Коммутация устройств осуществляется в памяти
2) Модули памяти ОЗУ имеют число входов равное числу устройств, которое к нему подключается
3) Средства коммуникации распределены между несколькими устройствами
4) Для наращивания системы предусматривается дополнительные входы в память
Особенности:
1) Используется несколько путей передачи информации
2) Блоки ОЗУ должны быть снабжены логическими схемами для разрешения конфликтов - когда несколько внешних устройств требуют доступа к одному и тому же элементу.
3) Каждый модуль памяти должен идентифицировать и обрабатывать запросы на доступ к определенным ячейкам памяти. Максимально возможная конфигурация системы данного типа ограничена числом входов модулей памяти.
22. Ассоциативные вычислительные системы
Предпосылки их появления - обработка информации, поступающей от многих датчиков, или систем слежения за многими объектами. Ассоциация - обработка данных может производиться не только обычными средствами, но и путем идентификации и выбора данных по их содержанию.
1) при приеме и размещении в памяти входного потока данных
2) реализация функций, связанных с перестроением данных.
Достижение наивысшей степени параллелизма обработки возможно когда число обрабатываемых элементов равно числу слов.
23. Матричные вычислительные системы
Выполняют последовательно поразрядные арифметические и логические операции. Каждый элемент соединяется с 4-мя другими. ПЭ - Процессор и ОЗУ. Разрядность слов устанавливается программно. От УУ - команды управления и различные константы.
Многомодальная логика - каждый ПЭ м.б. активным или пассивным.
25. Принципы векторной обработки
Векторная обработка увеличивает скорость и эффективность обработки за счет того, что обработка целого набора (вектора) данных выполняется одной командой. Скорость выполнения операций в векторном режиме приблизительно в 10 раз выше скорости скалярной обработки. Для фрагмента типа
Do i = 1, n
A(i) = B(i)+C(i)
End Do
в скалярном режиме потребуется сгенерировать целую последовательность команд: прочитать элемент B(I), прочитать элемент C(I), выполнить сложение, записать результат в A(I), увеличить параметр цикла, проверить условие цикла. В векторном режиме этот фрагмент преобразуется в: загрузить порцию массива B, загрузить порцию массива C (эти две операции будут выполняться со сдвигом в один такт, т.е. практически одновременно), векторное сложение, запись порции массива в память, если размер массивов больше длины векторных регистров, то повторить эту последовательность некоторое число раз.
Перед тем, как векторная операция начнет выдавать результаты, проходит некоторое время (startup), связанное с заполнением конвейера и подкачкой аргументов. Чем больше длина векторов, тем менее заметным оказывается влияние данного начального промежутка времени на все время выполнения программы.
Векторные операции, использующие различные ФУ и регистры, могут выполняться параллельно.
26. Факторы, снижающие производительность векторных ЭВМ. Возможность векторной обработки программ
Некоторый фрагмент программы может быть обработан в векторном режиме, если для его выполнения могут быть использованы векторные команды (соответственно полная или частичная векторизация). Поиск таких фрагментов в программе и их замена на векторные команды называется векторизацией программы. Для векторизации необходимы вектора-аргументы + независимые операции над ними. Кандидаты для векторизации - это самые внутренние циклы программы.
Пример. Нужно выполнить независимую обработку всех элементов поддиагональной части массива; в этом случае можем векторизовать по строкам, можем по столбцам, но не можем обработать все данные сразу в векторном режиме из-за нерегулярности расположения элементов поддиагональной части массива в памяти. Пример векторизуемого фрагмента, для которого выполнены все указанные условия:
Do i=1,n
A(i) = A(i) + s
EndDo
Пример невекторизуемого фрагмента (очередная итерация не может начаться, пока не закончится предыдущая):
Страницы: 1, 2, 3, 4, 5
