Духнич Е.И., Андреев А.Е. Организация вычислительных машин и систем

Подождите немного. Документ загружается.

времени и др.). При этом в данный момент времени ЦП или ОУ занято вы-

полнением какой-то одной задачи.

- ОКМД - Одиночный поток команд / Множество потоков данных

( SIMD - Single Instruction / Multiple Data ). Такая архитектура характерна для

векторных и матричных ВС, выполняющих специальные векторные и мат-

ричные операции как паралельные операции для разных потоков данных.

Под потоками данных подразумеваются последовательности элементов век-

торов (для векторных ВС) или строки матриц (для матричных ВС). В послед-

ние годы SIMD-расширения реализованы в системах команд процессоров об-

щего назначения (MMX, SSE, SSE2, SSE3 – Intel, 3DNow! – AMD и др.)

- МКОД - Множество потоков команд / Одиночный поток данных

( MISD - Multiple Instruction / Single Data ). Данная архитектура соответствует

ВС конвейерного типа, в которых один поток данных проходит разные ступе-

ни обработки в разных процессорных элементах (ПЭ).

Архитектуры типа ОКМД и МКМД используются при построении вы-

сокопроизводительных систем разного уровня, начиная от простых конвейер-

ных ВС до супер-ЭВМ с векторными и параллельными процессорами.

- МКМД - Множество потоков команд / Множество потоков данных

( MIMD - Multiple Instruction / Multiple Data ). Такая архитектура характерна

для ВС сверхвысокой производительности, в которых множество ПЭ, выпол-

няющих каждый свою вычислительную подзадачу (процесс), обмениваются

потоками команд и данных в разных направлениях (кластеры, системы с

массовым параллелизмом и др.)

Помимо четырех выделенных групп, иногда выделяют дополнитель-

ные, находящиеся на границе между перечисленными, например, MSIMD

или MMISD – соответственно Multi-SIMD, или Multi-MISD – системы с

несколькими параллельно работающими SIMD или MISD - блоками.

2. По управляющему потоку

- управляемые потоком команд (IF- instruction flow) ;

- управляемые потоком данных (DF- dataflow) .

Системы с управлением потоком данных иногда называют просто пото-

ковыми архитектурами

3. По использованию памяти :

- с общей памятью («разделяемая память» - shared memory);

- с локальной памятью для каждого процессора.

Общая разделяемая разными процессорами память может быть физи-

чески распределена по вычислительной системе. Для общей памяти, доступ

к которой осуществляется разными процессорами в системе за одинаковое

время, существует термин UMA – Unified Memory Access (память с одина-

ковым временем доступа). В случае, когда время доступа к разным адресам

общей памяти для разных процессоров неодинаково (обычно это характерно

для физически распределенной общей памяти), используют термин Non-

UMA (память с различным временем доступа) .

4. По способу обмена между процессорами:

- через общую разделяемую память (мультипроцессоры);

- через передачу сообщений по каналам ввода-вывода (мульти-

компьютеры или кластеры);

- кластеры мультипроцессоров.

5. По используемому типу параллелизма :

- естественный или векторный параллелизм (используется в вектор-

ных и матричных вычислительных системах);

- параллелизм независимых ветвей («крупнозернистый» или «Coarse

Grain») – используется в симметричных многопроцессорных систе-

мах Symmetric MultiProcessor (SMP), а также в системах MIMD;

- «мелкозернистый» («Fine Grain») параллелизм – используется в си-

стемах типа MIMD, в системах с массовым параллелизмом и др.;

- параллелизм смежных операций (Instruction Level Parallelism – ILP)

- используется в ЭВМ с длинным командным словом – VLIW и др.

6. По системе коммутации :

- полносвязанные МПВС (каждый процессор связан с каждым);

- с выделенным коммутатором ;

- с общей шиной ;

- линейный или матричный массивы (связаны друг с другом соседние

процессоры) ;

- гиперкубы (связаны соседние ПЭ, но массивы многомерные);

- параллельные машины с изменяемой конфигурацией связей;

- с программируемыми коммутаторами .

7. По сложности системы коммутации (по кол-ву уровней иерархии) :

