명시적 멀티스레딩

Explicit Multi-Threading(XMT)은 병렬 랜덤 액세스 머신(PRAM) 병렬 계산 모델을 중심으로 설계된 병렬 컴퓨터를 구축하고 프로그래밍하기 위한 컴퓨터 과학 패러다임입니다.XMT에 대한 보다 직접적인 설명은 시리얼 컴퓨팅을 심플하게 만든 기본적인 추상화부터 시작됩니다.즉, 시리얼 프로그램에서 실행할 수 있는 단일 명령어는 즉시 실행됩니다.이 추상화의 결과로 다음에 실행할 수 있는 명령에 대한 단계별(유도적) 설명이 이루어집니다.XMT의 배후에 있는 기본적인 병렬 추상화(2011년)는 동시 실행에 사용할 수 있는 명령어 수가 무한히 많다는 것입니다.ICE의 결과는 동시 실행을 위해 다음에 사용할 수 있는 지침을 단계별로(유도적인) 설명하는 것이다.시리얼 폰 노이만 컴퓨터(현재까지 유일하게 성공한 범용 플랫폼)를 넘어서는 XMT의 목표는 컴퓨터 과학이 간단한 한 줄 컴퓨팅 추상화를 통해 수학적 귀납을 다시 강화할 수 있다는 것입니다.

RAM(Random-Access Machine)은 컴퓨터 과학에서 표준 시리얼 컴퓨팅의 알고리즘과 복잡성을 연구하기 위해 사용되는 추상 머신 모델입니다.PRAM 계산 모델은 병렬 알고리즘과 병렬 컴퓨팅의 복잡성을 유사하게 연구하기 위해 아직 구축되지 않은 추상 병렬 머신 모델입니다.연구자들은 PRAM 모델을 위한 병렬 알고리즘에 대한 많은 지식을 개발했다.이러한 병렬 알고리즘은 병렬 알고리즘에 대한 다른 접근 방식의 표준으로 단순하다고 알려져 있습니다.

PRAM 모델에 대한 이러한 대규모 병렬 알고리즘 지식 및 비교적 단순성에 의해 프로그래밍이 이들 병렬 알고리즘에 의해 유도될 수 있는 컴퓨터 구축에 동기 부여되었습니다.병렬 프로그래머의 생산성은 오랫동안 병렬 컴퓨터의 성공에 중요한 것으로 여겨져 왔기 때문에 알고리즘의 단순성이 중요합니다.

멀티코어 컴퓨터는 1개의 집적회로 다이에 2개 이상의 프로세서 코어를 중심으로 구축됩니다.범용 컴퓨팅을 포함한 많은 애플리케이션 도메인에서 널리 사용되고 있습니다.Explicit Multi-Threading(XMT)은 프로세서 코어가 수십, 수백 또는 수천 개 있는 멀티 코어 컴퓨터를 구축 및 프로그래밍하기 위한 컴퓨팅 패러다임입니다.

2011년과 2012년에 발표된 실험 연구는 XMT 프로토타입의 고급 PRAM 알고리즘의 속도가 최첨단 멀티 코어 컴퓨터에서의 동일한 문제보다 훨씬 더 빠르다는 것을 보여줍니다.

2018년에 발표된 연구에 따르면 잠금 단계 병렬 프로그래밍(ICE 사용)이 XMT 시스템에서 가장 빠른 수동 튜닝 멀티 스레드 코드와 동일한 성능을 달성할 수 있습니다.이러한 유도 잠금 단계 접근법은 프로그래머에게 도전적인 것으로 알려진 다른 많은 핵심 시스템의 멀티 스레드 프로그래밍 접근 방식과 대조적입니다.

XMT 패러다임은 Uzi Vishkin에 의해 도입되었다.

XMT의 주요 추상화 수준

XMT(Explicit Multi-Threading) 컴퓨팅 패러다임은 몇 가지 추상화 수준을 통합합니다.

