소프트웨어 파이프라인화

컴퓨터 과학에서 소프트웨어 파이프라인은 하드웨어 파이프라인과 유사한 방식으로 루프를 최적화하기 위해 사용되는 기술입니다.소프트웨어 파이프라인은 순서가 잘못된 실행의 한 종류입니다.단, 순서 변경은 프로세서가 아닌 컴파일러(또는 손으로 작성한 어셈블리 코드의 경우 프로그래머)에 의해 이루어집니다.일부 컴퓨터 아키텍처는 소프트웨어 파이프라인링을 명시적으로 지원하고 있습니다.특히 인텔의 IA-64 아키텍처입니다.

중복 루프 반복의 타겟 코드 기술인 소프트웨어 파이프라인과 소프트웨어 파이프라인 루프 생성을 위한 현재 알려진 가장 효과적인 컴파일러 기술인 모듈로 스케줄링의 구별이 중요합니다.소프트웨어 파이프라이닝은 그러한 아키텍처가 존재한 이래로 명령 수준의 병렬 처리를 가진 기계의 언어 프로그래머를 조립하는 것으로 알려져 왔다.이러한 코드의 효과적인 컴파일러 생성은 Rau와 Glaeser에 ^[1]의한 모듈로 스케줄링의 발명으로 거슬러 올라간다.Lam은 효과적인 모듈로 스케줄링을 위해 특별한 하드웨어가 필요하지 않음을 보여주었습니다.그녀의 기술인 모듈로 변수 확대는 ^[2]실제로 널리 사용되고 있다.Gao 등은 최적의 소프트웨어 파이프라인을 정수 선형 프로그래밍으로 공식화하여 평가서에서 ^[3]고급 휴리스틱스를 검증했다.이 논문은 그 주제에 대한 참고 문헌이 풍부하다.

예

다음 루프를 고려합니다.

i = 1의 경우 A(i) B(i) C(i) 엔드를 Bignumber한다.

이 예에서는,A(i),B(i),C(i)각각 데이터로 동작하는 명령어입니다.i서로 종속되어 있습니다.바꿔 말하면A(i)전에 완료해야 합니다.B(i)기동할 수 있습니다.예를들면,A메모리에서 레지스터로 데이터를 로드할 수 있습니다.B데이터에 대해 산술 연산을 수행할 수 있습니다.C데이터를 메모리에 저장할 수 있습니다.단, 서로 다른 값에 대한 연산 사이에 의존하지 않도록 합니다.i다른 말로 하자면A(2)보다 먼저 시작할 수 있다A(1)종료됩니다.

소프트웨어 파이프라이닝을 사용하지 않으면 다음 순서로 작업이 실행됩니다.

A(1) B(1) C(1) A(2) B(2) C(2) A(3) B(3) C(3) ... 

각 명령을 완료하는 데 3개의 클럭 사이클이 걸린다고 가정합니다(루핑 제어 흐름의 비용은 무시합니다).또한 (대부분의 최신 시스템에서와 마찬가지로) 이미 실행 중인 명령에 의존하지 않는 한 사이클마다 명령을 디스패치할 수 있다고 가정합니다.따라서 줄이 쳐지지 않은 경우 각 반복을 완료하는 데9 사이클이 소요됩니다.A(1), 3 클럭 사이클:B(1), 및 의 3 클럭사이클C(1).

이제 소프트웨어 파이프라인에 대한 다음 일련의 지침을 검토합니다.

A(1) A(2) B(1) B(3) B(3) C(1) C(2) C(3) ... 

각 사이클마다 명령을 디스패치할 수 있다는 것을 쉽게 확인할 수 있습니다. 즉, 동일한 3회 반복을 총 9회 반복하여 1회당 평균 3회 반복할 수 있습니다.

실행

