All streams
Search
Write a publication
Pull to refresh
41
Karma
0
Global rating
Oleg T@lightln2

программист

Send message
ProfileArticles5PostsNewsComments133
Тетрис на битбордах: старые песни на новый лад
Вы имеете в виду, фигура, как на КПДВ? Вообще-то это твердый знак (ну, по крайней мере задумывался).
Нету смысла искать оптимальную стратегию в обычном тетрисе — известно, что он проходится до момента, пока не встретится какое-то количество z- и s- фигурок в определенной последовательности. Вот я и добавил фигурку, которая все «портит», чтобы вручную его тоже было сложно пройти — я, например, дальше компьютера не смог.
This comment wasn’t rated yet0
Look
Как ускорить игру «Жизнь» в сто раз
Спасибо! Было бы интересно, чего можно достичь на не-топовых FPGA.
Вообще интересно, чего можно достичь на разных технологиях за разные деньги. Я по сумме всех комментариев понял примерно так (плюс-минус порядок):
— процессор ($1'000) — 50'000 итераций в секунду
— видеокарта ($1'500) — 500'000 итераций в секунду
— FPGA ($15'000) — 50 миллионов итераций в секунду
— ASIC ($1'500'000) — 1 миллиард итераций в секунду
This comment wasn’t rated yet0
Look
Как ускорить игру «Жизнь» в сто раз
А это чисто физически можно сделать на двумерной схеме? Ведь у каждой клетки будет свой сумматор, и надо будет к нему тянуть линию от всех восьми ее соседей.
This comment wasn’t rated yet0
Look
Как ускорить игру «Жизнь» в сто раз
Круто! Получается, скорость будет ограничена только пропускной способностью канала памяти? После Вашего комментария полез искать, пользуются ли FPGA для ресёрча, и нашел, что пользуются, но, похоже, это единичные случаи.
Два вопроса по этому поводу (чисто теоретических):
1) Нашел в гугле, что есть FPGA Virtex-7 2000T с двумя миллионами ячеек; в нем можно сделать симуляцию игры не в памяти, а напрямую в этих ячейках? Или топология не позволяет?
2) Может быть, можно сделать специализированную микросхему с двумя мегабайтами SRAM, и к каждой ячейке прикрутить трехбитный сумматор? Тогда теоретически можно добиться по одной итерации на такт?
This comment wasn’t rated yet0
Look
Как ускорить игру «Жизнь» в сто раз
Ваш комментарий верен в общем случае, но при обходе двумерного массива внутренний цикл должен быть по второму индексу, так что в данном случае этот порядок правильный, можете поменять местами и проверить. Тут скорее проблема в том, что массив определялся как new bool[WIDTH, HEIGHT], хотя надо было бы длину и ширину поменять местами.
Total votes 1: ↑1 and ↓0+1
Look
Как ускорить игру «Жизнь» в сто раз
не копирую массив 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);
This comment wasn’t rated yet0
Look
Почему «angina» — это не «ангина», а «resin» — не «резина», или Ложные друзья переводчика
Мой любимый пример такого рода — электронная виза в Мексику. Вот оригинал:
image

А вот — русский вариант:
image
Насколько я понимаю, ministro de culto — это религиозный деятель, а министр культуры будет ministro de cultura. Этому переводу, кстати, уже лет 10, удивительно, что его так и не исправили, можете по ссылке сходить, посмотреть.
Total votes 3: ↑3 and ↓0+3
Look
Как ускорить игру «Жизнь» в сто раз
Если Вы имеете в виду наложение кода на картинку, то не фотошопом: я использовал paint.net, сгенерировал пять картинок, и воспользовался одним из онлайн-генераторов анимированных gif.
This comment wasn’t rated yet0
Look
Как ускорить игру «Жизнь» в сто раз
Я провел такой эксперимент, ускорение получилось в 3.5 раза для рандомной начальной конфигурации (но, конечно, для маленьких и статичных конфигураций ускорение может быть в сотни и тысячи раз)
Обсуждение и код в этой ветке. Может быть, кто-то сможет еще больше ускорить.
Я прошу прощения, нам с самого начала надо было вести обсуждение под Вашим комментарием (теперь, наверно, не перенести).
Total votes 1: ↑1 and ↓0+1
Look
Как ускорить игру «Жизнь» в сто раз
в программе Golly, взял статическую картинку из четырех точек и копипейстом размножил по форме букв: image
Total votes 1: ↑1 and ↓0+1
Look
Как ускорить игру «Жизнь» в сто раз
Последовал Вашему совету и полез в мой любимый 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

...
This comment wasn’t rated yet0
Look
Как ускорить игру «Жизнь» в сто раз
Проверил на коленке Вашу идею:
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
This comment wasn’t rated yet0
Look
Как ускорить игру «Жизнь» в сто раз
Кстати, насчет ассемблера: у меня изначально была реализация на C++ через интринсики, но она работала с абсолютно такой же скоростью, что и версия на C#. Я не ожидал, что JIT сможет скомпилировать такой же хороший код, что и C++
This comment wasn’t rated yet0
Look
Как ускорить игру «Жизнь» в сто раз
я видел ее. Мне кажется, или его результат только примерно совпадает с классическими правилами?
This comment wasn’t rated yet0
Look
Как ускорить игру «Жизнь» в сто раз
Из осциллятора, который получил QDeathNick, можно составить нестатическую фигуру, если я не ошибся в подсчетах, 32% плотности:
image
Total votes 1: ↑1 and ↓0+1
Look
Как ускорить игру «Жизнь» в сто раз
Сейчас проверил, переключение буфера вместо копирования дает ускорение примерно в 1.15 раз (на 13%)
Total votes 1: ↑1 and ↓0+1
Look
Как ускорить игру «Жизнь» в сто раз
наверняка есть, так как есть глобальная база, в которую все исследователи кладут «интересные» шаблоны (найденные брутфорсом на GPU).
Или можно еще скачать программу Golly, в ней есть пара сотен шаблонов (в простом текстовом формате)
This comment wasn’t rated yet0
Look
Как ускорить игру «Жизнь» в сто раз
эта игра жизнь ВСЕГДА вырождается к сильно разреженной матрице живых клеток

Доказано, что плотность может превышать 50%
This comment wasn’t rated yet0
Look
Как ускорить игру «Жизнь» в сто раз
Вот, например, неплохое объснение Hashlife, там очень похоже на то, как Вы описываете.
This comment wasn’t rated yet0
Look
Как ускорить игру «Жизнь» в сто раз
Вот, например: List_of_common_still_lifes
Total votes 1: ↑1 and ↓0+1
Look
1234
5
67

Information

Rating
6,717-th
Registered
Activity

Your account

Sections

Information

Services

Support
© 2006–2025, Habr