コンウェイのライフ ゲームを実装するための高速でメモリ効率の高い方法を探しています。
制約: 96x128 ボード、利用可能な約 2kB の RAM、および 52MHz のプロセッサ (技術仕様はこちら: http://www.getinpulse.com/featuresを参照)。
各セルをマトリックス (96*128/8=1,536 バイト) の単一ビットとして表す現在の素朴なソリューションは機能しますが、遅すぎます。パフォーマンスを向上させるために使用できるトリックは何ですか?
生きているセルの座標を保存すると (たとえば、この実装ではhttp://dotat.at/prog/life/life.html )、メモリが大量に使用されます。
楽しいハードウェアのように見えます。96x128 ピクセル ディスプレイのピクセルあたり 1 ビットを格納すると、12,288 ビットになります。これは、「利用可能」であるとあなたが言う 16,384 ビットの半分以上です。セルごとに 2 ビットを格納することさえできない場合、多くのことを行う余地はあまりありません。
いくつかのアイデア:
32 ビット プロセッサを使用しています。ビットマップを取得し、そのようなプロセッサで複数のセルの隣接セルの数を並行して計算するには、ビットをいじるトリックがいくつかあります。
多くの場合、世代ごとにゼロから近隣の数を再計算するよりも、誕生時に 8 つの近隣すべてをインクリメントし、死亡時に 8 つの近隣すべてをデクリメントして、近隣の数を保存する方が高速ですが、このアプローチには十分なメモリがないようです。 .
おそらく、セルあたり 2x2 ピクセル (3,072 個のセルのみが表示される) またはセルあたり 3x3 ピクセル (1,376 個のセルのみが表示される) を使用すると、ソフトウェアの作業が少なくなり、より高速に実行されているように見えます。(これにより、上記の隣接カウントを実行できる十分な RAM も解放されます)。
多くの生活パターンにはデッド スペースの大きな領域があるため、おそらく「ライブ領域」の小さなビットマップがあります。たとえば、12x16 のビット配列で、対応する 8x8 セル領域が完全に死んでいる場合、各ビットは「0」であり、「 1" 対応する領域内のいずれかのセルが生きている場合。次世代の更新では、ライブ リージョンとデッド リージョンの 1 セル幅の境界のみを確認する必要があります。デッド リージョンの 6x6 セル コアのチェックをスキップできます。また、最も近い 4 つの隣接する領域も死んでいる場合は、8x8 セル領域全体を完全にスキップできます。
多くの生活パターンには、静的で不変の「静物」パターンの大きな領域があるため、おそらく「動的領域」の小さなビットマップがあります。たとえば、12x16 のビット配列で、対応する 8x8 セル領域が最後の世代の更新では変更がなく、対応する領域内のセルのいずれかが最後の更新で変更された場合は「1」。次世代の更新では、動的領域と静的領域の 1 セル幅の境界のみを確認する必要があります。次世代でも同じであるため、静的領域の 6x6 セル コアのチェックをスキップできます。
パターンが「十分に大きい」場合、Gosper の Hashlife に基づく表現は、ビットマップを直接格納するよりも少ない RAM に格納できる場合があります。残念ながら、「十分な大きさ」のしきい値をはるかに下回っていると思います。
小さな生命の宇宙では、すべての側面を包み込むようにする (トロイダル宇宙を作る) のはよくあることですが、これにはダブル バッファリングが必要です。あなたの場合、これには 3KB の RAM が必要ですが、2KB しかありません。
ラップしない場合は、ユニバース全体をダブルバッファリングする必要はありません。計算への入力としてセルを使用し終える前に、セルを上書きしないようにする必要があります。
ユニバースが従来のビットマップとしてレイアウトされているとします。一連の行がメモリ内で順番に配置されるものとして扱います。ユニバースに 0 から 3 までの番号が付けられた 4 つの行があるとします。
0
1
2
3
4
...
次の世代を計算すると、行 3 の新しいバージョンは、行 2、3、および 4 (空白) を使用して計算されます。行 4 の上に行 3 の新しいバージョンを書き込むことができます。同様に、行 1、2、3 から新しい行 2 を計算し、それを行 3 の上に書き込みます。これは、行 2 の計算後にそのデータが不要になるためです。新しい行 1 は、行 0、1、2 から計算され、行 2 に上書きされます。
これは、追加の 1 行分のメモリのみが必要であることを意味します。97*128 ビットは 1552 バイトです。
欠点は、ユニバースがメモリをスクロールすることであり、これに対処するための何らかのメカニズムが必要です。計算のたびに元の位置にコピーするか (これは遅い)、メモリ内の任意の位置から表示できるようにして、計算システムと表示システムが上位アドレスから下位アドレスにラップアラウンドできるようにします。
Michael Abrash 著「The Zen of Code Optimization」のライフ ゲームの章を見てください。3 つのセルの現在と以前の状態を 1 つのワードにコード化し、ルックアップ テーブルとキャリー ビットを使用して次の状態を生成する実装がありました。爆速でした。
ボードの行を読み取り、H と L の 2 つの新しい行バッファーを生成するルーチンから始めることをお勧めします。 n-1) が元の行に設定され、(ビン n+1、ビット n、ビット n-1) の奇数が元の行に設定された場合、L のビット 'n' が設定されます。
合計 3 組の行バッファーを割り当てます (それらを H0..H2 および L0..L2 と呼びます)。ソース ファイルの各行を取得し、バッファーのペアを計算して HL ペアに格納し、それと前の 2 つを保持します。6 つのバッファすべてから単語を調べると、元のマトリックスの 32 個のセルのうち、以前にあった場合にのみライブにする必要があるセルと、以前の状態に関係なくアクティブにする必要があるセルが明らかになります。
マシン コードで最適なパフォーマンスを得るには、3 組のバッファーをインターリーブすることができます。これにより、1 ピクセルあたり 2 サイクル未満の実行速度を達成できる可能性があります。おそらく 52MHz ではやり過ぎかもしれませんが (12288 ピクセルしかないため、フレーム レートは ~4000fps になります)、速度はクールです。
ビット配列に固執し、このトリックでネイバーカウントをスキップします。ライブセルを作成または維持するネイバーセルブロックの可能なビットパターンを使用してルックアップテーブルを作成します。
メモリを最小限に抑えたい場合は、「インデックス」パターンを8ビットにパックできます。上の行から3ビット、列から両側に2ビット、下の行から3ビットです。ルックアップテーブルの単一ビットとして出力をエンコードし、合計で256ビットのみを使用できます。ルックアップ配列のビットシフトカウントとしてインデックスを使用して、結果を「計算」します。ビットシフトと算術OR演算は依然として非常に高速であり、この手法により、隣接する生細胞をその場でカウントする必要がなくなります。つまり、ルックアップテーブルがカウントと計算を前処理します。
処理のボトルネックの上位は次のとおりです。ボードのエッジの状態、つまり行の終わりをチェックします。単語の境界; 隣接ビットをインデックス値として抽出してパックします。32ビットプロセッサを使用すると、単語の境界に達する前に30個のセルを非常にすばやく循環できるはずです。セル行のアドレス指定は、ビットをワードサイズのintにパックする場合、列数/32を追加するだけの問題である可能性があります。結果を2つの予備のnew-life行にキャッシュし、1つを処理し終えたら、行全体をコピーします。
物事をさらに最適化するために利用できるパターンの対称性があるかもしれませんが、これで十分かもしれません。この手法により、処理とメモリ使用量が制限内に収まると思います。
デバイス（フラッシュメモリ）の残りの30KBを悪用するライセンスを持っている場合は、いつでもそこに保存できますが、理想的ではありませんが、限られたRAMを回避できる可能性があります。
効率的に言えば、CPUとメモリのパフォーマンスを相互に交換することになります。
メモリ効率については、ビット配列が最適なソリューションである可能性がありますが、そのグリッドを反復処理するとCPU効率が低下します。
機能とメモリアドレスのサイズに応じて、セルのリンクリストを使用して、グリッド全体の反復を回避できます。これにより、デッドセルの巨大な領域をスキャンする時間を確実に節約できます。