Линейное программирование симплекс-методом Данцига

1. Постановка задачи

2. Форматы команд и их кодировка

3. Структурная схема процессора

4. Регистры

5. АЛУ

6. Формат микрокоманд

7. Микрокод

8. Кодировка микрокода

9. Примеры выполнения команд

10. Основные сигналы и регистры процессора

11. Примеры программ

12. Определение производительности

Постановка задачи

Синтезировать структуру простого магистрального процессора с одним АЛУ, выполняющего 8 заданных команд. Разработать формат команд, кодировку команд. Разработать структурную схему процессора, функциональные схемы всех блоков процессора, функциональную схему процессора в целом с указанием всех шин и управляющих сигналов.

Разработать формат микрокоманд, организацию управления всеми устройствами процессора, микрокод для каждой из заданных команд. Привести примеры выполнения каждой команды с указанием значения всех основных сигналов и содержимого основных регистров на каждом такте. Привести 2 примера небольших программ с указанием значения основных сигналов и содержимого основных регистров на каждом такте.

Определить максимальную тактовую частоту процессора. Определить производительность процессора в операциях в секунду (IPS), а также выраженную в числе выполняемых тестовых программ в секунду. Указать способы повышения производительности процессора.

Характеристика процессора Простой процессор магистрального типа с одноблочным универсальным АЛУ.

Разрядность регистров РОН и АЛУ процессора — 8 бит.

Число РОН — 4.

Адресуемая память — 256 слов.

Устройство управления — микропрограммное с ПЗУ микропрограмм.

Способ выполнения команд — последовательное выполнение или JMP или JC.

Адресация памяти — прямая.

Арифметика в дополнительном коде.

Вариант: 54 = «2 2 2 3»

Без использования непосредственной адресации.

3х-адресные команды.

Операции АЛУ: NOP, ADD + SHRA, NAND.

Состав команд: LD, ST, ADD, SHR + JC, DEC, SUB, NAND.

Форматы команд и их кодировка

Коды команд

Формат команд

Структурная схема процессора

Регистры

При чтении старшей части регистра команд, на шину A или B поступает единичная константа (1). Это вполне допустимо, т.к. старшая часть регистра команд имеет свои выходы из блока регистров: (КОП, Rx, Ry, Rz). Младшая часть регистра команд поступает на шины A или B в неизменном виде, т.к. в некоторых командах процессора в младшей части регистра команд находиться 8-битный адрес. Единичная константа применяется при инкрементировании счетчика команд, а также для получения константы -1 = 11 111 111 (см. микрокод для команды DEC).

Разрядность РОН (регистры общего назначения) — 8 бит

Разрядность PC (program counter) — 8 бит

Разрядность IR (регистр команд) — 16 бит (доступно два регистра по 8 бит)

АЛУ

Структурная схема АЛУ и его связь с другими блоками машины показаны на рисунке. В состав АЛУ входят регистры Рг1 — Рг7, в которых обрабатывается информация, поступающая из оперативной или пассивной памяти N1, N2, …NS; логические схемы, реализующие обработку слов по микрокомандам, поступающим из устройства управления.

Закон переработки информации задает микропрограмма, которая записывается в виде последовательности микрокоманд A1, A2, …, Аn-1,An. При этом различают два вида микрокоманд: внешние, то есть такие микрокоманды, которые поступают в АЛУ от внешних источников и вызывают в нем те или иные преобразования информации (на рис. 1 микрокоманды A1, A2,…, Аn), и внутренние, которые генерируются в АЛУ и воздействуют на микропрограммное устройство, изменяя естественный порядок следования микрокоманд. Например, АЛУ может генерировать признаки в зависимости от результата вычислений: признак переполнения, признак отрицательного числа, признак равенства 0 всех разрядов числа др. На рис. 1 эти микрокоманды обозначены р1, p2,…, рm.

Результаты вычислений из АЛУ передаются по кодовым шинам записи у1, у2, …, уs, в ОЗУ.

Функции регистров, входящих в АЛУ:

Рг1 — сумматор (или сумматоры) — основной регистр АЛУ, в котором образуется результат вычислений;

Рг2, РгЗ — регистры слагаемых, сомножителей, делимого или делителя (в зависимости от выполняемой операции);

Рг4 — адресный регистр (или адресные регистры), предназначен для запоминания (иногда и формирования) адреса операндов и результата;

Ргб — k индексных регистров, содержимое которых используется для формирования адресов;

Рг7 — i вспомогательных регистров, которые по желанию программиста могут быть аккумуляторами, индексными регистрами или использоваться для запоминания промежуточных результатов.

Формат микрокоманд

A, B, C — номер регистра для осуществления чтения (A, B) или записи (C)

A MUX, B MUX, C MUX — откуда брать номер регистра

(0 — из команды IR, 1 — из микрокоманды MIR)

RD — чтение из ОЗУ

При этом адрес памяти берется с шины А, а результат подается на шину С

WR — запись в ОЗУ

При этом адрес памяти берется с шины А, а данные — с шины B

ALU — код операции АЛУ

COND — условие для определения адреса следующей выполняемой микрокоманды

