순서l

Sequence
순서
패러다임병렬 컴퓨팅, 기능, 순수 기능, 선언형 프로그래밍
설계자대니얼 쿡 박사
넬슨 러쉬튼 박사
브래드 네마니치 박사
개발자텍사스 공대
텍사스 멀티코어 테크놀로지스
처음 등장한1989년; 33년 전 (2011년)
타이핑 분야정적, 유형 추론
플랫폼x86, 전원, ARM
OSWindows, macOS, Linux
면허증.독자 사양[1]
웹 사이트texasmulticore.com[데드링크]

Sequence L은 범용 기능성 프로그래밍 언어 및 자동 병렬화(Parallel Computing) 컴파일러 및 도구 세트이며, 주요 설계 목표는 멀티 코어 프로세서 하드웨어의 성능, 프로그래밍의 용이성, 플랫폼의 이식성/최적화, 코드의 명확성과 가독성입니다.그 주된 장점은 프로그래머가 병렬 식별, 벡터화 지정, 레이스 조건 회피 및 수동 명령 기반 프로그래밍 접근의 기타 과제에 신경 쓸 필요 없이 사용 가능한 모든 처리 능력을 자동으로 최대한 활용하는 간단한 코드를 작성할 수 있다는 것입니다.예를 들어 OpenMP 등입니다.

SequenceL로 작성된 프로그램은 병렬로 실행되는 멀티스레드 코드로 컴파일할 수 있으며, 프로그래머로부터 병렬화 방법 또는 무엇을 지시받지 않습니다.2015년 현재 SequenceL 컴파일러 버전은 C++ 및 OpenCL로 병렬 코드를 생성하며, 이를 통해 C, C++, C#, Fortran, Java 및 Python을 포함한 가장 일반적인 프로그래밍 언어를 사용할 수 있습니다.플랫폼 고유의 런타임에 의해 스레드가 안전하게 관리되며 사용 가능한 코어 수에 따라 병렬 퍼포먼스가 자동으로 제공됩니다.현재 x86, POWER8 및 ARM 플랫폼을 지원하고 있습니다.

역사

Sequence L은 1989년부터 20년간 개발되었으며, 주로 텍사스 공대에서 개발되었습니다.주요 자금 조달은 NASA에서 제공했는데, NASA는 원래 "자기 검증"을 위한 사양 언어를 개발하고자 했습니다. 즉, 일단 작성되면 요구사항을 실행할 수 있고 원하는 결과에 대해 결과를 검증할 수 있습니다.

이 프로젝트의 주 연구자는 처음에 Daniel Cooke [2]박사로, 곧 Daniel Cooke 박사와 합류했다.넬슨 러쉬튼(또 다른 텍사스 공대 교수)과 나중에는 브래드 네마니치 박사(당시 쿡 밑에서 박사과정을 밟고 있었다).읽을 수 있을 만큼 단순하지만 실행 가능한 언어를 만들겠다는 목표는 프로그래머가 원하는 결과를 얻기 위한 수단이 아니라 설명하는 기능적이고 선언적인 언어 접근방식을 발명가들로 하여금 정착하게 만들었다.그러면 언어는 찾을 수 있는 가장 효율적인 방법으로 문제를 해결할 수 있습니다.

언어가 진화함에 따라, 연구원들은 소비-심플화-생산(CSP)[3]을 포함한 새로운 컴퓨터 접근 방식을 개발했습니다.1998년 Sequence L을 병렬 컴퓨팅에 적용하기 위한 연구가 시작되었습니다.이것은 2004년에 NT(Normal-Transpose) [4][5]시멘틱이 추가되면서 더욱 완전한 형태를 갖추게 되었습니다.이는 중앙처리장치(CPU)의 주요 벤더가 계속해서 클럭 속도를 높이는 것이 아니라 멀티코어 프로세서로 크게 전환한 것과 일치합니다.NT는 GAMMA [7]및 NESL과[6] 유사한 데이터 흐름과 같은 실행 전략에 기반하여 구조를 단순화하고 분해하는 데 사용되는 시맨틱 워크호스입니다.NT 시맨틱은 Lémmel과 Peyton-Jones의 보일러 플레이트 [8][9]제거와 유사한 목표를 달성한다.언어의 다른 모든 특징은 재귀, 첨자 구조, 함수 참조 및 함수 [10][11]본문 평가 등 이 두 가지 법칙에서 정의할 수 있습니다.

