칠크

Cilk, Cilk++, Cilk Plus 및 OpenCilk는 멀티스레드 병렬 컴퓨팅용으로 설계된 범용 프로그래밍 언어입니다.C 및 C++ 프로그래밍 언어에 기반하며 병렬 루프와 포크-조인 관용어를 표현하기 위한 구성으로 확장됩니다.

원래는 1990년대에 매사추세츠 공과대학(MIT)에서 찰스 E의 그룹에 의해 개발되었습니다. Leiserson, Cilk는 나중에 스피노프 회사인 Cilk Arts에 의해 Cilk++로 상품화되었습니다.그 후, 그 회사는 인텔에 인수되어 기존의 C 및 C++ 코드와의 호환성이 향상되어, Cilk Plus라고 불리고 있습니다.2017년 인텔이 Cilk Plus 지원을 중단한 후 MIT는 다시 OpenCilk 형태로 Cilk를 개발하고 있습니다.

역사

MIT Cilk

Cilk 프로그래밍 언어는 MIT 컴퓨터 ^[2]사이언스 연구소의 세 가지 프로젝트에서 발전했습니다.

• 멀티 스레드 애플리케이션 스케줄에 관한 이론적인 작업.
• StarTech – Thinking Machines Corporation의 Connection Machine 모델 CM-5에서 실행되도록 구축된 병렬 체스 프로그램.
• PCM/Threaded-C – CM-5에서 연속 통과 스타일의 스레드를 스케줄링하기 위한 C 기반 패키지

1994년 4월, 이 세 프로젝트가 합쳐져 "Cilk"라고 명명되었다.Cilk라는 이름은 머리글자가 아니라 "nice threads"(실크)와 C 프로그래밍 언어를 암시한 것입니다.Cilk-1 컴파일러는 1994년 9월에 출시되었습니다.

원래 Cilk 언어는 ANSI C에 기반하고 Cilk 고유의 키워드를 추가하여 신호 병렬화를 수행했습니다.CILK 소스 코드에서 Cilk 키워드를 삭제하면 결과는 항상 유효한 C 프로그램(풀 Cilk 프로그램의 시리얼 엘리션(또는 C 엘리션)이라고 불리며 단일 프로세서에서 실행되는 Cilk 프로그램과 동일한 의미)이 됩니다.몇 가지 유사점이 있지만 ^[which?]Cilk는 AT&T Bell Labs의 Concurrent C와 직접 관련이 없습니다.

Cilk는 GNU C 컴파일러(GCC)를 대상으로 C로의 번역자로서 실장되었습니다.마지막 버전인 Cilk 5.4.6은 MIT Computer Science and 인공지능 Laboratory(CSAIL)에서 구할 수 있지만 ^[3]더 이상 지원되지 않습니다.

Cilk의 능력을 보여주는 쇼케이스는 Cilkches 병렬 체스 프로그램이었는데, 이 프로그램은 1996년 오픈 네덜란드 컴퓨터 체스 ^[4]챔피언십을 포함하여 1990년대에 여러 컴퓨터 체스 상을 수상했습니다.

Cilk Arts 및 Cilk++

2006년 이전에는 Cilk 시장은 하이 퍼포먼스 컴퓨팅에 한정되어 있었습니다.메인스트림 컴퓨팅에 멀티코어 프로세서가 등장함에 따라 매년 수억 대의 새로운 병렬 컴퓨터가 출하되고 있었습니다.Cilk Arts는 이 기회를 활용하기 위해 설립되었습니다.2006년 Leiserson은 차세대 프로그래머의 상업적 요구를 지원하는 최신 버전의 Cilk를 만들고 시장에 내놓기 위해 Cilk Arts를 시작했습니다.2007년 10월에 시리즈A 벤처 파이낸스 라운드를 종료하고, 2008년 12월에 제품 「Cilk++ 1.0」을 출하했습니다.

Cilk++는 C++ 지원, 루프 지원 및 하이퍼 오브젝트 등 여러 가지 면에서 Cilk와 다릅니다.이것은 글로벌 변수에 대한 병렬 액세스로 인해 발생하는 데이터 레이스 문제를 해결하기 위해 설계된 새로운 구조입니다.Cilk++는 독점 소프트웨어입니다.이전 버전과 마찬가지로 Cilk-to-C++ 컴파일러로 구현되었습니다.Microsoft 및 GNU 컴파일러를 지원했습니다.

