From Wikipedia, the free encyclopedia

In computing, SPMD (Single Process, Multiple Data) or (Single Program, Multiple Data) is a technique employed to achieve parallelism; it is a subcategory of MIMD. Tasks are split up and run simultaneously on multiple processors with different input in order to obtain results faster. SPMD is the most common style of parallel programming[1]. It is also a prerequisite for research concepts such as active messages and distributed shared memory.

Computing에서 SPMD는 병렬화 작업을 위한 테크닉이다; 이것은 MIMD의 하위 카테고리이다. 다른 input에 대해 결과를 빠르게 얻기 위해서 Task들을 쪼개고, 여러개의 프로세서에서 동시에 실행시킨다. SPMD는 Parallel Programming 스타일 중에 가장 보편적인 것이다. Active Messages와 Distributed Shared memory와 같은 지식들도 SPMD Concept을 연구하기 위해 필수이다.

SPMD vs SIMD

In SPMD, multiple autonomous processors simultaneously execute the same program at independent points, rather than in the lockstep that SIMD imposes on different data. With SPMD, tasks can be executed on general purpose CPUs; SIMD requires vector processors to manipulate data streams. Note that the two are not mutually exclusive.

SPMD에서 SIMD의 다른 데이터에 대해 강요하는 고정적인 방법에서 보다 자발적으로 여러개의 프로세서들은 각 독립적인 위치에서 똑같은 프로그램을 동시에 실행시킨다. SPMD를 이용하여 CPU들의 일반적인 Purpose로 task들을 실행할 수 있다;SIMD는 데이터 stream을 생성하기 위해 vector processor들을 필요로 한다. SPMD와 SIMD는 상호 배타적인 관계는 아니다.

Distributed memory

SPMD usually refers to message passing programming on distributed memory computer architectures. A distributed memory computer consists of a collection of independent computers, called nodes. Each node starts its own program and communicates with other nodes by sending and receiving messages, calling send/receive routines for that purpose. Barrier synchronization may also be implemented by messages. The messages can be sent by a number of communication mechanisms, such as TCP/IP over Ethernet, or specialized high-speed interconnects such as Myrinet and Supercomputer Interconnect. Serial sections of the program are implemented by identical computation on all nodes rather than computing the result on one node and sending it to the others.

SPMD는 일반적으로 분산 메모리 컴퓨터 아키텍쳐에서의 message passing programming으로 간주된다. 분산메모리 컴퓨터는 node라고 불리는 독립적인 컴퓨터들의 집합으로 구성되어진다. 각 node는 그들 자신의 프로그램을 실행하고 메세지를 주고 받는 것으로 다른 node들과 통신하고, 이를 위해 send/receive 루틴을 사용한다. 메세지들은 Ethernet을 통한 TCP/IP와 같이 통신 메카니즘들의 갯수에 의해 전달 될 수 있고, 혹은 Myrinet 와 Supercomputer Interconnect와 같은 특화된 high-speed interconnect를 사용하여 전달 될 수 있다. 프로그램의 Serial section들은 하나의 노드에서 결과를 계산하고 그것을 다른 노드들로 보내는 방식보다, 모든 노드들의 각 노드들의 고유 연산에 의해 구현되어진다.

Nowadays, the programmer is isolated from the details of the message passing by standard interfaces, such as PVM and MPI.

최근에, PVM이나 MPI처럼 programmer는 일반적 interface들에 의한 message passing의 세부구현은 신경쓰지 않아도 된다

Distributed memory is the programming style used on parallel supercomputers from homegrown Beowulf clusters to the largest clusters on the Teragrid.

 분산메모리는 Teragrid에서 가장 큰 클러스터들을 위한 homegrown Beowulf cluster들에서 Parallel supercomputers에서 사용하기위한 programming style이다

Shared memory

On a shared memory machine (a computer with several CPUs that access the same memory space), messages can be sent by depositing their contents in a shared memory area. This is often the most efficient way to program shared memory computers with large number of processors, especially on NUMA machines, where memory is local to processors and accessing memory of another processor takes longer. SPMD on a shared memory machine is usually implemented by standard (heavyweight) processes.

