Комментарии 124
Интересно, что будет если обрабатывать только клетки с изменившимся состоянием и их соседей? Исходя из правил в большинстве случаем большую часть времени большая часть клеток находится в неизменном состоянии — так что можно их эффективно обсчитывать за 0 тактов.
В моей реализации почти так и происходит. Правда обрабатываются просто окрестности всех живых клеток.
Координаты каждой живой клетки упаковываются в 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 )
Обсуждение и код в этой ветке. Может быть, кто-то сможет еще больше ускорить.
Я прошу прощения, нам с самого начала надо было вести обсуждение под Вашим комментарием (теперь, наверно, не перенести).
Зачем поле делать 1920х1080, если оно даже в полноэкранном режиме не влезет в такой же монитор из-за верхней панели? Оптимизируйте размер поля так чтоб только на видимой части экрана было
1) редкий пользователь знает о полноэкранном режиме.
2) устройство можно повернуть, размер экрана изменится
3) браузер можно ресайзить
4) размеры под поле заранее тоже не угадаете — у всех разные панели сверху/снизу и в разных браузерах даже верхняя панель может быть разной (у меня на ней только 2 кнопки из 4 нормально отображаются)
Я бы сделал стандартное поле каким-то невыпирающим фиксированным, типа 800х600 и разрешил указывать свои размеры или по кнопке подгонять под текущий экран. Но это так себе решение.
По нажатию на «random pattern» я хочу видеть реально random, а не поле для ввода числа руками. И незачем это прятать в отдельное окно, если места на экране пустого уйма — покажите мне сид сразу. А переключение скорости мне вообще непонятно. 2х-50х примерно на одинаковой скорости работают, только на 50 заметно больше кадров пропускает. На не самом слабом компе эти переключатели не имеют смысла из-за размеров поля. Дайте посмотреть на это на поле поменьше/побольше, на мой вкус. Мне интересно было бы глянуть на реальный х50, пусть и на поле 600х600.
2х-50х примерно на одинаковой скорости работают
А какой у Вас браузер? У меня в Хроме на скорости 2x — 120 итераций в секунду, на 50x — 220. В Edge и на мобильном телефоне на всех 1x-50x скорость одинаковая — примерно 17 итераций в секунду, но, думаю, это из-за движка яваскрипта.
Средствами браузера не очень удобно, так как пропадает доступность панели управления.
У меня например случайно создалась довольно крупная стабильная структура, хотелось рассмотреть вблизи и пошагово, оказалось не очень удобно. Спас пробел, который работает как шаг, за это спасибо.
Кстати интересно, а есть каталог стабильных структур?
А в машиночитаемом виде есть такой?
Или можно еще скачать программу Golly, в ней есть пара сотен шаблонов (в простом текстовом формате)
Можно еще избавиться от операции копирования из temp-буфера, сделав 2 буфера, и переключаться между ними поочередно
Пусть есть 2 одинаковых массива A и B.
Будем считать, что ссылка x означает предыдущую итерацию, а y — следующую.
Пусть вначале x указывает на A, а y на B.
На каждом шаге выполняем следующие действия:
- Зачитываем данные из x, пишем в y.
- Рендерим на экран содержимое y.
- Выполняем операцию swap(x, y)
Короче, подробности я конечно не вспомню, но поле 640х480 на 386 проце делалось около 50 итераций в секунду. Это я запомнил, т.к. на экране «светофоры» замирали в одном положении, либо горизонтальном, либо вертикальном, т.к. за время прохождения строчной развертки ЭЛТ монитора программа успевала пройти (как минимум) две итерации.
Забавно то, что уже тогда основной эффект был достигнут переносом вычислений в видеопамять.
Я тут прикинул на коленке, поле было меньше в 6.75 раз, процессор медленнее в 100 раз (4ГГц сегодняшних процессоров против 40 МГц на 386 в режиме турбо).
AdvancedLifeExtensions на таком поле выдал бы 2500х6.75=16875 итераций в секунду, но в переводе на MIPSы 1995 года — в 100 раз меньше, 169 итераций в секунду.
Алгоритм 1995 года выдавал 50 итераций в секунду.
За 25 лет улучшение в 3.375 раз (смайлик).
Прошу, не воспринимайте этот пост слишком уж серьезно. Это больше про башковитых парней из подмосковного наукограда. Их же там много было раз существовало внутреннее соревнование.
Мы с другом были фанатами программирования, что было несколько необычно для нашей почти сельской местности. Благо повезло — учились в экспериментальной гимназии и компьютеры у нас в гимназии были. Не 386-е, конечно (о них мы только в журналах читали), а Поиск-2, но на то время и они казались нам неверояными. Где-то в 1997-м завезли нам один 286-й, но за него никого кроме учителей не пускали.
Мы постоянно зависали после уроков в компьютерном классе и что-то писали. Расходились по домам со списком задач, которые необходимо решить и возвращались с листочками, исписанными программами, которые печатали и решали чей вариант решения лучше.
В общем участвовали в районной олимпиаде по программированию, где участников было ещё несколько человек помимо нас двоих. Была надежда попасть на областную олимпиаду.
В области наши работы завернули под предлогом, что нам помогали учителя. Видимо слишком выбивались работы из обычного районного уровня.
Обидно было.
Ну так а сейчас-то как? Пошли по пути программиста профессионально или нет?
Для диплома написал программу для вычисления кредитоспособности предприятия исходя из годовых отчётов.
По специальности не работал. Сразу компы год собирал, потом фотографом пару лет отработал. На обоих местах писал софт для автоматизации рабочих мест. Недавно был в фотосалоне — до сих пор ребята на старой винде сидят и древним фотошопом пользуются, потому что за 14 лет уже не представляют себе как без моего софта работать, а у меня исходники не сохранились, чтобы прикрутить к чему посвежее (там глубокая интеграция с фотошопом).
После фотосалона выстрелило моё резюме на программиста, перебрался в столицу, ну и 14 лет уже как программирую.
Друг, к сожалению, пошёл в другую сторону и сейчас обычным электриком на родине трудится, хотя программировал гениально и компьютерами фанател. Алгоритмы его, как правило, получались получше моих. Пару лет назад виделись, пытался ему на пальцах объяснить что такое ООП, но, то ли способностей учителя у меня нет, то ли он навыки растерял…
Но для меня программирование — это жизнь, постоянно что-то писал (и пишу), ежедневно, а у друга были невероятные способности ко всему, как говорят «не гумманитарному». Математика, информатика, физика, химия — всё подряд. А вот с гумманитарными предметами — наоборот. Из гимназии был отчислен за неуспеваемость по иностранному языку. И с дальнейшим обучением были проблемы того же рода.
Его способностями восхищались все преподаватели естественных дисциплин. Уверен — при должной мотивации он мог бы сказать своё слово в науке, но наше образование всегда всех под одну гребёнку гребло и гребёт. Не вписываешься в стандарты — гуляй, даже если человек — гений в чём-то отдельном. Разве что спортсменов и шоуменов-КВНщиков готовы вытаскивать по всем предметам ради престижа учебного заведения. А физмат мало кому интересен, если гениальность в отрыве от гумманитарных предметов.
К сожалению, код для обработки данных на видеокарте пока еще невозможно написать на .NET.
Хорошая попытка, Microsoft, но нет.
Есть ещё http://www.aleagpu.com/ с бесплатной лицензией под одну консьюмерскую карту
При всей нелюбви к электрону, так считать нельзя. Во-первых, далеко не каждое нативное приложение использует SIMD-инструкции. Во-вторых, далеко не каждое приложение является подобной "битодробилкой", а в других областях соотношение производительности может оказаться другим.
А я наоборот, увидел что js не так плох как его малюют. То есть даже в такой алгоритмичной задаче js быстрее половины вариантов. Без этой статьи я бы поставил что js на порядки медленнее любой реализации.
Джону Хортону Конвею, жизнь которого в возрасте 82 лет прервал короновирус в апреле 2020-го года, посвящается...
Многопоточность никак тут не заюзать?
Это не отменяет пользу от однопоточной оптимизации, но согласен, про многопоточность, наверно, следовало упомянуть.
Если живых клеток на поле мало, то этот подход даст огромный эффект — можно получить ускорение и в 100 и в 1000 раз. Но если живых клеток много, то время, потраченное на проход их соседей, да еще и не в cache-friendly порядке, может замедлить алгоритм в десятки раз.
Например, на поле 1920x1080 примерно два миллиона клеток, и алгоритм, сканирующий все поле, делает два миллиона итераций.
Для какого-нибудь глайдера, в котором не больше 10 точек, алгоритм со списком будет обрабабывать за итерацию 10 + 8*10 < 100 точек, то есть, будет быстрее в 20000 раз!
Но если в начальной конфигурации поля половина клеток живая, то алгоритм со списком будет делать 9 миллионов итераций, то есть, в 4.5 раза медленнее (на самом деле, еще медленней из-за cache misses). И это только в сравнении с неоптимизированным алгоритмом.
даже если живых клеток более половины (чего я на видео не видел) экономия всё равно должна получаться существенная.
Вы же предлагаете проверять всех соседей каждой живой клетки — а их аж 9. А поскольку чтобы проверить не проверили ли мы уже клетку, надо тоже потратить время — выигрыш по времени выходит только когда живых клеток менее где-то 1/9.
эта игра жизнь ВСЕГДА вырождается к сильно разреженной матрице живых клеток
Доказано, что плотность может превышать 50%
![image](https://habrastorage.org/webt/cq/ln/ik/cqlnik4uougbjtm7mxyozxjxsd8.png)
![image](https://habrastorage.org/webt/7g/kx/ex/7gkxexrr9dj1jlzyo2pgsq53azc.png)
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
P.S. Для меня это стало большой неожиданностью, что создатель этой игры и великий математик Джон Конвей умер в этом году.
Так как такие функция будут чистыми, то это позволяет очень просто распараллеливать вычисления на любое количество потоков, включая также GPU
Интересно, как? У вас есть функция, которая принимает на вход все живые клетки и выдаёт новые живые клетки. Функция внутри особо не паралелится, а снаружи для запуска следующей итерации нужно закончить вычисление предыдущей.
А что такое "фигура"? Если между двумя фигурами есть промежуток в 1 пиксель — они считаются одной фигурой? Что если две фигуры влияют на один пиксель (растут)?
Сомнительный выигрыш, короче.
И потому что нет изменяемого состояния (например, как с копированием массива temp в тексте)
И что? Темп-массив можно заполнять параллельно по рядам, к примеру. Заполнение одного ряда никак не влияет на заполнение другого.
Примерно так и работает алгоритм Hashlife, который может работать в тысячи и миллионы раз быстрее, его придумал американский програмист Bill Gosper в 1983 году. Мне не удалось достать его оригинальную статью, так что не ручаюсь за достоверность, но я слышал, что его оригинальная версия была написана на лиспе.
причем крайние клетки всегда мертвые.
Извиняюсь, возможно я что-то упустил, но разве граничные клетки не сшиваются с противоположными краями, замыкая всю игровую поверхность?
В оригинале игра идёт на бесконечном поле. Но, так как память компьютера ограничена — то поле тоже ограничивается. А какую ему при этом дать топологию, прямоугольника или тора — это уже деталь реализации. В обоих случаях в симуляции возможны эффекты, которые на бесконечном поле невозможны.
копируем массив temp в исходный массив.
И вот здесь я перестал читать и просто проскролил до конца.
Ну, я вообще-то не очень умный. И соответственно часто поступаю не умно. Например, пишу все на ассемблере. И не копирую массив temp в исходный массив никогда. И кстати, поискал и оказывается, у меня в исходниках (500kloc) нет ни одной переменной, массив или просто этикетку с имени "temp". Мне стыдно, но что поделать… (но есть "template" — это считается?)
Ну-у-у, если и там копировали temp, то вполне нормально… Вообще, компилируемый язык и хороший компилятор не делают автоматически код быстрым. И писать действительно быстрый код на C++, совершенно нетривиальный процесс. (кстати, написать то же самое в плане оптимизации на ассемблере намного легче) Посмотрите как выглядит какая нибудь хорошо оптимизированная библиотека на C++.
/* 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++)
При обходе двумерного массива, внутренний цикл всегда должен быть по строке, а не столбцу. Так намного быстрее, особенно когда данные не влезают в кеш-память.
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 году. ))
И это мы делаем «в лоб»! Добавить оптимизаций и можно получить «плавающий фпс» хоть до +100KFPS в FullHD!(шучу немного)
Кнш… 50GB\s вы получить наврядли сможете, а вот 10GB\s вполне можно развести «недорого».
ЗЫ — Даже на SDRAM с дёшевеньких плат, на каких-нить циклонах4 с 22KLE, можно без оптимизаций ~40фпс выжать в FullHD.
Два вопроса по этому поводу (чисто теоретических):
1) Нашел в гугле, что есть FPGA Virtex-7 2000T с двумя миллионами ячеек; в нем можно сделать симуляцию игры не в памяти, а напрямую в этих ячейках? Или топология не позволяет?
2) Может быть, можно сделать специализированную микросхему с двумя мегабайтами SRAM, и к каждой ячейке прикрутить трехбитный сумматор? Тогда теоретически можно добиться по одной итерации на такт?
Я не сильный спец по 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
Вообще интересно, чего можно достичь на разных технологиях за разные деньги. Я по сумме всех комментариев понял примерно так (плюс-минус порядок):
— процессор ($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
Если последний шаг с AVX накатить на последнюю версию, где по 2 клетки на байт, разве не будет ускорения еще в 2 раза?
Тут есть техническая проблема: в AVX невозможно сдвинуть на 4 бита весь регистр как одно 256-разрядное число, минимум нужно делать два сдвига и одно сложение, так что ускорение будет немного меньше, чем в два раза, и код сильно усложняется, но выигрыш в скорости все равно получается существенный.
Вкупе с еще одной идеей: избавиться от временного буффера вообще, и хранить дополнительно только три линии поля (текущую, выше, и ниже) получается суммарно ускорение в 330 раз от начальной версии, от 25 до 7400 шагов в секунду!
Можно код посмотреть на гитхабе: AdvancedLifeExtensionsInLineCompressed.cs.
Ваша дополнительная идея очень хорошая. Ее можно слегка оптимизировать. Не уверен, что это сильно поможет. Когда Вы хотите произвести вычисления для некоторого элемента в середине поля, Вам необходимо знать предущую линию (под нее выделить память), в текущей линии предыдущий элемент, текущий и следующий (под них можно выделить 3 локальных переменных) и следующая линия (которая и так есть в исходном массиве, так как Вы еще не успели начать ее «портить»).
Тогда кешируется куски не 4 массивов, а лишь 3.
Но это, скорее оптимизация по памяти, чем по времени.
Есть такая замечательная инструкция VPSHUFB (_mm256_shuffle_epi8, Avx2.Shuffle), которая может использоваться в качестве lookup таблицы из 16 одно байтовых значений.
Этой операцией можно заменить почти все битовые операции во втором цикле.
Правда, ускорение, по моим подсчетам, получилось не очень большое, около 5%.
P.S. мой ник с 2005 года, Intel разработала эти инструкции в 2008 году, так что я не причём ))
Как ускорить игру «Жизнь» в сто раз