소프트웨어 파이프라이닝은 루프 언롤링과 조합하여 사용하는 경우가 많습니다.이러한 기술의 조합은 루프 언롤링만 하는 것보다 훨씬 좋은 최적화가 될 수 있습니다.위의 예에서는 다음과 같이 코드를 쓸 수 있습니다(당분간은bignumber3으로 나눌 수 있다:

i = 1 ~ (bignumber - 2) 3단계 A(i) A(i+1) A(i+1) B(i+1) B(i+1) C(i+1) C(i+2) 끝

물론, (통상 그렇듯이) 전체 반복 횟수가 풀리는 반복 횟수에 따라 나누어질 수 있다는 보장을 할 수 없다면 문제는 복잡합니다.이 문제의 해결책에 대한 자세한 내용은 루프 언롤링에 관한 기사를 참조해 주십시오.단, 소프트웨어 파이프라인으로 인해 Duff의 ^{[citation needed]}디바이스를 사용할 수 없습니다.

일반적인 경우 루프 언롤링은 소프트웨어 파이프라인을 구현하는 최선의 방법이 아닐 수 있습니다.대기 시간이 긴 명령이 포함된 루프를 고려합니다.예를 들어 다음과 같은 코드가 있습니다.

i = 1 to bignumber A(i); 3사이클 지연 B(i); 3C(i); 12(부동소수점 연산) D(i); 3E(i); 3F(i); 3end

명령의 병목 현상을 피하기 위해 루프를 12회 반복해야 합니다.C이는 루프의 코드가 12배 증가함을 의미합니다(메모리 사용량에 영향을 줄 뿐만 아니라 캐시 성능에도 영향을 줄 수 있습니다). 코드 블러트 참조).더 나쁜 것은 프롤로그(루프 전의 코드)입니다.bignumber12로 나누어지지 않음)은 루프용 코드보다 더 클 수 있으며, 이 코드에서는 소프트웨어 파이프라인을 사용할 수 없기 때문에 매우 비효율적일 수 있습니다(적어도 상당한 양의 추가 코드 블러트가 없는 한).게다가 만약bignumber는 전개된 반복 횟수(10~20회 등)에 비해 크기가 중간 정도일 것으로 예상되며, 실행은 대부분의 시간을 이 비효율적인 프롤로그 코드로 소비하여 소프트웨어 파이프라인 최적화를 무효로 합니다.

한편, 이 예에 대응하는 소프트웨어 파이프라인은 다음과 같습니다(프롤로그와 에필로그는 나중에 설명하겠습니다).

i = 1 to (bignumber - 6 ) A(i+6) B(i+5) C(i+4) D(i+2)의 프롤로그; i+3 E(i+1) F(i) 종료 에필로그를 건너뜁니다.

루프의 시작과 끝의 반복을 처리하는 프롤로그와 에필로그에 들어가기 전에 이 코드가 루프의 중간에 있는 반복에 대해 원래 코드와 동일한 기능을 수행하는지 확인합니다.구체적으로는 원래 루프에서의 반복7을 검토해 주십시오.파이프라인 루프의 첫 번째 반복은 원래 루프의 반복 7로부터의 명령을 포함하는 첫 번째 반복입니다.순서는 다음과 같습니다.

반복 1:A(7) B(6) C(5) D(3) E(2) F(1)

반복 2:A(8) B(7) C(6) D(4) E(3) F(2)

반복 3:A(9) B(8) C(7) D(5) E(4) F(3)

반복 4:A(10) B(9) C(8) D(6) E(5) F(4)

반복 5:A(11) B(10) C(9) D(7) E(6) F(5)

반복 6:A(12) B(11) C(10) D(8) E(7) F(6)

반복 7:A(13) B(12) C(11) D(9) E(8) F(7)

그러나 원래 루프와 달리 파이프라인 버전은 명령 시 병목 현상을 방지합니다.C에 주의해 주세요.C(7)및 종속 명령D(7)즉, 명령의 레이텐시 사이클이C(7)는 낭비되는 대신 다른 지침에 사용됩니다.

프롤로그와 에필로그는 루프의 시작과 끝에서 반복을 처리합니다.위의 예에서 생각할 수 있는 프롤로그를 다음에 나타냅니다.

; 루프 프롤로그(명확하게 하기 위해 행에 배치) A(1) A(3), B(2), C(1) A(4), B(3), C(2), A(1)를 기동할 수 없지만 A(5), B(4), C(3), D(1) A(6)는 기동할 수 없습니다.

위의 각 선은 주 파이프라인 루프의 반복에 해당하지만 아직 시작되지 않은 반복에 대한 지침은 없습니다.마찬가지로 에필로그는 완료된 반복에 대한 지침을 점진적으로 제거합니다.

; loop epilogue (명확성을 위해 행에 배열)B(bignumber), C(bignumber-1), D(bignumber-3), D(bignumber-5) C(bignumber-4), D(bignumber-2), E(bignumber-4), F(bignumber-4) dignumber

구현의 어려움

