Архитектура ЭВМ (стр. 3 из 6)

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. Факторы, снижающие производительность векторных ЭВМ. Возможность векторной обработки программ

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

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

Doi=1,n

A(i) = A(i) + s

EndDo

Пример невекторизуемого фрагмента (очередная итерация не может начаться, пока не закончится предыдущая):

Do i=1,n

A(i) = A(i-1)+s

End Do

Препятствия для векторизации

Препятствий для векторизации конкретного цикла может быть много, вот лишь некоторые из них:

Зависимость по данным (предыдущий фрагмент).

Отсутствие регулярно расположенных векторов:

Doi=1,n

ij = FUNC(i)

A(i) = A(i)+B(ij)

EndDo

Присутствие цикла, вложенного в данный - для реализации такого фрагмента нет соответствующих векторных команд.

Вызов неизвестных подпрограмм и функций:

Do i=1,n

CALL SUBR(A,B)

EndDo

29. Использование параллельных вычислительных систем. Закон Амдала

Предположим, что в вашей программе доля операций, которые нужно выполнять последовательно, равна f, где 0<=f<=1 (при этом доля понимается не по статическому числу строк кода, а по числу операций в процессе выполнения). Крайние случаи в значениях f соответствуют полностью параллельным (f=0) и полностью последовательным (f=1) программам. Так вот, для того, чтобы оценить, какое ускорение S может быть получено на компьютере из 'p' процессоров при данном значении f, можно воспользоваться законом Амдала: