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

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

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

Кількома роками пізніше мій друг Пол Рід запропонував мені видати репринт книги, в силу її значимості для вивчення системної архітектури і дає хорошу стартову точку для бажаючих будувати надійні системи з нуля.

Однак виникло серйозне перешкода. Оригінальний компілятор був створений для процесора, вже зник з ринку. Так що я вирішив переписати компілятор для сучасного процесора. Але в ході невеликого дослідження, я так і не зміг підібрати процесор, який повністю задовольняє моїм критеріям ясності, правильності і простоти (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 із-за її цінової доступності і простоти, що робить її придатною для освітніх установ, що купують цілі набори для класів. Велика вигода так само і в присутності статичної ПАМ'ЯТІ на платі, яка дозволяє підключатися (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 пропустити, результати.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

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.