?

Log in

No account? Create an account

Как бы рабочее, как бы программистское - Общество дровосеков Бердичева по изучению Мишны

Jan. 6th, 2012

01:09 pm - Как бы рабочее, как бы программистское

Previous Entry Share Next Entry



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

Дан блок кода, состоящий из 4-х операторов присваивания:

X = A;
X <= B;
X <= X + 1;
X = D;

где "=" - обычное присваивание, а "<=" - "необычное". Известно, что после завершения выполнения этого блока значение X равно A+1. Что можно сказать о семантике "необычного" присваивания?

Comments:

[User Picture]
From:yakov_sirotkin
Date:January 6th, 2012 09:20 pm (UTC)
(Link)
Обычное присваивание меняет внутреннее состояние X, а необычное - внешнее?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 6th, 2012 09:26 pm (UTC)
(Link)
Что такое "внешнее состояние"?
(Reply) (Parent) (Thread)
[User Picture]
From:yakov_sirotkin
Date:January 7th, 2012 05:37 am (UTC)
(Link)
Не суть важно, как назвать, очевидно, что у меня не было шансов угадать правильный термин. Главное, что полное состояние X описывается не одним, а двумя значениями.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:January 7th, 2012 08:34 am (UTC)
(Link)
Ну да, я просто ждал более очевидного "текущее" и "следующее".
(Reply) (Parent) (Thread)
[User Picture]
From:yakov_sirotkin
Date:January 7th, 2012 09:35 am (UTC)
(Link)
Есть ощущение, что надо довольно долго мозги затачивать, чтобы эта версия стала более очевидной:)

То есть, возвращаясь к началу поста, на интервью пальцы погнуть можно, но совсем быстро - не получиться.
(Reply) (Parent) (Thread)
[User Picture]
From:leonidph1972
Date:January 6th, 2012 09:26 pm (UTC)
(Link)
необычное присваивание работает с пайпланом
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 6th, 2012 09:28 pm (UTC)
(Link)
Т.е. как именно?
(Reply) (Parent) (Thread)
[User Picture]
From:leonidph1972
Date:January 7th, 2012 01:48 pm (UTC)
(Link)
Выполнение команды размазывается на несколько клоков
то что вы видете как X <= X + 1
реально 2 команды (как минимум)- сделать инкремент и занести результат.
мне сложно тут рисовть таблицу но так это работает
(Reply) (Parent) (Thread)
[User Picture]
From:excubitus
Date:January 6th, 2012 09:31 pm (UTC)
(Link)
Лень искать, но есть подозрение, что это какое-то отложенное присваивание, выполняющееся только после выхода из блока. X, небось, связан с каким-нибудь индикатором, который должен красиво мигнуть при переходе от А к А+1.
(Reply) (Thread)
[User Picture]
From:iime
Date:January 6th, 2012 09:36 pm (UTC)
(Link)
Это было бы нечестно)
(Reply) (Parent) (Thread)
[User Picture]
From:excubitus
Date:January 6th, 2012 09:38 pm (UTC)
(Link)
Ну, если бы мне на интервью дали такой тест, я бы поискал непременно. :)
(Reply) (Parent) (Thread)
[User Picture]
From:iime
Date:January 6th, 2012 09:39 pm (UTC)
(Link)
Я не про "искать", а про "только после выхода из блока.")
(Reply) (Parent) (Thread)
[User Picture]
From:excubitus
Date:January 6th, 2012 09:40 pm (UTC)
(Link)
Что ж в этом нечестного?
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:January 6th, 2012 09:41 pm (UTC)
(Link)
Языки описания хардвера - такие затейники!
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:January 6th, 2012 09:40 pm (UTC)
(Link)
Сидя перед интервьюером, говорить "ща погуглю" и зарыться в смартфон?
(Reply) (Parent) (Thread)
[User Picture]
From:excubitus
Date:January 6th, 2012 09:43 pm (UTC)
(Link)
Типа того. Понимаю, что не со всеми прокатит. :)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:January 6th, 2012 09:37 pm (UTC)
(Link)
Идея в том, чтобы понять без поиска. "Отложенное присваивание" - правильный для данного примера ответ. Этот пример чисто искусственный, а в реальной жизни такое присваивание позволяет, например, записывать обмен значениями между двумя переменными любого типа без привлечения третьей:

X <= Y;
Y <= X;