Shiloach & Vishkin(1982)에 의해 도입된 작업시간(WT) 프레임워크(일명 작업심도)는 병렬 알고리즘을 개념화하고 기술하는 간단한 방법을 제공합니다.WT 프레임워크에서는 우선 병렬 알고리즘이 병렬 라운드의 관점에서 설명된다.각 라운드에 대해 수행할 작업이 특징지어지지만 몇 가지 문제를 억제할 수 있습니다.예를 들어, 각 라운드의 동작의 수를 명확하게 할 필요는 없습니다.프로세서를 언급할 필요는 없습니다.프로세서를 작업에 할당하는 데 도움이 되는 정보는 설명하지 않아도 됩니다.둘째, 억제된 정보를 제공한다.억제된 정보의 포함은 사실 브렌트(1974년)로 인한 스케줄링 정리의 증명에 의해 유도된다.WT 프레임워크는 병렬 알고리즘의 초기 기술을 크게 단순화할 수 있지만 초기 기술에 의해 억제된 세부 정보를 삽입하는 것이 그리 어렵지 않기 때문에 유용합니다.예를 들어, WT 프레임워크는 병렬 알고리즘 책(PRAM 모델의 경우) JaJa(1992년)과 Keller, Kessler & Traeff(2001년) 및 클래스 노트 Vishkin(2009년)에서 기본 프레젠테이션 프레임워크로 채택되었다.Vishkin(2011)은 WT 프레임워크와 위에서 언급한 보다 기초적인 ICE 추상화 사이의 단순한 연관성을 설명한다.

XMT 패러다임은 프로그래밍 언어 C의 작은 확장인 병렬 멀티스레드 프로그래밍 언어인 XMTC를 사용하여 프로그래밍할 수 있습니다.XMT 패러다임에는 WT 프레임워크에서 알고리즘을 캐스팅하여 XMTC에서 프로그래밍하는 프로그래머의 워크플로우가 포함됩니다.

XMT 멀티 코어 컴퓨터 시스템은 여러 특허를 포함하는 멀티 스레드 프로그램의 런타임 로드 밸런싱을 제공합니다.그 중 하나는 von Neumann 아키텍처에서 멀티코어 하드웨어에 핵심인 프로그램 카운터 개념을 일반화한다.

XMT 프로토타이핑 및 추가 정보 링크

2007년 1월, 전체적인 컨셉을 나타내는 64 프로세서·컴퓨터 파라립이 ^[3]완성되었습니다.XMT 개념은 Vishkin 등(1998년)과 Naishlos 등에 제시되었다. (2003) 및 Wen & Vishkin(2008)의 XMT 64 프로세서 컴퓨터.병렬 프로그래밍을 쉽게 하는 것은 오늘날 컴퓨터 과학이 직면한 가장 큰 과제 중 하나이기 때문에, 이 데모에서는 고등학교 Torbert et al.(2010)에서 대학원까지 다양한 학생들에게 PRAM 알고리즘과 XMTC 프로그래밍의 기초를 가르치는 것도 시도했습니다.

실험적 작업 Caragea 및에 보도되고 최대 유량 문제에 대한 Vishkin(2011년), 에드워즈와 Vishkin(2012a, 2012b)에 의해는 Graph연결(접속성(그래프 이론)를 위해 두개의 서류)에 GraphBiconnectivity(biconnected 그래프)와 GraphTriconnectivity(Triconnected 구성 요소)문제 가장 진전을 보여 주었다.달.병렬 알고리즘 문헌의 알고리즘에 따르면 XMT 패러다임은 최첨단 멀티 코어 컴퓨터의 동일한 문제에 비해 8배에서 100배 이상의 속도 향상을 제공할 수 있습니다.보고된 각 속도 향상은 XMT 프로토타입의 클럭 사이클을 가장 빠른 시리얼 머신에서 실행되는 가장 빠른 시리얼 알고리즘과 비교하여 얻어진 것입니다.

XMT 프로토타이핑은 Ghanim, Vishkin & Barua(2018년)에서 정점을 찍었으며, 잠금 스텝 병렬 프로그래밍(ICE 사용)이 XMT 시스템에서 가장 빠른 수동 튜닝 멀티 스레드 코드와 동일한 성능을 달성할 수 있음을 확인했습니다.이 2018년 결과는 XMT 프로그래밍과 거의 모든 다른 코어 시스템에서 채택된 멀티 스레드 프로그래밍 접근 방식 간의 대조를 더욱 뚜렷하게 합니다. 이 시스템은 경쟁 조건과 다른 요구가 도전하는 경향이 있으며 프로그래머인 Vishkin(2014년)에 실패하는 경우도 있습니다.

