Кроме того больше суток гонял самодельную программку, которая тупо перебирала ВСЕ варианты простой заглушки...
В BOINC её
Да я свой сервер планирую написать и клиента надо пошустрее - с хешами и т.д.
P.S. Посмотрел внимательнее по меткам времени на файлах - гонял 16 часов примерно, получается 4670 вариантов в секунду обрабатывалось (по 11 поколений каждый вариант) - по идее с хэшами было бы намного быстрее
P.P.S. Кроме хешей можно ещё добавить логику, которая на первом же поколении отбросит кучу неживучих вариантов, если они нестабильны (поглащатель должен быть стабильным неменяющимся объектом, пока в него не въедет сигнал)
Пока хеши не стал заводить, но добавил проверку на нестабильность в самом начале - уже стало намного быстрее, иду дальше:
Стабильных вариантов (которые не разваливается в первом же поколении) очень мало теперь - программа работает примерно в 12 раз быстрее
P.S. За 1.4 миллиарда вариантов набралось только 33 стабильных - ничего успешного пока, но зато обнаружился почти отражатель - он отражает сигнал обратно в канал, а потом взрывается
P.P.S. Ускорил программу ещё сильнее (покидаю цикл раньше, если понятно, что с этим вариантом всё плохо) -- объём работ, что изначально выполнялся за 16 часов, теперь посчитался за полчаса - т.е. ускорение в более чем в 30 раз!!! Причём меняя программку, я продолжают с точки, где остановился, а не с самого начала - так что я уже за эти дни 2 миллиарда комбинаций перебрал
За 1.4 миллиарда вариантов набралось только 33 стабильных - ничего успешного пока, но зато обнаружился почти отражатель - он отражает сигнал обратно в канал, а потом взрывается
Есть такие штуки в "Игре Жизнь", которые называются wickstretchers - они похожи на puffers (которые похожи на spaceships, но улетая оставляют следы), которые растягивают wicks (линейные осцилляторы) и вот некоторые из них могут тянуть и полосатые каналы и через них даже можно посылать наши сигналы со скоростью света (одна клетка за такт) - например сигнал OSD4#A72B64 и wickstretcher его даже съест:
видео1
но сигнал должен идти в правильной фазе иначе всё взорвётся
видео2
тут проигрыватель игры жизнь сам удаляется, чтобы всё происходящее было видно
Во вторых 4 миллиардах оказалось только 7 стабильных конфигураций (которые тем не менее разваливались через несколько поколений), а в третьих 4 миллиардах набралось 16 стабильных...
Особенности реализации - клетки являются ячейками таблицы, в которых хранится количество соседей (и это количество визуально видно). По ходу пересчёта временное состояние ячеек сохраняется путём установки других (не white или blue) цветов - red для умирающих клеток и purple для рождающихся - но глазом это не заметно т.к. они потом быстро заменяются на нормальные цвета во втором проходе, когда корректируются числа соседей для клеток около которых произошло рождение или смерть.
Ещё раз объясню суть своего алгоритма 15 летней давности (смотреть по сишному коду) - вместо двухмерного массива булеанов имеем двумерный массив байтов, где храним (в младших 4 битах) заранее подсчитанное количество живых соседей для каждой клетки. В старших битах имеем один бит на текущее состояние и два бита на будущее - бит на рождение и бит на смерть. Пробегая по массиву нам уже не надо обегать каждую клетку считая соседей - они уже посчитаны - просто сверяемся по текущему состоянию и числу соседей - если клетка занята и не 2 и не 3 соседа - взводим флаг смерти, если клетка свободна и имеется ровно 3 соседа - взводим флаг рождения. После того как все флаги взведены - пробегаем по таблице ещё раз, обращая внимание только на те клетки где есть флаг смерти или флаг рождения, в соответствии с которыми декрементируем или инкрементируем суммы живых соседей в клетках вокруг. По моим понятиям вычислений будет сильно меньше, нежели в случае "честного" алгоритма, который считает соседей у каждой клетки каждый раз.
Нашёл тут один алгоритм от 1992 года, где тоже заранее подсчитанные соседи участвуют, но там клетки ещё и по 3 объединены для быстрых вычислений
P.S. Интересно что если идти по тому же пути что и тут - складывать вместе 2 или более соседних клеток, то на то чтобы хранить количество соседей для каждой клетки уже ненадо иметь 4 бита - достаточно только 3-х, так как мы имеем как минимум на одного соседа меньше (сосед в том же пакете сидит ; ) и 0...7 (8 минус один) замечательно влезает в 3 бита!
Там же у автора есть 32-битная версия (тоже с ассемблерными частями), где он по 4 клетки за раз обрабатывает - причем в ряд. Я решил тоже сделать 4 клетки, но в квадрате 2x2 - в этом случае у каждой клетки будет только 5 внешних соседей, т.е. количество соседей которое надо хранить может варьироваться от 0 до 5 - как это наиболее компактно представить? А очень просто: n1 + 6*n2 + 36*n3 + 216*n4 (где nN - количество внешних соседей соответствующей клетки) - в этом случае информация о соседях этих 4 клеток влезет в 11 битов
Еще я написал текстовую программку чтобы выяснить какого размера должна быть таблица байтов, чтобы при обращении к ней по индексу не было бы потерь на копирование из памяти в кеш данных - и у меня получилось, наращивая размер таблицы от 2^1 и далее 2^2, 2^3 и т.д., что до 2^14 индексирование случайным индексом идет абсолютно одинаковое время, а вот далее - скорость обращения падает в 2 и более раз. Соответственно получилось, что таблицу быстрых вычислений надо утолкать в 16 килобайт.
Значит нам надо зная состояние этих 4 клеток и количетсво соседей вокруг них посчитать состояние этих клеток для следующего поколения - для этого мы будем индексировать таблицу байтов адресом n1+6*n2+36*n3+216*n4+2048*s1+4096*s2+8192*s3 (где sN это текущее состояние клеток) и каждый байт в этой таблице будет иметь два набора по 4 бита описывающих будущее состояние для s4=0 (младший нибл) и для s4=1 (старший нибл) - так мы утолкаемся в 16 килобайт, например - если все 4 клетки заняты и у них нет внешних соседей, т.е. s1=s2=s3=s4=1 и n1=n2=n3=n4=0 - обращаемся по адресу 11100000000000 и берем старший нибл (т.к. s4=1) где будет 1111 (т.е. ничего не изменилось - все четыре клетки остаются на месте), вариант с s1=1 s2=1 s3=1 s4=0 будет обращаться к тому же байту, но младшему нибблу где тоже будет 1111, т.е. tab[0x380]=0xFF и т.д.
Далее сравнив 4 состояния что было и 4 состояния что стало можно понять у какой клетки надо обойти соседей и для каждого изменить количество его соседей (если клетка родилась то надо сделать +1 для каждой клетки вокруг, а если умерла, то -1) - проще всего сделать это через switch(было<<4|стало) { case 0x00: // ничего не изменилось (было 0000 стало 0000) break; case 0x01: // клетка родилась в правом-нижнем углу квадрата (было 0000 стало 0001) // сделать +1 для всех соседей правой-нижней клетки break; // и т.д. }
Еще я написал текстовую программку чтобы выяснить какого размера должна быть таблица байтов, чтобы при обращении к ней по индексу не было бы потерь на копирование из памяти в кеш данных - и у меня получилось, наращивая размер таблицы от 2^1 и далее 2^2, 2^3 и т.д., что до 2^14 индексирование случайным индексом идет абсолютно одинаковое время, а вот далее - скорость обращения падает в 2 и более раз...
Текст программки под спойлером и мои результаты с 64-битного дебиян-линуха на амд64 ниже:
Если у кого есть желание может попробовать на своём компьютере (собирать gcc -O2 lutest.c -o lutest запускать без параметров) и запостить результаты сюда
AMD64-CacheChart.png [ 213.87 KiB | Viewed 10277 times ]
L1 имеет задержку на доступ 3-4 такта, а L2 - уже 19 тактов (у Steamroller-a), поэтому массивы больше 16кб имеют в среднем в 5 раз более худшие времена доступа если лезть в них действительно случайным образом. Вот инфа про мою 4-коровую (+ 8 графических коров, которые в линухе не юзаются) конфигурацию AMD-проца: http://www.cpu-world.com/CPUs/Bulldozer/AMD-A10-Series%20A10-7850K.html (там правда написано 4 x 16 KB 4-way set associative data caches, т.е. их четыре - видимо один и тот же массив больше 16кб не может быть аккуратно порезан на разные кеши)
P.P.S. Intel Core i5 вроде как имеет 6 x 32KB 8-way дата кэш - там наверное результаты моей программки сдвинуться и до 2^15...
P.P.P.S. Так и есть - проверил на Intel Core Duo с WinXP в Cigwin:
Attachment:
IntelCoreDuo.gif [ 17.83 KiB | Viewed 10268 times ]
P.P.P.P.S. Откопал свой чёрный G4 Cube и как ни странно он живой Я его "потерял" при переезде из Нью-Йорка в 2017, а вот сейчас "нашёл" когда коробки для очередного переезда перепаковывал Вот его результаты, подтверждающие информацию, что процессор PowerPC G4 имеет L1 кеш данных размером 32кб:
Так же можно видеть, что копирование байтов из L1 кеша данных в G4 медленнее в 5-6 раз чем у AMD или Intel (разница частоты процессоров - как раз те самые 6 раз)
Это все биты помененные как x и 6 младших битов помеченных y или 3FFFFFFFFF - всего 38 битов, что есть 275 миллиардов вариантов, перебранных за 2 недели работы переборной программы
P.S. Остановил программку - ничего путнего не нашлось...
Еще я написал текстовую программку чтобы выяснить какого размера должна быть таблица байтов, чтобы при обращении к ней по индексу не было бы потерь на копирование из памяти в кеш данных - и у меня получилось, наращивая размер таблицы от 2^1 и далее 2^2, 2^3 и т.д., что до 2^14 индексирование случайным индексом идет абсолютно одинаковое время, а вот далее - скорость обращения падает в 2 и более раз...
Текст программки под спойлером и мои результаты с 64-битного дебиян-линуха на амд64 ниже:
Если у кого есть желание может попробовать на своём компьютере (собирать gcc -O2 lutest.c -o lutest запускать без параметров) и запостить результаты сюда
P.S. Да, похоже так и есть - у AMD процессоров размер L1 кеша данных 16кб (у меня семейство Bulldozer с микроархитектурой Steamroller): https://www.extremetech.com/extreme/188776-how-l1-and-l2-cpu-caches-work-and-why-theyre-an-essential-part-of-modern-chips L1 имеет задержку на доступ 3-4 такта, а L2 - уже 19 тактов (у Steamroller-a), поэтому массивы больше 16кб имеют в среднем в 5 раз более худшие времена доступа если лезть в них действительно случайным образом. Вот инфа про мою 4-коровую (+ 8 графических коров, которые в линухе не юзаются) конфигурацию AMD-проца: http://www.cpu-world.com/CPUs/Bulldozer/AMD-A10-Series%20A10-7850K.html (там правда написано 4 x 16 KB 4-way set associative data caches, т.е. их четыре - видимо один и тот же массив больше 16кб не может быть аккуратно порезан на разные кеши)
P.P.S. Intel Core i5 вроде как имеет 6 x 32KB 8-way дата кэш - там наверное результаты моей программки сдвинуться и до 2^15...
P.P.P.S. Так и есть - проверил на Intel Core Duo с WinXP в Cigwin:
P.P.P.P.S. Откопал свой чёрный G4 Cube и как ни странно он живой Я его "потерял" при переезде из Нью-Йорка в 2017, а вот сейчас "нашёл" когда коробки для очередного переезда перепаковывал Вот его результаты, подтверждающие информацию, что процессор PowerPC G4 имеет L1 кеш данных размером 32кб:
Так же можно видеть, что копирование байтов из L1 кеша данных в G4 медленнее в 5-6 раз чем у AMD или Intel (разница частоты процессоров - как раз те самые 6 раз)
Результат работы этой же программы на моём новом Apple Mac Mini M1:
Получается размер кэша данных первого уровня на M1 аж 2^17=128KB
P.S. Похоже так и есть для "high-performance" ядер:
Quote:
The Apple M1 chip works with 4 high-performance cores, each of which is what Apple described as the “world’s fastest.” These high-performance cores work with ultra-wide execution architecture as well as 192KB instruction cache. These high-performance cores include 128KN data cache and a shared 12MB L2 cache.
There’ll be four high-efficiency cores as well, with wide execution architecture, 128KB instruction cache, 64KB data cache, and shared 4MB L2 cache.
Для представления более "длинных" конструкций просто добавляем битов в начало - т.е. при переполнее 32-битного целого, можно легко перейти к 64-битным (при этом можно будет покрыть все ходилки-ползалки до 12 колонок в длинну, однако реально перебрать все варианты в этом случае будет практически невозможно)...
Screenshot from 2023-04-11 23-38-41.png [ 50.04 KiB | Viewed 4195 times ]
Суть задумки была тупым перебором от маленьких к большим найти все перемещабельные по полоскам объекты, чтобы потом построить на самых удачных из них компьютер внутри игры Жизнь...
Users browsing this forum: No registered users and 9 guests
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot post attachments in this forum