지점(컴퓨터 과학)

Branch (computer science)
소프트웨어 엔지니어링 개념에 대해서는 분기(버전 제어)를 참조하십시오.다른 용도는 분기(동음이의)를 참조하십시오.
기계코드
일반적인 개념
지침들

브랜치는 컴퓨터가 다른 명령 시퀀스를 실행하기 시작하도록 할 수 있는 컴퓨터 프로그램의 명령으로,[a] 명령어를 순서대로 실행하는 기본 동작에서 벗어난다.분기(또는 분기, 분기)는 분기 명령을 실행한 결과 다른 명령 시퀀스로 실행을 전환하는 행위도 참조할 수 있습니다.분기 명령은 프로그램 루프 및 조건부 제어 흐름을 구현하기 위해 사용됩니다(즉, 특정 조건이 충족될 경우에만 특정 명령 시퀀스를 실행합니다).

분기 명령어는 항상 분기가 되는 무조건 분기 또는 조건에 따라 분기가 발생하는 조건부 분기 중 하나입니다.또, 새로운 명령 시퀀스의 주소(「타깃」주소)를 지정하는 방법에 따라, 브랜치 명령은 일반적으로 직접, 간접 또는 상대적인 것으로 분류된다.즉, 명령어가 타겟 주소를 포함하거나, 타겟 주소를 찾을 장소(예를 들면, 레지스터 또는 메모리 위치)를 지정하거나, 특정하는 것을 의미한다.현재 주소와 타깃주소의 차이입니다.

실행

분기 명령은 CPU의 프로그램 카운터(또는 PC)(또는 인텔 마이크로프로세서의 명령 포인터)의 내용을 변경할 수 있습니다.PC는 가져오기 및 실행할 다음 기계 명령의 메모리 주소를 유지합니다.따라서 브랜치가 실행되면 CPU는 새로운 메모리주소에서 코드를 실행하고 프로그래머가 계획한 알고리즘에 따라 프로그램 로직을 변경합니다.

