술어(컴퓨터 아키텍처)

Predication (computer architecture)
분기 예측과 혼동하지 마십시오.

컴퓨터 과학에서 포식술은 조건부 분기 기계 지침에 의해 구현된 제어의 조건부 이전에 대한 대안을 제공하는 구조적 기능이다.포기는 명령어가 아키텍처 상태를 수정할 수 있는지 여부를 제어하기 위해 명령에서 사용하는 부울 값인 술어와 연관된 조건부(predated) 비지점 명령을 갖는 것으로 작동한다.만약 지시서에 명시된 술어가 참이라면, 그 명령은 건축 상태를 수정하고, 그렇지 않으면 건축 상태는 변하지 않는다.예를 들어, 사전 설정된 이동 명령(조건부 이동)은 술어가 참인 경우에만 목적지를 수정한다.따라서 분기 발생 여부를 제어하는 술어에 근거하여 명령이나 실행 지침의 순서를 선택하기 위해 조건부 분기를 사용하는 대신, 실행할 명령어는 그 술어와 연관되어 있기 때문에 그 술어가 참인지 거짓인지에 근거하여 실행되거나 실행되지 않는다.[1]

벡터 프로세서, 일부 SIMD ISA(AVX2 및 AVX-512와 같은) 및 GPU는 일반적으로 포식법을 많이 사용하며, 처리 중인 벡터 레지스터의 해당 요소에 조건부 마스크 Vector의 1비트를 적용하지만 스칼라 명령 집합의 스칼라 포식은 하나의 술어 비트만 필요하다.술어 마스크가 벡터 프로세싱에서 특히 강력해지는 경우, 벡터 요소당 한 개씩의 상태 코드 배열이 이후 벡터 지침에 적용되는 술어 마스크로 다시 공급될 수 있는 것이다.

개요

대부분의 컴퓨터 프로그램에는 조건부 코드가 포함되어 있는데, 예를 들어 사용자 입력에 따라 사전에 결정할 수 없는 요인에 따라서만 특정 조건에서만 실행된다.대다수의 프로세서가 단순히 다음 명령을 순차적으로 실행하기 때문에, 전통적인 해결책은 프로그램이 조건부로 코드의 다른 섹션으로 분기할 수 있도록 하는 분기 명령을 삽입하여, 따라서 순서의 다음 단계를 변경하는 것이다.이는 설계자들이 나뭇가지에 의해 느려지는 방법인 지시 파이프라이닝을 구현하여 성능을 향상시키기 전까지는 충분했다.발생한 문제와 인기 있는 솔루션에 대한 자세한 설명은 분기 예측 변수를 참조하십시오.

다행히도, 일반적으로 분기에 의존하는 더 흔한 코드 패턴 중 하나는 더 우아한 해결책을 가지고 있다.다음 유사 코드를 고려하십시오.[1]

만일 조건     {어떻게 좀 해봐.} 다른     {다른 것을 해라.};

조건부 분기를 사용하는 시스템에서 이는 다음과 유사한 기계 지침으로 변환될 수 있다.[1]

가지를 치다-만일-조건 로 라벨1 다른 것을 해라. 가지를 치다-로 라벨2 라벨1: 어떻게 좀 해봐. 라벨2: ...

포식 상태에서 가능한 모든 분기 경로는 인라인으로 코드화되지만, 일부 지침은 실행되지만 다른 지침은 실행되지 않는다.기본적인 생각은 각 지시는 술어(여기서 술어 논리에서의 그것의 용어와 유사하게 사용되는 단어)와 연관되어 있으며, 그 지시는 술어가 참일 경우에만 실행된다는 것이다.포식법을 사용하는 위의 예에 대한 기계 코드는 다음과 같이 보일 수 있다.[1]

(조건) 어떻게 좀 해봐. (아닌 조건) 다른 것을 해라.

분기를 제거하는 것 외에도, 구조가 사전 결정된 지침을 제공하는 경우, 총체적으로 필요한 코드는 적다.이것이 일반적으로 더 빠른 실행을 보장하지는 않지만, 코드의 및 블록이 충분히 짧다면 그렇게 될 것이다.