인텔(R) Cilk Plus

2009년 7월 31일, Cilk Arts는 자사 웹 사이트를 통해 자사 제품과 엔지니어링 팀이 Intel Corp.에 소속되었다고 발표했습니다.2010년 초에 Cilk 웹사이트:www.cilk.com는, 인텔의 Web 사이트로의 리다이렉트를 개시했습니다(2017년 초순부터, 원래의 Cilk Web 사이트는 호스트로 해결되지 않게 되었습니다).인텔과 Cilk Arts는 2010년 9월에 인텔 Cilk ^[5][6]Plus를 출시하여 테크놀로지를 더욱 발전시켰습니다.Cilk Plus는 Cilk++에서 Cilk Arts가 제안한 심플화를 채택하여 원래의 Cilk 키워드를 몇 개 사용할 필요가 없어지고 함수를 생성하거나 축소 조작에 관련된 변수를 처리할 수 있습니다.Cilk Plus는 어레이 확장기능 추가, 상용 컴파일러(인텔)에 내장, 기존 ^[7]디버거와의 호환성 등에서 Cilk 및 Cilk++와 다릅니다.

Cilk Plus는 인텔 C++ 컴파일러와 인텔 Composer XE ^{[citation needed]}2010의 인텔 컴파일러 릴리스에서 처음 구현되었습니다.오픈 소스(BSD 라이선스) 구현은 인텔에 의해 GNU 컴파일러 컬렉션(GCC)에 제공되었으며, GCC는 Cilk Plus를 버전 4.^[8]9에서 지원했습니다.단, GCC 5.0에서 추가된_cilk_for 키워드.2013년 2월에 인텔은 Cilk Plus를 ^[9]지원하는 Clangfork를 발표했습니다.인텔 컴파일러는 오픈 소스 구현이 아닌 레이스 디텍터와 퍼포먼스 아나라이저를 탑재하고 있습니다.

이후 인텔은 이 기능을 중단하고 사용자에게 OpenMP 또는 인텔 자체 TBB 라이브러리를 병행 프로그래밍에 ^[10]사용할 것을 권장합니다.

버전 간의 차이점

최초의 MIT Cilk 실장에서는, 최초의 Cilk 키워드는, 실제로 다음과 같습니다.cilkCilk로 기술된 함수를 식별합니다.Cilk 프로시저는 C 프로시저를 직접 호출할 수 있지만 C 프로시저는 Cilk 프로시저를 직접 호출하거나 생성할 수 없기 때문에 이 키워드는 Cilk 코드와 C 코드를 구별하기 위해 필요합니다.Cilk Plus는 이 제한과cilk따라서 C 및 C++ 함수는 Cilk Plus 코드를 호출할 수 있으며 그 반대도 가능합니다.

Cilk Plus 폐지

2017년 5월 GCC 7.1이 출시되어 Cilk Plus 지원이 ^[11]폐지되었습니다.인텔은 2017년 9월에 Cilk Plus를 2018년 인텔 소프트웨어 개발 ^[10]도구 출시와 함께 폐지한다고 발표했습니다.2018년 5월, GCC 8.1은 Cilk Plus 지원이 ^[12]제거된 상태로 출시되었습니다.

OpenCilk

Cilk Plus 지원이 인텔에 의해 폐지된 후 MIT는 OpenCilk ^[10][13]구현에서 Cilk 개발을 시작했습니다.OpenCilk는 Intel Cilk ^[14]Plus와 대부분 호환성이 있습니다.최초의 ^[15]안정판은 2021년 3월에 발매되었습니다.

언어 기능

Cilk 언어 설계의 이면에 있는 원칙은 프로그래머가 병렬을 공개하고 안전하게 병렬로 실행할 수 있는 요소를 식별해야 한다는 것입니다.그 후 실행 중에 프로세서 간에 작업을 실제로 분할하는 방법을 결정하는 것은 런타임 환경, 특히 스케줄러에게 맡겨야 합니다.이러한 책임은 분리되어 있기 때문에 Cilk 프로그램은 프로세서를 포함한 임의의 수의 프로세서에서 재기입하지 않고 실행할 수 있습니다.

