Мы привыкли думать о вычислениях как о битах, регистрах и арифметике. А что, если базовой единицей вычисления сделать не бит, а локальную геометрическую конфигурацию тетраэдров? В этой статье я покажу дискретный тетраэдрический движок состояний, симметрийную канонизацию, аттракторы, иерархические jump-таблицы и реальные замеры на RTX 3090 — с измеренным exact-ускорением в 554.92 раза на одной и той же задаче.
Нулевой раздел. Объяснение без формул: что здесь вообще происходит (добавлено)
Прежде чем говорить про мотивы, генераторы, аттракторы и jump-таблицы, давайте разберём идею совсем на пальцах.
Если совсем коротко
Обычно в вычислениях базовой единицей состояния является бит:
либо 0,
либо 1.
В этой работе я пробую другой подход: базовой единицей состояния становится не бит, а маленькая локальная геометрическая конфигурация.
То есть вместо «одной лампочки вкл/выкл» мы работаем с маленькой сценой из нескольких объектов, у которых есть положение и состояние.
Простыми словами
Если бит — это один переключатель, то здесь «ячейка состояния» — это маленькая геометрическая конструкция. Не одна кнопка, а мини-сборка.
Из чего состоит эта мини-сборка
Я беру 4 позиции — их можно представить как 4 места в маленькой локальной схеме.
Из этих 4 мест:
3 заняты тетраэдрами,
1 место пустое.
То есть в каждый момент времени мы имеем маленькую сцену: тут стоит тетраэдр, тут стоит тетраэдр, тут стоит тетраэдр, а тут пусто.
Простыми словами
Представьте 4 посадочных места. На трёх местах стоят фигурки, одно место свободно. Это и есть самый базовый «кадр» системы.
Что такое тетраэдр в этой модели
Здесь тетраэдр — это не реалистичный физический объект с массой и трением. Это дискретный элемент состояния.
У каждого тетраэдра в модели есть два параметра:
Ориентация
Это то, как он повернут. В коде я использую 12 дискретных ориентаций.
Фаза
Это дополнительная внутренняя метка состояния. В коде я использую 3 фазы.
Итого один занятый слот может находиться в:
12×3=36
вариантах состояния.
Простыми словами
У тетраэдра есть: «куда он смотрит» и «в каком режиме он находится». Например: повернут так и находится в фазе 1. Это просто два маленьких дискретных параметра.
Что такое локальная конфигурация
Теперь соберём всё вместе.
У нас есть:
4 позиции,
3 заняты,
1 пустая,
на каждой занятой позиции тетраэдр имеет:
ориентацию,
фазу.
Вот такую маленькую локальную сцену я и рассматриваю как единицу состояния.
Простыми словами
Это просто снимок маленького кусочка системы: кто где стоит, кто где пустой, кто как повернут, кто в каком режиме.
Почему я называю это «мотивом»
В статье я называю такую локальную конфигурацию словом motif — по-русски «мотив».
Но здесь нет никакой мистики и нет обязательного внешнего бэкграунда, который нужно знать заранее.
Я мог бы назвать это:
локальным шаблоном,
локальным паттерном,
локальной конфигурацией,
локальной сценой.
Смысл один и тот же.
Мотив = маленькая типовая локальная конфигурация
Простыми словами
Слово «мотив» тут не надо воспринимать как что-то специальное и страшное. Это просто короткое имя для маленькой стандартной сценки, с которой работает алгоритм.
Что делает алгоритм с мотивом
Теперь важный шаг.
Мы не просто храним мотив. Мы умеем его преобразовывать.
Для этого вводятся несколько базовых операций — я называю их генераторами.
Можно думать о генераторе как о маленьком локальном правиле:
один тетраэдр сдвинулся,
пустое место переехало,
ориентация обновилась,
фаза обновилась.
То есть генератор — это одна «микрокоманда», которая переводит одну локальную конфигурацию в другую.
Простыми словами
Генератор — это просто маленькое правило перестройки. Как будто вы взяли эту мини-сцену и слегка её передвинули по фиксированным правилам.
Что такое путь
Одна команда — это ещё не «программа». Поэтому я использую путь — короткую последовательность генераторов.
Например такой:
[2,2,1,2,2]
Это значит:
сначала применяем генератор 2,
потом ещё раз генератор 2,
потом генератор 1,
потом снова 2,
и ещё раз 2.
Именно такую последовательность можно рассматривать как маленькую программу над локальной конфигурацией.
Простыми словами
Если генератор — это одна команда, то путь — это мини-скрипт из нескольких команд.
Что означает запись motif → F(motif)
Теперь можно объяснить самую пугающую на вид запись.
Когда я пишу:
motif→F(motif)
это означает всего лишь:
взяли одну локальную конфигурацию;
применили к ней фиксированное правило F;
получили новую локальную конфигурацию.
Здесь F — это и есть путь, то есть последовательность генераторов.
Простыми словами
Это не страшная формула. Это буквально: «было одно состояние → применили правило → стало другое состояние».
Почему здесь вообще появляются большие числа
Если считать все варианты такой локальной конфигурации, их получается довольно много.
Потому что:
пустой слот может стоять в 4 местах;
у каждого из 3 занятых слотов есть 36 вариантов состояния.
Значит raw-space содержит:
4*36*36*36=186624
вариантов.
Но дальше мы учитываем симметрии и схлопываем эквивалентные конфигурации в канонические классы.
Так остаётся:
Canonical motifs: 15 576
Простыми словами
Сначала вариантов много. Потом выясняется, что многие из них на самом деле «одинаковые по сути, просто повёрнуты». После удаления таких дубликатов остаётся намного меньше типовых состояний.
Что такое аттрактор здесь
Если много раз применять один и тот же путь к мотиву, то состояние обычно не прыгает бесконечно случайно.
Оно попадает в более устойчивую структуру:
либо в цикл,
либо в маленькое семейство циклов,
либо в большой бассейн состояний, которые притягиваются к одному и тому же циклу.
Это и есть attractor-структура в этой модели.
Простыми словами
Если много раз крутить систему по одному и тому же правилу, она обычно не ведёт себя хаотично бесконечно. Она «скатывается» в устойчивый режим.
Где здесь ускорение
Самое интересное начинается тогда, когда мы понимаем:
если один и тот же путь применяется очень много раз, то можно не выполнять его каждый раз заново, а заранее подготовить таблицу:
этот мотив после 64 повторов перейдёт сюда;
после 4096 повторов — сюда;
после 16 миллионов повторов — сюда.
Тогда вместо длинной цепочки вычислений мы делаем один lookup по таблице.
Простыми словами
Мы не повторяем одну и ту же длинную работу заново, а заранее запоминаем результат длинной цепочки. Как будто заранее знаем «чем закончится длинный сценарий» и сразу прыгаем в финал.
Что важно понимать до чтения остальной статьи
Если после этого раздела запомнить только 5 вещей, то дальше читать будет намного проще:
Мотив — это маленькая локальная конфигурация из 4 позиций.
Ориентация — дискретный поворот тетраэдра.
Фаза — дополнительное дискретное внутреннее состояние.
Путь — короткая последовательность правил преобразования.
F(motif) — результат применения такого пути к мотиву.
Совсем коротко
бит → одна лампочка
мотив → маленькая геометрическая сценка
генератор → одна команда
путь → короткая программа
jump-таблица → заранее вычисленный результат длинной программы
Я просто беру маленькие геометрические состояния, заставляю их эволюционировать по фиксированным правилам и смотрю, можно ли сильно ускорить длинные композиции этих правил.
1. Зачем вообще считать не битами, а тетраэдрами
Обычная вычислительная логика устроена очень просто: есть биты 0/1, есть операции над ними, есть длинные цепочки преобразований.
Но можно посмотреть на вычисление иначе: не как на манипуляцию отдельными битами, а как на эволюцию локальных геометрических конфигураций.
Вместо «ячейка памяти хранит 0 или 1» можно взять более богатую сущность:
положение объекта,
ориентацию,
фазу,
допустимые симметрии,
правила локального преобразования.
В моей модели такой сущностью стал локальный кластер тетраэдров.
Бит — это лампочка: либо включена, либо выключена.
Тетраэдрический мотив — это уже маленькая механическая конструкция, у которой есть:
как она стоит,
куда повернута,
в каком состоянии находится,
как она может перестроиться дальше.
То есть одна «единица состояния» становится намного богаче обычного бита.
2. Почему именно тетраэдр
Тетраэдр — это простейшее трёхмерное тело с богатой симметрией:
4 вершины,
4 грани,
6 рёбер.
У него достаточно сложная геометрия, чтобы порождать интересные классы состояний, но при этом он ещё достаточно прост, чтобы всё это можно было эффективно кодировать.
В вычислительном смысле тетраэдр удобен по трём причинам:
у него компактная группа симметрий;
локальное состояние можно дискретизировать;
последовательности преобразований можно предвычислять.
Тетраэдр — это «минимальная интересная 3D-фигура». Куб слишком привычный. Треугольник — уже не 3D. А тетраэдр — это маленькая 3D-ячейка, на которой уже можно строить нетривиальную «механику состояний».
3. Как устроено состояние в движке
Чтобы не утонуть в терминах, сразу зафиксирую, что именно я называю в статье.
Тетраэдр
Это базовый элемент системы — маленький “объект”, который может стоять в одной из нескольких ориентаций и находиться в одной из нескольких фаз.
Это деталька,которую можно повернуть и перевести в другой режим.
Ориентация
Это дискретный поворот тетраэдра.
В коде у меня 12 возможных ориентаций.
Тетраэдр может быть направлен по-разному,и я кодирую эти варианты числом от 0 до 11.
Фаза
Это дополнительное дискретное внутреннее состояние тетраэдра.
В коде у меня 3 фазы.
Кроме поворота у тетраэдра есть ещё маленькая “внутренняя настройка” — например режим 0,1 или 2.
Локальная конфигурация
Я рассматриваю 4 позиции-слота.
Из них 3 заняты тетраэдрами, а 1 пустая.
Маленькая сценка из четырёх мест, где на трёх что-то стоит, а одно свободно.
Мотив (motif)
Мотив — это просто имя для такой локальной конфигурации.
Если бит — это одна лампочка, то мотив — это маленький геометрический шаблон.
F(motif)
Это результат применения правила преобразования F к данному мотиву.
Взяли локальную сцену,прогнали через правило,получили новую сцену.
В моей модели локальный кластер устроен так:
есть 4 слота;
в них находятся 3 тетраэдра;
1 слот пустой.
Каждый занятый слот хранит локальное состояние тетраэдра:
ориентация: 0..11,
фаза: 0..2.
Итого одно локальное состояние тетраэдра:
[ 12 × 3 = 36 ] вариантов.
Пустой слот кодируется отдельно.
То есть полный raw-state кластера — это конфигурация вида:
4 позиции,
из них 3 заняты,
в каждой занятой позиции — один из 36 вариантов.
Представьте 4 ячейки, как будто 4 места вокруг маленькой геометрической конструкции. На трёх местах стоят тетраэдры, одно место пустое. Каждый тетраэдр может:
стоять в одной из 12 ориентаций,
быть в одной из 3 фаз.
Из этого собирается локальная «сцена».
4. Сколько вообще таких состояний
Если не учитывать симметрии, то количество raw-state равно:
выбор пустого слота: 4,
три заполненных слота, в каждом по 36 вариантов.
[ 4 · 36^3 = 186,624 ]
Именно это и показал код:
Raw states: 186 624
Но это ещё не настоящие рабочие состояния, потому что многие из них эквивалентны с точностью до вращения тетраэдрической схемы.
Если просто «в лоб» перечислить все варианты, их почти 187 тысяч. Но среди них много одинаковых по сути, просто повернутых в пространстве. Как если бы вы посмотрели на один и тот же предмет с другой стороны — сам предмет не изменился, изменился только ракурс.
5. Симметрийная канонизация: как 186 тысяч состояний превращаются в 15 тысяч
Это один из ключевых шагов.
Мы берём группу вращений тетраэдра. Для неё я использовал 12 вращений — это ориентационно-сохраняющая группа симметрий тетраэдра, изоморфная A₄.
Для каждого raw-state мы:
применяем все допустимые симметрии;
получаем множество эквивалентных конфигураций;
выбираем канонический представитель, например, лексикографически минимальный packed-state.
Так raw-state схлопываются в классы эквивалентности.
Результат:
Canonical motifs: 15 576 Symmetry count: 12
То есть:[ 186,624 → 15,576 ]
Это уже серьёзное сжатие пространства состояний.
Мы перестаём хранить «одну и ту же фигуру, повёрнутую по-разному» как разные состояния. Мы говорим: у этой конфигурации есть «канонический вид», и всё приводим к нему. Это примерно как вместо «кошка лицом влево» и «кошка лицом вправо» хранить просто «кошка», если для задачи поворот не важен.
6. Что такое мотив
После канонизации базовой единицей вычисления становится motif — канонический локальный класс конфигурации.
То есть дальше движок работает уже не с произвольными «сырыми» состояниями, а с компактным идентификатором мотива:
[ \text{motifId} \in [0,15575] ]
Именно motif становится базовой «единицей вычисления».
После всей уборки и удаления дубликатов остаётся не 186 тысяч хаотичных вариантов, а 15 576 «типовых конструкций». Вот эти типовые конструкции и есть «слова» нашего геометрического языка.
7. Что такое генераторы преобразований
Дальше нужен механизм вычисления — то есть правила, как одна конфигурация переходит в другую.
Для этого вводятся 4 генератора:
[ G_0, G_1, G_2, G_3 ]
Каждый генератор делает три вещи:
переставляет слоты;
двигает один тетраэдр в пустую позицию;
изменяет его ориентацию и фазу;
слегка обновляет состояния остальных тетраэдров.
Фактически это локальная геометрическая операция переписывания.
Генератор — это как «одна маленькая команда»: что-то повернуть, что-то сдвинуть, пустое место поменять, обновить локальные состояния. То есть не арифметика, а маленькая геометрическая перестройка.
8. Что такое путь
Одна команда — это хорошо, но вычисление обычно состоит из последовательности команд.
Поэтому вводится путь — короткое слово над генераторами.
Например, базовый путь у меня был такой:
[ (2,2,1,2,2) ]
То есть:[ F = G_2 \circ G_2 \circ G_1 \circ G_2 \circ G_2 ]
Это уже не единичное движение, а маленькая программа.
Во второй и третьей версиях движка я использовал уже 8 разных путей:
pathId=0 [2,2,1,2,2] pathId=1 [0,1,2,3,0] pathId=2 [3,2,1,0,3] pathId=3 [1,1,1,1,1] pathId=4 [0,2,0,2,1] pathId=5 [3,3,0,1,2] pathId=6 [1,3,2,1,0] pathId=7 [2,0,3,1,2]
Если генератор — это одна команда, то путь — это короткий скрипт из 5 команд. То есть мы уже не просто «щёлкаем одной операцией», а задаём маленькую программу над геометрической системой.
9. Как происходит вычисление «в лоб»
Если делать всё напрямую, то для каждого мотива и каждого пути нужно последовательно применить все генераторы в слове.
Если путь повторяется много раз, например F⁶⁴, то приходится выполнять длинную цепочку переходов.
Именно так работает direct-режим.
Для случая F⁶⁴ и 4 млн элементов результаты такие:
Direct random time: 17,28 ms Direct grouped time: 10,10 ms
Это «честный тупой способ»: берём состояние, 5 раз применяем команды пути, потом ещё 64 раза повторяем весь путь, и так для миллионов элементов. Понятно, что это работает, но дорого.
10. Главная идея ускорения: предвычислить длинные композиции
Вот здесь начинается самое интересное.
Если путь фиксирован, то можно заранее вычислить, куда он переводит каждый мотив:
[ \text{motif} \to F(\text{motif}) ]
Это таблица J0 = F¹.
Но можно пойти дальше и заранее вычислить:
J1 = F⁶⁴
J2 = F⁴⁰⁹⁶
J3 = F²⁶²¹⁴⁴
J4 = F¹⁶⁷⁷⁷²¹⁶
То есть очень длинная программа превращается в один lookup. Именно это и есть jump-таблицы.
Вместо того чтобы каждый раз снова и снова выполнять длинную последовательность команд, мы делаем как в математике с таблицей степеней: заранее знаем, что получится после 64 шагов, после 4096 шагов, после 262 тысяч шагов, после 16.7 миллионов шагов. Тогда вычисление превращается в «сразу взять готовый ответ из таблицы».
11. Иерархия jump-таблиц
В base-64 варианте иерархия такая:
J0: F^1 J1: F^64 J2: F^4 096 J3: F^262 144 J4: F^16 777 216
Это означает, что:
J1 эквивалентен 64 применениям J0,
J2 эквивалентен 64 применениям J1,
и так далее.
Результат — очень глубокая композиция кодируется одной табличной операцией.
Это как матрёшка уровней ускорения: один уровень знает 1 шаг, следующий — 64 шага, следующий — уже 4096 шагов, и так дальше. Чем выше уровень, тем длиннее программа, спрятанная в одном lookup.
12. Почему понадобился ещё и binary jump hierarchy
Base-64 отлично работает для степеней 64, но плохо подходит для произвольного числа повторов.
Для этого была построена ещё и бинарная иерархия:
B0: F^1 B1: F^2 B2: F^4 B3: F^8 ... B24: F^16 777 216
Тогда любое число повторов N можно разложить по двоичным степеням и применить нужные jump-уровни. Это даёт лучший arbitrary-режим.
И код подтвердил это на практике:
Base64 arbitrary time: 3,86 ms Binary arbitrary time: 1,84 ms Binary arbitrary: 2,10x vs base64-arbitrary
Если нужно сделать не «ровно 64 в степени k», а какое-то произвольное число шагов, например 12 345 678, удобнее раскладывать не по 64, а по двоичным кускам: 1, 2, 4, 8, 16... Это стандартная идея «быстрого возведения», только применённая к геометрическим переходам.
13. Аттракторы: почему разные мотивы сходятся к одним и тем же циклам
Если взять отображение
[ \text{motif} \to F(\text{motif}) ]
то оно задаёт функциональный граф.
У такого графа каждая вершина имеет ровно одно исходящее ребро, а значит вся система распадается на:
хвосты,
циклы,
бассейны притяжения этих циклов.
Именно это и даёт аттракторную структуру.
Для разных путей картина оказалась очень разной. Например:
pathId=0 [2,2,1,2,2] | cycles=2, maxCycle=20, avgSteps=66,52, dominantBasin=15 486 (99,42%) pathId=5 [3,3,0,1,2] | cycles=3, maxCycle=145, avgSteps=26,21, dominantBasin=15 504 (99,54%) pathId=3 [1,1,1,1,1] | cycles=17, maxCycle=74, avgSteps=20,13, dominantBasin=7 913 (50,80%)
Если много раз применять один и тот же путь, система обычно не гуляет бесконечно куда попало. Она либо приходит в цикл, либо в маленькое семейство устойчивых режимов. Это как шарик, катящийся по поверхности: почти всегда он попадает в какую-то «ямку» или начинает крутиться по устойчивой траектории.
14. Что значат разные типы путей
Пути оказались не просто разными, а семантически разными.
Сильно сжимающие пути
Например, path 0 и path 5: почти все состояния затягиваются в один доминирующий basin. Это похоже на нормализацию или приведение к канонической форме.
Более выразительные пути
Например, path 3, path 2, path 6, path 7: больше циклов, больше разнообразия, меньше «схлопывание». Такие пути ближе к богатой логике состояний.
Какие-то пути работают как «пылесос» — почти всё засасывают в один режим. А какие-то пути больше похожи на «разветвитель» — сохраняют разнообразие и дают системе больше вариантов поведения. То есть пути начинают вести себя как разные инструкции процессора.
15. Packed metadata: как аттракторную информацию упаковали в один int
Для каждого (pathId, motifId) можно знать:
представителя цикла,
длину цикла,
число шагов до цикла.
Чтобы не читать несколько буферов, я упаковал это в один 32-битный integer:
representative: 14 бит,
cycleLength: 8 бит,
stepsToCycle: 10 бит.
Это уменьшает память и сокращает число чтений.
Вместо того чтобы хранить 3 разных числа в 3 разных местах, мы складываем их в одну компактную коробку из 32 бит. Меньше памяти — быстрее lookup.
16. Fused kernel: почему лучше сразу делать и jump, и attractor lookup
Отдельные проходы по памяти — дорого.
Поэтому был сделан fused-режим, который за один dispatch делает:
jump;
lookup packed attractor metadata.
То есть pipeline стал таким:
[ (\text{motifId},\text{pathId}) \to \text{newMotifId} + \text{attractorMeta} ]
Практически это оказалось очень удачным решением.
Вместо двух походов в память мы идём один раз: сразу прыгаем в итоговое состояние, сразу забираем всё, что нужно знать о его аттракторе. Это как сходить в магазин один раз и купить всё сразу, а не идти сначала за хлебом, потом отдельно за молоком.
17. Почему grouped pathId оказался быстрее random pathId
В direct-режиме путь для каждого элемента выбирается по pathId.
Если pathId случайный, потоки GPU идут по более «рваным» паттернам доступа. Если pathId сгруппирован, потоки становятся более согласованными.
Результат:
Direct random time: 17,28 ms Direct grouped time: 10,10 ms
То есть grouped scheduling даёт ускорение в 1.71x.
Для fused-режима эффект гораздо слабее:
Fused J1 random time: 1,85 ms Fused J1 grouped time: 1,74 ms
Это значит, что jump/fused-режим значительно устойчивее к path divergence.
Если соседние потоки делают похожую работу, GPU это любит. Если каждый поток живёт своей жизнью, начинаются потери. Поэтому «сортировать задачи по типу пути» — это хорошая идея, особенно для direct-режима.
18. Результаты по скорости
Вот ключевые результаты замеров.
Базовые тесты
Standard compute: 3,60 ms Direct F^64 random: 17,28 ms Direct F^64 grouped: 10,10 ms Jump J1 random: 1,62 ms Fused J1 random: 1,85 ms Fused J1 grouped: 1,74 ms Base64 arbitrary: 3,86 ms Binary arbitrary: 1,84 ms Base64 exact deep: 1,31 ms Binary exact deep: 1,66 ms
Простыми словами
Что это значит:
прямой пересчёт длинных путей — медленный;
jump-таблицы — очень быстрые;
fused-режим почти не уступает чистому jump;
binary лучше для произвольной глубины;
base64 лучше для точных степеней 64.
19. Что оказалось лучше для каких задач
Для F⁶⁴
Лучший режим — jump или fused jump.
Jump J1 random: 1,62 ms Fused J1 random: 1,85 ms
Против direct random:
17,28 ms
Для arbitrary repeat
Лучший режим — binary decomposition.
Binary arbitrary: 1,84 ms vs Base64 arbitrary: 3,86 ms
Для exact powers of 64
Лучший режим — base64 exact jump.
Base64 exact deep: 1,31 ms vs Binary exact deep: 1,66 ms
Если сильно упростить:
ровные большие степени → бери base64;
любое произвольное число шагов → бери binary;
нужна ещё информация про аттрактор → бери fused.
20. Самый важный тест: реальная точная задача на 30 секунд
Чтобы уйти от «оценок по линейной экстраполяции», я сделал реальный exact benchmark на 30 секунд.
Задача была одна и та же:
[ F^{4096} ]
Считалась двумя способами:
Direct exact: 64 последовательных запуска F⁶⁴.
Jump exact: 1 запуск J2 = F⁴⁰⁹⁶.
Обе реализации вычисляют одну и ту же точную функцию.
Результаты:
DIRECT EXACT F^4096 Time: 30,69 s Batches completed: 41 Exact depth per batch: F^4 096 Batches/sec: 1,3359 Path applications/sec: 21 887 824 042 Generator applications/sec: 109 439 120 208 JUMP EXACT F^4096 Time: 30,00 s Batches completed: 22 240 Exact depth per batch: F^4 096 Batches/sec: 741,3308 Path applications/sec: 12 145 964 037 056 Generator applications/sec: 60 729 820 185 278 Measured exact throughput speedup: 554,92x
Мы не сравниваем «примерно похожие штуки». Мы сравниваем одну и ту же задачу: либо выполнять её длинной прямой цепочкой, либо взять уже сжатый jump. И вот тут ускорение получилось 554.92x. То есть не «в теории», а реально, по секундомеру.
21. Почему 554.92x важнее, чем «миллионы раз по оценке»
Ранее по более глубоким jump-уровням можно было получить очень большие оценочные факторы, например миллионы раз, если линейно экстраполировать direct на F¹⁶·⁷⁷⁷·²¹⁶. Но это всё равно остаётся оценкой.
А вот ускорение в 554.92x на F⁴⁰⁹⁶ — это уже измеренный exact speedup.
22. За счёт чего вообще получается такая скорость
Теперь главный вопрос: почему это всё так быстро работает?
Причина №1. Мы считаем не арифметику, а переходы между классами состояний
Вместо длинной последовательности операций над числами мы работаем с компактными motif-id.
Простыми словами: Мы не считаем формулы в лоб, а ходим по карте уже известных состояний.
Причина №2. Симметрии сильно уменьшают пространство
Raw-state: 186,624 → Canonical motifs: 15,576.
Простыми словами: Мы избавились от огромного количества дубликатов.
Причина №3. Длинные программы предвычислены
F⁴⁰⁹⁶ превращается не в 4096 повторов, а в один lookup.
Простыми словами: Мы не повторяем длинную работу, а достаём уже готовый итог.
Причина №4. GPU хорошо любит табличные переходы малого размера
Все ключевые таблицы маленькие по современным меркам:
Generator table: ~0.24 MB
Base64 jump tables: ~2.38 MB
Packed attractor metadata: ~0.48 MB
Binary jump tables: ~11.88 MB
Простыми словами: Таблицы достаточно компактные, чтобы GPU быстро с ними работал.
Причина №5. Fused kernel уменьшает число проходов по памяти
Jump + attractor metadata делаются за один проход.
Простыми словами: Меньше бегаем туда-сюда по памяти — быстрее работаем.
Причина №6. Для arbitrary repeat используется правильная иерархия
Binary decomposition дала ускорение в 2.10x относительно base64 decomposition для произвольной глубины.
Простыми словами: Для разных типов задач нужен разный «способ прыжка». Мы это учли.
23. Что это НЕ означает
Чтобы остаться честными, нужно сказать и о границах метода.
Это не «ускорение любых вычислений»
Метод ускоряет длинные композиции в дискретной геометрической системе, а не произвольные задачи мира.
Простыми словами: Это не «новый суперкомпьютер для всего подряд», а очень сильный ускоритель для определённого класса вычислений.
Это не замена криптографии
Такой движок не заменяет SHA-256 и не делает валидный Bitcoin mining.
Простыми словами: Биткоин всё равно требует свой хеш, и сеть не примет «тетраэдрический ответ».
Это не магия
Основной выигрыш возникает потому, что вычисление имеет структуру, а структура позволяет сделать jump-таблицы.
Простыми словами: Если задача не имеет повторяемых переходов и симметрий, такого ускорения не будет.
24. Что это уже означает на практике
Зато вот что действительно означает:
У нас есть рабочий дискретный геометрический вычислитель:
богатая единица состояния;
симметрийная канонизация;
множество путей;
attractor-структура;
jump-компрессия.
У нас есть зачаток instruction set. Разные пути ведут себя по-разному: одни сильно сжимают пространство, другие дают богатую динамику, третьи создают длинные циклы.
У нас есть runtime-стратегия:
exact powers of 64 → base64 jump;
arbitrary repeats → binary jump;
metadata → fused;
path grouping → для лучшего scheduler behavior.
Итог
Если формулировать вывод максимально честно и точно, то он такой:
В этой работе я построил дискретный тетраэдрический вычислительный движок, в котором базовой единицей является не бит, а канонический геометрический мотив.
За счёт:
симметрийной канонизации,
предвычисления переходов,
иерархических jump-таблиц,
packed attractor metadata,
fused GPU-kernel,
и правильного выбора стратегии исполнения,
удалось получить измеренное exact-ускорение в 554.92x на одной и той же задаче F⁴⁰⁹⁶ на RTX 3090.
А также показать, что:
base64 jump лучше для точных степеней,
binary jump лучше для произвольной глубины,
разные пути формируют разные attractor-профили, а значит у такой системы уже появляется вычислительная семантика.
Главная мысль статьи очень простая: если считать не битами, а геометрическими состояниями, и заранее знать, как длинные цепочки преобразований схлопываются, то можно получить очень серьёзное ускорение на точных задачах.
Код программы:
Листинг кода
using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; using ComputeSharp; namespace TetraCombinationEngineV3 { internal static class Config { // ---------------------------------------------------- // Дискретная тетра-кодировка // ---------------------------------------------------- public const int SLOT_COUNT = 4; public const int OCCUPIED_COUNT = 3; public const int ORIENTATION_COUNT = 12; public const int PHASE_COUNT = 3; public const int LOCAL_STATE_COUNT = ORIENTATION_COUNT * PHASE_COUNT; // 36 public const int EMPTY = LOCAL_STATE_COUNT; // 36 public const int PACK_BASE = LOCAL_STATE_COUNT + 1; // 37 // ---------------------------------------------------- // Paths // ---------------------------------------------------- public const int PATH_LENGTH = 5; public static readonly int[][] PATHS = { new[] { 2,2,1,2,2 }, new[] { 0,1,2,3,0 }, new[] { 3,2,1,0,3 }, new[] { 1,1,1,1,1 }, new[] { 0,2,0,2,1 }, new[] { 3,3,0,1,2 }, new[] { 1,3,2,1,0 }, new[] { 2,0,3,1,2 } }; public static readonly string[] PATH_NAMES = { "2,2,1,2,2", "0,1,2,3,0", "3,2,1,0,3", "1,1,1,1,1", "0,2,0,2,1", "3,3,0,1,2", "1,3,2,1,0", "2,0,3,1,2" }; public static int PATH_COUNT => PATHS.Length; // ---------------------------------------------------- // Base-64 hierarchy // ---------------------------------------------------- // J0 = F^1 // J1 = F^64 // J2 = F^4096 // J3 = F^262144 // J4 = F^16777216 public const int BASE64_JUMP_BASE = 64; public const int BASE64_LEVELS = 5; // ---------------------------------------------------- // Binary hierarchy // ---------------------------------------------------- // B0 = F^1 // B1 = F^2 // ... // B24 = F^16777216 public const int BINARY_LEVELS = 25; // ---------------------------------------------------- // Packed attractor metadata // rep:14 bits [0..16383] // len:8 bits [0..255] // step:10 bits [0..1023] // total:32 bits // ---------------------------------------------------- public const int REP_BITS = 14; public const int LEN_BITS = 8; public const int STEP_BITS = 10; public const int REP_MASK = (1 << REP_BITS) - 1; public const int LEN_MASK = (1 << LEN_BITS) - 1; public const int STEP_MASK = (1 << STEP_BITS) - 1; public const int LEN_SHIFT = REP_BITS; public const int STEP_SHIFT = REP_BITS + LEN_BITS; // ---------------------------------------------------- // Benchmark // ---------------------------------------------------- public const int ELEMENTS = 4_000_000; public const int CORRECTNESS_TEST_SIZE = 100_000; public const int STANDARD_ITERATIONS = 80; public const int DIRECT_GPU_WORD_REPEATS = 64; public const int ARBITRARY_REPEAT_COUNT = 12_345_678; // exact deep target public const int EXACT_DEEP_REPEAT = 16_777_216; // ---------------------------------------------------- // Real 30-second task // exact semantic task:F^4096 // direct exact = 64 launches of F^64 // jump exact = one launch of J2 // ---------------------------------------------------- public const int REAL_TASK_REPEAT = 4_096; public const int REAL_TASK_BASE64_LEVEL = 2; // J2 = F^4096 public const int REAL_TASK_SECONDS = 30; } internal sealed class PathSummary { public required int PathId { get; init; } public required int CycleCount { get; init; } public required int MaxCycleLength { get; init; } public required float AverageSteps { get; init; } public required int DominantBasinSize { get; init; } public required int DominantCycleLength { get; init; } public required int DominantRepresentative { get; init; } } internal sealed class EngineBuildResult { public required int MotifCount { get; init; } public required int RawStateCount { get; init; } public required int SymmetryCount { get; init; } public required int[] CanonicalPackedByMotif { get; init; } public required int[] PathWords { get; init; } public required int[] GeneratorTransitions { get; init; } public required int[] Base64JumpTables { get; init; } // [((path * levels)+level)*motifCount + motif] public required long[] Base64LevelApplications { get; init; } public required int[] BinaryJumpTables { get; init; } // [((path * levels)+level)*motifCount + motif] public required long[] BinaryLevelApplications { get; init; } public required int[] PackedAttractorMetadata { get; init; } // [path * motifCount + motif] public required PathSummary[] PathSummaries { get; init; } } internal sealed class RealTaskResult { public required string Name { get; init; } public required int Elements { get; init; } public required int ExactRepeat { get; init; } public required double Seconds { get; init; } public required long BatchesCompleted { get; init; } public long TotalElementEvaluations => BatchesCompleted * (long)Elements; public long TotalPathApplications => BatchesCompleted * (long)Elements * ExactRepeat; public long TotalGeneratorApplications => TotalPathApplications * Config.PATH_LENGTH; public double BatchesPerSecond => BatchesCompleted / Seconds; public double PathApplicationsPerSecond => TotalPathApplications / Seconds; public double GeneratorApplicationsPerSecond => TotalGeneratorApplications / Seconds; } // ============================================================ // STANDARD GPU COMPUTE // ============================================================ [ThreadGroupSize(256, 1, 1)] [GeneratedComputeShaderDescriptor] public readonly partial struct StandardComputeKernel : IComputeShader { public readonly ReadWriteBuffer<float> Input; public readonly ReadWriteBuffer<float> Output; public readonly int Elements; public readonly int Iterations; public StandardComputeKernel( ReadWriteBuffer<float> input, ReadWriteBuffer<float> output, int elements, int iterations) { Input = input; Output = output; Elements = elements; Iterations = iterations; } public void Execute() { int i = ThreadIds.X; if (i >= Elements) return; float x = Input[i]; for (int iter = 0; iter < Iterations; iter++) { x = Hlsl.Sin(x * 1.13f) * Hlsl.Cos(x * 0.91f) + 0.31f * Hlsl.Exp(Hlsl.Abs(x) * 0.12f) + 0.27f * Hlsl.Log(1.0f + Hlsl.Abs(x) + 0.1f) + 0.19f * Hlsl.Sqrt(Hlsl.Abs(x) + 0.2f) - 0.08f * Hlsl.Tan(x * 0.15f); x = x * 0.87f + 0.013f; } Output[i] = x; } } // ============================================================ // DIRECT MULTI-PATH F^64 // ============================================================ [ThreadGroupSize(256, 1, 1)] [GeneratedComputeShaderDescriptor] public readonly partial struct DirectMultiPathKernel : IComputeShader { public readonly ReadWriteBuffer<int> InputMotifs; public readonly ReadWriteBuffer<int> InputPathIds; public readonly ReadWriteBuffer<int> OutputMotifs; public readonly ReadWriteBuffer<int> GeneratorTransitions; public readonly ReadWriteBuffer<int> PathWords; public readonly int Elements; public readonly int MotifCount; public readonly int PathLength; public readonly int WordRepeats; public DirectMultiPathKernel( ReadWriteBuffer<int> inputMotifs, ReadWriteBuffer<int> inputPathIds, ReadWriteBuffer<int> outputMotifs, ReadWriteBuffer<int> generatorTransitions, ReadWriteBuffer<int> pathWords, int elements, int motifCount, int pathLength, int wordRepeats) { InputMotifs = inputMotifs; InputPathIds = inputPathIds; OutputMotifs = outputMotifs; GeneratorTransitions = generatorTransitions; PathWords = pathWords; Elements = elements; MotifCount = motifCount; PathLength = pathLength; WordRepeats = wordRepeats; } public void Execute() { int i = ThreadIds.X; if (i >= Elements) return; int motif = InputMotifs[i]; int pathId = InputPathIds[i]; int pathOffset = pathId * PathLength; for (int r = 0; r < WordRepeats; r++) { for (int step = 0; step < PathLength; step++) { int g = PathWords[pathOffset + step]; motif = GeneratorTransitions[g * MotifCount + motif]; } } OutputMotifs[i] = motif; } } // ============================================================ // SINGLE-LEVEL JUMP LOOKUP // Works for both base64 and binary hierarchies // ============================================================ [ThreadGroupSize(256, 1, 1)] [GeneratedComputeShaderDescriptor] public readonly partial struct MultiPathJumpKernel : IComputeShader { public readonly ReadWriteBuffer<int> InputMotifs; public readonly ReadWriteBuffer<int> InputPathIds; public readonly ReadWriteBuffer<int> OutputMotifs; public readonly ReadWriteBuffer<int> JumpTables; public readonly int Elements; public readonly int MotifCount; public readonly int LevelCount; public readonly int Level; public MultiPathJumpKernel( ReadWriteBuffer<int> inputMotifs, ReadWriteBuffer<int> inputPathIds, ReadWriteBuffer<int> outputMotifs, ReadWriteBuffer<int> jumpTables, int elements, int motifCount, int levelCount, int level) { InputMotifs = inputMotifs; InputPathIds = inputPathIds; OutputMotifs = outputMotifs; JumpTables = jumpTables; Elements = elements; MotifCount = motifCount; LevelCount = levelCount; Level = level; } public void Execute() { int i = ThreadIds.X; if (i >= Elements) return; int motif = InputMotifs[i]; int pathId = InputPathIds[i]; int offset = ((pathId * LevelCount) + Level) * MotifCount; OutputMotifs[i] = JumpTables[offset + motif]; } } // ============================================================ // FUSED JUMP + PACKED ATTRACTOR LOOKUP // Works for both base64 and binary hierarchies // ============================================================ [ThreadGroupSize(256, 1, 1)] [GeneratedComputeShaderDescriptor] public readonly partial struct FusedJumpAttractorKernel : IComputeShader { public readonly ReadWriteBuffer<int> InputMotifs; public readonly ReadWriteBuffer<int> InputPathIds; public readonly ReadWriteBuffer<int> OutputMotifs; public readonly ReadWriteBuffer<int> OutputPackedMeta; public readonly ReadWriteBuffer<int> JumpTables; public readonly ReadWriteBuffer<int> PackedAttractorMetadata; public readonly int Elements; public readonly int MotifCount; public readonly int LevelCount; public readonly int Level; public FusedJumpAttractorKernel( ReadWriteBuffer<int> inputMotifs, ReadWriteBuffer<int> inputPathIds, ReadWriteBuffer<int> outputMotifs, ReadWriteBuffer<int> outputPackedMeta, ReadWriteBuffer<int> jumpTables, ReadWriteBuffer<int> packedAttractorMetadata, int elements, int motifCount, int levelCount, int level) { InputMotifs = inputMotifs; InputPathIds = inputPathIds; OutputMotifs = outputMotifs; OutputPackedMeta = outputPackedMeta; JumpTables = jumpTables; PackedAttractorMetadata = packedAttractorMetadata; Elements = elements; MotifCount = motifCount; LevelCount = levelCount; Level = level; } public void Execute() { int i = ThreadIds.X; if (i >= Elements) return; int motif = InputMotifs[i]; int pathId = InputPathIds[i]; int jumpOffset = ((pathId * LevelCount) + Level) * MotifCount; motif = JumpTables[jumpOffset + motif]; int metaOffset = pathId * MotifCount; int packed = PackedAttractorMetadata[metaOffset + motif]; OutputMotifs[i] = motif; OutputPackedMeta[i] = packed; } } // ============================================================ // BASE-64 ARBITRARY DECOMPOSITION // ============================================================ [ThreadGroupSize(256, 1, 1)] [GeneratedComputeShaderDescriptor] public readonly partial struct Base64DecomposedMultiPathKernel : IComputeShader { public readonly ReadWriteBuffer<int> InputMotifs; public readonly ReadWriteBuffer<int> InputPathIds; public readonly ReadWriteBuffer<int> OutputMotifs; public readonly ReadWriteBuffer<int> JumpTables; public readonly int Elements; public readonly int MotifCount; public readonly int LevelCount; public readonly int RepeatCount; public readonly int JumpBase; public Base64DecomposedMultiPathKernel( ReadWriteBuffer<int> inputMotifs, ReadWriteBuffer<int> inputPathIds, ReadWriteBuffer<int> outputMotifs, ReadWriteBuffer<int> jumpTables, int elements, int motifCount, int levelCount, int repeatCount, int jumpBase) { InputMotifs = inputMotifs; InputPathIds = inputPathIds; OutputMotifs = outputMotifs; JumpTables = jumpTables; Elements = elements; MotifCount = motifCount; LevelCount = levelCount; RepeatCount = repeatCount; JumpBase = jumpBase; } public void Execute() { int i = ThreadIds.X; if (i >= Elements) return; int motif = InputMotifs[i]; int pathId = InputPathIds[i]; int baseOffset = pathId * LevelCount * MotifCount; int remaining = RepeatCount; int d0 = remaining % JumpBase; remaining /= JumpBase; int d1 = remaining % JumpBase; remaining /= JumpBase; int d2 = remaining % JumpBase; remaining /= JumpBase; int d3 = remaining % JumpBase; remaining /= JumpBase; int d4 = remaining % JumpBase; int o0 = baseOffset + 0 * MotifCount; int o1 = baseOffset + 1 * MotifCount; int o2 = baseOffset + 2 * MotifCount; int o3 = baseOffset + 3 * MotifCount; int o4 = baseOffset + 4 * MotifCount; for (int k = 0; k < d0; k++) motif = JumpTables[o0 + motif]; for (int k = 0; k < d1; k++) motif = JumpTables[o1 + motif]; for (int k = 0; k < d2; k++) motif = JumpTables[o2 + motif]; for (int k = 0; k < d3; k++) motif = JumpTables[o3 + motif]; for (int k = 0; k < d4; k++) motif = JumpTables[o4 + motif]; OutputMotifs[i] = motif; } } // ============================================================ // BINARY ARBITRARY DECOMPOSITION // ============================================================ [ThreadGroupSize(256, 1, 1)] [GeneratedComputeShaderDescriptor] public readonly partial struct BinaryDecomposedMultiPathKernel : IComputeShader { public readonly ReadWriteBuffer<int> InputMotifs; public readonly ReadWriteBuffer<int> InputPathIds; public readonly ReadWriteBuffer<int> OutputMotifs; public readonly ReadWriteBuffer<int> JumpTables; public readonly int Elements; public readonly int MotifCount; public readonly int LevelCount; public readonly uint RepeatCount; public BinaryDecomposedMultiPathKernel( ReadWriteBuffer<int> inputMotifs, ReadWriteBuffer<int> inputPathIds, ReadWriteBuffer<int> outputMotifs, ReadWriteBuffer<int> jumpTables, int elements, int motifCount, int levelCount, uint repeatCount) { InputMotifs = inputMotifs; InputPathIds = inputPathIds; OutputMotifs = outputMotifs; JumpTables = jumpTables; Elements = elements; MotifCount = motifCount; LevelCount = levelCount; RepeatCount = repeatCount; } public void Execute() { int i = ThreadIds.X; if (i >= Elements) return; int motif = InputMotifs[i]; int pathId = InputPathIds[i]; int baseOffset = pathId * LevelCount * MotifCount; uint mask = RepeatCount; for (int level = 0; level < LevelCount; level++) { if ((mask & (1u << level)) != 0u) { motif = JumpTables[baseOffset + level * MotifCount + motif]; } } OutputMotifs[i] = motif; } } // ============================================================ // FENCE // ============================================================ [ThreadGroupSize(1, 1, 1)] [GeneratedComputeShaderDescriptor] public readonly partial struct FenceKernel : IComputeShader { public readonly ReadWriteBuffer<int> Fence; public FenceKernel(ReadWriteBuffer<int> fence) => Fence = fence; public void Execute() => Fence[0] = Fence[0] + 1; } internal static class Program { static void Main() { Console.OutputEncoding = Encoding.UTF8; Console.WriteLine("================================================"); Console.WriteLine("TETRA COMBINATION ENGINE - V3 BINARY + REAL 30s"); Console.WriteLine("================================================"); Console.WriteLine(); var device = GraphicsDevice.GetDefault(); Console.WriteLine($"GPU:{device.Name}"); Console.WriteLine($"Elements:{Config.ELEMENTS:N0}"); Console.WriteLine($"Path count:{Config.PATH_COUNT}"); Console.WriteLine($"Path length:{Config.PATH_LENGTH}"); Console.WriteLine($"Base64 levels:{Config.BASE64_LEVELS}"); Console.WriteLine($"Binary levels:{Config.BINARY_LEVELS}"); Console.WriteLine(); Console.WriteLine("Building engine on CPU..."); var swBuild = Stopwatch.StartNew(); EngineBuildResult engine = BuildEngine(); swBuild.Stop(); Console.WriteLine($"Build time:{swBuild.Elapsed.TotalMilliseconds:F2} ms"); Console.WriteLine($"Raw states:{engine.RawStateCount:N0}"); Console.WriteLine($"Canonical motifs:{engine.MotifCount:N0}"); Console.WriteLine($"Symmetry count:{engine.SymmetryCount}"); Console.WriteLine($"Generator table:{engine.GeneratorTransitions.Length:N0} ints (~{engine.GeneratorTransitions.Length * sizeof(int) / 1024.0 / 1024.0:F2} MB)"); Console.WriteLine($"Path word table:{engine.PathWords.Length:N0} ints"); Console.WriteLine($"Base64 jump tables:{engine.Base64JumpTables.Length:N0} ints (~{engine.Base64JumpTables.Length * sizeof(int) / 1024.0 / 1024.0:F2} MB)"); Console.WriteLine($"Binary jump tables:{engine.BinaryJumpTables.Length:N0} ints (~{engine.BinaryJumpTables.Length * sizeof(int) / 1024.0 / 1024.0:F2} MB)"); Console.WriteLine($"Packed attractor metadata:{engine.PackedAttractorMetadata.Length:N0} ints (~{engine.PackedAttractorMetadata.Length * sizeof(int) / 1024.0 / 1024.0:F2} MB)"); Console.WriteLine(); PrintBase64LevelStats(engine); Console.WriteLine(); PrintBinaryLevelStats(engine); Console.WriteLine(); PrintPathSummaries(engine); Console.WriteLine("\nTesting standard GPU compute..."); var standardTime = TestStandardCompute(device); Console.WriteLine($"Standard time:{standardTime.TotalMilliseconds:F2} ms"); Console.WriteLine($"\nTesting direct multi-path F^{Config.DIRECT_GPU_WORD_REPEATS:N0} (random pathId)..."); var directRandomTime = TestDirectMultiPath(device, engine, groupedPaths: false); Console.WriteLine($"Direct random time:{directRandomTime.TotalMilliseconds:F2} ms"); Console.WriteLine($"\nTesting direct multi-path F^{Config.DIRECT_GPU_WORD_REPEATS:N0} (grouped pathId)..."); var directGroupedTime = TestDirectMultiPath(device, engine, groupedPaths: true); Console.WriteLine($"Direct grouped time:{directGroupedTime.TotalMilliseconds:F2} ms"); Console.WriteLine("\nTesting base64 jump J1 = F^64 (random pathId)..."); var jump64RandomTime = TestSingleJump(device, engine, engine.Base64JumpTables, Config.BASE64_LEVELS, level: 1, groupedPaths: false); Console.WriteLine($"Jump J1 random time:{jump64RandomTime.TotalMilliseconds:F2} ms"); Console.WriteLine("\nTesting base64 fused J1 = F^64 + attractor (random pathId)..."); var fused64RandomTime = TestFusedSingleJump(device, engine, engine.Base64JumpTables, Config.BASE64_LEVELS, level: 1, groupedPaths: false); Console.WriteLine($"Fused J1 random time:{fused64RandomTime.TotalMilliseconds:F2} ms"); Console.WriteLine("\nTesting base64 fused J1 = F^64 + attractor (grouped pathId)..."); var fused64GroupedTime = TestFusedSingleJump(device, engine, engine.Base64JumpTables, Config.BASE64_LEVELS, level: 1, groupedPaths: true); Console.WriteLine($"Fused J1 grouped time:{fused64GroupedTime.TotalMilliseconds:F2} ms"); Console.WriteLine($"\nTesting base64 arbitrary F^{Config.ARBITRARY_REPEAT_COUNT:N0}..."); var base64ArbitraryTime = TestBase64Arbitrary(device, engine, Config.ARBITRARY_REPEAT_COUNT, groupedPaths: false); Console.WriteLine($"Base64 arbitrary time:{base64ArbitraryTime.TotalMilliseconds:F2} ms"); Console.WriteLine($"\nTesting binary arbitrary F^{Config.ARBITRARY_REPEAT_COUNT:N0}..."); var binaryArbitraryTime = TestBinaryArbitrary(device, engine, Config.ARBITRARY_REPEAT_COUNT, groupedPaths: false); Console.WriteLine($"Binary arbitrary time:{binaryArbitraryTime.TotalMilliseconds:F2} ms"); int exactBase64Level = TryGetExactLevel(Config.EXACT_DEEP_REPEAT, engine.Base64LevelApplications); int exactBinaryLevel = TryGetExactLevel(Config.EXACT_DEEP_REPEAT, engine.BinaryLevelApplications); Console.WriteLine($"\nTesting exact deep base64 jump F^{Config.EXACT_DEEP_REPEAT:N0}..."); var base64ExactTime = TestFusedSingleJump(device, engine, engine.Base64JumpTables, Config.BASE64_LEVELS, exactBase64Level, groupedPaths: false); Console.WriteLine($"Base64 exact deep time:{base64ExactTime.TotalMilliseconds:F2} ms"); Console.WriteLine($"\nTesting exact deep binary jump F^{Config.EXACT_DEEP_REPEAT:N0}..."); var binaryExactTime = TestFusedSingleJump(device, engine, engine.BinaryJumpTables, Config.BINARY_LEVELS, exactBinaryLevel, groupedPaths: false); Console.WriteLine($"Binary exact deep time:{binaryExactTime.TotalMilliseconds:F2} ms"); Console.WriteLine("\n================================================"); Console.WriteLine("PERFORMANCE COMPARISON"); Console.WriteLine("================================================"); double standardMs = standardTime.TotalMilliseconds; double directRandomMs = directRandomTime.TotalMilliseconds; double directGroupedMs = directGroupedTime.TotalMilliseconds; double jump64RandomMs = jump64RandomTime.TotalMilliseconds; double fused64RandomMs = fused64RandomTime.TotalMilliseconds; double fused64GroupedMs = fused64GroupedTime.TotalMilliseconds; double base64ArbMs = base64ArbitraryTime.TotalMilliseconds; double binaryArbMs = binaryArbitraryTime.TotalMilliseconds; double base64ExactMs = base64ExactTime.TotalMilliseconds; double binaryExactMs = binaryExactTime.TotalMilliseconds; Console.WriteLine($"Standard compute:{standardMs:F2} ms (baseline)"); Console.WriteLine($"Direct F^64 random:{directRandomMs:F2} ms ({standardMs / directRandomMs:F2}x vs baseline)"); Console.WriteLine($"Direct F^64 grouped:{directGroupedMs:F2} ms ({standardMs / directGroupedMs:F2}x vs baseline,{directRandomMs / directGroupedMs:F2}x vs direct-random)"); Console.WriteLine($"Jump J1 random:{jump64RandomMs:F2} ms ({standardMs / jump64RandomMs:F2}x vs baseline,{directRandomMs / jump64RandomMs:F2}x vs direct-random)"); Console.WriteLine($"Fused J1 random:{fused64RandomMs:F2} ms ({standardMs / fused64RandomMs:F2}x vs baseline,{directRandomMs / fused64RandomMs:F2}x vs direct-random)"); Console.WriteLine($"Fused J1 grouped:{fused64GroupedMs:F2} ms ({standardMs / fused64GroupedMs:F2}x vs baseline,{fused64RandomMs / fused64GroupedMs:F2}x vs fused-random)"); Console.WriteLine($"Base64 arbitrary:{base64ArbMs:F2} ms"); Console.WriteLine($"Binary arbitrary:{binaryArbMs:F2} ms ({base64ArbMs / binaryArbMs:F2}x vs base64-arbitrary)"); Console.WriteLine($"Base64 exact deep:{base64ExactMs:F2} ms"); Console.WriteLine($"Binary exact deep:{binaryExactMs:F2} ms"); Console.WriteLine("\n================================================"); Console.WriteLine("LOGICAL COMPRESSION"); Console.WriteLine("================================================"); double equivalentVsDirect64 = (double)Config.EXACT_DEEP_REPEAT / Config.DIRECT_GPU_WORD_REPEATS; double estimatedDirectDeepMs = directRandomMs * equivalentVsDirect64; Console.WriteLine($"Exact deep target:F^{Config.EXACT_DEEP_REPEAT:N0}"); Console.WriteLine($"Equivalent path applications vs direct F^64:{equivalentVsDirect64:N0}x"); Console.WriteLine($"Equivalent generator applications per element:{(long)Config.EXACT_DEEP_REPEAT * Config.PATH_LENGTH:N0}"); Console.WriteLine($"Estimated direct time for same depth (linear extrapolation):{estimatedDirectDeepMs / 1000.0:F2} s"); Console.WriteLine($"Estimated speedup of binary exact deep vs extrapolated direct:{estimatedDirectDeepMs / binaryExactMs:F2}x"); Console.WriteLine("\n================================================"); Console.WriteLine("REAL 30-SECOND EXACT TASK"); Console.WriteLine("================================================"); Console.WriteLine($"Exact semantic task:F^{Config.REAL_TASK_REPEAT:N0}"); Console.WriteLine("Direct exact implementation:64 sequential launches of F^64"); Console.WriteLine("Jump exact implementation:one J2 = F^4096 lookup"); Console.WriteLine($"Duration per mode:{Config.REAL_TASK_SECONDS} seconds"); Console.WriteLine(); var realDirect = RunRealThirtySecondDirectExactTask(device, engine, groupedPaths: false); var realJump = RunRealThirtySecondJumpExactTask(device, engine, groupedPaths: false); PrintRealTaskResult(realDirect); PrintRealTaskResult(realJump); Console.WriteLine(); Console.WriteLine($"Measured exact throughput speedup (path applications/sec):{realJump.PathApplicationsPerSecond / realDirect.PathApplicationsPerSecond:F2}x"); Console.WriteLine($"Measured exact throughput speedup (generator applications/sec):{realJump.GeneratorApplicationsPerSecond / realDirect.GeneratorApplicationsPerSecond:F2}x"); Console.WriteLine($"Measured exact batch speedup:{realJump.BatchesPerSecond / realDirect.BatchesPerSecond:F2}x"); Console.WriteLine("\n================================================"); Console.WriteLine("CORRECTNESS CHECK"); Console.WriteLine("================================================"); CheckCorrectness(device, engine); Console.WriteLine("\nDone. Press any key..."); Console.ReadKey(); } // ============================================================ // BUILD ENGINE // ============================================================ static EngineBuildResult BuildEngine() { var symmetryGroup = BuildA4SymmetryGroup(); var canonicalToId = new Dictionary<int, int>(capacity: 32768); var motifPackedList = new List<int>(capacity: 32768); int rawCount = 0; for (int missing = 0; missing < 4; missing++) { for (int a = 0; a < Config.LOCAL_STATE_COUNT; a++) { for (int b = 0; b < Config.LOCAL_STATE_COUNT; b++) { for (int c = 0; c < Config.LOCAL_STATE_COUNT; c++) { rawCount++; int[] slots = new int[4]; for (int i = 0; i < 4; i++) slots[i] = Config.EMPTY; int idx = 0; for (int s = 0; s < 4; s++) { if (s == missing) continue; slots[s] = idx switch { 0 => a, 1 => b, _ => c }; idx++; } int packed = PackSlots(slots[0], slots[1], slots[2], slots[3]); int canonical = Canonicalize(packed, symmetryGroup); if (!canonicalToId.ContainsKey(canonical)) { canonicalToId[canonical] = motifPackedList.Count; motifPackedList.Add(canonical); } } } } } int motifCount = motifPackedList.Count; int[] pathWords = new int[Config.PATH_COUNT * Config.PATH_LENGTH]; for (int p = 0; p < Config.PATH_COUNT; p++) { for (int k = 0; k < Config.PATH_LENGTH; k++) { pathWords[p * Config.PATH_LENGTH + k] = Config.PATHS[p][k]; } } int[] generatorTransitions = new int[4 * motifCount]; for (int motif = 0; motif < motifCount; motif++) { int packed = motifPackedList[motif]; for (int g = 0; g < 4; g++) { int nextRaw = ApplyGenerator(packed, g); int nextCanonical = Canonicalize(nextRaw, symmetryGroup); int nextMotif = canonicalToId[nextCanonical]; generatorTransitions[g * motifCount + motif] = nextMotif; } } // ------------------------- // Base64 jump tables // ------------------------- int[] base64JumpTables = new int[Config.PATH_COUNT * Config.BASE64_LEVELS * motifCount]; long[] base64LevelApps = new long[Config.BASE64_LEVELS]; base64LevelApps[0] = 1; for (int level = 1; level < Config.BASE64_LEVELS; level++) base64LevelApps[level] = base64LevelApps[level - 1] * Config.BASE64_JUMP_BASE; for (int pathId = 0; pathId < Config.PATH_COUNT; pathId++) { int offset0 = GetTableOffset(pathId, 0, motifCount, Config.BASE64_LEVELS); for (int motif = 0; motif < motifCount; motif++) { int current = motif; for (int step = 0; step < Config.PATH_LENGTH; step++) { int g = pathWords[pathId * Config.PATH_LENGTH + step]; current = generatorTransitions[g * motifCount + current]; } base64JumpTables[offset0 + motif] = current; } } for (int pathId = 0; pathId < Config.PATH_COUNT; pathId++) { for (int level = 1; level < Config.BASE64_LEVELS; level++) { int prevOffset = GetTableOffset(pathId, level - 1, motifCount, Config.BASE64_LEVELS); int curOffset = GetTableOffset(pathId, level, motifCount, Config.BASE64_LEVELS); for (int motif = 0; motif < motifCount; motif++) { int current = motif; for (int r = 0; r < Config.BASE64_JUMP_BASE; r++) { current = base64JumpTables[prevOffset + current]; } base64JumpTables[curOffset + motif] = current; } } } // ------------------------- // Binary jump tables // ------------------------- int[] binaryJumpTables = new int[Config.PATH_COUNT * Config.BINARY_LEVELS * motifCount]; long[] binaryLevelApps = new long[Config.BINARY_LEVELS]; binaryLevelApps[0] = 1; for (int level = 1; level < Config.BINARY_LEVELS; level++) binaryLevelApps[level] = binaryLevelApps[level - 1] * 2; for (int pathId = 0; pathId < Config.PATH_COUNT; pathId++) { int base64Offset0 = GetTableOffset(pathId, 0, motifCount, Config.BASE64_LEVELS); int binaryOffset0 = GetTableOffset(pathId, 0, motifCount, Config.BINARY_LEVELS); Array.Copy(base64JumpTables, base64Offset0, binaryJumpTables, binaryOffset0, motifCount); } for (int pathId = 0; pathId < Config.PATH_COUNT; pathId++) { for (int level = 1; level < Config.BINARY_LEVELS; level++) { int prevOffset = GetTableOffset(pathId, level - 1, motifCount, Config.BINARY_LEVELS); int curOffset = GetTableOffset(pathId, level, motifCount, Config.BINARY_LEVELS); for (int motif = 0; motif < motifCount; motif++) { int current = binaryJumpTables[prevOffset + motif]; current = binaryJumpTables[prevOffset + current]; binaryJumpTables[curOffset + motif] = current; } } } // ------------------------- // Attractor metadata from F^1 // ------------------------- int[] packedAttractorMetadata = new int[Config.PATH_COUNT * motifCount]; PathSummary[] pathSummaries = new PathSummary[Config.PATH_COUNT]; for (int pathId = 0; pathId < Config.PATH_COUNT; pathId++) { int offset0 = GetTableOffset(pathId, 0, motifCount, Config.BASE64_LEVELS); int[] next = new int[motifCount]; Array.Copy(base64JumpTables, offset0, next, 0, motifCount); AnalyzeFunctionalGraph( next, out int[] cycleId, out int[] cycleRepresentative, out int[] cycleLength, out int[] stepsToCycle); int maxRep = cycleRepresentative.Max(); int maxLen = cycleLength.Max(); int maxSteps = stepsToCycle.Max(); if (maxRep > Config.REP_MASK) throw new InvalidOperationException($"Representative {maxRep} exceeds packed REP range."); if (maxLen > Config.LEN_MASK) throw new InvalidOperationException($"Cycle length {maxLen} exceeds packed LEN range."); if (maxSteps > Config.STEP_MASK) throw new InvalidOperationException($"Steps-to-cycle {maxSteps} exceeds packed STEP range."); int metaOffset = pathId * motifCount; for (int motif = 0; motif < motifCount; motif++) { packedAttractorMetadata[metaOffset + motif] = PackMeta(cycleRepresentative[motif], cycleLength[motif], stepsToCycle[motif]); } int cycleCount = cycleId.Distinct().Count(); int maxCycleLength = cycleLength.Max(); float averageSteps = (float)stepsToCycle.Average(); var dominant = cycleId .GroupBy(x => x) .Select(g => { int firstIndex = Array.IndexOf(cycleId, g.Key); return new { BasinSize = g.Count(), CycleLength = cycleLength[firstIndex], Representative = cycleRepresentative[firstIndex] }; }) .OrderByDescending(x => x.BasinSize) .First(); pathSummaries[pathId] = new PathSummary { PathId = pathId, CycleCount = cycleCount, MaxCycleLength = maxCycleLength, AverageSteps = averageSteps, DominantBasinSize = dominant.BasinSize, DominantCycleLength = dominant.CycleLength, DominantRepresentative = dominant.Representative }; } return new EngineBuildResult { MotifCount = motifCount, RawStateCount = rawCount, SymmetryCount = symmetryGroup.Count, CanonicalPackedByMotif = motifPackedList.ToArray(), PathWords = pathWords, GeneratorTransitions = generatorTransitions, Base64JumpTables = base64JumpTables, Base64LevelApplications = base64LevelApps, BinaryJumpTables = binaryJumpTables, BinaryLevelApplications = binaryLevelApps, PackedAttractorMetadata = packedAttractorMetadata, PathSummaries = pathSummaries }; } // ============================================================ // BENCHMARKS // ============================================================ static TimeSpan TestStandardCompute(GraphicsDevice device) { int size = Config.ELEMENTS; using var input = device.AllocateReadWriteBuffer<float>(size); using var output = device.AllocateReadWriteBuffer<float>(size); FillRandomFloatData(device, input, size, 12345); device.For(size, new StandardComputeKernel(input, output, size, 8)); Synchronize(device); var sw = Stopwatch.StartNew(); device.For(size, new StandardComputeKernel(input, output, size, Config.STANDARD_ITERATIONS)); Synchronize(device); sw.Stop(); return sw.Elapsed; } static TimeSpan TestDirectMultiPath(GraphicsDevice device, EngineBuildResult engine, bool groupedPaths) { int size = Config.ELEMENTS; using var inputMotifs = device.AllocateReadWriteBuffer<int>(size); using var inputPathIds = device.AllocateReadWriteBuffer<int>(size); using var outputMotifs = device.AllocateReadWriteBuffer<int>(size); using var transitions = device.AllocateReadWriteBuffer<int>(engine.GeneratorTransitions.Length); using var pathWords = device.AllocateReadWriteBuffer<int>(engine.PathWords.Length); transitions.CopyFrom(engine.GeneratorTransitions); pathWords.CopyFrom(engine.PathWords); FillRandomMotifIds(device, inputMotifs, size, engine.MotifCount, 12345); if (groupedPaths) FillGroupedPathIds(device, inputPathIds, size, Config.PATH_COUNT); else FillRandomPathIds(device, inputPathIds, size, Config.PATH_COUNT, 54321); device.For(size, new DirectMultiPathKernel( inputMotifs, inputPathIds, outputMotifs, transitions, pathWords, size, engine.MotifCount, Config.PATH_LENGTH, Config.DIRECT_GPU_WORD_REPEATS)); Synchronize(device); var sw = Stopwatch.StartNew(); device.For(size, new DirectMultiPathKernel( inputMotifs, inputPathIds, outputMotifs, transitions, pathWords, size, engine.MotifCount, Config.PATH_LENGTH, Config.DIRECT_GPU_WORD_REPEATS)); Synchronize(device); sw.Stop(); return sw.Elapsed; } static TimeSpan TestSingleJump( GraphicsDevice device, EngineBuildResult engine, int[] jumpTables, int levelCount, int level, bool groupedPaths) { int size = Config.ELEMENTS; using var inputMotifs = device.AllocateReadWriteBuffer<int>(size); using var inputPathIds = device.AllocateReadWriteBuffer<int>(size); using var outputMotifs = device.AllocateReadWriteBuffer<int>(size); using var jumps = device.AllocateReadWriteBuffer<int>(jumpTables.Length); jumps.CopyFrom(jumpTables); FillRandomMotifIds(device, inputMotifs, size, engine.MotifCount, 12345); if (groupedPaths) FillGroupedPathIds(device, inputPathIds, size, Config.PATH_COUNT); else FillRandomPathIds(device, inputPathIds, size, Config.PATH_COUNT, 54321); device.For(size, new MultiPathJumpKernel( inputMotifs, inputPathIds, outputMotifs, jumps, size, engine.MotifCount, levelCount, level)); Synchronize(device); var sw = Stopwatch.StartNew(); device.For(size, new MultiPathJumpKernel( inputMotifs, inputPathIds, outputMotifs, jumps, size, engine.MotifCount, levelCount, level)); Synchronize(device); sw.Stop(); return sw.Elapsed; } static TimeSpan TestFusedSingleJump( GraphicsDevice device, EngineBuildResult engine, int[] jumpTables, int levelCount, int level, bool groupedPaths) { int size = Config.ELEMENTS; using var inputMotifs = device.AllocateReadWriteBuffer<int>(size); using var inputPathIds = device.AllocateReadWriteBuffer<int>(size); using var outputMotifs = device.AllocateReadWriteBuffer<int>(size); using var outputMeta = device.AllocateReadWriteBuffer<int>(size); using var jumps = device.AllocateReadWriteBuffer<int>(jumpTables.Length); using var meta = device.AllocateReadWriteBuffer<int>(engine.PackedAttractorMetadata.Length); jumps.CopyFrom(jumpTables); meta.CopyFrom(engine.PackedAttractorMetadata); FillRandomMotifIds(device, inputMotifs, size, engine.MotifCount, 12345); if (groupedPaths) FillGroupedPathIds(device, inputPathIds, size, Config.PATH_COUNT); else FillRandomPathIds(device, inputPathIds, size, Config.PATH_COUNT, 54321); device.For(size, new FusedJumpAttractorKernel( inputMotifs, inputPathIds, outputMotifs, outputMeta, jumps, meta, size, engine.MotifCount, levelCount, level)); Synchronize(device); var sw = Stopwatch.StartNew(); device.For(size, new FusedJumpAttractorKernel( inputMotifs, inputPathIds, outputMotifs, outputMeta, jumps, meta, size, engine.MotifCount, levelCount, level)); Synchronize(device); sw.Stop(); return sw.Elapsed; } static TimeSpan TestBase64Arbitrary(GraphicsDevice device, EngineBuildResult engine, int repeatCount, bool groupedPaths) { int size = Config.ELEMENTS; using var inputMotifs = device.AllocateReadWriteBuffer<int>(size); using var inputPathIds = device.AllocateReadWriteBuffer<int>(size); using var outputMotifs = device.AllocateReadWriteBuffer<int>(size); using var jumps = device.AllocateReadWriteBuffer<int>(engine.Base64JumpTables.Length); jumps.CopyFrom(engine.Base64JumpTables); FillRandomMotifIds(device, inputMotifs, size, engine.MotifCount, 12345); if (groupedPaths) FillGroupedPathIds(device, inputPathIds, size, Config.PATH_COUNT); else FillRandomPathIds(device, inputPathIds, size, Config.PATH_COUNT, 54321); device.For(size, new Base64DecomposedMultiPathKernel( inputMotifs, inputPathIds, outputMotifs, jumps, size, engine.MotifCount, Config.BASE64_LEVELS, repeatCount, Config.BASE64_JUMP_BASE)); Synchronize(device); var sw = Stopwatch.StartNew(); device.For(size, new Base64DecomposedMultiPathKernel( inputMotifs, inputPathIds, outputMotifs, jumps, size, engine.MotifCount, Config.BASE64_LEVELS, repeatCount, Config.BASE64_JUMP_BASE)); Synchronize(device); sw.Stop(); return sw.Elapsed; } static TimeSpan TestBinaryArbitrary(GraphicsDevice device, EngineBuildResult engine, int repeatCount, bool groupedPaths) { int size = Config.ELEMENTS; using var inputMotifs = device.AllocateReadWriteBuffer<int>(size); using var inputPathIds = device.AllocateReadWriteBuffer<int>(size); using var outputMotifs = device.AllocateReadWriteBuffer<int>(size); using var jumps = device.AllocateReadWriteBuffer<int>(engine.BinaryJumpTables.Length); jumps.CopyFrom(engine.BinaryJumpTables); FillRandomMotifIds(device, inputMotifs, size, engine.MotifCount, 12345); if (groupedPaths) FillGroupedPathIds(device, inputPathIds, size, Config.PATH_COUNT); else FillRandomPathIds(device, inputPathIds, size, Config.PATH_COUNT, 54321); device.For(size, new BinaryDecomposedMultiPathKernel( inputMotifs, inputPathIds, outputMotifs, jumps, size, engine.MotifCount, Config.BINARY_LEVELS, (uint)repeatCount)); Synchronize(device); var sw = Stopwatch.StartNew(); device.For(size, new BinaryDecomposedMultiPathKernel( inputMotifs, inputPathIds, outputMotifs, jumps, size, engine.MotifCount, Config.BINARY_LEVELS, (uint)repeatCount)); Synchronize(device); sw.Stop(); return sw.Elapsed; } // ============================================================ // REAL 30-SECOND EXACT TASK // ============================================================ static RealTaskResult RunRealThirtySecondDirectExactTask(GraphicsDevice device, EngineBuildResult engine, bool groupedPaths) { int size = Config.ELEMENTS; using var motifsA = device.AllocateReadWriteBuffer<int>(size); using var motifsB = device.AllocateReadWriteBuffer<int>(size); using var pathIds = device.AllocateReadWriteBuffer<int>(size); using var transitions = device.AllocateReadWriteBuffer<int>(engine.GeneratorTransitions.Length); using var pathWords = device.AllocateReadWriteBuffer<int>(engine.PathWords.Length); transitions.CopyFrom(engine.GeneratorTransitions); pathWords.CopyFrom(engine.PathWords); FillRandomMotifIds(device, motifsA, size, engine.MotifCount, 10101); if (groupedPaths) FillGroupedPathIds(device, pathIds, size, Config.PATH_COUNT); else FillRandomPathIds(device, pathIds, size, Config.PATH_COUNT, 20202); // warmup device.For(size, new DirectMultiPathKernel( motifsA, pathIds, motifsB, transitions, pathWords, size, engine.MotifCount, Config.PATH_LENGTH, Config.DIRECT_GPU_WORD_REPEATS)); Synchronize(device); bool aToB = true; long batches = 0; var sw = Stopwatch.StartNew(); while (sw.Elapsed.TotalSeconds < Config.REAL_TASK_SECONDS) { // exact F^4096 = 64 dispatches of F^64 for (int i = 0; i < 64; i++) { if (aToB) { device.For(size, new DirectMultiPathKernel( motifsA, pathIds, motifsB, transitions, pathWords, size, engine.MotifCount, Config.PATH_LENGTH, Config.DIRECT_GPU_WORD_REPEATS)); } else { device.For(size, new DirectMultiPathKernel( motifsB, pathIds, motifsA, transitions, pathWords, size, engine.MotifCount, Config.PATH_LENGTH, Config.DIRECT_GPU_WORD_REPEATS)); } aToB = !aToB; } Synchronize(device); batches++; } sw.Stop(); return new RealTaskResult { Name = "DIRECT EXACT F^4096", Elements = size, ExactRepeat = Config.REAL_TASK_REPEAT, Seconds = sw.Elapsed.TotalSeconds, BatchesCompleted = batches }; } static RealTaskResult RunRealThirtySecondJumpExactTask(GraphicsDevice device, EngineBuildResult engine, bool groupedPaths) { int size = Config.ELEMENTS; using var motifsA = device.AllocateReadWriteBuffer<int>(size); using var motifsB = device.AllocateReadWriteBuffer<int>(size); using var pathIds = device.AllocateReadWriteBuffer<int>(size); using var metaOut = device.AllocateReadWriteBuffer<int>(size); using var jumps = device.AllocateReadWriteBuffer<int>(engine.Base64JumpTables.Length); using var meta = device.AllocateReadWriteBuffer<int>(engine.PackedAttractorMetadata.Length); jumps.CopyFrom(engine.Base64JumpTables); meta.CopyFrom(engine.PackedAttractorMetadata); FillRandomMotifIds(device, motifsA, size, engine.MotifCount, 10101); if (groupedPaths) FillGroupedPathIds(device, pathIds, size, Config.PATH_COUNT); else FillRandomPathIds(device, pathIds, size, Config.PATH_COUNT, 20202); // warmup device.For(size, new FusedJumpAttractorKernel( motifsA, pathIds, motifsB, metaOut, jumps, meta, size, engine.MotifCount, Config.BASE64_LEVELS, Config.REAL_TASK_BASE64_LEVEL)); Synchronize(device); bool aToB = true; long batches = 0; var sw = Stopwatch.StartNew(); while (sw.Elapsed.TotalSeconds < Config.REAL_TASK_SECONDS) { if (aToB) { device.For(size, new FusedJumpAttractorKernel( motifsA, pathIds, motifsB, metaOut, jumps, meta, size, engine.MotifCount, Config.BASE64_LEVELS, Config.REAL_TASK_BASE64_LEVEL)); } else { device.For(size, new FusedJumpAttractorKernel( motifsB, pathIds, motifsA, metaOut, jumps, meta, size, engine.MotifCount, Config.BASE64_LEVELS, Config.REAL_TASK_BASE64_LEVEL)); } aToB = !aToB; Synchronize(device); batches++; } sw.Stop(); return new RealTaskResult { Name = "JUMP EXACT F^4096", Elements = size, ExactRepeat = Config.REAL_TASK_REPEAT, Seconds = sw.Elapsed.TotalSeconds, BatchesCompleted = batches }; } // ============================================================ // CORRECTNESS // ============================================================ static void CheckCorrectness(GraphicsDevice device, EngineBuildResult engine) { int size = Config.CORRECTNESS_TEST_SIZE; using var inputMotifs = device.AllocateReadWriteBuffer<int>(size); using var inputPathIds = device.AllocateReadWriteBuffer<int>(size); using var directOut = device.AllocateReadWriteBuffer<int>(size); using var jump64Out = device.AllocateReadWriteBuffer<int>(size); using var fused64Out = device.AllocateReadWriteBuffer<int>(size); using var fused64Meta = device.AllocateReadWriteBuffer<int>(size); using var base64ArbOut = device.AllocateReadWriteBuffer<int>(size); using var binaryArbOut = device.AllocateReadWriteBuffer<int>(size); using var transitions = device.AllocateReadWriteBuffer<int>(engine.GeneratorTransitions.Length); using var pathWords = device.AllocateReadWriteBuffer<int>(engine.PathWords.Length); using var base64Jumps = device.AllocateReadWriteBuffer<int>(engine.Base64JumpTables.Length); using var binaryJumps = device.AllocateReadWriteBuffer<int>(engine.BinaryJumpTables.Length); using var meta = device.AllocateReadWriteBuffer<int>(engine.PackedAttractorMetadata.Length); transitions.CopyFrom(engine.GeneratorTransitions); pathWords.CopyFrom(engine.PathWords); base64Jumps.CopyFrom(engine.Base64JumpTables); binaryJumps.CopyFrom(engine.BinaryJumpTables); meta.CopyFrom(engine.PackedAttractorMetadata); FillRandomMotifIds(device, inputMotifs, size, engine.MotifCount, 777); FillRandomPathIds(device, inputPathIds, size, Config.PATH_COUNT, 888); device.For(size, new DirectMultiPathKernel( inputMotifs, inputPathIds, directOut, transitions, pathWords, size, engine.MotifCount, Config.PATH_LENGTH, Config.DIRECT_GPU_WORD_REPEATS)); device.For(size, new MultiPathJumpKernel( inputMotifs, inputPathIds, jump64Out, base64Jumps, size, engine.MotifCount, Config.BASE64_LEVELS, 1)); device.For(size, new FusedJumpAttractorKernel( inputMotifs, inputPathIds, fused64Out, fused64Meta, base64Jumps, meta, size, engine.MotifCount, Config.BASE64_LEVELS, 1)); device.For(size, new Base64DecomposedMultiPathKernel( inputMotifs, inputPathIds, base64ArbOut, base64Jumps, size, engine.MotifCount, Config.BASE64_LEVELS, Config.ARBITRARY_REPEAT_COUNT, Config.BASE64_JUMP_BASE)); device.For(size, new BinaryDecomposedMultiPathKernel( inputMotifs, inputPathIds, binaryArbOut, binaryJumps, size, engine.MotifCount, Config.BINARY_LEVELS, Config.ARBITRARY_REPEAT_COUNT)); Synchronize(device); int[] direct = new int[size]; int[] jump64 = new int[size]; int[] fused = new int[size]; int[] metaOut = new int[size]; int[] base64Arb = new int[size]; int[] binaryArb = new int[size]; int[] pathIds = new int[size]; directOut.CopyTo(direct, 0, 0, size); jump64Out.CopyTo(jump64, 0, 0, size); fused64Out.CopyTo(fused, 0, 0, size); fused64Meta.CopyTo(metaOut, 0, 0, size); base64ArbOut.CopyTo(base64Arb, 0, 0, size); binaryArbOut.CopyTo(binaryArb, 0, 0, size); inputPathIds.CopyTo(pathIds, 0, 0, size); int directVsJump = 0; int jumpVsFused = 0; int metaMatches = 0; int base64VsBinaryArb = 0; for (int i = 0; i < size; i++) { if (direct[i] == jump64[i]) directVsJump++; if (jump64[i] == fused[i]) jumpVsFused++; int expectedMeta = engine.PackedAttractorMetadata[pathIds[i] * engine.MotifCount + fused[i]]; if (expectedMeta == metaOut[i]) metaMatches++; if (base64Arb[i] == binaryArb[i]) base64VsBinaryArb++; } Console.WriteLine($"Direct F^64 vs jump J1 match rate:{directVsJump * 100.0 / size:F2}%"); Console.WriteLine($"Jump J1 vs fused J1 motif match rate:{jumpVsFused * 100.0 / size:F2}%"); Console.WriteLine($"Fused packed metadata match rate:{metaMatches * 100.0 / size:F2}%"); Console.WriteLine($"Base64 arbitrary vs binary arbitrary match rate:{base64VsBinaryArb * 100.0 / size:F2}%"); // Exact deep equality:base64 J4 vs binary B24 { int sanity = 2000; int ok = 0; var rand = new Random(999); for (int i = 0; i < sanity; i++) { int pathId = rand.Next(Config.PATH_COUNT); int motif = rand.Next(engine.MotifCount); int j4 = engine.Base64JumpTables[GetTableOffset(pathId, 4, engine.MotifCount, Config.BASE64_LEVELS) + motif]; int b24 = engine.BinaryJumpTables[GetTableOffset(pathId, 24, engine.MotifCount, Config.BINARY_LEVELS) + motif]; if (j4 == b24) ok++; } Console.WriteLine($"Base64 J4 vs binary B24 sanity:{ok * 100.0 / sanity:F2}%"); } // Exact F^4096 equality: // direct exact by 64x J1 vs one J2 { int sanity = 2000; int ok = 0; var rand = new Random(1234); for (int i = 0; i < sanity; i++) { int pathId = rand.Next(Config.PATH_COUNT); int motif = rand.Next(engine.MotifCount); int current = motif; int j1Offset = GetTableOffset(pathId, 1, engine.MotifCount, Config.BASE64_LEVELS); for (int k = 0; k < 64; k++) current = engine.Base64JumpTables[j1Offset + current]; int j2 = engine.Base64JumpTables[GetTableOffset(pathId, 2, engine.MotifCount, Config.BASE64_LEVELS) + motif]; if (current == j2) ok++; } Console.WriteLine($"Exact F^4096 sanity (64x J1 == J2):{ok * 100.0 / sanity:F2}%"); } Console.WriteLine("Sample decoded fused metadata:"); for (int i = 0; i < 5; i++) { int rep = UnpackRep(metaOut[i]); int len = UnpackLen(metaOut[i]); int steps = UnpackSteps(metaOut[i]); Console.WriteLine( $" sample {i}:pathId={pathIds[i]},finalMotif={fused[i]},rep={rep},cycleLen={len},stepsToCycle={steps}"); } } // ============================================================ // REPORTING // ============================================================ static void PrintBase64LevelStats(EngineBuildResult engine) { Console.WriteLine("BASE64 JUMP HIERARCHY"); Console.WriteLine("------------------------------------------------"); for (int level = 0; level < engine.Base64LevelApplications.Length; level++) Console.WriteLine($" J{level}:F^{engine.Base64LevelApplications[level]:N0}"); } static void PrintBinaryLevelStats(EngineBuildResult engine) { Console.WriteLine("BINARY JUMP HIERARCHY"); Console.WriteLine("------------------------------------------------"); for (int level = 0; level < engine.BinaryLevelApplications.Length; level += 4) { var parts = new List<string>(); for (int k = 0; k < 4 && level + k < engine.BinaryLevelApplications.Length; k++) { int l = level + k; parts.Add($"B{l}:F^{engine.BinaryLevelApplications[l]:N0}"); } Console.WriteLine(" " + string.Join(" | ", parts)); } } static void PrintPathSummaries(EngineBuildResult engine) { Console.WriteLine("PATH ATTRACTOR SUMMARIES"); Console.WriteLine("------------------------------------------------"); for (int p = 0; p < engine.PathSummaries.Length; p++) { var s = engine.PathSummaries[p]; Console.WriteLine( $" pathId={p} [{Config.PATH_NAMES[p]}] | cycles={s.CycleCount},maxCycle={s.MaxCycleLength},avgSteps={s.AverageSteps:F2},dominantBasin={s.DominantBasinSize:N0} ({s.DominantBasinSize * 100.0 / engine.MotifCount:F2}%),dominantLen={s.DominantCycleLength},rep={s.DominantRepresentative}"); } } static void PrintRealTaskResult(RealTaskResult result) { Console.WriteLine(result.Name); Console.WriteLine($" Time:{result.Seconds:F2} s"); Console.WriteLine($" Batches completed:{result.BatchesCompleted:N0}"); Console.WriteLine($" Exact depth per batch:F^{result.ExactRepeat:N0}"); Console.WriteLine($" Batches/sec:{result.BatchesPerSecond:N4}"); Console.WriteLine($" Path applications/sec:{result.PathApplicationsPerSecond:N0}"); Console.WriteLine($" Generator applications/sec:{result.GeneratorApplicationsPerSecond:N0}"); } // ============================================================ // AUTO / LEVEL HELPERS // ============================================================ static int TryGetExactLevel(int repeatCount, long[] levelApplications) { for (int level = 0; level < levelApplications.Length; level++) { if (levelApplications[level] == repeatCount) return level; } return -1; } // ============================================================ // PACKED META // ============================================================ static int PackMeta(int representative, int cycleLength, int stepsToCycle) { return (representative & Config.REP_MASK) | ((cycleLength & Config.LEN_MASK) << Config.LEN_SHIFT) | ((stepsToCycle & Config.STEP_MASK) << Config.STEP_SHIFT); } static int UnpackRep(int packed) => packed & Config.REP_MASK; static int UnpackLen(int packed) => (packed >> Config.LEN_SHIFT) & Config.LEN_MASK; static int UnpackSteps(int packed) => (packed >> Config.STEP_SHIFT) & Config.STEP_MASK; // ============================================================ // GEOMETRIC / COMBINATORIAL CORE // ============================================================ static int ApplyGenerator(int packed, int generator) { int[] slots = UnpackSlots(packed); int[] perm = GetGeneratorPermutation(generator); int[] permuted = ApplyPermutation(slots, perm); int missing = FindEmpty(permuted); int movedTarget; if (missing != generator) { permuted[missing] = TransformMove(permuted[generator], generator, generator, missing); permuted[generator] = Config.EMPTY; movedTarget = missing; } else { int donor = FindFirstOccupied(permuted, generator); permuted[generator] = TransformMove(permuted[donor], generator, donor, generator); permuted[donor] = Config.EMPTY; movedTarget = generator; } for (int s = 0; s < 4; s++) { if (permuted[s] == Config.EMPTY) continue; if (s == movedTarget) continue; permuted[s] = TransformStay(permuted[s], generator, s); } return PackSlots(permuted[0], permuted[1], permuted[2], permuted[3]); } static int TransformMove(int localState, int generator, int sourceSlot, int targetSlot) { if (localState == Config.EMPTY) return Config.EMPTY; int orientation = localState % Config.ORIENTATION_COUNT; int phase = localState / Config.ORIENTATION_COUNT; orientation = (orientation + 1 + 3 * generator + 2 * sourceSlot + targetSlot) % Config.ORIENTATION_COUNT; phase = (phase + 1 + generator + sourceSlot + 2 * targetSlot) % Config.PHASE_COUNT; return phase * Config.ORIENTATION_COUNT + orientation; } static int TransformStay(int localState, int generator, int slot) { if (localState == Config.EMPTY) return Config.EMPTY; int orientation = localState % Config.ORIENTATION_COUNT; int phase = localState / Config.ORIENTATION_COUNT; orientation = (orientation + GeneratorOrientationDelta(generator, slot)) % Config.ORIENTATION_COUNT; phase = (phase + GeneratorPhaseDelta(generator, slot) + ((orientation & 3) == 0 ? 1 : 0)) % Config.PHASE_COUNT; return phase * Config.ORIENTATION_COUNT + orientation; } static int GeneratorOrientationDelta(int generator, int slot) { return generator switch { 0 => slot + 1, 1 => 2 * slot + 3, 2 => 3 * slot + 2, _ => 5 + slot }; } static int GeneratorPhaseDelta(int generator, int slot) { return (generator + 2 * slot + 1) % Config.PHASE_COUNT; } static int[] GetGeneratorPermutation(int generator) { return generator switch { 0 => new[] { 0, 2, 3, 1 }, 1 => new[] { 3, 1, 0, 2 }, 2 => new[] { 1, 3, 2, 0 }, _ => new[] { 2, 0, 1, 3 } }; } static int Canonicalize(int packed, List<int[]> symmetryGroup) { int best = int.MaxValue; foreach (var perm in symmetryGroup) { int transformed = ApplyPackedPermutation(packed, perm); if (transformed < best) best = transformed; } return best; } static List<int[]> BuildA4SymmetryGroup() { int[] a = { 0, 2, 3, 1 }; int[] b = { 1, 0, 3, 2 }; var result = new List<int[]>(); var seen = new HashSet<int>(); var queue = new Queue<int[]>(); int[] identity = { 0, 1, 2, 3 }; queue.Enqueue(identity); seen.Add(PermutationCode(identity)); while (queue.Count > 0) { int[] p = queue.Dequeue(); result.Add((int[])p.Clone()); int[] pa = ComposePermutations(p, a); int[] pb = ComposePermutations(p, b); int codeA = PermutationCode(pa); int codeB = PermutationCode(pb); if (seen.Add(codeA)) queue.Enqueue(pa); if (seen.Add(codeB)) queue.Enqueue(pb); } result.Sort((x, y) => PermutationCode(x).CompareTo(PermutationCode(y))); return result; } static int[] ComposePermutations(int[] first, int[] second) { int[] result = new int[4]; for (int old = 0; old < 4; old++) result[old] = second[first[old]]; return result; } static int PermutationCode(int[] perm) { return perm[0] + 4 * perm[1] + 16 * perm[2] + 64 * perm[3]; } static int[] ApplyPermutation(int[] slots, int[] oldToNew) { int[] result = new int[4]; for (int old = 0; old < 4; old++) result[oldToNew[old]] = slots[old]; return result; } static int ApplyPackedPermutation(int packed, int[] oldToNew) { int[] slots = UnpackSlots(packed); int[] transformed = ApplyPermutation(slots, oldToNew); return PackSlots(transformed[0], transformed[1], transformed[2], transformed[3]); } static int FindEmpty(int[] slots) { for (int i = 0; i < 4; i++) if (slots[i] == Config.EMPTY) return i; throw new InvalidOperationException("No empty slot found."); } static int FindFirstOccupied(int[] slots, int startSlot) { for (int k = 1; k <= 3; k++) { int s = (startSlot + k) & 3; if (slots[s] != Config.EMPTY) return s; } throw new InvalidOperationException("No occupied slot found."); } static int PackSlots(int s0, int s1, int s2, int s3) { int p = s3; p = p * Config.PACK_BASE + s2; p = p * Config.PACK_BASE + s1; p = p * Config.PACK_BASE + s0; return p; } static int[] UnpackSlots(int packed) { int[] slots = new int[4]; for (int i = 0; i < 4; i++) { slots[i] = packed % Config.PACK_BASE; packed /= Config.PACK_BASE; } return slots; } static int GetTableOffset(int pathId, int level, int motifCount, int levelCount) { return ((pathId * levelCount) + level) * motifCount; } // ============================================================ // FUNCTIONAL GRAPH / ATTRACTOR ANALYSIS // ============================================================ static void AnalyzeFunctionalGraph( int[] next, out int[] cycleId, out int[] cycleRepresentative, out int[] cycleLength, out int[] stepsToCycle) { int n = next.Length; cycleId = new int[n]; cycleRepresentative = new int[n]; cycleLength = new int[n]; stepsToCycle = new int[n]; Array.Fill(cycleId, -1); bool[] done = new bool[n]; int cycleCounter = 0; for (int start = 0; start < n; start++) { if (done[start]) continue; var path = new List<int>(64); var pos = new Dictionary<int, int>(64); int v = start; while (true) { if (done[v]) { int cid = cycleId[v]; int rep = cycleRepresentative[v]; int clen = cycleLength[v]; int steps = stepsToCycle[v]; for (int i = path.Count - 1; i >= 0; i--) { int node = path[i]; done[node] = true; cycleId[node] = cid; cycleRepresentative[node] = rep; cycleLength[node] = clen; stepsToCycle[node] = steps + 1; steps++; } break; } if (pos.TryGetValue(v, out int cycleStart)) { int cid = cycleCounter++; int rep = path[cycleStart]; int clen = path.Count - cycleStart; for (int i = cycleStart; i < path.Count; i++) if (path[i] < rep) rep = path[i]; for (int i = cycleStart; i < path.Count; i++) { int node = path[i]; done[node] = true; cycleId[node] = cid; cycleRepresentative[node] = rep; cycleLength[node] = clen; stepsToCycle[node] = 0; } int steps = 1; for (int i = cycleStart - 1; i >= 0; i--) { int node = path[i]; done[node] = true; cycleId[node] = cid; cycleRepresentative[node] = rep; cycleLength[node] = clen; stepsToCycle[node] = steps; steps++; } break; } pos[v] = path.Count; path.Add(v); v = next[v]; } } } // ============================================================ // DATA INIT / SYNC // ============================================================ static void FillRandomFloatData(GraphicsDevice device, ReadWriteBuffer<float> buffer, int size, int seed) { const int CHUNK = 1_000_000; var rand = new Random(seed); int offset = 0; while (offset < size) { int count = Math.Min(CHUNK, size - offset); float[] tmp = new float[count]; for (int i = 0; i < count; i++) tmp[i] = (float)(rand.NextDouble() * 2.0 - 1.0); buffer.CopyFrom(tmp, 0, offset, count); offset += count; } } static void FillRandomMotifIds(GraphicsDevice device, ReadWriteBuffer<int> buffer, int size, int motifCount, int seed) { const int CHUNK = 1_000_000; var rand = new Random(seed); int offset = 0; while (offset < size) { int count = Math.Min(CHUNK, size - offset); int[] tmp = new int[count]; for (int i = 0; i < count; i++) tmp[i] = rand.Next(motifCount); buffer.CopyFrom(tmp, 0, offset, count); offset += count; } } static void FillRandomPathIds(GraphicsDevice device, ReadWriteBuffer<int> buffer, int size, int pathCount, int seed) { const int CHUNK = 1_000_000; var rand = new Random(seed); int offset = 0; while (offset < size) { int count = Math.Min(CHUNK, size - offset); int[] tmp = new int[count]; for (int i = 0; i < count; i++) tmp[i] = rand.Next(pathCount); buffer.CopyFrom(tmp, 0, offset, count); offset += count; } } static void FillGroupedPathIds(GraphicsDevice device, ReadWriteBuffer<int> buffer, int size, int pathCount) { const int CHUNK = 1_000_000; int offset = 0; while (offset < size) { int count = Math.Min(CHUNK, size - offset); int[] tmp = new int[count]; for (int i = 0; i < count; i++) { long globalIndex = offset + i; tmp[i] = (int)((globalIndex * pathCount) / size); if (tmp[i] >= pathCount) tmp[i] = pathCount - 1; } buffer.CopyFrom(tmp, 0, offset, count); offset += count; } } static void Synchronize(GraphicsDevice device) { using var fence = device.AllocateReadWriteBuffer<int>(1); device.For(1, new FenceKernel(fence)); int[] tmp = new int[1]; fence.CopyTo(tmp); } } }
