Scientific journal

Scientific Review. Technical science

ISSN 2500-0799

ПИ №ФС77-57440

Неотъемлемой составляющей образовательного процесса, связанного с изучением вычислительной техники, является экспериментальное исследование изучаемых устройств. В настоящее время для проведения экспериментального исследования наряду со специальным лабораторным оборудованием широко применяются программные модели устройств. Программные модели создаются с помощью универсальных сред программирования или специальных систем.

Примерами специальных систем могут служить: среда функционально-логического моделирования MatLab/Simulink и САПР Quartus II компании Altera [1, 2]. Если образовательный процесс предполагает подготовку разработчиков средств вычислительной техники, то обучающиеся могут самостоятельно разрабатывать устройства, используя систему автоматизированного проектирования [2]. В то же время, если такой задачи не ставится, то более глубокого изучения структуры и алгоритма работы устройства можно достигнуть, когда обучающиеся самостоятельно строят и экспериментально исследуют действующую функциональную модель этого устройства с помощью системы моделирования. В этом случае представляет интерес использование в качестве средства моделирования табличного процессора Microsoft Excel, с которым обучающие, как правило, уже знакомы [3].

Цель работы: анализ возможностей применения технологии построения и экспериментального исследования учебных функциональных моделей устройств вычислительных машин, использующей в качестве средства моделирования табличный процессор Microsoft Excel, для создания моделей запоминающих устройств типа стек.

В общем случае стек – это структура данных, представляющая собой список элементов, организованных по принципу «последним пришел – первым вышел» (Last In – First Out, LIFO) [4]. Известно два основных подхода к построению памяти типа стек. В первом случае стек строится как регистровый файл с цепями реверсивного сдвига [5], а во втором – состоит из блока памяти адресного ЗУ с регистром-счетчиком, в котором хранится адресный маркер (указатель стека). Если стек входит в состав процессора, то функции блока памяти адресного ЗУ может выполнять область регистровой или оперативной памяти, а функции регистра указателя стека – специальный регистр или регистр общего назначения процессора. В зависимости от того, какую ячейку (первую свободную или последнюю занятую) выделяет указатель стека в режиме хранения данных и в какую сторону (младших или старших адресов) при записи растет стек, возможны четыре варианта организации стека на основе блока памяти (табл. 1).

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

Структура и режимы работы моделируемого стека

Структура моделируемого стека приведена на рисунке 1а, где СЗЧ – счетчик записи-чтения, выполняющий функции регистра указателя стека; БП – блок памяти, выполняющий функции накопителя стека; РЗД – регистр записи данных; РЧД – регистр чтения данных. СЗЧ можно устанавливать в нулевое состояние при подаче сигнала «Установка “0”», а также увеличивать (уменьшать) его содержимое с помощью сигнала «+1» («–1»).

Стек работает в трех режимах: запись, чтение и хранение. Запись производится по сигналу ЗП (запись), при этом содержимое РЗД записывается в БП по адресу, хранящемуся в СЗЧ. Чтение осуществляется по сигналу ЧТ (чтение) и приводит к считыванию содержимого БП по адресу из СЗЧ в РЧД. При отсутствии сигналов ЗП и ЧТ стек находится в режиме хранения. В процессе работы стека формируются два осведомительных сигнала: З (стек полностью заполнен) и П (стек пуст).

Алгоритм записи в стек приведен на рисунке 1б, где М[СЗЧ] – содержимое ячейки БП с адресом, указанным в СЗЧ. Запись производится только в том случае, если стек заполнен не полностью (З=0). При этом в первом такте содержимое РЗД записывается в ячейку БП по адресу из СЗЧ, а во втором такте содержимое СЗЧ увеличивается на единицу.

Алгоритм чтения из стека приведен на рисунке 1в. Чтение производится только в том случае, если стек не пуст (П=0). При этом в первом такте содержимое СЗЧ уменьшается на единицу, а во втором такте содержимое ячейки БП по адресу из СЗЧ считывается в РЧД.