(Reply) (Parent) (Thread)
[User Picture]
From:excubitus
Date:January 6th, 2012 09:39 pm (UTC)
(Link)
Красиво.
(Reply) (Parent) (Thread)
[User Picture]
From:iime
Date:January 6th, 2012 09:53 pm (UTC)
(Link)
А 'X = D' выполняется перед выполнением отложенных присваиваний и поэтому на результат не влияет?
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:January 6th, 2012 10:08 pm (UTC)
(Link)
Ну да.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:January 6th, 2012 10:05 pm (UTC)
(Link)
1) А что, явно границы такта в Верилоге не указываются?

2) Тогда я не понимаю, как может работать просто "=". "<=" подразумевает регистры, содержащие триггеры (flip-flops) с двухступенчатой синхронизацией. Т.е. если мы пишем

X <= Y
Y <= X

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

3) Все равно непонятно, почему результатом будет A+1, а не какая-то каша и не D.

4) При таком раскладе именно "<=" - обычное присваивание, а "=" - необычное.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:January 6th, 2012 10:19 pm (UTC)
(Link)
1) На верилоге можно писать и как на обычном языке программирования, без времянок. Семантика определяется в терминах очередей событий и списков чувствительности.

2) Это уже мышление в терминах register transfer logic, а язык позволяет и более абстрактный behavioral level, на котором можно написать и синтезируемую логику в процедурном стиле, и совершенно несинтезируемые конструкции.

3) Потому что блок выше, согласно современному стандарту языка, эквивалентен
X = A;
tmp_X = B;
tmp_X = X + 1;
X = D;
// дожидаемся завершения всех активных в данный момент блоков
X = tmp_Х;

4) Обычное - для программистов, не знающих Верилога.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:January 6th, 2012 11:34 pm (UTC)
(Link)
2) если "=" и "<=" применяются для разных регистров, то оно понятно, а вот для одного - странно

3) С другой стороны, при таком подходе можно сказать, что tmp_X - это у нас первая ступень двухступенчатого регистра, а собственно X - вторая. И если его синтезировать из индивидуальных элементов, совсем ничто не мешает так делать, и даже экономия выходит на том, что во многих случаях можно обходиться одноступенчатыми регистрами.

Кстати, исходя из чувствительностей, будет ли оно побито на такты вот так?

X = A;
tmp_X = B;
---
tmp_X = X + 1;
X = D;
---
X = tmp_Х;

4) Но ведь получается, что X=X+1 не имеет смысла, а X <= X+1 - имеет, то есть именно <= более привычно для обычных программистов. Или оно само умеет отслеживать циклическую зависимость в X=X+1 и вставлять tmp_X?
(Reply) (Parent) (Thread)
[User Picture]
From:master_a
Date:January 7th, 2012 01:34 am (UTC)
(Link)
1. На всякий случай назыаются эти присвоения в Верилоге
"blocking" and "non-blocking". Немало статей и книг посвящено пояснению как это все работает.

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

3. На уровне RTL следует помнить что кроме двухступенчатых регистров есть еще transparent latches.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:January 7th, 2012 02:03 am (UTC)
(Link)
2) Язык позволяет, а софтверному симулятору все равно, он алгоритм отрабатывает.

3) Если это написано в одном блоке, то будет выполнено за один цикл симуляции. Разбиение на такты - забота программиста. Более того, что получится из блока - комбинаторная логика, двухступенчатые регистры или задвижки (latches), зависит от объявленной чувствительности блока (которую я для простоты опустил) и/или от наличия у переменных, изменяемых в блоке, live ranges, пересекающих начало блока. В данном случае синтезатор увидит, что значение Х всегда равно A+1, т.е. это будет или комбинаторный инкрементор, или регистр с инкрементором на входе в зависимости от объявленной чувствительности блока (по фронту клока или по уровню данных).

4) Для вспомогательных переменных, которые используются только внутри одного последовательно выполняемого блока, X=X+1 имеет конкретный смысл изменения значения индуктивной переменной. Как же еще циклы писать?

Для переменных с "реальным физическим смыслом", используемых в разных параллельно выполняемых блоках, имеет смысл писать <=, чтобы гарантировать независимость результатов софтверной симуляции от порядка исполнения блоков на последовательной машине. А синтезатор смотрит на блоки по отдельности, поэтому что А=В, что А<=B при чувствительности по уровню данных ("always @(B)") будет буфер, а по фронту клока ("always @(posedge clk)") - регистр.

А если написать X<=X+1 с чувствительностью по уровню, то "что видишь, то и поимеешь" - будет комбинаторный цикл, никакого волшебства.

