На днях NVidia анонсировала новый процессор T10P для высокопроизводительных вычислений и новую модель 1U сервера Tesla S1070. Сервер содержит 4 процессора T10P, каждый по 240 GPU ядер (960 в сумме). Пиковая производительность 4 TFlops. Пропускная способность памяти 400GB/s.
Предполагаемая стоимость $8000. Т.е. вполне доступно для компаний и институтов.
Удивительное рядом.
Здравствуйте, remark, Вы писали:
R>Предполагаемая стоимость $8000. Т.е. вполне доступно для компаний и институтов. R>Удивительное рядом.
Ага только есть некоторые ограничения — все-таки это не обычный процессор, а графический. Он поддерживает несколько иную (мягко говоря) модель вычислений, и писать приложения под него придется с помощью библиотеки NVIDIA CUDA.
Но в целом использование GPU для мат. вычислений представляется очень интересной. Я сам сейчас этим занимаюсь
Мне очень нравится эта вещь http://graphics.cs.uiuc.edu/svn/kcrane/web/project_qjulia.html
Посмотрев исходники понятно что ничего "сверх" там нет. К сожалению на новых инвидиях не очень пашет, неизвестно почему (точнее говоря из-за дров, а дрова такие что вешают проц на 100% (при том что бесконечный цикл получается в коде GPU а не CPU), и с огромным трудом путём возвращается назад)... Пофиксить можно, если разобраться конечно. Но это к слову о вычислениях... Проц он и есть проц, дрова дровами... А так, если покумекать задачи всегда найдутся.
Здравствуйте, Sash_xp, Вы писали:
S_>Здравствуйте, remark, Вы писали:
R>>Предполагаемая стоимость $8000. Т.е. вполне доступно для компаний и институтов. R>>Удивительное рядом.
S_>Ага только есть некоторые ограничения — все-таки это не обычный процессор, а графический. Он поддерживает несколько иную (мягко говоря) модель вычислений, и писать приложения под него придется с помощью библиотеки NVIDIA CUDA. S_>Но в целом использование GPU для мат. вычислений представляется очень интересной. Я сам сейчас этим занимаюсь
а спарс матрицы решаются там хорошо? алгоритм навроде KLU интересует.
Здравствуйте, remark, Вы писали:
R>На днях NVidia анонсировала новый процессор T10P для высокопроизводительных вычислений и новую модель 1U сервера Tesla S1070. Сервер содержит 4 процессора T10P, каждый по 240 GPU ядер (960 в сумме). Пиковая производительность 4 TFlops. Пропускная способность памяти 400GB/s. R>Предполагаемая стоимость $8000. Т.е. вполне доступно для компаний и институтов. R>Удивительное рядом.
Вот ещё порадовало:
...it was only 11 years ago that the U.S. government spent approximately $33 million to build ASCI Red, one of the first supercomputers to achieve 1 billion floating point operations per second. The new graphics chips offer 1,000 times the power of that 1997-era supercomputer.
"Now we can go down to Fry's or Best Buy and buy a graphics board that has 1 teraflop of processing power for $600 or less...
Здравствуйте, merk, Вы писали:
S_>>Ага только есть некоторые ограничения — все-таки это не обычный процессор, а графический. Он поддерживает несколько иную (мягко говоря) модель вычислений, и писать приложения под него придется с помощью библиотеки NVIDIA CUDA. S_>>Но в целом использование GPU для мат. вычислений представляется очень интересной. Я сам сейчас этим занимаюсь
M>а спарс матрицы решаются там хорошо? алгоритм навроде KLU интересует.
Здравствуйте, Sergey Chadov, Вы писали:
SC>Здравствуйте, merk, Вы писали:
S_>>>Ага только есть некоторые ограничения — все-таки это не обычный процессор, а графический. Он поддерживает несколько иную (мягко говоря) модель вычислений, и писать приложения под него придется с помощью библиотеки NVIDIA CUDA. S_>>>Но в целом использование GPU для мат. вычислений представляется очень интересной. Я сам сейчас этим занимаюсь
M>>а спарс матрицы решаются там хорошо? алгоритм навроде KLU интересует.
SC>32-bit float only. Дальше думай сам
Здравствуйте, Sergey Chadov, Вы писали:
SC>Здравствуйте, merk, Вы писали:
SC>>>32-bit float only. Дальше думай сам
M>>это 23 бита на мантиссу которое? M>>Как трудно жить!
SC>Оно. Причем еще не до конца реализован стандарт IEEE в плане подержки NaN, используется неточное деление и корни.
все равно интересно. была бы возможность, я бы с этим повозился.
SC>>Оно. Причем еще не до конца реализован стандарт IEEE в плане подержки NaN, используется неточное деление и корни. M>все равно интересно. была бы возможность, я бы с этим повозился.
А в чем проблема? GeForce 8800 GT стоит 250$. Я вот себе купил. Теперь думаю как к диссеру прикрутить.
Здравствуйте, Sergey Chadov, Вы писали:
SC>Здравствуйте, merk, Вы писали:
SC>>>Оно. Причем еще не до конца реализован стандарт IEEE в плане подержки NaN, используется неточное деление и корни. M>>все равно интересно. была бы возможность, я бы с этим повозился.
SC>А в чем проблема? GeForce 8800 GT стоит 250$. Я вот себе купил. Теперь думаю как к диссеру прикрутить.
Здравствуйте, Sergey Chadov, Вы писали:
SC>Здравствуйте, merk, Вы писали:
SC>>>Оно. Причем еще не до конца реализован стандарт IEEE в плане подержки NaN, используется неточное деление и корни. M>>все равно интересно. была бы возможность, я бы с этим повозился.
SC>А в чем проблема? GeForce 8800 GT стоит 250$. Я вот себе купил. Теперь думаю как к диссеру прикрутить.
ну вот...русский человек сначала купит, затем повертит в руках, и задумаеццо — а куда это прикрутить???
европеец сначала придумает куда, потом станет полгода денег копить, потом купит и прикрутит. и что бы доход с нее был!
Здравствуйте, Sergey Chadov, Вы писали:
SC>Здравствуйте, merk, Вы писали:
SC>>>Оно. Причем еще не до конца реализован стандарт IEEE в плане подержки NaN, используется неточное деление и корни. M>>все равно интересно. была бы возможность, я бы с этим повозился.
SC>А в чем проблема? GeForce 8800 GT стоит 250$. Я вот себе купил. Теперь думаю как к диссеру прикрутить.
SC>>>>Оно. Причем еще не до конца реализован стандарт IEEE в плане подержки NaN, используется неточное деление и корни. M>>>все равно интересно. была бы возможность, я бы с этим повозился.
SC>>А в чем проблема? GeForce 8800 GT стоит 250$. Я вот себе купил. Теперь думаю как к диссеру прикрутить.
M>ну вот...русский человек сначала купит, затем повертит в руках, и задумаеццо — а куда это прикрутить??? M>европеец сначала придумает куда, потом станет полгода денег копить, потом купит и прикрутит. и что бы доход с нее был!
Да не, я давно на нее зуб точил, ждал пока подешевеет. А пока статейки читал, эмулятор ковырял. К тому же я не зря аспирант на кафедре высокопроизводительных вычислительных систем, параллельное программирование — мой непосредственный интерес. А тут такая девайсина недорого. Да и, что скрывать, в игрушки на ней тоже хорошо играть
Здравствуйте, merk, Вы писали:
SC>>А в чем проблема? GeForce 8800 GT стоит 250$. Я вот себе купил. Теперь думаю как к диссеру прикрутить.
M>для диссертации вот такая штучка будет ничего M>http://www.nvidia.com/object/tesla_c1060.html
это вещь хорошая, но нутром чую дорогая. По крайней мере по сравнению с 8800GT
Интересно то, что 4 гигабайта быстрой памяти сделать, похоже, нельзя, поэтому в Тесле пропускная способность памяти в 1.4 раза меньше (и для многих приложений это аукнется)
(c) http://www.gpgpu.ru/announces/gtx-280.html
S_>Скажем так, уже и double поддержимвается на новых процессорах серии GTX 200.
Ключевые слова "скажем так". Потому как так как оно там поддерживается, толку от него немного.
S_>К тому же для многих задач, скажем дискретной оптимизации может хватить и одинарной точности.
А для многих не хватит.
Здравствуйте, Sergey Chadov, Вы писали:
SC>Здравствуйте, Sash_xp, Вы писали:
S_>>Скажем так, уже и double поддержимвается на новых процессорах серии GTX 200. SC>Ключевые слова "скажем так". Потому как так как оно там поддерживается, толку от него немного.
Это да, верно.
S_>>К тому же для многих задач, скажем дискретной оптимизации может хватить и одинарной точности. SC>А для многих не хватит.
Так ведь даже и не каждая задача может быть эффективно распараллелена. Вы же учитесь на кафедре HPC и знаете, что универсальных вычислителей не бывает.
S_>>>К тому же для многих задач, скажем дискретной оптимизации может хватить и одинарной точности. SC>>А для многих не хватит. S_>Так ведь даже и не каждая задача может быть эффективно распараллелена. Вы же учитесь на кафедре HPC
Просто ради интереса, как расшифровывается НРС?
S_> и знаете, что универсальных вычислителей не бывает.
Так ведь хочется К тому же решение какой-либо задачи на оборудовании, на котором эта задача никогда не решалась, тоже вполне себе задача
Здравствуйте, Sergey Chadov, Вы писали:
S_>>>Ага только есть некоторые ограничения — все-таки это не обычный процессор, а графический. Он поддерживает несколько иную (мягко говоря) модель вычислений, и писать приложения под него придется с помощью библиотеки NVIDIA CUDA. S_>>>Но в целом использование GPU для мат. вычислений представляется очень интересной. Я сам сейчас этим занимаюсь
M>>а спарс матрицы решаются там хорошо? алгоритм навроде KLU интересует.
SC>32-bit float only. Дальше думай сам
В теслах поддерживается как 32, так и 64 битная IEEE-754 арифметика. Этоделает ее полностью пригодной для научных вычислений.
Здравствуйте, Sergey Chadov, Вы писали:
M>>это 23 бита на мантиссу которое? M>>Как трудно жить!
SC>Оно. Причем еще не до конца реализован стандарт IEEE в плане подержки NaN, используется неточное деление и корни.
Утверждается, что IEEE-754 реализован полностью для 32 и 64 битных чисел. Стандарт регламентирует не только представление чисел, но и точность операций над ними.
Здравствуйте, remark, Вы писали:
R>На днях NVidia анонсировала новый процессор T10P для высокопроизводительных вычислений и новую модель 1U сервера Tesla S1070. Сервер содержит 4 процессора T10P, каждый по 240 GPU ядер (960 в сумме). Пиковая производительность 4 TFlops. Пропускная способность памяти 400GB/s. R>Предполагаемая стоимость $8000. Т.е. вполне доступно для компаний и институтов. R>Удивительное рядом.
AMD FireStream 9170
# Parallel processing architecture with 320 stream cores
# Up to 500 GFLOPs single precision performance
# 2GB GDDR3 on-board memory
# Double Precision Floating Point
# Asynchronous DMA, allowing data transfers without interrupting streams processor or CPU
Следует отметить поддержку Double Precision Floating Point, т.е. упор на scientific вычисления.
1 There is no dynamically configurable rounding mode; however, most of the
operations support IEEE rounding modes, exposed via device functions;
2 There is no mechanism for detecting that a floating-point exception has occurred
and all operations behave as if the IEEE-754 exceptions are always masked, and
deliver the masked response as defined by IEEE-754 if there is an exceptional
event; for the same reason, while SNaN encodings are supported, they are not
signaling;
3 Absolute value and negation are not compliant with IEEE-754 with respect to
NaNs; these are passed through unchanged;
For single-precision floating-point numbers only: 1 Addition and multiplication are often combined into a single multiply-add
instruction (FMAD), which truncates the intermediate result of the
multiplication;
2 Division is implemented via the reciprocal in a non-standard-compliant way;
3 Square root is implemented via the reciprocal square root in a non-standardcompliant
way;
4 For addition and multiplication, only round-to-nearest-even and
round-towards-zero are supported via static rounding modes; directed
rounding towards +/- infinity is not supported;
5 Denormalized numbers are not supported; floating-point arithmetic and
comparison instructions convert denormalized operands to zero prior to the
floating-point operation;
6 Underflowed results are flushed to zero;
7 The result of an operation involving one or more input NaNs is the quiet
NaN of bit pattern 0x7fffffff; note that;
Для новых тесл и gforce 260/280 есть и single и double. Однако темп запуска double в 10-12 меньше темпа запуска single http://forums.nvidia.com/index.php?showtopic=75452. То есть хорошая производительность есть только для single. А при операциях с ними есть небольшое несоответствие с IEEE 754. И еще скорее всего в бюджетных чипах double-а не будет.
Здравствуйте, remark, Вы писали:
R>На днях NVidia анонсировала новый процессор T10P для высокопроизводительных вычислений и новую модель 1U сервера Tesla S1070. Сервер содержит 4 процессора T10P, каждый по 240 GPU ядер (960 в сумме). Пиковая производительность 4 TFlops. Пропускная способность памяти 400GB/s. R>Предполагаемая стоимость $8000. Т.е. вполне доступно для компаний и институтов. R>Удивительное рядом.
R>http://www.ddj.com/hpc-high-performance-computing/208404203?cid=RSSfeed_DDJ_All R>http://www.nvidia.com/object/tesla_s1070.html
Multicore приходит и в мир встраиваемых систем: SEAforth® 40C18
The SEAforth 40C18 is one of the IntellaSys® Scalable Embedded Array multicore processors. It has an array of 40 cores; each of the C18 cores is a complete computer, with its own ROM, RAM, and interprocessor communication. Together they can deliver up to 26 billion operations per second. The SEAforth 40C18 is a perfect embedded computer solution for consumer applications that demand high processing power and low power dissipation.
With 40 nodes to work with, designers can dedicate groups of them to specific tasks such as FFT and DFT algorithms. The result is a tightly coupled, extremely versatile user-defined group of dedicated processors assigned to specific tasks. Some can be doing highly compute-intensive audio processing, while others handle wireless interfaces, external memory, and user interface functions. And since each core has its own ROM and RAM, there is less need to go to external memory.
Each core runs asynchronously, at the full native speed of the silicon. During interprocessor communication, synchronization happens automatically; the programmer doesn’t have to create synchronization methods. Communication happens between neighbors through dedicated ports. A core waiting for data from a neighbor goes to sleep, dissipating less than one microwatt. Likewise, a core sending data to a neighbor not ready to receive it goes to sleep until that neighbor accepts it.
И программируется вся эта штука на FORTH.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, little_alex, Вы писали:
_>Здравствуйте, Gaperton, Вы писали:
G>>Утверждается, что IEEE-754 реализован полностью для 32 и 64 битных чисел. Стандарт регламентирует не только представление чисел, но и точность операций над ними.
G>>http://www.nvidia.ru/object/tesla_s1070_ru.html _>Это реклама. Смотреть надо документ для разработчиков.
Это ерунда. Фатальное несоответствие IEEE-754 — это уполовиненные по площади умножители. Которые дают погрешность в младших разрядах. Именно такие умножители были в видеокартах DX8.1, и, кстати, в ранних суперкомпьютерах Cray . Часть стандарта IEEE 754, которая действительно важна для научных вычислений — это правила округления результатов арифметики. Они соблюдаются — то есть арифметика там полная. Приведенные тобой отклонения — ерунда.
Здравствуйте, Gaperton, Вы писали:
G>Утверждается, что IEEE-754 реализован полностью для 32 и 64 битных чисел. Стандарт регламентирует не только представление чисел, но и точность операций над ними.
Угу. В Tesla C1060, S1070 версия compute capability 1.3, как и в GTX. То есть, long double поддерживается, но с некоторыми ограничениями, описанными выше.
Здравствуйте, byleas, Вы писали:
B>Здравствуйте, Gaperton, Вы писали:
G>>Утверждается, что IEEE-754 реализован полностью для 32 и 64 битных чисел. Стандарт регламентирует не только представление чисел, но и точность операций над ними. B>Угу. В Tesla C1060, S1070 версия compute capability 1.3, как и в GTX. То есть, long double поддерживается, но с некоторыми ограничениями, описанными выше.
как и написано выше, это ерунда. По сравнению с уполовиненными умножителями. Описать, что это такое?
Здравствуйте, Gaperton, Вы писали:
G>как и написано выше, это ерунда. По сравнению с уполовиненными умножителями. Описать, что это такое?
Может быть и ерунда. Но надо иметь ввиду, что результат вычислений на GPU может оказаться не равным результату IEEE-совместимого вычислителя. По крайней мере для single чисел.
Здравствуйте, little_alex, Вы писали:
_>Здравствуйте, Gaperton, Вы писали:
G>>как и написано выше, это ерунда. По сравнению с уполовиненными умножителями. Описать, что это такое? _>Может быть и ерунда. Но надо иметь ввиду, что результат вычислений на GPU может оказаться не равным результату IEEE-совместимого вычислителя. По крайней мере для single чисел.
Сравнивать на равенство плавающую запятую все равно нельзя . Вопрос ровно в том, соблюдается ли IEEE в области округления результатов арифметики.
Уполовиненный умножитель — это очень простая штука. Представь себе умножение в столбик. Перемножил два 32-х разрядных числа — получил 64-х разрядное. Вот, теперь представь это умножение на бумажке, расписанное в столбик, в двоичном коде.
Ты смотришь на матричный умножитель. А теперь, прикинь — нафиг нам младшие 32 разряда, если это, скажем, мантисса — все равно она будет сдвинута, и эти разряды отбросятся? Ну, она на самом деле другой длины, но это неважно. Важно то, что у разработчика возникает соблазн просто выбросить правую половину этого ромбика, в два раза съкономив площадь умножителя, и получить погрешность в нескольких младших разрядах мантиссы.
Так и поступали в графических ускорителях. Умножитель — самое большое по площади устройство из ходовой арифметики, а точность в графике все равно не нужна. Глаз разницы не заметит.
И так поступал хитрый Сеймур Крей, до тех пор, пока не придумали IEEE 754.
С точки зрения научных вычислений — 32-х битные floats сами по себе непригодны для многих задач, со своей короткой мантиссой, а с уполовиненными умножителями — так ваще никуда не годятся.
Поэтому, соблюдение IEEE в части точности операций — это основное. А точность соблюдается. Все. А что там с NaN-ами — да черт с ними. Какая разница.
Re: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, eao197, Вы писали:
E>Multicore Is Bad News For Supercomputers -- для некоторых классов задач память становится преградой для повышения производительности при увеличении числа ядер.
Ну во-первых, массовый 32-ядерный процессор ожидается в следующем году — Larabee: http://en.wikipedia.org/wiki/Larrabee_(GPU)
Хоть оффициально это и GPU, но он будет иметь x86 набор инструкций. Т.е. никаких CUDA, BROOK и т.д. и никаких только перемножений матриц, алгоритм любой сложности, написанный на С/С++ можно будет сгрузить на GPU.
Во-вторых, есть "настольные" системы с 2/4 процессорами, это не многоядерный процессор, но всё же. Похоже, что с появлением многоядерных процессоров, люди стали более толерантны и к многопроцессорным серверам. Т.е. если у нас 8-ми ядерные процессоры с 2 HT поками на ядро, + 4 процессора, то получаем в сумме 64 аппартных потока.
Плюс, Niagara II имеет 64 аппаратных потока.
Ну а если именно про настольные многоядерные процессоры x86 — то фиг его знает. Сейчас никто не знает. Интел планирует процессоры только на 4 года (2 поколения) вперёд, что будет в них известно, что будет дальше — никому не известно. Если люди, которые думают, что знают, что будет или что должно быть. Но это ещё не определено.
С уверенностью можно сказать только: (1) производительность процессоров будет расти, (2) за счёт повышения тактовой частоты в ближайшую декаду сещественного роста не предвидится, (3) когда Интел спросили, сильно ли они теперь привязаны к многоядерности (типа а может нам стоит просто переждать) — они ответили, что Да, Сильно и надолго (типа ждать не стоит).
С памятью — это известная проблема. Некоторые алгоритмы даже и на одном ядре в память упираются.
По-поводу того, что люди думают. Думают о разном.
Думают и о "сэндвичных" архитектурах, где ядра перемешаны с локальной памятью. Прецеденты уже имеются. Да и IBM Cell BE в некотором роде такая архитектура.
Думают о NUMA, т.е. в ядре имеется несколько контроллеров памяти, каждый присоединён к своей локальной памяти — очевидная масштабируемость пропускной способности к памяти.
Думают о неоднородных архитектурах. Причём неоднородных как по функциональным возможностям, так и по тактовой частот. Т.е. в процессоре несколько ядер, но они различаются по поддерживаим функциям и/или частоте. Опять же Cell BE.
Думают, что в них добавлять — то ли HTM, то ли аппаратную поддержку обмена сообщениями. Кстати, аппаратный обмен сообщениями тоже поможет решить проблему пропускной способности — ядра будут обмениваться данными не через память, а напрямую. Т.е. такой мини-кластер на процессоре (CoC — Cluster on a Chip).
Правда, для всего этого в контексте массовых процессоров есть серьёзная проблема — рядовые пользователи не готовы к таким наворотам... правда и к multicore они тоже не были готовы...
Но научных статей и прототипов и даже рабочих специализированных процессоров — хоть отбавляй. Вот тут можно поглядеть интересные картинки: http://en.wikipedia.org/wiki/TILE64 http://en.wikipedia.org/wiki/Cell_(microprocessor) http://www.clearspeed.com/products/csx700/ http://www.stretchinc.com/products/s6000.php
Я бы не брался предсказывать, что нас ожидает даже лет через 8. Толи это будет просто постепенный рост числа ядер + небольшие навороты типа NUMA; толи что-то принципиально новое.
Но я думаю, что часть "транзисторного потенциала" в контексте массовых процессоров в следующую декаду будет так же потрачена на интеграцию "перифирии" в процессоры. Т.е. прямо в процессоре будет графический процессор, аудио процессор, сетевая карта + ряд специализированных ускорителей (XML). Что ещё надо производителям ноут/нет-буков? При этом неиспользуемые ядра графического процессора могут прозрачно использовтаься как обычные ядра. А сетевая карта будет закачивать данные прямо в кэш процессора.
E>Multicore Is Bad News For Supercomputers -- для некоторых классов задач память становится преградой для повышения производительности при увеличении числа ядер.
Память вредна.
Поток данных — data flow, — полезен.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[3]: Может массовых процессоров 32+ ядрами и не будет?
R>Ну во-первых, массовый 32-ядерный процессор ожидается в следующем году — Larabee: R>http://en.wikipedia.org/wiki/Larrabee_(GPU) R>Хоть оффициально это и GPU, но он будет иметь x86 набор инструкций. Т.е. никаких CUDA, BROOK и т.д. и никаких только перемножений матриц, алгоритм любой сложности, написанный на С/С++ можно будет сгрузить на GPU.
Позвольте сказать "ха-ха" три раза.
Поверю, когда увижу.
R>Плюс, Niagara II имеет 64 аппаратных потока.
Там задача другая. А вот числодробилка от Sun под названием Rock будет иметь поменьше потоков.
R>С памятью — это известная проблема. Некоторые алгоритмы даже и на одном ядре в память упираются.
Cache oblivious algorithms to the rescue?
R>По-поводу того, что люди думают. Думают о разном. R>Думают и о "сэндвичных" архитектурах, где ядра перемешаны с локальной памятью. Прецеденты уже имеются. Да и IBM Cell BE в некотором роде такая архитектура.
Проблемы с компиляцией.
R>Думают о NUMA, т.е. в ядре имеется несколько контроллеров памяти, каждый присоединён к своей локальной памяти — очевидная масштабируемость пропускной способности к памяти.
Сложность реализации и балансировки.
R>Думают о неоднородных архитектурах. Причём неоднородных как по функциональным возможностям, так и по тактовой частот. Т.е. в процессоре несколько ядер, но они различаются по поддерживаим функциям и/или частоте. Опять же Cell BE.
Проблемы с компиляцией.
R>Думают, что в них добавлять — то ли HTM, то ли аппаратную поддержку обмена сообщениями. Кстати, аппаратный обмен сообщениями тоже поможет решить проблему пропускной способности — ядра будут обмениваться данными не через память, а напрямую. Т.е. такой мини-кластер на процессоре (CoC — Cluster on a Chip).
Купили-таки их. Повезло.
R>Но я думаю, что часть "транзисторного потенциала" в контексте массовых процессоров в следующую декаду будет так же потрачена на интеграцию "перифирии" в процессоры. Т.е. прямо в процессоре будет графический процессор, аудио процессор, сетевая карта + ряд специализированных ускорителей (XML).
Смысла нет. Кристалл растёт, выход рабочих образцом уменьшается. Очень дорого так делать.
Я бы ставил на обратное — на микросборки и межкристальный обмен наподобие HyperTransport.
R> Что ещё надо производителям ноут/нет-буков? При этом неиспользуемые ядра графического процессора могут прозрачно использовтаься как обычные ядра. А сетевая карта будет закачивать данные прямо в кэш процессора.
Вот в ноутбуке это прямо-таки необходимо, ага.
Ну, ладно, не буду мешать полёту мысли.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[3]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, thesz, Вы писали:
E>>Multicore Is Bad News For Supercomputers -- для некоторых классов задач память становится преградой для повышения производительности при увеличении числа ядер.
T>Память вредна.
T>Поток данных — data flow, — полезен.
Где-то уже были аннонсированы версии Windows, Linux, Solaris, FreeBSD, заточенных под архитектуры с data flow?
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[3]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, thesz, Вы писали:
E>>Multicore Is Bad News For Supercomputers -- для некоторых классов задач память становится преградой для повышения производительности при увеличении числа ядер.
T>Память вредна.
T>Поток данных — data flow, — полезен.
Там проблем ещё больше. Нет?
И знаешь как говорится: лучше двое старых граблей, чем одни новые.
T>>Память вредна. T>>Поток данных — data flow, — полезен.
E>Где-то уже были аннонсированы версии Windows, Linux, Solaris, FreeBSD, заточенных под архитектуры с data flow?
Это ты что хотел сказать?
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[5]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, thesz, Вы писали:
T>>>Память вредна. T>>>Поток данных — data flow, — полезен.
E>>Где-то уже были аннонсированы версии Windows, Linux, Solaris, FreeBSD, заточенных под архитектуры с data flow?
T>Это ты что хотел сказать?
подозреваю это был намек на тонкое обстоятельство что пока не будет операционных систем хоть как-то поддерживающих то dataflow ничего не светит
Re[5]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, thesz, Вы писали:
T>>>Память вредна. T>>>Поток данных — data flow, — полезен.
R>>Там проблем ещё больше. Нет?
T>Нет.
R>>И знаешь как говорится: лучше двое старых граблей, чем одни новые.
T>Двое новых граблей, обычно, имеют длину рукоятки чуть меньше, чем по пояс.
Здравствуйте, thesz, Вы писали:
R>>Плюс, Niagara II имеет 64 аппаратных потока.
T>Там задача другая. А вот числодробилка от Sun под названием Rock
будет иметь поменьше потоков.
Задача другая чем у чего? Чем у массовых процессоров?
R>>С памятью — это известная проблема. Некоторые алгоритмы даже и на
одном ядре в память упираются.
T>Cache oblivious algorithms to the rescue?
Какой Cache oblivious алгоритм сложения массивов?
R>>По-поводу того, что люди думают. Думают о разном. R>>Думают и о "сэндвичных" архитектурах, где ядра перемешаны с
локальной памятью. Прецеденты уже имеются. Да и IBM Cell BE в
некотором роде такая архитектура.
T>Проблемы с компиляцией.
Ты пытался копилировать под него "обычную" программу? И надеялся, что
она будет хорошо работать?
R>>Думают о NUMA, т.е. в ядре имеется несколько контроллеров памяти,
каждый присоединён к своей локальной памяти — очевидная
масштабируемость пропускной способности к памяти.
T>Сложность реализации и балансировки.
А у dataflow значит нет проблем со сложность реализации и других. Ну здорово! Жалко, что мужики ещё не знают, и всё ещё мутят там какие-то подходы для увеличения гранулярности, прикручивают явный поток управления на высоком уровне и т.д. Память-то, кстати, тоже у всех dataflow процессоров общего назначения имеется.
П можешь привести хоть один промышленный dataflow процессор общего назначения (не спец. кристалл и не ПЛИС), который использует dataflow и на высоком и на низком уровне? Если это такая замечательная штука без проблема, должны же быть какие-то.
R>>Думают о неоднородных архитектурах. Причём неоднородных как по
функциональным возможностям, так и по тактовой частот. Т.е. в
процессоре несколько ядер, но они различаются по поддерживаим функциям
и/или частоте. Опять же Cell BE.
T>Проблемы с компиляцией.
Никто обратного и не утверждает. Проблем с компиляцией нет только у симметричных многоядерных императивных процессоров.
R>>Думают, что в них добавлять — то ли HTM, то ли аппаратную поддержку
обмена сообщениями. Кстати, аппаратный обмен сообщениями тоже поможет
решить проблему пропускной способности — ядра будут обмениваться
данными не через память, а напрямую. Т.е. такой мини-кластер на
процессоре (CoC — Cluster on a Chip).
T>О! Неужто до data flow додумались?..
А ты думал, ты один в мире про dataflow знаешь? Ты никакого prior art не видел?
R>>Но я думаю, что часть "транзисторного потенциала" в контексте
массовых процессоров в следующую декаду будет так же потрачена на
интеграцию "перифирии" в процессоры. Т.е. прямо в процессоре будет
графический процессор, аудио процессор, сетевая карта + ряд
специализированных ускорителей (XML).
T>Смысла нет. Кристалл растёт, выход рабочих образцом уменьшается.
Очень дорого так делать.
T>Я бы ставил на обратное — на микросборки и межкристальный обмен
наподобие HyperTransport.
Кристалл и так будет расти. Или ты ставишь на то, что со следующего года число транзисторов не будет расти?
Если ты не заметил, то на кристалл уже затащили всё, что было рядом — сопроцессоры, кэши, контроллеры памяти, контроллеры меж-процессорного взаимодействия (этот же HyperTransport и QPI). Ну и кто жалуется?
R>> Что ещё надо производителям ноут/нет-буков? При этом
неиспользуемые ядра графического процессора могут прозрачно
использовтаься как обычные ядра. А сетевая карта будет закачивать
данные прямо в кэш процессора.
T>Вот в ноутбуке это прямо-таки необходимо, ага.
T>Ну, ладно, не буду мешать полёту мысли.
Забавно слышать про полёт мысли от человека, который помешан на dataflow и пророчит ему мировое господство
Здравствуйте, remark, Вы писали:
R>Но я думаю, что часть "транзисторного потенциала" в контексте массовых процессоров в следующую декаду будет так же потрачена на интеграцию "перифирии" в процессоры. Т.е. прямо в процессоре будет графический процессор, аудио процессор, сетевая карта + ряд специализированных ускорителей (XML). Что ещё надо производителям ноут/нет-буков? При этом неиспользуемые ядра графического процессора могут прозрачно использовтаься как обычные ядра. А сетевая карта будет закачивать данные прямо в кэш процессора.
Ох сомнения берут. Например аудио процессор... ну так, для поддержки какого-нибудь AC97 ещё куда ни шло. Что б было. А если по серьёзнее взяться — то оно сразу же не подходит, выключается, душится и забывается что там такое есть.
Ну и получается что привет внешним устройствам на FireWire, PCI и т.п.
С другими компонентами думаю приблизительно так же...
Re[4]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, fddima, Вы писали:
F>Здравствуйте, remark, Вы писали:
R>>Но я думаю, что часть "транзисторного потенциала" в контексте массовых процессоров в следующую декаду будет так же потрачена на интеграцию "перифирии" в процессоры. Т.е. прямо в процессоре будет графический процессор, аудио процессор, сетевая карта + ряд специализированных ускорителей (XML). Что ещё надо производителям ноут/нет-буков? При этом неиспользуемые ядра графического процессора могут прозрачно использовтаься как обычные ядра. А сетевая карта будет закачивать данные прямо в кэш процессора.
F> Ох сомнения берут. Например аудио процессор... ну так, для поддержки какого-нибудь AC97 ещё куда ни шло. Что б было. А если по серьёзнее взяться — то оно сразу же не подходит, выключается, душится и забывается что там такое есть. F>Ну и получается что привет внешним устройствам на FireWire, PCI и т.п.
Ну а подавляющее большинство сейчас посерьёзнее и не берётся. Аудио карта и на материнке, так, вообще-то по-хорошему — сакс. Но ведь использует огромное кол-во людей.
Понятно, что это решение не для профессиональных музыкантов, а так просто — в игрушки поиграть или на неприхотливое ухо.
F>С другими компонентами думаю приблизительно так же...
Здравствуйте, remark, Вы писали:
R>Ну а подавляющее большинство сейчас посерьёзнее и не берётся. Аудио карта и на материнке, так, вообще-то по-хорошему — сакс. Но ведь использует огромное кол-во людей. R>Понятно, что это решение не для профессиональных музыкантов, а так просто — в игрушки поиграть или на неприхотливое ухо.
Ну и неплохое решение кстати. Можно музыку послушать, вот например на работе.
F>>С другими компонентами думаю приблизительно так же... R>А более конкретно? Что ты имеешь в виду?
Ну приблизительно тоже самое имею ввиду и с видео. Одним и встроенной хватает — другим нет. Третьим нужна какая-то третья.
Миру —
Re[6]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, SleepyDrago, Вы писали:
SD>Здравствуйте, thesz, Вы писали:
T>>>>Память вредна. T>>>>Поток данных — data flow, — полезен.
E>>>Где-то уже были аннонсированы версии Windows, Linux, Solaris, FreeBSD, заточенных под архитектуры с data flow?
T>>Это ты что хотел сказать?
SD>подозреваю это был намек на тонкое обстоятельство что пока не будет операционных систем хоть как-то поддерживающих то dataflow ничего не светит
data flow — это архитектура процессора.
Типа суперскаляра.
Вот скажи, много ли потребовалось от windows для поддержки суперскалярных архитектур наподобие Пентиума?
Вот от компиляторов потребовалось.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[6]: Может массовых процессоров 32+ ядрами и не будет?
T>>Это ты что хотел сказать?
E>То, что серьезные революции в аппаратуре могут не выжить, если для них не будет серьезной поддержки со стороны доминирующих ОС.
Суперскаляр выжил, значит, и другие смогут.
data flow такая же странная архитектура, как и суперскаляр.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[6]: Может массовых процессоров 32+ ядрами и не будет?
R>>>И знаешь как говорится: лучше двое старых граблей, чем одни новые. T>>Двое новых граблей, обычно, имеют длину рукоятки чуть меньше, чем по пояс. R>Именно!
Это у тебя все аргументы такие? Типа, "вдвое большее число вдвое худших обстоятельств лучше, как говорится, чем одно привычное".
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
SEAForth хорошо заточен под так называемые систолические алгоритмы (systolic). В новой драконовской книге они названы "конвейерными".
Далеко не все алгоритмы могут быть разложены таким образом. Рекурсивные — точно не могут, алгоритмы на массивах — с большим трудом.
Далее, автором является Chuck Moore (c18, хе!), а он, при всём уважении к его заслугам, не трудится сделать жизнь обычных людей хоть чуть более простой.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[7]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, thesz, Вы писали:
R>>>>И знаешь как говорится: лучше двое старых граблей, чем одни новые. T>>>Двое новых граблей, обычно, имеют длину рукоятки чуть меньше, чем по пояс. R>>Именно!
T>Это у тебя все аргументы такие? Типа, "вдвое большее число вдвое худших обстоятельств лучше, как говорится, чем одно привычное".
Ты не догадался, что новые грабли — это dataflow?
А у тебя какие аргументы — "нет", "тут проблемы", "да"?
Здравствуйте, eao197, Вы писали:
E>Multicore Is Bad News For Supercomputers -- для некоторых классов задач память становится преградой для повышения производительности при увеличении числа ядер.
Не понятно, в чём проблема — тот же TILE64 имеет 64 ядра и 4 встроенных в процессор контроллера памяти. Допустим, что проблемы начинаются на 16 ядрах, значит, если поставить 4 контроллера памяти, то можно делать до 64 ядер. Когда массовые процессоры дойдут до 64 ядер, то поставят 8 контроллеров...
Это, конечно, всё не так приятно, как планомерное повышение частоты одного ядра в одном процессоре; но тем не менее т.н. Memory Wall тут пока не видится. Скорее даже наоборот — многоядерные процессоры решают Memory Wall, позволяя распараллеливать доступ к памяти.
Здравствуйте, remark, Вы писали:
E>>Multicore Is Bad News For Supercomputers -- для некоторых классов задач память становится преградой для повышения производительности при увеличении числа ядер.
R>Вот аналогичная статья, которая пророчит, что уже больше 16 или даже 8 ядер — бесполезно: R>http://arstechnica.com/news.ars/post/20081207-analysis-more-than-16-cores-may-well-be-pointless.html
R>Не понятно, в чём проблема — тот же TILE64 имеет 64 ядра и 4 встроенных в процессор контроллера памяти. Допустим, что проблемы начинаются на 16 ядрах, значит, если поставить 4 контроллера памяти, то можно делать до 64 ядер. Когда массовые процессоры дойдут до 64 ядер, то поставят 8 контроллеров... R>Это, конечно, всё не так приятно, как планомерное повышение частоты одного ядра в одном процессоре; но тем не менее т.н. Memory Wall тут пока не видится. Скорее даже наоборот — многоядерные процессоры решают Memory Wall, позволяя распараллеливать доступ к памяти.
Не знаю, я не разбираюсь в железе, но с точки зрения программиста раставлять по структурам данных специальные padding-и для того, чтобы не было cache line ping-pong -- это маразм, имхо. И мне кажется, что данные статьи как раз об этом свидетельствуют -- пока от многоядерности не выиграют обычные программы, не имеющие специальных средств защиты от подобных ping-pong-ов, смысла увеличивать число ядер не будет.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[8]: Может массовых процессоров 32+ ядрами и не будет?
T>>>>Двое новых граблей, обычно, имеют длину рукоятки чуть меньше, чем по пояс. R>>>Именно! T>>Это у тебя все аргументы такие? Типа, "вдвое большее число вдвое худших обстоятельств лучше, как говорится, чем одно привычное". R>Ты не догадался, что новые грабли — это dataflow?
Там выше моя первая строка, она должна была содержать прилагательное "старый" по отношению к граблям.
Ручки-то у граблей укорачиваются от работы.
R>А у тебя какие аргументы — "нет", "тут проблемы", "да"?
Если объяснять подробно, то получится долго и нудно.
Возьми тот же Cell. Ему не менее 4 лет, AFAIK, за ним стоит здоровенная корпорация IBM, а нормального компилятора, раскидывающего по SPE куски задачи, нет, как нет, и не предвидится.
Это умеренно сложная архитектура.
Что же будет, если ядер будет побольше, ядра будут поменьше, да ещё и по-гетерогенней?
Просто ради прикола возьми любую из понравившихся тебе архитектур, возьми любую хорошо знакомую тебе задачу и уложи вторую на первую. Потом попробуй обобщить на класс задач.
Возможно, ты увидишь проблемы с компиляцией, как их вижу я. Возможно, ты увидишь их ясней.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[9]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, thesz, Вы писали:
T>>>>>Двое новых граблей, обычно, имеют длину рукоятки чуть меньше, чем по пояс. R>>>>Именно! T>>>Это у тебя все аргументы такие? Типа, "вдвое большее число вдвое худших обстоятельств лучше, как говорится, чем одно привычное". R>>Ты не догадался, что новые грабли — это dataflow?
T>Там выше моя первая строка, она должна была содержать прилагательное "старый" по отношению к граблям.
T>Ручки-то у граблей укорачиваются от работы.
Да, по-моему, получилось как раз правильно. Какой мировой опыт разработки различного ПО под dataflow архитектуры по сравнению с традиционной архитектурой? Если так смотреть, то давай бросаться на все подряд "серебряные пули" — XML, COSA, STM и т.д. Все ж они superior. XML — идеальный способ хранения/передачи данных. COSA — идеальная модель программирования. STM — идеальная модель для параллелизма.
В любой новой технологии меня в первую очередь интересуют минусы, недостатки, подводные камни. С плюсами и так всё понятно, о них и так все кричат, да даже если плюс и не заметим, то ничего страшного не случится. А вот с минусами гораздо хуже. О них склонны умалчивать, не называть, или ещё хуже — не знать. А уж если технологию преподносят как вообще без минусов, то сразу "до свиданья" — либо тебе что-то продают, либо это что-то не готовое для реальной жизни.
R>>А у тебя какие аргументы — "нет", "тут проблемы", "да"?
T>Если объяснять подробно, то получится долго и нудно.
T>Возьми тот же Cell. Ему не менее 4 лет, AFAIK, за ним стоит здоровенная корпорация IBM, а нормального компилятора, раскидывающего по SPE куски задачи, нет, как нет, и не предвидится.
T>Это умеренно сложная архитектура.
T>Что же будет, если ядер будет побольше, ядра будут поменьше, да ещё и по-гетерогенней?
T>Просто ради прикола возьми любую из понравившихся тебе архитектур, возьми любую хорошо знакомую тебе задачу и уложи вторую на первую. Потом попробуй обобщить на класс задач.
T>Возможно, ты увидишь проблемы с компиляцией, как их вижу я. Возможно, ты увидишь их ясней.
Я не увижу никаких проблем с компиляцией. По очень простой причине. Я и не жду от компилятора никакой магии.
Задача компилятора — трансляция кода с более высокоуровнего языка в более низкоуровневый. Ну делать оптимизации на *низком* уровне, локальные. Ну делать кое-какие проверки, формальные и тоже локальные. Всё.
А где у нас "компиляторы", которые разбивают и раскидывают по ядрам куски кода для симметричных мало-ядерных процессоров? А где у нас "компиляторы", которые хотя бы для однопоточного случая создают производительные/оптимальные/устойчивые к сбоям программы? Я имею в виду не на низком уровне там битики переставить или операции местами поменять, а на высоком уровне — что б алгоритм оптимальный был, что б сервер производительный получился, что б сервер устойчивый получился, что б игра красивая получилась. Где такие "компиляторы"? А где "компиляторы", которые семантическую корректность программы гарантируют?
Тут везде, по-твоему, "проблемы с компиляцией"? По-моему, это — просто задачи разработчика.
Если у нас Cell или NUMA, то во-первых, надо алгоритм соответствующий подобрать. Не каждый на них ляжет. И если алгоритм не подходящий, то тут уж никакой компилятор не поможет, ни с проблемами, ни без проблем. Потом надо *самому* побить код на куски. АФАИК, никакой компилятор (за исключением вырожденных случаев типа FORTRAN в отношении простых циклов) не бьёт сам на куски.
Программировать под такие архитектуры, конечно, сложнее. Но никто обратного и не утверждает. Никто не говорит, что создание высокопроизводительного ПО просто. Никто не говорит, что создание надёжных серверов просто. Никто не говорит, что создание хороших игр просто. Эти задачи обладают высокой внутренней сложностью, которую никакой компилятор не уберёт (за исключением, разьве что, DSL для типовых задач). Снизу помощи сколько угодно — тут и компилятор, тут и библиотеки поддержки (те же агентные библиотеки/языки с поддержкой NUMA, топологии системы, гетерогенности и т.д.), сверху — только голова.
Здравствуйте, thesz, Вы писали:
T>Если объяснять подробно, то получится долго и нудно.
T>Возьми тот же Cell. Ему не менее 4 лет, AFAIK, за ним стоит здоровенная корпорация IBM, а нормального компилятора, раскидывающего по SPE куски задачи, нет, как нет, и не предвидится.
T>Это умеренно сложная архитектура.
T>Что же будет, если ядер будет побольше, ядра будут поменьше, да ещё и по-гетерогенней?
T>Просто ради прикола возьми любую из понравившихся тебе архитектур, возьми любую хорошо знакомую тебе задачу и уложи вторую на первую. Потом попробуй обобщить на класс задач.
T>Возможно, ты увидишь проблемы с компиляцией, как их вижу я. Возможно, ты увидишь их ясней.
буду признателен за ссылки или хоть что нибудь.
я бы очень хотел алгоритмы иметь отдельно от clutter который порождает решение всех мелких вопросов без которых с++ не компилируется.
моя проблема в том что такие инструменты как например scheme имеют модель исполнения которую никак просто не уложишь на аппаратуру. Если было нужно для бизнес задач то я бы и глазом не моргнул — пустил бы интерпретатор и поставил галочку "сделано". Проблема в том что оно должно обрабатывать большие (>10**9 полигонов) объемы векторной геометрии. И соответственно между моделью на языке высокого уровня и железом нужно копаться.
Так что есть серьезная нужда запускать, тестировать и анализировать алгоритмы в высокоуровневом описании, а затем не меняя смысла раскладывать это уже по элементам аппаратуры.
У меня есть пара хороших знакомых, которые в этих вопросах явно получше меня и они обеими руками за построение отображение "текст на яву" <-> "текст на С" (грубо говоря современный ассемблер). Не буду делать вид что это просто или что я понял как они это могут сделать. Так что любые клочки информации приветствуются.
Подход remark мне кажется реально бессмысленным — с каждым патчем архитектуры железки нужно проделывать полный реверс анализ факторов (например изменилась ассоциативность L2 и привет всем padding'ам в структурах и пока еще это всплывет). Фактически речь идет о поддержке софта под один компьютер, что с точки зрения экономики полный ...
Re[10]: Может массовых процессоров 32+ ядрами и не будет?
T>>Если объяснять подробно, то получится долго и нудно. T>>Возьми тот же Cell. Ему не менее 4 лет, AFAIK, за ним стоит здоровенная корпорация IBM, а нормального компилятора, раскидывающего по SPE куски задачи, нет, как нет, и не предвидится. T>>Это умеренно сложная архитектура. T>>Что же будет, если ядер будет побольше, ядра будут поменьше, да ещё и по-гетерогенней? T>>Просто ради прикола возьми любую из понравившихся тебе архитектур, возьми любую хорошо знакомую тебе задачу и уложи вторую на первую. Потом попробуй обобщить на класс задач. T>>Возможно, ты увидишь проблемы с компиляцией, как их вижу я. Возможно, ты увидишь их ясней. SD>буду признателен за ссылки или хоть что нибудь.
Ссылки на что? Алгоритмы анализа и преобразования кода?
Они грубо делятся на обработку программ над массивами (Фортран, умеренно просто) и обработку программ общего назначения (C/C++, ОЧЕНЬ СЛОЖНО). В обоих случаях надо определить наличие зависимости между циклами или вызовами, во втором случае всё осложняется произвольной рекурсией и перекрытием (aliasing).
Здравствуйте, SleepyDrago, Вы писали:
SD> Подход remark мне кажется реально бессмысленным — с каждым патчем архитектуры железки нужно проделывать полный реверс анализ факторов (например изменилась ассоциативность L2 и привет всем padding'ам в структурах и пока еще это всплывет). Фактически речь идет о поддержке софта под один компьютер, что с точки зрения экономики полный ...
Это, действительно, бессмыслица. И, к счастью, это не мой подход.
Ну там можно попробовать переменные использовать, настраивать как-то свой код.
З.ы. ассоциативность не влияет на padding'и.
З.з.ы. padding'и — это не мой подход. С ними так и так проблемы всплывут на NUMA системах. А если их не использовать, то и изменение размера кэш-линии не повлияет.
Здравствуйте, thesz, Вы писали:
SD>>буду признателен за ссылки или хоть что нибудь.
T>Ссылки на что? Алгоритмы анализа и преобразования кода?
T>Они грубо делятся на обработку программ над массивами (Фортран, умеренно просто) и обработку программ общего назначения (C/C++, ОЧЕНЬ СЛОЖНО). В обоих случаях надо определить наличие зависимости между циклами или вызовами, во втором случае всё осложняется произвольной рекурсией и перекрытием (aliasing).
T>Для первого случая: T>Dependence analysis T>Obligatory self promotion — про алгоритм Фурье-Моцкина
T>Второе есть в драконовской книге последнего издания. Это действительно очень сложно, я знаю только поверхностно.
"Преобразования кода" — звучит интересно.
Предположим что трансляция программ на фортране или си меня не интересует.
Предположим что проще написать по известному алгоритму наново чем отлавливать неопределенное поведение которым занимался старый код на краях.
Практический интерес тогда состоит в том как разделить работу над кодом алгоритма и работу по привязыванию этого алгоритма к конкретной железке. И соответственно как при первом не заниматься вторым и при втором не испортить первое. В идеале эти два вида деятельности требуют совершенно разных способнотей у людей.
Re[11]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, remark, Вы писали:
R>Здравствуйте, SleepyDrago, Вы писали:
SD>> Подход remark мне кажется реально бессмысленным — с каждым патчем архитектуры железки нужно проделывать полный реверс анализ факторов ... Фактически речь идет о поддержке софта под один компьютер, ...
R>Это, действительно, бессмыслица. И, к счастью, это не мой подход.
С этого момента я думаю становится интересно.
Что нибудь подробнее ? Пример с матрицей на 513 я думаю все помнят. Пример со смещением в 512 для второго потока чтения из памяти (в книге Касперски) тоже.
Ну гипотетический пример : Как вы себе представляете переход к 256 битной векторизации, если программа написана только на С++ . Rewrite ?
R>Ну там можно попробовать переменные использовать, настраивать как-то свой код.
код и так сложнее чем надо. Там только настраиваемых алгоритмических параметров вагон.
R>
Re[12]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, SleepyDrago, Вы писали:,
SD>>> Подход remark мне кажется реально бессмысленным — с каждым патчем архитектуры железки нужно проделывать полный реверс анализ факторов ... Фактически речь идет о поддержке софта под один компьютер, ...
R>>Это, действительно, бессмыслица. И, к счастью, это не мой подход. SD>С этого момента я думаю становится интересно. SD>Что нибудь подробнее ? Пример с матрицей на 513 я думаю все помнят. Пример со смещением в 512 для второго потока чтения из памяти (в книге Касперски) тоже.
Не помню.
SD>Ну гипотетический пример : Как вы себе представляете переход к 256 битной векторизации, если программа написана только на С++ . Rewrite ?
Так же как делали перевод на новую платформу десятилетиями — перекомпилировать соотв. компилятором (я думаю, ICC сможет это сделать без каких-либо изменений в коде).
R>>Ну там можно попробовать переменные использовать, настраивать как-то свой код. SD>код и так сложнее чем надо. Там только настраиваемых алгоритмических параметров вагон.
Не надо разные уровни мешать в одну кучу. Например, аллокатор памяти может очень сильно настраиваться от платформы, однако наружу он предоставляет те же malloc() и free().
Здравствуйте, SleepyDrago, Вы писали:
SD>"Преобразования кода" — звучит интересно. SD>Предположим что трансляция программ на фортране или си меня не интересует. SD>Предположим что проще написать по известному алгоритму наново чем отлавливать неопределенное поведение которым занимался старый код на краях. SD>Практический интерес тогда состоит в том как разделить работу над кодом алгоритма и работу по привязыванию этого алгоритма к конкретной железке. И соответственно как при первом не заниматься вторым и при втором не испортить первое. В идеале эти два вида деятельности требуют совершенно разных способнотей у людей.
Работает так: алгоритм описывается в абстрактном виде через массивы. Платформа имеет развитый ран-тайм с поддержком CPU, GPU, Cell. При запуске абстрактный алгоритм компилируется платформой под конкретное железо. Сейчас нет времени описывать подробнее, но там есть примеры в PDF'ах.
Здравствуйте, remark, Вы писали:
R> (2) за счёт повышения тактовой частоты в ближайшую декаду сещественного роста не предвидится
Я бы не был так уверен в этом. Текущая ситуация с частотами в основном обусловлена маркетинговыми моментами. Конкуренции со стороны AMD в области high end в ближайшие пару лет точно не предвидится, так что повышать частоту смысла нет. Однако при этом известно, что теперешние Penryn массово работают на 4.5ГГц с воздушным охлаждением. А на подходе уже 32нм техпроцесс.
R>+ ряд специализированных ускорителей (XML)
SSE4.2 уже имеет 5 команд, заточенных специально под парсинг XML.
... << RSDN@Home 1.2.0 alpha 4 rev. 1120 on Windows Vista 6.0.6001.65536>>
Здравствуйте, remark, Вы писали:
R>Здравствуйте, SleepyDrago, Вы писали:
SD>>"Преобразования кода" — звучит интересно. SD>>Предположим что трансляция программ на фортране или си меня не интересует. SD>>Предположим что проще написать по известному алгоритму наново чем отлавливать неопределенное поведение которым занимался старый код на краях. SD>>Практический интерес тогда состоит в том как разделить работу над кодом алгоритма и работу по привязыванию этого алгоритма к конкретной железке. И соответственно как при первом не заниматься вторым и при втором не испортить первое. В идеале эти два вида деятельности требуют совершенно разных способнотей у людей.
R>Можно посмотреть на платформу RapidMind. Звучит, как то, что надо. R>http://www.rapidmind.com/technology.php
R>Работает так: алгоритм описывается в абстрактном виде через массивы. Платформа имеет развитый ран-тайм с поддержком CPU, GPU, Cell. При запуске абстрактный алгоритм компилируется платформой под конкретное железо. Сейчас нет времени описывать подробнее, но там есть примеры в PDF'ах.
Ну как? Не смотрел? Если задача ляжет на их модель, то окажешься в шоколаде, как раз то, что ты хочешь.
Можешь ещё поглядеть на ASPEED ACCELLERANT: http://www.aspeed.com/
Я правда, даже после чтения всей их документации так ни чо про них и не понял
Маркетинга 200%, чо делают на самом деле — не понятно.
• Turbo-charges your applications without reprogramming
• Quickly create new high performance applications
• Cuts development time by up to 90%
• Exploit multi-core, multi-CPU, cluster, grid configurations
• Conforms to C, C++, C#, Java, FORTRAN languages
• Quick payback and ongoing ROI
• Automatically and dynamically optimizes application completion
• Achieve dramatic response time reductions
• Provides predictable response times+ A
• Maximizes existing IT infrastructure capacity
• Parallelizes the "unparallelizable"
• Distributes the "undistributable"
Смешно в самом деле. Ешё один подход "без недостатков".
Хотя, не знаю, может и стоящая штука...
Здравствуйте, remark, Вы писали:
R>Здравствуйте, remark, Вы писали:
R>>Здравствуйте, SleepyDrago, Вы писали:
SD>>>"Преобразования кода" — звучит интересно. SD>>>Предположим что трансляция программ на фортране или си меня не интересует. SD>>>Предположим что проще написать по известному алгоритму наново чем отлавливать неопределенное поведение которым занимался старый код на краях. SD>>>Практический интерес тогда состоит в том как разделить работу над кодом алгоритма и работу по привязыванию этого алгоритма к конкретной железке. И соответственно как при первом не заниматься вторым и при втором не испортить первое. В идеале эти два вида деятельности требуют совершенно разных способнотей у людей.
R>>Можно посмотреть на платформу RapidMind. Звучит, как то, что надо. R>>http://www.rapidmind.com/technology.php
R>>Работает так: алгоритм описывается в абстрактном виде через массивы. Платформа имеет развитый ран-тайм с поддержком CPU, GPU, Cell. При запуске абстрактный алгоритм компилируется платформой под конкретное железо. Сейчас нет времени описывать подробнее, но там есть примеры в PDF'ах.
R>Ну как? Не смотрел? Если задача ляжет на их модель, то окажешься в шоколаде, как раз то, что ты хочешь.
Не верю (С). Еще один транслятор с фортрана. С самодельного фортрана. И когда людям надоест изобретать фортран ?
у нас задачи бывают двух сортов — иерархические и плоские (по виду входных данных) и соответственно плоские еще как то можно представить в виде массивов (но это очень неэффективно) а мне повезло и я вожусь с иерархией. Там самая "популярная" операция "найти вглубь иерархии все что попадает в заданное окошко в корне". Какие тут фортраны ?
R>
зы смотрю пдфку еще раз. ИМХО — они пытаются сделать gpu язык лучше чем у nvidia и на всякий случай делают fallback на cpu. Я думаю им просто "не позволят этого". Сначала сама nvda а потом годика через 2-3 подтянется майкрософт. в этой области у них задействованы серьезные силы — тогда и посмотрим кто будет рулить на gpu. а пока связываться с такими ребятами если мы делаем софт а не тратим научный бюджет — самоубийство.
ззы имхо сначала нужно сделать "ассемблер для data-parallel" и таким как мы придется пописать на нем прежде чем гуру компиляции подтянутся. К сожалению пока вопрос открытый.
Re[15]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, SleepyDrago, Вы писали:
R>>>Можно посмотреть на платформу RapidMind. Звучит, как то, что надо. R>>>http://www.rapidmind.com/technology.php
R>>>Работает так: алгоритм описывается в абстрактном виде через массивы. Платформа имеет развитый ран-тайм с поддержком CPU, GPU, Cell. При запуске абстрактный алгоритм компилируется платформой под конкретное железо. Сейчас нет времени описывать подробнее, но там есть примеры в PDF'ах.
R>>Ну как? Не смотрел? Если задача ляжет на их модель, то окажешься в шоколаде, как раз то, что ты хочешь.
SD>Не верю (С). Еще один транслятор с фортрана. С самодельного фортрана. И когда людям надоест изобретать фортран ?
Именно! Об этом и речь.
SD>у нас задачи бывают двух сортов — иерархические и плоские (по виду входных данных) и соответственно плоские еще как то можно представить в виде массивов (но это очень неэффективно) а мне повезло и я вожусь с иерархией. Там самая "популярная" операция "найти вглубь иерархии все что попадает в заданное окошко в корне". Какие тут фортраны ?
Поэтому я и говорю про всякие "думать", "паддинги" и т.д.
Где эти решения, которые позволяют реализовывать произвольные вычисления, эффективно, абстрагировать от деталей, брать большую часть на себя, поддерживать HWT, SMP, NUMA, GPU, делать умный шедулинг, предотвращать гонки и дедлоки и т.д. Пусть кто-нибудь даст ссылки, если такое есть. Если уже можно не думать ни о распараллеливании, ни об аппаратуре, я буду только рад. Но АФАИК технологии ещё очень-очень далеки от этого.
Самые продвинутые вещи типа RapidMind или Cilk++ они во-первых платные и платные судя-по-всему не кисло, так и они очень и очень ограничены и по поддерживаемым задачам и по интеллекту.
Класс решаемых задач значительно шире, и особенно хороши как раз для иерахических задач (fork/join).
Но практически единственный интеллект, который они дают, — это достаточно хороший шедулинг для симметричных архитектур (SMP, multicore).
R>> SD>
SD>зы смотрю пдфку еще раз. ИМХО — они пытаются сделать gpu язык лучше чем у nvidia и на всякий случай делают fallback на cpu. Я думаю им просто "не позволят этого". Сначала сама nvda а потом годика через 2-3 подтянется майкрософт. в этой области у них задействованы серьезные силы — тогда и посмотрим кто будет рулить на gpu. а пока связываться с такими ребятами если мы делаем софт а не тратим научный бюджет — самоубийство.
Ну не знаю, меня это не особо интересует. Микрософт вроде не особо туда тянется. А от NVIDIA они выгодно отличаются тем, что поддерживают и CPU и другие GPU.
SD>ззы имхо сначала нужно сделать "ассемблер для data-parallel" и таким как мы придется пописать на нем прежде чем гуру компиляции подтянутся. К сожалению пока вопрос открытый.
Еще на тему использования GPU для серьезных вычислений. Проект с открытым исходным кодом OpenMM использует GPU nVidia и ATI для "modern molecular modeling simulation" (уж не знаю, как это правильно по русски обозвать). Так что, если кто-то интересуется темой использования GPU для расчетов, может использовать исходники OpenMM в качестве примера.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Я посмотрел на описание архитектуры A8 не так давно.
Это нечто странное.
У неё целочисленный конвейер в 13 этапов, по-моему. Они это сделали для повышения тактовой частоты, по их словам. В результате им пришлось добавить предсказатель переходов, поскольку чем длинней конвейер, тем тяжелее обходится его сброс.
Для сравнения, конвейер Sun UltraSPARC T2 (Inagara 2) имеет, AFAIR, 8 этапов конвейера и работает на частоте в 1GHz+. У ARM типичное применение требует 350MHz, втрое меньше.
На 350MHz синтезируется Leon3 с 7 этапами конвейера без проблем, прямо из коробки. Если его подразогнать вручную, то можно получить 400MHz+.
Чем занимались в ARM, мне непонятно.
A9, как я понимаю, унаследовал всю эту красоту от A8, только умножил на 4.
Но кое-что интересное там есть. Например, конвейер Neon (SIMD от ARM) идёт после целочисленного и к его старту все исключения уже проверены. Это мысль.
Иными словами, логика ARM мне непонятна. Не думаю, что там дураки сидят, поэтому прямо назвать A8 плохим я не могу. Но признаков плохого процессора у него достаточно.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
T>data flow такая же странная архитектура, как и суперскаляр.
Не совсем, загрузить работой суперскаляр — не проблема, в отличие от dataflow, где реальная загрузка выч. узлов зависит от св-в алгоритмов и даже от входных данных.
И совсем не понятно, как быть с приоритезацией, ибо аппаратная ассоциативная память и так сложна, а элементами приоритезации будет еще в два раза сложнее.
Re[8]: Может массовых процессоров 32+ ядрами и не будет?
T>>data flow такая же странная архитектура, как и суперскаляр. V>Не совсем, загрузить работой суперскаляр — не проблема, в отличие от dataflow, где реальная загрузка выч. узлов зависит от св-в алгоритмов и даже от входных данных.
А в суперскаляре, значит, не зависит.
Как интересно!
Ссылку, где ты почерпнул такие сведения, не подкинешь?
И не подскажешь ли заодно, почему практически все производители процессоров от out-of-order суперскаляров уходят-то? Просто, чтобы два раза не вставать.
V>И совсем не понятно, как быть с приоритезацией, ибо аппаратная ассоциативная память и так сложна, а элементами приоритезации будет еще в два раза сложнее.
Этого я ообще не понял. Что за приоретизация такая? Почему с элементами приоретизации ассоциативная память будет в два раза сложней? С какого-то это такого фига?
Ты, прошу прощения, проектированием железа занимался? Ну, чтобы процессор спроектировать и смоделировать, типа того. Или так, с бухты-барахты говоришь?
Ассоциативная память сводится к набору регистров и сравнению на равенство. Регистр — 6 транзисторов на бит. Сравнение на равенство — практически один 2И-НЕ на бит, четыре транзистора. Итого 10 транзисторов на бит. Ну, 15 максимум, я мог ошибиться.
В случае, если нам надо сравнивать с учётом больше-меньше-равно (это твой "элемент приоретизации", или нет), то появляется полноценный сумматор. У него один полный сумматор на бит — конечно, грубая прикидка, в реальности будет чуток больше, но не сильно, — это 3*(2И-НЕ)+(3И-НЕ) на схему переноса, 12+6 транзисторов, и еще, по-моему, 2*(2ИСКЛЮЧАЮЩЕЕ-ИЛИ), или 2*8 — 16 транзисторов. Итого, 18+16+6 = 40 транзисторов на бит. Простую ассоциативную память мы перегоняем примерно в три-четыре раза.
При этом ассоциативная память с учётом знака отношения может быть сильно меньше обычной по размеру в битах, поскольку позволяет отправлять наверх не нужные в ближайшее время токены. А работает достаточно хорошо в самой системе.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[9]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, thesz, Вы писали:
T>>>data flow такая же странная архитектура, как и суперскаляр. V>>Не совсем, загрузить работой суперскаляр — не проблема, в отличие от dataflow, где реальная загрузка выч. узлов зависит от св-в алгоритмов и даже от входных данных.
T>А в суперскаляре, значит, не зависит.
T>Как интересно!
T>Ссылку, где ты почерпнул такие сведения, не подкинешь?
Тебе ссылка нужна на принципы работы архитектур, или для красного словца? Работу суперскаляров планирует компилятор, который хоть что-то знает о св-вах компиллируемой программы, а работа датафлоу планируется "сама по себе", исходя из "чудесных" св-в автоматического спаривания операндов и операций.
T>И не подскажешь ли заодно, почему практически все производители процессоров от out-of-order суперскаляров уходят-то? Просто, чтобы два раза не вставать.
Известно почему, т.к. на каждую архитектуру супер-скаляра и даже на версию проца на одной архитектуре нужен свой компилятор. Т.е. совместимость по машинным кодами ничего не значит для скаляра, программа должна быть заточена под конкретное кол-во исполняющих устройств проца.
А ты думаешь, Sun и MS взялись за виртуальные машины с компилируемым по месту байт-кодом в разгар популярности суперскаляров просто так? Ха-ха.
V>>И совсем не понятно, как быть с приоритезацией, ибо аппаратная ассоциативная память и так сложна, а элементами приоритезации будет еще в два раза сложнее.
T>Этого я ообще не понял. Что за приоретизация такая? Почему с элементами приоретизации ассоциативная память будет в два раза сложней? С какого-то это такого фига?
Ты бы хоть набросал себе в общих чертах функциональную схему этой ассоциативной памяти, сразу ужаснулся бы пониманию того, что её быстродействие зависит от её размера, мало того, кол-во "вычислительных" вентилей превышает кол-во вентилей памяти и растёт в степенной зависимости от кол-ва вентилей памяти (формула для сочетаний). У схем приоритезаций — аналогично.
T>Ты, прошу прощения, проектированием железа занимался? Ну, чтобы процессор спроектировать и смоделировать, типа того. Или так, с бухты-барахты говоришь?
Это важно? Про возраст собеседника уже пора спрашивать или пока подождёшь?
T>Ассоциативная память сводится к набору регистров и сравнению на равенство. Регистр — 6 транзисторов на бит. Сравнение на равенство — практически один 2И-НЕ на бит, четыре транзистора. Итого 10 транзисторов на бит. Ну, 15 максимум, я мог ошибиться.
XOR чуть сложнее, чем один 2И-НЕ, но это пофиг, не там засаду ищешь. Ты "умудрился" забыть о том, что сравнивать надо не две ячейки памяти, а многие со многими, так же как и в схемах с приоритезацией с той разницей, что сравнение на больше/меньше более дорогое, чем на равенство, да еще с быстродействием, зависящим от колва сравниваемых бит. По хрен конкретные транзисторы, тем более, что не КМОП-ом единым... функциональную схему прикинь для начала.
Итого, что имеем:
— полностью все со всеми ячейки сравнивать накладно, ибо степенная зависимость от объема памяти, т.е. в перспективе ожидать значительного увеличения кол-ва одновременно сравниваемых элементов не стоит.
— схема сравнения имеет ограниченную "ширину" участка сравнения, через которую циклически прогоняется контент памяти, прогоняется он с конечной скоростью, и что мне больше всего здесь не нравится — этот процесс недетерминирован. Некие "важные" вычисления, т.е. те, от корорых зависят многие другие вычисления (о которых датафлоу процессор знать не может и "не хочет", согласно своей религии), могут быть или в начале этой очереди, или всё время в конце или даже уже вытолкнуты во внешнюю память — тут уж как повезет. И вот именно из-за этого момента, теоретическая автоспариваемость токенов может не работать из-за очевидного несоответствия структуры исполнительных узлов той самой "красивой" теоретической модели.
В общем, отсутствие планирования вперёд — это и достоинство датафлоу, и очень серьёзный недостаток одновременно. Все прекрасно понимают, что есть огромный пласт задач, где датафлоу будет вне конкуренции — это обсчитывание огромного числа однородных моделей, напр. расчёты по матрицам или моделирование огромного кол-ва мелких частиц (напр. медицинское или ядерное моделирование). Но вот в кач-ве современной операционной системы, где надо лихо управляться с вводом-выводом, блокировками и приоритезацией — эта архитектура покурит.
T>В случае, если нам надо сравнивать с учётом больше-меньше-равно (это твой "элемент приоретизации", или нет), то появляется полноценный сумматор.
Не полноценный сумматор, а проще гораздо (хотя и на сумматоре можно), но опять же, не в сложности единичной схемы сравнения суть, суть в их комбинаторном кол-ве.
T>При этом ассоциативная память с учётом знака отношения может быть сильно меньше обычной по размеру в битах, поскольку позволяет отправлять наверх не нужные в ближайшее время токены. А работает достаточно хорошо в самой системе.
Ага, т.е. к приоритезации токенов ты тоже пришёл. Имея приоритезацию, можно упорядочивать вычисления, делать их более детерминированными и даже планировать необходимые ресурсы. Т.е. непонятно, зачем было спорить, если сам прекрасно всё знаешь. А засада лишь в том, что реальных процов с приоритезацией токенов нет даже в проекте и вряд ли я увижу их в массовом производстве в ближайшие лет 10.
Re[10]: Может массовых процессоров 32+ ядрами и не будет?
T>>>>data flow такая же странная архитектура, как и суперскаляр. V>>>Не совсем, загрузить работой суперскаляр — не проблема, в отличие от dataflow, где реальная загрузка выч. узлов зависит от св-в алгоритмов и даже от входных данных. T>>А в суперскаляре, значит, не зависит. T>>Как интересно! T>>Ссылку, где ты почерпнул такие сведения, не подкинешь? V>Тебе ссылка нужна на принципы работы архитектур, или для красного словца? Работу суперскаляров планирует компилятор, который хоть что-то знает о св-вах компиллируемой программы, а работа датафлоу планируется "сама по себе", исходя из "чудесных" св-в автоматического спаривания операндов и операций.
Все успешные суперскаляры используют out-of-order выполнение потому, что компилятор не может предсказать всего. См. проблемы у VLIW (EPIC) и TTA. Внеочередное выполнение команд и представляет собой вариант dataflow.
Я делал модели и суперскалярных процессоров (in order и out of order — включалось флагом командной строки), и dataflow процессоров (http://thesz.mskhug.ru/browser/hiersort). Я знаю, о чем говорю.
T>>И не подскажешь ли заодно, почему практически все производители процессоров от out-of-order суперскаляров уходят-то? Просто, чтобы два раза не вставать. V>Известно почему, т.к. на каждую архитектуру супер-скаляра и даже на версию проца на одной архитектуре нужен свой компилятор. Т.е. совместимость по машинным кодами ничего не значит для скаляра, программа должна быть заточена под конкретное кол-во исполняющих устройств проца.
Откуда вообще появился out-of-order, знаешь?
Если не знаешь, то расскажу. Выяснилось, что программы для более старых моделей процессоров, рассчитанных на меньшее количество ИУ, можно эффективно выполнять на более новых, только выдачу команд надо переделать. Сделать такой, чтобы можно было не обращать внимание на не готовые операнды или на операнды, которые можно отбросить.
В основном, боролись с небольшим количеством регистров в процессоре (да-да, с небольшим количеством регистров в 32 штуки — инженеры DEC Alpha выяснили, что внутренние циклы могут эффективно задействовать до 80-ти регистров, потом общая эффективность системы выходит на плато) путём устранения write-after-write зависимостей. Но заодно решили проблемы задержки доступа к памяти. OOO суперскаляры обгоняют in-order суперскаляры всегда и везде.
Но теперь все производители процессоров вдруг резко стали уходить от этого богатства.
Вопрос — почему?
V>А ты думаешь, Sun и MS взялись за виртуальные машины с компилируемым по месту байт-кодом в разгар популярности суперскаляров просто так? Ха-ха.
Разворачивай.
V>>>И совсем не понятно, как быть с приоритезацией, ибо аппаратная ассоциативная память и так сложна, а элементами приоритезации будет еще в два раза сложнее. T>>Этого я ообще не понял. Что за приоретизация такая? Почему с элементами приоретизации ассоциативная память будет в два раза сложней? С какого-то это такого фига? V>Ты бы хоть набросал себе в общих чертах функциональную схему этой ассоциативной памяти, сразу ужаснулся бы пониманию того, что её быстродействие зависит от её размера, мало того, кол-во "вычислительных" вентилей превышает кол-во вентилей памяти и растёт в степенной зависимости от кол-ва вентилей памяти (формула для сочетаний). У схем приоритезаций — аналогично.
Я проектировал схемы ассоциативной памяти и делал их модели. Никаких "степенных" зависимостей, о которых ты говоришь, я не видел.
Мой основной тезис: надо сравнивать вход со всеми запомненными элементами, а не каждый с каждым.
Моя ассоциативная память работала вот так:
— массив парных элементов
— массив одиночных элементов
— вход элемента
— если элемент на входе одиночный и выход открыт, то мы сразу выдаём его на выход,
— если элемент на входе пары и есть пара и выход открыт, то мы сразу выдаём его на выход
— если выход закрыт, то одиночный элемент помещается в массив одиночных на первое попавшееся место.
— если выход закрыт, то парный элемент помещается в массив парных рядом со своей парой или на первое попавшееся место.
— если дял парного элемента нет пары, то он помещается на первое свободное место
— если на входе нет элемента и выход открыт, то выдаются два совпадающих парных элемента, если таковых нет, то одиночный элемент, если таковой есть в массиве одиночных.
Размерность N*N здесь может иметь только схема определения свободного места в массивах. Это если постараться и сделать её неправильно. Если сделать её правильно (наподобие схемы дешифратора), то и скорость останется высокой и квадратичной сложности не будет.
Схема с определением порядка между элементами меняет только схему компаратора. Вместо равенства будет использоваться вычитание. Ну, ещё надо всем сообщить о равенстве входного элемента какому-то из имевшихся, поскольку тогда большим, чем входной, не надо увеличивать свои индексы.
Что не так в моих рассуждениях?
На всякий случай: если у нас на входе несколько элементов одновременно, то хешированием и буферизацией мы можем свести их к одному элементу на входе схемы, описанной выше.
T>>Ты, прошу прощения, проектированием железа занимался? Ну, чтобы процессор спроектировать и смоделировать, типа того. Или так, с бухты-барахты говоришь? V>Это важно? Про возраст собеседника уже пора спрашивать или пока подождёшь?
Это важно.
Это важно для подробности аргументации. Сколько всего я могу опустить и стоит ли затраченные усилия продолжения разговора.
T>>Ассоциативная память сводится к набору регистров и сравнению на равенство. Регистр — 6 транзисторов на бит. Сравнение на равенство — практически один 2И-НЕ на бит, четыре транзистора. Итого 10 транзисторов на бит. Ну, 15 максимум, я мог ошибиться. V>XOR чуть сложнее, чем один 2И-НЕ, но это пофиг, не там засаду ищешь. Ты "умудрился" забыть о том, что сравнивать надо не две ячейки памяти, а многие со многими, так же как и в схемах с приоритезацией с той разницей, что сравнение на больше/меньше более дорогое, чем на равенство, да еще с быстродействием, зависящим от колва сравниваемых бит. По хрен конкретные транзисторы, тем более, что не КМОП-ом единым... функциональную схему прикинь для начала.
Как я выше показал, есть варианты, когда не надо сравнивать "многие-со-многими". "Один-со-многими" — надо. Но это другой класс сложности.
Сложность сравнения на больше-меньше ровно такая же, как и сравнение на равенство: O(log(N)). Различие только в множителе. Другого не дано.
V>Итого, что имеем: V>- полностью все со всеми ячейки сравнивать накладно, ибо степенная зависимость от объема памяти, т.е. в перспективе ожидать значительного увеличения кол-ва одновременно сравниваемых элементов не стоит.
Не стоит, согласен, но по другим причинам. По-моему, большая ассоциативная память просто не нужна.
V>- схема сравнения имеет ограниченную "ширину" участка сравнения, через которую циклически прогоняется контент памяти, прогоняется он с конечной скоростью, и что мне больше всего здесь не нравится — этот процесс недетерминирован. Некие "важные" вычисления, т.е. те, от корорых зависят многие другие вычисления (о которых датафлоу процессор знать не может и "не хочет", согласно своей религии), могут быть или в начале этой очереди, или всё время в конце или даже уже вытолкнуты во внешнюю память — тут уж как повезет. И вот именно из-за этого момента, теоретическая автоспариваемость токенов может не работать из-за очевидного несоответствия структуры исполнительных узлов той самой "красивой" теоретической модели.
Для этого необходимо делать так, чтобы токены не выбрасывались. Планирование вычислений и сортировка токенов с соответствии со "временем выполнения программы" решает эту проблему.
V>В общем, отсутствие планирования вперёд — это и достоинство датафлоу, и очень серьёзный недостаток одновременно. Все прекрасно понимают, что есть огромный пласт задач, где датафлоу будет вне конкуренции — это обсчитывание огромного числа однородных моделей, напр. расчёты по матрицам или моделирование огромного кол-ва мелких частиц (напр. медицинское или ядерное моделирование). Но вот в кач-ве современной операционной системы, где надо лихо управляться с вводом-выводом, блокировками и приоритезацией — эта архитектура покурит.
Посмотрим.
Но, как минимум, Roadrunner (или кто там сейчас в фаворитах) мы можем обставить.
T>>В случае, если нам надо сравнивать с учётом больше-меньше-равно (это твой "элемент приоретизации", или нет), то появляется полноценный сумматор. V>Не полноценный сумматор, а проще гораздо (хотя и на сумматоре можно), но опять же, не в сложности единичной схемы сравнения суть, суть в их комбинаторном кол-ве.
Как я показал, и, надеюсь, достаточно ясно, комбинаторного взрыва не произойдёт.
А вот сумматор нужен. Или эквивалентная ему схема.
T>>При этом ассоциативная память с учётом знака отношения может быть сильно меньше обычной по размеру в битах, поскольку позволяет отправлять наверх не нужные в ближайшее время токены. А работает достаточно хорошо в самой системе. V>Ага, т.е. к приоритезации токенов ты тоже пришёл. Имея приоритезацию, можно упорядочивать вычисления, делать их более детерминированными и даже планировать необходимые ресурсы. Т.е. непонятно, зачем было спорить, если сам прекрасно всё знаешь. А засада лишь в том, что реальных процов с приоритезацией токенов нет даже в проекте и вряд ли я увижу их в массовом производстве в ближайшие лет 10.
Я к этому делу пришёл два года тому назад. И даже сделал модель, как видишь.
Мне нравится быстро проверять свои идеи, чего и остальным желаю.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[4]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, thesz, Вы писали:
V>>А ты думаешь, Sun и MS взялись за виртуальные машины с компилируемым по месту байт-кодом в разгар популярности суперскаляров просто так? Ха-ха.
T>Разворачивай.
Что тут разворачивать? Много раз упоминалось уже, что байт-код теоретически должен компиллироваться наилучшим образом под конкретную аппаратную платформу. Выглядит это как-то так: "пишите на нашем байткоде сейчас и ваши инвестиции будут сохраняться по мере улучшения наших управляемых платформ".
T>Я проектировал схемы ассоциативной памяти и делал их модели. Никаких "степенных" зависимостей, о которых ты говоришь, я не видел.
T>Мой основной тезис: надо сравнивать вход со всеми запомненными элементами, а не каждый с каждым.
А выбор текущего парного элемента, если вход пуст? А как огранизовывать твои "очереди" аппаратно? А как делить память м/у очередями? Или под каждую очередь свою память?
T>Моя ассоциативная память работала вот так:
***
Похоже, что имелась ввиду структура, когда одна АП — одно исполнительное устройство. Тогда весь data-flow теряет смысл, должна быть общая ассоциативная память для как можно большего кол-ва узлов, т.е. должна работать ситуация, когда выходов и входов много.
T>Сложность сравнения на больше-меньше ровно такая же, как и сравнение на равенство: O(log(N)). Различие только в множителе. Другого не дано.
Дано, т.к. вентили бывают не только 2И-НЕ, но и куча*И-НЕ, поэтому схема сравнения на равенство получается "плоской" относительно кол-ва бит, а на больше-меньше — иерархической по модулю 2 (ты назвал "как дешифратор" , но и они не всегда иерархические опять же из-за наличия многовходовых вентилей).
T>Не стоит, согласен, но по другим причинам. По-моему, большая ассоциативная память просто не нужна.
Это пока ты матрицу перемножаешь как в той ссылке, а если у нас сотни _независимых_ потоков исполнения крутятся, а весь контекст вычислений сбросить в память — это тебе не 16 регистров в память сбросить, а еще бы знать, где в этой памяти контекст одного потока исполнения, и где — другого... В общем, сложностей хватает даже теоретических. Как спец-процессор для _пакетного_ выполнения задач data-flow хорош, это видно невооружённым взглядом, а вот в случае с реал-тайм — это ХЗ, ХЗ.
T>Для этого необходимо делать так, чтобы токены не выбрасывались. Планирование вычислений и сортировка токенов с соответствии со "временем выполнения программы" решает эту проблему.
Это иногда зависит от входных _данных_, с чего я и встрял. Даже обычный парсер какого-нить контекстно-зависимой грамматики ИМХО в состоянии "засрать" вариантами всю наличную ассоциативную память при "удачном" раскладе и графы будут выплёвываться в обычную память, а значит — прощай распараллеливание такой весьма параллельной по-сути задачи.
T>А вот сумматор нужен. Или эквивалентная ему схема.
В принципе не суть, схема сравнения на больше-меньше может быть чуть проще сумматора, но сложность в терминах O(N) эквивалентна до множителя. Однако, играет рояль не только сложность в кол-ве вентилей, а быстродействие, т.е. длина самой длинной аппаратной цепочки, а она в этих схемах одинакова и зависит от кол-ва бит линейно.
T>Я к этому делу пришёл два года тому назад. И даже сделал модель, как видишь. T>Мне нравится быстро проверять свои идеи, чего и остальным желаю.
Молодец, только вот от идеи до массовой реализации — сам понимаешь. Даже в той подветке про SymADE мне ситуация кажется менее безнадёжной, т.к. организовать немедленное производство ПО гораздо проще, чем железки. ПО можно разрабатывать поэтапно, опять же, с достижением результата на каждом этапе, а железка должна быть сразу без багов и сразу в рыночных конкурентноспособных характеристиках.
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[12]: Может массовых процессоров 32+ ядрами и не будет?
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) эквивалентна до множителя. Однако, играет рояль не только сложность в кол-ве вентилей, а быстродействие, т.е. длина самой длинной аппаратной цепочки, а она в этих схемах одинакова и зависит от кол-ва бит линейно.
Почему я и спрашивал, разрабатывал ли ты железо. У тебя предпосылки неправильные, и выводы, соответственно, тоже.
T>>Я к этому делу пришёл два года тому назад. И даже сделал модель, как видишь. T>>Мне нравится быстро проверять свои идеи, чего и остальным желаю. V>Молодец, только вот от идеи до массовой реализации — сам понимаешь. Даже в той подветке про SymADE мне ситуация кажется менее безнадёжной, т.к. организовать немедленное производство ПО гораздо проще, чем железки. ПО можно разрабатывать поэтапно, опять же, с достижением результата на каждом этапе, а железка должна быть сразу без багов и сразу в рыночных конкурентноспособных характеристиках.
"Сразу без багов" — это ты errata к MIPS/Intel/ARM не видел.
Рекомендую.
Если будет модель реальной системы (процессор+компилятор), уже будет неплохо.
Посмотрим, в общем.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[13]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, 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>Посмотрим, в общем.
Никто же не против, и в отличие от, говорить, что "все заведомо г-но и никому заведомо не нужно" не буду (ибо сам человек увлекающийся), но очевидные вопросы хотелось задать, так что — ничего личного.
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[14]: Может массовых процессоров 32+ ядрами и не будет?
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 видел, вполне достойно. Процент ошибок у железячников в пересчете на вентиль на многие порядки ниже, чем у программистов, в пересчетё на машинную инструкцию. Да уже высказывался несколько лет назад на эту тему.
Эффект от ошибки в железе больше.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[15]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, 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" написали, а как произвольные вложенные циклы из ЯВУ так же разворачивать и упорядочивать в общем случае — совершенно непонятно.
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[16]: Может массовых процессоров 32+ ядрами и не будет?
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>Модели процессора? И компилятор под него? Прямо здесь и сейчас? А ты связь с реальностью не теряешь, случаем?
Нет. Не надо компилятор. Надо модель процессора и программу для него. Программу можно и на ассемблере написать.
Я связь с реальностью не теряю. Написанием моделей я её поддерживаю. Я отвечаю за свою глупость (если моя идея глупа) своим потраченным временем.
Модель ассоциативной памяти не менее быстро — ещё день.
Итого, за выходные ты сможешь подтвердить или опровергнуть свои слова.
А я тебя очень сильно зауважаю.
V>>>Это, кстати, ответ на еще один вопрос — зачем одной ассоциативной памяти много исполнительных блоков. Затем, что выход одной операции может служить аргументом множества других операций, т.е. по идее может образоваться множество пар из одного токена. T>>Не может по условиям образования пар, если всё делать более-менее нормально. V>Я тебе пример привёл, где принципиально один выходной токен может образовывать кучу пар с другими — это банальный восходящий разбор с возвратами. После каждого очередного вывода в общем случае доступно более одного правила для последующего вывода.
Я могу построить программу так, чтобы этого не произошло. Более того, я так и построю программу. У меня ассоциативная память ничего не умеет, кроме, как образовывать пары.
Зато она хорошо масштабируема.
T>>Ассоциативную память надо делать как можно более простую. Предложенный тобой вариант с размножением страдает теоретическими проблемами (как определить, кого и когда надо размножать для анализируемой программы) V>Это предложенный не мной вариант, это автором data-flow предложенный. А твоя, с одним выч.узлом и циклическими очередями к нему — это самотворчество, имеющее большие проблемы с теоретическим обоснованием. Сам принцип data-flow — это автораспределение нагрузки, есть свободные парные токены и есть свободное выч.устройство — гоу на исполнение. Нет никакого смысла городить ассоциативную память ради одного приатаченного исполнительного блока, ибо ты не получишь того самого автораспределения нагрузки, ради которого все эти пляски.
Автораспределение нагрузки страдает большим недостатком — оно невероятно неэффективно. Это было доказано в ходе исследований, в которых я частично участвовал (а потом подтвердил своей моделью). Буквально, выполнение той же программы с планированием, где будет выполняться тот или иной узел, происходит в несколько раз быстрее, чем без такого планирования.
Цепочки передачи токенов от АП к ИУ имеют заметную задержку.
Поскольку мы планируем, как часто будет передаваться токен и куда, и мы знаем, что наружу он будет передаваться значительно реже, то нам выгодно обеспечить быстрый путь токена к ближайшему ИУ. Поскольку это чаще.
V>И твоё моделирование расчёта матрицы здесь — это хорошо, но, согласись, узкий класс задач.
Характерный. То же самое будет происходить со всеми вычислительными фортрановскими задачами, практически.
T>>и практическими — взрывной параллелизм, проблемы с порядком вычислений. V>Взрывной парралелизм — это св-во не процессора, а конкретной задачи. Там, где возможностей расспараллеливания не хватает, делают очереди и стеки, типа как упомянутый разбор на обычных процах или как вы делали по ссылке. Но это же все алгоритмы надо менять, и не компилятор это там делал, заметь, эту оптимизацию вы выполняли "вручную" — тонкий такой намёк любителю Хаскеля и противнику оптимизаций.
Я противник бессмысленной оптимизации вручную и тогда, когда не знаешь, что будешь делать вообще.
Поэтому модель системы у меня написана не оптимальна. Я не знал, как её сделать.
А оптимизации, что я выполнял вручную, могут быть выполнены компилятором, все алгоритмы для этого продуманы. Было бы время реализовать.
T>>Это плохой вариант. V>Так какой именно вариант плохой? Когда у нас много сравнивающих узлов и много вычислительных узлов? Это же "классика" (если это слово применимо к data flow). Или "плохой" — это "ты мне не нравишься"?
Это плохой вариант — когда много АП и много ИУ и все связаны со всеми.
Что самое интересное, даже в этом случае АП делается по описанному мной варианту с одним входом и одним выходом, просто делается коммутационная сеть.
V>Я с самого начала подветки и сказал, что именно в этом и есть проблемы у data-flow, по крайней мере у тех вариантов, у которых публиковались функциональные схемы "будущих потенциальных разработок". Этот неприятный момент очевиден, и я это сказал первый, можно было мне не возвращать.
Так и нечего к нему возвращаться. Зачем ты к нему вернулся? Ведь сам этот путь проделал, я тебя не подталкивал.
Поэтому впредь отталкивайся от лучшего варианта, например, моего.
T>>Эксперименты показывают, что 32-х слотов вполне достаточно. V>Эксперименты показывают, что вы эту программу на "ассемблере data flow" написали, а как произвольные вложенные циклы из ЯВУ так же разворачивать и упорядочивать в общем случае — совершенно непонятно.
Товарищи из автоматического распараллеливания умеют это делать ещё с... не знаю. Когда были сделаны первые систолические машины и разработаны методы получения систолического разложения алгоритмов? Вот, с того времени.
Мои бывшие коллеги, учёные из ИТМиВТ, все эти преобразования делать умеют, даже прототип компилятора Фортрана есть (с моим разборщиком, кстати). Надо будет мне его восстановить для моей модели.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[16]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, 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>Пионерской организацией за версту несет. Вы думаете ваши "стоили заоблачно" и "копейки" — это круто звучит? Да нихрена вы цен не знаете, и знать их не можете в принципе. Хватит понты кидать уже, смешно.
А вот это не опечатка. Еще к означенным понтам стоит прибавить смешные экскурсы в "физику" в дискуссии об архитектурах. Такая каша может только улыбку вызывать. Простите, вы таки "тополог", или "спициалист" по архитектурам? Это вообще разные специальности, нельзя хорошо разбираться в том и другом сразу. Вот зато ни в чем сразу не разбираться можно, это не фокус .
Re[17]: Может массовых процессоров 32+ ядрами и не будет?
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? Массовое производство спасёт отца русской демократии (уже спасает, и весьма заметно).
G>А вот это не опечатка. Еще к означенным понтам стоит прибавить смешные экскурсы в "физику" в дискуссии об архитектурах. Такая каша может только улыбку вызывать. Простите, вы таки "тополог", или "спициалист" по архитектурам?
Да ради бога, пусть вызывает улыбку. Рассуждения эти вообще ответвились из требования быстродейтсвующей ассоциативной памяти, и были постольку-поскольку. А насчёт физики — ну не буду же я здесь подробно описывать, почему не воспринимаю кремний всерьёз? Если человек не знает, что есть пороговое напряжение для полупроводника, и никак не реагирует на этот аргумент, если не ориентируется в проводимости материалов и не видел "шумовую" составляющую на АЧХ и на высокочастотных осциллографах, то это разговор в пустоту, кому это будет интересно? Мне повезло посвятить приличный период в своё время на разработку цифровой передачи по радио-каналам, со спецами по СВЧ проработал бок-о-бок не один год, и как раз о физике вещей могу поговорить с удовольствием, был бы собеседник... А топология — это несколько другой уровень, не находишь? И изменяется эта область довольно быстро вслед за уменьшением процесса (отслеживал до 2002-го года примерно, и всё время удивлялся скорости изменений, тогда как раз бум развития был). Однако, через принципиальные ограничения материалов не перепрыгнешь всё-равно. У меня, например, вызывает улыбку твоё решение привести сюда цифры по затратам. Я ведь тоже могу привести, правда не актульные, а уровня 99гг, но тем интереснее было бы сравнить, тем и смешнее тебе показались бы собственные аргументы, ибо, такое ощущение, что ты как только что это всё увидел, запечатлел себе некий "снапшот".
Неконструктив, короче. Я ведь и начал с того, что речь не идёт о тех технологиях, что есть сейчас, т.к. рыночную модель flow-процессоров еще никто и не начал разрабатывать (а пентиум 5 лет разрабатывали, если помнишь), и позволил себе предположить, к чему докатимся за более чем 5 лет... А ты мне сиюминутные цены выдаешь.
G>Это вообще разные специальности, нельзя хорошо разбираться в том и другом сразу. Вот зато ни в чем сразу не разбираться можно, это не фокус .
Гадание на кофейной гуще тоже за фокус сходит, главное, не относится к этому серьёзно.
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[17]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, 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>Поэтому впредь отталкивайся от лучшего варианта, например, моего.
Скромно и со вкусом.
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[18]: Может массовых процессоров 32+ ядрами и не будет?
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>Скромно и со вкусом.
Если есть другие, отталкивайся от них. Мой вариант был приведён только в качестве примера лучшего варианта.
Главное, не отталкивайся от плохого варианта с многими большими АП и многими ИУ, соединёнными каждый-с-каждым.
И не приводи теоретических соображений. Приводи практические. Они мне понятней.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[19]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, thesz, Вы писали:
T>Исследования показали, что такая организация неэффективна, что есть организации с более высоким КПД.
Есть ссылки на исследование именно этого факта?
Просто в твоём случае исследования показали несколько иное: что упорядочивание операций способно контроллировать кол-во промежуточных токенов, а это малость ортогонально кол-ву исполняющих устройств.
T>То есть, матричное умножение можно распараллелить, а разбор грамматик — принципиально требуется распараллелить. T>Как ты думаешь, я на это куплюсь?
Я думал, что ты и так это знаешь, и лишь старался ненавязчиво напомнить, без пошлого "поди-ка почитай хоть немного на эту тему", что про стековый разбор, что про сдвиг-свертку, что про паралельный недетерминированный разбор, навроде Эрли.
Дело в том, что умножение матриц не порождает неизвестное заранее кол-во промежуточных результатов, стандартный алгоритм вообще не требует доп. памяти для промежуточных результатов. Память под промежуточные результаты нам понадобилась именно в результате распараллеливания для хранения частичных сумм. И чем больше захочется уровня распараллеливания, тем больше нам надо промежуточных сумм. Если расчёт выполняет одно ИУ, как в твоём случае, то я вообще не вижу, где здесь распараллеливание и нафига козе баян? Сложить сумму из N членов это N-1 сложений, хоть иерархически, хоть последовательно.
А все эти алгоритмы недетерминированного разбора работают с помощью стека (или его аналога), для применениия системы правил на входную цепочку. Вместо стека некоторые алгоритмы перебирают все варианты "паралельно" (не физически параллельно, а алгоритмически), строя дерево вариантов, начиная от корня к произвольно кустящимся ветвям и листьям. Разве нам нужен стек или рекусия (принципиально заведомо неизвестной вложенности) для умножения матрицы?
T>Вот из-за таких передёргиваний и отпадает всякое желание общаться.
Оно пропадает от взаимного непонимания, и это проблема, в случае априорного нежелания разобраться в вопросе.
T>Ещё раз — сведения не мои, сведения из PTAPG. Это не я описался, это они, авторы PTAPG, жизнь положившие на разбор грамматик.
T>В паскале-подобном языке требующих контекстно-свободного разбора правил вот, сколько: арифметические выражения, структура блоков выполнения и... всё!
T>Два, ну, три. Ну, четыре места. А всяких списков переменных, списков аргументов, списков процедур и других списков и не-списков — кучами.
Ндааа... И эти люди запрещают мне ковыряться в носу... Фишка в том, что достоверно узнать, что вот тут у нас список, а тут еще что-то можно лишь после распознавания полной грамматикой. Заодно и ошибки выявить.
Ход твоих мыслей я понял, он заключается в том, что из системы правил некоей КС грамматики довольно часто можно выдрать подмножества правил, которые будут принадлежать классу регулярных грамматик. Сказать что валялся — не сказать ничего. Скаже по секрету, что вообще-то компиляторы и так бьют на лексические и синтаксические анализаторы. Да, предположим, что если "независимых" регулярных и КС грамматик "в мире одинаково", то учитывая общепринятое выделение регулярного подмножества из КС при разборе, регулярных получается больше... Наповал... (А что ты собрался делеать с этими "огрызками", кстати? Ведь без семантики ты не отличишь даже имя переменной от имени типа)
Могу еще по секрету сказать, что весь мейнстрим ЯП — он даже в КС не вписывается, полные грамматики языков обычно контекстно-зависимые. (Не против слова "обычно"?). И вот эту систему контекстно-зависимых грамматик упрощают или разбивают на систему из КС, и тогда мы получаем, что КС грамматик всегда больше чем КЗ...
Как тебе такое кино? Реально полные грамматики являются контекстно зависимыми, но разборщики для них мы пишем только регулярные и КС, ибо не существует пока способа построить эффективный распознаватель КЗ для общего случая. И по статистике, имплементаций КС конечно же больше, чем имплементаций КЗ, а имплементаций РГ еще больше.
Прикольный феномен, не спорю, но говорить на основании этого, что самих грамматик такого-то типа больше — это пять.
T>>>А вот CYK, работающий над разными частями текста, неважно, в какой он грамматике, может быть весьма параллелен. Весьма. V>>Это если "разные части текста" можно чётко поделить на независимые части, т.е. найти позиции, где разборщик заведомо будет в нач. состоянии. В принципе, для большинства популярных ЯП — не сложно.
T>Вот. Как минимум, для большинства современных ЯП. Да даже для контекстно-зависимого C++ это возможно.
До тех пор, пока макросами декларация класса не побъётся на отдельные файлы и тела методов — тоже. Вот с этими отдельными кусками без начала и без конца, да еще и с макрами — не так просто будет, ибо тот синтаксис, который допустим в теле декларации класса, недопустим в теле метода и наоборот. А еще прикольнее, если один и тот же файл с макрами включается дважды или даже трижды в разные места с разными определениями макросов... И типичный ведь приём в кроссплатформенной разработке.
T>Произвольное появление пар гарантируется семантикой упорядочения. Всё хорошо в АП с упорядочиванием токенов, ILP будет выявляться "на уровне" — можно больше суперскаляра, можно меньше. T>Если есть другие, отталкивайся от них. Мой вариант был приведён только в качестве примера лучшего варианта. T>Главное, не отталкивайся от плохого варианта с многими большими АП и многими ИУ, соединёнными каждый-с-каждым. T>И не приводи теоретических соображений. Приводи практические. Они мне понятней.
Ты и практически это не показал. Еще раз, если не понял, упорядочивание токенов ортогонально размерности схемы поиска пар в АП, нельзя сравнивать метры и киллограммы. И тем более, что я могу увидеть на модели, на который мы вольны быстродействие сколь угодно многопортовой АП выбрать равным 1 такту? Чем больше будет ИУ, тем быстрее отработает алгоритм, это понятно и так.
Давай сделаем следующим образом, ты придумаешь хотя бы один довод, почему, например, в твоей модели с приоритезацией, если добавить десяток другой ИУ и сделать АП многопортовой на вход и выход, то это ухудшит такой-то показатель. Тогда сяду и сделаю, и сравню с твоей моделью, практически на "слабо".
Еще раз возвращаюсь к тому, что у любого эксперимента должна быть цель. Ты пока ставишь цель "просто провести хоть какой-то эксперимент по датафлоу", тогда, типа, зауважаешь только лишь за сам факт проведения эксперимента. Это десад натуральный, и самое время попросить собеседника туда и прогуляться. Экспериментов мне и без датафлоу хватает, когда есть цель их проводить. Любой проектировщик достаточную часть времени экспериментами и так занят (если он адекваный проектировщик), дабы как можно меньше ошибок допустить на начальных стадиях любого проекта, особенно, если каждый раз идут новые технологии.
У тебя ведь тоже была вполне конкретная цель — проверить идею с приоритезацией на эффект в экономии ресурсов. А тут в чём должна состоять цель?
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[20]: Может массовых процессоров 32+ ядрами и не будет?
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 такту? Чем больше будет ИУ, тем быстрее отработает алгоритм, это понятно и так.
В качестве модели пойдёт.
Сейчас и тебе станет известно, что если применить хэщирование на входе, то входной поток шириной в несколько элементов можно переразбить статистически равномерно на произвольное количество потоков шириной в один элемент. Что означает, что мы можем задействовать однопортовые АП и получить результат, как для многопортовой.
На всякий случай: если у нас на входе несколько элементов одновременно, то хешированием и буферизацией мы можем свести их к одному элементу на входе схемы, описанной выше.
V>Давай сделаем следующим образом, ты придумаешь хотя бы один довод, почему, например, в твоей модели с приоритезацией, если добавить десяток другой ИУ и сделать АП многопортовой на вход и выход, то это ухудшит такой-то показатель. Тогда сяду и сделаю, и сравню с твоей моделью, практически на "слабо".
Поэтому надо всё сводить к однопортовой АП. И это известно, как делать.
(токены с одинаковым ключом попадут в один и тот же АП, поэтому пары будут производиться, как обычно. но параллельно на нескольких АП.
(кстати, для регистрового файла суперскаляра такая схема будет значительно сложней, если она, вообще, возможна)
V>Еще раз возвращаюсь к тому, что у любого эксперимента должна быть цель. Ты пока ставишь цель "просто провести хоть какой-то эксперимент по датафлоу", тогда, типа, зауважаешь только лишь за сам факт проведения эксперимента. Это десад натуральный, и самое время попросить собеседника туда и прогуляться. Экспериментов мне и без датафлоу хватает, когда есть цель их проводить. Любой проектировщик достаточную часть времени экспериментами и так занят (если он адекваный проектировщик), дабы как можно меньше ошибок допустить на начальных стадиях любого проекта, особенно, если каждый раз идут новые технологии.
V>У тебя ведь тоже была вполне конкретная цель — проверить идею с приоритезацией на эффект в экономии ресурсов. А тут в чём должна состоять цель?
В проверке на реальных (насколько уж нас с тобой на реальность хватит) примерах особенностей выполнения программ на dataflow машине. Приобретение понимания этих особенностей и понимания, как можно обойти слабые места, буде мы их обнаружим.
Я проверял на умножении матриц. Ты, если хочешь, можешь попробовать реализовать параллельный разбор.
И это будет круто!
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[21]: Может массовых процессоров 32+ ядрами и не будет?
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>Сейчас и тебе станет известно, что если применить хэщирование на входе, то входной поток шириной в несколько элементов можно переразбить статистически равномерно на произвольное количество потоков шириной в один элемент. Что означает, что мы можем задействовать однопортовые АП и получить результат, как для многопортовой.
Возвращаясь в сотый раз к нашим баранам, в случае минимизированных НКА/ДКА и так уже всё "кешировано" (эта часть минимизации называется минимизацией по входным сигналам). У меня разборщик смотрит не сам токен или символ, а его код из таблицы отображения, полученной в процессе минимизации КА.
На всякий случай: если у нас на входе несколько элементов одновременно, то хешированием и буферизацией мы можем свести их к одному элементу на входе схемы, описанной выше.
Да, не обратил внимания в начале на этот момент. Кол-во разрядов под ключ для 2-х АП может иметь на 1 разряд меньше (и схема сравнения тоже), для 4-х АП на 2 разряда меньше и так далее... жить можно.
Остаётся вопрос еще в равномерном распределении данных, если этих АП будет много, т.е. компилятор должен заранее знать, сколько у нас АП. В случае матриц такое статическое разбиение провести можно довольно точно, в отличие от разбора, где лишь "равновероятно", а там уже как карты лягут на конкретной входной последовательности. В любом случае, компилятор должен заранее знать кол-во этих блоков... т.е. байткоды и JIT-генерация будут рулить всё-равно.
T>Я проверял на умножении матриц. Ты, если хочешь, можешь попробовать реализовать параллельный разбор.
T>И это будет круто!
Есть еще один момент. Чтобы в полный рост экспериментировать на сложных задачах, нужен компилятор в этот ассемблер. А то в моём случае, немного подправь грамматику — и "компиллируй" вручную заново, а там нихрена себе сложность. Есть ссылки на принципы компиляции под dataflow, нумерования токенов и т.д.? Сложность я еще вижу в том, что для матриц, например, токены хранят сами данные, в то время как в моём случае токены больше будут хранить ссылку на структуры в памяти.
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[22]: Может массовых процессоров 32+ ядрами и не будет?
T>>Соображения по поводу распределения токенов по узлам в моей статье тоже есть. T>>В моём случае так же выгодно посылать токены на то же самое устройство, если это возможно. V>Это как раз понятно, мне в твоей схеме не очень понравилось, что токены выходят во "внешнюю" систему — упорядочиватель (накладные расходы как бы, т.е. короткие небольшие вычисления будут произвоиться дольше, чем могли бы), с другой стороны, тут есть определённый бенефит (в конце написал).
Короткие небольшие вычисления проходят через АП около ИУ. Они вытеснят оттуда "вычисления будущего" за счёт упорядочения.
T>>Поэтому надо будет применять так называемые cache oblivious алгоритмы (не зависящие от размера кэша). В этом случае умножение матрицы выполняется путём рекурсивного разбиения её на все более мелкие части. T>>Что означает, что у нас, в принципе, неограниченная рекурсия! V>Ах ты вот, про что... Только коэф рекурсии невероятно низкий получится, вряд ли будут перемножать матрицы, размерностью более, чем кол-во ячеек АП, а вот входные цепоки на порядки больше размерности — это запросто.
Обработка видео может привести к обработке матриц в несколько десятков и даже сотен тысяч элементов.
Там часто решаются задачи минимизации Ax=b методом наименьших квадратов, где x и b имеют размерности (2,3)xN (N — те самые десятки тысяч).
Аэродинамика — крыло надо посчитать с щагом в 1см^2 (хотя я не знаю точности, думаю, что порядок такой). Да ещё умножь на третье измерение. Матрица будет блочной, разреженной, но очень большой.
T>>(замечу, что есть языки, где имена типов отличаются V>а ну да, и как раз мейнстимовые.
, нет?
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, нумерования токенов и т.д.? Сложность я еще вижу в том, что для матриц, например, токены хранят сами данные, в то время как в моём случае токены больше будут хранить ссылку на структуры в памяти.
Что ж. Придётся откапывать исходники.
Не обещаю быстрого результата, но постараюсь.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[23]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, 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 этого не требуется.
Здравствуйте, Gaperton, Вы писали:
G>Прототип по технологии "кремний на германии" (правильно это называется так), который используется в СВЧ, стоил не так давно порядка 200К USD за запуск на фабрике IBM (открытые данные с mosis.com). Если мне память не изменяет. Прототип в кремнии — порядка 40К. Техпроцесс — 0,13. Это чтобы вы представляли себе, что означает "германий как раз таки недорогой".
G>Ни Интел, ни другие производители процессоров, включая IBM, которая имеет фабрики способные производить чипы по технологии "кремний-на-герминии", не полагаются на данную технологию при производстве процессоров. Данная технология сейчас применяется там, где без нее совсем никак. В основном, это сверхвысокочастотный RF-дизайн.
Кстати, порыл эту тему, и выяснилось, что ты малость поторопился. Да, подобная технология не получила широкого применения из-за "несовместимости" с существующими производственными линиями для кремния, от того и дорогая. Однако, в последнее время просачивается информация о том, что научились делать сплав кремния с германием (у них решётки близкого размера), и у этого сплава обнаружилась замечательная подвижность зарядов, не хуже, чем у арсенида галлия, а то и получше. Экспериментальные вентили свыше 250GHz отработали... (Не сплав, конечно, прямо кристалл выращивается из смешанных атомов)
Но самое примечательное, что механические и химические св-ва "сплава" таковы, что он сможет быть использован на имеющемся оборудовании под кремний. И Intel и IBM по слухам во всю работают по этому направлению, но подробностей не выдают даже под NDA... Так что, германий, похоже, всё-таки выстрелил. Еще бы научились добывать его менее затратно, а то в природе его гораздо больше серебра, но стоит как золото, и это часть проблемы.
Re[24]: Может массовых процессоров 32+ ядрами и не будет?
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>Или от того, что состояния НКА представлены не данными, а функциями, поменялась суть вещей? Я пока внимательно с кодом не разбирался, но есть ли у них такое же "схлопывание" эквивалентных состояний, которое получается само при работе по минимизированному НКА?
(немного другая техника, тем не менее)
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>У вас был "ассемблер"?
Компилятор, почти.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[25]: Может массовых процессоров 32+ ядрами и не будет?
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>Для определённых (вычислительных) задач можно.
Если перестать ходить вокруг дя около, то это стандартная задача генерирования "хорошей" хеш-функции. (похоже, я слишком мало букв пишу, чтобы выразить свою мысль). Я имел ввиду тот факт, что нахождение лучшей хеш-фии для известного кол-ва ячеек, по которым надо разбивать данные, гораздо более простая задача, чем нахождение лучшей хеш ф-ии для заведомо произвольного кол-ва ячеек, и в общем случае нерешаема.
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[26]: Может массовых процессоров 32+ ядрами и не будет?
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, насколько я понял. Т.е. компилятор для того же бинарного узла "+" должен будет нагенерить типов на всевозможные сочетания его операндов.
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'))). Половина всех пересылок будет проходить через всего один уровень иерархии (сортирующую псевдо-АП).
Как-то так.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[27]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, thesz, Вы писали:
T>Ты, видимо, с алгебраическими типами не знаком?
В других системах оно называется "discriminated union" и обладает теми же характеристиками. В boost для С++ есть типобезопасная реализация unions, например.
T>А вот обработка EPlus наверху может быть специализирована (типы классов и тп). Но это не наша забота.
Дык я и высказывался относительно последующей обработки EPlus, и там, где в Хаскеле нужен будет паттерн-матчинг по реальному подтипу, в С++, например, возможен статический вариант "визитора", т.е. на этапе компиляции. Но опять же, это всё верно для "ручного" конструирования разборщиков, автоматически же можно заведомо нагенерить узлы для всех допустимых сочетаний операндов "+" заранее и обойтись вообще без диспетчеризации для поиска обработчиков (т.е. использовать соответствие 1:1). Ведь в конечном коде и так должна быть обработка всех допустимых вариантов, так зачем сначала сливать в бутылочное горлышко, а затем разливать из него? Вопрос не праздный, просматривая исходники я иногда замечаю, что народ увлекается паттерн матчингом и алгебраическими типами "на ровном месте", а разве для реализации абстракции "классификация" нет статических ср-в?
T>Вот функция: zip(i,j). Она берёт последовательность i3i2i1i0 и j3j2j1j0 и создаёт последовательность i3j3i2j2i1j1i0j0.
T>Возьмём индексы реального цикла i и j. Сдвинем их вправо на два разряда и пропустим через наш zip.
T>Мы получили индекс устройства (АП+ИУ), в котором будут выполняться 16 близко лежащих вычислений. Пересылки соседним вычислениям, что не поместились в наш индекс, будут иметь адресатом индекс АП+ИУ с небольшим расстоянием по манхеттенской метрике (max (abs (x-x') (abs (y-y'))). Половина всех пересылок будет проходить через всего один уровень иерархии (сортирующую псевдо-АП).
Это всё зависит от семантики i и j, при простой адресации матрицы так и есть, я упоминал о сложности поиска хорошей хеш ф-ии для общего случая, когда семантика не очевидна для компилятора.
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[27]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, thesz, Вы писали:
T>В комбинаторах я пишу максимально декларативно, единственное, за чем мне надо следить — отсутствие левой рекурсии. Списки разбираются many1 p = pure ( <*> p <*> many p в отличии от LR, где many1 p = pure (flip ( <*> many p <*> p (many p = many1 p <|> return []). Нужна контекстно-зависимая грамматика — будет. Не нужна — не будет.
Кстати, я когда-то и сам высказывался за комбинаторный разбор на этих форумах, как простой способ реализации КЗ-парсеров путём разбиения их на некое множество КС-парсеров (некоторые из них даже вырождаются в регулярные). Тут мы поимеем приличный оверхед при классической реализации парсеров, понятное дело, т.к. в каждый КС-парсер уйдёт значительная часть общей грамматики, но будет эта дублированная часть реализована независимо в каждом из них. С другой стороны, при "ручной" реализации комбинаторов мы можем явным образом повторно использовать код для этих общих частей. Интересный момент, надо будет подолжить эксперименты (у меня есть кое-какие потуги в автоматическом разбиении грамматики на более простые составные части с выделением регулярного подмножества, т.к. хотелось иметь возможность разрабатывать парсеры без классической независимой разработки лексера и парсера, чтобы иметь возможность сразу описывать общую систему правил языка... а ведь тут можно пойти и дальше, я имею ввиду автоматическое разложение КЗ ).
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[28]: Может массовых процессоров 32+ ядрами и не будет?
T>>Ты, видимо, с алгебраическими типами не знаком? V>В других системах оно называется "discriminated union" и обладает теми же характеристиками. В boost для С++ есть типобезопасная реализация unions, например.
Похожими. Не "теми же".
T>>А вот обработка EPlus наверху может быть специализирована (типы классов и тп). Но это не наша забота. V>Дык я и высказывался относительно последующей обработки EPlus, и там, где в Хаскеле нужен будет паттерн-матчинг по реальному подтипу, в С++, например, возможен статический вариант "визитора", т.е. на этапе компиляции.
В Хаскеле, значит, не на этапе компиляции.
Ох. Ну, да ладно.
V>Но опять же, это всё верно для "ручного" конструирования разборщиков, автоматически же можно заведомо нагенерить узлы для всех допустимых сочетаний операндов "+" заранее и обойтись вообще без диспетчеризации для поиска обработчиков (т.е. использовать соответствие 1:1).
К разборщикам это имеет мало отношения. Семантика при их построении влияет только насколько она в них может быть выражена.
V>Ведь в конечном коде и так должна быть обработка всех допустимых вариантов, так зачем сначала сливать в бутылочное горлышко, а затем разливать из него? Вопрос не праздный, просматривая исходники я иногда замечаю, что народ увлекается паттерн матчингом и алгебраическими типами "на ровном месте", а разве для реализации абстракции "классификация" нет статических ср-в?
Сравнение с образцом, например.
К тебе приходит только что созданный объект, про структуру которого ты, в общем случае, не всё знаешь. Статически отклассифицировать его будет невозможно.
Поэтому разбирай динамически. Что визитором, что сравнением с образцом.
T>>Мы получили индекс устройства (АП+ИУ), в котором будут выполняться 16 близко лежащих вычислений. Пересылки соседним вычислениям, что не поместились в наш индекс, будут иметь адресатом индекс АП+ИУ с небольшим расстоянием по манхеттенской метрике (max (abs (x-x') (abs (y-y'))). Половина всех пересылок будет проходить через всего один уровень иерархии (сортирующую псевдо-АП). V>Это всё зависит от семантики i и j, при простой адресации матрицы так и есть, я упоминал о сложности поиска хорошей хеш ф-ии для общего случая, когда семантика не очевидна для компилятора.
Ты сперва простые случаи разбери.
В случае "неочевидности семантики" (что это означает, вообще? мы не смогли восстановить dataflow граф?) можно скатываться к последовательному коду.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[29]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, thesz, Вы писали:
T>К тебе приходит только что созданный объект, про структуру которого ты, в общем случае, не всё знаешь. Статически отклассифицировать его будет невозможно. T>Поэтому разбирай динамически. Что визитором, что сравнением с образцом.
Вот здесь не понимаю логики. Что значит "приходит"? Из "ниоткуда", что-ли? Для рассматриваемого случая объект формируется парсером, т.е. на момент формирования точный тип объекта уже известен, а значит прямо в процессе формирования к нему можно привязать обработчик. Ты, похоже, не понял вопроса: зачем сливать в бутылочное горлышко, если потом надо будет разливать. Ключевая фраза: "зачем сливать"?
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[30]: Может массовых процессоров 32+ ядрами и не будет?
T>>К тебе приходит только что созданный объект, про структуру которого ты, в общем случае, не всё знаешь. Статически отклассифицировать его будет невозможно. T>>Поэтому разбирай динамически. Что визитором, что сравнением с образцом.
V>Вот здесь не понимаю логики. Что значит "приходит"? Из "ниоткуда", что-ли? Для рассматриваемого случая объект формируется парсером, т.е. на момент формирования точный тип объекта уже известен, а значит прямо в процессе формирования к нему можно привязать обработчик. Ты, похоже, не понял вопроса: зачем сливать в бутылочное горлышко, если потом надо будет разливать. Ключевая фраза: "зачем сливать"?
Это можно fusion сделать. {-# RULES #-} в Хаскеле.
А может и компилятор догадаться.
Сливать надо потому, что так удобней писать код. Так лучше структурировать программу.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[31]: Может массовых процессоров 32+ ядрами и не будет?
T>Сливать надо потому, что так удобней писать код. Так лучше структурировать программу.
Может надо использовать "правильные языки" (С)?
А то ты про алгебраические типы говорил, а в compile-time template<typename Left, typename Right> AstNode — такой же алгебраический тип с т.з. компилятора, не находишь? И того же уровня классификация из разряда "чтобы удобнее было" сохраняется.
Это я про то, что мы можем для нашего случая специализировать всего 1 метод этого класса для различных сочетаний и избежать диспечеризации в ран-тайм. А если использовать частичную специализацию, то можно описывать обработчики для целого класса за раз.
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[32]: Может массовых процессоров 32+ ядрами и не будет?
T>>Сливать надо потому, что так удобней писать код. Так лучше структурировать программу. V>Может надо использовать "правильные языки" (С)?
Неужто C++, судя по typename? 8-O
V>А то ты про алгебраические типы говорил, а в compile-time template<typename Left, typename Right> AstNode — такой же алгебраический тип с т.з. компилятора, не находишь?
Нет, не нахожу.
V> И того же уровня классификация из разряда "чтобы удобнее было" сохраняется.
Нет, не сохраняется.
V>Это я про то, что мы можем для нашего случая специализировать всего 1 метод этого класса для различных сочетаний и избежать диспечеризации в ран-тайм. А если использовать частичную специализацию, то можно описывать обработчики для целого класса за раз.
То же можно сделать с помощью rewrite rules, когда упрёмся в производительность.
Не надо выполнять преждевременной оптимизации.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[33]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, thesz, Вы писали:
V>>А то ты про алгебраические типы говорил, а в compile-time template<typename Left, typename Right> AstNode — такой же алгебраический тип с т.з. компилятора, не находишь?
T>Нет, не нахожу.
Поищи внимательней еще раз.
Хинт: в С++ порой значительная часть программы выполняется в compile-time при использовании шаблонов.
V>> И того же уровня классификация из разряда "чтобы удобнее было" сохраняется.
T>Нет, не сохраняется.
Тогда поясни в чём же твоё "чтобы удобней было" состояло, если не в искуственной классификации. Потому как в этом смысле сохраняется полностью, да еще в самом типобезопасном варианте.
V>>Это я про то, что мы можем для нашего случая специализировать всего 1 метод этого класса для различных сочетаний и избежать диспечеризации в ран-тайм. А если использовать частичную специализацию, то можно описывать обработчики для целого класса за раз.
T>То же можно сделать с помощью rewrite rules, когда упрёмся в производительность. T>Не надо выполнять преждевременной оптимизации.
Ха-ха, это для хаскеля такой финт — преждевременная оптимизация, а для шаблонов С++ — стандартное использование, которое экономит многие строки кода.
И вообще, не стоит бездумно разбрасываться шаблонными фразами, удешевляя смысл сокрытой в них мудрости.
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[34]: Может массовых процессоров 32+ ядрами и не будет?
V>>>А то ты про алгебраические типы говорил, а в compile-time template<typename Left, typename Right> AstNode — такой же алгебраический тип с т.з. компилятора, не находишь? T>>Нет, не нахожу. V>Поищи внимательней еще раз. V>Хинт: в С++ порой значительная часть программы выполняется в compile-time при использовании шаблонов.
Что это означает?
V>>> И того же уровня классификация из разряда "чтобы удобнее было" сохраняется. T>>Нет, не сохраняется. V>Тогда поясни в чём же твоё "чтобы удобней было" состояло, если не в искуственной классификации. Потому как в этом смысле сохраняется полностью, да еще в самом типобезопасном варианте.
{-$ OPTIONS -fwarn-incomplete-patterns -fwarn-overlapping-patetrns #-}
V>>>Это я про то, что мы можем для нашего случая специализировать всего 1 метод этого класса для различных сочетаний и избежать диспечеризации в ран-тайм. А если использовать частичную специализацию, то можно описывать обработчики для целого класса за раз. T>>То же можно сделать с помощью rewrite rules, когда упрёмся в производительность. T>>Не надо выполнять преждевременной оптимизации. V>Ха-ха, это для хаскеля такой финт — преждевременная оптимизация, а для шаблонов С++ — стандартное использование, которое экономит многие строки кода.
Я потерял твою мысль.
Приведи пример кода на Хаскеле и на C++.
V>И вообще, не стоит бездумно разбрасываться шаблонными фразами, удешевляя смысл сокрытой в них мудрости.
Действительно.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[35]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, thesz, Вы писали:
V>>>>А то ты про алгебраические типы говорил, а в compile-time template<typename Left, typename Right> AstNode — такой же алгебраический тип с т.з. компилятора, не находишь? T>>>Нет, не нахожу. V>>Поищи внимательней еще раз. V>>Хинт: в С++ порой значительная часть программы выполняется в compile-time при использовании шаблонов.
T>Что это означает?
В данном примере диспечеризация у нас выполняется в compile-time, и в течении этого процесса семейство конкретных инстациирований приведенного шаблонного типа AstNode — такой же точно алгебраический тип, как для тебя алгебраические типы Хаскеля в run-time.
T>{-$ OPTIONS -fwarn-incomplete-patterns -fwarn-overlapping-patetrns #-}
И что? Для статической диспетчеризации в моём случае опций никаких задавать не надо, компилятор или линковщик и так знать дадут, если что-то забуду.
Например, для этого подхода ругнется линковщик при отсутствии обработчика нужной комбинации:
// H - файлtemplate<typename Left, typename Right>
class AstNode : public AstNodeBase {
Left left; Right right;
public:
// пусть это будет переопределение виртуального методаvirtual void Process();
};
...
// CPP-файл
// обработчик для конкретного типаvoid AstNode<int, int>::Process() { ... }
А в этом случае компилятор даст знать при отсутствии нужной пары:
// объявлениеtemplate<typename Node>
struct Processor;
// определение для конкретной пары типовtemplate
struct Processor<AstNode<int, int> > {
static void Process(AstNode<int, int> node) { ... }
};
Букв много, но теми же макрами их режут как-то так:
DEF_PROC(int, int, { ... } );
T>>>Не надо выполнять преждевременной оптимизации. V>>Ха-ха, это для хаскеля такой финт — преждевременная оптимизация, а для шаблонов С++ — стандартное использование, которое экономит многие строки кода. T>Я потерял твою мысль. T>Приведи пример кода на Хаскеле и на C++.
Для С++ привёл, для Хаскеля ты уже приводил. Скопировать еще раз? Логичней будет, чтобы ты объяснил, куда бы приспособить твой лозунг насчёт преждевременной оптимизации.
Re[36]: Может массовых процессоров 32+ ядрами и не будет?
T>>Что это означает? V>В данном примере диспечеризация у нас выполняется в compile-time, и в течении этого процесса семейство конкретных инстациирований приведенного шаблонного типа AstNode — такой же точно алгебраический тип, как для тебя алгебраические типы Хаскеля в run-time.
Нет глубокого анализа.
ors (Or a b) = ors a >> hPutStr h " " >> ors b
ors (Var a) = hPutStr h (show (varIds Map.! a))
ors (Not (Var a)) = hPutStr h ("-" ++ show (varIds Map.! a))
ors (Label a) = hPutStr h (show (labIds Map.! a))
ors (Not (Label a)) = hPutStr h ("-" ++ show (labIds Map.! a))
ors _ = error $ "Formula is not in CNF."
(HDL Atom, предшественник Bluespec, модуль SAT.hs)
T>>{-$ OPTIONS -fwarn-incomplete-patterns -fwarn-overlapping-patetrns #-} V>И что? Для статической диспетчеризации в моём случае опций никаких задавать не надо, компилятор или линковщик и так знать дадут, если что-то забуду. V>Например, для этого подхода ругнется линковщик при отсутствии обработчика нужной комбинации: V>
V>// H - файл
V>template<typename Left, typename Right>
V>class AstNode : public AstNodeBase {
V> Left left; Right right;
V>public:
V> // пусть это будет переопределение виртуального метода
V> virtual void Process();
V>};
V>...
V>// CPP-файл
V>// обработчик для конкретного типа
V>void AstNode<int, int>::Process() { ... }
V>
У тебя очень, очень простой анализ. Неглубокий.
V>Букв много, но теми же макрами их режут как-то так: V>
V>DEF_PROC(int, int, { ... } );
V>
Да-да. Макрами режут.
T>>>>Не надо выполнять преждевременной оптимизации. V>>>Ха-ха, это для хаскеля такой финт — преждевременная оптимизация, а для шаблонов С++ — стандартное использование, которое экономит многие строки кода. T>>Я потерял твою мысль. T>>Приведи пример кода на Хаскеле и на C++.
V>Для С++ привёл, для Хаскеля ты уже приводил. Скопировать еще раз? Логичней будет, чтобы ты объяснил, куда бы приспособить твой лозунг насчёт преждевременной оптимизации.
Хаскельный вариант работает медленней, но он сильно гибче. Он занимает меньше места в коде, для его использования не надо делать макры.
И несмотря на гибкость, он всё ещё проверяется во время компиляции, с указанием чего и как у тебя неправильно с точностью до набора образцов на реализацию и места в коде, которое избыточно.
Всё то же, что в C++ и более того, но медленней. Быстро можно сделать с помощью правил переписывания. Выполнить оптимизацию.
Твои соображения насчёт compile time dispatch заботятся только о скорости, об удобстве использования во вторую (хорошо, если так) очередь.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[18]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, vdimas, Вы писали: V>Потому что, "может быть распараллелено" и принципиально требует паралельного расчёта — это разные вещи. Матрица принципиально не требует, а ты лишь параллелишь до определённого уровня, подсчитывая и иерархически складывая частичные суммы. Ну блин, прямо Америку открыл, посмотри на БПФ и алгоритм "бабочки", и заодно станет понятно, почему он требует кол-во отсчётов, равное степени двойки — та же фигня.
оффтоп: БПФ (т.е. Кули-Тьюки) не требует степени двойки. Это популярный миф.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[15]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, thesz, Вы писали:
T>Пиши модель процессора, пиши для него программу разбора, попытайся получить взрывной параллелизм. О любых результатах расскажи.
Кстати, наткнулся у тебя в блогах на твои эксперименты с примитивными комбинаторами разбора. И там ты сам же и замечал, что даже на небольших входных цепочках у тебя быстро заканчивается память. Собственно, на твоём комбинаторе выбора и идёт раздвоение параллелизма. Но ситуация всё-равно плохо понятна в случае Хаскеля, он же ленивый.
Re[19]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, Sinclair, Вы писали:
S>оффтоп: БПФ (т.е. Кули-Тьюки) не требует степени двойки. Это популярный миф.
Какой миф? Алгоритм-то простейший. Посмотри сам, что происходит в случае подачи кол-ва отсчётов, отличное от степени двойки. Там всего два варианта: прореживание по частоте, или прореживание по времени, известные алгоритмы являются вариациями на эти темы. Но суть тут одна — каждый из вариантов использует БПФ на основе степени 2-ки как "подпрограмму", и отличаются они только способами формирования подпоследовательностей.
Есть еще распространённый в "бытовом применении" вариант: это дополнение отрезка нулями по краям и умножение на такую ф-ию окна, чтобы минимизировать влияние этих дополненных отрезков. Этот вариант, в отличие от первых двух, искажает конечный результат, поэтому используется для задач, где точность не важна.
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[20]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, vdimas, Вы писали: V>Какой миф?
Обычный, городской V>Алгоритм-то простейший. Посмотри сам, что происходит в случае подачи кол-ва отсчётов, отличное от степени двойки. Там всего два варианта: прореживание по частоте, или прореживание по времени, известные алгоритмы являются вариациями на эти темы. Но суть тут одна — каждый из вариантов использует БПФ на основе степени 2-ки как "подпрограмму", и отличаются они только способами формирования подпоследовательностей.
Вообще-то в алгоритме используется разложение количества отсчетов на простые делители. Вычислительная сложность линейно зависит от произведения количества делителей на их "размер". В случае N = 2^K получается ровно К=log2(N) делителей, само разложение выполняется тривиально, и делитель равен двум. "Подпрограмма" получается ровно одна. В случае, когда N простое, всё получается как можно хуже: сложность алгортма возвращается к O(N^2) для обычного ДПФ. Сравни, к примеру, заголовки 4.1. и 4.2 здесь. Так что алгоритм К-Т по основанию два — всего лишь популярный частный случай.
Существует библиотека, построенная на темплейтах C++ и бусте с локи, где БПФ преобразование выполняется для любого непростого N.
V>Есть еще распространённый в "бытовом применении" вариант: это дополнение отрезка нулями по краям и умножение на такую ф-ию окна, чтобы минимизировать влияние этих дополненных отрезков. Этот вариант, в отличие от первых двух, искажает конечный результат, поэтому используется для задач, где точность не важна.
Да, к примеру, если у тебя есть 1000 отсчетов, ты можешь дополнить его до 1024 и воспользоваться "тупым К-Т алгоритмом". А можешь разложить 1000 на 2*2*2*5*5*5 и получить временные характеристики, близкие к 2*2*2*2*2*2*2*2, безо всяких искажений спектра.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[21]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, Sinclair, Вы писали:
S>Существует библиотека, построенная на темплейтах C++ и бусте с локи, где БПФ преобразование выполняется для любого непростого N.
Доклад про это решение был представлен на конференции PSI'03 (http://psi.nsc.ru/psi03/list_e.shtml) "Marcin Zalewski and Sibylle Schupp. Polymorphic Algorithms FFT-Implementations That Share". Доклад в ПостСкрипте здесь.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[21]: Может массовых процессоров 32+ ядрами и не будет?
S>Да, к примеру, если у тебя есть 1000 отсчетов, ты можешь дополнить его до 1024 и воспользоваться "тупым К-Т алгоритмом". А можешь разложить 1000 на 2*2*2*5*5*5 и получить временные характеристики, близкие к 2*2*2*2*2*2*2*2, безо всяких искажений спектра.
Не совсем, низкая степень повторного использования слагаемых получится, тут у тебя в 2 раза примерно больше времени на вычисление. И еще есть тот факт, что в двоичном виде парная позиция — это перестановка бит в обратном порядке, и вообще много операций простым сдвигом выполняются, а для множителя 5 надо будет умножениями заниматься. Для всяких однокристаллических ЭВМ без умножителя это критично.
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[22]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, vdimas, Вы писали:
V>Не совсем, низкая степень повторного использования слагаемых получится, тут у тебя в 2 раза примерно больше времени на вычисление.
Кстати, перечитал статью — что-то с памятью. У меня отложилась значительно более оптимистичная оценка результатов.
На практике, парни наблюдали странные эффекты с разбросом времен в 1000 раз, и на момент публикации не имели понятия, где там порыта собака.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[23]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, Sinclair, Вы писали:
V>>Не совсем, низкая степень повторного использования слагаемых получится, тут у тебя в 2 раза примерно больше времени на вычисление. S>Кстати, перечитал статью — что-то с памятью. У меня отложилась значительно более оптимистичная оценка результатов. S>На практике, парни наблюдали странные эффекты с разбросом времен в 1000 раз, и на момент публикации не имели понятия, где там порыта собака.
Некоторые умудряются память динамически выделять во время расчётов БПФ (в одной из верхних ссылок по гуглю есть нехороший исходник), да мало ли что еще.
Принципиально больше всего повторений для множителя 2. Если какой-то из множителей встречается лишь однажды, то для него никаких повторений. Каждый множитель, отличный от 2-х, это суть классическое прореживание по частоте или времени (не принципиально) над БПФ, со всеми вытекающими. Например разложение 5*3*2^N эквивалентно 15*2^N, прореживание = 15, а это полный Вася, собирать потом 15 независимых БПФ.
--------------
На самом деле, классический БПФ экономит хоть и много, но на практике недостаточно — слишком много умножений всё-равно. Так вот еще один способ свести кол-во вычислений практически к K*Log(N), где К-константа, — это ограничение разрядности таблицы синусов. В принципе, 3-х разрядов достаточно для очень многих применений (особенно в случае непрерывной фильтрации результатов — ошибки сглаживаются). При таком раскладе вместо log(N) умножений имеем максимум К=7 различающихся вариантов умножения, и если таблица синусов захардкожена в умножениях на константу в развёрнутом цикле (6 различных значений синуса S всего, т.к. 0 пропускается при кодогенерации), то известно сколько раз встречается каждый из вариантов (M), т.е. захардкожено умножение на известную константу S*M, да и среди этих констант бывают повторения (с точностью до знака). В общем, на однокристалках без умножителей можно довольно приличные последовательности в реалтайм обсчитывать.
И самое главное, если мы сами разрабатываем некую систему, то нет никакой причины брать длину последовательности, отличную от степени двойки.
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[24]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, vdimas, Вы писали:
V>Технология generics в .Net позволит при надобности построить полностью типизированные узлы в рантайм, но у меня оччень большие сомнения в необходимости этого (обрати внимание на вывод типа узлов верхнего уровня — мрак).
А можно о выделенном чуть поподробнее?
now playing: Depeche Mode — Come Back
Re[25]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, EvilChild, Вы писали:
V>>Технология generics в .Net позволит при надобности построить полностью типизированные узлы в рантайм, но у меня оччень большие сомнения в необходимости этого (обрати внимание на вывод типа узлов верхнего уровня — мрак).
EC>А можно о выделенном чуть поподробнее?
Я имел ввиду, что сейчас AST обычно оперируют базовыми классами, что-то вроде такого:
class Expr {}
class BinExpr : Expr {
public Expr Left {get; }
public Expr Right { get; }
}
В то время как можно и так:
class Expr {}
class BinExpr<TLeft, TRight> : Expr
where TLeft : Expr
where TRIght: Expr
{
public TLeft Left {get; }
public TRIght Right { get; }
}
Я подобную технику применял для динамических вычислителей по вводимым юзверем формулам. Сначала строил AST как в первом варианте (код формирования AST в процессе разбора проще для первого варианта), а затем упрощал/трансформировал выражение, порождая результат в виде второго варианта, который к тому же был сделан на value-type (это важно для генериков, иначе такая оптимизация не имеет большого смысла). Получал примерно в 4-6 раз более быстродейственную версию такого динамического вычислителя. Все эти потуги были от того, что вводимая формула натравливалась на большое кол-во данных (котировки ценных бумаг).
В случае сложных формул тип формулы (узла верхнего уровня) выглядит жутко, ну дык я его только в отладке посмотреть и могу, и то из любопытства.
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[5]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, AndrewVK, Вы писали:
T>>Поверю, когда увижу.
AVK>Так официально сказано, что там слегка улучшенные ядра 486. Что может помешать?
Помешать? Подсистема памяти, шедулер потоков и заданий, и исполнительный конвейр в шейдерных процессорах весьма специально устроены. Ну очень нетрадиционно. Обычный аппаратный мультитред проиграет им по отдаче производительности с миллиметра кристалла. И модель выполнения там отличается от обычной — шейдерные программы относительно короткие, и работают пачками на разных данных, подо что и оптимизируется архитектура. Вот такого:
"алгоритм любой сложности, написанный на С/С++ можно будет сгрузить на GPU."
V>Кстати, наткнулся у тебя в блогах на твои эксперименты с примитивными комбинаторами разбора. И там ты сам же и замечал, что даже на небольших входных цепочках у тебя быстро заканчивается память. Собственно, на твоём комбинаторе выбора и идёт раздвоение параллелизма. Но ситуация всё-равно плохо понятна в случае Хаскеля, он же ленивый.
Приводи ссылку.
А то я такого не помню.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[26]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, vdimas, Вы писали: V>Я подобную технику применял для динамических вычислителей по вводимым юзверем формулам. Сначала строил AST как в первом варианте (код формирования AST в процессе разбора проще для первого варианта), а затем упрощал/трансформировал выражение, порождая результат в виде второго варианта, который к тому же был сделан на value-type (это важно для генериков, иначе такая оптимизация не имеет большого смысла). Получал примерно в 4-6 раз более быстродейственную версию такого динамического вычислителя.
Пардон, а почему не сделать Expr.Compile? Тогда-то наверное вообще в 40-60 раз быстрее выйдет, нет?
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[27]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, Sinclair, Вы писали:
S>Пардон, а почему не сделать Expr.Compile? Тогда-то наверное вообще в 40-60 раз быстрее выйдет, нет?
Нет, раза в полтора максимум получалось по отношению к вычислителю на структурах в лучшем случае, там же сплошной инлайн идёт, вот примерный код вычислителей:
struct PlusInt32<TLeft, TRight> :IEval<int>
where TLeft:IEval<int>
where TRight:IEval<int> {
...
public int Eval() { return _left.Eval() + _right.Eval(); }
}
struct Const<T> : IEval<T> {
...
public T Eval() { return _value; }
}
struct Int32Field : IEval<int> {
...
public int Eval() { return _reader.ReadInt32(_index); }
}
Последний вычислитель и есть бутылочное голышко, которое делает ненужным дальнейшую оптимизацию (отрабатывает раз в 20-30 медленнее первых двух при первом обращении к полю в этой же строке, и примерно в 5 раз при последующих) — вычисления происходили практически со скоростью выборки данных. Опять же, апп-сервер потенциально работает очень долго без перезагрузок, и бесконечно набивать память сборками как бы спорно, да и ручной эмит сложен малость (ту разницу получил на экспериментах на простейших операциях +-*/) , и было это за пару лет до VS2008.
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[28]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, vdimas, Вы писали:
V>Здравствуйте, Sinclair, Вы писали:
S>>Пардон, а почему не сделать Expr.Compile? Тогда-то наверное вообще в 40-60 раз быстрее выйдет, нет?
V>Опять же, апп-сервер потенциально работает очень долго без перезагрузок, и бесконечно набивать память сборками как бы спорно, да и ручной эмит сложен малость (ту разницу получил на экспериментах на простейших операциях +-*/) , и было это за пару лет до VS2008.
Expression.Compile() работает через DynamicMethod
MSDN:
You can use the DynamicMethod class to generate and execute a method at run time, without having to generate a dynamic assembly and a dynamic type to contain the method. The executable code created by the just-in-time (JIT) compiler is reclaimed when the DynamicMethod object is reclaimed. Dynamic methods are the most efficient way to generate and execute small amounts of code.
Re[29]: Может массовых процессоров 32+ ядрами и не будет?
K>Ну я тоже из непонятливых. DynamicMethod появился одновременно с дженериками.
Действительно. Тем не менее, одна из указанных причин было так же нежелание возиться с еммитом, тем более, что это практически ничего не давало в плане быстродействия.
... << RSDN@Home 1.2.0 alpha rev. 786>>
Re[4]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, AndrewVK, Вы писали:
R>> (2) за счёт повышения тактовой частоты в ближайшую декаду сещественного роста не предвидится
AVK>Я бы не был так уверен в этом. Текущая ситуация с частотами в основном обусловлена маркетинговыми моментами. ... Однако при этом известно, что теперешние Penryn массово работают на 4.5ГГц с воздушным охлаждением.
Все равно про рост частоты можно забыть, такого как в предыдущие 10-20 лет не будет уже никогда.
Уже при частоте 4.5ГГц свет проходит за такт 6 см (если не ошибаюсь). Даже без технологических тонкостей, при существенно большх частотах это уже бы была скорее распределенная система. Когда за такт сигнал(свет) не успевает пройти весь кристалл, архитектура значительно усложнится. И это уже будет "не полноценная" частота условная, так сказать. сильно не синхронная работа разных кусков кристалла связанных медленными каналами.
Re[5]: Может массовых процессоров 32+ ядрами и не будет?
Здравствуйте, Silver_s, Вы писали:
S_>Все равно про рост частоты можно забыть, такого как в предыдущие 10-20 лет не будет уже никогда. S_>Уже при частоте 4.5ГГц свет проходит за такт 6 см (если не ошибаюсь). Даже без технологических тонкостей, при существенно большх частотах это уже бы была скорее распределенная система. Когда за такт сигнал(свет) не успевает пройти весь кристалл, архитектура значительно усложнится.
Удивительный факт — архитектура современных процессоров уже не вполне синхронна. Задержки прохождения синхроимпульса (который, кстати, распространяется далеко не со скоростью света) начали учитывать уже давно, еще когда никаких гигагерцев не было.
... << RSDN@Home 1.2.0 alpha 4 rev. 1196 on Windows Vista 6.1.7000.0>>
