저전력에 대한 상태 인코딩

상태 인코딩은 유한 상태 기계(FSM)의 각 정의된 상태에 각각 1과 0의 고유한 패턴을 할당한다. 전통적으로 FSM 합성을 위한 설계 기준은 속도, 면적 또는 둘 다였다.무어의 법칙에 따라 기술 발전으로 집적회로의 밀도와 속도는 기하급수적으로 증가했다.이와 함께 영역당 전력 소산이 증가할 수밖에 없어 휴대용 컴퓨터 장치 및 고속 프로세서 설계자가 설계 고려 중 전력 소산을 중요한 파라미터로 고려할 수밖에 없게 되었다.^[1][2]

배경

FSM의 합성에는 세 가지 주요 단계가 포함된다.

1. 상태 최소화:이름에서 알 수 있듯이, FSM을 나타내기 위해 필요한 상태 수는 최소화된다.시사표, 행 일치 및 연속 분할 알고리즘과 같은 다양한 기법과 알고리즘은 동등하거나 중복된 상태를 식별하고 제거한다.
2. 상태 할당 또는 인코딩은 FSM의 내부 상태에 대한 부울 표현을 선택하는 것을 포함한다.즉, 각 주에 고유한 이진코드를 할당한다.올바른 인코딩 기법의 선택은 매우 중요하다.잘못된 결정은 너무 많은 논리 영역을 사용하거나, 너무 느리거나, 너무 많은 전력을 소비하거나, 또는 이것들의 어떤 조합도 초래하는 FSM을 초래할 수 있기 때문이다.
3. 결합 논리 최소화는 결합 논리를 줄이기 위해 할당되지 않은 상태 코드를 관리하지 않음으로 사용한다.

기존 인코딩 기술

상태 인코딩에 널리 사용되는 몇 가지 기술은 다음과 같다.

• 하나의 핫 인코딩에서 상태 변수의 비트 중 하나만 지정된 상태에 대해 "1" (hot)이다.다른 모든 비트는 "0"이다.이 기법의 해밍 거리는 2이다.한 번의 핫은 FSM의 모든 주에 대해 하나의 플립플롭을 필요로 한다.그 결과, 상태 기계는 이미 「디코딩」되어 있어, 어떤 플립플롭이 활성화되어 있는가를 알아내는 것만으로 기계의 상태가 결정된다.이 인코딩 기법은 결합 로직의 폭을 줄이고 그 결과 상태 기계는 레지스터 간 로직 수준을 적게 요구하여 복잡성을 줄이고 속도를 높인다.
• 이진 인코딩에서 상태당 비트 수(b)는 상태 수(n)에 따라 달라진다.관계는 다음 방정식으로 정의된다.

b = log2(n)

이 기법에서 상태는 이진수 0 이상부터 번호가 매겨지는 이진수 순서로 할당된다.분명히 사용되는 플립플롭의 수는 비트(b)와 동일하다.바이너리 인코딩은 기계를 인코딩하기 위해 최소 비트 수(플립 플롭스)를 사용하기 때문에 플립 플롭스는 최대한 활용된다.그 결과, One Hot에 비해 각 상태를 디코딩하는 데 더 많은 조합 논리가 필요하다.One hot에 비해 슬리핑 플롭이 적게 필요하지만 해밍 거리는 비트 수(b)만큼 심각할 수 있다.

• 회색 인코딩

반사된 이진 코드로도 알려진 회색 코드에서는 연속된 상태 코드가 1비트만 차이 나는 상태가 할당된다.또한 이 인코딩에서 비트 수와 상태 수 사이의 관계는 다음과 같이 정의된다.

b = log2(n)

사용된 플립 플롭의 수와 디코딩 로직의 복잡성은 이진 인코딩과 동일하다.그러나 회색 코드의 해밍 거리는 항상 1이다.

• 기타 인코딩 기술

출력 기반 인코딩, MUSTAG,^[3] NOVA,^[4]

동기

저전력을 위한 상태 인코딩 설계의 주요 아이디어는 가장 가능성이 높은 상태 전환의 해밍 거리를 최소화하여 전환 활동을 줄이는 것이다.따라서 전력 소비량을 최소화하기 위한 비용 모델은 최소 가중 해밍 거리(MWHD)를 갖는 것이다.^[1][2]

