멀티 쓰레드 프로그램 설계를 위한 8가지 규칙
멀티 쓰레드 프로그램을 위한 8가지 규칙
'The Art of Concurrency' 책의 챕터 4 영문을 번역한 글입니다.
https://www.oreilly.com/library/view/the-art-of/9780596802424/ch04.html
이 책의 제목에 바로 포함되어 있기 때문에 다음 문장 은 놀라운 일이 아닙니다. 동시 프로그래밍은 여전히 과학보다 예술 입니다. 이 장에서는 스레딩 설계 방법 툴킷에 추가 할 수있는 간단한 8 가지 규칙을 제공합니다.
순서대로 규칙을 구성하려고 시도했지만 규칙에 대한 엄격한 순서는 없습니다. “수영장에서 달리기 금지”,“얕은 곳에서 다이빙 금지”에 대하는 것과 같습니다. 다이빙을 안하는 사건이 수영장에서 달리는 사건에 비해 먼저 일어나거나 반대 순서로도 일어날 수 있습니다.
이러한 규칙을 따르면 응용 프로그램의 가장 효율적인 스레드 구현을 작성하는 데 더 많은 성공을 거둘 수 있습니다. 이전 장에서 그 중 일부를 언급 했으므로이 중 일부를 인식 할 수 있습니다. 다음 장에서는 특정 알고리즘의 설계 및 구현에 대해 논의 할 때 여덟 개의 규칙 중 하나 이상에 대한 관련 참조를 추가하여 추가 장을 작성하기 위해 여기에 있지 않음을 보여 드리겠습니다.
규칙 1 : 완전히 독립적인 계산을 식별
필자는이 첫 번째 규칙을 일요일까지 7 가지 방법으로 이미 다루었지만 전체 문제의 요점이므로 적어도 한 번 더 반복해야합니다. 실행될 작업이 서로 독립적으로 실행될 수 없다면 어떤 것도 동시에 실행할 수 없습니다. 단일 목표를 달성하기 위해 수행되는 서로 다른 실제 행동 사례를 쉽게 생각할 수 있습니다. 예를 들어 DVD 대여 창고를 생각해봅시다. 영화 주문은 수집되어 Worker에게 배포됩니다. Worker는 모든 디스크가 저장된 위치로 이동하여 지정된 주문을 충족시키기 위해 사본을 찾습니다. 한 Worker가 클래식 뮤지컬 코미디를 꺼낼 때 최신 공상 과학 작품을 찾고있는 다른 Worker를 방해하지 않으며, 인기있는 범죄 드라마 시리즈의 두 번째 시즌에서 에피소드를 찾으려고하는 Worker를 방해하지도 않습니다 (주문이 창고로 전송되기 전에 재고가 없어서 발생하는 모든 충돌이 해결 된 것으로 가정합니다). 또한 각 주문의 포장 및 우편 발송은 디스크 검색이나 다른 주문의 운송 및 처리를 방해하지 않습니다.
동시에 수행 할 수없는 순차 순차 계산이있는 경우가 있습니다. 이들 중 다수는 특정 순서로 수행해야하는 루프 반복 또는 단계 간의 종속성입니다. 일반적인 상황 목록은 이전 의 병렬 기능에서 설명했습니다 .
규칙 2 : 가능한 가장 높은 수준에서 동시성 구현
직렬 코드 스레딩에 접근 할 때 취할 수있는 두 가지 방향이 있습니다. 이것들은 상향식 과 하향식 입니다. 코드를 처음 분석 할 때는 실행 시간이 가장 많은 계산 핫스팟을 찾고 있습니다. 이러한 부분을 병렬로 실행하면 가능한 최대 성능을 얻을 수있는 최상의 기회가 제공됩니다.
상향식 접근 방식에서는 코드에 핫스팟을 직접 스레딩하는 것이 좋습니다. 이것이 가능하지 않은 경우, 응용 프로그램의 호출 스택을 검색하여 코드에 핫스팟을 병렬로 실행할 수있는 다른 위치가 있는지 판별하십시오. 핫스팟이 중첩 루프 구조의 가장 안쪽 루프 인 경우, 가장 안쪽에서 바깥 쪽까지 루프 중첩의 각 연속 레이어를 검사하여 해당 레벨을 동시에 수행 할 수 있는지 확인하십시오. 핫스팟 코드에서 동시성을 사용할 수 있더라도 호출 스택에서 코드의 상위 위치에서 해당 동시성을 구현할 수 있는지 확인해야합니다. 이것은 각 스레드가 수행하는 실행의 세분성을 증가시킬 수 있습니다.
이 규칙을 설명하려면 비디오 인코딩 응용 프로그램을 스레딩하는 것이 좋습니다. 핫스팟이 개별 픽셀의 계산 인 경우 단일 비디오 프레임 내에서 각 픽셀 계산을 처리하는 루프를 병렬화 할 수 있습니다. 이것으로부터 더“위로”보면, 비디오 프레임에 대한 루프는 독립적으로 프레임 그룹을 처리함으로써 동시에 실행될 수 있습니다. 비디오 인코딩 응용 프로그램이 여러 비디오를 처리 할 것으로 예상되는 경우 각 스레드에 다른 스트림을 할당하여 동시성을 표현하는 것이 가능한 동시성 수준입니다.
스레딩에 대한 다른 접근 방식은 하향식으로, 먼저 전체 응용 프로그램과 계산을 수행하도록 코딩 된 항목 (해당 계산을 실현하기 위해 결합하는 응용 프로그램의 모든 부분)을 고려합니다. 명백한 동시성은 없지만, 여전히 핫스팟 실행을 포함하는 계산 부분을 독립적 인 계산을 식별 할 수있을 때까지 작은 부분으로 증류하십시오.
비디오 인코딩 응용 프로그램의 경우 핫스팟이 개별 픽셀의 계산 인 경우 하향식 접근 방식은 먼저 응용 프로그램이 여러 개의 독립적 인 비디오 스트림 (모두 픽셀 계산 포함)의 인코딩을 처리하는 것으로 간주합니다. 거기에서 응용 프로그램을 병렬화 할 수 있다면 가장 높은 수준을 발견 한 것입니다. 그렇지 않은 경우 개별 픽셀로“아래로”작업하면 단일 스트림 내의 프레임을 통과 한 다음 프레임 내의 픽셀로 이동합니다.
이 규칙의 목적은 코드 핫스팟이 동시에 실행될 수 있도록 동시성을 구현할 수있는 최고 수준을 찾는 것입니다. 이것은 알고리즘의 레이어에서 "높은"레벨이 유리의 파르페 레이어가 질량을 더 많이 축적하는 방식과 같이 더 많은 (독립적 인) 작업과 동일하다는 믿음을 전제로합니다. 핫스팟 주위에 가능한 한 높은 수준에서 동시성을 배치하는 것은 스레드에 할당 할 가장 중요한 굵은 단위 작업을 달성하는 가장 좋은 방법 중 하나입니다.
규칙 3 : 증가하는 코어 수를 활용하기 위한 확장성 조기 계획
이 글을 쓰는 동안 쿼드 코어 프로세서가 기본 멀티 코어 칩이되었습니다. 향후 프로세서에서 사용할 수있는 코어 수는 증가 할 것입니다. 따라서 소프트웨어 내에서 이러한 프로세서 증가를 계획해야합니다. 확장 성은 시스템 리소스 (예 : 코어 수, 메모리 크기, 버스 속도) 또는 데이터 세트 크기의 변경을 처리하고 일반적으로 증가하는 응용 프로그램의 기능을 측정 한 것입니다. 더 많은 코어를 사용할 수있는 상황에서는 다양한 수의 코어를 활용할 수있는 유연한 코드를 작성해야합니다.
C. Northcote Parkinson은 다음과 같이 설명합니다.“사용 가능한 처리 능력을 채우기 위해 데이터가 확장됩니다.”이것은 계산 능력이 증가할수록 (더 많은 코어) 처리 될 데이터가 확장 될 가능성이 높아짐을 의미합니다. 수행해야 할 계산이 항상 더 있습니다. 과학 시뮬레이션에서 모델 충실도를 높이거나 표준 비디오 대신 HD 스트림을 처리하거나 여러 개의 더 큰 데이터베이스를 검색하든 추가 처리 리소스가 제공되면 처리 할 데이터가 더 많은 사람이 있습니다.
데이터 분해 방법으로 동시성을 설계 및 구현하면보다 확장 가능한 솔루션이 제공됩니다. 작업 분해 솔루션은 응용 프로그램의 독립 함수 또는 코드 세그먼트 수가 실행 중에 제한되고 고정 될 수 있다는 사실로 인해 어려움을 겪을 것입니다. 각 독립 작업에 실행할 스레드와 코어가 있으면 더 많은 코어를 활용하기 위해 스레드 수를 늘려도 응용 프로그램의 성능이 향상되지 않습니다. 데이터 크기는 애플리케이션에서 독립적 인 계산 수보다 증가 할 가능성이 높으므로 데이터 분해 설계는 확장 가능성이 가장 높습니다.
독립 기능에 할당 된 스레드를 사용하여 응용 프로그램을 작성했지만 입력 워크로드가 증가하더라도 더 많은 스레드를 계속 사용할 수 있습니다. 유한 한 수의 개별 작업을 수행 할 수있는 식료품 점을 짓는 것을 고려하십시오. 개발자가 인접한 토지를 구입하고 매장의 바닥 공간을 두 배로 늘리면 이러한 작업 중 일부에 추가 근로자가 배정 될 수 있습니다. 즉, 여분의 화가, 여분의 지붕 꾼, 여분의 바닥 타일러 및 여분의 전기 기술자를 사용할 수 있습니다. 따라서 태스크로 분해 된 솔루션 내에서도 증가 된 데이터 세트에서 발생할 수있는 데이터 분해 가능성을 알고 여분의 코어에서 추가 스레드를 사용하도록 계획해야합니다.
규칙 4 : 가능하면 스레드 안전 라이브러리 사용
라이브러리 호출을 통해 핫스팟 계산을 실행할 수있는 경우 필기 코드를 실행하는 대신 동등한 라이브러리 함수를 사용하는 것이 좋습니다. 직렬 응용 프로그램의 경우에도 최적화 된 라이브러리 루틴으로 이미 캡슐화 된 계산을 수행하는 코드를 작성하여 "바퀴를 재창조"하는 것은 결코 좋은 생각이 아닙니다. Intel Math Kernel Library (MKL) 및 Intel IPP (Integrated Performance Primitives)와 같은 많은 라이브러리에는 멀티 코어 프로세서를 활용하기 위해 스레드 기능이 있습니다.
그러나 스레드 라이브러리 루틴을 사용하는 것보다 훨씬 중요한 것은 사용 된 모든 라이브러리 호출이 스레드 안전하다는 것입니다. 직렬 코드의 핫스팟을 라이브러리 함수에 대한 호출로 교체 한 경우에도 애플리케이션의 호출 트리에서 더 높은 지점이 독립적 인 계산으로 나눌 수 있습니다. 라이브러리 함수 호출, 특히 써드 파티 라이브러리를 실행하는 동시 계산이있는 경우 라이브러리 내의 공유 변수를 참조하고 업데이트하는 루틴으로 인해 데이터 경쟁이 발생할 수 있습니다. 동시 실행 내에서 사용중인 라이브러리의 스레드 안전성에 대해서는 라이브러리 문서를 확인하십시오. 동시에 실행될 자체 라이브러리 루틴을 작성하고 사용할 때 루틴이 재진입해야합니다. 이것이 가능하지 않은 경우
규칙 5 : 올바른 스레딩 모델 사용
스레드 라이브러리가 응용 프로그램의 모든 동시성을 처리하기에 충분하지 않고 사용자 제어 스레드를 사용해야하는 경우 암시적 스레딩 모델 (예 : OpenMP 또는 Intel Threading Building Blocks)에 필요한 모든 기능이있는 경우 명시적 스레드를 사용하지 마십시오. 명시적 스레드는 스레딩 구현을보다 세밀하게 제어 할 수 있습니다. 그러나 계산 집약적 루프 만 병렬화하거나 명시적 스레드로 얻을 수있는 추가 유연성이 필요하지 않은 경우에는 필요한 것보다 더 많은 작업을 수행 할 이유가 없습니다. 구현이 복잡할수록 실수를 저지르기 쉽고 나중에 이러한 코드를 유지하기가 더 어려워집니다.
OpenMP는 데이터 분해 방법, 특히 대규모 데이터 세트에 걸쳐있는 스레딩 루프를 대상으로합니다. 이것이 응용 프로그램에 도입 할 수있는 유일한 병렬 처리 유형 인 경우에도 OpenMP 사용을 금지하는 외부 요구 사항 (예 : 고용주 또는 관리 환경 설정에 따라 지정된 엔지니어링 관행)이있을 수 있습니다. 이 경우 승인 된 (명시 적) 모델로 스레딩을 구현해야합니다. 이러한 상황에서는 OpenMP를 사용하여 계획된 동시성을 프로토 타입하고 잠재적 인 성능 향상, 가능한 확장 성 및 명시 적 스레드로 직렬 코드를 스레딩하는 데 얼마나 많은 노력이 필요한지 추정하는 것이 좋습니다.
규칙 6 : 특정 실행 순서를 가정하지 마십시오
직렬 계산을 사용하면 프로그램의 다른 명령문에 따라 실행될 명령문을 쉽게 예측할 수 있습니다. 반면 스레드의 실행 순서는 비결정 적이고 OS 스케줄러에 의해 제어됩니다. 즉, 한 실행에서 다른 실행으로 실행되는 스레드의 순서를 예측하거나 다음에 실행될 스레드를 예측할 수있는 확실한 방법이 없습니다. 이는 특히 스레드보다 코어 수가 적은 시스템에서 실행될 때 응용 프로그램 내에서 실행 대기 시간을 숨기기 위해 수행됩니다. 캐시에 없거나 I / O 요청을 처리하기 위해 메모리가 필요하기 때문에 스레드가 차단되면 스케줄러는 차단 된 스레드를 교체하고 실행할 준비가 된 스레드를 교체합니다.
데이터 경쟁은 이러한 비결 정성 스케줄링의 직접적인 결과입니다. 다른 스레드가 해당 값을 읽기 전에 한 스레드가 값을 공유 변수에 기록한다고 가정하면 항상 옳을 수도 있고, 때때로 옳을 수도 있고, 그렇지 않을 수도 있습니다. 운이 좋으면 응용 프로그램을 실행할 때마다 특정 플랫폼에서 스레드 실행 순서가 변경되지 않는 경우가 있습니다. 시스템 (디스크의 비트 위치 또는 메모리 소켓 또는 벽면 소켓에서 나오는 AC 전원의 주파수) 사이의 모든 차이는 스레드 일정을 변경할 가능성이 있습니다. 긍정적 인 사고를 통해서만 시행되는 스레드 중 특정 실행 순서에 의존하는 코드는 데이터 경쟁 및 교착 상태와 같은 문제에 시달릴 수 있습니다.
성능 측면에서 볼 때 그레이하운드 나 레이스의 순종과 같이 스레드가 최대한 방해받지 않도록하는 것이 가장 좋습니다. 반드시 필요한 경우가 아니면 특정 실행 순서를 강요하지 마십시오. 절대적으로 필요한 시간을 인식하고 스레드의 실행 순서를 서로 조정하기 위해 동기화 형식을 구현해야합니다.
이어 달리기 경주를 생각해보세요. 첫 번째 주자는 가능한 빨리 달리기 시작합니다. 그러나 레이스를 성공적으로 완료하려면 두 번째, 세 번째 및 앵커 주자가 배턴을 받기 전에 대기해야합니다. 배턴 패스는 레이스에서 스테이지 간의 "실행"순서를 제어하는 연속 러너 간의 동기화입니다.
규칙 7 : 가능한 경우 스레드 로컬 스토리지 사용 또는 특정 데이터에 Lock 설정
동기화는 응용 프로그램의 병렬 실행에서 정확한 응답이 생성되도록 보장하는 것을 제외하고는 계산 향상에 기여하지 않는 오버 헤드입니다. 동기화는 필요한 악입니다. 그럼에도 불구하고, 동기화 양을 최소로 유지하기 위해 적극적으로 노력해야합니다. 스레드에 로컬 인 스토리지를 사용하거나 독점 메모리 위치 (예 : 스레드 ID로 색인화 된 배열 요소)를 사용하여이를 수행 할 수 있습니다.
임시 작업 변수는 스레드간에 거의 공유되지 않으며 각 스레드에 로컬로 선언되거나 할당되어야합니다. 각 스레드에 대해 부분 결과를 보유하는 변수는 스레드에 대해 로컬이어야합니다. 부분 결과를 공유 위치로 결합하려면 동기화가 필요합니다. 공유 업데이트가 가능한 한 드물게 수행되도록하면 오버 헤드 양이 최소로 유지됩니다. 명시 적 스레드를 사용하는 경우 사용 가능한 스레드 로컬 스토리지 API를 사용하여 한 스레드 영역에서 다른 스레드 영역으로 또는 스레드에서 하나의 스레드 함수 호출에서 동일한 함수의 다음 실행에 로컬로 데이터를 지속시킬 수 있습니다.
각 스레드에 대한 로컬 스토리지가 유효한 옵션이 아니며 동기화 오브젝트 (예 : 잠금)를 통해 공유 자원에 대한 액세스를 조정해야하는 경우 잠금을 데이터 항목에 올바르게 연관 (또는 "첨부")해야합니다. 가장 쉬운 방법은 데이터 항목에 대한 일대일 (1 : 1) 잠금 관계를 갖는 것입니다. 항상 함께 액세스되는 여러 공유 변수가있는 경우 단일 잠금을 사용하여 이러한 변수와 관련된 모든 중요 영역에 독점적으로 액세스 할 수 있습니다. 이후 장에서는 특히 대규모 데이터 수집 (예 : 10,000 개 항목의 배열)에 대한 액세스를 보호해야하는 경우 사용할 수있는 일부 트레이드 오프 및 대체 동기화 기술에 대해 설명합니다.
그러나 잠금을 데이터 항목과 연관 시키려면 하나 이상의 잠금을 단일 데이터 오브젝트에 연관시키지 마십시오. 시걸의 법칙에 따르면“시계를 가진 사람은 몇 시인 지 알고 있습니다. 이 시계를 가진 사람은 결코 확실하지 않습니다. "두 개의 서로 다른 잠금, - 말 객체 경우 lockA와 lockB 같은 변수에 -protect 액세스 코드의 한 부분이 사용할 수 lockA 코드의 다른 부분은 사용할 수 있지만 액세스를 위해 lockB 이 두 코드 부분에서 실행되는 스레드는 데이터 레이스를 생성합니다. 각 레이스는 컨테스트 된 데이터에 독점적으로 액세스 할 수 있기 때문입니다.
규칙 8 : 동시성 향상을위한 알고리즘 변경
직렬 및 동시 애플리케이션의 성능을 비교할 때 가장 중요한 것은 벽시계 실행 시간입니다. 두 개 이상의 알고리즘 중에서 선택할 때 프로그래머는 점근 적 실행 순서에 의존 할 수 있습니다. 이 지표는 거의 항상 응용 프로그램의 상대 성능과 다른 성능의 상관 관계가 있습니다. 즉, 다른 모든 것이 일정하게 유지되면 Quicksort와 같은 O (n log n) 알고리즘 을 사용하는 응용 프로그램 은 O (n 2 ) 알고리즘 (예 : 선택 정렬) 보다 빠르게 실행 되며 동일한 결과를 생성합니다.
동시 응용 프로그램에서 더 나은 점근선 실행 순서를 가진 알고리즘도 더 빠르게 실행됩니다. 그럼에도 불구하고 최고의 직렬 알고리즘이 병렬화에 적합하지 않을 때가 있습니다. 핫스팟을 스레드 코드로 쉽게 전환 할 수없는 경우 (및 동시에 수행 할 수있는 핫스팟의 호출 스택에서 더 높은 지점을 찾을 수없는 경우) 현재 알고리즘이 아닌 차선책 직렬 알고리즘을 사용하여 변환하는 것을 고려해야합니다. 코드에서.
예를 들어, 두 정사각 행렬의 곱셈에 대한 선형 대수 연산을 고려하십시오. Strassen의 알고리즘은 가장 점근 적으로 실행되는 순서 중 하나 인 O (n 2.81 ) 입니다. 이것은 O (n 3 ) 보다 낫다 전통적인 트리플 네스트 루프 알고리즘. Strassen의 방법은 각 행렬을 4 개의 청크 (또는 하위 행렬)로 나누고 7 개의 재귀 호출을 사용하여 n / 2 × n / 2 하위 행렬을 곱합니다. 이러한 재귀 호출을 병렬화하기 위해 7 개의 독립적 인 서브 매트릭스 곱셈을 각각 실행할 새 스레드를 만들 수 있습니다. 실의 수는 기하 급수적으로 증가 할 것입니다 (세인트 아이브스에서 오는 아내, 자루, 고양이 및 새끼 고양이처럼). 서브 매트릭스가 점점 작아짐에 따라 새로 작성된 스레드에 지정된 할당 된 작업의 입도는 더 세밀 해집니다. 하위 행렬이 지정된 크기를 달성하면 직렬 알고리즘으로 전환하십시오.
행렬 곱셈을 병렬화하는 훨씬 쉬운 방법은 점증 적으로 열등한 3 중 루프 알고리즘을 사용하는 것입니다. 행렬에서 데이터 분해를 수행하고 (행으로 나누기, 열로 나누기 또는 블록으로 나누기) 여러 가지 방법으로 스레드에 필요한 계산을 할당 할 수 있습니다. 루프 수준 중 하나에서 OpenMP pragma를 사용하거나 필요에 따라 루프 인덱스 나누기를 구현하는 명시 적 스레드를 사용하여이 작업을 수행 할 수 있습니다. 더 간단한 직렬 알고리즘에는 코드 수정이 덜 필요하며 Strassen의 알고리즘을 스레드하려고 시도 할 때보 다 코드 구조가 손상되지 않을 수 있습니다. 더 좋은 방법은 간단한 규칙 4를 따르고 행렬-행렬 곱셈을 수행하는 동시 라이브러리 함수를 사용하는 것입니다.
요약
직렬 응용 프로그램을 동시 버전으로 변환하는 스레딩을 설계 할 때 명심해야 할 8 가지 간단한 규칙을 설명했습니다. 여기에 제시된 규칙을 따르면보다 강력하고 스레딩 문제가 발생할 가능성이 적으며 개발 시간이 줄어 최적의 성능을 향한 동시 솔루션을보다 쉽게 만들 수있었습니다. 여러분이 잘 해낼 것이라 믿습니다.
