Programming
System Analysis and Design
System Programming
June 2015 8

Система Оберон, реализованная на доступной FPGA-плате

Original author: Niklaus Wirth
Translation
by Niklaus Wirth
Professor (retired)
Swiss Federal Institute of Technology (ETH)
Zurich, Switzerland

В 1988 году мы с Юргом Гуткнехтом завершили и опубликовали язык программирования Оберон [1, 2], который являлся преемником двух других языков, Паскаля и Модулы-2, разработанных мной ранее. Язык Оберон был спроектирован нами изначально как более рациональный и эффективный, чем Модула-2, что облегчило студентам академической системы образования освоение компьютерной науки. Не останавливаясь на достигнутом, в 1990 году мы построили современную операционную систему (ОС) Оберон для рабочих станций, использующую окна и возможности для обработки текстов. Затем мы опубликовали книгу, раскрывающую детали как компилятора Оберона, так и одноимённой ОС. Книга, названная «Проект Оберон», включала в себя исходные тексты системы.

Несколькими годами позднее мой друг Пол Рид предложил мне издать репринт книги, в силу её значимости для изучения системной архитектуры и дающей хорошую стартовую точку для желающих строить надёжные системы c нуля.

Однако возникло серьёзное препятствие. Оригинальный компилятор был создан для процессора, уже исчезнувшего с рынка. Так что я решил переписать компилятор для современного процессора. Но в ходе небольшого исследования, я так и не смог подобрать процессор, полностью удовлетворяющий моим критериям ясности, правильности и простоты (clarity, regularity and simplicity). Поэтому мне пришлось спроектировать собственный процессор. Эта идея смогла осуществиться благодаря современному чипу ППВМ (программируемая пользователем вентильная матрица, FPGA), позволившему мне создать аппаратное обеспечение точно так же, как создаётся программная система. Более того, выбор Xilinx® FPGA дал мне возможность переделать систему, не отклоняясь сильно от оригинального проекта 1990 года.

Новый RISC-процессор реализован на недорогой плате Digilent Spartan®-3 с одномегабайтным модулем статической (SRAM) памяти. Все мои аппаратные доработки касались интерфейса мыши и SD-карты, заменяющей жёсткий диск в старой системе.

Книга и исходный текст всей системы доступны на сайте projectoberon.com [3,4,5]. Там же доступен отдельный файл S3RISCinstall.zip. Он содержит инструкцию, образ файловой системы для SD-карты и битовые конфигурационные файлы для FPGA (в форме PROM-файлов для флэш-памяти платы Spartan-3), конструктивные части для аппаратного интерфейса SD-карты и мыши.

RISC-процессор

Процессор представлен Verilog-модулем RISC5 и состоит из арифметико-логического устройства (АЛУ), массива из шестнадцати 32-битных регистров и управляющего модуля с регистром инструкций IR и программным счётчиком PC (см. более подробно — прим. перев.).

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

RISC5 импортируется из контекста (environment) RISC5Top, содержащей интерфейсы для различных устройств, отображаемых в память и SRAM (256 МБ х 32 бита). Вся же система (рис. 1)
Рис. 1. Диаграмма системы с Verilog-модулями.

содержит следущие Verilog-модули (показано количество строк каждого модуля):
RISC5Top environment 194
RISC5 processor 201
Multiplier integer arithmetic 47
Divider 24
FPAdder floating-point arithmetic 98
FPMultiplier 33
FPDivider 35
SPI SD card and transmitter/receiver 25
VID 1024 x 768 video controller 73
PS2 keyboard 25
Mouse mouse 95
RS232T RS232 transmitter 23
RS232R RS232 receiver 25

Я отобразил в память чёрно-белый VGA-дисплей так, чтобы он занимал 1024 х 768 х 1 бит на пиксель = 98,304 байта, по существу, 10 процентов от всей доступной памяти в 1 мегабайт. Доступ к SD-карте, заменившей собой 80 мегабайт из оригинальной системы, осуществляется по стандартному интерфейсу SPI, принимающему и сериализующему байты или 32-битные слова. Клавиатура и мышь подключены по стандартному последовательному интерфейсу PS-2. Кроме этого, имеются кабели последовательного асинхронного RS-232 и многоцелевого 8-битного параллельного интерфейса ввода-вывода. Также модуль RISC5Top содержит миллисекундный счётчик.

Операционная система Оберон

В программное обеспечение ОС входит ядро, включающее в себя распределитель памяти (memory allocator) со сборщиком мусора, файловая система вместе с загрузчиком, текстовая система, система просмотра (viewer system) и текстовый редактор.