- с коммутирующей цепью (сетью) - один уровень коммутации ;

- с кластерной коммутацией (когда группы вычислительных

устройств объединены с помощью одной системы коммутации, а

внутри каждой группы используется другая).

8. По организации доступа к общим ресурсам:

- симметричные многопроцессорные системы (все процессоры име-

ют одинаковый доступ к общим ресурсам);

- асимметричные (master-slave) многопроцессорные системы с разны-

ми возможностями доступа для разных процессоров.

Приложение 1 Базовые комбинационные и последовательностные схемы

Комбинационная схемы – это цифровые схемы с логическими (цифровыми) входа-

ми и выходами, которые реализует некоторые функции алгебры логики (функциональные

преобразователи). В таких схемах выходной сигнал в данный момент времени однозначно

определяется значениями входных сигналов в данный момент времени (без учета реаль-

ных задержек распространения сигналов по схеме).

К базовым схемотехническим узлам относят и базовые устройства памяти, т.н. по-

следовательностные схемы или автоматы. В них выходные сигналы в данный момент вре-

мени определяются не только значениями входных сигналов в данный дискретный момент

времени (в данном такте), но и значениями на входах в предыдущие моменты времени (в

предыдущие такты). То есть, данные схемы обладают памятью и могут находиться в

разных внутренних состояниях. Количество внутренних состояний определяет емкость па-

мяти схемы. Так, например, базовый элемент памяти – триггер - имеет два состояния, что

соответствует 1 биту информации.

Рассмотрим типовые комбинационные схемы и схемы памяти.

1) Базовые Логические Элементы (вентили)

X Y

НЕ

(NOT)

(AND)

ИЛИ

(OR)

И-НЕ

ИЛИ-

НЕ

(NOR)

Искл.

ИЛИ

(XOR)

Равенство

(NXOR)

X X*Y XvY XY XvY

X ⊕ Y

X=Y/(X+Y)

0 0 1 0 0 1 1 0 1

0 1 1 0 1 1 0 1 0

1 0 0 0 1 1 0 1 0

1 1 0 1 1 0 0 0 1

II) Сумматоры

1) Одноразрядный полусумматор (HS/HA) 2) Одноразрядный полный сумматор

HA – Half Adder FА – Full Adder

3) Параллельный сумматор Пример: Параллельный сумматор с

последовательным переносом.

X HA S

Y SM C

XYCS

0000

0101

1001

1110

X FA S

Z SM C

XYZCS

00000

00101

01001

01110

10001

10110

11010

11111

X SM S

Z C

X SM

Y S

Z C

X SM

Y S

Z C

m21

III) Дешифраторы и шифраторы (DC и CD)

n x 2

(2 x 4; 3 x 8 …)

Дешифратор – выполняет преобразование двоичного кода в позиционный

Шифратор – сворачивает позиционный код в двоичный.

Если на вход шифратора подается более одной единицы – шифратор будет работать не-

верно, либо надо использовать приоритетный шифратор.

IV) Мультиплексоры и демультиплексоры (коммутаторы) (MUX и DMUX)

M = [Log

N] Di {Aj}

Демультиплексор – обратно – подключение одного логического входа к множеству

выходов (каналов)

В общем случае Мультиплексор может быть многоразрядным

V) Буфер – разрешает передачу входа на выход при установке разрешающего кода в 1

DC D

. .

2n-1

D3D2D1D0

0 0 0 0 0 1

0 1 0 0 1 0

1 0 0 1 0 0

1 1 1 0 0 0

Мультиплексор - осуществляет логическую

коммутацию нескольких входов с

единственным выходом.

MUX

. D

n-1

MUX

. D

n-1

m – канальный

к – разрядный

= D

(OE = 1)

= - (OE = 0)

Базовые автоматы с памятью

VI) Триггеры (flip-flop) – ячейки памятью в 1 бит.

Делятся:

1) По управляющим кодам:

RS – триггеры; JK – триггеры;

D – триггеры; T – триггеры и др.

2) По способу управления:

Асинхронные

Синхронные

Со статическим управлением

С динамическим управлением

