병렬 랜덤 액세스 머신

Parallel Random Access Machines (PRAM)대부분의 병렬 알고리즘에서 고려되는 모델입니다. 여기서 여러 프로세서가 단일 메모리 블록에 연결됩니다. PRAM 모델에는-

유사한 유형의 프로세서 세트.
모든 프로세서는 공통 메모리 장치를 공유합니다. 프로세서는 공유 메모리를 통해서만 서로 통신 할 수 있습니다.
MAU (메모리 액세스 장치)는 프로세서를 단일 공유 메모리와 연결합니다.

여기, n 프로세서의 수는 독립적 인 작업을 수행 할 수 있습니다. n특정 시간 단위의 데이터 수. 이로 인해 서로 다른 프로세서가 동일한 메모리 위치에 동시에 액세스 할 수 있습니다.

이 문제를 해결하기 위해 PRAM 모델에 다음과 같은 제약이 적용되었습니다.

Exclusive Read Exclusive Write (EREW) − 여기서는 두 개의 프로세서가 동시에 같은 메모리 위치에서 읽거나 쓸 수 없습니다.
Exclusive Read Concurrent Write (ERCW) − 여기서 두 개의 프로세서는 동시에 같은 메모리 위치에서 읽을 수 없지만 동시에 같은 메모리 위치에 쓸 수 있습니다.
Concurrent Read Exclusive Write (CREW) − 여기서 모든 프로세서는 동일한 메모리 위치에서 동시에 읽을 수 있지만 동시에 같은 메모리 위치에 쓸 수는 없습니다.
Concurrent Read Concurrent Write (CRCW) − 모든 프로세서는 동일한 메모리 위치에서 동시에 읽거나 쓸 수 있습니다.

PRAM 모델을 구현하는 방법은 여러 가지가 있지만 가장 두드러진 방법은 다음과 같습니다.

공유 메모리 모델
메시지 전달 모델
데이터 병렬 모델

공유 메모리 모델

공유 메모리는 control parallelism ~보다 data parallelism. 공유 메모리 모델에서 여러 프로세스는 서로 다른 프로세서에서 독립적으로 실행되지만 공통 메모리 공간을 공유합니다. 프로세서 활동으로 인해 메모리 위치가 변경되면 나머지 프로세서에서 볼 수 있습니다.

여러 프로세서가 동일한 메모리 위치에 액세스 할 때 특정 시점에 둘 이상의 프로세서가 동일한 메모리 위치에 액세스 할 수 있습니다. 하나는 그 위치를 읽고 다른 하나는 그 위치에 쓰고 있다고 가정합니다. 혼란을 일으킬 수 있습니다. 이를 방지하기 위해 다음과 같은 일부 제어 메커니즘이 있습니다.lock / semaphore, 상호 배제를 보장하기 위해 구현됩니다.

공유 메모리 프로그래밍은 다음에서 구현되었습니다.

Thread libraries− 스레드 라이브러리는 동일한 메모리 위치에서 동시에 실행되는 여러 제어 스레드를 허용합니다. 스레드 라이브러리는 서브 루틴 라이브러리를 통해 멀티 스레딩을 지원하는 인터페이스를 제공합니다. 다음을위한 서브 루틴을 포함합니다.
- 스레드 생성 및 삭제
- 스레드 실행 예약
- 스레드간에 데이터 및 메시지 전달
- 스레드 컨텍스트 저장 및 복원

스레드 라이브러리의 예로는 Solaris 용 SolarisTM 스레드, Linux에서 구현 된 POSIX 스레드, Windows NT 및 Windows 2000에서 사용 가능한 Win32 스레드, 표준 JDK (JavaTM Development Kit)의 일부인 JavaTM 스레드가 있습니다.