레퍼런스

• 를 클릭합니다Brent, Richard P. (1974), "The parallel evaluation of general arithmetic expressions", Journal of the ACM, 21 (2): 201–208, CiteSeerX 10.1.1.100.9361, doi:10.1145/321812.321815.
• 를 클릭합니다Shiloach, Yossi; Vishkin, Uzi (1982), "An O(n² log n) parallel max-flow algorithm", Journal of Algorithms, 3 (2): 128–146, doi:10.1016/0196-6774(82)90013-X.
• JaJa, Joseph (1992), An Introduction to Parallel Algorithms, Addison-Wesley, ISBN 978-0-201-54856-3
• Keller, Jorg; Kessler, Cristoph W.; Traeff, Jesper L. (2001), Practical PRAM Programming, Wiley-Interscience, ISBN 978-0-471-35351-5
• 를 클릭합니다Naishlos, Dorit; Nuzman, Joseph; Tseng, Chau-Wen; Vishkin, Uzi (2003), "Towards a First Vertical Prototyping of an Extremely Fine-Grained Parallel Programming Approach" (PDF), Theory of Computing Systems, 36 (5): 551–552, doi:10.1007/s00224-003-1086-6.

• 를 클릭합니다Torbert, Shane; Vishkin, Uzi; Tzur, Ron; Ellison, David (2010), "Is teaching parallel algorithmic thinking to high school students possible?", Proceedings of the 41st ACM technical symposium on Computer science education - SIGCSE '10, p. 290, doi:10.1145/1734263.1734363, ISBN 9781450300063.
• 를 클릭합니다Vishkin, Uzi; Dascal, Shlomit; Berkovich, Efraim; Nuzman, Joseph (1998), "Explicit Multi-Threading (XMT) bridging models for instruction parallelism", Proc. 1998 ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 140–151.
• Vishkin, Uzi (2009), Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages (PDF), Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion
• 를 클릭합니다Wen, Xingzhi; Vishkin, Uzi (2008), "FPGA-based prototype of a PRAM-on-chip processor", Proc. 2008 ACM Conference on Computing Frontiers (Ischia, Italy) (PDF), pp. 55–66, doi:10.1145/1366230.1366240, ISBN 9781605580777.
• 를 클릭합니다Vishkin, Uzi (2011), "Using simple abstraction to reinvent computing for parallelism", Communications of the ACM, 54: 75–85, doi:10.1145/1866739.1866757.
• 를 클릭합니다Caragea, George; Vishkin, Uzi (2011), "Brief announcement: better speedups for parallel max-flow", Proc. 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 131–134, doi:10.1145/1989493.1989511, ISBN 9781450307437.
• 를 클릭합니다Edwards, James A.; Vishkin, Uzi (2012a), "Better speedups using simpler parallel programming for graph connectivity and biconnectivity", Proceedings of the 2012 International Workshop on Programming Models and Applications for Multicores and Manycores, pp. 103–114, doi:10.1145/2141702.2141714, ISBN 9781450312110.
• 를 클릭합니다Edwards, James A.; Vishkin, Uzi (2012b), "Brief announcement: speedups for parallel graph triconnectivity", Proc. 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 190–192, doi:10.1145/2312005.2312042, ISBN 9781450312134.
• 를 클릭합니다Vishkin, Uzi (2014), "Is Multi-Core Hardware for General-Purpose Parallel Processing Broken? Viewpoint article", Communications of the ACM, 57 (4): 35–39, doi:10.1145/2580945.
• 를 클릭합니다Ghanim, Fady; Vishkin, Uzi; Barua, Rajeev (February 2018), "Easy PRAM-Based High-Performance Parallel Programming with ICE", IEEE Transactions on Parallel and Distributed Systems, 29 (2): 377–390, doi:10.1109/TPDS.2017.2754376, hdl:1903/18521.

메모들

외부 링크

• XMT 프로젝트 홈페이지.소프트웨어 릴리즈, 온라인 튜토리얼 및 병렬 교육용 자료에 대한 링크를 제공합니다.