T>>Мой основной тезис: надо сравнивать вход со всеми запомненными элементами, а не каждый с каждым.
V>А выбор текущего парного элемента, если вход пуст?

Наименьший элемент, будь то пара или одиночный. В любом случае, нам не надо сравнивать содержимое элементов, нам надо сравнить их позиции по порядку. Для 32-х элементов в блоке это 5 бит. Или 32-бита, если это позиционное кодирование.

V>А как огранизовывать твои "очереди" аппаратно?

Я аппаратное решение и описал.

V>А как делить память м/у очередями? Или под каждую очередь свою память?

Под каждую очередь своя память. Это нормальное решение, вполне технологичное. Как блоки кэша.

T>>Моя ассоциативная память работала вот так:
V>***
V>Похоже, что имелась ввиду структура, когда одна АП — одно исполнительное устройство. Тогда весь data-flow теряет смысл, должна быть общая ассоциативная память для как можно большего кол-ва узлов, т.е. должна работать ситуация, когда выходов и входов много.

Зачем?

Не покажешь на модели преимущества этого подхода?

T>>Сложность сравнения на больше-меньше ровно такая же, как и сравнение на равенство: O(log(N)). Различие только в множителе. Другого не дано.
V>Дано, т.к. вентили бывают не только 2И-НЕ, но и куча*И-НЕ,

Не больше 4И-НЕ. 2,3 и 4. Даже XOR бывает только двухвходовой из-за того, что в столбце от питания к земле уже 4 вентиля.

V>поэтому схема сравнения на равенство получается "плоской" относительно кол-ва бит, а на больше-меньше — иерархической по модулю 2 (ты назвал "как дешифратор" , но и они не всегда иерархические опять же из-за наличия многовходовых вентилей).

Многовходовой вентиль — с числом входов больше 4-х, — это логика с предзарядом (precharged logic, domino logic). Там возможно (2,3)И-(1..64)ИЛИ (возможен вариант (2,3,4)И-(1..64)ИЛИ, но это уже гораздо менее надёжно). Штука мощная. Применение её ограничено, её могут применять только гиганты типа Intel или IBM. Там надо очень точно вычитывать времена задержек, чтобы вентиль не разрядился к завершению такта. Работа, практически, ручная, очень большой объём.

Поэтому на неё можно не рассчитывать.

T>>Не стоит, согласен, но по другим причинам. По-моему, большая ассоциативная память просто не нужна.
V>Это пока ты матрицу перемножаешь как в той ссылке, а если у нас сотни _независимых_ потоков исполнения крутятся, а весь контекст вычислений сбросить в память — это тебе не 16 регистров в память сбросить, а еще бы знать, где в этой памяти контекст одного потока исполнения, и где — другого...

Что мешает завести тэг вычислительного потока в ключе dataflow и сбрасывать его данные по отведённым только для него адресам?

V>В общем, сложностей хватает даже теоретических. Как спец-процессор для _пакетного_ выполнения задач data-flow хорош, это видно невооружённым взглядом, а вот в случае с реал-тайм — это ХЗ, ХЗ.

Рилтайм тоже разный бывает. Например, надо обрабатывать изображения, quasi dense stereo matching. Там приоритетные очереди, свёртки по окнам и тп.

T>>Для этого необходимо делать так, чтобы токены не выбрасывались. Планирование вычислений и сортировка токенов с соответствии со "временем выполнения программы" решает эту проблему.
V>Это иногда зависит от входных _данных_, с чего я и встрял. Даже обычный парсер какого-нить контекстно-зависимой грамматики ИМХО в состоянии "засрать" вариантами всю наличную ассоциативную память при "удачном" раскладе и графы будут выплёвываться в обычную память, а значит — прощай распараллеливание такой весьма параллельной по-сути задачи.

Тебе надо это показать.

Не напишешь модель? А то мне без реализации не понять проблемы.

T>>А вот сумматор нужен. Или эквивалентная ему схема.
V>В принципе не суть, схема сравнения на больше-меньше может быть чуть проще сумматора, но сложность в терминах O(N) эквивалентна до множителя. Однако, играет рояль не только сложность в кол-ве вентилей, а быстродействие, т.е. длина самой длинной аппаратной цепочки, а она в этих схемах одинакова и зависит от кол-ва бит линейно.

Она зависит от количества бит, как O(log(N)).

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

T>>Я к этому делу пришёл два года тому назад. И даже сделал модель, как видишь.
T>>Мне нравится быстро проверять свои идеи, чего и остальным желаю.
V>Молодец, только вот от идеи до массовой реализации — сам понимаешь. Даже в той подветке про SymADE мне ситуация кажется менее безнадёжной, т.к. организовать немедленное производство ПО гораздо проще, чем железки. ПО можно разрабатывать поэтапно, опять же, с достижением результата на каждом этапе, а железка должна быть сразу без багов и сразу в рыночных конкурентноспособных характеристиках.

"Сразу без багов" — это ты errata к MIPS/Intel/ARM не видел.

Рекомендую.

Если будет модель реальной системы (процессор+компилятор), уже будет неплохо.

Посмотрим, в общем.

Здравствуйте, thesz, Вы писали:

T>>>Сложность сравнения на больше-меньше ровно такая же, как и сравнение на равенство: O(log(N)). Различие только в множителе. Другого не дано.
V>>Дано, т.к. вентили бывают не только 2И-НЕ, но и куча*И-НЕ,

T>Не больше 4И-НЕ. 2,3 и 4. Даже XOR бывает только двухвходовой из-за того, что в столбце от питания к земле уже 4 вентиля.

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

Опять же, даже в случае КМОП можно немного пожертвовать быстродействием в угоду большей "комбинаторности", т.е. за счёт более рационального использования вентилей делаем больше схем сравнения. Для отработки лишней задержки пихаем на некоем такте токен в буфер (а не в память), а используем результат сравнения предыдущего такта. При достаточной наполненности ассоциативной памяти никакого проседания быстродействия не будет. И на многовходовые вентили вполне можно закладываться даже на КМОП на твоих гипотетических моделях.

И вообще, откуда идёт ограничение на именно 4 вентиля? А пороговое напряжение для кремния какое? А питание ядер сейчас какое? А почему порог снизу для кремния в районе 1.2В? А если в модели, о которой ты завёл речь, напряжение взять повыше для конкретно блока ассоциативной памяти? А если брать не дешёвый кремний, а арсенид галлия или германий в будущем производстве? У них быстродействие куда как повыше. Правда, и подложки дороже значительно, но в стоимости чипов пока что стоимость подложек — далеко не основная, в перспективе массового производства должна стремится к стоимости именно подложек.

В общем, по моему ИМХО, никто и никогда не будет делать ассоциативную память по имеющимся кремниевым технологиям — сложно будет получить приемлимые характеристики, убъёт всю идею на корню, закатает под сукно.


T>>>Не стоит, согласен, но по другим причинам. По-моему, большая ассоциативная память просто не нужна.
V>>Это пока ты матрицу перемножаешь как в той ссылке, а если у нас сотни _независимых_ потоков исполнения крутятся, а весь контекст вычислений сбросить в память — это тебе не 16 регистров в память сбросить, а еще бы знать, где в этой памяти контекст одного потока исполнения, и где — другого...

T>Что мешает завести тэг вычислительного потока в ключе dataflow и сбрасывать его данные по отведённым только для него адресам?

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


T>Тебе надо это показать.
T>Не напишешь модель? А то мне без реализации не понять проблемы.

Это шутка такая? Ты же разбором занимаешься, должен понимать, что такое разбор с возвратом и откуда варианты берутся и зачем параллелизм нужен. Бери Алгоритм Эрли или Кока—Янгера—Касами — они разбирают вообще всё (т.е. не нужно пытаться привести КС грамматику к некоторому классу, удовлетворяющему неким ограничениям).
Даже бери простой восходящий разбор с возвратами по любой грамматике (любой — ключевое слово) — вот и показал.

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


T>>>А вот сумматор нужен. Или эквивалентная ему схема.
V>>В принципе не суть, схема сравнения на больше-меньше может быть чуть проще сумматора, но сложность в терминах O(N) эквивалентна до множителя. Однако, играет рояль не только сложность в кол-ве вентилей, а быстродействие, т.е. длина самой длинной аппаратной цепочки, а она в этих схемах одинакова и зависит от кол-ва бит линейно.

T>Она зависит от количества бит, как O(log(N)).

T>Почему я и спрашивал, разрабатывал ли ты железо. У тебя предпосылки неправильные, и выводы, соответственно, тоже.

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


T>"Сразу без багов" — это ты errata к MIPS/Intel/ARM не видел.

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


T>Если будет модель реальной системы (процессор+компилятор), уже будет неплохо.
T>Посмотрим, в общем.

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

T>>>>Сложность сравнения на больше-меньше ровно такая же, как и сравнение на равенство: O(log(N)). Различие только в множителе. Другого не дано.
V>>>Дано, т.к. вентили бывают не только 2И-НЕ, но и куча*И-НЕ,
T>>Не больше 4И-НЕ. 2,3 и 4. Даже XOR бывает только двухвходовой из-за того, что в столбце от питания к земле уже 4 вентиля.
V>Предупредил же заранее горячего вьюношу — не КМОП-ом единым, тем более, что товарищ изначально ассоциативную память хотел оптической сделать.

I believe when I see it. Все экстравагантные "оптические памяти" идут лесом. Есть только КМОП и больше ничего.

Если уж мы говорим о каком-то практическом выходе в ближайшее время.

Поэтому ты "либо трусы одень, либо крестик сними". Либо говори о практическом выходе и как бы не закатать под сукно, либо говори об "оптической ассоциативной памяти".

V>Опять же, даже в случае КМОП можно немного пожертвовать быстродействием в угоду большей "комбинаторности", т.е. за счёт более рационального использования вентилей делаем больше схем сравнения. Для отработки лишней задержки пихаем на некоем такте токен в буфер (а не в память), а используем результат сравнения предыдущего такта. При достаточной наполненности ассоциативной памяти никакого проседания быстродействия не будет. И на многовходовые вентили вполне можно закладываться даже на КМОП на твоих гипотетических моделях.

Я тебя не понимаю. Ты с синтезом или с разработкой дело имел?

Если не имел, так прямо и скажи, я в каждом комментарии ликбез буду проводить.

V>И вообще, откуда идёт ограничение на именно 4 вентиля? А пороговое напряжение для кремния какое? А питание ядер сейчас какое? А почему порог снизу для кремния в районе 1.2В? А если в модели, о которой ты завёл речь, напряжение взять повыше для конкретно блока ассоциативной памяти? А если брать не дешёвый кремний, а арсенид галлия или германий в будущем производстве? У них быстродействие куда как повыше.

Тогда уж алмазные (углеродные) плёнки.

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

Поэтому на них рассчитывать нечего.

То, о чем ты говоришь — повышение питания и прочее, — относится к разряду оптимизаций.

Ты ещё не читал, как я отношусь к преждевременным оптимизациям?

V>В общем, по моему ИМХО, никто и никогда не будет делать ассоциативную память по имеющимся кремниевым технологиям — сложно будет получить приемлимые характеристики, убъёт всю идею на корню, закатает под сукно.

Надо сделать модель, желательно, на синтезируемом подмножестве чего-либо, и посмотреть.

Ты модель не делал, ты говоришь исключительно из теоретических соображений.

T>>Тебе надо это показать.
T>>Не напишешь модель? А то мне без реализации не понять проблемы.
V>Это шутка такая? Ты же разбором занимаешься, должен понимать, что такое разбор с возвратом и откуда варианты берутся и зачем параллелизм нужен. Бери Алгоритм Эрли или Кока—Янгера—Касами — они разбирают вообще всё (т.е. не нужно пытаться привести КС грамматику к некоторому классу, удовлетворяющему неким ограничениям).

Нет, это не шутка.

V>Даже бери простой восходящий разбор с возвратами по любой грамматике (любой — ключевое слово) — вот и показал.

Ещё раз — это не шутка. Когда дело доходит до проверки чьих-то мыслей на модели, я не намерен шутить.

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

Результатом также считается отказ от написания модели. Это один из наиболее важных для этой дискуссии результатов.

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

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

Ассоциативную память надо делать как можно более простую. Предложенный тобой вариант с размножением страдает теоретическими проблемами (как определить, кого и когда надо размножать для анализируемой программы) и практическими — взрывной параллелизм, проблемы с порядком вычислений.

Это плохой вариант.

T>>Она зависит от количества бит, как O(log(N)).
T>>Почему я и спрашивал, разрабатывал ли ты железо. У тебя предпосылки неправильные, и выводы, соответственно, тоже.
V>Насколько я понял приведённые схемы, там грубо в полтора раза больше вентилей на сумматор надо будет, хоть и уменьшаем максимальную длину вентильной цепочки. Это ведь в полтора раза меньше потенциальный объем памяти. Что-то мне говорит, что это "не наш метод".

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

