Pull to refresh

RAM-машина

Reading time 3 min
Views 12K

Часть I
Часть II
Часть III
Часть IV
Часть V


На Хабре уже была опубликована статья, посвящённая RAM-машине.
Вообще, статья про RAM-машину есть на Википедии.

RAM-машина, которая упоминается в книге «Построение и анализ вычислительных алгоритмов» (авторы: Ахо, Хопкрофт, Ульман) имеет ограниченный набор арифметических команд (сложение, вычитание, умножение, деление), команду безусловного перехода, две команды условных переходов. У нас же из арифметических команд будут только сложение и вычитание, команды ветвления (переходов) будут идентичными командам, приведённым в книге.

Отличием LIttle Man Computer'а (который я описывал в предыдущих частях цикла) от RAM-машины является механизм, обеспечивающий косвенную адресацию (возможность работать с числом, хранящемся в памяти, как с адресом).

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



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



Также будем загружать загружать адрес команды в аккумулятор Acc как число, для этого увеличим разрядность адресного входа мультиплексора, производящего выборку данных для загрузки в аккумулятор Асс. Адрес загружается на 4ый вход мультиплексора.



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



1ый такт осуществляет загрузку адреса в адресный регистр, 2ой такт осуществляет загрузку числа в аккумулятор Acc или в Память данных.

Подключим к аккумулятору 2 флага:

1. Флаг Acc = 0. Флаг поднимается, если содержимое Асс равно нулю.

2. Флаг Acc > 0. Флаг поднимается, если содержимое Асс больше нуля.


Получилась вот такая схема, которую можно скачать отсюда



Линия, идущая на разрешающий вход аккумулятора, нужна для того, чтобы схема не глючила.

Отключим некоторые команды и напишем программу, которая загружает нулевую ячейку Памяти данных по адресу, хранящемуся в нулевой ячейке. Будем в цикле увеличивать значение нулевой ячейки на единицу. Т.о. мы заполним Память данных порядковыми номерами.

1401 загружаем в Acc число 1
1100 прибавляем число в Acc к числу в нулевой ячейке
2000 сохраняем результат в нулевой ячейке
2080 загружаем число из Acc по адресу, на который ссылается нулевая ячейка
0010 прыгаем в начало программы




Напишем программу, суммирующую $ n $ натуральных чисел.
Будем записывать натуральные числа в 1ой ячейке, а их сумму в 0ой ячейке.
Для начала напишем программу, загружающую натуральные числа в первую ячейку
1401 загружаем в Acc число 1
1101 прибавляем число в Acc к числу в 1ой ячейке
2001 сохраняем результат в 1ой ячейке

В 0ой ячейке будем производить суммирование. После увеличения числа в 1ой ячейке надо прибавить это число к 0ой ячейке.
1300 загружаем в Acc число из ячейки 0
1101 прибавляем число в Acc к числу в 1ой ячейке
2000 сохраняем результат в 0ой ячейке
0010 прыгаем в начало программы

Полный текст программы
1401
1101
2001
1300
1101
2000
0010

Для того, чтобы вычислить $ n $ членов арифметической прогрессии, необходимо в 0ую ячейку загрузить первое слагаемое $ a_{0} $, в 1ую ячейку загрузить разность арифметической прогрессии $ d $.
Далее необходимо произвести суммирование:
1300 загружаем в Acc число из ячейки 0
1101 прибавляем число в Acc к числу в 1ой ячейке
2000 сохраняем результат в 0ой ячейке
Далее необходимо прыгнуть на 3 команды назад и повторить этот набор операций $ n $ раз.


Эмулятор классической RAM-машины (с раздельными лентами чтения/записи) можно скачать отсюда.



Проверим как работает схема, состоящая из двух d-триггеров. Эта схема обеспечивает двух-тактовый режим.
Напишем схему обычного d-триггера (без reset и enable). У него будет два входных порта — порт данных и тактовый порт.
module dff
(
    input  [1:0] key,  
  	 output  led 
);
wire clk;
assign clk = key [0]; // тактовый вход
  wire d =  key [1]; // вход данных
  reg q;
    always @(posedge clk)
      q <= d;
 assign led  = q;
endmodule


Светодиод led показывает состояние d-триггера.
Подключим два dff в общую схему.
Состояние первого d-триггера будет показывать светодиод q1_led.
Состояние второго d-триггера будет показывать светодиод q2_led.
Выведем тактовый сигнал на отдельный светодиод q3_led.

module dff_dff 
(
input clk,
output q1_led, q2_led,q3_led
);
assign q3_led = clk;
wire d1_in;
assign d1_in=~q2_led;
dff dff1(
 .clk(clk),
 .d(d1_in),
 .q(q1_led)
);
wire d2;
assign d2=q1_led;
dff dff2(
 .clk(clk),
 .d(d2),
 .q(q2_led)
);
endmodule

RTL-модель модуля dff_dff выглядит так

Работоспособность схемы можно проверить, непосредственно загрузив программу в ПЛИС.
Эта схема будет работать не на всех платах, на некоторых платах необходимо производить инициализацию d-триггеров. По этой же причине такая схема не будет симулироваться в ModelSim.
Tags:
Hubs:
+29
Comments 0
Comments Leave a comment

Articles