태스크 병렬 처리: 생성 및 동기화

Cilk의 C에 추가된 주요 키워드는 태스크 병렬 프로그램을 함께 작성할 수 있는 두 가지입니다.

• 함수 콜(스펀 f(x))보다 앞의 spawn 키워드는 함수 콜(f(x))이 호출 함수에서 그 뒤에 나오는 문장과 병행하여 안전하게 실행될 수 있음을 나타냅니다.스케줄러는 이 절차를 병렬로 실행할 필요가 없습니다.키워드는 이 순서를 실행할 수 있음을 스케줄러에게 알릴 뿐입니다.
• sync 문은 이전에 생성된 함수 호출이 모두 완료될 때까지 현재 함수의 실행을 계속할 수 없음을 나타냅니다.이것은 장벽 방법의 예시입니다.

(Cilk Plus에서는 키워드 철자는 _Cilk_spawn 및 _Cilk_sync, 또는 Cilk Plus 헤더가 포함되어 있는 경우는 cilk_spawn 및 cilk_sync 입니다).

다음은 CILK에서의 Fibonacci 함수의 재귀적인 실장입니다.이것에 의해, snc 키워드와 sync 키워드가 표시되는 병행 재귀 콜이 사용됩니다.원래 Cilk에서는 이러한 기능을 사용하는 모든 함수에 cilk 키워드의 주석을 붙여야 했습니다.이 키워드는 Cilk Plus에서는 사용되지 않습니다(Cilk 프로그램코드는 번호가 매겨지지 않습니다.이 번호는 논의를 쉽게 하기 위해 추가된 것입니다).

클릭하다 인트 파이브(인트 n) {     한다면 (n < > 2) {         돌아가다 n;     }     또 다른 {        인트 x, y;         x = 낳다 파이브(n - 1);        y = 낳다 파이브(n - 2);         동기;         돌아가다 x + y;     } } 

이 코드가 fib(2)의 값을 결정하기 위해 단일 프로세서에 의해 실행된 경우 해당 프로세서는 fib(2)의 프레임을 생성하고 라인 1~5를 실행합니다.6행에서는 프레임에 x와 y의 값을 유지하기 위한 공간을 만듭니다.행 8에서 프로세서는 현재 프레임을 일시정지하고 프로시저 fib(1)를 실행하기 위한 새로운 프레임을 생성하여 반환문에 도달할 때까지 해당 프레임의 코드를 실행한 후 fib(1)의 값을 fib(2)의 x 변수로 하여 fib(2) 프레임을 재개해야 합니다.다음 줄에서 fib(0)를 실행하고 결과를 fib(2)의 y 변수에 배치하려면 다시 일시 중단해야 합니다.

단, 멀티프로세서머신에서 코드가 실행되면 실행은 다르게 진행됩니다.1개의 프로세서가 fib(2)의 실행을 시작합니다.단, fib(n-1)에 콜을 수정하는 span 키워드는 fib(2)의 실행을 개시합니다.이 두 번째 프로세서는 fib(1)의 프레임을 작성하고 코드를 실행하며 종료 시 fib(2)의 프레임에 결과를 저장할 수 있습니다.첫 번째 프로세스입니다.r은 동시에 fib(2) 코드를 계속 실행합니다.프로세서는 생성된 프로시저를 다른 곳에 할당할 의무가 없습니다.머신이 2개의 프로세서만 가지고 있고 fib(2)를 실행하고 있는 프로세서가 프로시저 호출에 도달했을 때 두 번째 프로세서가 fib(1)로 아직 비지 상태일 경우 첫 번째 프로세서는 fib(2)를 일시 중단하고 fib(0) 자체를 실행합니다.물론, 다른 프로세서를 사용할 수 있는 경우는, 그 프로세서가 가동해, 3개의 프로세서가 동시에 다른 프레임을 실행합니다.

