본문 바로가기

프로그래밍/병렬프로그래밍22

[pthread] Thread 동기화 References An Introduction to Parallel Programming Contents Semaphore (세마포어) Producer-Consumer Synchronization 각 스레드는 다른 스레드로 '메세지 전송'을 수행하고 전송받은 메세지를 출력하는 프로그램을 작성한다고 가정해봅시다. 예를 들어, t개의 스레드가 있을 때, 스레드 0은 스레드 1로 메세지를 전송하고 스레드 1은 스레드 2로 메세지를 전송합니다. 즉, 스레드 t-2는 스레드 t-1에게 메세지 전송하고 스레드 t-1은 스레드 0에게 메세지를 전송합니다. 그리고 스레드는 메세지를 수신한 후에 수신받은 메세지를 출력하고 스레드를 종료합니다. 메세지 전송을 구현하기 위해서 char* 타입의 공유 배열을 할당하고, 각 .. 2021. 11. 18.
[pthread] Critical Section References An Introduction to Parallel Programming Contents PI 값 구하기 Critical Section (크리티컬 섹션) Busy waiting Mutex (뮤텍스) 행렬-벡터 연산 코드는 꽤 쉽게 작성했습니다. 이는 공유 메모리 위치를 쉽게 액세스할 수 있기 때문입니다. 초기화 이후에, y를 제외한 모든 변수들은 각 스레드에서 쉽게 접근할 수 있습니다. 즉, y를 제외한 모든 공유 변수들은 main 스레드에서 초기화된 이후에 변경될 수 없다는 것을 의미합니다. 게다가 y에 대해서 무언가 변경을 하려고 하더라도 오직 하나의 스레드만이 개별 컴포넌트를 변경할 수 있습니다. 따라서 두 스레드(혹은 그 이상)가 하나의 컴포넌트를 변경하지 않습니다. 잘 아시겠지.. 2021. 11. 17.
[pthread] 행렬 - 벡터 곱 연산 (+ 캐시 일관성, 거짓 공유) References An Introduction to Parallel Programming Contents 행렬-벡터 곱 연산 병렬화 Cache, Cache Coherence, False Sharing 이전에 MPI를 통해서 행렬-벡터 곱 연산을 병렬화하고 그 성능을 평가해보았습니다. 2021.11.12 - [프로그래밍/병렬프로그래밍] - [MPI] 행렬 - 벡터 곱 연산 + 성능 평가 [MPI] 행렬 - 벡터 곱 연산 + 성능 평가 References An Introduction of Parallel Programming Contents 행렬 - 벡터 곱 연산 MPI_Allgather MPI_Wtime, MPI_Barrier 이번에는 행렬-벡터 곱 연산을 MPI를 사용하여 병렬화해보도록 하겠습니다. \.. 2021. 11. 16.
[pthread] Hello, Pthreads References An Introduction to Parallel Programming Contents 공유 메모리 시스템 프로세스, 스레드 그리고 pthreads Hello, Pthreads 개발자 입장에서 공유 메모리 시스템은 모든 코어가 모든 메모리 위치에 접근할 수 있습니다. 그러므로 공유 메모리 시스템에서의 접근 방법은 특정 메모리 위치를 "공유"하도록 설정하는 것입니다. 이는 병렬 프로그래밍에서 당연한 방법입니다. 그러나 앞으로 pthread에 대해서 알아보면서 공유 메모리 시스템에서 프로그래밍할 때 문제가 있다는 것을 알아보도록 할 것입니다. 이러한 문제점들은 분산 메모리 프로그램에서 발생한 문제와는 조금 다릅니다. 프로세스, 스레드, Pthreads 스레드(thread)는 MPI 프로그.. 2021. 11. 15.
[MPI] Odd-even transposition sort (MPI Safety) References An Introduction to Parallel Programming Contents Odd-even transposition sort MPI Safety, MPI_Ssend MPI_Sendrecv 성능 측정 및 비교 분산 메모리 환경에서 병렬 정렬 알고리즘은 무엇을 의미할까요 ? 무엇이 '입력'이 되고, 무엇이 '출력'이 될까요? 이는 정렬하고자하는 키(key)에 달려 있습니다. 프로세스 간에 분산된 키를 가지고 시작하거나 하나의 프로세스에 할당된 키로 시작할 수도 있습니다. 이번 포스팅에서는 프로세스 간 분산된 키를 사용하는 정렬 알고리즘을 살펴보겠습니다. 만약 n개의 키가 있고, 프로세스 p = comm_sz개가 있다면, 각 프로세스에 \(\frac{n}{p}\)개의 키를 할당.. 2021. 11. 13.
[MPI] MPI Derived Datatypes (파생 데이터타입) References An Introduction to Parallel Programming Contents MPI Derived Datatypes MPI_Type_create_struct, MPI_Type_commit, MPI_Type_free 분산 메모리 시스템에서의 통신은 로컬 연산보다 훨씬 cost가 큽니다. 예를 들어, 한 노드에서 다른 노드로 double형을 전송하는 것은 노드의 로컬 메모리에 저장된 두 개의 double형을 덧셈하는 것보다 훨씬 더 시간이 많이 걸립니다. 게다가, 다중 메세지에서 고정된 양의 데이터를 전송하는 cost는 보통 하나의 메세지에서 동일한 양의 데이터를 전송하는 것보다 훨씬 큽니다. 따라서, 하나의 send/recieve 쌍보다 다음의 for 루프가 훨씬 느릴 것으로.. 2021. 11. 13.
[MPI] 행렬 - 벡터 곱 연산 + 성능 평가 References An Introduction to Parallel Programming Contents 행렬 - 벡터 곱 연산 MPI_Allgather MPI_Wtime, MPI_Barrier 이번에는 행렬-벡터 곱 연산을 MPI를 사용하여 병렬화해보도록 하겠습니다. \(\text{A}\)가 m x n 행렬이고, \(\textbf{x}\)가 n개의 컴포넌트를 갖고 있는 벡터라면, \(\textbf{y} = \text{A}\textbf{x}\)는 m개의 컴포넌트를 갖는 벡터가 됩니다. 그리고 y의 i번째 컴포넌트는 행렬 A의 i번째 행과 x의 dot product로 계산할 수 있습니다. 이 연산을 시리얼로 의사 코드를 작성하면, 다음과 같습니다. 위 코드는 일반적인 C코드입니다. 위에서 행렬을 표현하기.. 2021. 11. 12.
[MPI] 데이터 분산 (벡터합 병렬화) References An Introduction to Parallel Programming Contents 데이터 분산(distribution) MPI_Scatter, MPI_Gather 이번에는 MPI에서 벡터의 합을 어떻게 구하는지 살펴보도록 하겠습니다. 아래처럼 벡터의 합을 계산하는 함수를 작성한다고 가정해봅시다. \[\begin{align*}\textbf{x} + \textbf{y} &= (x_0, x_1, \cdots, x_{n-1}) + (y_0, y_1, \cdots, y_{n-1}) \\ &= (x_0 + y_0, x_1 + y_1, \cdots, x_{n-1} + y_{n-1}) \\ &= (z_0, z_1, \cdots, z_{n-1}) \\ &= \textbf{z} \end{align.. 2021. 11. 11.
[MPI] 사다리꼴 공식 (trapezoidal rule) 병렬화 - 2 References An Introduction to Parallel Programming Contents Collective Communication (집합 통신) MPI_Reduce, MPI_Allreduce, MPI_Bcast 이전 글에서 MPI로 사다리꼴 공식을 병렬화하여 코드를 작성해봤습니다. 2021.11.09 - [프로그래밍/병렬프로그래밍] - [MPI] 사다리꼴 공식 (trapezoidal rule) - 1 하지만 작성한 코드에서 각 프로세스들은 연산을 수행하고 그 연산 결과를 합하기 위하여 프로세스 0에게 결과를 전달하고, 프로세스 0에서 모든 결과를 더하는 작업을 수행합니다. 이전 글 마지막에 언급했듯이 이러한 작업이 최선이 아니고, 성능을 향상시킬 수 있는 여지가 남아있습니다. 트리 .. 2021. 11. 10.
[MPI] 사다리꼴 공식 (trapezoidal rule) 병렬화 - 1 References An Introduction to Parallel Programming Contents Trapezoidal rule 병렬화 I/O의 처리 사다리꼴 공식 (trapezoidal rule) 이번에는 MPI를 사용하여 사다리꼴 공식(trapezoidal rule)을 병렬화해보도록 하겠습니다. 사다리꼴 공식은 적분을 근사하는 수치적분 방법인데, 적분이 나타내는 넓이를 일련의 사다리꼴들의 넓의의 합으로 근사합니다. (참고 : 위키백과) 우리는 이 사다리꼴 규칙을 사용하여 \(y = f(x)\)라는 함수에 대한 그래프 사이의 영역에 대한 넓이의 근사값을 구해볼 것입니다. 기본적인 아이디어는 x축의 내부를 n개의 동일한 서브인터벌(subinterval)로 구분합니다. 그리고, 그래프와 각 서브인.. 2021. 11. 9.