Я готов пойти на 4-хкратное уменьшение объёма памяти, если я смогу сделать иерархию и не буду иметь проблем с устранением ненужных элементов из этого малого объёма.

Эксперименты показывают, что 32-х слотов вполне достаточно.

T>>"Сразу без багов" — это ты errata к MIPS/Intel/ARM не видел.
V>Для Alchemy от AMD видел, вполне достойно. Процент ошибок у железячников в пересчете на вентиль на многие порядки ниже, чем у программистов, в пересчетё на машинную инструкцию. Да уже высказывался несколько лет назад на эту тему.

Эффект от ошибки в железе больше.

Здравствуйте, thesz, Вы писали:

T>Германий использовался в производстве, он очень дорогой, от него отказались. Арсенид галлия составной, его получение уже трудоемко, легирование дешевле его не сделает.

T>Поэтому на них рассчитывать нечего.

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

Дорогой пока что второй из упомянутых, но очень уж неплох и всё-равно в обозримом будущем на него медленно, но верно переползают. Лет 15 назад транзисторы на арсениде галлия стоили заоблачно, а теперь копейки и общедоступны, т.е. прогресс идёт и довольно быстро. Пример популярных цифровых схем на арсениде галлия — делители частоты для СВЧ (счётчики).

Мало ли что от германия отказались в своё время, всё идёт по кругу. Кремниевый КМОП "выстрелил" сравнительно недавно из-за прорыва в миниатюризации, а до этого емкость затвора кремниевой КМОП ячейки была просто неприличной и всерьёз никто КМОП не рассматривал (286-е шли еще на n-МОП). Послужил кремний некоторое время, спасибо, но уже полностью сдох и это очевидно. Что 5 лет назад я покупал проц на 3.2GHz, что сейчас на 3.7GHz — а ведь до этого каждые полтора года — удвоение частоты, а сейчас имеем банальное экстенсивное развитие "вширь".

На тот момент дешевле оказалось развитие по пути миниатюризации, но этот путь не вечен, и заставить кремний работать на частотах свыше 10ГГц будет очень сложно (хотя уверен, что примерно до 15GHz его домучают всё-таки), ввиду ограничения снизу на 1.2-1.3 вольта по питанию — всё труднее становится отводить тепло, затрачиваемое на перезаряд паразитных емкостей затвовров. Германиевые могут работать при более низком напряжении, т.е. и дальше можно безопасно миниатюризировать, а арсенид-галлиевые с их подвижными зарядами демонстрируют чудеса — СВЧ счётчики, безо всякой современной нано-миниатюризации работают на частотах до 250ГГц, а _потенциально_ — еще в несколько раз выше.

В общем, тут и обсуждать нечего, учитывая, что первые массовые data flow процы появятся не ранее, чем лет через 10... ИМХО, кремниевый КМОП будет лишь одним из игроков, и далеко не самым топовым и престижным.


T>Ты ещё не читал, как я отношусь к преждевременным оптимизациям?

А оптимизация цены подложки? И не путаешь ли ты в одну кучу оптимизацию и следование требованиям? Быстродействующая ассоциативная память — это условие существования архитектуры как конкурентноспособного решения.


V>>Даже бери простой восходящий разбор с возвратами по любой грамматике (любой — ключевое слово) — вот и показал.

T>Ещё раз — это не шутка. Когда дело доходит до проверки чьих-то мыслей на модели, я не намерен шутить.

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


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

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

T>Результатом также считается отказ от написания модели. Это один из наиболее важных для этой дискуссии результатов.

Модели процессора? И компилятор под него? Прямо здесь и сейчас? А ты связь с реальностью не теряешь, случаем?


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

T>Не может по условиям образования пар, если всё делать более-менее нормально.

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

T>Ассоциативную память надо делать как можно более простую. Предложенный тобой вариант с размножением страдает теоретическими проблемами (как определить, кого и когда надо размножать для анализируемой программы)

Это предложенный не мной вариант, это автором data-flow предложенный. А твоя, с одним выч.узлом и циклическими очередями к нему — это самотворчество, имеющее большие проблемы с теоретическим обоснованием. Сам принцип data-flow — это автораспределение нагрузки, есть свободные парные токены и есть свободное выч.устройство — гоу на исполнение. Нет никакого смысла городить ассоциативную память ради одного приатаченного исполнительного блока, ибо ты не получишь того самого автораспределения нагрузки, ради которого все эти пляски.

И твоё моделирование расчёта матрицы здесь — это хорошо, но, согласись, узкий класс задач.


T>и практическими — взрывной параллелизм, проблемы с порядком вычислений.

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


T>Это плохой вариант.

Так какой именно вариант плохой? Когда у нас много сравнивающих узлов и много вычислительных узлов? Это же "классика" (если это слово применимо к data flow). Или "плохой" — это "ты мне не нравишься"?

Я с самого начала подветки и сказал, что именно в этом и есть проблемы у data-flow, по крайней мере у тех вариантов, у которых публиковались функциональные схемы "будущих потенциальных разработок". Этот неприятный момент очевиден, и я это сказал первый, можно было мне не возвращать.


T>Эксперименты показывают, что 32-х слотов вполне достаточно.

Эксперименты показывают, что вы эту программу на "ассемблере data flow" написали, а как произвольные вложенные циклы из ЯВУ так же разворачивать и упорядочивать в общем случае — совершенно непонятно.

V>Мало ли что от германия отказались в своё время, всё идёт по кругу.

Ага, BMW недавно добавило к своим дизелям паровую машину.

V>Кремниевый КМОП "выстрелил" сравнительно недавно из-за прорыва в миниатюризации, а до этого емкость затвора кремниевой КМОП ячейки была просто неприличной и всерьёз никто КМОП не рассматривал (286-е шли еще на n-МОП). Послужил кремний некоторое время, спасибо, но уже полностью сдох и это очевидно. Что 5 лет назад я покупал проц на 3.2GHz, что сейчас на 3.7GHz — а ведь до этого каждые полтора года — удвоение частоты, а сейчас имеем банальное экстенсивное развитие "вширь".

V>На тот момент дешевле оказалось развитие по пути миниатюризации, но этот путь не вечен, и заставить кремний работать на частотах свыше 10ГГц будет очень сложно (хотя уверен, что примерно до 15GHz его домучают всё-таки), ввиду ограничения снизу на 1.2-1.3 вольта по питанию — всё труднее становится отводить тепло, затрачиваемое на перезаряд паразитных емкостей затвовров. Германиевые могут работать при более низком напряжении, т.е. и дальше можно безопасно миниатюризировать, а арсенид-галлиевые с их подвижными зарядами демонстрируют чудеса — СВЧ счётчики, безо всякой современной нано-миниатюризации работают на частотах до 250ГГц, а _потенциально_ — еще в несколько раз выше.

V>В общем, тут и обсуждать нечего, учитывая, что первые массовые data flow процы появятся не ранее, чем лет через 10... ИМХО, кремниевый КМОП будет лишь одним из игроков, и далеко не самым топовым и престижным.

Вот-вот.

Поэтому я и рассчитываю на кремний.

T>>Ты ещё не читал, как я отношусь к преждевременным оптимизациям?
V>А оптимизация цены подложки? И не путаешь ли ты в одну кучу оптимизацию и следование требованиям? Быстродействующая ассоциативная память — это условие существования архитектуры как конкурентноспособного решения.

Это не так. Здесь нужен баланс.

V>>>Даже бери простой восходящий разбор с возвратами по любой грамматике (любой — ключевое слово) — вот и показал.
T>>Ещё раз — это не шутка. Когда дело доходит до проверки чьих-то мыслей на модели, я не намерен шутить.
V>Это ты или не ты? В соседнем топике ты спрашивал в таком духе: "отчего было использовано моделирование, а не прямой расчёт характеристик и их реализация?"

Это где я так спрашивал?

T>>Пиши модель процессора, пиши для него программу разбора, попытайся получить взрывной параллелизм. О любых результатах расскажи.
V>Взрывной парралелизм для задачи разбора с возвратами не зависит от модели процессора, а исключительно от св-в грамматики и конкретной входной цепочки.

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

Почему?

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

Беда в том, что грамматики строятся так, что большая их часть регулярна, а не контекстно-свободна. И уж тем более не LR. (источник PTAPG)

Поэтому параллельный запуск многих разборщиков неэффективен. Кстати, это легко проверить с помощью par/pseq на обычном монадическом разборщике. Хотя это и так видно.

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

T>>Результатом также считается отказ от написания модели. Это один из наиболее важных для этой дискуссии результатов.
V>Модели процессора? И компилятор под него? Прямо здесь и сейчас? А ты связь с реальностью не теряешь, случаем?

Нет. Не надо компилятор. Надо модель процессора и программу для него. Программу можно и на ассемблере написать.

Я связь с реальностью не теряю. Написанием моделей я её поддерживаю. Я отвечаю за свою глупость (если моя идея глупа) своим потраченным временем.

Кстати, модель процессора пишется ну очень быстро: http://thesz.livejournal.com/440974.html

Это, максимум, день.

Модель ассоциативной памяти не менее быстро — ещё день.

Итого, за выходные ты сможешь подтвердить или опровергнуть свои слова.

А я тебя очень сильно зауважаю.

V>>>Это, кстати, ответ на еще один вопрос — зачем одной ассоциативной памяти много исполнительных блоков. Затем, что выход одной операции может служить аргументом множества других операций, т.е. по идее может образоваться множество пар из одного токена.
T>>Не может по условиям образования пар, если всё делать более-менее нормально.
V>Я тебе пример привёл, где принципиально один выходной токен может образовывать кучу пар с другими — это банальный восходящий разбор с возвратами. После каждого очередного вывода в общем случае доступно более одного правила для последующего вывода.

Я могу построить программу так, чтобы этого не произошло. Более того, я так и построю программу. У меня ассоциативная память ничего не умеет, кроме, как образовывать пары.

Зато она хорошо масштабируема.

T>>Ассоциативную память надо делать как можно более простую. Предложенный тобой вариант с размножением страдает теоретическими проблемами (как определить, кого и когда надо размножать для анализируемой программы)
V>Это предложенный не мной вариант, это автором data-flow предложенный. А твоя, с одним выч.узлом и циклическими очередями к нему — это самотворчество, имеющее большие проблемы с теоретическим обоснованием. Сам принцип data-flow — это автораспределение нагрузки, есть свободные парные токены и есть свободное выч.устройство — гоу на исполнение. Нет никакого смысла городить ассоциативную память ради одного приатаченного исполнительного блока, ибо ты не получишь того самого автораспределения нагрузки, ради которого все эти пляски.

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

Цепочки передачи токенов от АП к ИУ имеют заметную задержку.

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

V>И твоё моделирование расчёта матрицы здесь — это хорошо, но, согласись, узкий класс задач.

Характерный. То же самое будет происходить со всеми вычислительными фортрановскими задачами, практически.

T>>и практическими — взрывной параллелизм, проблемы с порядком вычислений.
V>Взрывной парралелизм — это св-во не процессора, а конкретной задачи. Там, где возможностей расспараллеливания не хватает, делают очереди и стеки, типа как упомянутый разбор на обычных процах или как вы делали по ссылке. Но это же все алгоритмы надо менять, и не компилятор это там делал, заметь, эту оптимизацию вы выполняли "вручную" — тонкий такой намёк любителю Хаскеля и противнику оптимизаций.

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

Поэтому модель системы у меня написана не оптимальна. Я не знал, как её сделать.

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

T>>Это плохой вариант.
V>Так какой именно вариант плохой? Когда у нас много сравнивающих узлов и много вычислительных узлов? Это же "классика" (если это слово применимо к data flow). Или "плохой" — это "ты мне не нравишься"?

Это плохой вариант — когда много АП и много ИУ и все связаны со всеми.

Что самое интересное, даже в этом случае АП делается по описанному мной варианту с одним входом и одним выходом, просто делается коммутационная сеть.

V>Я с самого начала подветки и сказал, что именно в этом и есть проблемы у data-flow, по крайней мере у тех вариантов, у которых публиковались функциональные схемы "будущих потенциальных разработок". Этот неприятный момент очевиден, и я это сказал первый, можно было мне не возвращать.

Так и нечего к нему возвращаться. Зачем ты к нему вернулся? Ведь сам этот путь проделал, я тебя не подталкивал.

Поэтому впредь отталкивайся от лучшего варианта, например, моего.

T>>Эксперименты показывают, что 32-х слотов вполне достаточно.
V>Эксперименты показывают, что вы эту программу на "ассемблере data flow" написали, а как произвольные вложенные циклы из ЯВУ так же разворачивать и упорядочивать в общем случае — совершенно непонятно.

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

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

Здравствуйте, vdimas, Вы писали:

