Comments 124
Интересно, что будет если обрабатывать только клетки с изменившимся состоянием и их соседей? Исходя из правил в большинстве случаем большую часть времени большая часть клеток находится в неизменном состоянии — так что можно их эффективно обсчитывать за 0 тактов.
Можно даже дальше пойти: разбить плоскость на квадраты и кешировать результат итераций для каждого квадрата. Собственно, эта идея лежит в основе того самого Hashlife.
В моей реализации почти так и происходит. Правда обрабатываются просто окрестности всех живых клеток.
Координаты каждой живой клетки упаковываются в int и засовываются в Set. Размер инта позволяет таким образом иметь тороидальное поле 64к*64к.
lightln2 может объединимся?
Кому интересно поковырять через консоль, это можно сделать так:
state = new Set
for( let x = -100; x < 100; ++x ) {
for( let y = -100; y < 100; ++y ) {
if( Math.random() > .5 ) state.add( $mol_coord_pack( x , y ) )
}
}
$hyoo_life.Root(0).Map().state( state )
Я провел такой эксперимент, ускорение получилось в 3.5 раза для рандомной начальной конфигурации (но, конечно, для маленьких и статичных конфигураций ускорение может быть в сотни и тысячи раз)
Обсуждение и код в этой ветке. Может быть, кто-то сможет еще больше ускорить.
Я прошу прощения, нам с самого начала надо было вести обсуждение под Вашим комментарием (теперь, наверно, не перенести).
Обсуждение и код в этой ветке. Может быть, кто-то сможет еще больше ускорить.
Я прошу прощения, нам с самого начала надо было вести обсуждение под Вашим комментарием (теперь, наверно, не перенести).
Вот отличный алгоритм на случай если надо будет ускорить сильнее.
И SIMD через wasm
Вроде пока еще на стадии proposal
Зачем поле делать 1920х1080, если оно даже в полноэкранном режиме не влезет в такой же монитор из-за верхней панели? Оптимизируйте размер поля так чтоб только на видимой части экрана было
А как лучше эту проблему решить? Просто уменьшить размер поля на высоту панели? или скриптом проверять размер экрана и скейлить канвас? или можно как-то подобрать значение meta name=«viewport», чтобы браузер сам все за нас сделал? Я имеюю в виду даже не технический аспект, а юзабилити — какой способ даст наиболее логичное с точки зрения пользователя поведение?
Картинка должна остаться пиксель в пиксель, чтоб не получить проблемы растяжения/сжатия. С точки зрения пользователя поле должно идеально вписываться в экран) Но есть проблемы:
1) редкий пользователь знает о полноэкранном режиме.
2) устройство можно повернуть, размер экрана изменится
3) браузер можно ресайзить
4) размеры под поле заранее тоже не угадаете — у всех разные панели сверху/снизу и в разных браузерах даже верхняя панель может быть разной (у меня на ней только 2 кнопки из 4 нормально отображаются)
Я бы сделал стандартное поле каким-то невыпирающим фиксированным, типа 800х600 и разрешил указывать свои размеры или по кнопке подгонять под текущий экран. Но это так себе решение.
По нажатию на «random pattern» я хочу видеть реально random, а не поле для ввода числа руками. И незачем это прятать в отдельное окно, если места на экране пустого уйма — покажите мне сид сразу. А переключение скорости мне вообще непонятно. 2х-50х примерно на одинаковой скорости работают, только на 50 заметно больше кадров пропускает. На не самом слабом компе эти переключатели не имеют смысла из-за размеров поля. Дайте посмотреть на это на поле поменьше/побольше, на мой вкус. Мне интересно было бы глянуть на реальный х50, пусть и на поле 600х600.
1) редкий пользователь знает о полноэкранном режиме.
2) устройство можно повернуть, размер экрана изменится
3) браузер можно ресайзить
4) размеры под поле заранее тоже не угадаете — у всех разные панели сверху/снизу и в разных браузерах даже верхняя панель может быть разной (у меня на ней только 2 кнопки из 4 нормально отображаются)
Я бы сделал стандартное поле каким-то невыпирающим фиксированным, типа 800х600 и разрешил указывать свои размеры или по кнопке подгонять под текущий экран. Но это так себе решение.
По нажатию на «random pattern» я хочу видеть реально random, а не поле для ввода числа руками. И незачем это прятать в отдельное окно, если места на экране пустого уйма — покажите мне сид сразу. А переключение скорости мне вообще непонятно. 2х-50х примерно на одинаковой скорости работают, только на 50 заметно больше кадров пропускает. На не самом слабом компе эти переключатели не имеют смысла из-за размеров поля. Дайте посмотреть на это на поле поменьше/побольше, на мой вкус. Мне интересно было бы глянуть на реальный х50, пусть и на поле 600х600.
Спасибо за фидбек, у меня нет опыта в UI, и для меня такие вещи не очевидны.
А какой у Вас браузер? У меня в Хроме на скорости 2x — 120 итераций в секунду, на 50x — 220. В Edge и на мобильном телефоне на всех 1x-50x скорость одинаковая — примерно 17 итераций в секунду, но, думаю, это из-за движка яваскрипта.
2х-50х примерно на одинаковой скорости работают
А какой у Вас браузер? У меня в Хроме на скорости 2x — 120 итераций в секунду, на 50x — 220. В Edge и на мобильном телефоне на всех 1x-50x скорость одинаковая — примерно 17 итераций в секунду, но, думаю, это из-за движка яваскрипта.
С точки зрения пользователя хочется ещё иметь возможность масштабировать поле.
Средствами браузера не очень удобно, так как пропадает доступность панели управления.
У меня например случайно создалась довольно крупная стабильная структура, хотелось рассмотреть вблизи и пошагово, оказалось не очень удобно. Спас пробел, который работает как шаг, за это спасибо.
Кстати интересно, а есть каталог стабильных структур?
Средствами браузера не очень удобно, так как пропадает доступность панели управления.
У меня например случайно создалась довольно крупная стабильная структура, хотелось рассмотреть вблизи и пошагово, оказалось не очень удобно. Спас пробел, который работает как шаг, за это спасибо.
Кстати интересно, а есть каталог стабильных структур?
Вот, например: List_of_common_still_lifes
А в машиночитаемом виде есть такой?
наверняка есть, так как есть глобальная база, в которую все исследователи кладут «интересные» шаблоны (найденные брутфорсом на GPU).
Или можно еще скачать программу Golly, в ней есть пара сотен шаблонов (в простом текстовом формате)
Или можно еще скачать программу Golly, в ней есть пара сотен шаблонов (в простом текстовом формате)
Спасибо, нашёл свою структуру в списке осциляторов . Оказалась довольно распространённой. Интересненько.
Можно еще избавиться от операции копирования из temp-буфера, сделав 2 буфера, и переключаться между ними поочередно
Согласен, это тоже классическая оптимизация, которую было бы неплохо применить. Я, честно говоря, поленился: суммарно оба массива не превышают одного мегабайта, и должны помещаться в кеш третьего уровня, так что копирование должно быть быстрым по сравнению с довольно большим количеством логических операций. Но так как эта оптимизация не усложняет код, то кажется логичным ее применить, даже если она даст только 10% выигрыша.
Можете, пожалуйста, чуть подробнее объяснить?
Сейчас проверил, переключение буфера вместо копирования дает ускорение примерно в 1.15 раз (на 13%)
Интересно, насколько известная Golly golly.sourceforge.net (C++) с алгоритмом QuickLife и другими обгоняет эту C# программу (даже без учёта очень быстрого алгоритма HashLife, реализованного в Golly и дающего большое преимущество в случае регулярных паттернов на поле).
Я, когда готовил статью и искал интересные шаблоны, работал с Golly, но в основном на Hashlife. Я сейчас мельком посмотрел на код qlifealgo.cpp, и там тоже огромное количество оптимизаций, при чем они все равно используют quadtree, так что его скорость тоже растет с улучшением регулярности. Хотя SIMD они не используют. Я сейчас запустил его на рандомно заполненном поле размера 1920x1080 с коэффициентом 0.5 (то есть, примерно половина клеток — живые, половина — мертвые), и за первую секунду он обработал 1000 итераций, за вторую — уже 10000, и на статической картинке скорость стабилизировалась где-то на 50000 в секунду. На картинке из КПДВ он работает стабильно примерно со скоростью 5000 в секунду.
В 1995 году во время олимпиады по математике-информатике я познакомился с парнем из Черноголовки, который предложил свою оптимизацию проходов поля игры Жизнь. У них в школе это было типа внутреннего соревнования, в котором он победил.
Короче, подробности я конечно не вспомню, но поле 640х480 на 386 проце делалось около 50 итераций в секунду. Это я запомнил, т.к. на экране «светофоры» замирали в одном положении, либо горизонтальном, либо вертикальном, т.к. за время прохождения строчной развертки ЭЛТ монитора программа успевала пройти (как минимум) две итерации.
Забавно то, что уже тогда основной эффект был достигнут переносом вычислений в видеопамять.
Я тут прикинул на коленке, поле было меньше в 6.75 раз, процессор медленнее в 100 раз (4ГГц сегодняшних процессоров против 40 МГц на 386 в режиме турбо).
AdvancedLifeExtensions на таком поле выдал бы 2500х6.75=16875 итераций в секунду, но в переводе на MIPSы 1995 года — в 100 раз меньше, 169 итераций в секунду.
Алгоритм 1995 года выдавал 50 итераций в секунду.
За 25 лет улучшение в 3.375 раз (смайлик).
Прошу, не воспринимайте этот пост слишком уж серьезно. Это больше про башковитых парней из подмосковного наукограда. Их же там много было раз существовало внутреннее соревнование.
Короче, подробности я конечно не вспомню, но поле 640х480 на 386 проце делалось около 50 итераций в секунду. Это я запомнил, т.к. на экране «светофоры» замирали в одном положении, либо горизонтальном, либо вертикальном, т.к. за время прохождения строчной развертки ЭЛТ монитора программа успевала пройти (как минимум) две итерации.
Забавно то, что уже тогда основной эффект был достигнут переносом вычислений в видеопамять.
Я тут прикинул на коленке, поле было меньше в 6.75 раз, процессор медленнее в 100 раз (4ГГц сегодняшних процессоров против 40 МГц на 386 в режиме турбо).
AdvancedLifeExtensions на таком поле выдал бы 2500х6.75=16875 итераций в секунду, но в переводе на MIPSы 1995 года — в 100 раз меньше, 169 итераций в секунду.
Алгоритм 1995 года выдавал 50 итераций в секунду.
За 25 лет улучшение в 3.375 раз (смайлик).
Прошу, не воспринимайте этот пост слишком уж серьезно. Это больше про башковитых парней из подмосковного наукограда. Их же там много было раз существовало внутреннее соревнование.
Где-то в то же время (может на 2-3 года позже) довелось мне столкнуться с разочарованием.
Мы с другом были фанатами программирования, что было несколько необычно для нашей почти сельской местности. Благо повезло — учились в экспериментальной гимназии и компьютеры у нас в гимназии были. Не 386-е, конечно (о них мы только в журналах читали), а Поиск-2, но на то время и они казались нам неверояными. Где-то в 1997-м завезли нам один 286-й, но за него никого кроме учителей не пускали.
Мы постоянно зависали после уроков в компьютерном классе и что-то писали. Расходились по домам со списком задач, которые необходимо решить и возвращались с листочками, исписанными программами, которые печатали и решали чей вариант решения лучше.
В общем участвовали в районной олимпиаде по программированию, где участников было ещё несколько человек помимо нас двоих. Была надежда попасть на областную олимпиаду.
В области наши работы завернули под предлогом, что нам помогали учителя. Видимо слишком выбивались работы из обычного районного уровня.
Обидно было.
Мы с другом были фанатами программирования, что было несколько необычно для нашей почти сельской местности. Благо повезло — учились в экспериментальной гимназии и компьютеры у нас в гимназии были. Не 386-е, конечно (о них мы только в журналах читали), а Поиск-2, но на то время и они казались нам неверояными. Где-то в 1997-м завезли нам один 286-й, но за него никого кроме учителей не пускали.
Мы постоянно зависали после уроков в компьютерном классе и что-то писали. Расходились по домам со списком задач, которые необходимо решить и возвращались с листочками, исписанными программами, которые печатали и решали чей вариант решения лучше.
В общем участвовали в районной олимпиаде по программированию, где участников было ещё несколько человек помимо нас двоих. Была надежда попасть на областную олимпиаду.
В области наши работы завернули под предлогом, что нам помогали учителя. Видимо слишком выбивались работы из обычного районного уровня.
Обидно было.
Ну так а сейчас-то как? Пошли по пути программиста профессионально или нет?
Отучился не по профилю (далековато до области было, а поблизости — разве что пединститут на учителя информатики), на экономиста. В кабинете информатики и там был завсегдатаем, на кафедре ИКТ был как родной. Деньги зарабатывал на расчётках по информатике и курсовых по разным предметам.
Для диплома написал программу для вычисления кредитоспособности предприятия исходя из годовых отчётов.
По специальности не работал. Сразу компы год собирал, потом фотографом пару лет отработал. На обоих местах писал софт для автоматизации рабочих мест. Недавно был в фотосалоне — до сих пор ребята на старой винде сидят и древним фотошопом пользуются, потому что за 14 лет уже не представляют себе как без моего софта работать, а у меня исходники не сохранились, чтобы прикрутить к чему посвежее (там глубокая интеграция с фотошопом).
После фотосалона выстрелило моё резюме на программиста, перебрался в столицу, ну и 14 лет уже как программирую.
Друг, к сожалению, пошёл в другую сторону и сейчас обычным электриком на родине трудится, хотя программировал гениально и компьютерами фанател. Алгоритмы его, как правило, получались получше моих. Пару лет назад виделись, пытался ему на пальцах объяснить что такое ООП, но, то ли способностей учителя у меня нет, то ли он навыки растерял…
Но для меня программирование — это жизнь, постоянно что-то писал (и пишу), ежедневно, а у друга были невероятные способности ко всему, как говорят «не гумманитарному». Математика, информатика, физика, химия — всё подряд. А вот с гумманитарными предметами — наоборот. Из гимназии был отчислен за неуспеваемость по иностранному языку. И с дальнейшим обучением были проблемы того же рода.
Его способностями восхищались все преподаватели естественных дисциплин. Уверен — при должной мотивации он мог бы сказать своё слово в науке, но наше образование всегда всех под одну гребёнку гребло и гребёт. Не вписываешься в стандарты — гуляй, даже если человек — гений в чём-то отдельном. Разве что спортсменов и шоуменов-КВНщиков готовы вытаскивать по всем предметам ради престижа учебного заведения. А физмат мало кому интересен, если гениальность в отрыве от гумманитарных предметов.
Для диплома написал программу для вычисления кредитоспособности предприятия исходя из годовых отчётов.
По специальности не работал. Сразу компы год собирал, потом фотографом пару лет отработал. На обоих местах писал софт для автоматизации рабочих мест. Недавно был в фотосалоне — до сих пор ребята на старой винде сидят и древним фотошопом пользуются, потому что за 14 лет уже не представляют себе как без моего софта работать, а у меня исходники не сохранились, чтобы прикрутить к чему посвежее (там глубокая интеграция с фотошопом).
После фотосалона выстрелило моё резюме на программиста, перебрался в столицу, ну и 14 лет уже как программирую.
Друг, к сожалению, пошёл в другую сторону и сейчас обычным электриком на родине трудится, хотя программировал гениально и компьютерами фанател. Алгоритмы его, как правило, получались получше моих. Пару лет назад виделись, пытался ему на пальцах объяснить что такое ООП, но, то ли способностей учителя у меня нет, то ли он навыки растерял…
Но для меня программирование — это жизнь, постоянно что-то писал (и пишу), ежедневно, а у друга были невероятные способности ко всему, как говорят «не гумманитарному». Математика, информатика, физика, химия — всё подряд. А вот с гумманитарными предметами — наоборот. Из гимназии был отчислен за неуспеваемость по иностранному языку. И с дальнейшим обучением были проблемы того же рода.
Его способностями восхищались все преподаватели естественных дисциплин. Уверен — при должной мотивации он мог бы сказать своё слово в науке, но наше образование всегда всех под одну гребёнку гребло и гребёт. Не вписываешься в стандарты — гуляй, даже если человек — гений в чём-то отдельном. Разве что спортсменов и шоуменов-КВНщиков готовы вытаскивать по всем предметам ради престижа учебного заведения. А физмат мало кому интересен, если гениальность в отрыве от гумманитарных предметов.
Довольно странно. Видеопамять в таких компах была очень медленной, и видеокарты ничего вычислять не умели.
К сожалению, код для обработки данных на видеокарте пока еще невозможно написать на .NET.
Хорошая попытка, Microsoft, но нет.
UFO just landed and posted this here
Есть ещё http://www.aleagpu.com/ с бесплатной лицензией под одну консьюмерскую карту
Я бы из них тогда попробовал ILGPU — она OpenSource и, вроде как, не требует сложной настройки.
UFO just landed and posted this here
При всей нелюбви к электрону, так считать нельзя. Во-первых, далеко не каждое нативное приложение использует SIMD-инструкции. Во-вторых, далеко не каждое приложение является подобной "битодробилкой", а в других областях соотношение производительности может оказаться другим.
А я наоборот, увидел что js не так плох как его малюют. То есть даже в такой алгоритмичной задаче js быстрее половины вариантов. Без этой статьи я бы поставил что js на порядки медленнее любой реализации.
Джону Хортону Конвею, жизнь которого в возрасте 82 лет прервал короновирус в апреле 2020-го года, посвящается...
UFO just landed and posted this here
Я точно не знаю, но возможно, что так как она была придумана в 1970 году, когда персональных компьютеров не было, требовался игрок, который должен был вручню гонять симуляцию на листке в клеточку.
UFO just landed and posted this here
Песочница же. Как минимум начальное состояние можно задавать, а в некоторых реализациях можно вводить паттерны прямо в процессе. В детстве написал себе игрушку, в которой было два вида клеток, и одному виду можно было вручную помогать вытеснить второй.
Многопоточность никак тут не заюзать?
Да, конечно, думаю, тут можно (и даже нужно!) использовать многопоточность, если мы хотим добиться максимальной производительности.
Это не отменяет пользу от однопоточной оптимизации, но согласен, про многопоточность, наверно, следовало упомянуть.
Это не отменяет пользу от однопоточной оптимизации, но согласен, про многопоточность, наверно, следовало упомянуть.
В моей реализации (на java) многопоточность дает четырехкратный прирост при работе в 8 и более потоков на четрехъядерном восьмипоточном процессоре.
UFO just landed and posted this here
Это другой тип оптимизации, который может сильно ускорить «хорошие» сценарии, но сильно замедлить «плохие».
Если живых клеток на поле мало, то этот подход даст огромный эффект — можно получить ускорение и в 100 и в 1000 раз. Но если живых клеток много, то время, потраченное на проход их соседей, да еще и не в cache-friendly порядке, может замедлить алгоритм в десятки раз.
Например, на поле 1920x1080 примерно два миллиона клеток, и алгоритм, сканирующий все поле, делает два миллиона итераций.
Для какого-нибудь глайдера, в котором не больше 10 точек, алгоритм со списком будет обрабабывать за итерацию 10 + 8*10 < 100 точек, то есть, будет быстрее в 20000 раз!
Но если в начальной конфигурации поля половина клеток живая, то алгоритм со списком будет делать 9 миллионов итераций, то есть, в 4.5 раза медленнее (на самом деле, еще медленней из-за cache misses). И это только в сравнении с неоптимизированным алгоритмом.
Если живых клеток на поле мало, то этот подход даст огромный эффект — можно получить ускорение и в 100 и в 1000 раз. Но если живых клеток много, то время, потраченное на проход их соседей, да еще и не в cache-friendly порядке, может замедлить алгоритм в десятки раз.
Например, на поле 1920x1080 примерно два миллиона клеток, и алгоритм, сканирующий все поле, делает два миллиона итераций.
Для какого-нибудь глайдера, в котором не больше 10 точек, алгоритм со списком будет обрабабывать за итерацию 10 + 8*10 < 100 точек, то есть, будет быстрее в 20000 раз!
Но если в начальной конфигурации поля половина клеток живая, то алгоритм со списком будет делать 9 миллионов итераций, то есть, в 4.5 раза медленнее (на самом деле, еще медленней из-за cache misses). И это только в сравнении с неоптимизированным алгоритмом.
UFO just landed and posted this here
UFO just landed and posted this here
даже если живых клеток более половины (чего я на видео не видел) экономия всё равно должна получаться существенная.
Вы же предлагаете проверять всех соседей каждой живой клетки — а их аж 9. А поскольку чтобы проверить не проверили ли мы уже клетку, надо тоже потратить время — выигрыш по времени выходит только когда живых клеток менее где-то 1/9.
UFO just landed and posted this here
эта игра жизнь ВСЕГДА вырождается к сильно разреженной матрице живых клеток
Доказано, что плотность может превышать 50%
UFO just landed and posted this here
Из осциллятора, который получил QDeathNick, можно составить нестатическую фигуру, если я не ошибся в подсчетах, 32% плотности:
Проверил на коленке Вашу идею:
Лучше, чем LifeBytes, но хуже, чем LongLife. Код:
По поводу последнего: в такой большой рандомной картинке даже на тысяной итерации изменяется около сорока тысяч клеток:
LifeInList: 1000 steps in 17.252 seconds, 57.965 steps/sec
LifeIsChange: 1000 steps in 11.783 seconds, 84.868 steps/sec
Лучше, чем LifeBytes, но хуже, чем LongLife. Код:
проверяем только живые и их соседей
/// <summary>
/// only processes live cells and their neighbours
/// </summary>
public class LifeInList : LifeJourney
{
List<int> liveCells = new List<int>();
byte[] field = new byte[WIDTH * HEIGHT];
List<int> nextLiveCells = new List<int>();
List<int> processedCells = new List<int>();
bool[] processed = new bool[WIDTH * HEIGHT];
public override bool Get(int i, int j) => field[j * WIDTH + i] == 1;
public override void Set(int i, int j, bool value)
{
if (value && (i == 0 || i == WIDTH - 1)) throw new ArgumentException("i");
if (value && (j == 0 || j == HEIGHT - 1)) throw new ArgumentException("j");
if (Get(i, j) == value) return;
field[j * WIDTH + i] = (byte) (value? 1 : 0);
if (value) liveCells.Add(j * WIDTH + i);
else liveCells.Remove(j * WIDTH + i); // very slow but not used on hot-path
}
private void ProcessLiveCell(int cell)
{
if (processed[cell]) return;
processedCells.Add(cell);
processed[cell] = true;
int x = cell % WIDTH;
int y = cell / WIDTH;
if (x == 0 || x == WIDTH - 1) return;
if (y == 0 || y == HEIGHT - 1) return;
int neighbours =
field[cell - WIDTH - 1] + field[cell - WIDTH] + field[cell - WIDTH + 1] +
field[cell - 1] + field[cell + 1] +
field[cell + WIDTH - 1] + field[cell + WIDTH] + field[cell + WIDTH + 1];
if(neighbours == 2 || neighbours == 3)
{
nextLiveCells.Add(cell);
}
}
private void ProcessDeadCell(int cell)
{
if (field[cell] == 1) return; // cell is alive, will be processed in the main loop
if (processed[cell]) return; // already processed
processedCells.Add(cell);
processed[cell] = true;
int x = cell % WIDTH;
int y = cell / WIDTH;
if (x == 0 || x == WIDTH - 1) return;
if (y == 0 || y == HEIGHT - 1) return;
int neighbours =
field[cell - WIDTH - 1] + field[cell - WIDTH] + field[cell - WIDTH + 1] +
field[cell - 1] + field[cell + 1] +
field[cell + WIDTH - 1] + field[cell + WIDTH] + field[cell + WIDTH + 1];
if (neighbours == 3)
{
nextLiveCells.Add(cell);
}
}
public override void Step()
{
foreach(int cell in liveCells)
{
ProcessLiveCell(cell);
ProcessDeadCell(cell - WIDTH - 1);
ProcessDeadCell(cell - WIDTH);
ProcessDeadCell(cell - WIDTH + 1);
ProcessDeadCell(cell - 1);
ProcessDeadCell(cell + 1);
ProcessDeadCell(cell + WIDTH - 1);
ProcessDeadCell(cell + WIDTH);
ProcessDeadCell(cell + WIDTH + 1);
}
foreach (int cell in liveCells) field[cell] = 0;
foreach (int cell in processedCells) processed[cell] = false;
processedCells.Clear();
foreach (int cell in nextLiveCells) field[cell] = 1;
List<int> temp = liveCells;
liveCells = nextLiveCells;
nextLiveCells = temp;
nextLiveCells.Clear();
}
}
проверяем только изменившиеся и их соседей
/// <summary>
/// only processes changed cells and their neighbours
/// </summary>
public class LifeIsChange : LifeJourney
{
byte[] currentField = new byte[WIDTH * HEIGHT];
byte[] nextField = new byte[WIDTH * HEIGHT];
List<int> currentChangedCells = new List<int>(WIDTH * HEIGHT);
List<int> nextChangedCells = new List<int>(WIDTH * HEIGHT);
List<int> processedCellsList = new List<int>(WIDTH * HEIGHT);
bool[] processedCellsMap = new bool[WIDTH * HEIGHT];
public override bool Get(int i, int j) => currentField[j * WIDTH + i] == 1;
public override void Set(int i, int j, bool value)
{
if (value && (i == 0 || i == WIDTH - 1)) throw new ArgumentException("i");
if (value && (j == 0 || j == HEIGHT - 1)) throw new ArgumentException("j");
int cell = j * WIDTH + i;
currentField[cell] = (byte) (value ? 1 : 0);
currentChangedCells.Add(cell);
}
private void ProcessCell(int cell)
{
if (processedCellsMap[cell]) return;
int x = cell % WIDTH;
int y = cell / WIDTH;
if (x == 0 || x == WIDTH - 1) return;
if (y == 0 || y == HEIGHT - 1) return;
processedCellsMap[cell] = true;
processedCellsList.Add(cell);
bool alive = currentField[cell] == 1;
int neighbours =
currentField[cell - WIDTH - 1] + currentField[cell - WIDTH] + currentField[cell - WIDTH + 1] +
currentField[cell - 1] + currentField[cell + 1] +
currentField[cell + WIDTH - 1] + currentField[cell + WIDTH] + currentField[cell + WIDTH + 1];
bool nextAlive = (alive & (neighbours == 2 || neighbours == 3)) || (!alive && neighbours == 3);
nextField[cell] = (byte)(nextAlive ? 1 : 0);
if(nextField[cell] != currentField[cell]) nextChangedCells.Add(cell);
}
public override void Step()
{
foreach(int cell in currentChangedCells)
{
ProcessCell(cell - WIDTH - 1);
ProcessCell(cell - WIDTH);
ProcessCell(cell - WIDTH + 1);
ProcessCell(cell - 1);
ProcessCell(cell);
ProcessCell(cell + 1);
ProcessCell(cell + WIDTH - 1);
ProcessCell(cell + WIDTH);
ProcessCell(cell + WIDTH + 1);
}
foreach (int cell in processedCellsList) processedCellsMap[cell] = false;
//Console.WriteLine($"Processed {processedCellsList.Count} cells because of {currentChangedCells.Count} changed cells");
processedCellsList.Clear();
List<int> tempCells = currentChangedCells;
currentChangedCells = nextChangedCells;
nextChangedCells = tempCells;
byte[] tempField = currentField;
currentField = nextField;
nextField = tempField;
nextChangedCells.Clear();
}
}
По поводу последнего: в такой большой рандомной картинке даже на тысяной итерации изменяется около сорока тысяч клеток:
...
Processed 191416 cells because of 45367 changed cells
Processed 190530 cells because of 45175 changed cells
Соседей — 8.
bump
А если использовать функциональный подход и взять функциональный язык, то тогда возможна игра не бесконечном поле. Для этого вместо того чтобы хранить массив клеток, надо хранить только множество живых фигур. Тогда будет обсчитываться только та часть поля, где есть фигуры, а та часть поля, где фигур больше нет — не будет обсчитываться. Это ещё и решает проблему того, что планер улетает в бесконечность. Нет никаких проблем чтобы просчитать одинокий планер улетевший в бесконечность, поскольку мы не храним многомиллионный массив. И функция Step будет не обходить массив в цикле на каждом шаге, а будет преобразовывать фигуру прошлого поколения, в фигуру нового поколения. Так как такие функция будут чистыми, то это позволяет очень просто распараллеливать вычисления на любое количество потоков, включая также GPU. При этом можно использовать такие же битовые оптимизации. Также это будет обобщённым решением, и позволит играть хоть на 3D поле, а не только 2D.
P.S. Для меня это стало большой неожиданностью, что создатель этой игры и великий математик Джон Конвей умер в этом году.
P.S. Для меня это стало большой неожиданностью, что создатель этой игры и великий математик Джон Конвей умер в этом году.
Так как такие функция будут чистыми, то это позволяет очень просто распараллеливать вычисления на любое количество потоков, включая также GPU
Интересно, как? У вас есть функция, которая принимает на вход все живые клетки и выдаёт новые живые клетки. Функция внутри особо не паралелится, а снаружи для запуска следующей итерации нужно закончить вычисление предыдущей.
Параллелизм тут только на уровне одного шага, следующий шаг зависит от предыдущего. Функция принимает фигуру, мы не храним полное состояние поля. Если две фигуры расположены в разных углах, они независимы и не могут повлиять друг на друга. И поэтому мы их можем посчитать независимо. То есть новое поколение фигуры зависит только от самой фигуры, а не от глобального состояния. Из-за этого эта функция чистая и их можно легко распараллеливать. И потому что нет изменяемого состояния (например, как с копированием массива temp в тексте), мы можем, образно говоря, посчитать каждую из фигур в вакууме.
Вот, например, неплохое объснение Hashlife, там очень похоже на то, как Вы описываете.
А что такое "фигура"? Если между двумя фигурами есть промежуток в 1 пиксель — они считаются одной фигурой? Что если две фигуры влияют на один пиксель (растут)?
Сомнительный выигрыш, короче.
И потому что нет изменяемого состояния (например, как с копированием массива temp в тексте)
И что? Темп-массив можно заполнять параллельно по рядам, к примеру. Заполнение одного ряда никак не влияет на заполнение другого.
fuggy
Примерно так и работает алгоритм Hashlife, который может работать в тысячи и миллионы раз быстрее, его придумал американский програмист Bill Gosper в 1983 году. Мне не удалось достать его оригинальную статью, так что не ручаюсь за достоверность, но я слышал, что его оригинальная версия была написана на лиспе.
Примерно так и работает алгоритм Hashlife, который может работать в тысячи и миллионы раз быстрее, его придумал американский програмист Bill Gosper в 1983 году. Мне не удалось достать его оригинальную статью, так что не ручаюсь за достоверность, но я слышал, что его оригинальная версия была написана на лиспе.
забавная игра, спасибо за статью
причем крайние клетки всегда мертвые.
Извиняюсь, возможно я что-то упустил, но разве граничные клетки не сшиваются с противоположными краями, замыкая всю игровую поверхность?
копируем массив temp в исходный массив.
И вот здесь я перестал читать и просто проскролил до конца.
Вы поступили не умно. Очень интересная статья.
Ну, я вообще-то не очень умный. И соответственно часто поступаю не умно. Например, пишу все на ассемблере. И не копирую массив temp в исходный массив никогда. И кстати, поискал и оказывается, у меня в исходниках (500kloc) нет ни одной переменной, массив или просто этикетку с имени "temp". Мне стыдно, но что поделать… (но есть "template" — это считается?)
Кстати, насчет ассемблера: у меня изначально была реализация на C++ через интринсики, но она работала с абсолютно такой же скоростью, что и версия на C#. Я не ожидал, что JIT сможет скомпилировать такой же хороший код, что и C++
Ну-у-у, если и там копировали temp, то вполне нормально… Вообще, компилируемый язык и хороший компилятор не делают автоматически код быстрым. И писать действительно быстрый код на C++, совершенно нетривиальный процесс. (кстати, написать то же самое в плане оптимизации на ассемблере намного легче) Посмотрите как выглядит какая нибудь хорошо оптимизированная библиотека на C++.
Последовал Вашему совету и полез в мой любимый zlib. Поймите меня правильно, я люблю ассемблер, и сам на нем когда-то писал, но не могу удержаться:
/* inffast.c -- fast decoding
* Copyright (C) 1995-2017 Mark Adler
* For conditions of distribution and use, see copyright notice in zlib.h
*/
#include "zutil.h"
#include "inftrees.h"
#include "inflate.h"
#include "inffast.h"
#ifdef ASMINF
# pragma message("Assembler code may have bugs -- use at your own risk")
#else
...
А в C есть фабричная гарантия от багов, что ли???
Кстати, я Марка очень уважаю, но в высоко оптимизированном коде, намного вероятнее что баги будут именно в C коде а не в ассемблере.
Но что баги — их тестят и исправляют.
П.С. Кстати, я имел ввиду смотреть на оптимизированный код C/C++, а не на то что написано на ассемблере.
не копирую массив temp в исходный массив никогда
просто этикетку с имени «temp»
Если кому интересно, простой поиск по коду Linux находит дофига и переменных temp, и копирования в и из них
drivers/misc/mic/scif/scif_dma.c
if (!window_virt)
return;
if (to_temp)
memcpy(temp, window_virt, loop_len);
else
memcpy(window_virt, temp, loop_len);
window_virt = _get_local_va(offset, window, loop_len);
if (!window_virt)
return;
if (to_temp)
memcpy(temp, window_virt, loop_len);
Сложно найти человека, не знакомого с игрой «Жизнь»
ИМХО, таких людей очень много.
Если вдруг решите оптимизировать по-настоящему, то посмотрите на эту статью — https://habr.com/ru/post/180135/
for (int i = 1; i < WIDTH - 1; i++)
for (int j = 1; j < HEIGHT - 1; j++)При обходе двумерного массива, внутренний цикл всегда должен быть по строке, а не столбцу. Так намного быстрее, особенно когда данные не влезают в кеш-память.
Ваш комментарий верен в общем случае, но при обходе двумерного массива внутренний цикл должен быть по второму индексу, так что в данном случае этот порядок правильный, можете поменять местами и проверить. Тут скорее проблема в том, что массив определялся как new bool[WIDTH, HEIGHT], хотя надо было бы длину и ширину поменять местами.
«Жизнь» можно даже
SQL-запросом:
with
-- параметры - количество поколений, ширина, высота и количество элементов
parms as (select last_gen, width, height, width * height total_cells
from (select 8 last_gen, 10 width, 7 height from dual)
),
-- Исходное поле
src_field as (
select rpad(lpad(rpad('0010', width, '0') || rpad('0001', width, '0') ||
rpad('0111', width, '0'),
width * 4,
'0'),
total_cells,
'0') field
from parms
),
-- Жизнь, как она есть
life(gen, i, field, next_field) as (
select 0 gen, 0 i, field, '' next_field
from src_field
union all
select case
when i = total_cells then
gen + 1
else
gen
end gen,
mod(i + 1, total_cells + 1) i,
case
when i = total_cells then
translate(next_field, '0123456789ABCDEFGH', '000100000001100000')
else
field
end field,
case
when i = total_cells then
''
else
next_field ||
substr('0123456789ABCDEFGH',
substr(field, i + 1, 1) * 9 +
substr(field,
mod(i + total_cells - width - 1, total_cells) + 1,
1) + substr(field,
mod(i + total_cells - width, total_cells) + 1,
1) +
substr(field,
mod(i + total_cells - width + 1, total_cells) + 1,
1) +
substr(field, mod(i + total_cells - 1, total_cells) + 1, 1) +
substr(field, mod(i + 1, total_cells) + 1, 1) +
substr(field, mod(i + width - 1, total_cells) + 1, 1) +
substr(field, mod(i + width, total_cells) + 1, 1) +
substr(field, mod(i + width + 1, total_cells) + 1, 1) + 1,
1)
end next_field
from life, parms
where gen < last_gen
and i <= total_cells
)
-- select --------------------------------------
select case
when y = -1 then
'Generation ' || gen
else
translate(substr(field, y * width + 1, width), '01', '.X')
end v
from life
cross join (select level - 2 y, width
from parms
connect by level <= height + 1) ys
where i = 0
order by gen, y;
Generation 0
..........
..X.......
...X......
.XXX......
..........
..........
..........
...
Generation 1
..........
..........
.X.X......
..XX......
..X.......
..........
..........
Generation 2
..........
..........
...X......
.X.X......
..XX......
..........
..........
Generation 3
..........
..........
..X.......
...XX.....
..XX......
..........
..........
Generation 4
..........
..........
...X......
....X.....
..XXX.....
..........
..........
Generation 5
..........
..........
..........
..X.X.....
...XX.....
...X......
..........
Generation 6
..........
..........
..........
....X.....
..X.X.....
...XX.....
..........
Generation 7
..........
..........
..........
...X......
....XX....
...XX.....
..........
Generation 8
..........
..........
..........
....X.....
.....X....
...XXX....
..........
Не могу не отметить, что объяснять правила на примере, где белые клетки — живые, а черные — мертвые… Нужно быть сильно рисковым человеком в 2020 году. ))
«Жизнь» лучше всего работает на FPGA. Прикрутить RAM на ~50GB\s и можно наслаждаться 14КFPS в FullHD и не на самом топовом камне. :D
И это мы делаем «в лоб»! Добавить оптимизаций и можно получить «плавающий фпс» хоть до +100KFPS в FullHD!(шучу немного)
Кнш… 50GB\s вы получить наврядли сможете, а вот 10GB\s вполне можно развести «недорого».
ЗЫ — Даже на SDRAM с дёшевеньких плат, на каких-нить циклонах4 с 22KLE, можно без оптимизаций ~40фпс выжать в FullHD.
И это мы делаем «в лоб»! Добавить оптимизаций и можно получить «плавающий фпс» хоть до +100KFPS в FullHD!(шучу немного)
Кнш… 50GB\s вы получить наврядли сможете, а вот 10GB\s вполне можно развести «недорого».
ЗЫ — Даже на SDRAM с дёшевеньких плат, на каких-нить циклонах4 с 22KLE, можно без оптимизаций ~40фпс выжать в FullHD.
Круто! Получается, скорость будет ограничена только пропускной способностью канала памяти? После Вашего комментария полез искать, пользуются ли FPGA для ресёрча, и нашел, что пользуются, но, похоже, это единичные случаи.
Два вопроса по этому поводу (чисто теоретических):
1) Нашел в гугле, что есть FPGA Virtex-7 2000T с двумя миллионами ячеек; в нем можно сделать симуляцию игры не в памяти, а напрямую в этих ячейках? Или топология не позволяет?
2) Может быть, можно сделать специализированную микросхему с двумя мегабайтами SRAM, и к каждой ячейке прикрутить трехбитный сумматор? Тогда теоретически можно добиться по одной итерации на такт?
Два вопроса по этому поводу (чисто теоретических):
1) Нашел в гугле, что есть FPGA Virtex-7 2000T с двумя миллионами ячеек; в нем можно сделать симуляцию игры не в памяти, а напрямую в этих ячейках? Или топология не позволяет?
2) Может быть, можно сделать специализированную микросхему с двумя мегабайтами SRAM, и к каждой ячейке прикрутить трехбитный сумматор? Тогда теоретически можно добиться по одной итерации на такт?
В такой задаче у нас будет матрица из 1024 вычислителей (32х32), и посути их работа тормозится лишь памятью. Если не заморачиваться с конвейером и широкими шинами с кэшем, то загруженность матрицы для плат с SDRAM меньше 1% при fmax в районе 50МГц(можно и больше, но опять же, конвейер нужно делать).
Я не сильный спец по FPGA, это моё излюбленное хобби. Воссоздаю старые железки, пишу свои. Вот так вот))
1 — Скорее всего можно, ибо самих данных о ячейках «жизнь» меньше чем шина между ними. Разве что придумать чуть хитрый подход как этот массив считывать, чтоб место на чипе сэкономить, и только. Такую матрицу не получится настроить кнш, но чисто фиксировано считать HD может хотя бы на те же 50МГц, те ~50МFPS
А если прям обмозговать, думаю там найдётся способ используя внутреннюю SRAM расширить хотя бы до FullHD или уж больше. Но тут ещё раз проблема как это считывать и хотяб просто по ethernet отправить чтоб камень не разрося раз в 5.
2 — (*После написания осознал что видимо не так вас понял, ASIC, те специализированную схему, можно сделать любой, я вас умоляю. Но нафига? Это очень дорого выйдет, а аппаратно считать «жизнь» в 4К с 500MFPS??? А то и 1GFPS если вы сможете достаточно хорошо оптимизировать это всё, почему нет? xDDDD. Дальше можно не читать, меня просто понесло сильно, но я решил оставить хз зачем*)
С SRAM камнем ты просто получишь меньше задержек при считывании, но не большие МБ\с. (многие поддерживают конвейерный подход что нам на руку)
Замечу что хорошие и быстрые SRAM камушки стоят почти столько же сколько дешёвый фпга типа тех же 4 циклонов c 22КLE.
В принципе добиться одной итерации за такт можно, ибо это FPGA. У тебя может быть просто 1024 ячеек + регистры с данными о них, а потом по сигналу «ena» посчитать их за один такт. Толи дело что fmax страдать будет.
Про суматор я не сильно понял, прошу прощения ))
А лучший способ ускорить матрицу, это ввести нормальный конвейер с кэшированием. Тк задача без ветвлений, то конвейер даже простаивать не будет + SRAM тоже конвейерный. Также можем просто считать строки 32х32, и дальние(что не используются в вычислениях а нужны лишь их крайние ячейки) сохранять в кэш, что уже разгрузит память неплохо ибо нужно лишь 1 раз по данным пройтись.
Дальше улучшать… Остаётся лишь добавить аппаратное сжатие к памяти, либо усложнять сами алгоритмы загрузки.
К примеру…
Тк мы не ограничены лютыми задержками ибо SRAM+кэш, можем добавить лишний байт к каждой группе ячеек, и просто не грузить их если они пустые и наоборот, иначе грузить всю группу. Что даст не хилый такой буст во многих случаях, но оно даст плавающий FPS, а не стабильный как раньше.
Чисто прикинем, если раньше мы всегда читали полностью 32х32 то теперь мы читаем группы по 4х4. Тоесть при пустых ячейках у нас тратится 64такта на чтение 32х32, при полу пустых 576, а при полных 1088. Что вроде как больше чем старые 1024, но как я знаю, у нас редко когда все ячейки полностью забиты. Потому думаю в среднем FPS будет выше.
Думаю при всём этом на DE0-Nano можно будет выжать ~100фпс FullHD в среднем
(У меня сейчас под рукой подобного типа китайская плата просто)
Ну и последняя улучшалка, вроде видел 2х порт SRAM камни, что может офигеть как разгрузить шину, и не надо будет пропускную способность на 2 делить. Либо поставить их несколько и писать\читать по цепочке.
Ой чота меня понесло, не буду удалять во общем.
Тут я просто «на глаз» оценивал, в реале цифры могут отличаться
И да, по факту у нас всё упрётся в память, ибо только на топовые FPGA можно прикрутить достаточно быструю память, чтоб она смогла покрыть чистую «производительность» матрицы, либо уже на их внутренних SRAM ячейках всё держать.
Крч по приколу, надо сделать это. В ближайшее время и простенькую статью написать… Мб аккаунт до «полноценного» улчшу xDDD
Я не сильный спец по FPGA, это моё излюбленное хобби. Воссоздаю старые железки, пишу свои. Вот так вот))
1 — Скорее всего можно, ибо самих данных о ячейках «жизнь» меньше чем шина между ними. Разве что придумать чуть хитрый подход как этот массив считывать, чтоб место на чипе сэкономить, и только. Такую матрицу не получится настроить кнш, но чисто фиксировано считать HD может хотя бы на те же 50МГц, те ~50МFPS
А если прям обмозговать, думаю там найдётся способ используя внутреннюю SRAM расширить хотя бы до FullHD или уж больше. Но тут ещё раз проблема как это считывать и хотяб просто по ethernet отправить чтоб камень не разрося раз в 5.
2 — (*После написания осознал что видимо не так вас понял, ASIC, те специализированную схему, можно сделать любой, я вас умоляю. Но нафига? Это очень дорого выйдет, а аппаратно считать «жизнь» в 4К с 500MFPS??? А то и 1GFPS если вы сможете достаточно хорошо оптимизировать это всё, почему нет? xDDDD. Дальше можно не читать, меня просто понесло сильно, но я решил оставить хз зачем*)
С SRAM камнем ты просто получишь меньше задержек при считывании, но не большие МБ\с. (многие поддерживают конвейерный подход что нам на руку)
Замечу что хорошие и быстрые SRAM камушки стоят почти столько же сколько дешёвый фпга типа тех же 4 циклонов c 22КLE.
В принципе добиться одной итерации за такт можно, ибо это FPGA. У тебя может быть просто 1024 ячеек + регистры с данными о них, а потом по сигналу «ena» посчитать их за один такт. Толи дело что fmax страдать будет.
Про суматор я не сильно понял, прошу прощения ))
А лучший способ ускорить матрицу, это ввести нормальный конвейер с кэшированием. Тк задача без ветвлений, то конвейер даже простаивать не будет + SRAM тоже конвейерный. Также можем просто считать строки 32х32, и дальние(что не используются в вычислениях а нужны лишь их крайние ячейки) сохранять в кэш, что уже разгрузит память неплохо ибо нужно лишь 1 раз по данным пройтись.
Дальше улучшать… Остаётся лишь добавить аппаратное сжатие к памяти, либо усложнять сами алгоритмы загрузки.
К примеру…
Тк мы не ограничены лютыми задержками ибо SRAM+кэш, можем добавить лишний байт к каждой группе ячеек, и просто не грузить их если они пустые и наоборот, иначе грузить всю группу. Что даст не хилый такой буст во многих случаях, но оно даст плавающий FPS, а не стабильный как раньше.
Чисто прикинем, если раньше мы всегда читали полностью 32х32 то теперь мы читаем группы по 4х4. Тоесть при пустых ячейках у нас тратится 64такта на чтение 32х32, при полу пустых 576, а при полных 1088. Что вроде как больше чем старые 1024, но как я знаю, у нас редко когда все ячейки полностью забиты. Потому думаю в среднем FPS будет выше.
Думаю при всём этом на DE0-Nano можно будет выжать ~100фпс FullHD в среднем
(У меня сейчас под рукой подобного типа китайская плата просто)
Ну и последняя улучшалка, вроде видел 2х порт SRAM камни, что может офигеть как разгрузить шину, и не надо будет пропускную способность на 2 делить. Либо поставить их несколько и писать\читать по цепочке.
Ой чота меня понесло, не буду удалять во общем.
Тут я просто «на глаз» оценивал, в реале цифры могут отличаться
И да, по факту у нас всё упрётся в память, ибо только на топовые FPGA можно прикрутить достаточно быструю память, чтоб она смогла покрыть чистую «производительность» матрицы, либо уже на их внутренних SRAM ячейках всё держать.
Крч по приколу, надо сделать это. В ближайшее время и простенькую статью написать… Мб аккаунт до «полноценного» улчшу xDDD
Спасибо! Было бы интересно, чего можно достичь на не-топовых FPGA.
Вообще интересно, чего можно достичь на разных технологиях за разные деньги. Я по сумме всех комментариев понял примерно так (плюс-минус порядок):
— процессор ($1'000) — 50'000 итераций в секунду
— видеокарта ($1'500) — 500'000 итераций в секунду
— FPGA ($15'000) — 50 миллионов итераций в секунду
— ASIC ($1'500'000) — 1 миллиард итераций в секунду
Вообще интересно, чего можно достичь на разных технологиях за разные деньги. Я по сумме всех комментариев понял примерно так (плюс-минус порядок):
— процессор ($1'000) — 50'000 итераций в секунду
— видеокарта ($1'500) — 500'000 итераций в секунду
— FPGA ($15'000) — 50 миллионов итераций в секунду
— ASIC ($1'500'000) — 1 миллиард итераций в секунду
Было бы интересно, чего можно достичь на не-топовых FPGA.
Ну много чего можно, проблема лишь в том, что выгодней делать именно специальные схемы для конкретных задач и только те что на видяхе считаются меньше ~200М«итераций»(я взял в среднем из сложных что видел). То есть, те же хэши считать, вроде на EP4CE115 можно уместить 4 «считалки» хэшей, которые могут тянуть 4*200Мхэш\с, но если примерно такой же цены видеокарта справляется так же, профита будет не особо много. Разве что Ватт меньше жрать будет. (В разы меньше xD)
Так со многими задачами где надо считать что-то или фильтровать + зависит от того кто делает это всё. Ибо можно оптимизировать архитектуру под конкретную FPGA, а можно просто логику описать, думаю понятно что результаты будут разные и порой в разы. (Самое простое, это что мультиплексоры для конкретного камня надо делать «определённой разрядности», те подгонять условия правильно, иначе это может генерить очень много лишней логики)
Кстааате, на FPGA очень офигенно синтезируются старые процессоры(примерно до ~10Мгц, уже дальше фана меньше). Допустим описав логику можно получить «аппаратную» эмуляцию с частотами даже в 10 раз больше оригинальной и кучей плюшек. Толку? Можно много всяких свистелок придумать, вон популярная статья на хабре была, где NES делали. (Вроде как малинка тоже так умеет, но радостей от «аппаратного клона» было больше xD) Ещё можно спокойно тренить ИИ на таком камушке. Помнится всплывала подобная статья на хабре, где взяли «не сильно» жирный камень и уместили ~10старых приставок, разогнали их в несколько раз и тренили ИИ, приводилось что на Xeon'ах оно работало изрядно плохо, потому искали другие пути.(точных чисел не помню, ну буст там был дичайший xD)
И ещё знаю пару людей, коих интересуют всякие «новаторские» подходы в параллельном программировании. То есть, различные конфигурации по типу… Тех же NUMA, или уж совсем экзотические.(Давно не общался, не помню точно всё + я с этим плохо знаком) Как бы выглядели чисто «аппаратные» свистелки которые прижились в программировании параллельных «программок». И просто всякие эксперименты «а оно вообще работать будет?»… Кнш двигалось это черепашьим темпом, но просто как забавный факт, есть
На этом применимость FPGA для меня «всё». Можно ещё так «по изучать» как железо работает, что бы вот прям быть «знающим страшные тайны, что не подвласны абстракциям!!!» xD
Было бы очень интересно прочесть такую статью
Давайте тогда на ASIC сразу замахнемся :)
Может, сразу делать дисплеи с интегрированной логикой клеток? Каждый пиксель смотрит на 8 своих соседей. Обсчёт всего поля — 1-2 такта. Можно достичь скорости 4e9 FPS.
Возможно уже писали такой комментарий. Я не нашел.
Если последний шаг с AVX накатить на последнюю версию, где по 2 клетки на байт, разве не будет ускорения еще в 2 раза?
Если последний шаг с AVX накатить на последнюю версию, где по 2 клетки на байт, разве не будет ускорения еще в 2 раза?
Спасибо за комментарий, это действительно отличная идея, я ее проверил уже после написания статьи.
Тут есть техническая проблема: в AVX невозможно сдвинуть на 4 бита весь регистр как одно 256-разрядное число, минимум нужно делать два сдвига и одно сложение, так что ускорение будет немного меньше, чем в два раза, и код сильно усложняется, но выигрыш в скорости все равно получается существенный.
Вкупе с еще одной идеей: избавиться от временного буффера вообще, и хранить дополнительно только три линии поля (текущую, выше, и ниже) получается суммарно ускорение в 330 раз от начальной версии, от 25 до 7400 шагов в секунду!
Можно код посмотреть на гитхабе: AdvancedLifeExtensionsInLineCompressed.cs.
Тут есть техническая проблема: в AVX невозможно сдвинуть на 4 бита весь регистр как одно 256-разрядное число, минимум нужно делать два сдвига и одно сложение, так что ускорение будет немного меньше, чем в два раза, и код сильно усложняется, но выигрыш в скорости все равно получается существенный.
Вкупе с еще одной идеей: избавиться от временного буффера вообще, и хранить дополнительно только три линии поля (текущую, выше, и ниже) получается суммарно ускорение в 330 раз от начальной версии, от 25 до 7400 шагов в секунду!
Можно код посмотреть на гитхабе: AdvancedLifeExtensionsInLineCompressed.cs.
Точно! Вы правы. Я что-то не подумал об усложнениях, которые появляются.
Ваша дополнительная идея очень хорошая. Ее можно слегка оптимизировать. Не уверен, что это сильно поможет. Когда Вы хотите произвести вычисления для некоторого элемента в середине поля, Вам необходимо знать предущую линию (под нее выделить память), в текущей линии предыдущий элемент, текущий и следующий (под них можно выделить 3 локальных переменных) и следующая линия (которая и так есть в исходном массиве, так как Вы еще не успели начать ее «портить»).
Тогда кешируется куски не 4 массивов, а лишь 3.
Но это, скорее оптимизация по памяти, чем по времени.
Ваша дополнительная идея очень хорошая. Ее можно слегка оптимизировать. Не уверен, что это сильно поможет. Когда Вы хотите произвести вычисления для некоторого элемента в середине поля, Вам необходимо знать предущую линию (под нее выделить память), в текущей линии предыдущий элемент, текущий и следующий (под них можно выделить 3 локальных переменных) и следующая линия (которая и так есть в исходном массиве, так как Вы еще не успели начать ее «портить»).
Тогда кешируется куски не 4 массивов, а лишь 3.
Но это, скорее оптимизация по памяти, чем по времени.
UFO just landed and posted this here
Тут дело не сколько в размерах кеша, сколько в количествах обращений к оперативной памяти.
Вроде бы чисто теоретически должно сработать, но затрудняюсь сказать, насколько это усложнит код. Кроме того, размер поля 1 мегабайт, а размер линии — 1 килобайт (по 4бита на клетку), так что экономия на одной линии не особо должна повлиять на производительность. Вот действительно где можно было бы сильно сэкономить, — это хранить клетки не в 4 битах, а в одном бите, и распаковывать только для подсчетов, примерно как это делается в этой статье. К сожалению, чтобы биты расширить в байты более-менее эффективно, нужен десяток AVX-инструкций; я пытался делать, но производительность только ухудшилась. В AVX512 будет специальная инструкция для этого, тогда можно будет попробовать, но пока процессоры не особо его поддерживают.
промахнулся
Небольшое замечание по поводу AVX2 версии:
Есть такая замечательная инструкция VPSHUFB (_mm256_shuffle_epi8, Avx2.Shuffle), которая может использоваться в качестве lookup таблицы из 16 одно байтовых значений.
Этой операцией можно заменить почти все битовые операции во втором цикле.
Есть такая замечательная инструкция VPSHUFB (_mm256_shuffle_epi8, Avx2.Shuffle), которая может использоваться в качестве lookup таблицы из 16 одно байтовых значений.
Этой операцией можно заменить почти все битовые операции во втором цикле.
Да, Вы правы, я уже после написания статьи заменил логические операции на shuffle, получив три строчки кода вместо шести (причем, более понятные): AdvancedLifeExtensions.cs:73
Правда, ускорение, по моим подсчетам, получилось не очень большое, около 5%.
Правда, ускорение, по моим подсчетам, получилось не очень большое, около 5%.
Тот случай, когда слишком много «AVX» в статье :-)
P.S. мой ник с 2005 года, Intel разработала эти инструкции в 2008 году, так что я не причём ))
P.S. мой ник с 2005 года, Intel разработала эти инструкции в 2008 году, так что я не причём ))
Sign up to leave a comment.
Как ускорить игру «Жизнь» в сто раз