(앞의 설명은 완전히 정확한 것은 아닙니다.Cilk에 대해 논의하는 일반적인 용어는 프로세서가 다른 프로세서에 작업을 생성하도록 결정하는 것을 의미하지만, 실제로는 나중에 설명하는 work-stealing이라는 정책을 사용하여 프로세서에 작업을 할당하는 것이 스케줄러입니다.)

fib(2)를 실행하고 있는 프로세서가 다른 프로세서가 프레임을 완료하기 전에 라인 13을 실행하면 잘못된 결과 또는 오류가 발생합니다.fib(2)는 x와 y에 저장되어 있는 값을 추가하려고 하지만 둘 중 하나 또는 둘 다 값이 누락됩니다.sync 키워드의 목적은 다음과 같습니다.이 키워드는 프레임을 실행하는 프로세서에 대해 생성된 모든 프로시저 콜이 반환될 때까지 프레임 자체의 실행을 정지해야 함을 나타냅니다.fib(2)가 11행의 sync 스테이트먼트를 통과할 수 있는 경우 fib(1)와 fib(0)가 결과를 완료하고 x와 y에 배치했기 때문에 이러한 결과를 계산해도 안전합니다.

위의 코드 예에서는 Cilk-5 구문을 사용하고 있습니다.원래의 Cilk(Cilk-1)에서는 명시적인 연속 전달 스타일의 프로그래밍이 필요한 다소 다른 구문을 사용했습니다.Fibonacci의 예는 다음과 같습니다.^[16]

실 파이브(콘텐트 인트 k, 인트 n) {     한다면 (n < > 2) {         송신_실행(k, n);     }     또 다른 {         콘텐트 인트 x, y;         spawn_next 합(k, ?x, ?y);         낳다 파이브(x, n - 1);         낳다 파이브(y, n - 2);     } }  실 합(콘텐트 인트 k, 인트 x, 인트 y) {      송신_실행(k, x + y); } 

fib의 재귀적 케이스 내에서 spawn_next 키워드는 spoan에 의해 생성된 자 스레드가 아닌 후속 스레드의 생성을 나타냅니다.자 스레드는 재귀 호출에 의해 연속 변수 x 및 y가 입력되기를 기다린 후 sum 서브루틴을 실행합니다.베이스 케이스와 합계는 send_argument(k, n) 연산을 사용하여 연속 변수 k를 n의 값으로 설정하고 값을 실질적으로 후속 스레드로 되돌립니다.

유입구

나머지 2개의 Cilk 키워드는 조금 더 고급이며 인렛 사용에 관한 것입니다.일반적으로 Cilk 프로시저가 생성되면 생성된 프로시저의 결과를 부모 프레임의 변수에 넣는 것만으로 결과를 부모 프로시저로 되돌릴 수 있습니다.이 예에서는 생성된 프로시저 콜의 결과를 다음과 같이 할당했습니다.x그리고.y.

다른 방법은 흡입구를 사용하는 것입니다.인렛은 Cilk 프로시저 내부의 함수이며 생성된 프로시저 콜의 결과가 반환될 때 처리됩니다.인렛을 사용하는 주요 이유 중 하나는 프로시저의 모든 인렛이 서로 및 부모 프로시저에 대해 원자적으로 동작하도록 보증되기 때문에 여러 리턴 프로시저가 부모 프레임에서 동일한 변수를 동시에 업데이트하려고 할 때 발생할 수 있는 오류를 피할 수 있다는 것입니다.

• 그inlet키워드는 절차 내에서 정의된 기능을 인렛으로 나타냅니다.
• 그abort키워드는 입력구 내에서만 사용할 수 있습니다.이 키워드는 부모 프로시저에 의해 생성된 다른 프로시저를 안전하게 중단할 수 있음을 스케줄러에 알립니다.

유입구는 Cilk가 Cilk++가 되었을 때 삭제되었으며 Cilk Plus에는 없습니다.

병렬 루프

Cilk++는 Cilk Plus에서 cilk_for라는 이름의 병렬루프를 추가했습니다.이 루프들은 마치