Модуль под названием «Oberon» является центральным диспетчером задач, а «System» это базовый командный модуль. Действие (action) вызывается кликом средней кнопки мыши на тексте вида «M.P» в любом отображении на дисплее, где P – имя процедуры, объявленной в модуле M. Если M недоступен, он автоматически загружается.
Большинство команд редактирования текста вызываются обычными мышиными кликами, в которых левая кнопка обслуживает каретку, помечающую текущую позицию в тексте, а правая кнопка отвечает за выделение текста.

В модуль «Kernel» входят дисковое хранилище (disk-store management) и сборщик мусора.
Просмотрщики (viewers) располагаются плиткой и не накладываются друг на друга. Стандартная разметка отображает две вертикальных дорожки с неограниченным количеством просмотрщиков. Вы можете увеличивать или уменьшать их, а также перетаскивать за титульную полоску. На рис. 2 показан пользовательский интерфейс на мониторе, подключенному к плате Spartan-3 с клавиатурой и мышью.


Рис. 2. Пользовательский интерфейс на мониторе и Spartan-3 справа внизу.

Загруженная система занимает 112,640 байт в модульном пространстве (21 процент) и 16,128 байт в куче (3 процента). Она состоит из следующих модулей (с числом строк каждого), показанных на рис. 3:
Kernel 271 (inner core)
FileDir 352
Files 505
Modules (loader) 226
Viewers 216 (outer core)
Texts 532
Oberon 411
MenuViewers 208
TextFrames 874
System 420
Edit 233

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

Компилятор Оберона

Компилятор встроен в систему и использует простой метод рекурсивного нисходящего синтаксического разбора. Активация компилятора делается с помощью команды ORP.Compile @. Парсер получает символы от сканера, обрабатывающего идентификаторы, числа и специальные символы (такие, как BEGIN, END, + и другие). Эта схема доказала свою пригодность и элегантность во многих приложениях и описана в моей книге «Compiler Construction»[6,7].

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

Все адреса переменных рассчитываются относительно базового регистра. Это R14 (стековый указатель) для локальных переменных (задаётся при входе в процедуру в рантайме), или R13 для глобальных и импортированных переменных. Базовые адреса загружаются по запросу из глобальной таблицы модулей, чей адрес хранится в регистре R12. Регистр R15 использован для адресов возврата, согласно RISC-архитектуре. Остальные регистры, R0 – R11, доступны для вычисления выражений и передачи процедурных параметров.

Весь компилятор состоит из четырех относительно небольших и эффективных модулей (указано число строк каждого):
ORP parser 968
ORG code generator 1120
ORB base def 435
ORS scanner 311

Компилятор занимает 115,912 байт (22 процента) модульного пространства и 17,508 байт (4 процента) кучи (перед компиляцией). Его исходный код размером около 65 килобайт. Компиляция самого компилятора отнимает всего несколько секунд на 25-МГц RISC-процессоре [8].

Компилятор всегда генерирует проверки для индексов массива и указателей на NIL. Это порождает трапы (trap, ловушка — прим. перев.) в случае нарушения. Такая техника гарантирует высокий уровень защиты от ошибок и повреждений. Фактически, целостность системы может быть нарушена только путём использования таких операций псевдо-модуля SYSTEM, как PUT и COPY. Эти операции должны быть использованы ограниченно, только в модулях драйверов устройств и их легко отыскать по имени SYSTEM в списке импорта. Вся же система запрограммирована на самом Обероне, без использования ассемблерных кодов.

Я выбрал плату Digilent Spartan-3 из-за её ценовой доступности и простоты, что делает её подходящей для образовательных учреждений, приобретающих целые наборы для классов. Большая выгода так же и в присутствии статической RAM на плате, которая позволяет подключаться (interfacing) напрямую (и даже считывать байты). К сожалению, новейшие платы используют динамическую RAM, которая хотя и вместительнее, но более сложна для подключения, требует дополнительные контуры для обновления и инициализации (калибровки). Подобная схемотехника может быть не менее сложной, чем весь процессор со статической RAM. Даже если контроллер поставляется на чипе, он нарушает наш принцип, согласно которому всё должно быть доступно для контроля.

Мысли напоследок

Более 40 лет назад Ч. Хоар отметил, что во всех ответвлениях науки и технологии студенты подвергаются влиянию большого количества примеров серьёзных конструкций до того, как наберут собственный экспериментальный опыт. Программирование и проектирование программ подчёркивают эту парадигму. Студентам приходится писать программы с самого начала, вместо изучения различных образцов.
Причина столь ужасного положения была в том, что почти не существовало литературы с квалифицированными примерами. Поэтому я решил исправить ситуацию и написал книгу «Алгоритмы и структуры данных» в 1975 году. В дальнейшем (вместе с Ю.Гуткнехтом), в рамках преподавания курса операционных систем, я спроектировал систему Оберон (1986—88).
Спустя время, преподавание программирования не получило заметного улучшения в силу того, что системы драматически усложнились и увеличились в размерах. Хотя опенсурс и получил признание, но он не смог изменить ситуацию, поскольку большинство программ создаются лишь бы поскорее их запустить, а не для лучшего понимания их человеком.
Я продолжаю делать смелые предположения о том, что все программы должны быть созданы не только для компьютера, но и для понимания человеком. Они должны быть доступны. Это задача гораздо сложнее, чем создание исполняющихся программ, даже если они корректны и эффективны. Это подразумевает, что не должно быть ассемблерных вставок.