원래 의도는 아니었지만, 이러한 새로운 접근법은 언어가 수행한 연산의 상당 부분을 프로그래머에게 투명하게 병렬화할 수 있게 했다.2006년에 텍사스 공대에서 자동 병렬화 컴파일러 프로토타입을 개발했습니다.2009년, Texas Tech는 후속 상업 개발을 위해 [12]TMT(Texas Multicore Technologies)에 지적 재산을 라이센스했습니다.2017년 1월 TMT는 상용 프로페셔널 에디션 외에 다운로드 가능한 무료 커뮤니티 에디션을 포함하는 v3를 출시했습니다.

설계.

Sequence L은 가능한 한 간단하게 학습하고 사용할 수 있도록 설계되어 있습니다.예를 들어 C가 I/O를 잘 처리했기 때문에 발명가가 I/O를 재창조하지 않기로 선택한 알고리즘 코드에 중점을 두고 있습니다.그 결과 SequenceL의 전체 언어 참조는 40페이지에 불과하며, 풍부한 예제를 포함하고 있으며, 공식 문법은 약 15개의 생산 [13]규칙을 가지고 있습니다.

시퀀스 L은 엄격하게 평가되고(Lisp와 같이), 유형 추론(Haskell과 같이) 정적으로 입력되며, 표준적이고 비공식적인 수학 표기법(C, Pascal, Python 등)과 유사한 infix 연산자와 접두사 연산자의 조합을 사용합니다.이는 순수하게 선언적인 언어이며, 프로그래머가 함수를 수학적인 의미로 정의하는 것을 의미하며, 그 구현에 대한 지침을 제공하지 않습니다.예를 들어 행렬 곱셈의 수학적 정의는 다음과 같습니다.

p×n 행렬 B를 갖는 m×p 행렬 A의 곱은 m×n 행렬이며, 여기서 (i,j)의 입력은 다음과 같다.

SequenceL 정의는 그 정의를 거의 그대로 반영하고 있습니다.