카운터의 경우 그레이 코딩은 최소 스위칭 활동을 제공하므로 저전력 설계에 적합하다.상태 변경이 순차적일 때 회색 인코딩이 가장 적합하다.임의 상태 변경 시 저전력 설계에 대한 FSM 회색 코드가 실패함그러한 FSM의 경우, 단일 핫 인코딩은 모든 상태 변경에 대해 2비트의 전환을 보장한다.그러나 필요한 상태 변수의 수는 상태 수와 같기 때문에 상태가 증가함에 따라 1-hot 인코딩은 비실용적인 해결책이 되는데, 주로 회로에 대한 입력과 출력의 수가 증가하여 복잡성과 용량성 부하가 증가하기 때문이다.최대 해밍 거리가 상태 변수의 수와 같기 때문에 이진 코딩은 저전력에 대해 최악이다.

임의 상태 변경 FSM에 대한 해결책이 필요하게 되면서 상태 전환 중 전환 활동을 줄이는 데 초점을 맞춘 여러 상태 인코딩 기법이 생겨났다.

기술

저전력 상태 할당을 위한 칼럼 기반 접근 방식

^[5] 이 접근방식은 상태 전환 간 전환 활동을 최소화하는 상태 할당을 선택하여 순차적 회로에 의한 전력 소산을 줄이는 것을 목표로 한다.따라서 FSM의 결합 부분은 입력 전환 확률이 낮으며 합성 시 낮은 전력 소산에 가깝다.이 알고리즘은 상태 코드에 해당하는 행과 상태 변수에 해당하는 열이 있는 부울 행렬을 사용한다.단일 상태 변수는 한 번에 고려되며 전체 할당을 위한 전환 활동을 최소화할 수 있는 방식으로 FSM의 각 상태에 값을 할당하려고 시도한다.이 절차는 다음 변수에 대해 반복된다.최소화 기법이 칼럼별로 적용되기 때문에 이 기법을 Column based라고 부른다.

다중 코드 상태 할당

다중 코드 상태 할당 기법은 중복 상태를 억제하여 우선 순위 인코딩을 구현한다.따라서 적은 수의 상태 변수(비트)를 사용하여 상태를 인코딩할 수 있다.또한, 누락된 상태 변수에 해당하는 플립플롭은 클럭 게이팅이 가능하다.^[6]

프로파일링 기반 상태 할당

^[7] 이 기법은 FSM 프로파일링 데이터에서 추출한 동적 루프 정보를 순차적으로 활용하여 전환 활동을 줄인다.이 기술이 사용하는 단계는 다음과 같다.

1. FSM 상태 프로파일링은 관련 입력 데이터 세트에 대한 FSM의 동적 거동에 대한 정보를 수집한다.
2. 루프 검출은 상태 추적에서 루프를 검색하고 각 루프는 저장 및 계수되어 루프의 주파수를 얻는다.
3. 상태 할당은 전환 활동을 최소화하기 위해 처음 두 단계에서 수집된 데이터를 기반으로 각 상태에 상태 변수를 할당한다.상태 변수를 할당하는 알고리즘은 세 가지가 있으며

• 기본 DFS 상태 할당 알고리즘
• 루프 기반 DFS 상태 할당 알고리즘
• 루프 기반 상태별 경험적 상태 할당 알고리즘

기타 기법

• 일부 기술은 낮은 전력을^[8][9] 대상으로 하는 2-레벨 및 다-레벨 구현을 생성하기 위해 상태 전환 그래프(STG)를 인코딩한다.
• 전력 최적화를 위한 기존 로직 레벨 순차 회로의 재인코딩이 제안되었다.
• 스패닝 트리 기반 상태 인코딩,^[11] Depth_First Method,^[12][12] 최소 거리 Method, 1_Level_tree Method,^[12][12] 여기서 다시 상태 전환으로 인한 스위칭 활동이 감소되는 등의 다른 상태에 상태 변수를 할당하는 데 초점을 맞춘다.
• 저전력에 대한 단순한 암호화 상태를 제외하고, 일부 기법은 FSM을 두 개 이상의 하위 기계로 분해하는 것을 포함하며, 이 중 한 기법만 대부분 활성화된다.이를 이용하여 다른 하위 기계는 클럭 게이트^[13] 또는 전력 게이트가 가능하다.^[14]

참고 항목

• 버스 인코딩
• DFA 최소화
• 논리합성
• 저전력 전자제품
• 등록-이송수준

참조