JMP ADDRESS — адрес в памяти микропрограмм, куда осуществляется переход

Микрокод

Кодировка микрокода

DEPTH = 64; % количество слов %

WIDTH = 24; % размер слова в битах %

ADDRESS_RADIX = DEC; % система счисления для адреса %

DATA_RADIX = BIN; % система счисления для данных %

CONTENT

BEGIN

[0.63]: 0; % по умолчанию везде нули %

% Инициализация %

0: 101 100 011 101 099 994 906 624; % IR_HI = NOP (PC); READ %

1: 101 111 011 011 000 098 881 536; % PC = ADD (PC, IR_HI) %

2: 101 100 011 111 100 004 171 776; % IR_LO = NOP (PC); READ %

3: 100 011 001 000 000 995 328; % DECODE %

% ADD Rx, Ry, Rz %

4: 110 111 110; % Rx = ADD (Ry, Rz); JMP 62%

% NAND Rx, Ry, Rz %

12: 1 110 111 110; % Rx = NAND (Ry, Rz); JMP 62%

% SHR Rx, Ry %

20: 1 010 111 110; % Rx = SHR (Ry); JMP 62%

% JC address %

28: 100 110 011 001 000 005 992 448; % Temp0 = NOP (Temp0); JC 30%

29: 100 110 011 001 000 005 992 448; % JMP 62%

30: 111 110 011 011 000 017 354 752; % PC = NOP (IR_LO); JMP 0%

% DEC Rx, Ry %

36: 110 100 011 001 001 006 858 240; % Temp0 = SHR (IR_HI) %

37: 100 110 011 001 001 096 511 488; % Temp0 = NAND (Temp0, Temp0) %

38: 10 010 000 000 110 110 720; % Rx = ADD (Ry, Temp0); JMP 62%

% SUB Rx, Ry, Rz %

44: 110 100 011 001 001 006 858 240; % Temp0 = SHR (IR_HI) %

45: 100 100 001 001 000 100 954 112; % Temp0 = ADD (Temp0, Rz) %

46: 100 110 011 001 001 096 511 488; % Temp0 = NAND (Temp0, Temp0) %

47: 100 111 011 001 000 100 102 144; % Temp0 = ADD (Temp0, IR_HI) %

48: 10 010 000 000 110 110 720; % Rx = ADD (Ry, Temp0); JMP 62%

% LD Rx, address %

52: 111 100 010 000 100 005 773 312; % Rx = NOP (IR_LO); READ; JMP 62%

% ST Ry, address %

60: 11 001 000 000 000 000; % Temp0 = NOP (Ry) %

61: 111 110 011 001 010 007 310 336; % Temp0 = NOP (IR_LO, Temp0);

WRITE; JMP 62%

62: 101 111 011 011 000 115 658 752; % PC = ADD (PC, IR_HI); JMP 0%

END ;

Примеры выполнения команд

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

Основные сигналы и регистры

Примеры программ

ПРИМЕР 1

DEPTH = 256; % Memory depth and width are required %

WIDTH = 8; % Enter a decimal number %

ADDRESS_RADIX = DEC; % Address and value radixes are optional %

DATA_RADIX = BIN; % Enter BIN, DEC, HEX, or OCT; unless %

CONTENT

BEGIN

%—————————-%

0: 11 001 000; % LD Rg1, %

1: 110;

2: 11 010 000; % LD Rg2, %

3: 111;

4: 11 011; % ADD Rg3, Rg1, Rg2%

5: 0;

6: 10 110; % const 22 (DEC) %

7: 100 001; % const 33 (DEC) %

END ;

ПРИМЕР 2

DEPTH = 256; % Memory depth and width are required %

WIDTH = 8; % Enter a decimal number %

ADDRESS_RADIX = DEC; % Address and value radixes are optional %

DATA_RADIX = BIN; % Enter BIN, DEC, HEX, or OCT; unless %

CONTENT

BEGIN

%————————-%

0: 11 001 000; % LD Rg1, %

1: 1 010;

2: 1 010 010; % SHR Rg2, Rg1%

3: 111;

4: 1 100 000; % JC 8%

5: 1 000;

6: 10 010 010; % DEC Rg2, Rg1%

7: 0;

8: 11 100 010; % ST Rg1, %

9: 1 010;

10: 1; % const = 1%

END ;

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

Определение производительности

Среднее количество микрокоманд при выполнении команды процессора можно приблизительно оценить как 4 + 17/8 + 1 = 7 микрокоманд на команду процессора. Таким образом, при максимальной тактовой частоте в 33,3 МГц средняя производительность процессора составит 4, 7 MOPS (или 33,3 М мops / сек).

Повысить производительность процессора можно одним из следующих способов:

§ Увеличить разрядность шины-приемника с 8 до 16 бит, и считывать команду из ОЗУ не за три такта, а за один;

§ Увеличить функциональность АЛУ, при этом можно будет сократить длину микрокода для некоторых команд (особенно для SUB и DEC);

§ Перейти от микропрограммного управления к управлению на основе жесткой логики;

§ Применить конвейеризацию;

§ Что-нибудь распараллелить.