(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:January 7th, 2012 04:24 am (UTC)
(Link)
2) Мне более интересно, как оно выходит в итоге в настоящем железе. Я бы на самом деле заставил компилятор выдавать ошибку на такую заведомо непотребную мешанину в коде. Потому что она скорее всего означает, что кто-то криво сделал cut-n-paste.

3) Но в итоге-то увеличенное значение должно попасть назад в X?

4) Я правильно понимаю, что X до присваивания и X после присваивания X=X+1 будут разными физическими регистрами, а потом переложится назад когда пойдет следующая итерация цикла? Потому что если это сделать в одном одноступенчатом регистре, то выйдет гонка с неопределенным результатом.
(Reply) (Parent) (Thread)
[User Picture]
From:master_a
Date:January 7th, 2012 06:42 am (UTC)
(Link)
Имея корни в жестком железе соединяемом проводами, я всегда думаю в терминах получающегося "мягкого" железа а не того что позволяет язык.

Нанятно что верилог придуман для симуляции (равно как и VHDL) а использование для синтеза пришло потом. Так что не удивительно что бывает несинтезируемый код. В отличие от програм, которые всегда выполняемы, даже если результат - core dump.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:January 7th, 2012 02:04 pm (UTC)
(Link)
Ну почему, пронраммы тоже могут содержать семантические ошибки, на которых компилятор остановится.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:January 7th, 2012 09:01 am (UTC)
(Link)
2) Да, конечно, синтезаторы по умолчанию ругаются на смесь двух типов присваиваний, но теоретически эту ошибку можно подавить.

3,4) Если грубо, то перед синтезом сначала строится static single assignment graph блока (с разворачиванием циклов со статическими границами и прочими статическими оптимизациями), который для X<=A+1 и X=A; X=X+1 получится один и тот же.

Из блока получается кусок схемы, входами которого служат значения переменных, используемых как r-values до присваивания, а выходами - все переменные, которые бывали l-values. Если у блока была попрошена чувствительность по фронту клока, то к выходным переменным присобачиваются двухступенчатые регистры (flip-flops).
Если не было, то для каждой выходной переменной анализируется условие, при котором она может изменить значение. Если это условие не тождественная истина, то делается одноступенчатый регистр с защелкой, управляемой этим условием, иначе будет просто комбинаторная логика. При этом могут получиться комбинаторные циклы, и синтезатор о них может предупредить, но в общем случае он не в состоянии это определить (например, если цикл пересекает границы раздельно синтезируемых модулей), и этим занимаются утилиты "дальше по течению".
Так что если написать просто X=X+1 или X <= X+1 в качестве единственного оператора в блоке без клока, то получится без всяких регистров (потому что Х изменяет значение безусловно, а клока не попросили) инкрементор, замкнутый сам на себя. Это физического смысла не имеет, но Верилог - он как Си. Их девиз "вы этого хотели - вот вам".
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:January 7th, 2012 02:09 pm (UTC)
(Link)
То есть, когда присваивается глобальная переменная X, не используется каждый раз тот же самый регистр, а на каждое присваивание создается новый? А там где она читается, оно анализирует, из какого кода могло выполнение сюда прийти и использует соответствующий из них?

И оно же небось время исполнения комбинаторной логики должно тоже анализировать? А то если ее сильно много, то она в такт не уложится.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:January 7th, 2012 06:12 pm (UTC)
(Link)
На каждое присваивание создается новая переменная, которая в конце концов окажется не регистром, а проводом.

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

Именно так. Например, если было написано
x = a + b; if (cond) x = с + d;
то т.к. мы в зависимости от cond можем прийти к концу блока по двум разным путям, в результате для х получится мультиплексор с (безымянными) входами от a+b и с+d и селектором cond.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:January 7th, 2012 06:15 pm (UTC)
(Link)
А то если ее сильно много, то она в такт не уложится.

Для timing analysis есть отдельные утилиты. Это не проблема синтезатора, так же как не проблема компилятора с языка программирования предупреждать программиста о неэффективном алгоритме.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:January 8th, 2012 02:53 pm (UTC)
(Link)
Но тут-то он будет не просто неэффективный, а нерабочий. Если вычисление функции не уложится в цикл, в результате получится мусор.
(Reply) (Parent) (Thread)
[User Picture]
From:msh
Date:January 6th, 2012 09:35 pm (UTC)
(Link)
Все операции синхронизированы с клоком и = и <= выполняются в разное время такта?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 6th, 2012 09:39 pm (UTC)
(Link)
Можно и так сказать, но нужно уточнить, что значит "выполняются".
(Reply) (Parent) (Thread)
[User Picture]
From:ilya_dogolazky
Date:January 6th, 2012 10:31 pm (UTC)
(Link)
А вот задачка про другой язык программирования, ну скажем Метапост.