Distributed Shared Memory (DSM) Systems− DSM 시스템은 하드웨어 지원없이 공유 메모리 프로그래밍을 구현하기 위해 느슨하게 결합 된 아키텍처에서 공유 메모리의 추상화를 생성합니다. 표준 라이브러리를 구현하고 최신 운영 체제에있는 고급 사용자 수준 메모리 관리 기능을 사용합니다. 예를 들어 트레드 마크 시스템, Munin, IVY, Shasta, Brazos 및 Cashmere가 있습니다.
Program Annotation Packages− 이는 균일 한 메모리 액세스 특성을 갖는 아키텍처에서 구현됩니다. 프로그램 주석 패키지의 가장 주목할만한 예는 OpenMP입니다. OpenMP는 기능적 병렬 처리를 구현합니다. 주로 루프의 병렬화에 중점을 둡니다.

공유 메모리의 개념은 공유 메모리 시스템의 낮은 수준의 제어를 제공하지만 지루하고 오류가 많은 경향이 있습니다. 응용 프로그래밍보다 시스템 프로그래밍에 더 적합합니다.

공유 메모리 프로그래밍의 장점

전역 주소 공간은 메모리에 대한 사용자 친화적 인 프로그래밍 접근 방식을 제공합니다.
메모리가 CPU에 가깝기 때문에 프로세스 간의 데이터 공유가 빠르고 균일합니다.
프로세스 간의 데이터 통신을 명확하게 지정할 필요가 없습니다.
프로세스 통신 오버 헤드는 무시할 수 있습니다.
배우는 것은 매우 쉽습니다.

공유 메모리 프로그래밍의 단점

휴대용이 아닙니다.
데이터 지역을 관리하는 것은 매우 어렵습니다.

메시지 전달 모델

메시지 전달은 분산 메모리 시스템에서 가장 일반적으로 사용되는 병렬 프로그래밍 접근 방식입니다. 여기에서 프로그래머는 병렬성을 결정해야합니다. 이 모델에서 모든 프로세서는 자체 로컬 메모리 장치를 가지고 있으며 통신 네트워크를 통해 데이터를 교환합니다.

프로세서는 서로 통신하기 위해 메시지 전달 라이브러리를 사용합니다. 전송되는 데이터와 함께 메시지에는 다음 구성 요소가 포함됩니다.

메시지가 전송되는 프로세서의 주소.
송신 프로세서에서 데이터의 메모리 위치 시작 주소;
보내는 데이터의 데이터 유형.
보내는 데이터의 데이터 크기
메시지가 전송되는 프로세서의 주소.
수신 프로세서의 데이터에 대한 메모리 위치의 시작 주소입니다.

프로세서는 다음 방법 중 하나로 서로 통신 할 수 있습니다.

지점 간 통신
집단 커뮤니케이션
메시지 전달 인터페이스

지점 간 통신

지점 간 통신은 메시지 전달의 가장 간단한 형태입니다. 여기서 메시지는 다음 전송 모드 중 하나에 의해 송신 프로세서에서 수신 프로세서로 전송 될 수 있습니다.

Synchronous mode − 다음 메시지는 메시지의 순서를 유지하기 위해 이전 메시지가 전달되었다는 확인을받은 후에 만 전송됩니다.
Asynchronous mode − 다음 메시지를 전송하기 위해 이전 메시지 전송 확인을받을 필요가 없습니다.

집단 커뮤니케이션

집합 적 통신에는 메시지 전달을 위해 두 개 이상의 프로세서가 포함됩니다. 다음 모드는 집단 통신을 허용합니다-

Barrier − 통신에 포함 된 모든 프로세서가 특정 블록을 실행하면 배리어 모드가 가능합니다. barrier block) 메시지 전달.
Broadcast − 방송은 두 가지 유형이 있습니다 −
- One-to-all − 여기서 단일 작업을 수행하는 하나의 프로세서는 다른 모든 프로세서에 동일한 메시지를 보냅니다.
- All-to-all − 여기서 모든 프로세서는 다른 모든 프로세서에 메시지를 보냅니다.

방송되는 메시지는 세 가지 유형이 있습니다.

Personalized − 고유 메시지는 다른 모든 대상 프로세서로 전송됩니다.
Non-personalized − 모든 대상 프로세서가 동일한 메시지를받습니다.
Reduction − 축소 방송에서 그룹의 한 프로세서는 그룹의 다른 모든 프로세서로부터 모든 메시지를 수집하여 그룹의 다른 모든 프로세서가 액세스 할 수있는 단일 메시지로 결합합니다.

