kiến thức [Event Tặng Title] Concurrency/multi-threading in the nut shell

bribnt đã nói:

Tăng số lượng thread khi quá số thread của CPU thì không làm tăng số instruction được fetch, nhưng có tác dụng tận dung thời gian rỗi của CPU nếu ứng dụng là I/O bound.
Vì cơ chế của OS là khi gặp I/O thì context-switch sang thread khác, và chỉ dựng dậy khi đã có kết quả.
Tăng quá nhiều thread thì có cái hại là overhead của OS (bao gồm context switch, scheduling, chiếm tài nguyên) có thể lớn hơn lợi ích thu được. Vậy nên người ta mới nghĩ ra coroutine.

Nhưng với ứng dụng CPU bound thì không có tác dụng mà chỉ toàn hại.



Atomic được cài đặt bằng Fence, không liên quan đến SIMD.




Slide này cũng cũ rồi.
CPU ngày nay (khoảng 20 năm nay) ngoài pipeline thì họ sử dụng thêm một kỹ thuật khác gọi là Out-of-order execution (OOO). Tức là các instruction không chỉ bị chia thành nhiều pipeline stage khác nhau, mà việc thực thi các stage còn không theo thứ tự. CPU sẽ tự sắp xếp các các micro-ops (do 1 instruction chia nhỏ thành ở stage decode) rồi lập lịch để thực thi các stage tiếp theo, miễn là đảm bảo không bị conflict về dữ liệu. Thuật toán họ sử dụng để lập lịch là Tomasulo.

Chính vì OOO cho nên cùng một lúc CPU có thể thực thi được nhiều instruction (không conflict nhau). Nhưng nó không phải theo kiểu là số stage == số instruction tối đa. Mà là trong những stage cuối cùng của pipeline sẽ là bước chính thức thực thi micro-ops, việc này được thực hiện bởi các Execution Unit (EU). Số micro-ops tối đa mà CPU thực thi được trong một thời điểm == số ops được Retire (đã tính toán xong kết quả) ~ số EU.

VD đây là kiến trúc Zen 3. Có thể thấy 1 core CPU có đến hơn 14 EU.

Trong thực tế thì có nhiều lý do nên không thể nào sử dụng hết cùng lúc 14 EU đó được. Một trong số đó là do phụ thuộc về mặt dữ liệu giữa các instruction, một cách để cải thiện là simultaneous multithreading (SMT), phía Intel gọi là Hyper threading (HT), nhờ đó mà có thể cùng lúc có 2, 4, hoặc 8 luồng thực thi, vì các instruction thuộc các luồng khác nhau nên chắc chắn không phụ thuộc nhau về mặt dữ liệu (*), nên hiệu suất sử dụng các EU tăng cao hơn.

(*):dữ liệu đang nói đến ở đây là dữ liệu trên thanh ghi, còn trong memory thì CPU không có cách nào detect được dependency, coder phải dùng một cơ chế gọi là Fence để chỉ thị cho cpu biết thứ tự thực hiện các instruction nên như nào, tránh reorder lung tung.

Nhấp để mở rộng...

sirhung1993 đã nói:

Tại sao lại có gía trị bị trùng lặp ở đây?
trong khi cả 2 callback để increment lần lượt là 1 vs 2.
Lý do là việc access memory như cách trên ở môi trường multi-thread sẽ gây ra race-condition ->

• 1 thread fetch gía trị chưa được update ( dirty-cache)
• increment trên cái gía trị cũ, rồi write-back ( đứa ghi sau, đè lên đứa trước )

Nhấp để mở rộng...

thuyduong2007 đã nói:

Vấn đề là 5 instruction này nó không nằm trong 5 thread khác nhau, cùng lắm thì chỉ là 2 nếu cpu là hyper threading. Vì nếu 5 instruction của 5 thread khác nhau cùng được load vào các stage khác nhau trong pipeline thì cần 5 program counter để có thể giữ được vị trí câu lệnh hiện tại của 5 thread. Nên kết luận số stage trong pipeline càng lớn thì càng lằm tăng khả năng concurrency là đang hiểu sai pipeline.

Nhấp để mở rộng...

tien_manh_a2 đã nói:

arr[0]=arr[0]++; đâu có increase đâu bác
Mình sửa thành arr[0]=arr[0]+1; thì không thấy bị trùng lặp gì