X=A;
X:=X+1;
X=D;

После его выполнения А получается на единицу меньше чем D. В чём семантика значков "=" и ":=" ?

Edited at 2012-01-06 10:32 pm (UTC)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 6th, 2012 10:41 pm (UTC)
(Link)
Стандартная семантика присваивания для = и := удовлетворяет такой формулировке.

В интерфейсе ЖЖ не хватает фичи оповещения о редактировании комментария в процессе написания ответа на него. "=" - ребро между узлом типа "значение" и узлом типа "функция", ":=" - определение функции в узле. Так годится?

Edited at 2012-01-06 10:47 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:ilya_dogolazky
Date:January 6th, 2012 10:48 pm (UTC)
(Link)
я там поэтому поменял слегка, теперь не удовлетворяет
(Reply) (Parent) (Thread)
[User Picture]
From:ilya_dogolazky
Date:January 6th, 2012 10:49 pm (UTC)
(Link)
Ну может и годится, но тогда это какой-то другой язык. Уточню ещё --- ":=" это обычное присваивание.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:January 6th, 2012 10:59 pm (UTC)
(Link)
Тогда можно сказать, что = - это временный aliasing.
(Reply) (Parent) (Thread)
[User Picture]
From:ilya_dogolazky
Date:January 6th, 2012 11:12 pm (UTC)
(Link)
"=" это "равно", то есть такой значок задаёт (линейное) уравнение
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:January 7th, 2012 12:42 am (UTC)
(Link)
Если я правильно уловил принцип смешения декларативных и процедурных "присваиваний", результат зависит от того, у каких переменных до того были определены значения, и уравнение A=D+1 в общем случае не получится.
(Reply) (Parent) (Thread)
[User Picture]
From:ilya_dogolazky
Date:January 7th, 2012 08:46 am (UTC)
(Link)
Если я правильно понимаю, в том примере всё развалится при попытке присваивания X:=X+1, потому что к тому моменту X ещё не вычислено. Если в самое начало добавить что-нибуть типа X+2A=6 то всё исправится, и оба X и A будут вычислены после второго уравнения (X=A), после чего Х увеличится на единичку и D вычислится в последней строке. Но это всё конечно фигня, присваивание для обычных численных переменных в этом языке просто не нужно, вполне хватает линейных уравнений
(Reply) (Parent) (Thread)
[User Picture]
From:ygam
Date:January 7th, 2012 01:15 am (UTC)
(Link)
Еще в языке SISAL можно написать:

X := old Y;
Y := old X

http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=00130079

Edited at 2012-01-07 01:16 am (UTC)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 7th, 2012 01:31 am (UTC)
(Link)
У меня нет подписки. Вот тут хорошо: http://www2.cmp.uea.ac.uk/~jrwg/Sisal/16.Seq.loops.html
(Reply) (Parent) (Thread)
[User Picture]
From:ygam
Date:January 7th, 2012 02:40 am (UTC)
(Link)
О! Похоже, у моего работодателя есть подписка!
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:January 7th, 2012 02:52 am (UTC)
(Link)
И терпентин майкрософт на что-нибудь полезен!
(Reply) (Parent) (Thread)
[User Picture]
From:janatem
Date:January 7th, 2012 09:58 am (UTC)
(Link)
Если этот код валиден, то Verilog воистину странный язык. Я знаю VHDL и осмелюсь утверждать, что достаточно хорошо понимаю принципы описания цифровой аппаратуры.

Даже если предположить, что одно из присваиваний подразумевает onclock, а другое -- просто alias (соединение проводников), всё равно непонянто, почему не будет ошибки типа multisource. Даже если на разных "=>" разные клоки, будет либо явно multisource, либо мусорное значение в результате.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 7th, 2012 06:04 pm (UTC)
(Link)
Верилог по сравнению с VHDL действительно странен (моим первым HDL был как раз VHDL, и когда я начинал учить верилог, он меня удивил, но VHDL я уже успел практически забыть).

Фокус в том, что ни одно из присваиваний ничего само по себе не подразумевает. Наличие и тип регистра для переменной выводится из data flow graph, построенного из блока(плюс еще некоторые синтаксические тонкости, но это детали).

почему не будет ошибки типа multisource

Потому что все эти присваивания - внутри одного блока. Один блок - один source.
(Reply) (Parent) (Thread)