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

Содержание

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 поступает единичная константа (00000001). Это вполне допустимо, т.к. старшая часть регистра команд имеет свои выходы из блока регистров: (КОП, Rx, Ry, Rz). Младшая часть регистра команд поступает на шины A или B в неизменном виде, т.к. в некоторых командах процессора в младшей части регистра команд находиться 8-битный адрес. Единичная константа применяется при инкрементировании счетчика команд, а также для получения константы -1 = 11111111 (см. микрокод для команды 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; % система счисления для данных %CONTENTBEGIN[0..63] : 0; % по умолчанию везде нули %% Инициализация %0: 101100011101100000000000; % IR_HI = NOP(PC); READ %1: 101111011011000100000000; % PC = ADD(PC, IR_HI) %2: 101100011111100000000000; % IR_LO = NOP(PC); READ %3: 000100011001000001000000; % DECODE % % ADD Rx, Ry, Rz %4: 000000000000000110111110; % Rx = ADD(Ry, Rz); JMP 62 % % NAND Rx, Ry, Rz %12: 000000000000001110111110; % Rx = NAND(Ry,Rz); JMP 62 % % SHR Rx, Ry %20: 000000000000001010111110; % Rx = SHR(Ry); JMP 62 % % JC address %28: 100110011001000011011110; % Temp0 = NOP(Temp0); JC 30 %29: 100110011001000010111110; % JMP 62 %30: 111110011011000010000000; % PC = NOP(IR_LO); JMP 0 %% DEC Rx, Ry %36: 110100011001001000000000; % Temp0 = SHR(IR_HI) %37: 100110011001001100000000; % Temp0 = NAND(Temp0, Temp0) %38: 000010010000000110111110; % Rx = ADD(Ry,Temp0); JMP 62 %% SUB Rx, Ry, Rz %44: 110100011001001000000000; % Temp0 = SHR(IR_HI) %45: 100100001001000100000000; % Temp0 = ADD(Temp0, Rz) %46: 100110011001001100000000; % Temp0 = NAND(Temp0, Temp0) %47: 100111011001000100000000; % Temp0 = ADD(Temp0, IR_HI) %48: 000010010000000110111110; % Rx = ADD(Ry, Temp0); JMP 62 %% LD Rx, address %52: 111100010000100010111110; % Rx = NOP(IR_LO); READ; JMP 62% % ST Ry, address %60: 000000011001000000000000; % Temp0 = NOP(Ry) %61: 111110011001010010111110; % Temp0 = NOP(IR_LO, Temp0); WRITE; JMP 62 %62: 101111011011000110000000; % PC = ADD(PC, IR_HI); JMP 0 %END ; Примеры выполнения команд

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

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

Примеры программПРИМЕР 1DEPTH = 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 %CONTENTBEGIN %-------------------%0: 11001000; % LD Rg1, [6] %1: 00000110; 2: 11010000; % LD Rg2, [7] %3: 00000111; 4: 00011011; % ADD Rg3, Rg1, Rg2 %5: 00000000; 6: 00010110; % const 22 (DEC) %7: 00100001; % const 33 (DEC) % END ; ПРИМЕР 2DEPTH = 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 %CONTENTBEGIN %-----------------%0: 11001000; % LD Rg1, [10] %1: 00001010; 2: 01010010; % SHR Rg2, Rg1 %3: 00000111; 4: 01100000; % JC 8 %5: 00001000; 6: 10010010; % DEC Rg2, Rg1 %7: 00000000; 8: 11100010; % ST Rg1, [10] %9: 00001010; 10: 00000001; % const = 1 % END ;Значения основных сигналов и содержимое основных регистров на каждом такте выполнения данных примеров программ приведены в виде временных диаграмм на электронном носителе.Определение производительности

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

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

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

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

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

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

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