hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
프로세스 모델링 모델의 품질
초기 프로세스 모델은 관련 개념, 사용 가능한 기술, 특정 구현 환경, 프로세스 제약 조건 등에 따라 인스턴스화하여 얻은 실제 프로세스로 프로세스의 역동성을 반영했다.
모델의 품질에 대한 수많은 연구가 진행되었지만, 프로세스 모델의 품질에 대한 초점은 덜 옮겨졌다. 프로세스 모델의 품질 문제는 철저하게 평가될 수 없지만, 이를 위한 네 가지 주요 지침과 프레임워크가 실제로 존재한다. 이들은: 하향식 품질 프레임워크, 품질 측면과 관련된 상향식 메트릭, 모델링 기술과 관련된 실증적 조사, 그리고 실용적인 지침이다.
Hommes는 Wang 등 (1994)의 말을 인용하여, 모델 품질의 모든 주요 특성은 정확성과 유용성의 두 가지 그룹으로 분류될 수 있다고 말했다. 정확성은 모델이 모델링된 현상과의 일치성부터 모델링의 구문 규칙과의 일치성까지 다양하며, 모델이 사용되는 목적과는 독립적이다.
반면, 유용성은 모델이 처음 구성된 특정 목적에 유용하다는 것으로 볼 수 있다. Hommes는 또한 내부 정확성(경험적, 구문적, 의미적 품질)과 외부 정확성(유효성)을 추가적으로 구분한다.
프로세스 모델링 모델의 품질
개념 모델의 품질을 정의하는 일반적인 시작점은 모델링 언어의 언어적 속성을 살펴보는 것이며, 그 중 구문과 의미가 가장 자주 적용된다.
또한, Krogstie가 SEQUAL이라는 하향식 품질 프레임워크를 사용하여 수행한 것처럼, 언어학보다는 기호학에 기반을 둔 더 넓은 접근 방식도 있다. 이 프레임워크는 모델, 지식 외부화, 도메인, 모델링 언어, 그리고 학습, 행동, 모델링 활동 간의 관계를 기반으로 여러 품질 측면을 정의한다.
하지만 이 프레임워크는 다양한 품질의 정도를 결정하는 방법을 제공하지는 않지만, 수행된 경험적 테스트에서 비즈니스 프로세스 모델링에 광범위하게 사용되었다.
Moody 등의 이전 연구에 따르면, Lindland 등 (1994)이 제안한 개념 모델 품질 프레임워크를 사용하여 프로세스 모델의 품질을 평가한 결과 세 가지 수준의 품질이 확인되었다.
프로세스 모델링 모델의 품질
연구 결과, 품질 프레임워크가 프로세스 모델의 품질 평가에 사용하기 쉽고 유용하다는 것이 밝혀졌지만, 신뢰성 및 결함 식별의 어려움이라는 한계가 있었다. 이러한 한계는 크로그스티의 후속 연구를 통해 프레임워크가 개선되는 계기가 되었다. 이 프레임워크는 Krogstie 등(1995)이 제안한 SEQUEL 프레임워크(Krogstie & Jørgensen, 2002에 의해 추가 개선)로, 세 가지 품질 측면을 추가했다.
개념적 품질 프레임워크의 차원
모델링 도메인은 문제 도메인을 설명하는 데 관련성이 있고 올바른 모든 문장들의 집합이며, 언어 확장은 사용되는 모델링 언어의 문법과 어휘가 허용하는 모든 문장들의 집합이다. 모델 외부화는 문제 도메인의 개념적 표현이다.
이는 문제 도메인에 대해 실제로 만들어진 진술들의 집합으로 정의된다. 사회적 행위자 해석과 기술적 행위자 해석은 각각 인간 모델 사용자들과 모델과 상호작용하는 도구들이 문제 도메인의 개념적 표현이 포함하고 있다고 '생각하는' 진술들의 집합이다.
프로세스 모델링 모델의 품질
마지막으로, 참가자 지식은 모델링 프로세스에 참여하는 인간 행위자들이 문제 도메인을 나타내기 위해 만들어져야 한다고 믿는 진술들의 집합이다. 이러한 품질 차원은 나중에 모델의 물리적 및 사회적 측면을 다루는 두 그룹으로 나뉘었다.
이후 작업에서 Krogstie 등은 SEQUAL 프레임워크의 확장이 초기 프레임워크의 일부 한계를 해결했지만, 다른 한계는 여전히 남아 있다고 언급했다.
특히, 프레임워크는 의미론적 품질에 대한 관점이 너무 정적이며, 주로 모델링 활동이 아닌 모델을 고려하고, 이러한 모델을 정적 도메인과 비교하기보다는 모델을 도메인 변경의 촉진자로 본다.
또한, 프레임워크의 실용적 품질 정의는 매우 협소하며, Morris의 기호학에 따라 이해에 중점을 두지만, 언어학 및 기호학의 새로운 연구는 단순한 이해를 넘어 모델이 어떻게 사용되고 해석자에게 영향을 미치는지에 초점을 맞추고 있다.
프로세스 모델링 모델의 품질
기호학적 품질 프레임워크에서 보다 동적인 관점의 필요성은 프로세스 모델을 고려할 때 특히 명백하다. 프로세스 모델 자체는 종종 문제 도메인에서 행동을 규정하거나 심지어 실행하므로, 모델의 변경은 문제 도메인을 직접적으로 변경할 수도 있다. 이 논문은 활성 프로세스 모델과 관련하여 품질 프레임워크를 논의하고 이를 기반으로 개정된 프레임워크를 제안한다.
Krogstie 등(2006)은 활성 프로세스 모델에 더 적합하도록 SEQUAL 프레임워크를 수정하기 위해 이전 연구보다 더 좁은 해석으로 물리적 품질을 재정의했다.
사용 중인 또 다른 프레임워크는 일반 회계 원칙에 기반을 둔 모델링 지침(GoM)으로, 다음 여섯 가지 원칙을 포함한다: 정확성, 명확성은 모델 시스템의 이해도와 명시성(시스템 설명)을 다룬다.
이해도는 정보 객체의 그래픽적 배열과 관련되며, 따라서 모델의 이해도를 지원한다.
관련성은 모델과 제시되는 상황과 관련된다. 비교 가능성은 모델을 비교할 수 있는 능력, 즉 두 모델 간의 의미적 비교를 포함하며, 경제적 효율성은 설계 프로세스의 생성 비용이 최소한 제안된 비용 절감 및 수익 증가로 충당되어야 한다.
프로세스 모델링 모델의 품질
조직의 목적은 대부분의 경우 이윤 극대화이므로, 이 원칙은 모델링 프로세스의 경계를 정의한다. 마지막 원칙은 체계적인 설계로, 모델링 내에서 다양한 관점 간에 수용 가능한 차별화가 있어야 함을 정의한다.
정확성, 관련성, 경제적 효율성은 모델 품질의 전제 조건이며 충족되어야 하지만, 나머지 지침은 선택 사항이지만 필요하다.
SEQUAL과 GOM이라는 두 가지 프레임워크는 모델링에 능숙하지 않은 사람이 사용할 수 없다는 한계가 있다. 이들은 주요 품질 측정 기준을 제공하지만 비전문가가 쉽게 적용하기 어렵다.
프로세스 모델의 품질 측면과 관련된 상향식 메트릭의 사용은 모델링 비전문가가 다른 두 프레임워크를 사용하는 격차를 해소하려는 시도이지만, 대부분 이론적이며 그 사용을 뒷받침하는 경험적 테스트는 수행되지 않았다.
프로세스 모델링 모델의 품질
수행된 대부분의 실험은 메트릭과 품질 측면 간의 관계와 관련되며, 이러한 작업은 다양한 저자에 의해 개별적으로 수행되었다. Canfora 등은 주로 개수 메트릭(예: 작업 또는 분할 수 - 소프트웨어 프로세스 모델의 유지보수성) 간의 연결을 연구한다. Cardoso는 제어 흐름 복잡성과 인지된 복잡성 간의 상관관계를 검증한다. 그리고 Mendling 등은 프로세스 모델에서 교착 상태와 같은 제어 흐름 오류를 예측하는 데 메트릭을 사용한다.
결과는 모델의 크기가 증가하면 품질과 이해도가 감소하는 것으로 나타났다.
Mendling 등의 추가 연구는 메트릭과 이해도 간의 연결을 조사한다. 그리고 일부 메트릭이 그 효과에 대해 확인되었지만, 모델러의 역량과 같은 개인적인 요인도 모델에 대한 이해에 중요함이 밝혀졌다.
수행된 여러 경험적 조사는 여전히 프로세스 모델의 품질을 평가하는 명확한 지침이나 방법을 제공하지 못하지만, 모델러가 이 작업을 수행하는 데 필요한 명확한 지침 세트가 필요하다. 실용적인 지침은 다양한 실무자들에 의해 제안되었지만, 실제에서 그러한 지침을 모두 설명하는 것은 어렵다.
프로세스 모델링 모델의 품질
대부분의 가이드라인은 쉽게 실행되지 않지만, "동사-명사 활동 레이블 지정" 규칙은 다른 실무자들이 이전에 제안하고 경험적으로 분석했다.
연구에서 프로세스 모델의 가치는 그래픽 구성 요소의 선택뿐만 아니라 분석해야 할 텍스트 레이블로 주석을 다는 것에도 달려 있다는 것이 밝혀졌다. 그 결과 다른 레이블링 스타일보다 이해 측면에서 더 나은 모델을 생성한다는 것을 알 수 있었다.
이전 연구 및 프로세스 모델 품질 평가 방식에서 프로세스 모델의 크기, 구조, 모델러의 전문성 및 모듈성이 전반적인 이해도에 영향을 미친다는 것이 확인되었다.
 이를 바탕으로 7가지 프로세스 모델링 가이드라인(7PMG)이 제시되었다. 이 가이드라인은 동사-객체 스타일뿐만 아니라 모델의 요소 수, 구조화된 모델링의 적용, 프로세스 모델의 분해에 대한 가이드라인을 사용한다. 가이드라인은 다음과 같다.