matmul(A(2), B(2) [i,j] := k := 1...size(B); 요약하면 A[i,k] * B[k,j];

정의 왼쪽에 있는 각 매개변수 A와 B 뒤에 있는 첨자는 A와 B가 깊이 2 구조(즉, 스칼라 목록 목록)임을 나타내며, 여기서 행렬로 간주한다.이 공식 정의에서 시퀀스 L은 정의된 곱의 치수를 (i, j)번째 입력 공식(오른쪽이 정의된 쌍(i, j)의 집합)에서 추론하고 위의 비공식 정의에서와 동일한 공식으로 각 항목을 계산한다.이 정의에는 반복에 대한 명시적 지시 또는 연산을 실행하는 순서에 대한 명시적 지시가 없습니다.따라서 SequenceL 컴파일러는 정의 방정식을 만족시키는 임의의 순서(병렬 순서 포함)로 연산을 수행할 수 있습니다.이 예제에서 제품의 좌표 계산은 큰 행렬의 경우 프로세서의 수에 따라 선형적으로 조정되는 방식으로 병렬화됩니다.

위에서 설명한 바와 같이 Sequence L은 다른 프로그래밍 언어와 가법적으로 동작하도록 설계되었기 때문에 입출력(I/O)을 위한 빌트인 구조가 없습니다.멀티스레드 C++로 컴파일하여 20+SWIG(Simplified Wrapper and Interface Generator) 언어(C, C++, C#, Java, Python 등)를 지원하기로 결정함으로써 기존 설계 흐름, 훈련 및 도구에 쉽게 적합합니다.결과 코드를 I/O 작업을 수행하는 다른 코드와 연결함으로써 기존 애플리케이션을 개선하고 멀티코어 라이브러리를 만들 수 있으며 독립 실행형 애플리케이션을 만들 수도 있습니다.SequenceL 함수는 Python 및 기타 해석된 언어처럼 지정된 입력으로 인터프리터로부터 쿼리할 수도 있습니다.

정규화 - 트랜스포즈

SequenceL의 주요 비스칼라 구조는 시퀀스이며, 이는 기본적으로 목록입니다.시퀀스는 임의의 레벨로 네스트 할 수 있습니다.순수하게 기능하는 많은 언어에서 일반적인 재귀의 일상적인 사용을 피하기 위해 시퀀스 L은 정규화-트랜스포즈(NT)라는 기술을 사용합니다.이 기술에서는 스칼라 연산은 [14]시퀀스의 요소에 자동으로 분산됩니다.예를 들어 SequenceL에서는

이는 '+' 연산자를 오버로드한 것이 아니라 내장 및 사용자 정의의 모든 작업으로 확장되는 NT의 효과에서 비롯됩니다.또 다른 예로 f()가 스칼라 인수의 3인수 함수일 경우 적절한 x와 z에 대하여

NT 구문은 예를 들어 에서와 같이 동시에 여러 인수에 사용할 수 있습니다.

또한 예상되는 인수가 임의의 타입 T의 비스칼라이고 실제 인수가 타입 T(또는 일반적으로는 좌표가 타입 T인 데이터 구조)의 오브젝트 리스트인 경우에도 기능합니다.예를 들어, A가 행렬이고s X가 행렬 [X1, ..., Xn]의 목록이고 위의 행렬 곱셈 정의가 주어진다면, 시퀀스 L에서 우리는 다음과 같이 될 것이다.

matmul(A,Xs) = [matmul(A,X1),...matmul(A,Xn)]

일반적으로 NT는 반복, 재귀 또는 높은 수준의 기능 연산자를 필요로 하지 않습니다.

  1. 데이터 구조의 모든 멤버에게 동일한 작업을 수행하거나
  2. 유사한 형태의 구조물의 해당 부분을 함께 처리합니다.

이것은 반복과 재귀의 사용의 대부분을 설명하는 경향이 있습니다.

예: 소수

위의 개념을 보여주는 좋은 예는 소수를 찾는 것이다.소수는 다음과 같이 정의됩니다.

1보다 큰 정수이며, 그 자체와 1 이외의 양의 제수는 없습니다.

따라서 2에서 z-1까지의 숫자가 없으면 양의 정수 z는 소수입니다. 균등하게 나눕니다.SequenceL을 사용하면 위의 정의를 그대로 언어로 변환하여 이 문제를 프로그래밍할 수 있습니다.

시퀀스 L에서는 2에서 z-1까지의 숫자의 시퀀스가 (2...(z-1))이므로 100에서 200 사이의 모든 소수를 찾는 프로그램을 작성할 수 있습니다.

prime(z) : none(z mod (2...(z-1)) = 0일 때 z;

영어로만 말해두요

... 인수 자체보다 작은 2와 1 사이의 숫자가 없는 경우 인수로 균등하게 분할합니다.

이 조건이 충족되지 않으면 함수는 아무것도 반환하지 않습니다.그 결과 이 프로그램을 실행하면

cmd:>prime(17)17 cm:>prime(18)비어 있음

"100 ~ 200" 문자열은 프로그램에 표시되지 않습니다.오히려 프로그래머는 일반적으로 그 부분을 인수로 넘깁니다.프로그램은 스칼라를 인수로 예상하기 때문에 이를 대신 전달하면 시퀀스 L이 시퀀스의 각 멤버에 대해 자동으로 동작을 수행합니다.함수는 실패한 값에 대해 빈 값을 반환하므로 결과는 입력 시퀀스가 되지만 소수점 기준을 충족하는 숫자만 반환하도록 필터링됩니다.

cmd:> prime(100...)200)    [101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199]

이 문제를 매우 짧고 읽을 수 있는 프로그램으로 해결하는 것 외에 중첩된 시퀀스에 대한 SequenceL의 평가는 모두 병렬로 수행됩니다.

구성 요소들

SequenceL 코드 작성에 사용할 수 있는 소프트웨어 컴포넌트는 TMT에 의해 지원됩니다.모든 구성 요소는 Windows, macOS 및 대부분의 Linux(CentOS, RedHat, OpenSUSE 및 Ubuntu 포함)를 실행하는 x86 플랫폼과 대부분의 Linux를 실행하는 ARM 및 IBM Power 플랫폼에서 사용할 수 있습니다.

통역사

명령줄 인터프리터를 사용하면 명령 셸에 직접 코드를 쓰거나 미리 작성된 텍스트 파일에서 코드를 로드할 수 있습니다.이 코드를 실행하고 결과를 평가하여 코드의 정확성을 확인하거나 빠른 답을 찾을 수 있습니다.또한 널리 사용되는 Eclipse 통합 개발 환경(IDE)을 통해서도 사용할 수 있습니다.인터프리터에서 실행되는 코드는 병렬로 실행되지 않고 하나의 스레드에서 실행됩니다.

컴파일러

명령줄 컴파일러는 SequenceL 코드를 읽고 고도로 병렬화된, 벡터화된, C++ 및 옵션으로 OpenCL을 생성합니다.이것들은 실행하기 위해 SequenceL 런타임 라이브러리와 링크되어야 합니다.

런타임

런타임 환경은 컴파일된 병렬화된 C++ 코드와 함께 작동하여 타깃 플랫폼에서 최적으로 실행되는 사전 컴파일된 라이브러리 세트입니다.인텔(R) 스레드 빌딩 블록([15]TBB)을 기반으로 구축되어 캐시 최적화, 메모리 관리, 작업 큐 스틸링, 퍼포먼스 감시 등의 작업을 처리합니다.

이클립스 IDE 플러그인과 디버거

Eclipse 통합 개발 환경 플러그인은 표준 편집 기능(함수 롤업, 크로코딩 등)과 SequenceL 디버깅 환경을 제공합니다.이 플러그인은 SequenceL 인터프리터에 대해 실행되므로 멀티스레드코드 디버깅에는 사용할 수 없습니다.단, 자동 병렬화를 제공함으로써 병렬 SequenceL 코드의 디버깅은 시퀀셜 SequenceL 코드의 정확성을 실제로 검증합니다.즉, 순차적으로 올바르게 실행되면 올바르게 병렬로 실행되므로 인터프리터에서의 디버깅으로 충분합니다.

라이브러리

프로그래밍 프로세스를 합리화하고 모범 사례로 사용하기 위해 다양한 산술 및 기타 표준 함수 라이브러리가 SequenceL 소스 코드로 포함되어 있습니다.이것들은, C 또는 C++ 라이브러리가 #포함되는 것과 같은 방법으로 Import 할 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ "SequenceL Licensing". Archived from the original on 2017-02-02. Retrieved 2017-01-26.
  2. ^ "Dr. Daniel Cooke at Texas Multicore Technologies". Archived from the original on 2016-03-04. Retrieved 2016-02-24.
  3. ^ "Consume-simplify-produce (CSP)" (PDF). Archived from the original (PDF) on 2017-02-02. Retrieved 2017-01-26.
  4. ^ Nemanich, Brad; Cooke, Daniel; Rushton, Nelson (2010), SequenceL: Transparency And Multi-Core Parallelisms (PDF), DAMP '10 Proceedings of the 5th ACM SIGPLAN workshop on Declarative Aspects of Multicore Programming, New York, NY, US: ACM, pp. 45–52, archived from the original (PDF) on 2017-02-02, retrieved 2017-01-26
  5. ^ Cooke, Daniel; Rushton, Nelson; Nemanich, Brad; Watson, Robert G.; Andersen, Per (March 2008), "Normalize, Transpose, and Distribute: An Automatic Approach for Handling Nonscalars", ACM Transactions on Programming Languages and Systems, 30 (2): 1–49, doi:10.1145/1330017.1330020
  6. ^ Banater, J-P; Le Metayer, D. (January 1993), "Programming by Multiset Transformation" (PDF), Communications of the ACM, 36 (1): 98–111, doi:10.1145/151233.151242
  7. ^ Blelloch, Guy (March 1996), "Programming Parallel Algorithms", Communications of the ACM, 39 (3): 85–97, CiteSeerX 10.1.1.141.5884, doi:10.1145/227234.227246
  8. ^ Lämmel, Ralf; Peyton-Jones, Simon (2003), "Scrap your boilerplate: a practical design pattern for generic programming", Proceedings of TLDI 2003
  9. ^ Lämmel, Ralf; Peyton-Jones, Simon (2004), "Scrap more boilerplate: reflection, zips, and generalised casts", Proceedings of ICFP 2004
  10. ^ Cooke, Daniel; Rushton, Nelson (January 1993), "Iterative and Parallel Algorithm Design from High Level Language Traces" (PDF), ICCS'05 Proceedings of the 5th International Conference on Computational Science, Part III: 891–894, doi:10.1007/11428862_132, ISBN 978-3-540-26044-8, archived from the original (PDF) on 2017-02-02, retrieved 2017-01-26
  11. ^ Cooke, Daniel; Rushton, Nelson (June 27–30, 2005), "SequenceL – An Overview of a Simple Language", Proceedings of the 2005 International Conference on Programming Languages and Compilers, PLC 2005
  12. ^ 텍사스 멀티코어 테크놀로지스
  13. ^ Nemanich, Brad; Cooke, Daniel; Rushton, Nelson (2010), SequenceL: Transparency And Multi-Core Parallelisms (PDF), DAMP '10 Proceedings of the 5th ACM SIGPLAN workshop on Declarative Aspects of Multicore Programming, New York, NY, US: ACM, pp. 45–52, archived from the original (PDF) on 2017-02-02, retrieved 2017-01-26
  14. ^ Cooke, Daniel; Rushton, Nelson (June 27–30, 2005), "SequenceL – An Overview of a Simple Language", Proceedings of the 2005 International Conference on Programming Languages and Compilers, PLC 2005
  15. ^ 인텔(R) 스레드 빌딩 블록 (TBB)

외부 링크