VI.1) Асинхронные триггеры

1) RS триггер 2) JK триггер

Q(t+1) – следующее состояние триггера

S – Set J S

R – Reset K  R

3) T триггер (для построения счетчиков)

VI.2) Синхронные триггеры

1) Со статическим управлением

* - 0 или 1

Аналогично работают другие триггеры со статическим управлением.

2) С динамическим управлением

R T Q

S Q

RS Q(t+1)

00 Q(t)

01 1

10 0

11 -

J T Q

K Q

JK Q(t+1)

00 Q(t)

01 0

10 1

11 !Q(t)

TQ(t+1)

0 Q(t)

1!Q(t)

T T Q

R Q

D T Q

C Q

D C Q(t+1)

* 0 Q(t)

0 1 0

1 1 1

Уровень

сигнала

Работа

разрешена

D TT Q

C Q

D C Q(t+1)

* 0 Q(t)

* 1 Q(t)

0 / 0

1 / 1

Уровень

сигнала

Фронт

Триггер управляется фронтом (спадом) сигнала синхронизации.

Аналогично работают RS, JK и Т триггеры.

VII] Регистры – совокупность триггеров с общей схемой управления. При этом

триггеры могут быть связаны друг с другом.

Основные типы:

- регистры хранения

- сдвиговые регистры

- многофункциональные регистры

Регистры предназначены для хранения и сдвигов многоразрядных кодов.

VIII) Счетчики – совокупность триггеров с дополнительными схемами управле-

ния. При этом триггеры связаны между собой, в том числе – цепями обратной связи.

RD RG

SL D

RD – read

WR – write

SL –shift left

SR – shift right

DL – digit left

DR – digit right

CTz

+1 D

-1

Счетчики предназначены для

хранения и выполнения операций

счета (инкремент и декремент).

Считают от 0 до 2

- 1

Приложение 2 Пример синтеза цифрового автомата

Согласно модели Глушкова цифровой автомат (ЦА) как устройство для автоматиче-

ской обработки цифровой информации по заданным алгоритмам представляет собой со-

вокупность операционного автомата (ОА) и управляющего автомата (УА). Первый служит

для выполнения собственно набора требуемых микроопераций алгоритма, а второй задает

последовательность действий по алгоритму в зависимости от условий (которые также

формируются операционным автоматом как логические сигналы).

Исходной информацией для синтеза операционного автомата является требуемый

для выполнения определенного набора алгоритмов (или одного алгоритма) набор микроо-

пераций. В алгоритме выделяют переменные, выходные и внутренние слова, набор ми-

кроопераций и логических условий, после чего выполняется синтез.

Этапы синтеза ОА:

1) Каждому входному слову ставится в соответствие шина необходимой разрядно-

сти, которая соединяется со входом регистра также необходимой разрядности, предназна-

ченного для хранения этого входного слова.

2) Каждому выходному слову ставится в соответствие шина, соединенная с выхо-

дом регистра.

3) Каждой внутренней переменной ставится в соответствие регистр необходимой

разрядности, либо счетчик для хранения этой переменной.

4) Каждой микрооперации y

задаваемой в алгоритме оператором присваивания ста-

вится в соответствие операционный элемент (ОЭ - комбинационная схема), либо сдвиго-

вый регистр, либо счетчик y

: b

= Ψ

, Q

, …, Q

), входы которого соединены с выхода-

ми регистров операндов с помощью неуправляемых шин, а выход соединен со входом

регистра результата с помощью шины, управляемой сигналом y

Рис.П2.1

5) Каждому логическому условию xj = λj(Q

, Q

, …, Q

) ставится в соответствие ком-

бинационная схема для его формирования, входы которой соединены с регистрами опе-

рандов, а выходы являются выходами автомата.

В результате этого синтеза получается автомат канонической структуры.

Часто такой автомат является избыточным, поскольку содержит избыточное количе-

ство ОЭ. Эти операционные элементы можно исключить, используя одни и те же ОЭ для

выполнения различных микроопераций.

Исключив все элементы, которые являются избыточными, получим I - автомат. При

этом избыточными являются элементы, которые нельзя использовать параллельно с други-

