맨위로가기

브랜치 (컴퓨터 과학)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

브랜치(Branch)는 CPU의 프로그램 실행 흐름을 변경하는 명령어이다. 분기 명령어는 프로그램 카운터(PC)의 값을 변경하여 실행 위치를 이동시키며, 점프, 호출, 반환 명령어 등이 있다. 고급 프로그래밍 언어에서는 조건문과 반복문을 통해 구현된다. 최신 프로세서는 파이프라인 방식 사용으로 인해 분기 명령어 실행 시 성능 저하가 발생할 수 있으며, 이를 해결하기 위해 분기 예측, 분기 힌트, 분기 없는 코드 작성, 지연 슬롯 등의 기술이 사용된다.

더 읽어볼만한 페이지

  • 기계어 - 주소 지정 방식
  • 기계어 - CPUID
    CPUID는 x86 아키텍처에서 CPU의 제조사, 모델, 기능 등을 식별하는 명령어이며, EAX 레지스터를 통해 호출 매개변수를 지정하여 정보를 반환받을 수 있고, 다른 아키텍처에서도 유사한 정보 획득 방법이 존재하며, 고급 언어에서도 접근 가능하다.
  • 명령어 처리 - 멀티스레딩
    멀티스레딩은 프로세스 내에서 여러 스레드를 동시 실행하여 처리 능력을 향상시키는 기술로, 응답성 향상과 자원 공유 등의 장점이 있지만, 자원 간섭과 소프트웨어 복잡성 증가 등의 단점도 존재하며, 다양한 모델과 구현 방식, 스레드 스케줄러, 가상 머신 활성화 가능성 등을 고려해야 한다.
  • 명령어 처리 - 마이크로아키텍처
    마이크로아키텍처는 명령어 집합 아키텍처를 구현하는 프로세서의 구성 요소, 상호 연결, 작동 방식을 포괄하는 개념으로, 동일 ISA에서 반도체 기술 발전과 새로운 구조 및 회로를 통해 성능 향상을 가능하게 한다.
  • 제어 흐름 - 프로그램 카운터
    프로그램 카운터는 CPU 내에서 다음에 실행될 명령어의 주소를 저장하는 레지스터로, 명령어 사이클의 fetch 단계에서 사용되어 명령어를 가져오고 실행 후 갱신되며, CPU 성능 향상 기술과 현대 프로그래밍 모델에 영향을 미친다.
  • 제어 흐름 - 예외 처리
    예외 처리는 프로그램 실행 중 예외 발생 시 정상적인 실행 흐름을 유지하거나 안전하게 종료하기 위한 메커니즘으로, 많은 프로그래밍 언어에서 제공하며 예외 안전성을 목표로 한다.