Работа стека на примере записи последовательности данных a, b, c и чтения данного c показана на рисунке 1г, где ЯП 0, ЯП2 1, ЯП 2, ЯП 3 – ячейки БП, а символом «*», представляющим маркер записи (указатель стека), отмечена ячейка, адрес которой находится в СЗЧ. В примере в режиме хранения указатель стека показывает на первую свободную ячейку памяти, а стек растет в сторону старших адресов.

В рассматриваемом стеке единичное значение признака З формируется, когда число в СЗЧ после записи превысит максимальный адрес ячейки БП, а единичное значение признака П – когда число в СЗЧ после чтения станет равным нулю.

Таблица 1

Варианты организации стека на основе блока памяти

Рис. 1. Стек на основе блока памяти: структура (а), алгоритм записи (б), алгоритм чтения (в), пример записи и чтения (г)

Реализация функций стека с помощью функций Microsoft Excel

Применяемый подход основан на пословном моделировании основных узлов и блоков ЭВМ с помощью стандартных функций Microsoft Excel, когда в ячейках могут находиться многоразрядные двоичные коды, а вычисления производятся в десятичной системе счисления. При этом сохраняется представление состояний входов и выходов узлов и блоков на экранных формах в двоичной системе счисления [3]. Пословное моделирование узлов и блоков позволяет значительно уменьшить объем работы по моделированию за счет использования меньшего числа более простых формул и сокращения количества необходимых ячеек Microsoft Excel.

В процессе разработки функциональной модели стека использовались следующие основные функции Microsoft Excel.

ДЕС(текст;основание). Преобразует текстовое представление числа с указанным основанием в десятичное число. Примеры: =ДЕС(100;2); =4. =ДЕС(100;2)+1; =5.

ОСНОВАНИЕ(число;основание;[минимальная_длина]). Преобразует число в текстовое представление с указанным основанием системы счисления. Пример: =ОСНОВАНИЕ(4;2;8); =00000100.

Увеличение двоичного числа (100) на единицу: =ОСНОВАНИЕ(ДЕС(100;2)+1;2;3); =101.

Уменьшение двоичного числа (100) на единицу: =ОСНОВАНИЕ (ДЕС(100;2)-1;2;3); =011.

ВЫБОР(номер_индекса;значение1;[значение2];...). Результатом вычисления функции является одно из значений, выбранное из последовательности аргументов, начинающейся со второго аргумента (значение1). Порядковый номер выбираемого аргумента последовательности задается первым аргументом (номер_индекса). Функция позволяет моделировать чтение из блока памяти. Первый аргумент функции ВЫБОР – (номер_индекса) используется в качестве адреса считываемой ЯП, который предварительно увеличивается на единицу. Увеличение адреса ЯП требуется в связи с тем, что адреса ЯП начинаются с нуля, а индекс может быть числом от 1 до 254. ЯП представляются в Microsoft Excel ссылками, которые задаются аргументами функции ВЫБОР: значение1;[значение2]; ...

Пример. Считывание данных в РСД, моделируемый ячейкой Microsoft Excel G15, из ЯП, двоичный код адреса которой находится в ячейке Microsoft Excel D6, может быть описано следующий формулой:

=ВЫБОР(ДЕС(D6;2)+1;G6;G7;G8;G9;G10;G11;G12;G13);G15).

Здесь G6, G7, …, G13 – ячейки Microsoft Excel, соответствующие ЯП, имеющим следующие двоичные коды адресов: 000, 001, …, 111. Первый аргумент функции ВЫБОР вычисляется путем преобразования двоичного кода адреса ЯП в десятичное число и увеличения его на единицу: ДЕС(D6;2)+1. При D6=100 в примере будет выбрана ЯП, представленная ячейкой Microsoft Excel G10, которая имеет в функции ВЫБОР номер 5.

Разработка функциональной модели стека

