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

Содержание 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. Форматы команд и их кодировка Коды команд КОП Команда Действие 000 ADD Rx,Ry,Rz Rx=Ry+Rz сложение 001 NAND Rx,Ry,Rz Rx=!(Ry&Rz) И-НЕ 010 SHR Rx,Ry Rx=Ry/2 арифметический сдвиг вправо 011 JC address jmp on carry условный переход по переносу 100 DEC Rx,Ry Rx=Ry-1 декремент (уменьшение на 1) 101 SUB Rx,Ry,Rz Rx=Ry-Rz вычитание 110 LD Rx,address Rx=Mem(address) загрузка из ОЗУ в регистр 111 ST Ry,address Mem(address)=Rx запись из регистра в ОЗУ Формат команд ADD Rx,Ry,Rz КОП Rx Ry Rz не используется 0 0 0 x x y y z z NAND Rx,Ry,Rz КОП Rx Ry Rz не используется 0 0 1 x x y y z z SHR Rx,Ry КОП Rx Ry не используется 0 1 0 x x y y JC address КОП не использ. address 0 1 1 a a a a a a a a DEC Rx,Ry КОП Rx Ry не используется 1 0 0 x x y y Сокращения:КОП – код команды Rx – регистр приемник Ry – регистр источник 1 Rz – регистр источник 2 address – 8-битный адрес SUB Rx,Ry,Rz КОП Rx Ry Rz не используется 1 0 1 x x y y z z LD Rx,address КОП Rx не исп. address 1 1 0 x x a a a a a a a a ST Rx,address КОП не исп Ry address 1 1 1 y y a a a a a a a a Структурная схема процессора Регистры Номер При записи (по шине С) При чтении (по шине A и B) 000 0 Rg0 программно-доступные регистры Rg0 программно-доступные регистры 001 1 Rg1 Rg1 010 2 Rg2 Rg2 011 3 Rg3 Rg3 100 4 Temp0 Temp0 101 5 PC PC 110 6 IR_HI (старшая часть IR) IR константа 1 111 7 IR_LO (младшая часть IR) IR_LO При чтении старшей части регистра команд, на шину 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 вспомогательных регистров, которые по желанию программиста могут быть аккумуляторами, индексными регистрами или использоваться для запоминания промежуточных результатов. Формат микрокоманд MIR – Microinstruction register – регистр микрокоманд (24 bit) A A MUX B B MUX C C MUX RD WR ALU COND JMP ADDRESS A, B, C – номер регистра для осуществления чтения (A, B) или записи (C) A MUX, B MUX, C MUX – откуда брать номер регистра (0 – из команды IR, 1 – из микрокоманды MIR) RD – чтение из ОЗУ При этом адрес памяти берется с шины А, а результат подается на шину С WR – запись в ОЗУ При этом адрес памяти берется с шины А, а данные – с шины B ALU – код операции АЛУ КОП АЛУ Операция АЛУ 00 NOP 01 ADD 10 SHRA 11 NAND COND – условие для определения адреса следующей выполняемой микрокоманды COND Куда переходим 00 NEXT на следующую микрокоманду 01 DECODE декодирование команды, Address = [KOP]100 10 JMP безусловный переход 11 JC условный переход по переносу (Carry Flag) JMP ADDRESS – адрес в памяти микропрограмм, куда осуществляется переход Микрокод Адрес Микрокоманда Пояснение 0 1 2 3 IR_HI = NOP(PC); READ PC = ADD(PC, IR_HI) IR_LO = NOP(PC); READ DECODE чтение старшего слова команды переход к следующему слову (PC = PC + 1) чтение младшего слова команды декодирование считанной команды ADD Rx, Ry, Rz 4 Rx = ADD(Ry, Rz); JMP 62 сложение содержимого регистров NAND Rx, Ry, Rz 12 Rx = NAND(Ry,Rz); JMP 62 И-НЕ для содержимого регистров SHR Rx, Ry 20 Rx = SHR(Ry); JMP 62 арифметич. сдвиг содержимого регистра JC address 28 29 30 Temp0 = NOP(Temp0); JC 30 JMP 62 PC = NOP(IR_LO); JMP 0 организация условного перехода если условие не выполнилось, то завершить иначе записать в PC новый адрес из IR_LO DEC Rx, Ry 36 37 38 Temp0 = SHR(IR_HI) Temp0 = NAND(Temp0, Temp0) Rx = ADD(Ry,Temp0); JMP 62 Temp0 = 0 (00000001  00000000) Temp0 = -1 (11111111) Rx = Ry + Temp0 = Ry + (-1) SUB Rx, Ry, Rz 44 45 46 47 48 Temp0 = SHR(IR_HI) Temp0 = ADD(Temp0, Rz) Temp0 = NAND(Temp0, Temp0) Temp0 = ADD(Temp0, IR_HI) Rx = ADD(Ry, Temp0); JMP 62 Temp0 = 0 (00000001  00000000) Temp0 = 0 + Rz = Rz инвертировать Temp0 = Rz Temp0 = ( ! Rz) + 1 Rx = Ry + (-Rz) LD Rx, address 52 Rx = NOP(IR_LO); READ; JMP 62 чтение из ОЗУ (шина A – адрес) ST Ry, address 60 61 Temp0 = NOP(Ry) Temp0 = NOP(IR_LO, Temp0); WRITE; JMP 62 Temp0 = Ry (данные на шину B) запись в ОЗУ (шина A – адрес, шина B – данные) End: 62 PC = ADD(PC, IR_HI); JMP 0 увеличение счетчика команд (PC=PC+1) Кодировка микрокода DEPTH = 64; % количество слов % WIDTH = 24; % размер слова в битах % ADDRESS_RADIX = DEC; % система счисления для адреса % DATA_RADIX = BIN; % система счисления для данных % CONTENT BEGIN [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 ; Примеры выполнения командПримеры выполнения каждой команды с указанием значения всех основных сигналов и содержимым основных регистров на каждом такте выполнения приведены на электронном носителе.Основные сигналы и регистры Сокращение Примечание CLOCK синхронизирующий сигнал C_SEL[2..0] номер регистра выбранного в качестве приемника A_SEL[2..0] номер регистра выбранного в качестве источника 1 B_SEL[2..0] номер регистра выбранного в качестве источника 2 Rx[2..0] номер регистра приемника из IR (регистра команд) Ry[2..0] номер регистра источника 1 из IR (регистра команд) Rz[2..0] номер регистра источника 2 из IR (регистра команд) MIR_A[2..0] номер регистра приемника из MIR (р-ра микрокоманд) MIR_B[2..0] номер регистра источника 1 из MIR (р-ра микрокоманд) MIR_C[2..0] номер регистра источника 2 из MIR (р-ра микрокоманд) AMUX Откуда брать номер регистра (0 – из IR, 1 – из MIR) Эти сигналы управляют соответствующими мультиплексорами. BMUX CMUX A_bus[7..0] Данные на шинах источниках, выходящих из блока регистров B_bus[7..0] C_ALU[7..0] Результат выходящий из АЛУ C_RAM[7..0] Данные, считанные из ОЗУ C_bus[7..0] Выбранные данные для записи (С_ALU или C_RAM) RD сигнал чтения из ОЗУ WR сигнал записи в ОЗУ KOP_ALU[1..0] код операции АЛУ (поступает из MIR) COND[1..0] определение следующей микрокоманды (из MIR) CBL_SEL[1..0] результат работы Control Branch Logic (логика управления ветвлением) – определяет следующую микрокоманду CF флаг переноса, поступающий из АЛУ в Control Branch Logic JMP_ADR[5..0] адрес следующей микрокоманды (из MIR) MIR[23..0] полное значение регистра микрокоманд (24 бит) PC программный счетчик (адрес в ОЗУ) Примеры программ ПРИМЕР 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: 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 ; ПРИМЕР 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: 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 / сек). Тестовая программа Количество команд процессора Количество микрокоманд Время выполнения, нс N / сек ПРИМЕР 1 3 18 540 1851851 ПРИМЕР 2 5 34 1020 980398 Повысить производительность процессора можно одним из следующих способов: Увеличить разрядность шины-приемника с 8 до 16 бит, и считывать команду из ОЗУ не за три такта, а за один; Увеличить функциональность АЛУ, при этом можно будет сократить длину микрокода для некоторых команд (особенно для SUB и DEC); Перейти от микропрограммного управления к управлению на основе жесткой логики; Применить конвейеризацию; Что-нибудь распараллелить.