7PMG는 여전히 다음과 같은 사용상의 한계를 가진다: 유효성 문제 7PMG는 프로세스 모델의 내용에 관련되지 않고, 오직 그 내용이 조직되고 표현되는 방식에만 관련된다.
이는 내용이 그대로 유지되는 동안 프로세스 모델의 다른 구조를 조직하는 방법을 제안하지만, 모델에 무엇을 포함해야 하는지에 대한 실용적인 문제는 여전히 남아 있다.
두 번째 한계는 우선순위 지정 가이드라인과 관련되어 있다. 도출된 순위는 21명의 프로세스 모델러의 참여에만 의존하므로 경험적 근거가 작다.
이는 한편으로 프로세스 모델러의 경험에 대한 더 넓은 참여의 필요성으로 볼 수 있지만, 다른 한편으로는 우선순위 지정 가이드라인에 도달하기 위한 다른 접근 방식이 무엇이 있을 수 있는지에 대한 질문을 제기한다.
배리어 (컴퓨터 과학)
병렬 컴퓨팅에서 배리어(barrier)는 동기화 방법의 일종이다. 소스 코드의 스레드 또는 프로세스 그룹에 대한 배리어는 모든 스레드/프로세스가 이 지점에서 멈춰야 하며, 다른 모든 스레드/프로세스가 이 배리어에 도달할 때까지 진행할 수 없음을 의미한다.
많은 집단 루틴과 지시문 기반 병렬 언어는 암시적 배리어를 부과한다. 예를 들어, OpenMP가 포함된 포트란의 병렬 do 루프는 마지막 반복이 완료될 때까지 어떤 스레드에서도 계속할 수 없다. 이는 프로그램이 루프 완료 직후의 결과에 의존하는 경우에 대비하기 위함이다. 메시지 전달에서, (리덕션 또는 스캐터와 같은) 모든 전역 통신은 배리어를 암시할 수 있다.
병행 컴퓨팅에서 배리어는 상승 또는 하강 상태일 수 있다. '래치'라는 용어는 때때로 상승 상태로 시작하여 하강 상태가 되면 다시 상승할 수 없는 배리어를 지칭하는 데 사용된다. '카운트다운 래치'라는 용어는 미리 정해진 수의 스레드/프로세스가 도착하면 자동으로 하강하는 래치를 지칭하는 데 사용되기도 한다.
배리어 (컴퓨터 과학) 구현
스레드 배리어로 알려진 스레드에 대한 예시를 살펴보자. 스레드 배리어는 배리어에 진입한 총 스레드 수를 추적하는 변수를 필요로 한다. 충분한 스레드가 배리어에 진입하면 배리어가 해제된다. 뮤텍스와 같은 동기화 기본요소 또한 스레드 배리어를 구현할 때 필요하다.
이 스레드 배리어 방법은 "중앙 배리어" 앞에서 대기해야 하는 스레드들이 예상된 수의 스레드가 배리어에 도달할 때까지 배리어가 해제되지 않는다는 점에서 중앙 집중식 배리어라고도 불린다.
다음은 POSIX 스레드를 사용하여 스레드 배리어를 구현한 C 코드이며, 이 절차를 보여준다:
이 프로그램에서 스레드 배리어는 struct _thread_barrier라는 구조체로 정의되며, 여기에는 다음이 포함된다:
배리어의 정의에 따라, 이 프로그램에서 배리어를 해제하기 위해 프로그램의 총 스레드 수를 "모니터링"할 thread_barrier_wait()와 같은 함수를 구현해야 한다.
이 프로그램에서 thread_barrier_wait()를 호출하는 모든 스레드는 THREAD_BARRIERS_NUMBER 수의 스레드가 스레드 배리어에 도달할 때까지 차단된다.
이 프로그램의 결과는 다음과 같다:
배리어 (컴퓨터 과학) 구현
프로그램에서 볼 수 있듯이, 생성된 스레드는 단 2개뿐이다. 이 두 스레드 모두 스레드 함수 핸들러로 thread_func()를 가지며, 이는 thread_barrier_wait(&barrier)를 호출한다. 반면 스레드 배리어는 해제되기 위해 3개의 스레드가 pthread_barrier_wait (THREAD_BARRIERS_NUMBER = 3)를 호출할 것으로 예상한다.