Разрабатывается функциональная модель учебного варианта рассмотренного стека, накопитель которого представляет собой БП, содержащий 8 8-разрядных ячеек памяти. Для удобства проведения экспериментальных исследований функциональная модель стека содержит одноразрядные поля управляющих сигналов: ЗП, ЧТ, НУ (начальная установка), ВД (ввод данных) и 8-разрядное поле данных Д (данные). Кроме того, в состав учебного стека включен блок управления (БУ), а вместо регистра записи данных используется регистр счетчик данных (РСД), что позволяет не только заносить в РСД данные из поля ввода данных Д, но и в режиме записи увеличивать содержимое РСД на единицу (при ВД=1).

Структура учебного стека при проведении экспериментальных исследований отображается на экранной форме, приведенной на рисунке 2. По сигналу НУ независимо от состояния БУ осуществляются следующие начальные установки: РСД:=Д; СЗЧ:=000; РЧД:=00000000, и во все ЯП записывается код 00000000. Запись в стек и чтение из стека выполняются за два такта. При записи в нечетных тактах (Т=1) производится запись данного из РСД в выбранную ЯП, а в четных (Т=0) содержимое СЗЧ увеличивается на единицу. При чтении в нечетных тактах (Т=1) содержимое СЗЧ уменьшается на единицу, а в четных (Т=0) данное из выбранной ЯП считывается в РЧД.

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

Таблица 2

Изменение состояний регистров, ячеек памяти и триггеров признаков стека в зависимости от управляющих и тактовых сигналов

а) б)

в)

Рис. 2. Экранная форма для экспериментального исследования стека: начальная установка (а), приостановка чтения (б), запись (в)

Функциональное моделирование стека осуществляется с помощью формул MS Excel (табл. 3).

Каждому регистру, ЯП и признаку выделяется соответствующая ячейка MS Excel, номер которой указан в квадратных скобках, следом за обозначением регистра, ЯП или признака.

Для моделирования функционирования БУ, РСД, СЗЧ, ЯП и РЧД, которые являются последовательностными схемами, используются формулы с циклическими ссылками, позволяющие сохранять состояния таких схем. Переход последовательностных схем в новые состояния осуществляется после подачи «синхронизирующего сигнала», который моделируется нажатием клавиши F9, вызывающим пересчет формул Microsoft Excel.

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

БУ[C3]: =ЕСЛИ(И(НЕ(D9);НЕ(C3));1;0) <Если сигнал НУ[D9]=1, то независимо от текущего состояния генератор после нажатия клавиши F9 переходит в состояние БУ[C3]=0 (Т=0), которое остается неизменным при последующих нажатиях этой клавиши. При НУ[D9]=0 каждое нажатие клавиши F9 вызывает смену состояния БУ[C3] на противоположное, формируя новые сигналы нечетных (Т=1) и четных (Т=0) тактов, влияющие на смену состояний других последовательностных схем>.

Таблица 3

Функциональное моделирование блоков, ячеек памяти и признаков стека с помощью формул MS Excel

РСД[G4]: =ЕСЛИ(ИЛИ(D9;И(B9; НЕ(C3); НЕ(I4))); G2<Если сигнал НУ[D9]=1 или сигнал записи ЗП[B9]=1 и БУ[C3]=0 (Т=0, четный такт) и сигнал ввода данных ВД[I4]=0, то в РСД[G4] заносится 8-разрядный двоичный код из поля ввода данных Д[G2]>;ЕСЛИ(И(B9;I4;НЕ(C3);НЕ(I7));ОСНОВАНИЕ(ДЕС(G4;2)+1;2;8)<иначе, если сигнал записи ЗП[B9]=1 и БУ[C3]=0 и сигнал ввода данных ВД[I4]=1 и стек заполнен не полностью З[I7]=0, то 8-разрядный двоичный код в РСД[G4] преобразуется в десятичную систему счисления и увеличивается на единицу, а затем снова преобразуется 8-разрядный двоичный код>;G4<иначе содержимое РСД[G4] сохраняется без изменения>)).