Nhấp để mở rộng...

tien_manh_a2 đã nói:

arr[0]=arr[0]++; đâu có increase đâu bác
Mình sửa thành arr[0]=arr[0]+1; thì không thấy bị trùng lặp gì

Nhấp để mở rộng...

const worker = require('worker_threads');
let arr = [0];

setInterval(() => {
  arr[0]=arr[0]+1;
  console.log(`Worker.isMainThread: ${worker.isMainThread} T1: ${worker.threadId} : ${arr[0]} `);
}, 0);

setInterval(() => {
  arr[0]=arr[0]+2
  //console.log("T2: " + arr[0]);
  console.log(`Worker.isMainThread: ${worker.isMainThread} T2: ${worker.threadId} : ${arr[0]} `);
}, 0);

sirhung1993 đã nói:

Thế ví dụ là của 2 threads thôi đi, gỉa sử tại thời điểm T nào đó, đang có 5 instructions đã fetch vào, thì PC store state của nó ở đâu nhỉ ? Vì cũng phải lưu 5 cái, theo như luận điểm của bạn?

Nhấp để mở rộng...

thuyduong2007 đã nói:

Có 2 thread mà phải lưu 5 cái gì vậy bạn???
2 thread chạy đồng thời thì chỉ cần 2 program counter thôi.

Nhấp để mở rộng...

sirhung1993 đã nói:

Ví dụ là 5 instruction của 2 thread, theo như slide của bác Fire Of Heart kia gửi, thì sẽ có 1 thời điểm nó có 5 instruction đang được xử lý trong pipe-line.

Thì như luận điểm cần lưu state của bác, thì nó lưu như thế nào ? Chứ nếu 5 state bị bound bởi số thread, thì việc tăng stage lên có ý nghĩa gì ?

Nhấp để mở rộng...

sirhung1993 đã nói:

JavaScript:

const worker = require('worker_threads');
let arr = [0];

setInterval(() => {
  arr[0]=arr[0]+1;
  console.log(`Worker.isMainThread: ${worker.isMainThread} T1: ${worker.threadId} : ${arr[0]} `);
}, 0);

setInterval(() => {
  arr[0]=arr[0]+2
  //console.log("T2: " + arr[0]);
  console.log(`Worker.isMainThread: ${worker.isMainThread} T2: ${worker.threadId} : ${arr[0]} `);
}, 0);

Nó vẫn chạy trên main_thread.
Hàm setInterval() ko đẩy callback vào worker

Nhấp để mở rộng...

sirhung1993 đã nói:

Ví dụ là 5 instruction của 2 thread, theo như slide của bác Fire Of Heart kia gửi, thì sẽ có 1 thời điểm nó có 5 instruction đang được xử lý trong pipe-line.

Thì như luận điểm cần lưu state của bác, thì nó lưu như thế nào ? Chứ nếu 5 state bị bound bởi số thread, thì việc tăng stage lên có ý nghĩa gì ?

Nhấp để mở rộng...

thuyduong2007 đã nói:

Nó chỉ lưu stage của thread đang được chạy thôi, trường hợp bt là có 1 program counter thì chỉ có 1 thread được chạy, 5 instruction đó là của 1 cùng 1 thread, bởi vậy nó mới nảy sinh chuyện data dependency và branch predicting để tăng được throughput của pipeline lên. Chứ k phải 5 stage nó load 5 câu lệnh của 5 thread khác nhau đâu.

Nhấp để mở rộng...

mov eax, 1
mov ebx, eax
add ebx, 2
...
// làm gì đó với eax, ebx

mov eax, 5
mov ecx, 10
add ecx, eax
...
// làm gì đó với eax, ecx

thuyduong2007 đã nói:

Nó chỉ lưu stage của thread đang được chạy thôi, trường hợp bt là có 1 program counter thì chỉ có 1 thread được chạy, 5 instruction đó là của 1 cùng 1 thread, bởi vậy nó mới nảy sinh chuyện data dependency và branch predicting để tăng được throughput của pipeline lên. Chứ k phải 5 stage nó load 5 câu lệnh của 5 thread khác nhau đâu.

Nhấp để mở rộng...

