proto.lib

Parallel Merge Sort: chia để trị và cái bẫy ở bước merge

Sắp xếp song song thường chia mảng cho các luồng sắp xếp độc lập, nhưng bước merge tuần tự sau đó lại là nút cổ chai; giải pháp là song song hoá cả merge bằng cách binary-search điểm chia để mỗi luồng chỉ merge một đoạn kết quả độc lập.

ConcurrencyNâng cao2026-08-25
Parallel Merge Sort: chia để trị và cái bẫy ở bước merge

Tags

#merge-sort#parallel-sort#divide-and-conquer#binary-search#task-parallelism#amdahls-law

Tài liệu tham khảo

Mở rộng

Animation gốc là một file HTML tự chứa, có thể nhúng lại ở bất kỳ trang nào khác. Mở file gốc

Liên quan

ConcurrencyCơ bản

Amdahl's Law - Giới hạn tăng tốc song song

Phần code tuần tự không thể song song hóa sẽ giới hạn tốc độ tối đa dù thêm bao nhiêu core.

#amdahls-law#speedup#parallelism#scalability
ConcurrencyTrung bình

Fork-Join Parallelism

Đệ quy chia nhỏ một tác vụ thành các tác vụ con, chạy song song rồi hợp nhất kết quả để tăng tốc xử lý.

#fork-join#divide-and-conquer#parallelism#recursion
ConcurrencyTrung bình

Writer Starvation trong RWLock: writer chờ vô hạn

Một readers-writer lock ưu tiên reader (reader-preferring) cho phép luồng đọc mới liên tục chen vào miễn còn ít nhất một reader đang giữ khoá, khiến writer chờ vô hạn; chính sách write-preferring hoặc phase-fair chặn reader mới khi có writer đang đợi để writer được vào sau khi các reader hiện tại kết thúc.

#rwlock#writer-starvation#fairness#phase-fair