СЗЧ[D6]: =ЕСЛИ(D9;»000»<Если сигнал НУ[D9]=1, то СЗЧ[D6]=000>; ЕСЛИ(И(B9;НЕ(C3);НЕ(I7));ОСНОВАНИЕ(ДЕС(D6;2)+1;2;ЕСЛИ(D6=»1000»;4;3))<иначе, если сигнал записи ЗП[B9]=1 и БУ[C3]=0 и стек заполнен не полностью З[I7]=0, то 3-разрядный двоичный код в СЗЧ преобразуется в десятичный и увеличивается на единицу, а затем преобразуется снова в двоичный код, причем если это код «1000», то для его отображения выделяется 4 разряда, а иначе – 3>;ЕСЛИ(И(C9;ДЕС(D6;2)>0;C3;НЕ( ));ОСНОВАНИЕ(ДЕС(D6;2)-1;2;3)<иначе, если сигнал чтения ЧТ[C9]=1 и содержимое СЗЧ[D6]>0 и БУ[C3]=1 и стек не пуст П[I15]=0, то 3-разрядный двоичный код в СЗЧ преобразуется в десятичный и уменьшается на единицу, а затем преобразуется снова в 3-разрядный двоичный код>;D6 <иначе содержимое СЗЧ[D6] сохраняется без изменения>))).

ЯП[G6] (на примере ЯП 0): =ЕСЛИ (D$9;»00000000»<Если сигнал НУ[D9]=1, то ЯП[G6]=00000000>;ЕСЛИ(И(B$9; D$6=F6; C$3);G$4<иначе, если ЗП[B9]=1 и З[I7]=0 и СЗЧ[D6]=адресу ЯП[F6] и БУ[C3]=1, то ЯП[G6]=РСД[G4]>; G6 <иначе содержимое ЯП[G6] сохраняется без изменения>)).

РЧД[G15]: =ЕСЛИ(D9;»00000000»< Если сигнал НУ[D9]=1, то РЧД[G15]=00000000>;ЕСЛИ(И(C9;НЕ(C3);НЕ(I12));ВЫБОР(ДЕС(D6;2)+1;G6;G7;G8;G9;G10;G11;G12;G13)<иначе, если сигнал чтения ЧТ[C9]=1 и БУ[C3]=0 и стек не пуст П[I15]=0, то в РЧД[G15] передается содержимое ЯП, адрес которой указан в СЗЧ[D6] (двоичный код в СЗЧ[D6] преобразуется в десятичный, увеличивается на единицу и используется в качестве порядкового номера соответствующей ячейки Microsoft Excel в функции ВЫБОР)>;G15 <иначе содержимое РЧД[G15] сохраняется без изменения>)).

З[I7]: = ЕСЛИ(ИЛИ(D9;C9);0<Если или сигнал НУ[D9]=1, или ЧТ[С9]=1, то З[I7]=0>; ЕСЛИ(И(B9;НЕ(C3); D6=»1000»); 1<иначе, если ЗП[B9]=1 и БУ[C3]=0 и СЗЧ[D6]=1000, то З[I7]=1>;I7< иначе значение З[I7] сохраняется без изменения>)).

П[I15]: =ЕСЛИ(ИЛИ(D9;B9);0<Если или сигнал НУ[D9]=1, или ЗП[B9]=1, то П[I15]=0>; ЕСЛИ(И(B9;НЕ(C3); D6=»000»); 1<иначе, если ЧТ[C9]=1 и БУ[C3]=0 и СЗЧ[D6]=000, то П[I15]=1>; I15<иначе значение П[I15] сохраняется без изменения>)).

Экспериментальные исследования

Проведению экспериментальных исследований предшествует изменение параметров Microsoft Excel, связанных с вычислением формул: выбираются вычисления в книге «вручную» и включаются итеративные вычисления с предельным числом итераций, равным единице. При заданных настройках каждое нажатие клавиши F9 вызывает пересчет формул Microsoft Excel и моделирование выполнения такта в модели стека. При этом состояние БУ[C3] меняется на противоположное. Для удобства проведения исследований предусмотрена начальная установка устройства, которая осуществляется однократным нажатием клавиши F9 при предварительно установленном значении управляющего сигнала НУ[D9]=1. Начальные состояния регистров, ячеек памяти и признаков приведены в таблице 1 (столбец НУ (Т=0)). Последующие нажатия клавиши F9 не меняют состояние стека, включая и состояние БУ[C3]=0. Начальную установку стека можно выполнить в любой момент проведения исследования. Работа стека исследуется в трех режимах.