공유 메모리 머신(컴퓨터의 여러개의 CPU들이 같은 메모리 공간에 접근하는 형태) 상에서, message들은 공유 메모리 영역에 그들의 data를 저장해 두는 것으로 전달되어 질 수 있다. 이것은 종종 processor가 대량으로 있는 형태에서 프로그램이 컴퓨터의 공유메모리를 활용하는 가장 효과적인 방법이다. 특히 NUMA 기계들에서 메모리는 processor들을 위한 공간이고 다른 processor들의 접근가능한 메모리이다. 공유 메모리 기계상에서 SPMD는 보통 standard(heavyweight) 프로세서들에 의해 구현되어진다.

Unlike SPMD, shared memory multiprocessing, also called symmetric multiprocessing or SMP, presents the programmer with a common memory space and the possibility to parallelize execution by having the program take different paths on different processors. The program starts executing on one processor and the execution splits in a parallel region, which is started when parallel directives are encountered. In a parallel region, the processors execute a single program on different data. A typical example is the parallel DO loop, where different processors work on separate parts of the arrays involved in the loop. At the end of the loop, execution is synchronized, only one processor continues, and the others wait. The current standard interface for shared memory multiprocessing is OpenMP. It usually implemented by lightweight processes, called threads.

SPMD와 다르게, 공유 메모리 multiprocessing은 SMP혹은 대칭 multiprocessing이라고 불리며, programmer에게 일반적 메모리 공간과 그리고 다른 processor들 상에서 프로그램이 다른 경로를 사용하게 함으로서 병렬 수행을 위한 가능성을 제공한다. 프로그램은 하나의 Processor에서 실행되기 시작하고, 수행작업은 parallel region으로 나눠지고, Parallel처리를 하기 시작한다. Parallel region에서 processor들은 다른 데이터에 대해 동일한 프로그램을 실행한다. 일반적인 예로는 Parallel DO loop구조이며, 이것이 다른 processor들에서 배열들의 일부분을 가져와 작업을 수행한다. Loop의 마지막에는, 수행되는 작업은 동기화되며, 단 하나의 프로세서는 계속 작업을 하고 다른 프로세서들은 Wait상태가 된다. 공유 메모리 multiprocessing을 위한 현재의 표준 interface는 OpenMP이다. 이것은 보통 thread라고 불리는 lightweight process들에 의해 구현되어 진다

Combination of levels of parallelism

Current computers allow exploiting of many parallel modes at the same time for maximum combined effect. A distributed memory program using MPI may run on a collection of nodes. Each node may be a shared memory computer and execute in parallel on multiple CPUs using OpenMP. Within each CPU, SIMD vector instructions (usually generated automatically by the compiler) and superscalar instruction execution (usually handled transparently by the CPU itself), such as pipelining and the use of multiple parallel functional units, are used for maximum single CPU speed.

현재 컴퓨터들은 동시에 최대 combined effect를 위한 많은 병렬화 방법들의 개발을 허용하고 있다. MPI를 이용한 분산 메모리 program은 아마 node들의 집합단위로 실행되어질 것이다. 각 CPU에서 pipelining과 parallel functional unit들의 사용과 같이, SIMD 벡터 instruction들(보통 컴파일러에 의해 자동적으로 생성된다) 그리고 superscalar instruction 수행(보통 CPU에 의해 투명하게 핸들링된다) 은 single CPU 속도를 최대화 하기 위해 사용된다.

History

SPMD was proposed in 1984 by Frederica Darema at IBM for highly parallel machines like the RP3 (the IBM Research Parallel Processor Prototype), in an unpublished IBM memo^[1] By late 1980s, there were many distributed computers with proprietary message passing libraries. The first SPMD standard was PVM. The current de-facto standard is MPI.

The Cray parallel directives were a direct predecessor of OpenMP.