Кремниевая компиляция.

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

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

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

Модель вычислений - общее, крайне абстрактное описание того, что может наш вычислитель. Грубого говоря, для фон-Неймановского процессора это сводится к работе пересылке данных между памятью, регистрами и портами ввода/вывода, обработкой данный в АЛУ (и тут не важно какие команды), видами адресации и последовательным принципом выполнения команд с jmp. Другими слова МВ - набор базовых правил, по которым работает система.

Вычислитель - коробка (или программа), которая реализует МВ и позволяет выполнять на себе программу.

Семантический разрыв - разница между моделями вычислений. В чём её мерить сказать крайне трудно, но интуитивно это довольно понятно. К примеру, программа на СИ легко транслируется в машинный код, в то время как программу на Java значительно сложнее (я бы даже осказал что не транслируется совсем. Да, я знаю про jit и ниже упомяну почему занимаю такую позицию). Пример из другой области: семантическая разница между градусами Кельвина и Цельсия меньше, чем между градусами Кельвина и Фаренгейта (в первом случае зависимость линейна, во втором нет). Таким образом, интуитивное понимание понятия семантического разрыва сводится к тому, что чем сложнее нам перевести что-либо из одного представления в другое, тем больше семантический разрыв между этими представлениями.

Как было сказано выше, существующие методы преодоления семантических разрывов довольно плачевны, причём это даже не имеет прямой зависимости от области применений. Хорошо сопоставляются между собой только те вещи, между которыми семантический разрыв минимален, в остальных же случаях он позволяет получать довольно посредственные результаты. Наиболее ярким примером может являться системы автоматического перевода. Возвращаясь к вычислительной технике, можно выделить основные пути решения проблемы семантического разрыва, удачные и не очень (исключая непосредственный перевод).

1. Расширение МВ вычислителя. Идея очень проста и полностью аналогична идеи Магомета подойти к горе. Если мы не можем преобразовать код под конкретный вычислитель, можно преобразовать вычислитель под конкретный код. Этого можно добиться путём реализации расширения для вычислителя, наиболее яркими примерами которых являются виртуальные машины (на пример Java, которая всегда имеет свой run-time, и как следствие, никогда полностью не транслируется). Возможны и аппаратные расширения
2. Абстрактная МВ. Основной идеей данного подхода является то, что бы ввести в инструментальную цепочку промежуточный язык, который построен таким образом, что бы не завязывать систему на конкретную платформу для реализации и при этом покрывать все возможные решения. К сожалению, этот подход довольно проблематичен, так как подобную МВ крайне сложно определить таким образом, что бы она оказывала минимальное влияние на программу, то есть: не добавляла в код новых ограничений, не добавляла ему новых свойств, не затачивала под конкретный вычислитель (класс вычислителей) или язык разработки. В качестве одного из наиболее удачных примеров использования этого подхода можно назвать LLVM (на сколько мне известно, есть попытки прикрутить к нему синтез HDL).
3. Выскоуровневое проектирование. Идея подхода заключается в том, что бы сделать некоторое гетерогенное (разнородное), иерархическое описание вычислительной системы, где на разных уровнях используются различные МВ, что позволяет с одной стороны решать проблемы наиболее оптимальным образом и с другой стороны, при использование "базовых" МВ, относительно легко реализовывать трансляторы кода как в программный код, так и в аппаратуру. Подробнее об этих идеях можно почитать в документациях к проекту ptolemy или в моей бакалаврской.

Возвращаясь к вопросу о кремневой компиляции, зачем нам это надо? Основных причин две:

1. Портировать существующий код в аппаратуру.
2. Работать с более высокоуровневым кодом, нежели позволяют HDL языки, и тем самым понизить стоимость разработки.

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

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

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

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

Правда, тут есть и целый ряд ложек дёгтя:

• МВ довольно необычна, и к ней придётся довольно долго привыкать.
• МВ не является моделью вычислений общего назначения (такая как в СИ), а значит, некоторые вещи прийдётся решать на ней не типичным способом или опускать на уровень аппаратуры.

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

PS Проект в текущий момент является закрытым, но постепенно, с появлением в нём завёршённых этапов, он будет открываться.

Литуратурная аппаратура на VHDL

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

Сперва о инструментарии, который мною использовался. Это была реализация системы литературного программирования noweb, которая не привязана ни к какому языку программирования (что оказалось крайне приятным, так как VHDL специально никто ничего подобного не делал). В качестве редактора использовался emacs + noweb.el. Текстовая часть кода оформлялась в LaTeX (тут была альтернатива в качестве html). В принципе, эти инструменты позволили с комфортом работать над задачей, после некоторой привычки. К сожалению, noweb.el является достаточно кривой реализацией, с некоторым количеством неприятных моментов (часто слетает подсветка синтаксиса).

Русская вики даёт следующее определение для литературного программирования:

Литературное (английский термин намеренно двусмысленный), или грамотное программирование (англ. Literate Programming) — концепция, методология программирования и документирования. Термин и саму концепцию разработал Дональд Кнут в 1981 году при разработке системы компьютерной вёрстки TeX.

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

