병렬 램

Parallel RAM

컴퓨터 과학에서 병렬 랜덤 액세스 머신(병렬 RAM 또는 PRAM)은 공유 메모리 추상 머신이다. 이름에서 알 수 있듯이 PRAM은 RAM(Random-Access Memory와 혼동되지 않도록)과 병렬 컴퓨팅 유사성을 목적으로 한다. 순차 알고리즘 설계자가 RAM을 사용하여 알고리즘 성능을 모델링(시간 복잡성 등)하는 것과 마찬가지로 PRAM은 병렬 알고리즘 설계자가 병렬 알고리즘 성능을 모델링하는 데 사용한다(시간 복잡성과 같이, 일반적으로 가정된 프로세서의 개수가 명시되어 있는 경우). RAM 모델이 캐시 메모리 대 메인 메모리와 같은 실제적인 문제를 무시하는 것과 유사하게, PRAM 모델은 동기화 및 통신과 같은 문제를 무시하지만 (문제 크기 의존적인) 프로세서의 수를 제공한다. 예를 들어 알고리즘 비용은 두 매개변수 O(시간)와 O(시간 × processor_number)를 사용하여 추정한다.

읽기/쓰기 충돌

동일한 공유 메모리 위치에 동시에 액세스할 때 일반적으로 인터락이라고 하는 읽기/쓰기 충돌은 다음 전략 중 하나로 해결된다.

  1. 단독 읽기 전용 쓰기(ERW)—모든 메모리 셀은 한 번에 하나의 프로세서에 의해서만 읽거나 쓸 수 있다.
  2. 동시 읽기 전용 쓰기(CRW)—여러 프로세서가 메모리 셀을 읽을 수 있지만 한 번에 하나만 쓸 수 있음
  3. 전용 읽기 동시 쓰기(ERCW) - 고려되지 않음
  4. 동시 읽기 동시 쓰기(CRCW)—여러 프로세서가 읽고 쓸 수 있다. CRCW PRAM은 때때로 동시 랜덤 액세스 기계라고 불린다.[1]

여기서 E와 C는 각각 '독점'과 '동류'를 의미한다. 동시 쓰기는 다음과 같이 정의되는 동안 읽기는 불일치를 일으키지 않는다.

공통—모든 프로세서가 동일한 값을 쓰지만 그렇지 않으면 불법임
임의적(임의적) - 하나의 임의적 시도만 성공하고 다른 시도들은 폐기함
우선 순위—프로세서 순위는 쓰려는 사용자를 나타냄
SUM, Logical AND 또는 MAX와 같은 또 다른 종류의 어레이 축소 작업.

PRAM에 대한 알고리즘 개발을 고려하면서 몇 가지 간단한 가정을 한다. 다음 구성 요소:

  1. 기계의 프로세서 수에는 제한이 없다.
  2. 모든 메모리 위치는 모든 프로세서에서 균일하게 액세스할 수 있다.
  3. 시스템의 공유 메모리 양에는 제한이 없다.
  4. 리소스 경합이 없음
  5. 이러한 기계에 쓰여진 프로그램은 일반적으로 SIMD 유형이다.

이러한 종류의 알고리즘은 동시성의 착취를 이해하고, 원래의 문제를 유사한 하위 문제로 나누어 병렬로 해결하는 데 유용하다. Wyllie의 1979년 논문에서[2] 공식적인 'P-RAM' 모델의 도입은 튜링 기계와 유사한 방식으로 병렬 알고리즘의 분석을 정량화하는 것을 목적으로 했다. 분석은 CRUE 모델을 이용한 프로그래밍의 MIMD 모델에 초점을 맞췄지만, CRCW 모델을 구현하고 SIMD 기계에 구현하는 등 많은 변종이 일정한 오버헤드만으로 가능하다는 것을 보여주었다.

실행

PRAM 알고리즘은 DRAM이 동시 액세스를 허용하지 않기 때문에 CPU와 DRAM(Dynamic Random-Access Memory)의 조합과 병행할 수 없지만, 하드웨어에서 구현하거나 FPGA(Field-Programmable Gate Array)의 내부 정적 RAM(SRAM) 블록에 읽기/쓰기할 수 있으므로 CRCW 알고리즘을 사용하여 실행할 수 있다.

