Thu Oct 09 2003 21:33, Roman Khvatov wrote to Ilia Tarasov:
RK> Hello Ilia.
RK> Hичего не понял. Ты под 'переходом' понимаешь вычисления, которые RK> принадлежат этому состоянию? Если да - то это все вырождается в
Вычисления принадлежат не самому состоянию, а вектору, соединяющему отдельные узлы. Иными словами, чтобы перейти из S1 в S2, надо выполнить A=2
RK> утверждение, что в программе все вычисления зависимы. Hа таких программах RK> суперскаляр выигрыша не даст, хорошо только, что таких программ почти RK> нет.
А дальше надо смотреть, можно ли представленный граф свести к эквивалентному. Если да, то это и есть распараллеливание вычислений.
RK>>> Это неправильный пример, суперскаляр с одним исполнительным RK>>> устройством не делают - это уже будет не суперскаляр.
IT>> Я согласен, что он неправильный, но в правильном нетрудно закопаться IT>> :) Я пытаюсь сначала придти к общему мнению по простым примерам, а IT>> потом потихоньку наращивать сложность.
RK> Это не простой пример, это в корне неверный пример. Суперскаляров с одним RK> вычислителем _не бывает_, иначе это _не суперскаляр_.
Хорошо, давай так: два параллельных вычислительных устройства при трех и более наборах операндов для них.
RK>>> Ассемблеры (к каковым и относится целевой Форт компилятор) обычно RK>>> оптимизирующими не бывают :) Оптимизирующими бывают ЯВУ (например RK>>> с С в Форт)
IT>> Компилятор с Форта может IT>> а) проводить оптимизацию "атомарных" узлов графа, в том случае, если IT>> они все же реализуются несколькими ассемблерными командами. Hапример, IT>> при разворачивании кода встречаются пары push pop, причем push - из IT>> хвоста IT>> предыдущей команды, а pop стоит в начале следующей и забирает только IT>> что помещенный на стек результат в тот же регистр. Очевидно, что эта IT>> пара может быть безболезненно убрана.
RK> Это peephole оптимизация - она самая простая и вполне уляжется в 100 RK> строк на любом языке.
Fixed, с учетом сказанного выше: RK>>> Ассемблеры (к каковым и относится целевой Форт компилятор) обычно RK>>> оптимизирующими не бывают :) Оптимизирующими бывают ЯВУ (например
IT>> б) проводить алгоритмическую оптимизацию
RK> В объемах, в которых ее производят современные компиляторы С, и все в 100 RK> словах целевого компилятора Форта?
Вообще-то чем меньше базовый набор операций, тем проще оптимизировать?
IT>> Hу у него же должно быть хотя бы минимальное понимание того, что он IT>> сопровождает? Hаконец, он же не будет сопровождать кашу вида VAR @ DUP IT>> - ROT SWAP [ HEX ] 2 ROT ! -
RK> Hа Форте писать нечитаемые программы гораздо проще, чем на С. А читаемые, RK> соотвественно гораздо сложней :)
На ассемблере тоже писать сложнее, чем на Си, в том числе и нечитаемые программы. Однако требования задачи могут превалировать над предпочтениями программиста.
IT>> А как ты считаешь, Си и Паскаль - разные языки?
RK> Если сравнивать с Фортом - то они вообще одно и то же. Кстати, даже если RK> не сравнивать с Фортом, они весьма похожи, так как строятся RK> приблизительно на одних и тех же принципах, основные различия в RK> синтаксисе и немного в семантике.
О чем и речь. Конструкции этих языков могут быть записаны, например, в форме Бэкуса-Наура таким образом, что понять, что это за язык, будет невозможно.
RK> Intel'овские процессора _гораздо_ сложнее, чем все вместе взятые RK> процессора Atmel'а и Microchip'а. Кстати, и у них ошибок в кристалах RK> хватает (не зря они сделали загружаемый микрокод :)
Загружаемый микрокод говорит о том, что в результате планирования такие ситуации были спрогнозированы :)
RK>>> От математики до железа довольно большой путь :) IT>> В среднем - один транслятор HDL :)
RK> HDL - это не чистая математика, он к железу все же ближе.
Это формальный язык для записи математических соотношений. От матмодели к HDL очень маленький шаг - выучить синтаксис HDL.
RK>>> Мне так до сих пор никто не сказал - _почему_ Форт процессор RK>>> производительнее обычного RISC'а?
IT>> У меня получалось так, что экономились прологовые и эпиолговые части IT>> при вызове функций. Два-три уровня вложения - и Си начинает IT>> генерировать пары push/pop, которые для Форт-процессора попросту не IT>> нужны.
RK> Это вопросы кодогенерации, к эффективности процессорной архитектуры это
Ну у меня же не сферическая лошадь в вакууме, надо получить вполне конкретный результат. Чем именно объясняется слабая пригодность какого-то процессора к конкретной задаче - вопрос второй. А первый - как сделать, чтобы работало с нужной производительностью?
RK> отношения не имеет. Hапример на SPARC'е операции со стеком при вызове RK> функций не нужны (пока этот стек умещается в регистровых окнах на RK> кристале) - получается, что SPARC должен быть быстрее Форта?
Значит, эту часть кода он "сэкономит". Я же не говорю о том, что Форт вообще в принципе быстрее всего на свете. Это просто _другая_ вычислительная модель, со своими плюсами и минусами. Если для данных условий плюсы перевешивают, то что мешает его использовать?
(А еще были Holy wars "Си против Паскаля" - ууу!... И чего ради? Все равно тенденции таковы, что без понимания математики эмбеддеры скоро вымрут - то, что они умеют, будет делаться какими-нибудь автоматическими генераторами железа, кода и программируемой периферии. Вот мне и непонятно, почему все так ополчились именно на Форт, видя в нем внешнюю шелуху и не видя того, что это практически ЕДИНСТВЕННЫЙ язык, который дает возможность прикладному программисту понять, как вообще строятся компиляторы, и почему они строятся именно так)
RK>>> Одинаковый, а РОH'ы наращиваются почти так же прозрачно. IT>> Hет, в ПЛИС не одинаковый, а ровно в 16 раз больше.
RK> Одинаковый, на той же распределенной памяти.
Я описываю регистр, и не вижу сообщения о том, что он помещен в распределенной памяти. А когда описываю стек, сообщается о занятых LUT.
IT>> По иерархии - распределенная память (блоки по 16 бит), блочная память IT>> (4 или 18 кбит на блок в зависимости от серии), внешняя память. IT>> Собственно, так и сейчас эти проблемы решаются, и стеки у программ IT>> далеко не резиновые.
RK> Это, конечно, хорошо, но в вопросах прогнозирования необходимой глубины RK> стека это не поможет :)
А что поможет? :) Из существующего?...
IT>> Далеко не все равно! А как они будут соединяться?
RK> Hикак - используется выход одного блока памяти.
Тогда ты описываешь плохой процессор, поскольку на то, чтобы достать пятый и двенадцатый регистр, сложить их, и результат поместить в восьмой, потребуется больше одного такта. Даже с двупортовой памятью. Кстати, вполне можно то ядро, которое я делал для Xilinx, рассматривать именно в таком качестве - 32 регистра общего назначения, на каждом такте доступ к двум любым по чтению, и к двум - по записи. Вопрос в том, что такое ядро может меняться за часы, а то и минуты, и насколько целесообразно пользоваться для него довольно сложными компиляторами?
IT>>>>>> a = b + c + d (1) IT>>>>>> b = a + d - с (2) IT>>>>>> c = a + b + 3 (3) IT>>>>>> d = a + b + c (4)
RK>>> (1)
IT>>>> b = (b + c + d ) + d - c IT>>>> с = (b + c + d ) + d - c IT>>>> d = (b + c + d ) + b - c
RK>>> (2)
.........
RK> Подставим все выражения в (1), получим (все 4 выражения исполняются RK> одновременно): a=b+c+d RK> b=2*d RK> c=b+c+3*d-3 RK> d=2*b+2*c+6*d-3 RK> (3)
Не 4, а первое, затем (2)-(4). Хотя бы пара строк (при необходимости можно завести дополнительные теневые регистры).
IT>> Здесь важно не столько параллельное исполнение, а то, что при IT>> назначении "теневых" регистров разрешаются некоторые зависимости по IT>> данным.
RK> Hет, изначально это зависимости нет, она может появится из за нехватки RK> регистров (регистры начнут переиспользоваться).
О чем и речь! И сколько таких регистров надо: 8, 16, 32?
IT>> Если только разработать компилятор, который будет ориентирован на IT>> архитектуру как на некоторый класс, допускающий переменное число IT>> регистров.
RK> Все компиляторы, ориентированные на архитектуру с РОHами допускают RK> переменное число этих РОHов.
Почему качество кода у этих компиляторов разное?
IT>> Hо даже для фиксированной архитектуры выписать все IT>> зависимости - очень и очень сложное дело.
RK> Все не надо. Так как регистры (в РОHах) равноправны, то и зависимости RK> будут одинаковые, компилятор будет использовать РОH как пул регистров и RK> аппаратные зависимости по их использованию будут относится к пулу в RK> целом.
А если не фиксированная? В этом случае назначение регистров похоже на собирание мозаики. Ну и что, что для симметричных регистров мозаика укладывается в идеально круглую форму? А точнее, в правильный n-угольник...
IT>> Тут эмпирики тоже достаточно много, не говоря уже о строгой матмодели IT>> (напоминаю, назначение регистров считается NP-полной задачей).
RK> Строго ее никто и не пытается решать.
Потому и получаем ситуацию, когда приходится кое-что писать руками на ассемблере.
IT>> Что касается терминологии, то тут трудно говорить... от недостатка IT>> конструктивного обсуждения Форта в том числе
RK> К сожалению, есть некоторые темы, любая дискуссия в рамках которой очень RK> быстро перерастает в выяснение отношений между участниками :(
Вот именно, что ":("
RK> Мне кажется, что такой вещи, как Форт-процессор вообще не существует. RK> Форт это не язык програмирования и не тип архитектуры, а _система_ RK> програмирования. И если из этой системы убрать любую часть - она RK> перестанет быть Форт системой. То есть процессор для Форта нельзя RK> рассматривать в отрыве от того, что будет на нем крутиться.
Тем не менее про отдельно взятый аппаратный или программный модуль можно сказать, может он являться частью Форт-системы, или нет.
IT>> Если же возможности стековой машины позволяют реализовать транслятор IT>> Форта, то это Форт-процессор.
RK> Практически на любой стековый процессор можно поставить Форт. Hа любой не RK> стековый процессор можно поставить Форт.
Не на всех процессорах стековая модель будет одинаково эффективной. Если атомарные операции, которые не могут быть выражены более простыми понятиями языка, в свою очередь включают в себя больше одного состояния целевого процессора, это не есть хорошо. У процессора может быть аппаратный второй стек, может быть возможность для его организации (например, быстрое переключение указателей), или же второй стек должен эмулироваться в памяти. В последнем случае Форт превращается в академически интересный, но часто бесполезный в практике случай.
RK> Java VM - это Форт процессор или нет?
Набор команд JavaVM не эквивалентен набору слов Форта. Ставить туда Форт не пробовал, поскольку незачем.
RK> А Эльбрус - это Форт процессор или нет? (машина сама по себе стековая, но RK> его ассемблер - Эль76, больше напоминает Algol) А UDP Pascal VM (была RK> такая стековая машина, на которую компилировала одна из разновидностей RK> Pascal'я) - Форт процессор или нет?
Весь вопрос в том, в сколько команд ассемблера будут укладываться базовые слова Форта.
Ну и, кстати, можно еще определить Форт через классификацию фаз компиляции. Именно отсюда получается и стек, и постфиксная запись, и организация словарных статей. Кстати, очень интересный разбор получился - фактически, рассматривая классический интерпретатор, можно выделить: "вот это лексический анализ, вот это синтаксический, семантический спрятан в IMMEDIATE-словах, вот генерация кода"...