Здравствуйте, 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 мне ситуация кажется менее безнадёжной, т.к. организовать немедленное производство ПО гораздо проще, чем железки. ПО можно разрабатывать поэтапно, опять же, с достижением результата на каждом этапе, а железка должна быть сразу без багов и сразу в рыночных конкурентноспособных характеристиках.
.