포식자의 가장 간단한 형태는 부분 포식이며, 여기서 아키텍처는 조건부 이동 또는 조건부 선택 명령이 있다.조건부 이동지시는 술어의 값이 참인 경우에만 한 레지스터의 내용을 다른 레지스터 위에 쓰는 반면, 조건부 선택지시는 두 레지스터 중 어떤 레지스터의 내용을 술어의 값에 기초하여 3분의 1로 쓰는지 선택한다.좀 더 일반화되고 유능한 형태는 완전한 약탈이다.완전 술어에는 술어를 저장하기 위한 술어 레지스터 집합(여러 개의 내포 또는 순차 분기를 동시에 제거할 수 있음)이 있으며, 아키텍처의 대부분의 지침에는 술어를 제공하는 술어 레지스터를 지정하는 레지스터 지정자 필드가 있다.[2]

이점

프로그램 코드의 매우 작은 부분에 대한 점프를 방지하여 파이프라인 실행의 효과를 높이고 캐시에 문제가 발생하지 않도록 하는 것이 주요 목적이다.또한 다음과 같은 여러 가지 미묘한 이점이 있다.

  • 기존에는 단순한 산술 연산과 비트 와이즈 연산을 사용하여 계산한 함수가 사전 지정된 명령을 사용하여 계산하는 것이 더 빠를 수 있다.
  • 서로 다른 술어를 사용하는 사전 정의된 지침은 서로 혼합될 수 있으며 무조건적인 코드도 함께 사용할 수 있어 더 나은 명령 스케줄링이 가능하고 성능이 더욱 우수하다.
  • 불필요한 분기 지시를 제거하면 분기 예측 메커니즘에 대한 부하를 줄임으로써 루프를 구성하는 분기와 같이 필요한 분기의 실행을 더 빠르게 할 수 있다.
  • 깊은 파이프라인 아키텍처에서 높은 비용을 발생시킬 수 있는 지점 오용 비용 제거.
  • 지침에 의해 생성된 포괄적인 조건 코드가 있는 명령 집합은 상황 레지스터를 직접 사용하거나 포식자로 사용하여 코드 크기를 더 줄일 수 있다.

단점들

술어의 주된 단점은 늘어난 인코딩 공간에 있다.일반적인 구현에서, 모든 지침은 어떤 조건에서 어떤 명령이 영향을 미치는지 명시하는 술어를 위한 비트 필드를 보유한다.임베디드 기기와 같이 사용 가능한 메모리가 제한될 경우, 이 공간 비용은 엄청나게 비쌀 수 있다.그러나 엄지손가락-2와 같은 일부 아키텍처는 이러한 문제를 피할 수 있다(아래 참조).기타 유해한 점은 다음과 같다.[3]

  • 포식은 중요한 경로에 로직 수준을 추가함으로써 하드웨어를 복잡하게 하고 잠재적으로 클럭 속도를 저하시킨다.
  • 사전 설정된 블록은 모든 작동에 대한 주기를 포함하므로 짧은 경로가 더 오래 걸리고 불이익을 받을 수 있다.
  • 포식은 보통 추측되지 않고 더 긴 의존 사슬을 야기한다.주문된 데이터의 경우 이는 예측 가능한 분기 대비 성능 손실을 의미한다.[4]

포식은 경로가 균형을 이루거나 가장 긴 경로가 가장 자주 실행될 때 가장 효과적이지만,[3] 프로파일링 정보가 있는 경우에도 컴파일 시간에 그러한 경로를 결정하는 것은 매우 어렵다.

역사

1950년대의 유럽 컴퓨터 디자인에서는 Mailüfterl(1955년), Zeuse Z22(1955년), ZEBRA(1958년), Electricogramica X1(1958년) 등 사전 지정된 지침이 유행했다.1967년 IBM ACS-1 설계는 명령 형식의 "스킵" 비트를 할당했고, 1976년 CDC 플렉시블 프로세서는 마이크로 Instruction 형식의 조건부 실행 비트 3개를 할당했다.