Результат игнорирования человеческого фактора приводит к тому, что повсюду возникают не очень тщательно спроектированные приложения, доводимые до рабочего состояния отладкой, иногда с мрачными последствиями. Для достижения понимаемости стоит придерживаться простоты и порядка, отказываясь от ненужных украшений и, избегая колокольчиков со свистками, различать общепринятость и пригодность (conventional and convenient).

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

И наконец, преимущество краткости ещё и в том, что можно безопасно надстраивать такую систему, не опасаясь неизвестных возможностей, таких как бэкдоры (back doors). Это существенное свойство, очень важное для систем, критичных к вопросам безопасности, если учесть увеличивающуюся опасность атак на целостность систем. Не менее важно, что и аппаратная часть нашей системы не содержит никаких скрытых частей. Никто не сможет дать гарантий для систем, построенных на фундаменте, недоступном для понимания во всей полноте.

Благодарность

Я очень признателен Полу Риду за его неоценимый вклад. Он предложил мне отредактировать книгу «Проект Оберон» и также предложил заново реализовать всю систему на FPGA. Пол был неиссякающим источником ободрения. Заменить диск на SD-карту была его идея и он же предоставил SPI, PS-2 и VID Verilog-интерфейсы.

Ссылки

1. www.inf.ethz.ch/personal/wirth/Oberon/Oberon07.Report.pdf
2. www.inf.ethz.ch/personal/wirth/Oberon/PIO.pdf
3. www.inf.ethz.ch/personal/wirth/ProjectOberon/index.html
4. www.inf.ethz.ch/personal/wirth/Oberon/PIO.pdf
5. www.inf.ethz.ch/personal/wirth/Oberon/Oberon07.Report.pdf
6. www.inf.ethz.ch/personal/wirth/CompilerConstruction/CompilerConstruction1.pdf
7. www.inf.ethz.ch/personal/wirth/CompilerConstruction/CompilerConstruction2.pdf
8. www.inf.ethz.ch/personal/wirth/ProjectOberon/PO.Applications.pdf (Ch. 12)

Приложение

Язык Лола и его трансляция в Verilog



Язык описания аппаратуры (hardware-description language, HDL), названный Лола, был определён в 1990 году в целях преподавания основ проектирования аппаратного обеспечения. Это было время, когда текстовые определения начинали заменять принципиальные электрические схемы и тогда же становились доступны первые FPGA, хотя и не достигшие ещё промышленного уровня. Для Лолы был создан компилятор, генерирующий битовые файлы, пригодные для загрузки в FPGA. Форматы битовых файлов раскрыты фирмами Algotronix, Inc. и Concurrent Logic Inc. Оба формата позволяли работать с ячейками довольно простых структур, оптимальных для автоматической разводки.

По итогам моего проекта переделки Оберона для FPGA, возникла идея возродить также и Лолу. Поскольку ячейки Xilinx FPGA являются более сложными, то мы не рискнули предпринять усилия по реализации размещения и разводки, независимо от того, что Xilinx отказалась открыть свой запатентованный формат бит-файла.

Очевидным решением было построить такой компилятор Лолы, который не будет генерировать патентованные бит-файлы, но позволит транслировать в язык, для которого Xilinx предоставляет специальный инструмент. Мы выбрали Verilog. Это решение подразумевало несколько экстравагантный обходной путь: во-первых, модуль Лолы должен быть распарсен (parsed), затем оттранслирован, и в итоге распарсен снова. На всех этих этапах мы должны гарантировать, что компилятор Лолы имеет надлежащий контроль ошибок и возможности проверки типов.

Чтобы подтолкнуть разработку Лолы-2, нам потребовалось переформулировать на Лолу все модули RISC5-процессора. Что и было сделано.

Язык Лола

Лола является маленьким, немногословным языком в стиле Оберона (см. www.inf.ethz.ch/personal/wirth/Lola/Lola2.pdf). Для краткости, мы покажем здесь только один пример текста на Лоле (рис. 1). Единица исходного текста называется модуль. Его заголовок определяет имя модуля, имена и типы входных и выходных параметров. После заголовка следует секция объявлений локальных объектов, таких как переменные и регистры. Далее располагается секция определения значений переменных и регистров. BYTE задаёт массив из 8 бит.