브랜치 (컴퓨터 과학)
컴퓨터 과학에서의 분기
정의프로그램 실행 흐름을 변경하는 명령어
종류조건 분기
무조건 분기
활용조건문 구현
반복문 구현
함수 호출
예외 처리
조건 분기
설명특정 조건의 참/거짓 여부에 따라 실행 경로를 변경
예시만약 (조건) { // 조건이 참일 때 실행 } 그렇지 않으면 { // 조건이 거짓일 때 실행 }
무조건 분기
설명조건 없이 지정된 위치로 실행 흐름을 이동
예시goto 레이블; // 레이블 위치로 이동
어셈블리어에서의 분기 명령어
예시 명령어JMP (점프): 무조건 분기
JE (같으면 점프), JNE (같지 않으면 점프): 조건 분기
JG (크면 점프), JL (작으면 점프): 조건 분기

2. 구현

분기 명령어는 CPU의 프로그램 카운터(PC) 값을 변경하여 프로그램 실행 흐름을 바꾼다. 프로그램 카운터는 다음에 실행될 명령어의 메모리 주소를 가리킨다. 분기가 실행되면 CPU는 새로운 메모리 주소에서 코드를 실행하게 된다.[1]

기계어 수준에서 분기 유형에는 점프 명령어, 호출 명령어, 반환 명령어가 있다.


  • 점프 명령어: PC 값을 특정 값으로 변경하여 실행 위치를 이동시킨다. 조건부 점프는 특정 조건이 참일 때만 실행된다.
  • 호출 명령어: 서브루틴을 실행하기 위해 사용되며, 현재 PC 값(반환 주소)을 스택에 저장하고 서브루틴의 시작 주소로 PC 값을 변경한다.
  • 반환 명령어: 스택에서 반환 주소를 꺼내 PC 값에 로드하여 호출한 위치로 돌아간다.


프로세서에 따라 점프 및 호출 명령어는 PC 레지스터의 내용을 변경하는 방식이 다를 수 있다. 절대 주소를 사용하거나, 현재 PC 값에 특정 값을 더하거나 빼는 방식으로 상대 주소를 사용할 수 있다.

고급 프로그래밍 언어에서도 분기는 조건문(if-then-else) 및 반복문(loop)과 같은 제어 구조를 통해 구현된다. 무조건 분기 명령어 (GOTO)도 존재한다.

분기 명령어의 조건은 플래그 레지스터에 저장된 값을 기반으로 하거나, 레지스터 값을 직접 비교하여 결정될 수 있다.

일부 초기 및 단순 CPU 아키텍처는 조건부 점프 대신 조건부 "다음 명령어 건너뛰기" 연산을 사용하기도 한다.

2. 1. 예

branch영어 명령어는 컴퓨터 프로그램에서 특정 조건이 만족되면 다른 부분으로 실행 흐름을 바꾸는 명령어이다. 다양한 컴퓨터 아키텍처에서 사용되는 분기 명령어의 예시는 다음과 같다.

다양한 아키텍처에서의 분기 명령어 예시
조건 또는 결과x86PDP-11, VAXARM (일부 6502)등식
제로 (sub/cmp의 경우 같음을 의미)JZ; JNZBEQ; BNEBEQ; BNE제로; 제로 아님
음수(N), 부호(S), 또는 마이너스(M)JS; JNSBMI; BPLBMI; BPL음수; 음수 아님
산술 오버플로 (플래그 O 또는 V라고 함)JO; JNOBVS; BVCBVS; BVC오버플로; 오버플로 아님
캐리 (add, cmp, shift 등에서)JC; JNCBCS; BCCBCS; BCC캐리; 캐리 아님
부호 없는 미만 (더 작음)JBBLOBLO *빌림
부호 없는 미만이거나 같음 (더 작거나 같음)JBEBLOSBLS *빌림 또는 제로
부호 없는 이상이거나 같음 (더 크거나 같음)JAEBHISBHS *빌림 아님
부호 없는 초과 (더 큼)JABHIBHI *빌림 아님 및 제로 아님
부호 있는 미만JLBLTBLT부호≠오버플로
부호 있는 미만이거나 같음JLEBLEBLE(부호≠오버플로) 또는 제로
부호 있는 이상이거나 같음JGEBGEBGE부호=오버플로
부호 있는 초과JGBGTBGT(부호=오버플로) 및 제로 아님



x86, PDP-11, VAX 및 일부 다른 아키텍처는 "빌림"을 신호하기 위해 캐리 플래그를 설정하고 "빌림 없음"을 신호하기 위해 캐리 플래그를 지운다. ARM, 6502, PIC 및 일부 다른 아키텍처는 뺄셈 연산에 대해 반대로 수행한다. 특정 명령어에 대한 캐리 플래그의 이러한 반전된 기능은 위 표에서 *로 표시되어 있다. 즉, 표의 일부에서 '''빌림=not 캐리'''이지만, 달리 언급되지 않으면 빌림≡캐리이다. 그러나 덧셈 연산에 대한 캐리는 대부분의 아키텍처에서 동일하게 처리된다.[1]

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

3. 성능 문제 및 최적화

최신 프로세서는 고성능을 위해 파이프라인 방식을 사용한다. 이 방식은 각 명령어의 일부를 처리하고, 결과를 다음 단계로 전달하며, 다음 명령어를 처리하는 여러 부분으로 구성되어 프로그램이 특정 순서로 실행될 것이라 예상한다. 그러나 조건 분기 명령어는 이러한 순서를 예측하기 어렵게 만들어, 프로세서가 프로그램의 다른 부분에서 다시 시작해야 하는 "스톨" 현상을 일으킬 수 있다.[1]

이러한 분기로 인한 지연을 줄이고 속도를 향상시키기 위해 분기 예측, 분기 힌트, 분기 없는 코드 작성, 지연 슬롯 등의 기술이 사용된다.

3. 1. 분기 예측

분기 예측기는 조건부 분기의 결과를 추측하는 프로세서의 일부이다. 그러면 프로세서의 로직은 예상된 명령 흐름의 실행을 시작하여 추측에 따라 작동한다. 간단한 하드웨어 분기 예측 방식의 예로는 모든 역방향 분기(즉, 더 작은 프로그램 카운터로)는 실행된 것으로 가정하고(루프의 일부이기 때문에), 모든 정방향 분기(더 큰 프로그램 카운터로)는 실행되지 않은 것으로 가정하는 것이다(루프를 벗어나기 때문에).[1] 더 나은 분기 예측기는 다양한 테스트 프로그램을 시뮬레이션하여 통계적으로 개발되고 검증된다.[1] 좋은 예측기는 일반적으로 이전 분기 실행 결과를 계산한다.[1] 더 빠르고, 더 비싼 컴퓨터는 더 나은 분기 예측 전자 장치에 투자하여 더 빠르게 실행될 수 있다.[1] 하드웨어 분기 예측이 있는 CPU에서 분기 힌트는 컴파일러의 더 우수한 분기 예측이 하드웨어의 더 단순한 분기 예측을 무시하도록 한다.[1]

3. 2. 분기 힌트

과거에는 분기 예측에 통계를 사용하고 그 결과를 활용하여 코드를 최적화했다. 프로그래머는 프로그램의 테스트 버전을 컴파일하고 테스트 데이터로 실행했다. 테스트 코드는 분기가 실제로 어떻게 실행되는지 계산했다. 그런 다음 컴파일러는 테스트 코드의 통계를 사용하여 릴리스된 코드의 분기를 최적화했다. 최적화를 통해 가장 빠른 분기 방향(실행 또는 비실행)이 항상 가장 자주 실행되는 제어 흐름 경로가 되도록 했다. 이를 허용하려면 CPU가 예측 가능한 분기 타이밍을 갖도록 (또는 적어도 갖도록) 설계되어야 한다. 일부 CPU는 컴파일러가 각 분기를 어떻게 실행해야 하는지 CPU에 알릴 수 있도록 "분기 힌트"로 설계된 명령어 세트(예: Power ISA)를 가지고 있다.

소프트웨어 분기 예측의 문제는 복잡한 소프트웨어 개발 프로세스가 필요하다는 것이다.

3. 3. 분기 없는 코드 작성

어떤 논리는 분기 없이, 또는 더 적은 분기로 작성될 수 있다. 비트 연산, 조건부 이동 또는 기타 조건부 실행을 분기 대신 사용하는 것이 종종 가능하다.[1][2] 실제로 분기 없는 코드는 타이밍 공격 때문에 암호화에 필수적이다.[3]

3. 4. 지연 슬롯

분기 지연 슬롯은 분기 명령어 바로 다음 명령어를 분기 조건과 관계없이 항상 실행하는 기법이다. MIPS 아키텍처의 가능성/불가능성 분기 명령어와 같은 몇 가지 예외가 있다.[1] 따라서 컴퓨터는 파이프라인이 정지되는지 여부에 관계없이 이 명령어를 사용하여 유용한 작업을 수행할 수 있다.[1] 이 방식은 역사적으로 RISC 컴퓨터에서 인기가 있었다.[1] 호환 가능한 CPU 제품군에서 이는 멀티 사이클 CPU (파이프라인 없음), 예상보다 긴 파이프라인을 가진 더 빠른 CPU, 그리고 수퍼스칼라 CPU (비순차적으로 명령어를 실행할 수 있음)를 복잡하게 만든다.[1]

참조

[1] 서적 The Art of Computer Programming
[2] 웹사이트 Avoiding Branches https://www.chesspro[...]
[3] 웹사이트 Constant-Time Crypto https://www.bearssl.[...]
[4] 서적 Computer Architecture and Organization
[5] 문서 命令セットアーキテクチャにも依り、例えば[[スタックマシン]]においてスタックのトップを暗黙の引数とするため引数を持たない、という設計もあるかもしれない。またサブルーチンからの戻りを分岐命令とする場合、多くの設計で特定のレジスタか[[コールスタック]]のトップが暗黙の引数であり、命令自体は引数を持たない。
[6] 문서 後者はともかく、前者はPCへの任意の代入があり得ることから、パイプラインストールのペナルティは悪化しうる。
[7] 웹사이트 w11: PDP-11/70 CPU and SoC の DEC Patents https://wfjm.github.[...] 2024-09-04
[8] 웹사이트 うんちく：アドレッシングモードの色々 https://www.am.ics.k[...] 2024-09-04
[9] 논문 A Survey of Techniques for Dynamic Branch Prediction https://www.research[...] CPE


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com