T>>Германий использовался в производстве, он очень дорогой, от него отказались. Арсенид галлия составной, его получение уже трудоемко, легирование дешевле его не сделает.

T>>Поэтому на них рассчитывать нечего.

+1

V>Ты прямо с какой-то параллельной реальности.

В чем проблема? Правильно человек говорит, не надо на них рассчитывать.

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

Прототип по технологии "кремний на германии" (правильно это называется так), который используется в СВЧ, стоил не так давно порядка 200К USD за запуск на фабрике IBM (открытые данные с mosis.com). Если мне память не изменяет. Прототип в кремнии — порядка 40К. Техпроцесс — 0,13. Это чтобы вы представляли себе, что означает "германий как раз таки недорогой".

Ни Интел, ни другие производители процессоров, включая IBM, которая имеет фабрики способные производить чипы по технологии "кремний-на-герминии", не полагаются на данную технологию при производстве процессоров. Данная технология сейчас применяется там, где без нее совсем никак. В основном, это сверхвысокочастотный RF-дизайн.

Что такое "кремний даром". Не называя фабрик, чтобы не нарушить NDA — полный запуск (не прототип) по техпроцессу 0.90 обойдется в сумму порядка 700-100 тыщ. баксов, техпроцесс 0.13 можно найти от 300К USD и выше. Это стоимость изготовления фотошаблонов, разовая выплата. Далее, за каждую пластину диаметром 200-300мм вы заплатите сумму порядка 2-3 тыщ долларов. Если для вас все это "даром", то я вам завидую.

Это фабрика. Стоимость полного комплекта САПР на весь цикл разработки доходит до миллиона долларов в год на человека. Обычных САПР. Для кремния на германии требуются свои САПР-ы, которые дороже.

V>Дорогой пока что второй из упомянутых, но очень уж неплох и всё-равно в обозримом будущем на него медленно, но верно переползают. Лет 15 назад транзисторы на арсениде галлия стоили заоблачно, а теперь копейки и общедоступны, т.е. прогресс идёт и довольно быстро. Пример популярных цифровых схем на арсениде галлия — делители частоты для СВЧ (счётчики).

Вы цены на запуски знаете? Нет, вы их не знаете, и знать не можете в принципе, потому реальность такова, что эти цены доступны только под NDA по запросу от фабрик, и разглашать их запрещено.

Пионерской организацией за версту несет. Вы думаете ваши "стоили заоблачно" и "копейки" — это круто звучит? Да нихрена вы цен не знаете, и знать их не можете в принципе. Хватит понты кидать уже, смешно.

Здравствуйте, Gaperton, Вы писали:

G>(открытые данные с mosis.com).

mosis.org

G>Что такое "кремний даром". Не называя фабрик, чтобы не нарушить NDA — полный запуск (не прототип) по техпроцессу 0.90 обойдется в сумму порядка 700-100 тыщ. баксов,

90нм, в сумму 700-1000 тыщ баксов.

G>Пионерской организацией за версту несет. Вы думаете ваши "стоили заоблачно" и "копейки" — это круто звучит? Да нихрена вы цен не знаете, и знать их не можете в принципе. Хватит понты кидать уже, смешно.

А вот это не опечатка. Еще к означенным понтам стоит прибавить смешные экскурсы в "физику" в дискуссии об архитектурах. Такая каша может только улыбку вызывать. Простите, вы таки "тополог", или "спициалист" по архитектурам? Это вообще разные специальности, нельзя хорошо разбираться в том и другом сразу. Вот зато ни в чем сразу не разбираться можно, это не фокус .

Здравствуйте, Gaperton, Вы писали:


G>Ни Интел, ни другие производители процессоров, включая IBM, которая имеет фабрики способные производить чипы по технологии "кремний-на-герминии", не полагаются на данную технологию при производстве процессоров. Данная технология сейчас применяется там, где без нее совсем никак. В основном, это сверхвысокочастотный RF-дизайн.

Тем не менее, я предлагал взглянуть на динамику. Еще лет 10 назад приведенные цифры по германию были на порядок примерно больше, а по арсениду галлия — на пару порядков больше. И ты правильно сказал, насчёт "где без нее совсем никак". У кремния есть непреодолимый недостаток — высокое пороговое напряжение перехода (около 0.5-0.6В), т.е. ситуация такова, что при низкой собственной подвижности носителей, увеличивать тактовую частоту можно будет лишь за счёт увеличения кол-ва прокачиваемых зарядов на величину амплитуды колебания напряжения, банально — за счёт увеличения потребления, а как отводить тепло при этом — не понятно, т.к. теплопроводность кремния (в сравнении с тем же германием) — невелика. По напряжению уже достигли минимального порога — точка. По тех-процессу — для кремния скоро будем на пороге достоверного срабатывания (т.к. большой к-т шумов). Там, где на кремнии будет достигнут минимум размеров техпроцесса, на германии можно будет еще продолжать и продолжать. Как альтернатива — вообще отказаться от повышения тактовой частоты и пойти по эксенсивному пути наращивания вычислительных блоков на кристалле. Но, что-то мне подсказывает, что рано или поздно придётся нгачать работать над увеличением тактовой. Если бы прогресс по тактовой частоте не замер 4 года назад, я бы даже не рассуждал на эти темы, т.к. тема была бы преждевременной. Но существующий "ступор" развития — на лицо. Некоторое время можно будет, конечно, еще отыграть за счёт "экстенсивного" пути развития, но, уверен, гораздо меньше, чем 10 лет.

G>Что такое "кремний даром". Не называя фабрик, чтобы не нарушить NDA — полный запуск (не прототип) по техпроцессу 0.90 обойдется в сумму порядка 700-100 тыщ. баксов, техпроцесс 0.13 можно найти от 300К USD и выше. Это стоимость изготовления фотошаблонов, разовая выплата. Далее, за каждую пластину диаметром 200-300мм вы заплатите сумму порядка 2-3 тыщ долларов. Если для вас все это "даром", то я вам завидую.

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


V>>Дорогой пока что второй из упомянутых, но очень уж неплох и всё-равно в обозримом будущем на него медленно, но верно переползают. Лет 15 назад транзисторы на арсениде галлия стоили заоблачно, а теперь копейки и общедоступны, т.е. прогресс идёт и довольно быстро. Пример популярных цифровых схем на арсениде галлия — делители частоты для СВЧ (счётчики).

G>Вы цены на запуски знаете? Нет, вы их не знаете, и знать не можете в принципе, потому реальность такова, что эти цены доступны только под NDA по запросу от фабрик, и разглашать их запрещено.

G>Вы думаете ваши "стоили заоблачно" и "копейки" — это круто звучит? Да нихрена вы цен не знаете, и знать их не можете в принципе. Хватит понты кидать уже, смешно.

Хватит кидать свои понты, в свою очередь. Я знаю продажные цены, и вижу нехилую динамику в последние годы (на порядок примерно за 10 лет). Названные тобой цены — это однократные вложения, которые в себестоимости лежат обратно пропорционально кол-ву выпущенных и проданных изделий. А от чего цены так сильно упали на некремниевые схемы за десятилетие? Не от того ли, что случился бум мобильников и высокоскоростного оптического ethernet? Массовое производство спасёт отца русской демократии (уже спасает, и весьма заметно).

Здравствуйте, Gaperton, Вы писали:


G>А вот это не опечатка. Еще к означенным понтам стоит прибавить смешные экскурсы в "физику" в дискуссии об архитектурах. Такая каша может только улыбку вызывать. Простите, вы таки "тополог", или "спициалист" по архитектурам?

Да ради бога, пусть вызывает улыбку. Рассуждения эти вообще ответвились из требования быстродейтсвующей ассоциативной памяти, и были постольку-поскольку. А насчёт физики — ну не буду же я здесь подробно описывать, почему не воспринимаю кремний всерьёз? Если человек не знает, что есть пороговое напряжение для полупроводника, и никак не реагирует на этот аргумент, если не ориентируется в проводимости материалов и не видел "шумовую" составляющую на АЧХ и на высокочастотных осциллографах, то это разговор в пустоту, кому это будет интересно? Мне повезло посвятить приличный период в своё время на разработку цифровой передачи по радио-каналам, со спецами по СВЧ проработал бок-о-бок не один год, и как раз о физике вещей могу поговорить с удовольствием, был бы собеседник... А топология — это несколько другой уровень, не находишь? И изменяется эта область довольно быстро вслед за уменьшением процесса (отслеживал до 2002-го года примерно, и всё время удивлялся скорости изменений, тогда как раз бум развития был). Однако, через принципиальные ограничения материалов не перепрыгнешь всё-равно. У меня, например, вызывает улыбку твоё решение привести сюда цифры по затратам. Я ведь тоже могу привести, правда не актульные, а уровня 99гг, но тем интереснее было бы сравнить, тем и смешнее тебе показались бы собственные аргументы, ибо, такое ощущение, что ты как только что это всё увидел, запечатлел себе некий "снапшот".

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


G>Это вообще разные специальности, нельзя хорошо разбираться в том и другом сразу. Вот зато ни в чем сразу не разбираться можно, это не фокус .

Гадание на кофейной гуще тоже за фокус сходит, главное, не относится к этому серьёзно.

Здравствуйте, thesz, Вы писали:

T>>>Ты ещё не читал, как я отношусь к преждевременным оптимизациям?
V>>А оптимизация цены подложки? И не путаешь ли ты в одну кучу оптимизацию и следование требованиям? Быстродействующая ассоциативная память — это условие существования архитектуры как конкурентноспособного решения.

T>Это не так. Здесь нужен баланс.

Мне бы хотелось прояснить твою позицию по data-flow, а то идёт уже которое сообщение подряд неконструктив. Мне (и уверен, не только мне), показалось, что flow-архитектуру двигают именно как средство масштабирования (наращивания кол-ва) вычислительных узлов, одновременно работающих над одними и теми же данными (смысла ради 1-го узла в data-flow практически нет), и способными эффективно делить м/у собой эти данные именно с помощью ассоциативной памяти. И, хотя матрицы NxN можно избежать, согласен, но тут у нас по-любому будет матрица MxN (как в анкдоте), и еще порядка сложности M*Log(M) схема распределения по узлам _одновременно_ получаемых парных токенов. Поэтому, мне и кажется — что если речь зайдет о многих десятках выч. узлов, то никаким "балансом" не обойтись, безальтернативно нужна будет "серебрянная пуля" в виде этой непростой ассоциативной памяти. От того и позволил себе пофантазировать, относительно технологии изготовления этого узла (заметь — не всего проца, а только АП).


V>>>>Даже бери простой восходящий разбор с возвратами по любой грамматике (любой — ключевое слово) — вот и показал.
T>>>Ещё раз — это не шутка. Когда дело доходит до проверки чьих-то мыслей на модели, я не намерен шутить.
V>>Это ты или не ты? В соседнем топике ты спрашивал в таком духе: "отчего было использовано моделирование, а не прямой расчёт характеристик и их реализация?"

T>Это где я так спрашивал?

Это ты спрашивал, почему джиттер буфер моделировал, я не расчитывал. Я подробно там ответил, ты, похоже, решил не читать ответ.


T>>>Пиши модель процессора, пиши для него программу разбора, попытайся получить взрывной параллелизм. О любых результатах расскажи.
V>>Взрывной парралелизм для задачи разбора с возвратами не зависит от модели процессора, а исключительно от св-в грамматики и конкретной входной цепочки.

T>Это не так. В перемножении матриц взрывной параллелизм получается вообще всегда, однако в моей модели его нет.

Странно, а в обычном алгоритме всего надо 3 ячейки, хранящие текущие состояния 3-х вложенных циклов.

T>Почему?

Потому что, "может быть распараллелено" и принципиально требует паралельного расчёта — это разные вещи. Матрица принципиально не требует, а ты лишь параллелишь до определённого уровня, подсчитывая и иерархически складывая частичные суммы. Ну блин, прямо Америку открыл, посмотри на БПФ и алгоритм "бабочки", и заодно станет понятно, почему он требует кол-во отсчётов, равное степени двойки — та же фигня. Можно и распараллелить, но принципиально паралеллить не требуется, в отличие от разбора грамматик, более высоких по уровню, чем регулярные и не сводящихся к LL(k), где к — фикированное (т.е. заведомо конечный коэф. возможного распараллеливания).


T>Беда в том, что грамматики строятся так, что большая их часть регулярна, а не контекстно-свободна. И уж тем более не LR. (источник PTAPG)

Эту чушь даже коментировать не хочу, надеюсь — ты описался. Если нет, то можно начать с простейшего — взять в любой форме записанную грамматику разбора простейших арифм. выражений — плюс/минус/умножить/скобки (благо в гугле полно ссылок и на её БНФ и PEG), и вот сведи мне её к регулярной. А заодно озвучь важное св-во регулярной грамматики, помня о котором всегда довольно быстро можно определить — является ли грамматика, описанная системой правил, регулярной или нет.

