Beware of the Turing tar-pit in
which everything is possible
 but nothing of interest is easy.
Alan J. Perlis

В 1936 году, за семь лет до создания первого в мире электронного компьютера общего назначения, и за 22 года до изобретения интегральной схемы, перевернувшей весь мир цифровых вычислений, английский математик Алан Тьюринг предложил концепцию абстрактного исполнителя, который впоследствии был назван в честь своего автора – машина Тьюринга. Эта гипотетическая модель обладает удивительным свойством – любое вычисление, которое может быть описано при помощи машины Тьюринга, может быть реализовано физически, в виде некоего исполнительного устройства.

Существует несколько вариантов описания машины Тьюринга, однако основной считается модель с конечным управлением, ограниченной с одной стороны и бесконечной с другой лентой, разделённой на ячейки, и управляющим устройством-головкой, способным за один шаг заданным образом обрабатывать одну ячейку на ленте. В каждой ячейке может храниться только один символ, определённый конечным алфавитом, или "пустой" символ, причём изначально в некотором количестве ячеек хранится входная цепочка символов, задающая начальное поведение машины.

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

"Машина Тьюринга в представлении художника.

Таким образом, машина Тьюринга – это абстрактное устройство, представляющее собой простейший вычислитель с памятью, имеющей линейную организацию. Данные в памяти преобразуются посредством элементарных действий, последовательность которых задаётся правилами перехода, причём число возможных действий конечно. Становится очевидно, что на машине Тьюринга можно реализовать любую алгоритмическую разрешимую функцию, множество которых называется вычислимым, причём из последнего вытекает определение полноты по Тьюрингу. Проще говоря, тьюринг-полным называется исполнитель, если на нём можно реализовать любую вычислимую функцию.

Я не буду погружаться в теорию – в контексте математической науки данная тема неисчерпаема. Между тем, я не зря начал с абстрактных определений, ведь ниже речь пойдёт об одном из наиболее известных эзотерических языков программирования, по своему устройству имитирующему самую настоящую машину Тьюринга. Речь идёт о языке с нецензурным названием – Brainfuck.

Пришло мне в голову реализовать игру «жизнь» в ПЛИС в плате Марсоход2.
Не знаю, стоит ли объяснять правила этой игры — они, кажется, общеизвестны. Очень хорошее описание есть в википедии.

Ну, ладно, вкратце повторюсь:

• есть прямоугольная решетка, в каждой ячейке решетки может жить «микроорганизм», клетка. Есть два состояния клетки решетки — «живая» или «не живая»;
• каждая клетка имеет восемь возможных соседей. Даже на краях решетки у клеток есть 8  соседей. Решетка рассматривается как «бесконечная плоскость»: нижний край соединен без шва с верхним, а правый край с левым. Такая поверхность называется «тор». По тору-бублику можно ходить бесконечно, в любом направлении, не встречая препятствия;
• если живых соседей меньше двух, то клетка умирает от одиночества;
• если живых соседей больше трех, то клетка умирает от перенаселения;
• если у клетки живых соседей ровно три, то в клетке зарождается новая жизнь;
• если у клетки два живых соседа — ее жизнь продолжается;
• в начале игры пространство как-то заполняется живыми клетками — на каждом шаге в каждой клетке происходит таинство жизни — где-то кто-то рождается, а где-то кто-то и умирает. Ну а зритель просто наблюдает за эти процессом.

Эта модель жизни получила название «клеточный автомат».
Программных реализаций для клеточного автомата существует огромное множество. Игру «жизнь» наверное уже написали на всех возможных языках программирования: C/C++, Javascript, Python, Pascal..

Я решил написать клеточный автомат игры «жизнь» для ПЛИС на Verilog HDL.
Меня заинтересовала эта игра тем, что в некотором роде на этой модели я могу попытаться реализовать эдакий «суперпроцессор». Это как раз задача для ПЛИС.

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

Первое сентября традиционно ассоциируется с началом учебного года и возвращением в отдохнувшее за время летних каникул здание школы или иного учебного заведения за новыми знаниями. Как человек, давно закончивший школу, и по случайному стечению обстоятельств студент-заочник, волнующих переживаний в связи с началом календарной осени я не испытываю. Тем не менее, я тоже решил заняться изучением чего-нибудь нового, интересного и полезного. Тема была выбрана не самая простая – проектирование цифровых устройств, ПЛИС и языки описания аппаратуры (в частности, VHDL).

Интересно, что многие материалы по проектированию для ПЛИС, понятные абсолютному новичку вроде меня и доступные в русскоязычном сегменте интернета, связаны с проектом Марсоход, который развивается силами небольшой команды инженеров из Таганрога. Марсоход это не просто плата-конструктор и её старший и более серьёзный родственник в лице второй модели. Это сообщество, в котором найдётся место и опытным профессионалам, и "чайникам", только начавшим постигать все тонкости искусства проектирования цифровых схем.

Наверное, поэтому я захотел поделиться своим опытом изучения ПЛИС с аудиторией блога Марсоход. С программируемой логикой ранее мне сталкиваться не приходилось, а идея познакомиться с ПЛИС поближе возникла после изучения курса схемотехники – появилось желание почувствовать процесс разработки изнутри, а отсутствие практических навыков заставляет действовать именно в таком формате. Свои заметки – эту, и, надеюсь, будущие – я бы хотел представлять в виде "докладов" и "лабораторных работ", нарочно уделяя повышенное внимание возможно очевидным аспектам затронутой темы. Разумеется, любое описываемое устройство будет протестировано в плате Марсоход2, а соответствующие проекты для Quartus II будут доступны для загрузки.

Мне очень нравится проект Марсоход – это сообщество замечательных людей, увлеченных интересной темой. Оно состоит как из опытных разработчиков на ПЛИС, так и из начинающих, как профессиональных разработчиков, так и любителей. Кто-то шел по тернистому пути освоения программируемой логики сам, кого-то вели преподаватели в ВУЗе. Сам я отношусь ко второй категории, и считаю, что мне повезло: обучали меня схемотехнике и, в частности, ПЛИСам на кафедре автоматики и вычислительной техники (ныне компьютерных систем и программных технологий) Санкт-Петербургского Политеха, на базе которой создан официальный центр обучения Altera в России.

Не знаю, сознательно или нет, на сайте https://marsohod.org не затронута тема синтезируемого процессора Altera Nios II. Пробежавшись по темам на сайте, не обнаружил ни одного проекта на Nios II, зато нашел целую ветку, посвященную процессору Amber ARM. Считаю, что Nios незаслуженно обошли вниманием. Бытует мнение, что процессор Nios утратил свою актуальность, что в реальных проектах его никто не использует, что с появлением Altera SoC FPGA с аппаратным процессором ARM Nios исчезнет за ненадобностью и т.д. Сразу скажу, что слухи о его смерти несколько преувеличены, более того, недавно вышла новая ревизия процессора Nios II Gen 2, которая и будет развиваться, начиная с версии 14.0, однако в данном тексте речь пойдет исключительно о Nios II Gen 1.