TOTAL_THREADS를 3으로 변경하면 스레드 배리어가 해제된다:
스레드 배리어를 성공적으로 통과한 모든 스레드에 대해 총 스레드 수를 1씩 감소시키는 것 외에도, 스레드 배리어는 스레드 상태를 통과 또는 중지로 표시하기 위해 반대 값을 사용할 수 있다. 예를 들어, 상태 값이 0인 스레드 1은 배리어에서 중지되었음을 의미하고, 상태 값이 1인 스레드 2는 배리어를 통과했음을 의미하며, 스레드 3의 상태 값 = 0은 배리어에서 중지되었음을 의미하는 식이다. 이는 센스 반전으로 알려져 있다.
다음 C 코드는 이를 보여준다:
이 프로그램은 이전 중앙 집중식 배리어 소스 코드와 유사한 모든 기능을 가지고 있다. 단지 2개의 새로운 변수를 사용하여 다른 방식으로 구현할 뿐이다:
배리어 (컴퓨터 과학) 구현
스레드가 배리어에서 멈추면 local_sense의 값이 토글된다. THREAD_BARRIERS_NUMBER 미만의 스레드가 스레드 배리어에서 멈출 때, 해당 스레드들은 struct _thread_barrier의 flag 멤버가 개인 local_sense 변수와 같지 않다는 조건 하에 계속 기다린다.
THREAD_BARRIERS_NUMBER 스레드가 스레드 배리어에서 정확히 멈추면 총 스레드 수는 0으로 재설정되고, flag는 local_sense로 설정된다.
중앙 집중식 배리어의 잠재적인 문제는 모든 스레드가 통과/정지를 위해 전역 변수에 반복적으로 접근하기 때문에 통신 트래픽이 상당히 높아서 확장성이 저하된다는 점이다.
이 문제는 스레드를 재그룹화하고 다단계 배리어(예: 결합 트리 배리어)를 사용하여 해결할 수 있다. 또한 하드웨어 구현은 더 높은 확장성의 이점을 가질 수 있다.
결합 트리 배리어는 모든 스레드가 동일한 위치에서 스핀하는 상황을 피함으로써 확장성 문제를 해결하기 위해 계층적인 방식으로 배리어를 구현하는 방법이다.
배리어 (컴퓨터 과학) 구현
k-트리 배리어에서 모든 스레드는 k개 스레드의 서브그룹으로 균등하게 나뉘고, 이 서브그룹 내에서 1차 동기화가 이루어진다. 모든 서브그룹이 동기화를 마치면 각 서브그룹의 첫 번째 스레드는 2차 동기화를 위해 다음 레벨로 진입한다. 2차 레벨에서는 1차 레벨과 마찬가지로 스레드들이 k개 스레드의 새로운 서브그룹을 형성하고 그룹 내에서 동기화하며, 각 서브그룹에서 하나의 스레드를 다음 레벨로 보내는 방식으로 진행된다. 결국, 최종 레벨에는 하나의 서브그룹만 동기화된다. 최종 레벨 동기화 후, 해제 신호가 상위 레벨로 전송되고 모든 스레드가 배리어를 통과한다.
하드웨어 배리어는 위의 기본 배리어 모델을 구현하기 위해 하드웨어를 사용한다.
가장 간단한 하드웨어 구현은 전용 와이어를 사용하여 신호를 전송함으로써 배리어를 구현한다. 이 전용 와이어는 OR/AND 연산을 수행하여 통과/차단 플래그 및 스레드 카운터 역할을 한다. 소규모 시스템에서는 이러한 모델이 작동하며 통신 속도가 주요 고려 사항이 아니다. 대규모 다중 프로세서 시스템에서 이 하드웨어 설계는 배리어 구현에 높은 지연 시간을 초래할 수 있다. 프로세서 간의 네트워크 연결은 지연 시간을 낮추는 한 가지 구현 방법이며, 이는 결합 트리 배리어와 유사하다.
배리어 (컴퓨터 과학) POSIX 스레드 배리어 함수
POSIX 스레드 표준은 직접적으로 스레드 배리어 함수를 지원하며, 이는 지정된 스레드 또는 전체 프로세스를 해당 배리어에 다른 스레드가 도달할 때까지 차단하는 데 사용될 수 있다. POSIX가 스레드 배리어를 구현하기 위해 지원하는 세 가지 주요 API는 다음과 같다:
pthread_barrier_init()
배리어를 해제하기 위해 배리어에서 대기해야 하는 스레드 수로 스레드 배리어를 초기화한다.
pthread_barrier_destroy()
스레드 배리어를 파괴하여 자원을 다시 해제한다.
pthread_barrier_wait()
이 함수를 호출하면 pthread_barrier_init()에서 지정한 수의 스레드가 pthread_barrier_wait()를 호출하여 배리어를 해제할 때까지 현재 스레드가 차단된다.
다음 예제(C로 pthread API를 사용하여 구현됨)는 스레드 배리어를 사용하여 메인 프로세스의 모든 스레드를 차단하고 따라서 전체 프로세스를 차단할 것이다:
이 소스 코드의 결과는 다음과 같다:
배리어 (컴퓨터 과학) POSIX 스레드 배리어 함수
소스 코드에서 볼 수 있듯이, 생성된 스레드는 단 두 개뿐이다. 이 두 스레드는 모두 스레드 함수 핸들러인 thread_func()를 가지며, 이는 pthread_barrier_wait(&barrier)를 호출한다. 반면 스레드 배리어는 해제되기 위해 3개의 스레드가 pthread_barrier_wait (THREAD_BARRIERS_NUMBER = 3)를 호출할 것으로 예상한다.