T>Поэтому параллельный запуск многих разборщиков неэффективен. Кстати, это легко проверить с помощью par/pseq на обычном монадическом разборщике. Хотя это и так видно.

Я не понял, что здесь видно. Если грамматика нерегулярна, это значит, что её эквивалентный НКА неприводим к ДКА, а моделирование работы НКА — это в общем случае тот самый взрывной параллелизм, со степенной зависимостью от длины цепочки. Единственно как стараются строить грамматики — это так, чтобы коэф при этой сложности был как можно меньше, т.е. минимизировать кол-во промежуточных неоднозначностей, тогда в процессе работы НКА большее кол-во вариантов его состояний будут тупиковыми и отпадать, экономя память для хранения текущих вариантов при паралельном разборе, или же глубину и "ветвистость" при рекурсивном (суть одно и то же, заметь, и не зависит от восходящей или нисходящей техники разбора).

T>А вот CYK, работающий над разными частями текста, неважно, в какой он грамматике, может быть весьма параллелен. Весьма.

Это если "разные части текста" можно чётко поделить на независимые части, т.е. найти позиции, где разборщик заведомо будет в нач. состоянии. В принципе, для большинства популярных ЯП — не сложно.


T>>>Результатом также считается отказ от написания модели. Это один из наиболее важных для этой дискуссии результатов.
V>>Модели процессора? И компилятор под него? Прямо здесь и сейчас? А ты связь с реальностью не теряешь, случаем?

T>Нет. Не надо компилятор. Надо модель процессора и программу для него. Программу можно и на ассемблере написать.

T>Я связь с реальностью не теряю. Написанием моделей я её поддерживаю. Я отвечаю за свою глупость (если моя идея глупа) своим потраченным временем.

T>Кстати, модель процессора пишется ну очень быстро: http://thesz.livejournal.com/440974.html

T>Это, максимум, день.

T>Модель ассоциативной памяти не менее быстро — ещё день.

Согласен, тема интересная, в свободное время я люблю экспериментировать, но для начала надо определиться собственно с целью моделирования. А для этого надо бы определиться с моим первым абзацем в этом посте. То, что алгоритм бабочки легко ложится на сумму ряда — этот трюк известный, его моделировать смысла нет.

T>Итого, за выходные ты сможешь подтвердить или опровергнуть свои слова.

Эмулятор написать-то не проблема. А вот написать парсер сложного языка — это за выходные не получится. Это тебе не программа перемножения матриц. А потом еще вручную перевести на этот "ассемблер". Программка на порядок объемнее получится, и времени займет соответственно. Так что, сначала хотелось бы ясности в теор. плане.


T>А я тебя очень сильно зауважаю.

Только из-за потраченного времени на твои любимые data-flow? В других областях не катит? Тут как-то проскакивал парень с мат.-образованием, попросил накидать эффективную инфраструктуру сетки для ИИ, чтобы экспериментировать с алгоритмами обучения. Я давно единомышленников ждал, т.к. тема мне очень интересна и последние лет много всё хочу ей вплотную заняться, поэтому уделил прилично свободного времени на это... Инфраструктуру накидал, простейший back propagation работает... а парень пропал... т.е. смысл мне кидаться туда-сюда, должен быть какой-то результат, поступательное движение вперёд. А сама тема ИИ, заметь, просто рай для параллельных вычислений, похлеще перемножения матриц. Так что, если уж тратить драгоценное свободное время, то на то, что интересно и можно будет использовать прямо сейчас. (По ИИ знаю пару направлений, где есть потребность прямо сейчас).


T>Я могу построить программу так, чтобы этого не произошло. Более того, я так и построю программу. У меня ассоциативная память ничего не умеет, кроме, как образовывать пары.

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


T>Автораспределение нагрузки страдает большим недостатком — оно невероятно неэффективно. Это было доказано в ходе исследований, в которых я частично участвовал (а потом подтвердил своей моделью). Буквально, выполнение той же программы с планированием, где будет выполняться тот или иной узел, происходит в несколько раз быстрее, чем без такого планирования.

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


V>>И твоё моделирование расчёта матрицы здесь — это хорошо, но, согласись, узкий класс задач.

T>Характерный. То же самое будет происходить со всеми вычислительными фортрановскими задачами, практически.

Там где прогрессии считать надо — то да, т.к. сама задача в том, что из кучи чисел после вычисления получаем одно.


T>Это плохой вариант — когда много АП и много ИУ и все связаны со всеми.

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

T>Что самое интересное, даже в этом случае АП делается по описанному мной варианту с одним входом и одним выходом, просто делается коммутационная сеть.

А как один вход и один выход обслужит одновременно несколько выч. блоков? Я предполагаю, что большинство операций (суммирование/сравнение/проверка бит и т.д.) будут выполняться выч. блоками никак не медленнее, чем операция парования в АП.


T>Поэтому впредь отталкивайся от лучшего варианта, например, моего.

Скромно и со вкусом.

T>>>>Ты ещё не читал, как я отношусь к преждевременным оптимизациям?
V>>>А оптимизация цены подложки? И не путаешь ли ты в одну кучу оптимизацию и следование требованиям? Быстродействующая ассоциативная память — это условие существования архитектуры как конкурентноспособного решения.
T>>Это не так. Здесь нужен баланс.
V>Мне бы хотелось прояснить твою позицию по data-flow, а то идёт уже которое сообщение подряд неконструктив. Мне (и уверен, не только мне), показалось, что flow-архитектуру двигают именно как средство масштабирования (наращивания кол-ва) вычислительных узлов, одновременно работающих над одними и теми же данными (смысла ради 1-го узла в data-flow практически нет), и способными эффективно делить м/у собой эти данные именно с помощью ассоциативной памяти.

Как всегда, дьявол спрятался в эпитете "эффективно" (as in "эффективный собственник").

Считается, что эффективно — это когда каждая АП может послать запрос на выполнение любому ИУ.

Исследования показали, что такая организация неэффективна, что есть организации с более высоким КПД.

V>И, хотя матрицы NxN можно избежать, согласен, но тут у нас по-любому будет матрица MxN (как в анкдоте), и еще порядка сложности M*Log(M) схема распределения по узлам _одновременно_ получаемых парных токенов. Поэтому, мне и кажется — что если речь зайдет о многих десятках выч. узлов, то никаким "балансом" не обойтись, безальтернативно нужна будет "серебрянная пуля" в виде этой непростой ассоциативной памяти. От того и позволил себе пофантазировать, относительно технологии изготовления этого узла (заметь — не всего проца, а только АП).

Поэтому ты отталкиваешься от неправильных посылок (в плане эффективности) и делаешь неправильные выводы.

T>>>>Пиши модель процессора, пиши для него программу разбора, попытайся получить взрывной параллелизм. О любых результатах расскажи.
V>>>Взрывной парралелизм для задачи разбора с возвратами не зависит от модели процессора, а исключительно от св-в грамматики и конкретной входной цепочки.
T>>Это не так. В перемножении матриц взрывной параллелизм получается вообще всегда, однако в моей модели его нет.
V>Странно, а в обычном алгоритме всего надо 3 ячейки, хранящие текущие состояния 3-х вложенных циклов.

И что это означает?

T>>Почему?
V>Потому что, "может быть распараллелено" и принципиально требует паралельного расчёта — это разные вещи. Матрица принципиально не требует, а ты лишь параллелишь до определённого уровня, подсчитывая и иерархически складывая частичные суммы. Ну блин, прямо Америку открыл, посмотри на БПФ и алгоритм "бабочки", и заодно станет понятно, почему он требует кол-во отсчётов, равное степени двойки — та же фигня. Можно и распараллелить, но принципиально паралеллить не требуется, в отличие от разбора грамматик, более высоких по уровню, чем регулярные и не сводящихся к LL(k), где к — фикированное (т.е. заведомо конечный коэф. возможного распараллеливания).

То есть, матричное умножение можно распараллелить, а разбор грамматик — принципиально требуется распараллелить.

Как ты думаешь, я на это куплюсь?

Вот из-за таких передёргиваний и отпадает всякое желание общаться.

T>>Беда в том, что грамматики строятся так, что большая их часть регулярна, а не контекстно-свободна. И уж тем более не LR. (источник PTAPG)
V>Эту чушь даже коментировать не хочу, надеюсь — ты описался. Если нет, то можно начать с простейшего — взять в любой форме записанную грамматику разбора простейших арифм. выражений — плюс/минус/умножить/скобки (благо в гугле полно ссылок и на её БНФ и PEG), и вот сведи мне её к регулярной. А заодно озвучь важное св-во регулярной грамматики, помня о котором всегда довольно быстро можно определить — является ли грамматика, описанная системой правил, регулярной или нет.

Ещё раз — сведения не мои, сведения из PTAPG. Это не я описался, это они, авторы PTAPG, жизнь положившие на разбор грамматик.

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

Два, ну, три. Ну, четыре места. А всяких списков переменных, списков аргументов, списков процедур и других списков и не-списков — кучами.

T>>А вот CYK, работающий над разными частями текста, неважно, в какой он грамматике, может быть весьма параллелен. Весьма.
V>Это если "разные части текста" можно чётко поделить на независимые части, т.е. найти позиции, где разборщик заведомо будет в нач. состоянии. В принципе, для большинства популярных ЯП — не сложно.

Вот. Как минимум, для большинства современных ЯП. Да даже для контекстно-зависимого C++ это возможно.

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

T>>>>Результатом также считается отказ от написания модели. Это один из наиболее важных для этой дискуссии результатов.
V>>>Модели процессора? И компилятор под него? Прямо здесь и сейчас? А ты связь с реальностью не теряешь, случаем?
T>>Нет. Не надо компилятор. Надо модель процессора и программу для него. Программу можно и на ассемблере написать.
T>>Я связь с реальностью не теряю. Написанием моделей я её поддерживаю. Я отвечаю за свою глупость (если моя идея глупа) своим потраченным временем.
T>>Кстати, модель процессора пишется ну очень быстро: http://thesz.livejournal.com/440974.html
T>>Это, максимум, день.
T>>Модель ассоциативной памяти не менее быстро — ещё день.
V>Согласен, тема интересная, в свободное время я люблю экспериментировать, но для начала надо определиться собственно с целью моделирования. А для этого надо бы определиться с моим первым абзацем в этом посте. То, что алгоритм бабочки легко ложится на сумму ряда — этот трюк известный, его моделировать смысла нет.

Вот в этом я тебе не помогу. Я не могу тебе ставить цели. Я попросил показать то, что мне интересно увидеть. Как ты будешь увиливать от выполнения эксперимента, меняя цели, меня не заботит.

И вообще. Вот я — люблю экспериментировать. Результаты экспериментов часто появляются в моём ЖЖ. Модель Sorting DFL — результат экспериментов.

А ты, пока, выглядишь, как человек, который любит говорить, что он любит экспериментировать.

Результатов нет. Сплошные голые слова.

T>>Итого, за выходные ты сможешь подтвердить или опровергнуть свои слова.
V>Эмулятор написать-то не проблема. А вот написать парсер сложного языка — это за выходные не получится. Это тебе не программа перемножения матриц. А потом еще вручную перевести на этот "ассемблер". Программка на порядок объемнее получится, и времени займет соответственно. Так что, сначала хотелось бы ясности в теор. плане.

Напиши генератор.

На современном ФЯ это дело делается очень быстро. Ещё пару выходных, максимум.

T>>А я тебя очень сильно зауважаю.
V>Только из-за потраченного времени на твои любимые data-flow? В других областях не катит? Тут как-то проскакивал парень с мат.-образованием, попросил накидать эффективную инфраструктуру сетки для ИИ, чтобы экспериментировать с алгоритмами обучения. Я давно единомышленников ждал, т.к. тема мне очень интересна и последние лет много всё хочу ей вплотную заняться, поэтому уделил прилично свободного времени на это... Инфраструктуру накидал, простейший back propagation работает... а парень пропал... т.е. смысл мне кидаться туда-сюда, должен быть какой-то результат, поступательное движение вперёд. А сама тема ИИ, заметь, просто рай для параллельных вычислений, похлеще перемножения матриц. Так что, если уж тратить драгоценное свободное время, то на то, что интересно и можно будет использовать прямо сейчас. (По ИИ знаю пару направлений, где есть потребность прямо сейчас).

Мне совершенно неинтересно ИИ. Мне интересен dataflow. Ты именно по нему высказываешь странные мысли, которые я бы хотел увидеть подтверждёнными экспериментально.

Не хочешь подтверждать, не надо. Для меня это не важно.

T>>Я могу построить программу так, чтобы этого не произошло. Более того, я так и построю программу. У меня ассоциативная память ничего не умеет, кроме, как образовывать пары.
V>Надеюсь, я уже пояснил, почему почему у тебя не произошло роста кол-ва токенов.

