Conway의 생명 게임으로 알아보는 올바른 FPGA 인코딩 선택: 실습 연구

FPGA 설계에 가장 적합한 인코딩을 선택하는 방법을 보여주는 세 가지 실험을 따라가봅니다.

FPGA 로직을 설계할 때 합성 도구가 일반적으로 인코딩을 선택하며, 그 결정을 신뢰하는 것이 일반적으로 최선입니다. 그러나 이진, 그레이, 원-핫 표현의 뉘앙스를 이해하면 컴파일러가 언제 하나를 다른 것들보다 선호할지 예측하는 데 도움이 될 수 있습니다.

이 기사는 Conway의 생명 게임을 테스트벤치로 사용하는 실용적인 실험을 통해, 유한 상태 머신의 대규모 배열에 각 인코딩을 적용할 때 나타나는 트레이드오프를 강조합니다.

이 시리즈에서는 Verilog에서의 FSM 구축, 초기 상태와 메모리가 인코딩에 미치는 영향, 이진, 원-핫, 그레이 방식의 고수준 비교를 다루었습니다.

테스트 대상 시스템

하드웨어 차이를 확대하기 위해, 23×23 그리드에 걸쳐 상태 머신을 수십 번 인스턴스화하여 이진, 그레이, 원-핫 인코딩을 직접 비교했습니다.

Conway의 생명 게임은 직사각형 2D 격자에서 세포의 탄생, 생존, 죽음을 모델링하는 고전적인 셀룰러 오토마톤입니다. 각 세포는 매 사이클마다 세 가지 간단한 규칙을 따릅니다:

1. 살아있는 이웃이 2개 또는 3개인 살아있는 세포는 생존합니다.
2. 살아있는 이웃이 3개인 죽은 세포는 살아납니다.
3. 그 외 모든 세포는 죽거나 죽은 상태로 유지됩니다.

이 규칙들은 풍부한 창발 패턴을 생성하며, 인코딩 전략을 평가하기 위한 깔끔하고 잘 이해된 워크로드를 제공합니다.

아래는 Conway의 생명 게임에서 인기 있는 패턴인 Bill Gosper의 글라이더 건의 GIF입니다.

Conway의 생명 게임 변형인 Bill Gosper의 글라이더 건. Gif 제작: Lucas Vieira [CC BY‑SA 3.0]

Verilog 코드

세포 로직은 8-상태 FSM으로 모델링됩니다. 생명 게임의 세포당 계산은 단일 사이클에 완료되지만, 8-상태 설계는 인코딩 간의 눈에 띄는 차이를 만듭니다. 다음 Verilog 모듈은 원래 이진 인코딩을 보여줍니다.

`define STATE_0 3'b000 `define STATE_1 3'b001 `define STATE_2 3'b010 `define STATE_3 3'b011 `define STATE_4 3'b100 `define STATE_5 3'b101 `define STATE_6 3'b110 `define STATE_7 3'b111

module LifeCell( input clk, input nrst, input seed, input [7:0] neighbors, output reg alive); reg [2:0] state; always @ (posedge clk) if (nrst == 0) state <= `STATE_0; else case(state) `STATE_0: begin // ... state <= `STATE_1; end `STATE_1: begin // ... state <= `STATE_2; end // ... `STATE_7: begin // ... state <= `STATE_1; end endcase endmodule

코드에 대해 더 깊이 알고 싶다면, 전체 프로젝트는 GitHub에서 확인할 수 있습니다.

FPGA 인코딩 구현

설계는 23×23 세포 그리드에서 합성되었으며, 그 결과 27개의 구별되는 구현이 나왔습니다: 세 가지 FSM 변형, 각각 이진, 그레이, 원-핫 인코딩으로 컴파일, 세 가지 타겟 FPGA 전반에 걸쳐.

FSM #1: 원래 모델

이 FSM은 초기 상태를 한 번 실행한 후 나머지 7개 상태를 순환합니다. 이 시퀀스는 그레이 인코딩이 유리할 수 있음을 시사했습니다.

FSM #2: 시퀀스

단순한 3비트 카운터 역할을 하는 이 FSM은 그레이 인코딩이 우세할 것이라는 기대를 더욱 강화했습니다.

FSM #3: 임의의 얽힘

이 변형은 FSM #1의 크리티컬 경로를 공유하지만 이웃 수가 3을 초과하면 비선형 경로를 취합니다. 원-핫 인코딩이 이러한 불규칙한 전이에 자연스러운 선택처럼 보였습니다.

타겟 아키텍처

구현은 다음 장치에 대한 벤더 툴체인으로 빌드되었습니다:

• Artix-7 FPGA용 Xilinx Vivado Suite
• Cyclone-V FPGA용 Intel Quartus Prime
• LatticeXP2 FPGA용 Lattice Diamond

결과 비교

FPGA 설계 벤치마킹은 본질적으로 메트릭 주도입니다. 로직 리소스 사용량, 레지스터 수, 예상 최대 주파수, 온칩 전력이라는 네 가지 핵심 지표를 선택하고 각각에 가중치 점수를 할당했습니다. 각 메트릭에서 최고 성능자는 +1(가중치 메트릭은 +2), 최악은 -1(가중치 메트릭은 -2), 중간은 0을 받았습니다.

• 로직 유닛: LUT (Xilinx/Lattice) 또는 ALM (Intel). 가중치 1.
• 레지스터: 가중치 1.
• 최대 주파수: 가중치 2.
• 온칩 전력: 가중치 2.

모든 27개 구현에 대한 누적 점수는 아래와 같습니다.

모든 27개 구현에 대한 결과 표. 녹색은 최적 인코딩, 빨간색은 최악, 노란색은 중간(동점 없음)을 강조.

전반적으로 원-핫 인코딩은 하위 두 행에 나타나며, 다른 방식과의 동률은 단 두 사례에 불과합니다. 대조적으로, 주파수와 전력이 더 높은 가중치를 가질 때 그레이 인코딩이 일관되게 최상위 성능자로 부상합니다.

승자를 강조하기 위해, 아래 표는 각 변형에 대한 선두 인코딩을 분리합니다.

결론

데이터는 이 특정 생명 게임 워크로드에 대해 그레이 인코딩을 선호하지만, 결과는 어떤 메트릭을 우선시하느냐에 달려 있습니다. 리소스 사용량을 성능보다 중시한다면 다른 순위가 나타날 수 있습니다. 제 목표는 만능 규칙을 처방하는 것이 아니라, 경험적 증거가 어떻게 인코딩 선택을 안내할 수 있는지 보여주는 것입니다.

소스 코드, 27개 합성 구현, 프로젝트 GitHub 저장소의 라이브 생명 게임 시뮬레이션을 자유롭게 탐색해 보세요.