Не знаю как все, но лично я, как правило, перед тем как решать какую-то задачу, в случае если она не совсем тривиальна, или по тем или иным причинам для меня не обычна, я сперва беру блокнот с ручкой, и пишу свои рассуждения о ней на бумаге. А затем, поглядывая в записи, пишу код. Само собой, никакого желания ни документировать, ни писать комментарии после этого как правила нет. В случае же использования литературного программирования, этот текст пишется в текстовом редакторе. Причём, не имеет никакого значения, как именно должен быть записан код, текст пишется именно так, как он думается, как он придумывается. Вот формулируется мысль о каком-то конкретном аспекте поведения, и прямо тут же, вы пишете:

<<фича такая-то>>=

Код этой фичи, абсолютно выдранный из контекста.

@

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

<<имя_файла>>=

Заголовок такой-то
<<контескт такой-то фичи>>

<<фича такая-то>>

<<фича такая-то>>

<<фича такая-то>>

Ещё какой-то код, необходимый тут.

@

Теперь, мы можем двумя простыми командами получить как статью, в которой довольно неплохо описано, что делает программа (noweave -delay programm.nw > text.tex) и собственно сам код программы (notangle -Rимя_файла programm.nwп > имя_файла). Так как вы нормальный человек, а следовательно не достаточно внимательны, команда для кода скорее всего любезно скажет вам, какие аспекты программы вы забыли, и вы будете вынуждены, добавить пару абзацев текста.

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

Примерно так выглядит разработка в литературном стиле у меня. Сейчас попробую тезисами привести преимущества и недостатки данного стиля (подчёркиваю, я его крайне мало практиковал и только для малых задачей, так что это не более чем размышления).

Преимущества:

- Вы пишите код к той форме и в том порядке, в котором вы думаете. Соответственно он намного проще проверяется, намного проще восстанавливается в голове, так как в нём все его детали всегда явно присутствуют и вводятся последовательно.

- Наличие такой детальной документации в коде, позволяет в нём разобраться любому человеку, и для этого не обязательно знать язык разработки.

Недостатки:

- Не понятно как это можно применять для динамических языков, таких как Smalltalk и Lisp.

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

- Не совсем понятно, как такой стиль может применяться в коллективе, так как все думают по разному.

- (самый существенный, также его отмечает Кнут) Мало уметь программировать, надо уметь и писать. 

Непонятные моменты:
- Время написания программы значительно выше, нежели в случае традиционного подхода, но в тоже время количество ошибок меньше. Сложные ошибки исправлять проше, а простые труднее.

Не смотря на то, что численно недостатков больше, первое преимущество их может переплюнуть с лёгкостью. Теперь, вероятно, буду стараться использовать этот подход как можно чаще.

http://dl.dropbox.com/u/1619524/src/literate_lab1.zip.

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

5 + 1 главных особенностей, которые необходимо знать о конструкторах в Scala

Вольный перевод данного поста: Top 5 Things to Know About Constructors in Scala и плюс ещё одна особенность, на которую волей случая наткнулся.

Я играюсь со Scala в течение нескольких месяцев, и одной из вещей, с котороми пришлось бороться после перехода с Java были конструкторы. Они похожи на конструкторы в Java, но синтаксис имеет отличия.
Что бы помочь вам быстрее начать пользоваться Scala, приведу пять основных особенностей связанных с конструкторами. Начнём:

1. Как сделать конструктор с параметром?

public class Foo() { public Bar bar; public Foo(Bar bar) {  this.bar = bar;  } }

На Scala это будет выглядеть так:

class Foo(val bar:Bar)

В данном случае val создаёт неизменяемое публичное поле, используте var для создание изменяемых полей.

2. Как сделать приватные поля?

public class Foo() { private final Bar bar; public Foo(Bar bar) { this.bar = bar; } }

На Scala это будет выглядеть так:

class Foo(private val bar: Bar)

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

3. Как использовать super()?

public class Foo() extends SuperFoo { public Foo(Bar bar) { super(bar); } }

На Scala это будет выглядеть так:

class Foo(bar:Bar) extends SuperFoo(bar)b

4. Как создать более одного конструктора?

public class Foo { public Bar bar; public Foo() { this(new Bar()); } public Foo(Bar bar) { this. bar = bar; } }

На Scala это будет выглядеть так:

class Foo(val bar:Bar) { def this() = this(new Bar) } Второй конструктор (this()) делегирует свои обязанности другому конструктору.

5. Как сделать "bean style" геттер и сеттер?

public class Foo() { private Bar bar; public Foo(Bar bar) { this.bar = bar; } public Bar getBar() { return bar; } public void setBar(Bar bar) { this.bar = bar; } } На Scala это будет выглядеть так:

class Foo(@BeanProperty var bar:Bar) Поле bar является публичным, что не представляет проблем в Scala (смотри выше).

(далее от переводчика)
6. Как сделать конструктор c несколькими выражений?
Данный пункт отмечен в примечание к посту, но я покажу его подробнее.