Нет, ты не пояснил.

Ты не пояснил, почему у меня всё равно высокий ILP.

T>>Автораспределение нагрузки страдает большим недостатком — оно невероятно неэффективно. Это было доказано в ходе исследований, в которых я частично участвовал (а потом подтвердил своей моделью). Буквально, выполнение той же программы с планированием, где будет выполняться тот или иной узел, происходит в несколько раз быстрее, чем без такого планирования.
V>Называя вещи своими именами, "упорядочивая вычисления" — фактически делая часть из них последовательно относительно друг-друга, а не хаотически. Дык, для задач накопления частичных сумм это запросто должно компилятором делаться, ибо алгоритм тут не будет зависеть от входных данных.

Планирование распределения — это не упорядочивание вычислений. Они независимы друг от друга.

V>>>И твоё моделирование расчёта матрицы здесь — это хорошо, но, согласись, узкий класс задач.
T>>Характерный. То же самое будет происходить со всеми вычислительными фортрановскими задачами, практически.
V>Там где прогрессии считать надо — то да, т.к. сама задача в том, что из кучи чисел после вычисления получаем одно.

Да.

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

T>>Это плохой вариант — когда много АП и много ИУ и все связаны со всеми.
V>Плохой, если нет возможности приоритезации, а так — очень даже теоретически хорош для _общего_случая_, когда парование токенов не предсказывается компилятором (в твоём примере это известно заранее).

Он может быть сколь угодно теоретически хорош, но он практически не реализуем.

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

V>Если в алгоритме if-ов больше гораздо, чем арифметических операций (т.е. программа преимущественно управляется внешними данными), то нужно расчитывать на произвольное появление пар.

Произвольное появление пар гарантируется семантикой упорядочения. Всё хорошо в АП с упорядочиванием токенов, ILP будет выявляться "на уровне" — можно больше суперскаляра, можно меньше.

T>>Что самое интересное, даже в этом случае АП делается по описанному мной варианту с одним входом и одним выходом, просто делается коммутационная сеть.
V>А как один вход и один выход обслужит одновременно несколько выч. блоков? Я предполагаю, что большинство операций (суммирование/сравнение/проверка бит и т.д.) будут выполняться выч. блоками никак не медленнее, чем операция парования в АП.

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

Мы можем (и должны) сделать ИУ многопоточным (multithreaded), чтобы задержки на длительные полезные операции не мешали выполнению уже готовых пар. Что я и сделал в своей модели, там даже несколько вариантов приоритетов вычислений в ИУ есть.

Поэтому пока выполняется одна пара, можно запустить ещё несколько на то же ИУ.

T>>Поэтому впредь отталкивайся от лучшего варианта, например, моего.
V>Скромно и со вкусом.

Если есть другие, отталкивайся от них. Мой вариант был приведён только в качестве примера лучшего варианта.

Главное, не отталкивайся от плохого варианта с многими большими АП и многими ИУ, соединёнными каждый-с-каждым.

И не приводи теоретических соображений. Приводи практические. Они мне понятней.

Здравствуйте, thesz, Вы писали:

T>Исследования показали, что такая организация неэффективна, что есть организации с более высоким КПД.

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


T>То есть, матричное умножение можно распараллелить, а разбор грамматик — принципиально требуется распараллелить.
T>Как ты думаешь, я на это куплюсь?

Я думал, что ты и так это знаешь, и лишь старался ненавязчиво напомнить, без пошлого "поди-ка почитай хоть немного на эту тему", что про стековый разбор, что про сдвиг-свертку, что про паралельный недетерминированный разбор, навроде Эрли.

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

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


T>Вот из-за таких передёргиваний и отпадает всякое желание общаться.

Оно пропадает от взаимного непонимания, и это проблема, в случае априорного нежелания разобраться в вопросе.


T>Ещё раз — сведения не мои, сведения из PTAPG. Это не я описался, это они, авторы PTAPG, жизнь положившие на разбор грамматик.

T>В паскале-подобном языке требующих контекстно-свободного разбора правил вот, сколько: арифметические выражения, структура блоков выполнения и... всё!

T>Два, ну, три. Ну, четыре места. А всяких списков переменных, списков аргументов, списков процедур и других списков и не-списков — кучами.

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

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

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

Как тебе такое кино? Реально полные грамматики являются контекстно зависимыми, но разборщики для них мы пишем только регулярные и КС, ибо не существует пока способа построить эффективный распознаватель КЗ для общего случая. И по статистике, имплементаций КС конечно же больше, чем имплементаций КЗ, а имплементаций РГ еще больше.

Прикольный феномен, не спорю, но говорить на основании этого, что самих грамматик такого-то типа больше — это пять.


T>>>А вот CYK, работающий над разными частями текста, неважно, в какой он грамматике, может быть весьма параллелен. Весьма.
V>>Это если "разные части текста" можно чётко поделить на независимые части, т.е. найти позиции, где разборщик заведомо будет в нач. состоянии. В принципе, для большинства популярных ЯП — не сложно.

T>Вот. Как минимум, для большинства современных ЯП. Да даже для контекстно-зависимого C++ это возможно.

До тех пор, пока макросами декларация класса не побъётся на отдельные файлы и тела методов — тоже. Вот с этими отдельными кусками без начала и без конца, да еще и с макрами — не так просто будет, ибо тот синтаксис, который допустим в теле декларации класса, недопустим в теле метода и наоборот. А еще прикольнее, если один и тот же файл с макрами включается дважды или даже трижды в разные места с разными определениями макросов... И типичный ведь приём в кроссплатформенной разработке.


T>Произвольное появление пар гарантируется семантикой упорядочения. Всё хорошо в АП с упорядочиванием токенов, ILP будет выявляться "на уровне" — можно больше суперскаляра, можно меньше.
T>Если есть другие, отталкивайся от них. Мой вариант был приведён только в качестве примера лучшего варианта.
T>Главное, не отталкивайся от плохого варианта с многими большими АП и многими ИУ, соединёнными каждый-с-каждым.
T>И не приводи теоретических соображений. Приводи практические. Они мне понятней.

Ты и практически это не показал. Еще раз, если не понял, упорядочивание токенов ортогонально размерности схемы поиска пар в АП, нельзя сравнивать метры и киллограммы. И тем более, что я могу увидеть на модели, на который мы вольны быстродействие сколь угодно многопортовой АП выбрать равным 1 такту? Чем больше будет ИУ, тем быстрее отработает алгоритм, это понятно и так.

Давай сделаем следующим образом, ты придумаешь хотя бы один довод, почему, например, в твоей модели с приоритезацией, если добавить десяток другой ИУ и сделать АП многопортовой на вход и выход, то это ухудшит такой-то показатель. Тогда сяду и сделаю, и сравню с твоей моделью, практически на "слабо".

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

У тебя ведь тоже была вполне конкретная цель — проверить идею с приоритезацией на эффект в экономии ресурсов. А тут в чём должна состоять цель?

T>>Исследования показали, что такая организация неэффективна, что есть организации с более высоким КПД.
V>Есть ссылки на исследование именно этого факта?

Я не знаю, были ли они опубликованы.

Если интересно, то попробуй связаться с Андреем Михайловичм Степановым по a_stepanov@ipmce.ru (или astepanov@ipmce.ru)

Он руководил этими исследованиями.

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

Соображения по поводу распределения токенов по узлам в моей статье тоже есть.

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

T>>То есть, матричное умножение можно распараллелить, а разбор грамматик — принципиально требуется распараллелить.
T>>Как ты думаешь, я на это куплюсь?
V>Я думал, что ты и так это знаешь, и лишь старался ненавязчиво напомнить, без пошлого "поди-ка почитай хоть немного на эту тему", что про стековый разбор, что про сдвиг-свертку, что про паралельный недетерминированный разбор, навроде Эрли.
V>Дело в том, что умножение матриц не порождает неизвестное заранее кол-во промежуточных результатов, стандартный алгоритм вообще не требует доп. памяти для промежуточных результатов.

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

V>Память под промежуточные результаты нам понадобилась именно в результате распараллеливания для хранения частичных сумм. И чем больше захочется уровня распараллеливания, тем больше нам надо промежуточных сумм. Если расчёт выполняет одно ИУ, как в твоём случае, то я вообще не вижу, где здесь распараллеливание и нафига козе баян? Сложить сумму из N членов это N-1 сложений, хоть иерархически, хоть последовательно.

Этот параграф означает, что идею ты так и не понял. Статью не читал, исходники не изучал, у меня (автора) не спрашивал.

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

Это, в целом, несколько отличается от "расчёт выполняет один ИУ" и, наверное, объясняет, "нафига козе баян".

V>А все эти алгоритмы недетерминированного разбора работают с помощью стека (или его аналога), для применениия системы правил на входную цепочку. Вместо стека некоторые алгоритмы перебирают все варианты "паралельно" (не физически параллельно, а алгоритмически), строя дерево вариантов, начиная от корня к произвольно кустящимся ветвям и листьям. Разве нам нужен стек или рекусия (принципиально заведомо неизвестной вложенности) для умножения матрицы?

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

Поэтому надо будет применять так называемые cache oblivious алгоритмы (не зависящие от размера кэша). В этом случае умножение матрицы выполняется путём рекурсивного разбиения её на все более мелкие части.

Что означает, что у нас, в принципе, неограниченная рекурсия!

T>>Вот из-за таких передёргиваний и отпадает всякое желание общаться.
V>Оно пропадает от взаимного непонимания, и это проблема, в случае априорного нежелания разобраться в вопросе.

Теперь вопрос: кто не желает разбираться в вопросе?

T>>Ещё раз — сведения не мои, сведения из PTAPG. Это не я описался, это они, авторы PTAPG, жизнь положившие на разбор грамматик.
T>>В паскале-подобном языке требующих контекстно-свободного разбора правил вот, сколько: арифметические выражения, структура блоков выполнения и... всё!
T>>Два, ну, три. Ну, четыре места. А всяких списков переменных, списков аргументов, списков процедур и других списков и не-списков — кучами.
V>Ндааа... И эти люди запрещают мне ковыряться в носу... Фишка в том, что достоверно узнать, что вот тут у нас список, а тут еще что-то можно лишь после распознавания полной грамматикой. Заодно и ошибки выявить.
V>Ход твоих мыслей я понял, он заключается в том, что из системы правил некоей КС грамматики довольно часто можно выдрать подмножества правил, которые будут принадлежать классу регулярных грамматик. Сказать что валялся — не сказать ничего. Скаже по секрету, что вообще-то компиляторы и так бьют на лексические и синтаксические анализаторы.
V>Да, предположим, что если "независимых" регулярных и КС грамматик "в мире одинаково", то учитывая общепринятое выделение регулярного подмножества из КС при разборе, регулярных получается больше... Наповал... (А что ты собрался делеать с этими "огрызками", кстати? Ведь без семантики ты не отличишь даже имя переменной от имени типа)