TOTAL_THREADS를 3으로 변경하면 스레드 배리어가 해제된다:
main()이 스레드로 취급되므로, 즉 프로세스의 "메인" 스레드이므로, main() 안에서 pthread_barrier_wait()를 호출하면 다른 스레드가 배리어에 도달할 때까지 전체 프로세스가 차단된다. 다음 예제는 main() 안에서 pthread_barrier_wait()를 사용하여 프로세스/메인 스레드를 5초 동안 차단하며, 이는 2개의 "새로 생성된" 스레드가 스레드 배리어에 도달하기를 기다리는 동안이다:
이 예제는 2개의 "새로 생성된" 스레드가 완료될 때까지 기다리기 위해 pthread_join()을 사용하지 않는다. 대신 main() 내에서 pthread_barrier_wait()를 호출하여 메인 스레드를 차단하므로, 2개의 스레드가 5초 대기(9행 - sleep(5)) 후 작업을 완료할 때까지 프로세스가 차단된다.
C++ AMP
C++ AMP(C++ Accelerated Massive Parallelism)는 C++ 프로그래밍 언어와 해당 런타임 라이브러리의 요소를 포함하는 네이티브 프로그래밍 모델이다. 이 모델은 데이터 병렬 하드웨어(예: 그래픽 카드 및 그래픽 처리 장치(GPU))에서 컴파일 및 실행되는 프로그램을 쉽게 작성하는 방법을 제공한다.
비주얼 스튜디오 2022(버전 17.0)부터 C++ AMP는 더 이상 지원되지 않는 것으로 선언되어 비주얼 스튜디오 2022 이후에는 지원이 종료된다.
C++ AMP는 DirectX 11에 구현된 라이브러리이며, C++에서 데이터 병렬 처리를 직접 구현하기 위한 마이크로소프트의 개방형 사양이다. 이는 개발자가 GPU 프로그래밍을 쉽게 할 수 있도록 지원하며, GPU 프로그래밍에 대한 경험이 없는 경우에도 시스템이 최선을 다해 처리하거나, 더 세밀하게 제어할 수 있으면서도 이식성을 유지하도록 의도되었다. 마이크로소프트 구현에서는 GPU에서 실행할 수 없는 코드는 대신 하나 이상의 CPU로 대체되어 SSE 명령어를 사용한다. 마이크로소프트 구현은 디버거 및 프로파일러 지원을 포함하여 비주얼 스튜디오 2012에 포함되어 있다.
C++ AMP
마이크로소프트의 초기 C++ AMP 릴리스는 최소 윈도우 7 또는 윈도우 서버 2008 R2를 필요로 한다. C++ AMP는 개방형 사양이므로 시간이 지남에 따라 마이크로소프트 외부에서도 구현이 등장할 것이다. 이러한 초기 사례 중 하나는 클랭–LLVM 및 오픈 컴퓨팅 언어(OpenCL)에서 C++ AMP를 인텔의 실험적 구현인 Shevlin Park이다.
2013년 11월 12일, HSA 재단은 현재 C++ AMP 사양을 지원하는 OpenCL, Standard Portable Intermediate Representation (SPIR) 및 HSA Intermediate Language (HSAIL)로 출력하는 C++ AMP 컴파일러를 발표했다. 소스 코드는 https://github.com/RadeonOpenCompute/hcc에서 사용할 수 있다. C++ AMP 지원은 구식으로 간주되며, 현재 ROCm 1.9 시리즈가 이를 지원하는 마지막 버전이 될 것이다.
C++ 클래스를 사용하여 병렬 및 이기종 프로그래밍 기능을 표현하는 것과 같은 C++AMP의 기본 개념은 SYCL 표준에 영감을 주었다.
C++ AMP 기능
마이크로소프트는 C++ AMP 가속기에서 함수가 실행될 수 있음을 선언하기 위해 어떤 함수(람다 포함)에도 적용할 수 있는 restrict(amp) 기능을 추가했다. 컴파일러는 관리 및 별도의 언어를 사용할 필요 없이 자동으로 컴퓨트 커널을 생성한다. restrict 키워드는 컴파일러에게 함수가 대부분의 GPU에서 지원되는 언어 기능만 사용하는지 정적으로 확인하도록 지시한다. 예를 들어, void myFunc() restrict(amp) {…} 와 같이 사용할 수 있다.
마이크로소프트 또는 개방형 C++ AMP 사양의 다른 구현자는 C++ AMP와 관련 없는 목적을 포함하여 다른 목적을 위한 다른 restrict 지정자를 추가할 수 있다.
C++ AMP 기능
새로운 언어 기능 외에 C++ AMP의 나머지 기능은 동시성(concurrency) 네임스페이스의 <amp.h> 헤더 파일을 통해 사용할 수 있다. 주요 C++ AMP 클래스는 다음과 같다: array(가속기의 데이터 컨테이너), array_view(데이터 래퍼), index(N차원 점), extent(N차원 크기), accelerator(메모리를 할당하고 실행할 GPU와 같은 계산 리소스), accelerator_view(가속기의 뷰). 전역 함수 parallel_for_each는 병렬 루프를 작성할 수 있도록 한다.
핍홀 최적화
핍홀 최적화(Peephole optimization)는 핍홀 또는 윈도우로 알려진 소규모 컴파일러 생성 명령어 집합에 대해 수행되는 최적화 기법으로, 해당 명령어를 더 나은 성능을 가진 논리적으로 동등한 집합으로 대체하는 것을 포함한다.
예시:
핍홀 최적화라는 용어는 1965년에 윌리엄 마샬 매키먼이 도입했다.
핍홀 최적화 대체
핍홀 최적화 대체에는 다음이 포함되지만 이에 국한되지 않는다:
핍홀 최적화 구현
최신 컴파일러는 종종 패턴 매칭 알고리즘으로 핍홀 최적화를 구현한다.
핍홀 최적화 예시
다음 자바 바이트코드:
은 더 빠르게 실행되는 다음 코드로 대체될 수 있다:
대부분의 핍홀 최적화와 마찬가지로, 이는 다른 명령어들의 상대적 효율성을 기반으로 한다. 이 경우, `dup` (스택의 맨 위를 복제하고 푸시하는)은 `aload` (지역 변수를 로드하고 스택에 푸시하는)보다 더 효율적인 것으로 알려져/가정된다.
다음 소스 코드:
는 간단히 다음과 같이 컴파일된다:
하지만 다음으로 최적화할 수 있다:
컴파일러가 서브루틴을 호출하기 전에 레지스터를 스택에 저장하고 반환할 때 복원하는 경우, 연속적인 서브루틴 호출에는 중복된 스택 명령어가 있을 수 있다.
핍홀 최적화 예시
컴파일러가 각 프로시저 호출에 대해 다음 Z80 명령어를 생성한다고 가정하자:
두 개의 연속적인 서브루틴 호출이 있다면 다음과 같이 보일 것이다:
동일한 레지스터에 대해 POP regs 뒤에 PUSH가 오는 시퀀스는 일반적으로 중복된다. 중복되는 경우, 핍홀 최적화는 이 명령어들을 제거할 것이다. 이 예시에서는 핍홀에 또 다른 중복 POP/PUSH 쌍이 나타나게 되고, 이들은 차례로 제거될 것이다. 서브루틴 _ADDR2가 이전 레지스터 값에 의존하지 않는다고 가정하면, 위 예시의 모든 불필요한 코드를 제거하면 결국 다음 코드가 남게 될 것이다:
루프 불변 코드 이동
컴퓨터 프로그래밍에서 루프 불변 코드는 프로그램의 의미론에 영향을 주지 않고 루프 본문 밖으로 이동할 수 있는 명령문 또는 표현식( 명령형 프로그래밍 프로그래밍 언어에서)으로 구성된다. 루프 불변 코드 이동(Loop-invariant code motion, 호이스팅 또는 스칼라 승격이라고도 함)은 이 이동을 자동으로 수행하는 컴파일러 최적화이다.
루프 불변 코드 이동 예시
다음 코드 샘플에는 두 가지 최적화가 적용될 수 있다.
x = y + z와 x * x 계산은 루프 불변이지만, 코드를 루프 밖으로 이동하기 전에 주의를 기울여야 한다. 루프 조건이 false일 가능성(예: n이 음수 값을 가질 경우)이 있으며, 이 경우 루프 본문은 전혀 실행되지 않아야 한다. 올바른 동작을 보장하는 한 가지 방법은 루프 외부에 조건부 분기를 사용하는 것이다. 루프 조건을 평가하는 것은 부작용을 가질 수 있으므로, if 구성에 의한 추가 평가는 while 루프를 do {} while로 대체하여 보상해야 한다. 코드가 처음부터 do {} while을 사용했다면, 루프 본문이 최소 한 번 실행될 것이 보장되므로 전체 보호 프로세스가 필요 없다.
이 코드는 더욱 최적화될 수 있다. 예를 들어, 강도 감소는 루프 내의 두 곱셈(6*i 및 a[i])을 제거할 수 있고, 유도 변수 제거는 i를 완전히 생략할 수 있다. 6 * i는 i 자체와 동기화되어야 하므로 둘 다 가질 필요는 없다.
루프 불변 코드 이동 불변 코드 감지
일반적으로, 도달 정의 분석은 명령문이나 표현식이 루프 불변인지 감지하는 데 사용된다.
예를 들어, 어떤 단순 표현식의 피연산자에 대한 모든 도달 정의가 루프 밖에 있다면, 그 표현식은 루프 밖으로 이동될 수 있다.
모이앙, 루비아노, 세이예의 최근 연구는 데이터 흐름 의존성 분석을 사용하여 불변 명령어뿐만 아니라 내부 루프와 같은 더 큰 코드 조각도 감지한다. 이 분석은 또한 임의의 차수의 준불변, 즉 루프 본문의 고정된 반복 횟수 후에 불변이 되는 명령어 또는 코드 조각을 감지한다. 이 기술은 후에 오베르, 루비아노, 루쉬, 세이예에 의해 루프를 자동으로 병렬화하는 데 사용되었다.
루프 불변 코드 이동 장점
루프 밖으로 이동된 루프 불변 코드는 더 적게 실행되어 속도를 향상시킨다. 이 변환의 또 다른 효과는 상수를 레지스터에 저장하고 각 반복마다 주소를 계산하고 메모리(또는 캐시 라인)에 접근할 필요가 없다는 것이다.
그러나 너무 많은 변수가 생성되면, 특히 32비트 X86과 같이 레지스터가 적은 프로세서에서는 레지스터 압박이 높아진다. 컴파일러가 레지스터를 다 소진하면 일부 변수는 레지스터 스필링된다. 이를 상쇄하기 위해 역최적화인 재자료화가 수행될 수 있다.
고래자리 은하군
고래자리 A 은하군은 고래자리 A를 중심으로 한 작은 은하군이다.
고래자리 은하군 다른 이름
이 은하군을 NGC 1068 은하군(NGC 1068 Group)이라고도 한다.
루프 언롤링
루프 언롤링(Loop unrolling) 또는 루프 언와인딩(loop unwinding)은 프로그램의 이진 크기를 늘리는 대신 실행 속도를 최적화하려는 루프 변환 기술로, 이는 공간-시간 트레이드오프라고 알려진 접근 방식이다. 변환은 프로그래머가 수동으로 수행하거나 최적화 컴파일러가 수행할 수 있다. 최신 프로세서에서는 루프 언롤링으로 인해 코드 크기가 증가하여 캐시 미스가 더 많이 발생할 수 있으므로 역효과를 낼 때가 많다. 더프의 장치를 참고하라.
루프 언와인딩의 목표는 각 반복에서 포인터 연산 및 "루프 끝" 테스트와 같이 루프를 제어하는 명령어를 줄이거나 제거하여 프로그램의 속도를 높이는 것이다. 분기 페널티를 줄이고, 메모리에서 데이터를 읽는 지연을 포함한 대기 시간을 숨기는 것이다. 이러한 계산 오버헤드를 제거하기 위해 루프는 유사한 독립적인 명령문의 반복 시퀀스로 다시 작성될 수 있다.
루프 언롤링은 또한 특정 형식 검증 기술, 특히 유한 모델 검사의 일부이다.
루프 언롤링 장점
"타이트한" 루프의 오버헤드는 종종 배열의 다음 요소에 대한 포인터나 인덱스를 증가시키는 명령어(포인터 연산)와 "루프 종료" 테스트로 구성된다. 최적화 컴파일러나 어셈블러가 개별적으로 참조되는 각 배열 변수에 대한 오프셋을 미리 계산할 수 있다면, 이들은 기계어 명령어에 직접 내장될 수 있으므로 런타임에 추가적인 산술 연산이 필요하지 않다.
최적화 컴파일러는 때때로 자동으로 또는 요청에 따라 언롤링을 수행한다.
루프 언롤링 단점
코드 크기 증가: 언롤링은 명령어 수를 늘려 프로그램 이진 파일을 더 크게 만든다.
높은 저장 요구 사항: 확장된 코드는 더 많은 메모리를 차지하며, 이는 마이크로컨트롤러나 제한된 저장 공간을 가진 임베디드 시스템에 문제가 될 수 있다.
명령어 캐시 압력: 언롤링된 루프는 명령어 캐시에서 더 많은 공간을 소비한다. 캐시 크기를 초과하면 빈번한 캐시 미스가 발생하여 값비싼 메모리 접근으로 인해 심각한 성능 저하가 발생할 수 있다.
분기 예측: 최신 CPU는 분기 예측을 사용하여 분기가 어느 방향으로 갈지 추측하려고 한다. 예측이 정확하면 CPU는 분기가 해결될 때까지 기다리지 않고 명령어를 계속 실행할 수 있다. 그러나 예측이 잘못되면 CPU는 파이프라인을 비우고 올바른 명령어를 실행하기 시작해야 하며, 이는 성능 저하를 초래할 수 있다. 루프 언롤링은 코드 내 분기 수를 증가시켜 더 많은 분기 오예측과 낮은 성능으로 이어질 수 있다.
루프 언롤링 정적/수동 루프 언롤링
수동 (또는 정적) 루프 언롤링은 프로그래머가 루프를 분석하고 반복을 루프 오버헤드를 줄이는 일련의 명령어로 해석하는 것을 포함한다. 이는 컴파일러에 의해 수행되는 동적 언롤링과는 대조된다.
컴퓨터 프로그램의 한 절차는 컬렉션에서 100개의 항목을 삭제하는 것이다. 이는 일반적으로 delete(item_number) 함수를 호출하는 `for` 루프를 통해 수행된다. 이 프로그램 부분이 최적화되어야 하고, 루프의 오버헤드가 delete(x) 함수에 비해 상당한 리소스를 요구하는 경우, 언와인딩을 사용하여 속도를 높일 수 있다.
이 수정의 결과로 새 프로그램은 100번 대신 20번만 반복하면 된다. 그 후에는 점프와 조건부 분기의 20%만 수행하면 되며, 이는 많은 반복에 걸쳐 루프 관리 오버헤드의 잠재적으로 상당한 감소를 나타낸다. 최적의 이점을 얻으려면 언롤링된 코드에 포인터 연산이 필요한 변수를 지정해서는 안 된다. 이는 일반적으로 인덱스 참조 방식 대신 "기준 주소 + 오프셋" 주소 지정을 필요로 한다.
루프 언롤링 정적/수동 루프 언롤링
반면에 이 수동 루프 언롤링은 원본 코드 크기를 3줄에서 7줄로 확장하며, 이는 작성, 확인, 디버깅해야 한다. 또한 컴파일러는 확장된 루프 반복에서 변수를 저장하기 위해 더 많은 레지스터를 할당해야 할 수도 있다. 게다가, 언롤링된 루프 구조 내의 루프 제어 변수와 연산 횟수는 결과가 원래 코드와 동일하도록 신중하게 선택해야 한다(이미 작동하는 코드에 대한 후속 최적화라고 가정할 때). 예를 들어, 반복 횟수가 5로 나누어지지 않는 경우의 영향을 고려해 보라. 테스트 조건이 변수인 경우 수동 수정 사항은 다소 더 복잡해진다. 더프의 장치도 참조하라.
간단한 경우, 루프 제어는 생산적인 명령문을 배열하는 단순한 관리 오버헤드이다. 루프 자체는 원하는 결과에 아무런 기여도 하지 않으며, 단지 프로그래머가 코드를 백 번 복제하는 지루함을 덜어줄 뿐이다. 이는 전처리가 복제를 생성하거나 텍스트 편집기가 수행할 수 있었던 일이다. 마찬가지로, `if` 문 및 기타 흐름 제어 문은 코드 복제로 대체될 수 있지만, 코드 블롯이 발생할 수 있다. 컴퓨터 프로그램은 조합을 쉽게 추적하지만, 프로그래머는 이러한 반복을 지루해하며 실수를 저지른다.
고려해 보자:
루프 언롤링 정적/수동 루프 언롤링
그러나 물론 수행되는 코드가 프로시저 호출일 필요는 없으며, 다음 예시에서는 계산에 인덱스 변수가 포함된다.
이것이 컴파일되면 많은 코드를 생성할 수 있지만(프린트 문이 악명 높음), 추가 최적화가 가능하다. 이 예시는 루프에서 x(i)와 x(i - 1)만을 참조한다(후자는 새로운 값 x(i)를 개발하기 위해서만). 따라서 여기서 개발된 배열 x에 대한 나중 참조가 없다고 가정하면, 그 사용은 단순 변수로 대체될 수 있다. 그러나 그러한 변경은 값이 변경되는 단순 변수를 의미할 것이지만, 배열을 유지한다면 컴파일러의 분석은 배열의 값이 상수이며, 각각 이전 상수에서 파생되었음을 인지하고 상수 값을 전달하여 코드가 다음과 같이 될 것이다.
일반적으로 루프의 내용은 크고 복잡한 배열 인덱싱을 포함할 수 있다. 이러한 경우는 최적화 컴파일러가 언롤링하는 것이 가장 좋다. 내부 루프를 복제하면 많은 최적화가 가능하지만, n이 크지 않으면 작은 이득만 얻을 수 있다.
다음과 유사한 의사코드 WHILE 루프를 고려해 보자.
이 경우, ENDWHILE(루프 시작으로 점프)이 66% 덜 실행되므로 언롤링이 더 빠르다.
심지어 더 좋은 것은 일부 최적화 컴파일러가 자동으로 수행할 수 있는 "조정된" 의사코드 예시로, 무조건 점프를 완전히 제거한다.
루프 언롤링 동적 언롤링
루프 언롤링의 이점은 종종 배열의 크기에 따라 달라지며, 이는 런타임까지 알 수 없는 경우가 많기 때문에 JIT 컴파일러는 (예를 들어) "표준" 루프 시퀀스를 호출할지 아니면 각 요소에 대해 (상대적으로 짧은) 개별 명령어 시퀀스를 생성할지 결정할 수 있다. 이러한 유연성은 루프 언롤링의 맥락에서 정적 또는 수동 최적화와 비교하여 JIT 기술의 장점 중 하나이다. 이 상황에서는 n의 값이 비교적 작을 때 절약 효과가 여전히 유용하며, 프로그램 크기 전체적으로 거의 (또는 전혀) 증가시키지 않는다 (이는 표준 라이브러리의 일부로 한 번만 포함될 수 있다).
어셈블리어 프로그래머(최적화 컴파일러 개발자 포함)도 효율적인 분기 테이블에 사용되는 방법과 유사한 방법을 사용하여 동적 루프 언롤링 기술의 이점을 얻을 수 있다. 여기서 장점은 특정 배열에서 참조되는 필드의 최대 오프셋이 기계어 명령어로 지정할 수 있는 최대 오프셋보다 작은 경우에 가장 크다(초과하면 어셈블러가 플래그를 표시한다).
루프 언롤링 동적 언롤링
이 예시는 IBM/360 또는 Z/아키텍처 어셈블러를 위한 것으로, FROM 배열에서 TO 배열로 100바이트 필드(오프셋 0)를 복사하는 것을 가정한다. 두 배열 모두 50개의 항목을 가지며 각 요소의 길이는 256바이트이다.
이 예시에서는 "기존" 루프(50회 반복)를 사용하면 약 202개의 명령어가 필요하지만, 위 동적 코드는 약 89개의 명령어만 필요하므로 약 56%의 절약 효과가 있다. 배열에 두 개의 항목만 포함되어 있었다면, 원래 언롤링된 루프와 거의 같은 시간으로 실행되었을 것이다. 배열에 수천 개의 항목이 있더라도 코드 크기 증가는 약 108바이트에 불과하다.
여러 명령어가 관련되어 있는 경우에도 결합된 명령어 길이가 그에 따라 조정되는 한 유사한 기술을 사용할 수 있다. 예를 들어, 이 동일한 예시에서 복사된 100바이트 필드 직후에 각 배열 항목의 나머지를 널 문자로 지워야 하는 경우, 추가 지우기 명령어인 `XC xx*256+100(156,R1),xx*256+100(R2)`를 시퀀스의 모든 MVC 바로 뒤에 추가할 수 있다(여기서 `xx`는 위 MVC의 값과 일치한다).
루프 언롤링 동적 언롤링
물론, 단일 어셈블러 매크로 명령문을 사용하여 위 코드를 "인라인"으로 생성하고 네다섯 개의 피연산자만 지정하거나(또는 간단한 호출로 접근할 수 있는 라이브러리 서브루틴으로 만들어 매개변수 목록을 전달하는 방식으로), 최적화를 쉽게 사용할 수 있도록 하는 것이 완벽하게 가능하다.
다음 예시는 C로 작성된 간단한 프로그램에 대한 동적 루프 언롤링을 보여준다. 위 어셈블러 예시와 달리, 이 예시에서는 변수 (i)가 여전히 배열 요소를 주소 지정하는 데 사용되므로 컴파일러가 여전히 포인터/인덱스 연산을 생성한다. 완전한 최적화는 대체 명령문에서 절대 인덱스를 사용하는 경우에만 가능하다.
코드 중복은 더프의 장치와 같이 두 부분을 함께 작성하여 피할 수 있다.
출처:
다음 예시는 double 타입의 100개 항목 벡터 A와 B의 스칼라곱을 계산할 것이다. C 언어 코드는 다음과 같다:
다음은 루프 언롤링을 구현하기 전에 100개 항목의 벡터 A와 B의 스칼라곱을 계산하는 MIPS 어셈블리어 코드이다. 아래 코드는 루프 초기화를 생략한다.
배열의 한 요소 크기(a `double`)는 8바이트이다.
다음은 위와 같지만, 4배로 루프 언롤링을 구현한 것이다. 배열의 한 요소 크기(a `double`)는 8바이트이므로 0, 8, 16, 24 변위와 각 루프의 32 변위를 다시 참고한다.
강도 감소
컴파일러 구성에서 강도 감소 또는 스트렝스 리덕션(strength reduction)은 비용이 많이 드는 연산을 동등하지만 비용이 적게 드는 연산으로 대체하는 컴파일러 최적화이다. 강도 감소의 고전적인 예는 루프 내의 강한 곱셈을 약한 덧셈으로 변환하는 것으로, 이는 배열 주소 지정에서 자주 발생한다.(Cooper, Simpson & Vick 1995, 1쪽)
강도 감소의 예로는 루프 내의 곱셈을 덧셈으로 대체하고 루프 내의 거듭제곱을 곱셈으로 대체하는 것이 있다.
강도 감소 코드 분석
프로그램 실행 시간의 대부분은 일반적으로 코드의 작은 부분(핫 스팟이라고 불림)에서 소비되며, 이 코드는 종종 반복적으로 실행되는 루프 내에 있다.
컴파일러는 루프를 식별하고 해당 루프 내의 레지스터 값 특성을 인식하는 방법을 사용한다. 강도 감소를 위해 컴파일러가 관심을 갖는 것은 다음과 같다.
루프 불변은 본질적으로 루프 내에서 상수이지만, 그 값은 루프 외부에서 변경될 수 있다. 유도 변수는 알려진 양만큼 변경된다. 이 용어는 특정 루프에 상대적이다. 루프가 중첩될 때, 바깥쪽 루프의 유도 변수는 안쪽 루프의 루프 불변이 될 수 있다.
강도 감소는 루프 불변과 유도 변수를 포함하는 표현식을 찾는다. 이러한 표현식 중 일부는 단순화될 수 있다. 예를 들어, 루프 불변 c와 유도 변수 i의 곱셈은
연속적인 약한 덧셈으로 대체될 수 있다.
강도 감소 강도 감소 예제
다음은 배열 인덱싱 주소 계산에서 발생한 모든 루프 곱셈을 강도 감소시키는 예제이다.
배열을 단위 행렬로 설정하는 간단한 루프를 상상해 보자.
컴파일러는 이 코드를 다음과 같이 볼 것이다.
이것은 2차원 배열 A를 n*n 크기의 1차원 배열로 표현하므로, 고수준 코드가 A[x, y]를 표현할 때마다 유효한 모든 인덱스 x와 y에 대해 내부적으로 A[(x*n)+y]가 된다.
컴파일러는 강도 감소뿐만 아니라 많은 최적화를 시작한다. 루프 내에서 상수(불변)인 표현식은 루프 밖으로 끌어올려진다. 부동 소수점 레지스터 fr3 및 fr4와 같은 상수는 두 루프 외부에서 로드될 수 있다. 일부 변수가 변경되지 않는다는 인식은 레지스터를 병합할 수 있게 한다. n은 상수이므로 r2, r4, r7, r12는 끌어올려지고 병합될 수 있다. 공통 값 i*n은 (끌어올려진) r8과 r13에서 계산되므로, 이들은 합쳐진다. 가장 안쪽 루프(0120-0260)는 11개에서 7개의 중간 명령어로 감소되었다. 가장 안쪽 루프에 남아있는 유일한 곱셈은 0210번 줄의 8 곱셈이다.
강도 감소 강도 감소 예제
더 많은 최적화가 필요하다. 레지스터 r3은 가장 안쪽 루프(0140-0260)의 주요 변수이다. 루프를 통과할 때마다 1씩 증가한다. 레지스터 r8(가장 안쪽 루프에서 불변)이 r3에 더해진다. 컴파일러는 r3 대신 r3을 제거하고 r9를 사용할 수 있다. 루프는 r3 = 0에서 n-1까지 제어되는 대신 r9=r8+0에서 r8+n-1까지 제어될 수 있다. 이는 4개의 명령어를 추가하고 4개의 명령어를 제거하지만, 루프 내부에는 하나의 명령어가 더 적다.
이제 r9가 루프 변수이지만, 8을 곱하는 연산과 상호작용한다. 여기에서 우리는 강도 감소를 할 수 있다. 8을 곱하는 연산은 8을 연속적으로 더하는 것으로 줄일 수 있다. 이제 루프 안에 곱셈 연산이 없다.
레지스터 r9와 r10(= 8*r9) 모두 필요하지 않다. 루프에서 r9를 제거할 수 있다. 이제 루프는 5개의 명령어로 구성된다.
전체 그림으로 돌아가서:
이제 r1을 증가시키는 외부 루프 내에 4개의 곱셈이 있다. 0190번 줄의 r8 = r1*r2는 루프 진입 전(0055번 줄)에 설정하고 루프 하단(0385번 줄)에서 r2만큼 증가시켜 강도 감소할 수 있다.
강도 감소 강도 감소 예제
값 r8*8(0118번 줄)은 초기화(0056번 줄)하고 r8이 증가할 때 8*r2를 더하여(0386번 줄) 강도 감소할 수 있다.
레지스터 r20은 루프를 통과할 때마다 0117번 줄에서 불변/상수 r2에 의해 증가하고 있다. 증가된 후 8을 곱하여 0119번 줄에서 r22를 생성한다. 이 곱셈은 루프를 통과할 때마다 8*r2를 더함으로써 강도 감소할 수 있다.
이제 두 루프는 외부 루프 내에 하나의 곱셈 연산(0330번 줄)만 남고 내부 루프에는 곱셈 연산이 없다.
0320번 줄에서 r14는 r8과 r1의 합이며, r8과 r1은 루프 내에서 증가하고 있다. 레지스터 r8은 r2(=n)만큼 증가하고 r1은 1만큼 증가한다. 결과적으로 r14는 루프를 통과할 때마다 n+1만큼 증가한다. 0330번 줄의 마지막 루프 곱셈은 루프를 통과할 때마다 (r2+1)*8을 더함으로써 강도 감소될 수 있다.
아직 더 남았다. 상수 폴딩은 프롤로그에서 r1=0임을 인식하여 여러 명령어를 정리할 것이다. r8은 루프에서 사용되지 않으므로 사라질 수 있다.
게다가, r1은 루프를 제어하기 위해서만 사용되므로, r1은 r40과 같은 다른 유도 변수로 대체될 수 있다. i가 0 <= i < n으로 갔던 곳에서, 레지스터 r40은 0 <= r40 < 8 * n * n으로 간다.
강도 감소 다른 강도 감소 연산
연산자 강도 감소는 수학적 항등식을 사용하여 느린 수학 연산을 더 빠른 연산으로 대체한다. 이점은 대상 CPU와 때로는 주변 코드(CPU 내의 다른 기능 단위의 가용성에 영향을 미칠 수 있음)에 따라 달라진다.
강도 감소 유도 변수 (고아)
유도 변수 또는 재귀적 강도 감소는 체계적으로 변하는 변수의 함수를 함수의 이전 값을 사용하여 더 간단한 계산으로 대체한다. 절차형 프로그래밍 언어에서는 루프 변수를 포함하는 표현식에 적용되며, 선언형 프로그래밍 언어에서는 재귀 함수의 인수에 적용된다. 예를 들어,
는 다음과 같이 된다.
여기서 수정된 재귀 함수 f′는 두 번째 매개변수 z = 3 ** x를 사용하여 비용이 많이 드는 계산 (3 ** x)을 더 저렴한 (3 * z)로 대체할 수 있게 한다.
강도 감소 각주
Allen, Francis E.; Cocke, John; Kennedy, Ken (1981), 〈Reduction of Operator Strength〉,   Munchnik, Steven S.; Jones, Neil D., 《Program Flow Analysis: Theory and Applications》, Prentice-Hall, ISBN 978-0-13-729681-1
Cocke, John; Kennedy, Ken (November 1977), “An algorithm for reduction of operator strength”, 《Communications of the ACM》 20 (11): 850–856, doi:10.1145/359863.359888, S2CID 1092505
공통 부분식 제거
컴파일러 이론에서 공통 부분식 제거(Common subexpression elimination, CSE)는 동일한 식의 인스턴스를 찾고(즉, 모두 동일한 값으로 평가됨), 계산된 값을 포함하는 단일 변수로 대체하는 것이 가치가 있는지 분석하는 컴파일러 최적화이다.
공통 부분식 제거 예시
다음 코드에서:
코드를 다음과 같이 변환하는 것이 가치가 있을 수 있다.
tmp를 저장하고 검색하는 비용이 b * c를 추가로 계산하는 비용보다 적은 경우이다.
공통 부분식 제거 원리
CSE를 수행할 가능성은 사용 가능한 식 분석(일종의 데이터 흐름 분석)을 기반으로 한다. 식 b*c는 프로그램의 지점 p에서 다음 경우에 사용 가능하다.
옵티마이저가 수행하는 비용/편익 분석은 tmp에 저장하는 비용이 곱셈 비용보다 적은지 계산한다. 실제로 어떤 값이 어떤 레지스터에 저장되어 있는지와 같은 다른 요인들도 중요하다.
컴파일러 개발자들은 두 가지 종류의 CSE를 구분한다.
두 가지 모두 프로그램의 어떤 지점에서 어떤 식이 사용 가능한지에 대한 데이터 흐름 분석에 의존한다.
공통 부분식 제거 이점
CSE를 수행하는 이점은 매우 커서 일반적으로 사용되는 최적화이다.
위 예시와 같은 간단한 경우에 프로그래머는 코드를 작성하면서 중복 식을 수동으로 제거할 수 있다. CSE의 가장 큰 원천은 컴파일러가 생성하는 중간 코드 시퀀스인데, 예를 들어 배열 인덱싱 계산과 같이 개발자가 수동으로 개입할 수 없는 경우이다. 어떤 경우에는 언어 기능이 많은 중복 식을 생성할 수 있다. 예를 들어, C 매크로의 경우, 매크로 확장이 원래 소스 코드에서는 명확하지 않은 공통 부분식을 초래할 수 있다.
컴파일러는 값을 저장하기 위해 생성되는 임시 변수의 수를 신중하게 결정해야 한다. 과도한 수의 임시 값은 레지스터 압력을 생성하여 메모리로 레지스터 스필링을 초래할 수 있으며, 이는 필요할 때 단순히 산술 결과를 재계산하는 것보다 더 오래 걸릴 수 있다.
상수 폴딩
상수 폴딩(constant folding)과 상수 전파(constant propagation)는 많은 현대 컴파일러에서 사용되는 관련 컴파일러 최적화 기법이다. 희소 조건부 상수 전파로 알려진 상수 전파의 고급 형태는 상수를 더 정확하게 전파하고 동시에 불필요한 코드를 제거할 수 있다.
상수 폴딩 상수 폴딩
상수 폴딩은 런타임에 계산하는 대신 컴파일 타임에 상수 표현식을 인식하고 평가하는 과정이다. 상수 표현식의 항은 일반적으로 정수 리터럴 2와 같은 단순 리터럴이지만, 컴파일 타임에 값이 알려진 변수일 수도 있다. 다음 문장을 살펴보자.
대부분의 컴파일러는 이 문장에 대해 실제로 두 개의 곱셈 명령과 하나의 저장 명령을 생성하지 않는다. 대신 이러한 구문을 식별하고 컴파일 타임에 계산된 값(이 경우 2,048,000)으로 대체한다.
상수 폴딩은 산술 항등식을 활용할 수 있다. x가 숫자이면 컴파일러가 x의 값을 모르더라도 0 * x의 값은 0이다. (이것은 x가 무한대나 NaN일 수 있으므로 IEEE 부동소수점에서는 유효하지 않다는 점에 유의한다.)
상수 폴딩은 숫자 외에도 적용될 수 있다. 문자열 리터럴과 상수 문자열의 연결은 상수 폴딩될 수 있다. "abc" + "def"와 같은 코드는 "abcdef"로 대체될 수 있다.
상수 폴딩 상수 폴딩과 크로스 컴파일
크로스 컴파일러를 구현할 때 호스트 아키텍처의 산술 연산 동작이 대상 아키텍처의 동작과 일치하는지 확인해야 한다. 그렇지 않으면 상수 폴딩을 활성화하면 프로그램의 동작이 변경된다. 이는 부동소수점 연산의 경우 특히 중요하며, 정밀한 구현이 크게 다를 수 있다.
상수 폴딩 상수 전파
상수 전파는 컴파일 타임에 표현식에서 알려진 상수의 값을 대체하는 과정이다. 이러한 상수에는 위에 정의된 상수뿐만 아니라 상수 값에 적용된 내장 함수도 포함된다. 다음 의사 코드를 살펴보자.
x를 전파하면 다음과 같다.
계속 전파하면 다음과 같은 결과가 나온다 (이는 x와 y 모두에 대한 불필요한 코드 제거를 통해 추가로 최적화될 가능성이 높다.)
상수 전파는 정의 도달 분석 결과를 사용하여 컴파일러에 구현된다. 변수의 모든 도달 정의가 동일한 할당(동일한 상수를 변수에 할당하는)인 경우 변수는 항상 동일한 값을 가지므로 상수로 대체될 수 있다.
상수 전파는 또한 조건 표현식이 컴파일 타임에 참 또는 거짓으로 평가되어 유일한 가능한 결과를 결정할 수 있는 경우 조건부 분기를 하나 이상의 무조건 명령문으로 단순화할 수 있다.
상수 폴딩 최적화의 작동 방식
상수 폴딩과 전파는 많은 단순화 및 감소를 달성하기 위해 일반적으로 함께 사용되며, 이러한 효과가 멈출 때까지 번갈아 가며 반복적으로 적용된다.
분석을 기다리는 알 수 없는 숫자를 반환하는 최적화되지 않은 다음 의사 코드를 살펴보자.
상수 전파를 한 번 적용한 다음 상수 폴딩을 적용하면 다음과 같다.
두 단계를 두 번 반복하면 다음과 같다.
변수 a와 b의 모든 사용을 상수로 대체했으므로 컴파일러의 불필요한 코드 제거가 해당 변수에 적용되어 다음과 같이 남는다.
(불리언 구성은 언어와 컴파일러마다 다르지만, 참의 상태, 원본 및 표현과 같은 세부 사항은 이러한 최적화 원칙에 영향을 미치지 않는다.)
전통적인 상수 전파는 더 이상의 최적화를 생성하지 않는다. 프로그램을 재구성하지 않는다.
그러나 유사한 최적화인 희소 조건부 상수 전파는 적절한 조건부 분기를 선택하고 항상 참인 조건부 테스트를 제거하여 더 나아간다. 따라서 변수 c는 불필요해지고 상수 연산만 남는다.
만약 이 의사 코드가 함수 본문을 구성한다면, 컴파일러는 이 함수가 정수 상수 4로 평가된다는 것을 알게 되어 함수 호출을 4로 대체하고 프로그램 효율성을 더욱 높일 수 있다.
정적 단일 대입 형식
컴파일러 설계에서 정적 단일 대입 형식(Static single-assignment form, SSA 형식 또는 단순히 SSA로 약칭)은 각 변수가 정확히 한 번 할당되는 중간 표현 (IR)의 한 유형이다. SSA는 LLVM, GNU 컴파일러 모음 및 많은 상업용 컴파일러를 포함하여 명령형 언어에 대한 대부분의 고품질 최적화 컴파일러에서 사용된다.
프로그램을 SSA 형식으로 변환하기 위한 효율적인 알고리즘이 있다. SSA로 변환하기 위해 원래 IR의 기존 변수들은 버전으로 분할되며, 일반적으로 원래 이름에 아래첨자가 붙어 각 정의가 고유한 버전을 갖도록 한다. 두 제어 흐름 경로의 조인 지점에 변수의 새 버전에 할당하는 추가 문도 도입해야 할 수 있다. SSA 형식에서 기계 코드로 변환하는 것도 효율적이다.