기계 레벨 브랜치의 한 가지 유형은 점프 명령입니다.이로 인해 PC가 로딩되거나 변경되는 경우가 있습니다(현재 명령에서 다음 명령을 가리키도록 증가).점프는 일반적으로 조건 없는 형태와 조건적인 형태가 있는데, 어떤 조건에 따라 후자가 수행되거나 수행되지 않을 수 있다(PC가 수정되거나 수정되지 않을 수 있다.

머신 레벨 브랜치의 두 번째 유형은 서브루틴을 구현하기 위해 사용되는 콜 명령입니다.점프 명령과 마찬가지로 콜은 상태 코드에 따라 PC를 변경할 수도 있고 변경할 수도 있지만 반환 주소는 메모리의 안전한 장소(통상은 스택이라고 불리는 메모리 상주 데이터 구조)에 저장됩니다.서브루틴이 완료되면 이 리턴 주소가 PC로 복원되므로 호출 명령에 따른 명령으로 프로그램 실행이 재개됩니다.

세 번째 유형의 머신레벨 브랜치는 반환 명령입니다.이것에 의해, 스택으로부터 리턴 주소가 「팝」되어 PC 레지스터에 로드되어 콜 루틴으로 제어가 돌아옵니다.반환 명령은 조건부로 실행될 수도 있습니다.이 설명은 일반적인 관행과 관련이 있지만, 머신 프로그래머는 스택상의 리턴 주소를 조작할 수 있는 상당한 능력을 가지고 있기 때문에 프로그램 실행을 다양한 방법으로 리다이렉트 할 수 있습니다.

프로세서에 따라서는, 점프와 호출의 지시에 의해서 PC 레지스터의 내용이 다른 방법으로 변경되는 일이 있습니다.절대 주소가 로드되거나 PC의 현재 컨텐츠가 현재 값에서 추가 또는 차감되어 프로그램의 현재 위치에 상대적인 수신처 주소가 될 수 있습니다.변위값의 출처는 명령어에 포함된 즉시값, 프로세서 레지스터 또는 메모리 위치의 내용, 인덱스 값에 추가된 일부 위치의 내용 등 다양할 수 있습니다.

분기라는 용어는 고급 프로그래밍 언어로 된 프로그램을 참조할 때도 사용할 수 있습니다.이러한 브랜치에서는 보통 조건이 충족될 경우 실행되는 명령 시퀀스를 캡슐화하는 다양한 형식의 조건문 형식을 취합니다.GOTO와 같은 무조건 분기 명령은 무조건 다른 명령 시퀀스로 점프하기 위해 사용됩니다.알고리즘에 조건부 브랜치가 필요한 경우 GOTO(또는 GOSUB 서브루틴콜) 앞에 조건을 지정하는 IF-THEN 문이 붙습니다.모든 고급 언어는 루프로 코드를 재사용할 수 있는 알고리즘을 지원합니다.이 알고리즘은 루프가 종료되는 조건이 충족될 때까지 일련의 명령을 반복하는 제어 구조입니다.루프는 분기 명령으로도 사용할 수 있습니다.머신 레벨에서 루프는 실행을 반복 코드로 리다이렉트하는 통상적인 조건부 점프로서 실장됩니다.

플래그 레지스터가 있는 CPU에서는 이전 명령이 플래그 레지스터에 조건을 설정합니다.이전 명령은 산술 명령 또는 논리 명령일 수 있습니다.브랜치 직전에 지시하는 것은 아니지만 브랜치에 가까운 경우가 많습니다.그런 다음 저장된 조건은 jump if overflow-flag set 등의 브랜치에서 사용됩니다.이 임시 정보는 종종 플래그 레지스터에 저장되지만 다른 위치에 있을 수도 있습니다.플래그 레지스터 설계는 더 느리고 단순한 컴퓨터에서는 간단합니다.고속 컴퓨터에서는 플래그 레지스터가 속도에 병목 현상을 일으킬 수 있습니다. 왜냐하면 병렬로 동작할 수 있는 명령어는 특정 순서로 플래그 비트를 설정할 필요가 있기 때문입니다.

또한 점프 명령 자체에 의해 상태를 확인할 수 있는 기계(또는 특정 명령)도 있습니다. 예를 들어 레지스터 X가 음의 경우 분기 <label>과 같습니다.단순한 컴퓨터 설계에서 비교 브랜치는 플래그 레지스터 브랜치보다 더 많은 연산을 실행하고 더 많은 전력을 사용할 수 있습니다.빠른 컴퓨터 설계에서 비교 브랜치는 플래그 레지스터 브랜치보다 더 빠르게 실행될 수 있습니다. 왜냐하면 비교 브랜치는 동일한 CPU 메커니즘을 계산으로 사용하여 더 많은 병렬로 레지스터에 액세스할 수 있기 때문입니다.

마이크로컨트롤러에서 여전히 볼 수 있는 일부 초기 및 단순한 CPU 아키텍처는 조건부 점프를 구현하지 않고 조건부 "다음 명령 건너뛰기" 작업만 구현할 수 있습니다.따라서 조건부 점프 또는 콜은 무조건 점프 또는 콜 명령의 조건부 스킵으로 구현됩니다.

예

컴퓨터 아키텍처에 따라 점프 명령의 어셈블리 언어 니모닉은 일반적으로 단어 점프 또는 단어 분기의 일부 축약된 형태이며, 종종 조건을 나타내는 다른 유익한 문자(또는 추가 매개 변수)와 함께 사용됩니다.점프 범위(오프셋 크기)나 실제 유효 오프셋을 찾는 데 사용해야 하는 특수 주소 지정 모드와 같은 다른 세부 사항도 포함될 수 있습니다.

다음 표에 몇 가지 유명한 아키텍처에서 볼 수 있는 머신레벨의 분기 또는 점프 순서를 나타냅니다.

조건 또는 결과 x86 PDP-11, VAX ARM(일부 6502) 방정식
제로(서브/cmp의 경우와 동일) JZ; JNZ BEQ; BNE BEQ; BNE 제로, 제로 아님
음수(N), 기호(S) 또는 마이너스(M) JS; JNS BMI; BPL BMI; BPL 마이너스, 마이너스 아님
산술 오버플로(O 또는 V라고 하는 플래그) JO; JNO BVS, BVC BVS, BVC 오버플로우, 오버플로우 없음
운반(add, cmp, shift 등) JC; JNC BCS; BCC BCS; BCC 운반하다
아래(아래)에 부호 없음 JB 블록 블록 빌리다
아래 또는 동일(낮음 또는 동일)의 부호가 없는 JBE 하지 않다 BLS * 차용 또는 제로
위에서 또는 동등하게 부호 없는(부호 또는 동일) 재 BHIS BHS * 빌리지 않다
위에 부호 없음(필수) 네. BHI BHI * 빌리지 않고 제로도 아니다
보다 적게 서명했다 JL BLT BLT 사인
보다 적게 또는 동등하게 서명된 JLE 삐걱거리다 삐걱거리다 (부호) 또는 제로
보다 크거나 동등하게 서명된 JGE BGE BGE 부호 = 표시
보다 큰 서명 JG BGT BGT (sign=sign) 및 0이 아님

* x86, PDP-11, VAX 및 기타 일부에서는 캐리어 플래그를 차용 신호로 설정하고 캐리어 플래그를 클리어하여 차용 신호를 보냅니다.ARM, 6502, PIC 및 기타 일부에서는 감산 연산에 대해 이와 반대입니다.특정 명령에 대한 이 반송 플래그의 반전 함수는 ()*로 표시됩니다. 즉, 표의 일부 부분에 borrow=not carry, 그러나 달리 명시되지 않은 경우 borrown-carry로 표시됩니다.그러나 가법 연산은 대부분의 아키텍처에서 동일한 방식으로 처리됩니다.

브랜치 명령의 퍼포먼스 문제

고성능을 실현하기 위해 최신 프로세서는 파이프라인으로 되어 있습니다.이들은 각각 부분적으로 명령을 처리하고 파이프라인의 다음 단계로 결과를 전송하며 프로그램의 다음 명령 작업을 시작하는 여러 부분으로 구성됩니다.이 설계에서는 특정 변경되지 않은 시퀀스로 명령이 실행되어야 합니다.조건부 분기 명령에서는 이 시퀀스를 알 수 없습니다.따라서 조건부 브랜치로 인해 프로그램의 다른 부분에서 파이프라인을 재시작해야 하는 "스톨"이 발생할 수 있습니다.

지점에서의 좌판을 줄임으로써 퍼포먼스 향상

조건부 분기의 스톨을 줄임으로써 몇 가지 기술이 속도를 향상시킵니다.

분기 예측 힌트

이전에는 분기 예측이 통계를 취하여 결과를 사용하여 코드를 최적화했습니다.프로그래머는 프로그램의 테스트 버전을 컴파일하여 테스트 데이터로 실행합니다.테스트 코드는 나뭇가지가 실제로 어떻게 찍혔는지 세어 보았습니다.테스트 코드로부터의 통계는, 해방된 코드의 브랜치를 최적화하기 위해서 컴파일러에 의해서 사용되었습니다.최적화는 가장 빠른 분기 방향(취득 여부에 관계없이)이 항상 가장 빈번하게 취해지는 제어 흐름 경로가 되도록 준비합니다.이를 허용하려면 CPU는 예측 가능한 브랜치타이밍을 설계해야 합니다(또는 적어도 가지고 있어야 합니다.일부 CPU에는 "브런치 힌트"를 사용하여 설계된 명령 집합(Power ISA 등)이 있어 컴파일러가 각 브런치를 취득하는 방법을 CPU에 지시할 수 있습니다.

소프트웨어 브랜치 예측의 문제는 복잡한 소프트웨어 개발 프로세스가 필요하다는 것입니다.

하드웨어 분기 예측 변수

소프트웨어를 실행하기 위해 하드웨어 브랜치 프레딕터는 통계정보를 전자제품으로 이동시켰습니다.분기 예측 변수는 조건부 분기 결과를 추측하는 프로세서의 일부입니다.그 후 프로세서의 로직은 예상되는 명령 플로우의 실행을 시작함으로써 추측에 도달합니다.단순한 하드웨어 분기 예측 스킴의 예로는 모든 후방 분기(즉, 작은 프로그램 카운터)가 취해지고(루프의 일부이기 때문에), 모든 전방 분기(더 큰 프로그램 카운터)가 취하지 않는다고 가정하는 것이 있다(루프를 남기기 때문에).보다 우수한 분기 예측 변수는 다양한 테스트 프로그램에서 시뮬레이션으로 실행함으로써 통계적으로 개발 및 검증됩니다.좋은 예측 변수는 일반적으로 이전에 실행된 지점의 결과를 계산합니다.더 빠르고 더 비싼 컴퓨터는 더 나은 분기 예측 전자 장치에 투자함으로써 더 빨리 실행될 수 있습니다.하드웨어 분기 예측을 가진 CPU에서 분기 힌트는 컴파일러의 아마도 우수한 분기 예측을 하드웨어의 보다 단순한 분기 예측을 덮어쓸 수 있도록 합니다.

브런치 프리 코드

일부 논리는 분기 없이 또는 더 적은 분기로 작성할 수 있습니다.많은 [1][2]경우 분기 대신 비트 연산, 조건부 이동 또는 기타 프레딕션을 사용할 수 있습니다.실제로 타이밍 [3]공격으로 인해 브런치프리 코드는 암호화에 필수적입니다.

지연 슬롯

또 다른 방법은 분기 지연 슬롯입니다.이 접근법에서는 분기 후에 항상 하나의 명령이 실행됩니다.따라서 컴퓨터는 파이프라인 정지 여부에 관계없이 이 명령을 사용하여 유용한 작업을 수행할 수 있습니다.이 어프로치는, RISC 컴퓨터에서는 지금까지 널리 사용되고 있었습니다.호환되는 CPU 제품군에서는 멀티사이클 CPU(파이프라인이 없음), 예상보다 긴 파이프라인이 있는 고속 CPU 및 슈퍼스케일러 CPU(명령어를 잘못 실행할 수 있음)가 복잡해집니다.

「 」를 참조해 주세요.

메모들

  1. ^ 적어도 개념적으로는 순서가 잘못된 실행을 참조하십시오.

레퍼런스

  1. ^ Knuth, Donald (2008). The Art of Computer Programming. Vol. 4, Pre-fascicle 1A (Revision 6 ed.). pp. 48–49.
  2. ^ "Avoiding Branches". Chessprogramming wiki.
  3. ^ "Constant-Time Crypto". BearSSL.

외부 링크