(замечу, что есть языки, где имена типов отличаются

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

V>Прикольный феномен, не спорю, но говорить на основании этого, что самих грамматик такого-то типа больше — это пять.

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

В случае, конечно, параллельного запуска обычных последовательных разборщиков.

T>>>>А вот CYK, работающий над разными частями текста, неважно, в какой он грамматике, может быть весьма параллелен. Весьма.
V>>>Это если "разные части текста" можно чётко поделить на независимые части, т.е. найти позиции, где разборщик заведомо будет в нач. состоянии. В принципе, для большинства популярных ЯП — не сложно.
T>>Вот. Как минимум, для большинства современных ЯП. Да даже для контекстно-зависимого C++ это возможно.
V>До тех пор, пока макросами декларация класса не побъётся на отдельные файлы и тела методов — тоже. Вот с этими отдельными кусками без начала и без конца, да еще и с макрами — не так просто будет, ибо тот синтаксис, который допустим в теле декларации класса, недопустим в теле метода и наоборот. А еще прикольнее, если один и тот же файл с макрами включается дважды или даже трижды в разные места с разными определениями макросов... И типичный ведь приём в кроссплатформенной разработке.

Видишь ли, ко мне поступит поток лексем с позициями в файлах (которые определяются #pragma). Я могу прочитать его часть нужного мне размера и отдать на откуп CYK. Сам же я буду заниматься лексическим разбором и запуском других CYK-разборов дальше. CYK-разборы построят мне наборы деревьев, которые я солью вместе.

По-моему, отличная модель.

T>>Произвольное появление пар гарантируется семантикой упорядочения. Всё хорошо в АП с упорядочиванием токенов, ILP будет выявляться "на уровне" — можно больше суперскаляра, можно меньше.
T>>Если есть другие, отталкивайся от них. Мой вариант был приведён только в качестве примера лучшего варианта.
T>>Главное, не отталкивайся от плохого варианта с многими большими АП и многими ИУ, соединёнными каждый-с-каждым.
T>>И не приводи теоретических соображений. Приводи практические. Они мне понятней.
V>Ты и практически это не показал. Еще раз, если не понял, упорядочивание токенов ортогонально размерности схемы поиска пар в АП, нельзя сравнивать метры и киллограммы. И тем более, что я могу увидеть на модели, на который мы вольны быстродействие сколь угодно многопортовой АП выбрать равным 1 такту? Чем больше будет ИУ, тем быстрее отработает алгоритм, это понятно и так.

В качестве модели пойдёт.

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

Я упоминал

Автор: thesz
Дата: 24.02.09

об этом:

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

V>Давай сделаем следующим образом, ты придумаешь хотя бы один довод, почему, например, в твоей модели с приоритезацией, если добавить десяток другой ИУ и сделать АП многопортовой на вход и выход, то это ухудшит такой-то показатель. Тогда сяду и сделаю, и сравню с твоей моделью, практически на "слабо".

Многопортовая АП имеет (условно) квадратичную сложность по площади. (Квадратично) растёт количество соединений внутри: Therefore, the wire pitch area increases as the square of the number of ports, and the transistor area increases linearly. At some point, it may be smaller and/or faster to have multiple redundant register files, with smaller numbers of read ports, than a single register file with all the read ports.

Поэтому надо всё сводить к однопортовой АП. И это известно, как делать.

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

(кстати, для регистрового файла суперскаляра такая схема будет значительно сложней, если она, вообще, возможна)

V>Еще раз возвращаюсь к тому, что у любого эксперимента должна быть цель. Ты пока ставишь цель "просто провести хоть какой-то эксперимент по датафлоу", тогда, типа, зауважаешь только лишь за сам факт проведения эксперимента. Это десад натуральный, и самое время попросить собеседника туда и прогуляться. Экспериментов мне и без датафлоу хватает, когда есть цель их проводить. Любой проектировщик достаточную часть времени экспериментами и так занят (если он адекваный проектировщик), дабы как можно меньше ошибок допустить на начальных стадиях любого проекта, особенно, если каждый раз идут новые технологии.

V>У тебя ведь тоже была вполне конкретная цель — проверить идею с приоритезацией на эффект в экономии ресурсов. А тут в чём должна состоять цель?

В проверке на реальных (насколько уж нас с тобой на реальность хватит) примерах особенностей выполнения программ на dataflow машине. Приобретение понимания этих особенностей и понимания, как можно обойти слабые места, буде мы их обнаружим.

Я проверял на умножении матриц. Ты, если хочешь, можешь попробовать реализовать параллельный разбор.

И это будет круто!

Здравствуйте, thesz, Вы писали:


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

Это как раз понятно, мне в твоей схеме не очень понравилось, что токены выходят во "внешнюю" систему — упорядочиватель (накладные расходы как бы, т.е. короткие небольшие вычисления будут произвоиться дольше, чем могли бы), с другой стороны, тут есть определённый бенефит (в конце написал).


T>Стандартный алгоритм разбора... тоже не требует особо большого количества памяти!

Какой из десятка примерно является стандартным? Если ты имел ввиду классческие рекурсивные стековые или сдвиг+свёртка, то они требуют памяти O(длина цепочки), но скорость их работы сильно зависит от входной цепочки и характера правил, при большом кол-ве откатов в ходе работы показатели вообще неприемлимы (т.к. степенная зависимость от кол-ва правил).

Приличная часть остальных разновидностей (кроме пресловутого ограниченного LL(k)) — это попытки разного рода уйти от прямой рекурсии в разборе, т.е. уход от степенной зависимости от времени, в сторону степенной зависимости по памяти.

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

T>Поэтому ещё раз объясняю: ...
T>Это, в целом, несколько отличается от "расчёт выполняет один ИУ" и, наверное, объясняет, "нафига козе баян".

Схему понял, но не "проникся" вначале, в конце поста подробней.


T>Поэтому надо будет применять так называемые cache oblivious алгоритмы (не зависящие от размера кэша). В этом случае умножение матрицы выполняется путём рекурсивного разбиения её на все более мелкие части.

T>Что означает, что у нас, в принципе, неограниченная рекурсия!

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


T>(замечу, что есть языки, где имена типов отличаются

а ну да, и как раз мейнстимовые.


T>Меня не волнует, имя это типа или имя переменной. Кусок программы я могу разобрать в обеих предположениях, а потом посмотреть, что же было до этого и взять необходимый результат разбора (будь то ошибка или правильный разбор).

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

V>>Прикольный феномен, не спорю, но говорить на основании этого, что самих грамматик такого-то типа больше — это пять.

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

У меня среднее приращение "параллельности" за шаг в среднем около 3-х на несложных, вообще-то, грамматиках EDI. Да, тупиковые ветви тоже постоянно отмирают на каждом шаге, так что на рельных входных данных более 15-20 вариантов на входной токен бывает редко. Но это не спроста — сами спецификации транзакций EDI так и разрабатывались, чтобы уменьшить общую "мощность" неоднозначности в процессе разбора. Т.е. вместо оптимизации структуры с т.з. бизнес-требований, вводят доп. сегменты и т.д., чтобы быстрее разбиралось. Во многих местах очевидно, что доп. сегменты, описывающие структуру, просто лишние, но без них степень параллелизма к концу разбора может стать просто неприемлимой. Кстати, в том же С++ есть запрет писать две подряд закрывающие скобки >> когда речь идёт о шаблонных параметрах, ибо возникает противоречие с оператором сдвига. И, хотя в каждом конкретном случае отличить можно запросто, компилятору придётся туго, т.к. он должен будет параллельно (или рекурсивно — не суть) еще рассматривать варианты, когда у нас открывающая — это просто оператор сравнения. И на кажом вложенном шаблоне мы получим доп. приращение параллельности.

В тех точках разбора, которые однозначны, вся параллельность "схлопывается" до 1-й версии, понятное дело. Тут еще загвоздка в том, что даже если для некоторого подмножества правил есть регулярные "участки", и даже, если эти участки совпадают на некотором достаточно длинном отрезке, это все-лишь будет означать отсутствие приращений "паралелльности" на этом отрезке, а вся предыдущая "паралельная" история разбора никуда не девается. В принципе, немного допилив тот же алгоритм Эрли, а именно — предварительно построив минимизированный НКА по системе правил (класический строит его прямо в процессе разбора), удаётся на тех самых участках (и вообще на любом входном символе), для всех паралельных вариантов делать лишь одно сравнение. Т.е. такое допиливание бесполезно в общем случае, но очень к месту, если у нас полно "похожих" правил. И опять же — это оптимизация под разбор одним процессором, в случае независимого разбора вариантов этот трюк не прокатит.


T>Я говорил ровно вот, что: из-за преобладания регулярных частей в произвольно взятой грамматике параллельность её разбора по реальному тексту много меньше ожидаемой.
T>В случае, конечно, параллельного запуска обычных последовательных разборщиков.

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

T>Видишь ли, ко мне поступит поток лексем с позициями в файлах (которые определяются #pragma). Я могу прочитать его часть нужного мне размера и отдать на откуп CYK. Сам же я буду заниматься лексическим разбором и запуском других CYK-разборов дальше. CYK-разборы построят мне наборы деревьев, которые я солью вместе.

T>По-моему, отличная модель.

Наверно, имел ввиду #include, а не #pragma, но не суть. Ты не уловил, в С++ многие файлы не являются синтаксически-законченными единицами, как обычные H или CPP файлы, а предназначены исключительно для включения в другие файлы с предварительной настройкой макросов. В общем, это разновидность кодогенерации. И, хотя в этих "кодогенераторах" много полезного и сложного С++ кода, такие файлы разбирать не получается без предварительно известной предыстории переопределения макросов. Если бы такой файл подключался лишь однажды, то еще хоть какая-то была возможность его разобрать, а т.к. он подклучается из разных мест, то открыв этот файл в редакторе, IDE не будет знать, какой из вариантов будущего включения разработчик держит в голове, работая с этим исходником.



T>>>Произвольное появление пар гарантируется семантикой упорядочения. Всё хорошо в АП с упорядочиванием токенов, ILP будет выявляться "на уровне" — можно больше суперскаляра, можно меньше.
T>>>Если есть другие, отталкивайся от них. Мой вариант был приведён только в качестве примера лучшего варианта.
T>>>Главное, не отталкивайся от плохого варианта с многими большими АП и многими ИУ, соединёнными каждый-с-каждым.
T>>>И не приводи теоретических соображений. Приводи практические. Они мне понятней.
V>>Ты и практически это не показал. Еще раз, если не понял, упорядочивание токенов ортогонально размерности схемы поиска пар в АП, нельзя сравнивать метры и киллограммы. И тем более, что я могу увидеть на модели, на который мы вольны быстродействие сколь угодно многопортовой АП выбрать равным 1 такту? Чем больше будет ИУ, тем быстрее отработает алгоритм, это понятно и так.

T>В качестве модели пойдёт.

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

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


T>Я упоминал

Автор: thesz
Дата: 24.02.09

об этом:

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

V>>Давай сделаем следующим образом, ты придумаешь хотя бы один довод, почему, например, в твоей модели с приоритезацией, если добавить десяток другой ИУ и сделать АП многопортовой на вход и выход, то это ухудшит такой-то показатель. Тогда сяду и сделаю, и сравню с твоей моделью, практически на "слабо".

T>Многопортовая АП имеет (условно) квадратичную сложность по площади. (Квадратично) растёт количество соединений внутри: Therefore, the wire pitch area increases as the square of the number of ports, and the transistor area increases linearly. At some point, it may be smaller and/or faster to have multiple redundant register files, with smaller numbers of read ports, than a single register file with all the read ports.

T>Поэтому надо всё сводить к однопортовой АП. И это известно, как делать.

T>(токены с одинаковым ключом попадут в один и тот же АП, поэтому пары будут производиться, как обычно. но параллельно на нескольких АП.

Да, не обратил внимания в начале на этот момент. Кол-во разрядов под ключ для 2-х АП может иметь на 1 разряд меньше (и схема сравнения тоже), для 4-х АП на 2 разряда меньше и так далее... жить можно.

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

T>Я проверял на умножении матриц. Ты, если хочешь, можешь попробовать реализовать параллельный разбор.

T>И это будет круто!

Есть еще один момент. Чтобы в полный рост экспериментировать на сложных задачах, нужен компилятор в этот ассемблер. А то в моём случае, немного подправь грамматику — и "компиллируй" вручную заново, а там нихрена себе сложность. Есть ссылки на принципы компиляции под dataflow, нумерования токенов и т.д.? Сложность я еще вижу в том, что для матриц, например, токены хранят сами данные, в то время как в моём случае токены больше будут хранить ссылку на структуры в памяти.

T>>Соображения по поводу распределения токенов по узлам в моей статье тоже есть.
T>>В моём случае так же выгодно посылать токены на то же самое устройство, если это возможно.
V>Это как раз понятно, мне в твоей схеме не очень понравилось, что токены выходят во "внешнюю" систему — упорядочиватель (накладные расходы как бы, т.е. короткие небольшие вычисления будут произвоиться дольше, чем могли бы), с другой стороны, тут есть определённый бенефит (в конце написал).

Короткие небольшие вычисления проходят через АП около ИУ. Они вытеснят оттуда "вычисления будущего" за счёт упорядочения.

T>>Поэтому надо будет применять так называемые cache oblivious алгоритмы (не зависящие от размера кэша). В этом случае умножение матрицы выполняется путём рекурсивного разбиения её на все более мелкие части.
T>>Что означает, что у нас, в принципе, неограниченная рекурсия!
V>Ах ты вот, про что... Только коэф рекурсии невероятно низкий получится, вряд ли будут перемножать матрицы, размерностью более, чем кол-во ячеек АП, а вот входные цепоки на порядки больше размерности — это запросто.

Обработка видео может привести к обработке матриц в несколько десятков и даже сотен тысяч элементов.

Там часто решаются задачи минимизации Ax=b методом наименьших квадратов, где x и b имеют размерности (2,3)xN (N — те самые десятки тысяч).

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

T>>(замечу, что есть языки, где имена типов отличаются
V>а ну да, и как раз мейнстимовые.

Haskell же, вроде, considered mainstream

Автор: thesz
Дата: 04.03.09

, нет?

T>>Меня не волнует, имя это типа или имя переменной. Кусок программы я могу разобрать в обеих предположениях, а потом посмотреть, что же было до этого и взять необходимый результат разбора (будь то ошибка или правильный разбор).
V>Синтаксически это может быть правильно для для обоих вариантов, а вот семантически — это уже lookup по таблицам символов. В том то и дело, что "смотреть" и "выбирать" может сам разборщик и сделает это гораздо эффективнее тебя, т.к. не заглядывает в таблицы.

И от этого lookup мне требуется только знание, тип ли идентификатор или переменная. Я могу занести текущее знание в таблицу и выполнять ветку с этим знанием. Или две ветки с разным знанием одновременно.

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

Я, вообще, оперирую понятиями комбинаторных разборщиков. Они создают наименьшее количество проблем при разработке.

Поэтому особой разницы между КСГ или КЗГ или даже РГ для меня нет.

T>>Я говорил ровно вот, что: из-за преобладания регулярных частей в произвольно взятой грамматике параллельность её разбора по реальному тексту много меньше ожидаемой.
V>У меня среднее приращение "параллельности" за шаг в среднем около 3-х на несложных, вообще-то, грамматиках EDI. Да, тупиковые ветви тоже постоянно отмирают на каждом шаге, так что на рельных входных данных более 15-20 вариантов на входной токен бывает редко. Но это не спроста — сами спецификации транзакций EDI так и разрабатывались, чтобы уменьшить общую "мощность" неоднозначности в процессе разбора. Т.е. вместо оптимизации структуры с т.з. бизнес-требований, вводят доп. сегменты и т.д., чтобы быстрее разбиралось. Во многих местах очевидно, что доп. сегменты, описывающие структуру, просто лишние, но без них степень параллелизма к концу разбора может стать просто неприемлимой. Кстати, в том же С++ есть запрет писать две подряд закрывающие скобки >> когда речь идёт о шаблонных параметрах, ибо возникает противоречие с оператором сдвига. И, хотя в каждом конкретном случае отличить можно запросто, компилятору придётся туго, т.к. он должен будет параллельно (или рекурсивно — не суть) еще рассматривать варианты, когда у нас открывающая — это просто оператор сравнения. И на кажом вложенном шаблоне мы получим доп. приращение параллельности.

То есть, у тебя параллельность порядка 15-20 нитей. Больше не получается. Что я и предполагал.

T>>Видишь ли, ко мне поступит поток лексем с позициями в файлах (которые определяются #pragma). Я могу прочитать его часть нужного мне размера и отдать на откуп CYK. Сам же я буду заниматься лексическим разбором и запуском других CYK-разборов дальше. CYK-разборы построят мне наборы деревьев, которые я солью вместе.
T>>По-моему, отличная модель.
V>Наверно, имел ввиду #include, а не #pragma, но не суть. Ты не уловил, в С++ многие файлы не являются синтаксически-законченными единицами, как обычные H или CPP файлы, а предназначены исключительно для включения в другие файлы с предварительной настройкой макросов. В общем, это разновидность кодогенерации. И, хотя в этих "кодогенераторах" много полезного и сложного С++ кода, такие файлы разбирать не получается без предварительно известной предыстории переопределения макросов. Если бы такой файл подключался лишь однажды, то еще хоть какая-то была возможность его разобрать, а т.к. он подклучается из разных мест, то открыв этот файл в редакторе, IDE не будет знать, какой из вариантов будущего включения разработчик держит в голове, работая с этим исходником.

С макросами — да, так. С синтаксическим анализом всё проще.

T>>В качестве модели пойдёт.
T>>Сейчас и тебе станет известно, что если применить хэщирование на входе, то входной поток шириной в несколько элементов можно переразбить статистически равномерно на произвольное количество потоков шириной в один элемент. Что означает, что мы можем задействовать однопортовые АП и получить результат, как для многопортовой.
V>Возвращаясь в сотый раз к нашим баранам, в случае минимизированных НКА/ДКА и так уже всё "кешировано" (эта часть минимизации называется минимизацией по входным сигналам). У меня разборщик смотрит не сам токен или символ, а его код из таблицы отображения, полученной в процессе минимизации КА.

Табличные разборщики — это ну очень двадцатый век. Современность — это функциональный подход. Особенно комбинаторный.

T>>(токены с одинаковым ключом попадут в один и тот же АП, поэтому пары будут производиться, как обычно. но параллельно на нескольких АП.
V>Да, не обратил внимания в начале на этот момент. Кол-во разрядов под ключ для 2-х АП может иметь на 1 разряд меньше (и схема сравнения тоже), для 4-х АП на 2 разряда меньше и так далее... жить можно.

V>Остаётся вопрос еще в равномерном распределении данных, если этих АП будет много, т.е. компилятор должен заранее знать, сколько у нас АП. В случае матриц такое статическое разбиение провести можно довольно точно, в отличие от разбора, где лишь "равновероятно", а там уже как карты лягут на конкретной входной последовательности. В любом случае, компилятор должен заранее знать кол-во этих блоков... т.е. байткоды и JIT-генерация будут рулить всё-равно.

Это уже надо смотреть.

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

В случае с типичными суперскалярами мы себя ограничиваем 32-мя регистрами. И простая реализация использовать большее количество не сможет. А сложная будет намного сложней. С dataflow всё, пока, выглядит по пристойней.

T>>И это будет круто!

V>Есть еще один момент. Чтобы в полный рост экспериментировать на сложных задачах, нужен компилятор в этот ассемблер. А то в моём случае, немного подправь грамматику — и "компиллируй" вручную заново, а там нихрена себе сложность. Есть ссылки на принципы компиляции под dataflow, нумерования токенов и т.д.? Сложность я еще вижу в том, что для матриц, например, токены хранят сами данные, в то время как в моём случае токены больше будут хранить ссылку на структуры в памяти.

Что ж. Придётся откапывать исходники.

Не обещаю быстрого результата, но постараюсь.

Здравствуйте, thesz, Вы писали:

T>Обработка видео может привести к обработке матриц в несколько десятков и даже сотен тысяч элементов.
T>Там часто решаются задачи минимизации Ax=b методом наименьших квадратов, где x и b имеют размерности (2,3)xN (N — те самые десятки тысяч).

А что за обработка? В большинстве алгоритмов сжатия с потерями идёт работа с фиксированными и очень небольшими блоками изображения.

T>Я, вообще, оперирую понятиями комбинаторных разборщиков. Они создают наименьшее количество проблем при разработке.
T>Поэтому особой разницы между КСГ или КЗГ или даже РГ для меня нет.

"Поиграться" и "поэкспериментировать" действительно разницы нет, в отличие от промышленного применения.

T>То есть, у тебя параллельность порядка 15-20 нитей. Больше не получается. Что я и предполагал.

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

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


T>Табличные разборщики — это ну очень двадцатый век.

Осталось уточнить, что ты имел ввиду под "табличными разборщиками". Ибо, многие стековые тоже пользуются таблицами.
Если же речь об LR(1)/LR(1) или регулярной грамматике, то таблица здесь — это таблица переходов ДКА, и ничего быстрее и проще в природе пока не существует.

Насчёт "20-й" век, я чего-то не понял юмора... может, ты имел ввиду, что иногда грамматики специально ограничивали, чтобы впихнуть в ДКА ввиду низкой вычислительной мощности машин 20-го века? Может быть, может быть... Но, если грамматика изначально из-за своих свойств ложится в ДКА, то не применять его — это банально совершить инженерную ошибку, практически продемонстрировать профнепригодность. Единственный случай, когда оправданно состояния представлять ф-иями для ДКА — это случай сильно разрежённой таблицы переходов — типичный для многих LR(1). Но опять же, решение о представлении состояний — это банальное инженерное решение, которое должно диктоваться не коссвенными причинами, типа предпочтений разработчика, а исключительно характеристиками грамматики.

T>Современность — это функциональный подход. Особенно комбинаторный.

Насколько я понял из статьи, они использовали параллельный недетерминированный восходящий разбор? А разбор по НКА, про который я тебе уже сколько говорю, по твоему — какой?
Или от того, что состояния НКА представлены не данными, а функциями, поменялась суть вещей? Я пока внимательно с кодом не разбирался, но есть ли у них такое же "схлопывание" эквивалентных состояний, которое получается само при работе по минимизированному НКА?

А вообще, ты бы и сам должен был заметить эквивалентность с моим подходом: An interesting feature of our parsers is the passing multiple continuations. These could also be implemented using the multi-function return feature proposed by Shivers (SFar) as an alternative to continuations.

Правда, ребята малость забываются, и подают так, будто Америку открыли, будто до них никто параллельным разбором не занимался и не представлял состояния автомата ф-ями. А ты говоришь 20-й век.
И еще не объяснили, почему именно на списках континюэйшенов. Разве это более эффективно чем каринг и список ф-ий?

Еще момент: у меня программа работает по заведомо неизвестной грамматике, ибо должна работать по описанию произвольных EDI-транзакций, т.е. я генерирую парсер в ходе работы, а они — "ручками", и у меня вызывает сомнение, как верифицировать полученный парсер. Мне, например, достаточно оттестировать правильность построения парсера для очень ограниченного кол-ва разновидностей правил (из которых можно строить заведомо произвольные описания грамматик), а им парсер надо тестировать на целевых данных... ха-ха, это даже не 20-й век.

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

Далее, про типизированность. Непонятны бенефиты от неё в случае, если не предполагается прямого редактирования AST человеком. Сейчас обычно AST строится на полиморфных типах, строят его абстрактные фабрики, обходят визиторами — и каждый раз всё вполне типизированно и достаточно для существующих задач. Технология generics в .Net позволит при надобности построить полностью типизированные узлы в рантайм, но у меня оччень большие сомнения в необходимости этого (обрати внимание на вывод типа узлов верхнего уровня — мрак). ИМХО, для полностью машинной обработки, типа задач компиляции ЯП, эта типизация — бесполезные накладные расходы.


T>То, что на размеры аппаратуры надо ориентироваться, это да. Другой вопрос, сколько это будет стоить, эта ориентация.

Сколько бы ни стоила, в случае большого кол-ва независимых небольших АП полагаться на автоматическое "гладкое" распределение данных вряд ли стоит.

T>В случае с типичными суперскалярами мы себя ограничиваем 32-мя регистрами. И простая реализация использовать большее количество не сможет. А сложная будет намного сложней. С dataflow всё, пока, выглядит по пристойней.

Потому как не используются спецрегистры по спецназначению. В типичном ассемлерном коде x86 добрая половина инструкций — это переливание из пустого в порожнее — перемещение данных м/у регистрами, в dataflow этого не требуется.


T>Что ж. Придётся откапывать исходники.

У вас был "ассемблер"?

Здравствуйте, Gaperton, Вы писали:

G>Прототип по технологии "кремний на германии" (правильно это называется так), который используется в СВЧ, стоил не так давно порядка 200К USD за запуск на фабрике IBM (открытые данные с mosis.com). Если мне память не изменяет. Прототип в кремнии — порядка 40К. Техпроцесс — 0,13. Это чтобы вы представляли себе, что означает "германий как раз таки недорогой".

G>Ни Интел, ни другие производители процессоров, включая IBM, которая имеет фабрики способные производить чипы по технологии "кремний-на-герминии", не полагаются на данную технологию при производстве процессоров. Данная технология сейчас применяется там, где без нее совсем никак. В основном, это сверхвысокочастотный RF-дизайн.

Кстати, порыл эту тему, и выяснилось, что ты малость поторопился. Да, подобная технология не получила широкого применения из-за "несовместимости" с существующими производственными линиями для кремния, от того и дорогая. Однако, в последнее время просачивается информация о том, что научились делать сплав кремния с германием (у них решётки близкого размера), и у этого сплава обнаружилась замечательная подвижность зарядов, не хуже, чем у арсенида галлия, а то и получше. Экспериментальные вентили свыше 250GHz отработали... (Не сплав, конечно, прямо кристалл выращивается из смешанных атомов)

Но самое примечательное, что механические и химические св-ва "сплава" таковы, что он сможет быть использован на имеющемся оборудовании под кремний. И Intel и IBM по слухам во всю работают по этому направлению, но подробностей не выдают даже под NDA... Так что, германий, похоже, всё-таки выстрелил. Еще бы научились добывать его менее затратно, а то в природе его гораздо больше серебра, но стоит как золото, и это часть проблемы.

T>>Обработка видео может привести к обработке матриц в несколько десятков и даже сотен тысяч элементов.
T>>Там часто решаются задачи минимизации Ax=b методом наименьших квадратов, где x и b имеют размерности (2,3)xN (N — те самые десятки тысяч).
V>А что за обработка? В большинстве алгоритмов сжатия с потерями идёт работа с фиксированными и очень небольшими блоками изображения.

Получение этой самой, как её... А! Фундаментальной матрицы.

T>>Табличные разборщики — это ну очень двадцатый век.
V>Осталось уточнить, что ты имел ввиду под "табличными разборщиками". Ибо, многие стековые тоже пользуются таблицами.
V>Если же речь об LR(1)/LR(1) или регулярной грамматике, то таблица здесь — это таблица переходов ДКА, и ничего быстрее и проще в природе пока не существует.
V>Насчёт "20-й" век, я чего-то не понял юмора... может, ты имел ввиду, что иногда грамматики специально ограничивали, чтобы впихнуть в ДКА ввиду низкой вычислительной мощности машин 20-го века? Может быть, может быть... Но, если грамматика изначально из-за своих свойств ложится в ДКА, то не применять его — это банально совершить инженерную ошибку, практически продемонстрировать профнепригодность.

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

Применять ДКА после фиксации грамматики на нескольких поколениях продукта и при отсутствии других ресурсов для оптимизации — самое оно.

Подход товарищей из gcc мне нравится больше всего.

V>Единственный случай, когда оправданно состояния представлять ф-иями для ДКА — это случай сильно разрежённой таблицы переходов — типичный для многих LR(1). Но опять же, решение о представлении состояний — это банальное инженерное решение, которое должно диктоваться не коссвенными причинами, типа предпочтений разработчика, а исключительно характеристиками грамматики.

Сроками получения конечного продукта.

По-моему, в этом и состоит различие наших позиций.

T>>Современность — это функциональный подход. Особенно комбинаторный.

V>Насколько я понял из статьи, они использовали параллельный недетерминированный восходящий разбор? А разбор по НКА, про который я тебе уже сколько говорю, по твоему — какой?
V>Или от того, что состояния НКА представлены не данными, а функциями, поменялась суть вещей? Я пока внимательно с кодом не разбирался, но есть ли у них такое же "схлопывание" эквивалентных состояний, которое получается само при работе по минимизированному НКА?

Детерминированный разбор очень интересен. Схлопывание состояний, AFAIK, там получается: http://people.cs.uu.nl/doaitse/Papers/1999/SofSem99.pdf

(немного другая техника, тем не менее)

V>А вообще, ты бы и сам должен был заметить эквивалентность с моим подходом: An interesting feature of our parsers is the passing multiple continuations. These could also be implemented using the multi-function return feature proposed by Shivers (SFar) as an alternative to continuations.
V>Правда, ребята малость забываются, и подают так, будто Америку открыли, будто до них никто параллельным разбором не занимался и не представлял состояния автомата ф-ями. А ты говоришь 20-й век.
V>И еще не объяснили, почему именно на списках континюэйшенов. Разве это более эффективно чем каринг и список ф-ий?

Продолжения это те же самые функции. Карринг делает замыкание.

В общем, то же, но в профиль.

V>Еще момент: у меня программа работает по заведомо неизвестной грамматике, ибо должна работать по описанию произвольных EDI-транзакций, т.е. я генерирую парсер в ходе работы, а они — "ручками", и у меня вызывает сомнение, как верифицировать полученный парсер. Мне, например, достаточно оттестировать правильность построения парсера для очень ограниченного кол-ва разновидностей правил (из которых можно строить заведомо произвольные описания грамматик), а им парсер надо тестировать на целевых данных... ха-ха, это даже не 20-й век.

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

V>С другой стороны, функциональное представление состояний автомата лучше ляжет на data-flow, т.к. именно для этой архитектуры это даст уменьшение косвенности (для обычных архитектур надо хранить адрес точки входа ф-ии, т.е. уменьшения косвенности для функционального представления нет).

Это у меня вызывает сомнение, но это надо проверить.

V>Далее, про типизированность. Непонятны бенефиты от неё в случае, если не предполагается прямого редактирования AST человеком. Сейчас обычно AST строится на полиморфных типах, строят его абстрактные фабрики, обходят визиторами — и каждый раз всё вполне типизированно и достаточно для существующих задач. Технология generics в .Net позволит при надобности построить полностью типизированные узлы в рантайм, но у меня оччень большие сомнения в необходимости этого (обрати внимание на вывод типа узлов верхнего уровня — мрак). ИМХО, для полностью машинной обработки, типа задач компиляции ЯП, эта типизация — бесполезные накладные расходы.

Типы убираются компилятором (type erasure).

Если у тебя p :: P String и q :: String -> P Var, то p >>= q всегда будет правильно собрана и всегда даст правильный результат. И на типы расходов не будет.

T>>То, что на размеры аппаратуры надо ориентироваться, это да. Другой вопрос, сколько это будет стоить, эта ориентация.
V>Сколько бы ни стоила, в случае большого кол-ва независимых небольших АП полагаться на автоматическое "гладкое" распределение данных вряд ли стоит.

Для определённых (вычислительных) задач можно.

T>>Что ж. Придётся откапывать исходники.
V>У вас был "ассемблер"?

Компилятор, почти.

Здравствуйте, thesz, Вы писали:


T>Сроками получения конечного продукта.

T>По-моему, в этом и состоит различие наших позиций.

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


T>Продолжения это те же самые функции. Карринг делает замыкание.

T>В общем, то же, но в профиль.

Я, наверно, недостаточно точно задал вопрос. ИМХО, продожения — это малость накладная технология, в сравнении с замыканиями, поэтому выбор этой технологии для меня и странен. Ну, разве что понятно желание сэкономить по строчке кода на каждую ф-ию.


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

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

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


V>>С другой стороны, функциональное представление состояний автомата лучше ляжет на data-flow, т.к. именно для этой архитектуры это даст уменьшение косвенности (для обычных архитектур надо хранить адрес точки входа ф-ии, т.е. уменьшения косвенности для функционального представления нет).

T>Это у меня вызывает сомнение, но это надо проверить.

Я имел ввиду, что доступ во внешнюю память может оказаться накладнее, чем более трудоёмкие вычисления внутри процессора. Чтобы это проверить, надо в модели задавать реальное отношение задержек для доступа во внешнюю память.

V>>Далее, про типизированность. Непонятны бенефиты от неё в случае, если не предполагается прямого редактирования AST человеком. Сейчас обычно AST строится на полиморфных типах, строят его абстрактные фабрики, обходят визиторами — и каждый раз всё вполне типизированно и достаточно для существующих задач. Технология generics в .Net позволит при надобности построить полностью типизированные узлы в рантайм, но у меня оччень большие сомнения в необходимости этого (обрати внимание на вывод типа узлов верхнего уровня — мрак). ИМХО, для полностью машинной обработки, типа задач компиляции ЯП, эта типизация — бесполезные накладные расходы.

T>Типы убираются компилятором (type erasure).

T>Если у тебя p :: P String и q :: String -> P Var, то p >>= q всегда будет правильно собрана и всегда даст правильный результат. И на типы расходов не будет.

Там имелся ввиду вывод конкретных типов узлов AST, насколько я понял. Т.е. компилятор для того же бинарного узла "+" должен будет нагенерить типов на всевозможные сочетания его операндов. ХЗ, насколько это надо для случая машинной обработки результата. С другой стороны мы можем поиметь эффективный статический полиморфизм при дальнейшей обработке, т.е. на некоторых языках это явно может сэкономить нам в строках высокоуровневого кода, который работает с результатами разбора. Напр., именно на подобных задачах С++ гораздо эффективнее тех же C# и Java из-за мощного статического полиморфизма, думаю, в Хаскеле тот же эффект.


T>>>То, что на размеры аппаратуры надо ориентироваться, это да. Другой вопрос, сколько это будет стоить, эта ориентация.
V>>Сколько бы ни стоила, в случае большого кол-ва независимых небольших АП полагаться на автоматическое "гладкое" распределение данных вряд ли стоит.

T>Для определённых (вычислительных) задач можно.

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

T>>Сроками получения конечного продукта.
T>>По-моему, в этом и состоит различие наших позиций.
V>Я вижу различие в подходе. Ты бы внимательней ту свою ссылку посмотрел, они там и минимизировали и решали неоднозначности ДО кодирования. В любом случае, они всё это делали вручную... На самом деле, основная разница в подходах именно в этом. Я считаю подобный подход неприемлимым в общем случае и отлаживаю грамматики в декларативном виде, а целевые парсеры и лексеры генерят тулзы, которые накопились за много лет. Всё это позволяет мне делать больше проб и экспериментов в единицу времени. При ручном кодировании паттерн-матчинга иногда вообще сложно/невозможно определить характеристики получившейся грамматики, а значит, верифицировать её — ты же там произвольным образом решаешь кофликты (зачастую, просто игнорируя, и беря наиболее удобный с т.з. кодера вариант). По сути, не по описанию некоего DSL генерится разборщик, а из получившихся св-в разборщика надо определять спецификацию DSL. Мне как бы сложно принять этот путь, хотя — это твоё демократическое право, как тебе решать подобные задачи.

Это совсем, совершенно, абсолютно неправильно.

Вот это:

По сути, не по описанию некоего DSL генерится разборщик, а из получившихся св-в разборщика надо определять спецификацию DSL.

В комбинаторах я пишу максимально декларативно, единственное, за чем мне надо следить — отсутствие левой рекурсии. Списки разбираются many1 p = pure ( <*> p <*> many p в отличии от LR, где many1 p = pure (flip ( <*> many p <*> p (many p = many1 p <|> return []). Нужна контекстно-зависимая грамматика — будет. Не нужна — не будет.

Быть может, не удастся добиться высокой оптимизации, но уж описание будет максимально оторвано от деталей реализации. Оно будет максимально "какое необходимо".


V>Неужели от нефиг делать наиболее популярный способ описания грамматик — это декларативный?

Наиболее популярный это обязательно самый лучший для всех возможных применений?

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

То есть, когда программе уже пара лет, как минимум.

V>>>Далее, про типизированность. Непонятны бенефиты от неё в случае, если не предполагается прямого редактирования AST человеком. Сейчас обычно AST строится на полиморфных типах, строят его абстрактные фабрики, обходят визиторами — и каждый раз всё вполне типизированно и достаточно для существующих задач. Технология generics в .Net позволит при надобности построить полностью типизированные узлы в рантайм, но у меня оччень большие сомнения в необходимости этого (обрати внимание на вывод типа узлов верхнего уровня — мрак). ИМХО, для полностью машинной обработки, типа задач компиляции ЯП, эта типизация — бесполезные накладные расходы.
T>>Типы убираются компилятором (type erasure).
T>>Если у тебя p :: P String и q :: String -> P Var, то p >>= q всегда будет правильно собрана и всегда даст правильный результат. И на типы расходов не будет.
V>Там имелся ввиду вывод конкретных типов узлов AST, насколько я понял. Т.е. компилятор для того же бинарного узла "+" должен будет нагенерить типов на всевозможные сочетания его операндов.

Ты, видимо, с алгебраическими типами не знаком?

Проведу ликбез.

data AST = Statement | Block [Statements]
data Statement = Assign VarRef Expr
data VarRef = VarRef String [Expr] -- v[i][j] => VarRef "v" [EVar "i",EVar "j"]
data Expr = EConst Literal | EVar String | Eplus Expr Expr
data Literal = LitInt Integer | LitChar Char

EPlus будет иметь ровно один тип входных операндов: Expr и Expr.

Мы можем усложнить структуру:

data AST = Statement | Block [Statements]
data Statement where Assign :: (VarRef ty) -> (Expr ty) -> Statement
data VarRef ty where VarRef :: (Lookup ty) -> [Expr Int] -> VarRef ty
data Expr ty where
  EConst :: Literal ty -> Expr ty
  EVar :: Lookup ty -> Expr ty
  Eplus :: Expr ty -> Expr ty -> Expr ty
data Literal ty where
    LitInt ::  Integer -> Literal Int
    LitChar :: Char -> Literal Char

Строка-имя-переменной заменена на Lookup ty, который получается по результатам выборки из окружения. То же и с литералами. Далее тип протаскивается и у нас получается невозможно сделать неправильное присваивание.

Здесь EPlus будет иметь... Снова один тип!

Вот у EVar и EConst код увеличится. Там происходит развилка.

А вот обработка EPlus наверху может быть специализирована (типы классов и тп). Но это не наша забота.

V>ХЗ, насколько это надо для случая машинной обработки результата. С другой стороны мы можем поиметь эффективный статический полиморфизм при дальнейшей обработке, т.е. на некоторых языках это явно может сэкономить нам в строках высокоуровневого кода, который работает с результатами разбора. Напр., именно на подобных задачах С++ гораздо эффективнее тех же C# и Java из-за мощного статического полиморфизма, думаю, в Хаскеле тот же эффект.

Вроде, как так и есть.

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

Вот функция: zip(i,j). Она берёт последовательность i3i2i1i0 и j3j2j1j0 и создаёт последовательность i3j3i2j2i1j1i0j0.

Возьмём индексы реального цикла i и j. Сдвинем их вправо на два разряда и пропустим через наш zip.

Мы получили индекс устройства (АП+ИУ), в котором будут выполняться 16 близко лежащих вычислений. Пересылки соседним вычислениям, что не поместились в наш индекс, будут иметь адресатом индекс АП+ИУ с небольшим расстоянием по манхеттенской метрике (max (abs (x-x') (abs (y-y'))). Половина всех пересылок будет проходить через всего один уровень иерархии (сортирующую псевдо-АП).

Как-то так.