ми и которые могут быть заменены другими существующими в автомате элементами.

Рассмотрим пример синтеза автомата канонической структуры на примере автомата

для выполнения умножения беззнаковых четырехразрядных чисел (модулей).

Используем схему умножения с младших разрядов множителя со

сдвигом вправо суммы частичных произведений (СЧП). Пусть A -

множимое, B – множитель, C – СЧП. Младший разряд имеет

индекс n-1= 3 (n = 4). Получим алгоритм, изображенный на рис. 5.

Пример вычислений по алгоритму приведен ниже.

Регистр С Регистр

Комментарий

0000

+0101

0101

0010

+0101

0111

0011

0001

011

001

000

100

110

C:=0; CNT=4 (n=4) - счетчик

B(4)=0  B ; C  CNT=4-

1=3;

CNT<>0 B(4)=1 => C:=C+A

CNT=3-1=2;

CNT<>0 B(4)=1 => C:=C+A

CNT=2-1=1;

CNT<>0 B(4)=0 =>

CNT=1-1=0;

Рис. П2.2

Результат : произведение равно 30 / 256 (старшая часть в C, младшая - в B,

множитель не сохраняется).

В алгоритме можно выделить следующие переменные :

А, В – входные переменные

B, C – выходные переменные

CNT – внутренняя переменная (счетчик)

Также в алгоритме можно выделить несколько микроопераций, часть из которых

могут выполняться параллельно и их можно объединить в микрокоманды. Всего отдель-

ных микрокоманд три, они обозначены на рис. П2.2 Y0 – Y2.

В одной микрокоманде можно выполнять совместные микрооперации. К несовме-

стимым относятся:

1) Запись значений в один и тот же регистр.

2) Запись в регистр и сдвиг регистра (то есть параллельная и последовательная за-

пись).

Помимо микрокоманд в алгоритме выделяем также два логических условия (инфор-

мационных сигнала ОА). Они обозначены на рис. П2.2 как x0 и x1.

Пример:

A = 5/16 B = 6/16

A = ,0101 B = ,0110

С := 0

CNT := n

B(n)

B := B / 2

B(1) := C(n)

C:=C/2

CNT := CNT -1

C := C +A

CNT = 0?

По данному алгоритму в соответствии с рассмотренными выше этапами синтеза

можно синтезировать следующую функциональную схему операционного автомата (рис.

П2.3) :

Рис. П2.3

Рассмотрим синтез управляющего автомата с

жесткой логикой для ЦА, реализующего алгоритм

косвенного умножения модулей (беззнаковых чи-

сел).

Схема алгоритма приведена на рис. П2.4. (до-

полнительно к рассмотренному в лабораторной

работе №1 алгоритму в этом алгоритме введен

цикл ожидания начала работы и соответсвующий

управляющий сигнал Start).

Будем синтезировать автомат Мура на базе D-

триггеров. Сначала обозначим состояния на алго-

ритме и составим отмеченную таблицу переходов

(ОТП) для автомата Мура :

Y0 - Load

X1 - Bn

Y2 - ShiftR

Done

Y1 - Add

X2 -Zero

Done

X0 - Start

Рис. П2.4

Таблица П2.1 (ВС – Входной Сигнал, ПС – Предыдущее Состояние)

ВС\ПС b0 b1 b2 b3

Start b1 - - -

!Start b0 - - -

!X1!X2 - b3 b3 b3

!X1X2 - b3 b3 b2

X1!X2

X1X2 - b2 b3 b0

Теперь можно приступить собственно к синтезу УАЖЛ. Закодируем со-

стояния автомата с помощью обычных двоичных кодов :

Таблица П2.2

Состояние Код

b0 00

b1 01

b2 10

b3 11

Для заданного типа триггеров (D-триггеры) составим его таблицу

переходов как элементарного автомата :

Таблица П2.3

Переход D

0 → 0 0

0 → 1 1

1 → 0 0

1 → 1 1

Составим закодированную таблицу переходов (выходные сигналы в та-

блице не отмечаем, так как их можно получить с помощью дешифратора кода

состояния).