Nó chỉ lưu stage của thread đang được chạy thôi, trường hợp bt là có 1 program counter thì chỉ có 1 thread được chạy, 5 instruction đó là của 1 cùng 1 thread

Nhấp để mở rộng...

bribnt đã nói:

Các stage trung gian trong pipeline của 1 instruction hoàn toàn có thể có trạng thái riêng của nó.
Tùy vào loại stage mà có các lưu trạng thái khác nhau.

Một trong số đó là Register File, bao gồm khoảng vài trăm thanh ghi. Những thanh ghi này dev không access được mà nó chỉ lưu giá trị tạm của các phép tính. Dev chỉ access được khoảng vài chục thanh ghi do tập lệnh quy định mà thôi.

Lấy ví dụ một đoạn lệnh như sau

Mã:

mov eax, 1
mov ebx, eax
add ebx, 2
...
// làm gì đó với eax, ebx

mov eax, 5
mov ecx, 10
add ecx, eax
...
// làm gì đó với eax, ecx

Ta thấy hai nửa tuy có cùng dùng chung thanh ghi eax nhưng nhìn kỹ thì eax ở đoạn sau không phụ thuộc gì eax ở đoạn trước vì nó đã gán eax = 5 rồi.
CPU sẽ tự nhận biết điều này và có thể cắt đứt liên hệ giữa hai đoạn bằng cách rename eax ở nửa đầu thành một thanh ghi eax_temp nào đó, eax_temp sẽ được đặt trong register file.
Nhờ vậy mà trong cùng một thời điểm, đoạn mã ở hai nửa có thể cùng lúc thực thi, có thể cùng hoặc khác stage, không cần quan tâm đến nhau.

Nhấp để mở rộng...

sirhung1993 đã nói:

Mình bổ sung 1 idea là, scope của bác @thuyduong2007 là lúc hardware-thread hoặc core .

Còn phần concurrency mình đang nói là scope của OS-thread, tức là giai đoạn quyết định instruction nào được fecth vào PC trước. Tức là nhiều OS-threads có thể cùng share cùng 1 hardware-core/thread.

Code của application xin tăng OS-thread, để tăng tỉ lệ instruction được fetch vào hoặc fetch vào concurrency mà ko cần đợi mainthread gửi vào one-by-one.

Nhấp để mở rộng...

Kurt Godel đã nói:

physical core: 1 core xử lý 1 calculation/1 thời điểm. Cái này là cố định.
Tuy nhiên các nhà sx chip đưa ra kỹ thuật Hyperthreading hay Intel họ còn gọi là Simultaneous Multithreading (SMT). Kỹ thuật này chuyển 1 physical core có thể hiện diện như 2 core ảo (logical core).

hyperthreading lại là kỹ thuật tận dụng triệt để khoảng thời gian rảnh rỗi physical core CPU, giúp tăng đối đa throughput của CPU.

Nhấp để mở rộng...

thuyduong2007 đã nói:

Chính xác rồi bạn. Với hyper threading thì mặc dù chỉ có 1 core vật lý nhưng OS vẫn hiểu đó là 2 core.

Nhấp để mở rộng...

Kurt Godel đã nói:

mà mỗi calculation mất khoảng 1 nanosecond xử lý => Dù OS thread là 100 thread thì đấy là cách mà hệ điều hành lập lịch. Còn lại thực tế physical core vẫn xử lý 1 calculation/1 thời điểm mà thôi.

Nhấp để mở rộng...

bribnt đã nói:

Sai.
Trong 1 thời điểm CPU có thể xử lý nhiều hơn 1 calculation, và cũng có thể nhiều hơn số thread SMT.

Nhấp để mở rộng...

Kurt Godel đã nói:

Mình chưa thể chứng minh được 0.000000001 seconds nó có tồn tại hay không tồn tại. Nên mình xem như bạn nói đúng mình nói sai ở thời điểm này.

Nhấp để mở rộng...

bribnt đã nói:

Cứ dựa vào lý thuyết với đo đạc mà tính thôi.
Bạn cứ thử dùng một tool như GNU Perf rồi đo IPC một ứng dụng CPU bound nào đó, ví dụ như mprime95. Thì khả năng cho ra IPC > 2, tức là trong 1 clock (khoảng 1/4 nano giây), CPU thực hiện được nhiều hơn 2 lệnh.

Nhấp để mở rộng...