public class Foo() {
  private Int b; 
  private Int y; 
  public Foo(Int b) { 
    this.b = b; 
  } 
  public Foo() { 
    this.y = java.util.Random.nextInt();
    this.y += 1;
    this.b = b; 
  } 
}

На Scala это будет выглядеть так:

class Foo (val b:Int) {
  var y = 0
  def this() = {
    this(3)
    y = scala.util.Random.nextInt
    y += 1
  }
}

Язык Scala накладывает ограничение на метод this(): "- первым вызовом конструктора должен быть вызов другого конструктора, причем любого - важно только чтобы цепочка вызовов конструкторов в итоге привела к вызову первичного конструктора"

Спасибо javverwocky, за указание на ошибку и пример.

Модель простейшего процессора на Haskell

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

Описание процессора:

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

Основные характеристики:

Разрядность процессора: 8 бит. 

Организация памяти: гарвардская, с отдельными блоками памяти для команд и данных. 

Подсистема обработки прерываний и команды вызова подпрограмм отсутствует. 

Внешние устройства (для данной работы это светодиоды, двухпозиционные переключатели и тактовые кнопки) отображаются в адресное пространство данных. Работа с ними выполняется по опросу. 

Команды выполняются за 2 или 3 такта (в зависимости от типа команды): 1) Выборка команды 2) Выборка операндов 3) Выполнение команды. 

Регистры:

PC — счетчик команд

IR — регистр инструкций

AR — регистр адреса операнда

C — флаг переноса/заёма

Z — флаг нуля

Описание системы команд можно найти в файле Cmd.hs, функция cmd. Функциональность описана в комментариях с использование C синтаксиса. pmem и dmem - память программ и данных соответственно. arg - аргумент команды.

Модель.

Модель создавалась с учётом того, что бы в случае необходимости её можно было относительно легко перетащить в Verilog, а значит вариант с наивным case по командам отпадал вроде такого:

command 0x01 state = someFunctiom1 state

command 0x02 state = someFunctiom2 state

или в без точечном стиле (в основном будет использовать именно он):

command 0x01 = someFunctiom1

command 0x02 = someFunctiom2

Не подходит, так как в данном случае пришлось бы переписывать весь код полностью. Разбираясь с принципами работы процесса, довольно быстро становится очевидно, что наиболее простой способ описания работы команд - потактово задать функции, определяющие изменения состояния процессора после каждого из них. Функции на каждый такт можно получить при помощи композиции нескольких простейших функций, которые были бы в реальном процессоре представлены управляющими сигналами (назовём их микрокомандами, хотя ими они и не являются). К примеру, первый такт программы представляет из себя выборку команд, который может быть описан через композицию сигнала для инкриминирования регистра PC и чтения команды в регистр IR. В моделе это выглядит так:

nextCommand = incPC . pmem2IR

К сожалению, модель вычислений языка Haskell довольно сильно отличается от модели SDF, которая присутствует в Verilog (или отчасти присутствует), и мы вынуждены следить за соблюдением правильной последовательности операций при композиции функций. Использую этот подход, вся система команд может быть описана в одной таблице следующим образом:
cmd = [(0x01, Nop, NoneArg, [nop]), -- nope
       (0x00, Hlt, NoneArg, [hlt]), -- halt model
       (0x02, Ldm, DmemArg, [incPC . pmem2AR, dmem2acc]), -- acc = dmem[arg]; c = const; z = (dmem[arg] == 0)
       (0x03, Ldi, ValueArg, [incPC . pmem2acc]), -- acc = arg; c = const; z = (arg == 0)
...
В данном случае важен только первый (код команды) и последний (поведение) элемент кортежа (остальные необходимы для компилятора). Поведение команды задаётся списком функций, каждая из которых выполняется за такт. Значительная часть функций задаётся композицией микрокоманд которые имеют тип (State -> State).

Таким образом, описание микропроцессора сводится к определению: 

• типа данных State - хранит состояние процессора в текущий момент; 
• таблицы cmd, в которой описываются все команды; 
• микрокоманды, путём композиции которых получаются собственно сами команды; 

Само моделирование производится следующим небольшим кусочком кода:

step (State {on = False}) = return ()

step state = step $ executeCommand state' commandFlow

    where 

      state'@(State{ir = hexCommand}) = nextCommand state

      commandFlow = commandFlowFromInfo $ getCommandInfo hexCommand

      executeCommand state [] = state

     executeCommand state (f:fs) = executeCommand (f state) fs

В нём происходит следующее, производится выборка команды (PC инкриминируется), из таблицы cmd выбираются команды, список функций команд по очереди применяется к текущему состоянию и далее по рекурсии. 

Явные недочёты: 

• Внешние устройства "зашиты" в структуру модели. По хорошему их необходимо вынести из модели, и обрабатывать в step. (тут же использование Trace, для функциональности). 
• Использование неправильных структур данных (в частности для cmd). 
• В модуле отвечающем за моделирование захардкодено всё, что только можно. 

В ближайшее время будет описан разработанный в параллель компилятор, тогда же и будет полный код и продемонстрирована его работоспособность. 

Cmd.hs - http://gist.github.com/492325

SimpleRiscModel - http://gist.github.com/492327