프롤로그와 에필로그의 요건은 소프트웨어 파이프라인 실장의 주요 어려움 중 하나입니다.이 예의 프롤로그는 루프 자체의 3배인 18개의 명령어입니다.후기는 또한 18개의 지시사항일 것이다.즉, 프롤로그와 에필로그를 합친 크기는 루프 자체의 6배입니다.이 예에서는 루프 롤링을 시도하는 것보다도 소프트웨어 파이프라이닝에서는 속도와 메모리 사용률의 균형을 맞출 필요가 있습니다.또한 코드 블러트가 너무 크면 캐시 성능 저하로 인해 속도에 영향을 미친다는 점도 유의하십시오.

또 다른 어려움은 많은 아키텍처에서 대부분의 명령어는 레지스터를 인수로 사용하며 사용하는 특정 레지스터는 명령어에 하드 코딩되어야 한다는 것입니다.즉, 많은 아키텍처에서 이러한 명령어를 "레지스터의 내용을 다중화"하는 것은 불가능하다.X등록하다Y그리고 결과를 레지스터에 올린다.Z", 어디서X,Y,그리고.Z는 다른 레지스터 또는 메모리에서 가져온 번호입니다.이는 기존 아키텍처에서 소프트웨어 파이프라인을 효과적으로 구현할 수 없는 이유로 자주 언급되어 왔습니다.

실제로 모니카 램은 논문 'A Systolic Array Optimizing Compiler (1989)'에서 이 문제에 대한 우아한 해결책을 제시했습니다. ISBN0-89838-300-5).그녀는 이것을 모듈로 변수 확장이라고 부릅니다.이 트릭은 루프가 스케줄된 후 본문을 복제하여 동시에 활성화해야 할 경우 동일한 변수의 다른 값에 다른 레지스터를 사용할 수 있도록 하는 것입니다.가장 간단한 예를 들어 다음과 같이 가정해 봅시다.A(i)그리고.B(i)병렬로 발행할 수 있으며 전자의 지연은 2사이클입니다.파이프라인 본체는 다음과 같습니다.

A(i+2); B(i)

이 루프 본체의 레지스터 할당은 다음 결과에서 발생하는 문제에 직면합니다.A(i+2)2회 반복 라이브를 유지해야 합니다.결과에 동일한 레지스터 사용A(i+2)및 의 입력B(i)잘못된 결과를 초래합니다.

단, 스케줄된 루프바디를 복제하면 문제가 해결됩니다.

A(i+2); B(i)A(i+3); B(i+1)

이제 개별 레지스터를 다음 결과에 할당할 수 있습니다.A(i+2)그리고.A(i+3)좀 더 구체적으로 말하면:

r1 = A(i+2); B(i) = r1 r2 = A(i+3); B(i+1) = r2 i = i + 2 // 확실히 하기 위해

각 명령 번들이 출력 레지스터를 쓰기 전에 입력 레지스터를 읽는다는 가정 하에 이 코드는 정확합니다.복제된 루프 본체의 시작 부분에서r1가치를 가지고 있다A(i+2)루프가 반복되고 있습니다.부터i그 사이에 2씩 증가했습니다.이것은 실제의 값입니다.A(i)이 반복 루프의 반복에 사용됩니다.

물론 코드 복제는 프롤로그나 에필로그와 마찬가지로 코드 크기와 캐시 압력을 높입니다.그럼에도 불구하고 충분한 명령어레벨 병렬성을 가진 아키텍처에서 트립 카운트가 큰 루프의 경우, 이 기술은 코드 크기를 늘릴 가치가 있을 만큼 충분히 잘 작동합니다.

IA-64 구현

인텔의 IA-64 아키텍처는 소프트웨어 파이프라인의 어려움을 고려하여 설계된 아키텍처의 예를 제공합니다.소프트웨어 파이프라인에 대한 아키텍처 지원에는 다음이 포함됩니다.

• "회전" 레지스터 뱅크. 명령은 루프가 반복될 때마다 다른 레지스터로 리다이렉트되는 레지스터 번호를 참조할 수 있습니다(결국 선두로 루프백).따라서 이전 예에서 삽입된 추가 명령이 필요하지^[specify] 않습니다.
• 특수 루프 명령에서 값을 가져오는 술어(명령어를 "예약"하는 데 사용됩니다. 분기 술어 참조).이러한 술어는 루프의 특정 명령을 켜거나 끄므로 별도의 프롤로그와 에필로그가 필요하지 않습니다.

레퍼런스