그러나 PRAM(또는 RAM) 알고리즘의 실제 관련성에 대한 시험은 비용 모델이 일부 컴퓨터의 효과적인 추상화를 제공하는지에 따라 달라진다. 컴퓨터의 구조는 추상적 모델과 상당히 다를 수 있다. 삽입할 필요가 있는 소프트웨어와 하드웨어의 레이어에 대한 지식은 이 글의 범위를 벗어난다. 그러나 Vishkin(2011)과 같은 기사는 PRAM과 같은 추상화가 어떻게 명시적 멀티스레딩(XMT) 패러다임에 의해 지지될 수 있는지, Caragea & Vishkin(2011)과 같은 기사는 최대 흐름 문제에 대한 PRAM 알고리즘이 동일한 문제에 대한 가장 빠른 직렬 프로그램에 비해 강력한 속도를 제공할 수 있음을 보여준다. 기사 Ghanim, Vishkin & Barua(2018)는 XMT에서 PRAM 알고리즘을 멀티스레드 프로그램으로 캐스팅하려는 추가 노력 없이도 경쟁적 성능을 달성할 수 있음을 보여주었다.

예시 코드

이는 단 2회의 클럭 사이클에서 배열의 최대값을 찾는 SystemVerilog 코드의 예다. 첫 번째 클럭에서 배열 원소의 모든 조합을 비교하고, 두 번째 클럭에서 결과를 병합한다. CRCW 메모리를 사용한다. m[i] <= 1 그리고 maxNo <= data[i] 동시에 쓰여진다. 알고리즘은 동일한 값이 동일한 메모리에 기록된다는 것을 보증하기 때문에 동시성은 충돌을 일으키지 않는다. 이 코드는 FPGA 하드웨어에서 실행할 수 있다. 

모듈 FindMax #(매개 변수 인트로 렌 = 8)                 (입력하다 물다 시계를 맞추다, 리셋N, 입력하다 물다[7:0] 자료[렌], 생산량 물다[7:0] 맥스노);     타이피프 열거하다 물다[1:0] {비교, 병합, 완료} 주;                          주 주;     물다 m[렌];     인트로 i, j;          always_ff @(양지의 시계를 맞추다, 바싹 다가붙다 리셋N) 시작되다         만일 (!리셋N) 시작되다             을 위해 (i = 0; i < 렌; i++) m[i] <= 0;             주 <= 비교;         종지부를 찍다 다른 시작되다             케이스 (주)                 비교: 시작되다                     을 위해 (i = 0; i < 렌; i++) 시작되다                         을 위해 (j = 0; j < 렌; j++) 시작되다                             만일 (자료[i] < 자료[j]) m[i] <= 1;                         종지부를 찍다                     종지부를 찍다                     주 <= 병합;                 종지부를 찍다                                  병합: 시작되다                     을 위해 (i = 0; i < 렌; i++) 시작되다                         만일 (m[i] == 0) 맥스노 <= 자료[i];                     종지부를 찍다                     주 <= 완료;                 종지부를 찍다             말단 케이스         종지부를 찍다     종지부를 찍다 종말모듈

참고 항목

참조

  1. ^ Neil Imerman, 표현성 및 병렬 복잡성. SIAM 컴퓨터 저널, 제18권, 제3권, 페이지 625-638, 1989.
  2. ^ 윌리, 제임스 C 코넬대학교 컴퓨터과학과 박사과정, 박사과정, 병렬컴퓨팅의 복잡성
  • Eppstein, David; Galil, Zvi (1988), "Parallel algorithmic techniques for combinatorial computation", Annu. Rev. Comput. Sci., 3: 233–283, doi:10.1146/annurev.cs.03.060188.001313
  • JaJa, Joseph (1992), An Introduction to Parallel Algorithms, Addison-Wesley, ISBN 0-201-54856-9
  • Karp, Richard M.; Ramachandran, Vijaya (1988), A Survey of Parallel Algorithms for Shared-Memory Machines, University of California, Berkeley, Department of EECS, Tech. Rep. UCB/CSD-88-408
  • Keller, Jörg; Christoph Keßler; Jesper Träff (2001). Practical PRAM Programming. John Wiley and Sons. ISBN 0-471-35351-5.
  • 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
  • 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 Constantin; Vishkin, Uzi (2011), "Brief announcement: Better speedups for parallel max-flow", Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA '11, p. 131, doi:10.1145/1989493.1989511, ISBN 9781450307437
  • Ghanim, Fady; Vishkin, Uzi; Barua, Rajeev (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

외부 링크