메시지 전달의 장점

낮은 수준의 병렬 처리 제어를 제공합니다.
휴대용입니다.
오류가 적습니다.
병렬 동기화 및 데이터 배포의 오버 헤드가 적습니다.

메시지 전달의 단점

병렬 공유 메모리 코드와 비교할 때 메시지 전달 코드에는 일반적으로 더 많은 소프트웨어 오버 헤드가 필요합니다.

메시지 전달 라이브러리

많은 메시지 전달 라이브러리가 있습니다. 여기에서 가장 많이 사용되는 메시지 전달 라이브러리 두 가지에 대해 설명합니다.

메시지 전달 인터페이스 (MPI)
병렬 가상 머신 (PVM)

메시지 전달 인터페이스 (MPI)

분산 메모리 시스템의 모든 동시 프로세스간에 통신을 제공하는 범용 표준입니다. 일반적으로 사용되는 대부분의 병렬 컴퓨팅 플랫폼은 메시지 전달 인터페이스의 구현을 하나 이상 제공합니다. 호출 된 미리 정의 된 함수 모음으로 구현되었습니다.library C, C ++, Fortran 등과 같은 언어에서 호출 할 수 있습니다. MPI는 다른 메시지 전달 라이브러리에 비해 빠르고 이식 가능합니다.

Merits of Message Passing Interface

공유 메모리 아키텍처 또는 분산 메모리 아키텍처에서만 실행됩니다.
각 프로세서에는 고유 한 지역 변수가 있습니다.
대용량 공유 메모리 컴퓨터에 비해 분산 메모리 컴퓨터는 비용이 저렴합니다.

Demerits of Message Passing Interface

병렬 알고리즘에는 더 많은 프로그래밍 변경이 필요합니다.
때로는 디버깅하기가 어렵습니다. 과
노드 간의 통신 네트워크에서 잘 수행되지 않습니다.

병렬 가상 머신 (PVM)

PVM은 별도의 이기종 호스트 시스템을 연결하여 단일 가상 시스템을 형성하도록 설계된 휴대용 메시지 전달 시스템입니다. 관리 가능한 단일 병렬 컴퓨팅 리소스입니다. 초전도 연구, 분자 역학 시뮬레이션 및 매트릭스 알고리즘과 같은 대규모 계산 문제는 많은 컴퓨터의 메모리와 집계 능력을 사용하여보다 비용 효율적으로 해결할 수 있습니다. 호환되지 않는 컴퓨터 아키텍처의 네트워크에서 모든 메시지 라우팅, 데이터 변환, 작업 예약을 관리합니다.

Features of PVM

설치 및 구성이 매우 쉽습니다.
여러 사용자가 동시에 PVM을 사용할 수 있습니다.
한 사용자가 여러 응용 프로그램을 실행할 수 있습니다.
작은 패키지입니다.
C, C ++, Fortran 지원;
주어진 PVM 프로그램 실행에 대해 사용자는 머신 그룹을 선택할 수 있습니다.
메시지 전달 모델입니다.
프로세스 기반 계산;
이기종 아키텍처를 지원합니다.

데이터 병렬 프로그래밍

데이터 병렬 프로그래밍 모델의 주요 초점은 데이터 세트에 대한 작업을 동시에 수행하는 것입니다. 데이터 세트는 배열, 하이퍼 큐브 등과 같은 구조로 구성됩니다. 프로세서는 동일한 데이터 구조에 대해 집합 적으로 작업을 수행합니다. 각 작업은 동일한 데이터 구조의 다른 파티션에서 수행됩니다.

모든 알고리즘이 데이터 병렬성 측면에서 지정 될 수있는 것은 아니므로 제한적입니다. 이것이 데이터 병렬성이 보편적이지 않은 이유입니다.

데이터 병렬 언어는 데이터 분해 및 프로세서에 대한 매핑을 지정하는 데 도움이됩니다. 또한 프로그래머가 데이터를 제어 할 수 있도록하는 데이터 배포 문 (예 : 어떤 데이터가 어떤 프로세서로 이동하는지)을 포함하여 프로세서 내 통신량을 줄입니다.