---
tags: Multi-threading in Java
---

# 016: Cách thiết kế chương trình **parallel execution** P1

Bài viết nằm trong series [Multithread từ hardware tới software với Java](https://hackmd.io/@datbv/r1uoC54Kd).

Chúng ta đã đi qua một loạt về cơ chế, cách hoạt động của **hardware** với **single/multi-processors** và implement **software** với **multi-thread** chỉ nhằm mục đích duy nhất: tăng tốc chương trình.

Lý thuyết đã nắm vững, bước quan trọng nhất là làm thế nào để thiết kế một chương trình **parallel execution**, tối đa sức mạnh của **multi-processors**.

Chủ đề hôm nay sẽ bàn về các step để thiết kế chương trình **parallel execution**, gồm có 4 phần:
- Partitioning
- Communication
- Agglomeration
- Mapping

## 1) Partitioning
Với bước đầu tiên là **partitioning**, tư tưởng là chia nhỏ task lớn thành các task nhỏ, chia task nhỏ thành các task nhỏ hơn. Nhưng điều quan trọng nhất là chia như thế nào? Có bạn nào gặp hội chứng Trypophobia không nhỉ. Hội chứng sợ những cái **lỗ**. Nhìn hình dưới cũng hơi hãi :worried:.


Có 2 yếu tố cơ bản có thể dựa vào để phân chia thành các task nhỏ hơn:
> - **Domain/Data**: phân tách các task dựa trên data gắn với task đó.
> - **Function**: chia nhỏ task theo hướng chức năng.

Ví dụ, lần này bọn mình sẽ làm spaghetti. Cụ thể là 2 người làm 8 đĩa spaghetti.
> - Với **domain/data partitioning**, mình sẽ chia làm hai phần, mỗi người làm 4 đĩa spaghetti.
> - Với **function partitioning**, mình sẽ chia công đoạn thực hiện đĩa spaghetti thành nhiều bước: luộc mì, làm sốt... Mỗi người sẽ đảm nhiệm một vài task và thực hiện cho cả 8 đĩa.



Trong thực tế, chúng ta sẽ áp dụng cả 2 yếu tố trên để thực hiện **partitioning** một bài toán. Như vậy bước đầu tiên lý thuyết khá đơn giản, phần khó nhất vẫn là thực thành sao cho đúng với lý thuyết.

Một câu thần chú quen thuộc, dựa vào bài toán cụ thể, tình hình thực tế để thực thi sao cho đúng nhất, nếu chưa đúng ta bỏ đi hết làm lại từ đầu :worried:.

## 2) Communication
Bước tiếp theo cần quan tâm và xử lý đó là làm thế nào để các task (cụ thể là các thread thực thi task) giao tiếp với nhau, chia sẻ dữ liệu với nhau.

Mặc dù chúng ta cố gắng để chia thành các task thực thi độc lập, không phụ thuộc vào các task còn lại, tuy nhiên các bài toán thực tế không đơn giản như vậy.

### 2.1) Point-to-point communication

Giả sử mình mong muốn các đĩa spaghetti được trang trí nhiều kiểu và không đĩa nào giống đĩa nào. Như vậy mình phải biết thông tin của các đĩa đã hoàn thành, hay nói cách khác, cần sự giao tiếp giữa các task để yêu cầu được thực hiện chính xác.


Như vậy, mặc dù các task có thể thực thi đồng thời với nhau tuy nhiên **vẫn phụ thuộc ít nhiều** vào nhau. Trong tình huống này, tất cả các task đều cần communicate với nhau, được gọi là **point-to-point communication**.
- Một task sẽ đóng vai trò là **sender** hoặc **producer**
- Task còn lại đóng vai trò **receiver** hoặc **consumer**.


### 2.2) Collective communication
Ngoài ra, ta có thể dùng cơ chế khác để giao tiếp giữa các task thay cho **point-to-point communication**. Nếu một **task** muốn **share/collect** dữ liệu **to/from** nhiều **task** khác nhau, chúng ta sẽ sử dụng cơ chế **collective communication**.


Với **collective communication**, một **task** sẽ đóng vai trò giống như bộ quản lý trung tâm, phân tán và thu cập các data từ nhiều **task** khác nhau. Khi số lượng các task xung quanh tăng lên đồng nghĩ với việc **task** trung tâm phải làm việc nhiều hơn, rất có khả năng xảy ra **bottle neck**. Điều tương tự cũng có thể xảy ra với **point-to-point communication**.


### 2.3) Devide & Conquer

Có sử dụng chiến lược **devide and conquer**/**fork and join** để xử lý vấn đề giao tiếp và chia sẻ data. Mục tiêu của phương pháp này là chia từ một phần thành các phần nhỏ hơn, các phần nhỏ hơn tiếp tục chia nhỏ hơn nữa. Các **task** chỉ giao tiếp trực tiếp với **task** ở level trên và level dưới, giảm gánh nặng của **task** trung tâm.


### 2.4) Synchronous & Asynchronous
Ngoài các các trên để mô hình hóa sự giao tiếp giữa các task, một yếu tố nữa cần quan tâm đó là cách giao tiếp:
> **Synchronous**:
> - Giao tiếp đồng bộ. **Blocking communication**.
> - Một **task** sẽ chờ cho đến khi quá trình **communicate** thành công, nhận được response (nếu có) mới tiếp tục xử lý.
> - Do đó, không thể thực thi các nhiệm vụ khác trong quá trình chờ response.
>
> **Asynchronous**:
> - Giao tiếp bất đồng bộ. **Non-blocking communication**.
> Một **task** không cần chờ cho đến khi nhận được response.
> Nhờ vậy, nó có thể thực thi nhiệm vụ khác trong quá trình chờ response.

Ngoài ra, vài yếu tố khác cần quan tâm trong quá trình **communication**:
- **Overhead**: tài nguyên mà máy tính cần cho quá trình **communication**. Giao tiếp cũng tốn calories mà.
- **Latency**: thời gian một **message** gửi từ **A** đến **B**.
- **Bandwidth**: rất quen thuộc, băng thông. Dung lượng **message** tối đa có thể truyền tải trong một đơn vị thời gian (GiB/s). Nếu trong cùng thiết bị vật lý thì thông số này không quá quan trọng. Tuy nhiên nếu triển khai trên nhiều thiết bị vật lý và giao tiếp thông qua Internet, nó là một yếu tố cần được chú ý.

Còn 2 step nữa, mình sẽ giới thiệu trong bài sau:
- Agglomeration
- Mapping

### Reference
- https://hackmd.io/@datbv/r1uoC54Kd#Reference

© [Dat Bui](https://www.linkedin.com/in/datbv/)