Деление целых положительных чисел

 

Делимое всегда берется двойным словом – 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 если отрицателен.

Классификация аппаратных средств многопроцессорных вычислительных комлпексов (МПВК) по Ф.Г. Энслоу

 

Общая шина

Перекрестная коммутация

Многовходовые ОЗУ

Ассоциативные

Матричные, векторные

С конвейерной обработкой.

МПВК с общей шиной

 

Физическая или логическая (опр. методы передачи инфы по проводам). Все устр-ва в ней. Связь только между двумя устройствами. Малонадежны, делают дополнительную шину, кот-ую можно использовать для ускорения работы. Дост. – простота выполнения, доступ всех модулей к ОЗУ. Низкое быстродействие и надежность.

 

МПВК с перекрестной коммутацией

 

Три вида: 1) сетка – к ней все подключено 2) к каждому процессору добавляется своя память

3) отделяются процессоры ввода-вывода, в дополнительную матрицу. Они соединяется через процессор ввода-вывода.

Достоинства: обмен инфой по нескольким путям, эфф. Скорость передачи выше чем в первом случае, отсутствие проблем при || работе процссорв, упрощ. интерфейсы, отст. Конфликтов., возможность установления связи на любое длит. время, нарушение к-л не влечет выход всей системы.

Недостатки – сложность наращивание, дороговизна комм. матрицы.

МПВК с многовходовыми ОЗУ

 

1) Коммутация устройств осуществляется в памяти

2) Модули памяти ОЗУ имеют число входов равное числу устройств, которое к нему подключается

3) Средства коммуникации распределены между несколькими устройствами

4) Для наращивания системы предусматривается дополнительные входы в память

Особенности:

1) Используется несколько путей передачи информации

2) Блоки ОЗУ должны быть снабжены логическими схемами для разрешения конфликтов – когда несколько внешних устройств требуют доступа к одному и тому же элементу.

3) Каждый модуль памяти должен идентифицировать и обрабатывать запросы на доступ к определенным ячейкам памяти. Максимально возможная конфигурация системы данного типа ограничена числом входов модулей памяти.