Режим хранения. Устанавливаются следующие значения управляющих сигналов: ЗП[B9]=0; ЧТ[C9]=0; НУ[D9]=0. В этом случае нажатие клавиши F9 вызывает изменение только состояния БУ[C3].

Режим записи. Перед исследованием работы стека в поле данных Д[G2] с клавиатуры заносится записываемый 8-разрядный двоичный код, а затем выполняется начальная установка стека (НУ[D9]=1, F9), в результате которой код из поля данных пересылается в РСД[G4]. Если установить управляющий сигнал ВД[I4]=1, то следующее записываемое в стек данное будет формироваться путем увеличения на единицу содержимого РСД[G4]. После начальных установок задаются значения управляющих сигналов: ЗП[B9]=1; ЧТ[C9]=0; НУ[D9]=0. Далее запись в стек выполняется за два такта. После первого нажатия клавиши F9 содержимое РСД[G4] записывается в ЯП, определяемую адресом в СЗЧ[D6], после второго – содержимое СЗЧ[D6] и РСД[G4] (при ВД[I4]=1) увеличивается на единицу. Продолжая нажатия клавиши F9, можно последовательно записывать содержимое РСД[G4] в стек. Причем, если З[I7]=1 (СЗЧ[D6]=«1000», стек полностью заполнен), то процесс записи приостанавливается, а последующие нажатия клавиши F9 вызывают изменение только состояния БУ[C3]. В этом случае работа стека возобновляется при переходе в режим чтения.

Режим чтения. Устанавливаются следующие значения управляющих сигналов: ЗП[B9]=0; ЧТ[C9]=1; НУ[D9]=0. Если выполнению чтения предшествует начальная установка устройства, то после нажатия клавиши F9 формируется сигнал П[I12]=1 (СЗЧ[D6]=«000», пустой стек) и процесс чтения приостанавливается, а последующие нажатия клавиши F9 вызывают изменение только состояния БУ[C3]. В этом случае работа стека возобновляется при переходе в режим записи. Если П[I12]=0 (стек не пуст), то чтение выполняется за два такта. После первого нажатия клавиши F9 содержимое СЗЧ[D6] уменьшается на единицу, после второго – в РЧД[15] считывается содержимое ЯП, адрес которой находится в СЗЧ[D6]. Продолжая нажатия клавиши F9, можно последовательно считывать содержимое ЯП стека в РЧД[15] вплоть до формирования сигнала П[I12]=1 (СЗЧ[D6]=«000», пустой стек).

Заключение

Анализ возможностей применения технологии построения и экспериментального исследования учебных функциональных моделей устройств вычислительных машин, использующей в качестве средства моделирования табличный процессор Microsoft Excel, для создания моделей запоминающих устройств типа стек позволяет сделать следующие выводы. Применение рассматриваемой технологии предполагает решение следующих задач: определение структуры и режима работы моделируемого стека; выбор стандартных функций Microsoft Excel, обеспечивающих реализацию функций стека; разработка экранной формы для экспериментального исследования стека; составление необходимых формул для ячеек Microsoft Excel, выполняющих функции узлов и блоков стека; составления описания процесса проведения экспериментальных исследований. Простота функциональной структуры и алгоритмов работы стека в сочетании с пословным моделированием его узлов и блоков значительно сокращают время, необходимое для разработки и отладки функциональной модели. Самостоятельная разработка и экспериментальное исследование функциональной модели стека позволяют обучающемуся более глубоко изучить данное устройство. Число вариантов заданий обучающимся может быть увеличено путем задания различных типов стека и вариантов его организации.