휴렛패커드의 PA-RISC 아키텍처(1986)는 무효화라는 특징을 가지고 있었는데, 이를 통해 대부분의 지시사항이 앞의 지시로 전제될 수 있었다.IBM의 POWER 아키텍처 (1990)는 조건부 이동 지시사항을 특징으로 했다.POWER의 후임인 PowerPC(1993)는 이러한 지시를 내렸다.디지털기기공사의 알파 아키텍처(1992)도 조건부 이동지시를 특징으로 했다.MIPS는 1994년 MIPS IV 버전으로 조건부 이동 명령을 얻었으며 SPARC는 버전 9(1994)에서 정수 및 부동 소수점 레지스터에 대한 조건부 이동 명령을 사용하여 확장되었다.

Hewlett-Packard/Intel IA-64 아키텍처에서는 대부분의 지침이 전제되어 있다.술어는 64개의 특수 목적 술어 레지스터에 저장되며, 술어 레지스터 중 하나는 항상 참이기 때문에 정의되지 않은 지시사항은 단순히 참 값과 관련된 지시사항일 뿐이다.IA-64의 소프트웨어 파이프라인 구현에는 포식 사용이 필수적이다. 왜냐하면 프롤로그와 에필로그에 대해 구분된 코드를 작성할 필요가 없기 때문이다.[clarification needed]

x86 아키텍처에서 조건부 이동 명령어 제품군 (CMOV그리고FCMOV )는 IntelPentium Pro(1995) 프로세서에 의해 아키텍처에 추가되었다.그CMOV지시사항은 플래그 레지스터 값으로 제공되는 술어에 따라 소스 레지스터의 내용을 목적지 레지스터에 복사했다.

ARM 아키텍처에서, 원래 32비트 명령 집합은 이전 명령으로 설정된 4가지 조건 코드의 어떤 조합에 기초하는 13가지 술어 중 하나에 의해 대부분의 명령이 예단될 수 있도록 하는 조건부 실행이라는 기능을 제공한다.ARM의 썸 명령어 세트(1994)는 16비트에 들어갈 수 있도록 명령어 크기를 줄이기 위해 조건부 실행을 취하했지만, 그 후임자인 썸-2(2003)는 다음 4가지 명령어에 술어를 공급하는 것 외에는 별다른 효과가 없는 특수 명령을 사용함으로써 이 문제를 극복했다.ARMv8-A(2011년)에 도입된 64비트 명령 집합은 조건부 실행을 조건부 선택 지침으로 대체했다.

SIMD, SIMT 및 벡터 술어

AVX2와 같은 일부 SIMD 명령 집합은 조건부 이동의 병렬 형태인 메모리에 조건부로 로드/저장하기 위해 논리 마스크를 사용할 수 있으며, 병렬 연산을 실행하는 개별 산술 단위에도 개별 마스크 비트를 적용할 수 있다.이 기법은 플린의 택사노미에서 "어소시에이티브 프로세싱"으로 알려져 있다.

이러한 형태의 술어는 벡터 프로세서와 단일 명령, 다중 스레드 GPU 컴퓨팅에서도 사용된다.단일 스칼라 포식술의 모든 기법, 장점, 단점은 병렬 처리 케이스에도 똑같이 적용된다.

참고 항목

참조

  1. ^ a b c d Rick Vinyard (2000-04-26). "Predication". cs.nmsu.edu. Retrieved 2014-04-22.
  2. ^ Mahlke, Scott A.; Hank, Richard E.; McCormick, James E.; August, David I.; Hwn, Wen-mei W. (22–24 June 1995). "A Comparison of Full and Partial Predicated Execution Support for ILP Processors". The 22nd International Symposium on Computer Architecture.
  3. ^ a b 조셉 A.Fisher, Paolo Faraboschi, Cliff Young(2004) Embedded Computing - 건축, 컴파일러 및 Tools에 대한 VLIW 접근법172페이지.
  4. ^ Cordes, Peter. "assembly - How does Out of Order execution work with conditional instructions, Ex: CMOVcc in Intel or ADDNE (Add not equal) in ARM". Stack Overflow. Unlike with control dependencies (branches), they don't predict or speculate what the flags will be, so a cmovcc instead of a jcc can create a loop-carried dependency chain and end up being worse than a predictable branch. [1] is an example of that. {{cite web}}:외부 링크 위치 quote=(도움말)

추가 읽기