MODULE Counter0 (IN CLK50M, rstIn: BIT;
	IN swi: BYTE; OUT leds: BYTE);

TYPE IBUFG := MODULE (IN I: BIT; OUT O: BIT) ^;
VAR clk, tick0, tick1: BIT;
	clkInBuf: IBUFG;
	REG (clk) rst: BIT;
	cnt0: [16] BIT; (*half milliseconds*)
	cnt1: [10] BIT; (*half seconds*)
	cnt2: BYTE;

BEGIN leds := swi.7 -> swi : swi.0 -> cnt1[9:2] : cnt2;
	tick0 := (cnt0 = 49999);
	tick1 := tick0 & (cnt1 = 499);
	rst := ~rstIn;
	cnt0 := ~rst -> 0 : tick0 -> 0 : cnt0 + 1;
	cnt1 := ~rst -> 0 : tick1 -> 0 : cnt1 + tick0;
	cnt2 := ~rst -> 0 : cnt2 + tick1;
	clkInBuf (CLK50M, clk)
END Counter0.

Рис. 1. Исходный текст на Лоле показывает счётчик секунд и миллисекунд, отображаемых на индикаторах платы.

Компилятор Лолы

Компилятор использует простой метод рекурсивного нисходящего синтаксического разбора. Он активируется на выбранном исходном тексте Лолы командой LSC.Compile @. Парсер получает символы от сканера, обрабатывающего идентификаторы, числа и специальные символы (такие, как BEGIN, END, + и другие). Эта схема доказала свою пригодность и элегантность во многих приложениях и описана в книге «Compiler Construction (Part 1 и 2)».

Вместо генерирования текстов Verilog прямо на лету, парсер сначала создаёт дерево операторов, что более подходит для дальнейшей обработки. Такой подход имеет преимущество в том, что любой требуемый вывод может быть легко сгенерирован подходящим транслятором. Один из таких — транслятор в Verilog. Первая команда LSV.List outputfile.v. Другая команда может транслировать в VHDL или просто вывести дерево. Третья может сгенерировать список соединений (netlist) для дальнейшей обработки разводчиком.

Таким образом, весь компилятор состоит не менее чем из четырёх относительно небольших и эффективных модулей:
LSS scanner 159
LSB base 52
LSC compiler/parser 503
LSV Verilog generator 215

Инструкции по транлсяции из Лолы в Verilog можно найти здесь: www.inf.ethz.ch/personal/wirth/Lola/LolaCompiler.pdf.

Различия между программными и аппаратными «программами»

В прошлом предпринималось множество усилий для того, чтобы заставить языки HDL выглядеть как «обычные» языки программирования. Кроме этого, HDL имеют «двойников» среди других ЯП, адаптируясь к их стилю. Например, Verilog произошёл от Си, VHDL от Ады и Лола от Оберона. Но мы считаем, что важно видеть фундаментальные отличия между двумя этими классами, в частности, в присутствии синтаксических сходств, или даже идентичностей. Что же это за фундаментальные отличия?

Чтобы упростить объяснение, мы ограничим наш анализ синхронными схемами — то есть, такими, в которых все регистры привязаны к одному тактовому генератору. В общем-то, синхронные схемы суть неплохая архитектурная парадигма, которой стоит придерживаться, по возможности.

Далее, совершенно очевидно, что все элементы схемы работают одновременно, буквально в одно и то же время. Каждая переменная и каждый регистр определяются одним и только одним выражением (комбинационная схема). Множественные присвоения не имеют смысла. Каждую HDL-программу мы можем легко представить заключённой в большой бесконечный цикл, поскольку присвоения регистрам и переменным происходят в каждый такт.

Идея Джона фон Неймана представить процессорную архитектуру на базе секвенсора (sequencer) была гениальной. Секвенсор содержит регистр инструкций, согласно которым в каждом такте выбираются определённые схемы и игнорируются остальные, что приводит к умелому повторному использованию различных частей АЛУ. Такты или шаги по своей природе последовательные, стало быть, возможно переприсвоить значения переменным согласно тому, как программный счётчик соотносит их с определёнными местами в программе и в последовательности инструкций. Идея секвенсора сделала возможной выполнение огромнейших программ на относительно простых схемах.

Итак, Лола-2 это HDL в стиле ЯП Оберон. Представленный здесь компилятор транслирует модули Лолы в Verilog-модули. Преимущества Лолы как в простой и привычной структуре языка, так и в акцентировании компилятора на проверку типов и усовершенствованной диагностике ошибок. Полный набор модулей для RISC-процессора, описанных на Лоле: www.inf.ethz.ch/personal/wirth/Lola/index.html

+19
13.2k 69
Comments 20
Top of the day