무효 고리(인트 *a, 인트 n) {     #고수의 알갱이 크기=100// 옵션     cilk_for. (인트 i = 0; i < > n; i++) {         a[i] = f(a[i]);     } } 

이것에 의해, 루프의 본체(여기서 f에 이어 어레이 a에의 할당)에의 호출이, 0부터 n까지의 i의 값 마다 부정 순서로 실행된다.옵션의 "grain size" 플러그마에 따라 조화가 결정됩니다.100개 이하의 요소의 서브 배열이 순차적으로 처리됩니다.Cilk 사양은 구성의 정확한 동작을 명시하지 않지만 일반적인 구현은 프로그래머가 작성한 것처럼 분할 및 정복 재귀입니다.^[17]

정적인 무효 재귀(인트 *a, 인트 개시하다, 인트 끝.) {     한다면 (끝. - 개시하다 <=> 100) {  // 여기 100은 곡립 크기입니다.         위해서 (인트 i = 개시하다; i < > 끝.; i++) {             a[i] = f(a[i]);         }     }     또 다른 {         인트 중간점 = 개시하다 + (끝. - 개시하다) / 2;         cilk_displays(실제) 재귀(a, 개시하다, 중간점);         재귀(a, 중간점, 끝.);         cilk_sync;     } }  무효 고리(인트 *a, 인트 n) {     재귀(a, 0, n); } 

루프 본체를 함수로 호출하는 루프가 아닌 분할 및 정복 프로그램을 생성하는 이유는 세분화된 처리와 효율 모두에 있습니다.즉, 단일 작업에서 모든 산란을 수행하면 로드밸런싱이 ^[18]병목현상이 됩니다.

HPCwire 상의 다양한 병렬루프 구조를 검토한 결과 cilk_for constructure는 매우 일반적인 것으로 확인되었지만, cilk Plus 사양에서는 반복이 데이터에 의존할 필요가 없다고 규정되어 있지 않기 때문에 컴파일러는 cilk_for loop을 자동으로 벡터화할 수 없습니다.또, 리덕션(어레이의 합계 등)에 추가 ^[17]코드가 필요한 것도 확인했습니다.

리듀서 및 하이퍼 오브젝트

Cilk++는 하이퍼오브젝트라고 불리는 오브젝트를 추가했습니다.이러한 오브젝트에서는, 레이스 조건이나 명시적인 잠금을 사용하지 않고, 복수의 스트랜드가 상태를 공유할 수 있습니다.각 스트랜드에는 하이퍼오브젝트에 대한 뷰가 있어 스트랜드가 동기화되면 뷰가 프로그래머에 ^[19]의해 지정된 방식으로 결합됩니다.

하이퍼오브젝트의 가장 일반적인 유형은 리덕터이며, 이는 OpenMP의 리덕터 절 또는 모노이드의 대수적 개념에 대응합니다.각 리덕터에는 2개의 값을 조합하는 아이덴티티 요소와 관련 연산이 있습니다.원형환원자는 숫자의 합계입니다.아이덴티티 요소는 0이고 연관환원연산은 합계를 계산합니다.이 리듀서는 Cilk++ 및 Cilk Plus에 내장되어 있습니다.

// 0 ~ N 의 i 의 foo(i) 를 병렬로 계산합니다. 클릭하다::리듀서_opadd< >흘러가다> 결과(0); cilk_for. (인트 i = 0; i < > N; i++)     결과 += 후우(i); 

다른 리듀서를 사용하여 링크 리스트 또는 문자열을 작성할 수 있으며 프로그래머는 커스텀 리듀서를 정의할 수 있습니다.

하이퍼오브젝트의 한계는 제한된 결정성만 제공한다는 것입니다.Burkhardt 등은 합산기조차도 비결정론적 행동을 일으킬 수 있으며, 스케줄링 ^[20]순서에 따라 1 또는 2를 생성할 수 있는 프로그램을 보여줄 수 있다고 지적한다.

무효 추가 1(클릭하다::리듀서_opadd< >인트> &r) { r++; } // ... 클릭하다::리듀서_opadd< >인트> r(0); cilk_displays(실제) 추가 1(r); 한다면 (r == 0) { r++; } cilk_sync; 산출량(r.get_value(값()); 

배열 표기법

인텔(R) Cilk Plus는 어레이 전체 또는 어레이 섹션에 대한 높은 수준의 연산을 표현하기 위한 표기법을 추가했습니다.예를 들어, 통상적으로 기입되는 axpy 형식의 함수입니다.

 // y ← α x + y  무효 액스피(인트 n, 흘러가다 알파, 컨스턴트 흘러가다 *x, 흘러가다 *y)  {      위해서 (인트 i = 0; i < > n; i++) {          y[i] += 알파 * x[i];      }  } 

Cilk Plus에서는 다음과 같이 나타낼 수 있습니다.

y[0:n] += 알파 * x[0:n]; 

이 표기법은 컴파일러가 응용 프로그램을 효과적으로 벡터화하는 데 도움이 됩니다.인텔(R) Cilk Plus는 C/C++ 연산을 여러 어레이 요소에 병렬로 적용할 수 있습니다.또, 벡터화된 시프트, 회전, 삭감에 사용할 수 있는 일련의 빌트인 기능도 갖추고 있습니다.Fortran 90에도 같은 기능이 있습니다.Cilk Plus는 임시 어레이를 할당하지 않기 때문에 메모리 사용량을 쉽게 예측할 수 있습니다.

기본 함수

Cilk Plus에서 요소 함수는 스칼라 인수 또는 배열 요소에서 병렬로 호출할 수 있는 일반 함수입니다.OpenCL의 커널 함수와 유사합니다.

#sysma simd

이 플러그마는 자동 벡터화에 실패할 수 있는 경우에도 루프를 벡터화할 수 있는 권한을 컴파일러에 부여합니다.이것은 수동으로 벡터화를 적용하는 가장 간단한 방법입니다.

워크스틸링

Cilk 스케줄러는 "work-stealing"이라고 불리는 정책을 사용하여 프로시저 실행을 여러 프로세서로 효율적으로 나눕니다.다시 말씀드리지만 CILK 코드가 싱글프로세서 머신에서 실행되는 방법을 먼저 살펴보면 가장 이해하기 쉽습니다.

프로세서는 프로시저 콜을 처리하기 위해 정지해야 하는 각 프레임을 배치하는 스택을 유지합니다.fib(2)를 실행하고 있을 때 fib(1)에 대한 재귀 호출이 발생하면 fib(2)의 상태(변수 및 코드 실행이 중단된 위치 포함)를 저장하고 스택에 해당 상태를 배치합니다.서스펜드의 원인이 된 프로시저 콜과 그 순서로 호출된 프로시저가 모두 실행될 때까지 스택에서 서스펜드 상태가 해제되어 실행을 재개하지 않습니다.

프로세서가 여러 개 있으면 당연히 상황이 달라집니다.각 프로세서에는 실행이 정지된 프레임을 저장하기 위한 스택이 있습니다.단, 이러한 스택은 데크에 가깝습니다.이러한 스택은 어느 한쪽 끝에서나 삭제할 수 있습니다.프로세서는 아직 상태를 스택에서 삭제할 수 있습니다.단, 현재 동작하지 않는 프로세서(자체 작업을 완료했거나 할당되지 않은 프로세서)는 스케줄러를 통해 무작위로 다른 프로세서를 선택하여 스택 반대쪽에서 작업을 "스틸"하려고 합니다.uspended 상태.도용 프로세서가 실행을 시작할 수 있습니다.도난당한 상태는 도난당한 프로세서가 마지막으로 실행될 때까지의 상태입니다.

「 」를 참조해 주세요.

• 그랜드 센트럴 디스패치
• 인텔 동시 컬렉션 (CnC)
• 인텔 병렬 빌딩 블록 (PBB)
  • 인텔 어레이 빌딩 블록 (ArBB)
• Intel Parallel Studio
• 네슬
• OpenMP
• 병렬 컴퓨팅
• 체 C++ 병렬 프로그래밍 시스템
• 스레드 빌딩 블록(TBB)
• Unified Parallel C

레퍼런스

외부 링크

• OpenCilk 공식 웹사이트
• 인텔 Cilk Plus 웹사이트
• MIT의 Cilk Project 웹사이트
• Arch D. Robison, "Cilk Plus: 스레드 및 벡터 병렬화를 위한 언어 지원" 및 "Cilk Plus를 사용한 병렬 프로그래밍", 2012년 7월 16일.