Bỏ qua tới nội dung chính

Trước khi có tính toán song song

Tính toán song song: chia một việc lớn cho nhiều nhân và nhiều máy

Tính toán song song: định luật Gustafson, chia dữ liệu cho nhiều tiến trình, tranh chấp và phép gộp, cân bằng tải, chi phí giao tiếp — và nên học từ đâu.

Ban biên tập OpenER

Cập nhật 18/11/2026 · 20 phút đọc · CC BY 4.0

Chiều cuối năm, cả nhà ngồi gói bánh chưng. Một người rửa lá, một người đãi đỗ, ba người cùng gói: năm mươi chiếc bánh xong nhanh hơn hẳn một người làm. Nhưng ai từng gói cũng biết những chỗ vướng: hai người cùng với lấy chậu gạo, người gói nhanh ngồi chờ người buộc lạt chậm, và nồi bánh vẫn phải luộc suốt đêm — thêm bao nhiêu người cũng không làm nó sôi nhanh hơn.

Máy tính hôm nay gặp đúng những chuyện ấy. Chiếc laptop của bạn có thể có 8 nhân, nhưng một chương trình Python tính nặng viết theo cách thông thường chỉ dùng một: mở Task Manager sẽ thấy một nhân chạy hết sức, bảy nhân còn lại gần như ngồi chơi. Ở đầu kia, siêu máy tính Frontier ở Mỹ có hơn chín nghìn máy cùng giải một bài toán. Tính toán song song (parallel computing) là môn học cách chia một việc lớn cho nhiều nhân, nhiều máy sao cho nhanh hơn thật — và không ai giẫm chân ai.

Trước khi có tính toán song song

Suốt mấy chục năm, phần lớn chương trình được viết cho một bộ xử lý: muốn nhanh hơn thì chờ chip đời sau. Tới giữa thập niên 2000, cách đó hết tác dụng vì chip không tăng tần số được nữa — bài Kiến trúc máy tính kể chuyện bức tường công suất. Nhưng những bài toán lớn nhất chưa bao giờ chịu chờ. "Nhà máy dự báo" 64.000 người tính tay mà Lewis Fry Richardson mơ tới năm 1922, chuyện có trong bài Vật lý, thực chất là một máy song song làm bằng người.

Những cỗ máy song song bằng điện tử ra đời từng bước:

  1. Mảng bộ xử lý: ILLIAC IV. Thiết kế ở Đại học Illinois trong thập niên 1960, do hãng Burroughs chế tạo, chạy ở trung tâm NASA Ames từ giữa thập niên 1970: 64 bộ xử lý cùng làm một lệnh trên 64 mảnh dữ liệu khác nhau. Dự định có 256 bộ, chỉ làm được 64; chi phí đội từ khoảng 8 lên 31 triệu đô la. Máy chạy kém ổn định, nhưng chứng minh được ý tưởng một lệnh, nhiều dữ liệu (SIMD) — bài Kiến trúc máy tính đã giải thích — mà card đồ họa ngày nay vẫn dùng.
  2. Máy vector: Cray-1 (1976). Máy của Seymour Cray xử lý cả một dãy tới 64 số bằng một lệnh, cho các số chảy liên tục qua đường ống tính toán; đỉnh 160 triệu phép tính số thực mỗi giây. Chiếc đầu tiên về phòng thí nghiệm Los Alamos, với băng ghế bọc nệm quanh chân che bộ nguồn.
  3. Cụm máy thường: Beowulf (1994). Thomas Sterling và Donald Becker ở NASA Goddard nối 16 máy tính cá nhân dùng chip 486 bằng cáp Ethernet, chạy Linux. Thay vì mua một siêu máy tính đặt làm riêng, ghép nhiều máy bán đại trà thành cụm (cluster) — công thức mà phòng lab đại học, trung tâm dữ liệu và nhiều siêu máy tính dùng tới hôm nay.
  4. Một chuẩn chung để nhắn tin: MPI (1994). Trước đó mỗi hãng có một thư viện riêng để các máy gửi dữ liệu cho nhau; chương trình viết cho máy này phải viết lại cho máy kia. Diễn đàn MPI (MPI Forum), gồm các hãng, phòng thí nghiệm và trường đại học, công bố MPI (Message Passing Interface) 1.0 tháng 5/1994. Ba mươi năm sau, nó vẫn là chuẩn trên siêu máy tính.
  5. GPU cho người lập trình: CUDA (2007). Trước đó, muốn dùng card đồ họa để tính toán khoa học phải "đóng giả" phép tính thành phép vẽ. Đầu năm 2007, NVIDIA phát hành CUDA: viết chương trình gần giống C cho hàng nghìn nhân nhỏ của GPU. Vài năm sau, GPU thành cỗ máy chính của học sâu — bài Học máy kể tiếp.

Từ năm 1993, danh sách TOP500 xếp hạng 500 máy mạnh nhất thế giới hai lần mỗi năm, bằng bài đo LINPACK: giải một hệ phương trình tuyến tính rất lớn (gốc của bài đo có trong bài Tính toán khoa học). Danh sách công bố cuối tháng 5/2022 đưa Frontier, ở Phòng thí nghiệm quốc gia Oak Ridge, lên đầu với 1,102 exaflops — máy đầu tiên vượt mốc 10¹⁸ phép tính số thực mỗi giây trong bảng xếp hạng chính thức. Frontier gồm 9.408 nút, mỗi nút một CPU và bốn GPU.

Không có tính toán song song
Có tính toán song song
Muốn nhanh hơn
Chờ chip đời sau
Thêm nhân, thêm máy
Bài toán lớn hơn bộ nhớ một máy
Thu nhỏ bài toán, bỏ bớt chi tiết
Chia dữ liệu, mỗi máy giữ một phần
Dự báo thời tiết, mô phỏng
Lưới thô, ít phương án
Lưới mịn, nhiều phương án chạy cùng lúc
Huấn luyện một mô hình AI lớn
Một GPU phải chạy hàng nghìn năm
Vài tháng trên hơn mười nghìn GPU
Lỗi chương trình
Chạy lại là gặp lại
Có lỗi chỉ hiện "thỉnh thoảng", tùy thứ tự chạy

Ngày nay, chương trình Python bạn viết vẫn có thể "chưa có" song song. Trình thông dịch Python chuẩn có một khóa thông dịch toàn cục (global interpreter lock — GIL): mỗi lúc chỉ một luồng được chạy code Python. Thử đổi Pool thành ThreadPool (nhập từ multiprocessing.pool) trong chương trình ở ý 2 dưới đây: trên máy chạy thử, bốn luồng còn chậm hơn một luồng. Từ Python 3.13 đã có bản dựng bỏ GIL — thử nghiệm ở 3.13, được hỗ trợ chính thức từ 3.14 — nhưng tới lúc viết bài, bản mặc định mà hầu hết mọi người cài vẫn có GIL. Vì vậy các ví dụ dưới đây dùng tiến trình (process) thay cho luồng.

Môn này trả lời câu hỏi gì

Môn Tính toán song song trả lời câu hỏi: làm sao chia một việc lớn cho nhiều nhân, nhiều máy để xong nhanh hơn — hoặc làm được việc lớn hơn — mà kết quả vẫn đúng?

Câu hỏi đó tách thành mấy câu nhỏ: chia việc theo dữ liệu hay theo công đoạn; ai làm phần nào; khi nào phải chờ nhau và chờ thế nào; gửi cho nhau những gì, bao nhiêu; và đo thế nào để biết thêm máy có đáng không.

Môn này khác đồng thời (concurrency) mà bài Hệ điều hành dạy. Đồng thời là một đầu bếp xoay xở ba món cùng lúc, sao cho không món nào cháy; song song là ba đầu bếp cùng nấu một mâm cỗ, sao cho mâm cỗ xong sớm.

Vì sao cần học? Vì từ giữa thập niên 2000, gần như mọi con chip đều nhiều nhân, kể cả chip trong điện thoại, và tốc độ chủ yếu đến từ chỗ dùng được nhiều nhân.

Năm ý tưởng cốt lõi

1. Định luật Gustafson: máy lớn hơn để làm bài toán lớn hơn

Bài Kiến trúc máy tính và bài Cấu trúc tính toán đã nói về định luật Amdahl: phần không chia được quyết định trần tăng tốc, nên nếu 5% thời gian là phần tuần tự thì nghìn nhân cũng không nhanh quá 20 lần. Vậy người ta xây máy hàng triệu nhân để làm gì?

Năm 1988, John Gustafson ở phòng thí nghiệm Sandia (Mỹ) báo cáo rằng nhóm ông đạt mức tăng tốc 1016 tới 1021 lần trên một máy 1.024 bộ xử lý, với ba chương trình tính toán khoa học thật. Lời giải nằm ở một giả định ngầm của Amdahl: bài toán giữ nguyên cỡ. Ngoài đời hiếm ai làm vậy. Có máy mạnh hơn, người ta không giải bài cũ nhanh hơn, mà giải bài lớn hơn trong cùng thời gian: lưới mịn hơn, nhiều bước hơn, nhiều dữ liệu hơn. Phần chuẩn bị — đọc số liệu, ghi kết quả — gần như không đổi, còn phần chia được lớn lên theo số máy. Cách tính này — Gustafson ghi công cho đồng nghiệp E. Barsis — nay gọi là định luật Gustafson (Gustafson's law).

Ví dụ một bản dự báo thời tiết phải chạy xong trong một giờ để kịp bản tin: 3 phút đọc và ghi số liệu — đúng 5% như trên — và 57 phút tính trên lưới ô. Mỗi khi thêm máy, ta chia lưới mịn hơn sao cho mỗi máy vẫn giữ một phần cỡ như cũ:

python
noi_tiep, song_song = 3, 57      # phút, đo trên hệ song song: 3 phút đọc–ghi số liệu, 57 phút tính

for may in (1, 10, 100, 1000):
    mot_may = noi_tiep + song_song * may    # nếu chỉ một máy làm hết khối việc đó thì mất bao lâu
    print(f"{may:5} máy: khối việc của {mot_may / 60:6.1f} giờ-máy, xong trong 1 giờ")
    1 máy: khối việc của    1.0 giờ-máy, xong trong 1 giờ
   10 máy: khối việc của    9.6 giờ-máy, xong trong 1 giờ
  100 máy: khối việc của   95.0 giờ-máy, xong trong 1 giờ
 1000 máy: khối việc của  950.0 giờ-máy, xong trong 1 giờ

Với nghìn máy, trong một giờ ta làm xong khối việc mà một máy cần gần 950 giờ. Amdahl và Gustafson không mâu thuẫn; họ trả lời hai câu hỏi khác nhau. Amdahl hỏi: cùng bài toán, nhanh hơn được bao nhiêu? Gustafson hỏi: cùng thời gian, làm được bài toán lớn tới đâu? Nhưng Gustafson chỉ đúng khi phần chia được thật sự lớn theo dữ liệu, và khi chi phí trao đổi giữa các máy không lớn nhanh hơn — chuyện của ý 5.

2. Chia việc: song song dữ liệu

Có hai cách chia việc chính. Song song dữ liệu (data parallelism): mọi người làm cùng một việc trên các phần dữ liệu khác nhau — năm người, mỗi người gói một phần số bánh. Song song tác vụ (task parallelism): mỗi người một công đoạn — người rửa lá, người đãi đỗ, người gói. Phần lớn chương trình song song lớn là song song dữ liệu, vì dữ liệu càng nhiều thì càng nhiều việc để chia.

Thử với một việc nặng: đếm các số nguyên tố dưới một triệu bằng cách thử chia. Ta cắt khoảng số thành 200 đoạn, giao cho một nhóm tiến trình; tiến trình nào xong đoạn này thì nhận đoạn tiếp theo:

python
import math, os, time
from multiprocessing import Pool

def dem_nguyen_to(doan):                    # đếm số nguyên tố trong [a, b) bằng cách thử chia
    a, b = doan
    return sum(1 for n in range(max(a, 2), b)
               if all(n % d for d in range(2, math.isqrt(n) + 1)))

if __name__ == "__main__":                  # cần có trên Windows và macOS
    cac_doan = [(a, a + 5_000) for a in range(0, 1_000_000, 5_000)]   # 200 đoạn nhỏ
    print("Số nhân logic:", os.cpu_count())
    for so_tien_trinh in (1, 2, 4, 8):
        with Pool(so_tien_trinh) as pool:
            t = time.perf_counter()
            tong = sum(pool.map(dem_nguyen_to, cac_doan, chunksize=1))   # mỗi lần giao một đoạn
            print(f"{so_tien_trinh} tiến trình: {time.perf_counter() - t:5.2f} giây, {tong} số nguyên tố")

Lần nào cũng ra 78.498 số nguyên tố. Còn thời gian thì mỗi lần đo một khác; trên máy chạy thử, một laptop có 4 nhân thật mà hệ điều hành báo 8 nhân logic, một tiến trình mất khoảng 9 giây, hai tiến trình 5–6 giây, bốn tiến trình khoảng 3,5 giây, tám tiến trình khoảng 3 giây. Nhanh gấp chừng hai lần rưỡi tới ba lần — không phải tám. Vì sao?

  • 8 nhân logic thật ra là 4 nhân, mỗi nhân chạy hai luồng nhờ siêu phân luồng (hyper-threading). Hai luồng chung một nhân thì chia nhau các khối tính toán của nhân đó.
  • Khi nhiều nhân cùng chạy, chip tự hạ tần số để không vượt giới hạn điện và nhiệt — chuyện của bài Vật lý. Một nhân chạy một mình được đẩy tần số lên cao, bốn nhân cùng chạy thì mỗi nhân chậm đi.
  • Máy còn chạy những chương trình khác, và khởi động tiến trình, gửi việc, nhận kết quả đều tốn thời gian.

Bài học đầu tiên của môn này: "N nhân nhanh gấp N lần" chỉ có trên giấy. Con số trên máy bạn sẽ khác — hãy chạy và đo. Bài toán đếm số nguyên tố còn thuộc loại dễ nhất: các đoạn không cần biết gì về nhau, gọi là song song hiển nhiên (embarrassingly parallel). Ba ý tiếp theo nói về lúc các phần phải dính dáng tới nhau.

3. Đồng bộ: khi mọi người cùng ghi vào một bảng

Bài Hệ điều hành đã giải thích điều kiện tranh chấp (race condition): hai luồng cùng tăng một biến đếm thì có lần cộng bị mất. Môn song song hỏi thêm một câu: sửa cho đúng rồi, có còn nhanh không?

Thử lập phổ điểm cho một triệu bài thi, điểm từ 0 đến 10: một bảng 11 ô, mỗi bài thi cộng 1 vào ô của điểm mình. Bốn tiến trình chia nhau một triệu bài, theo ba cách:

python
import random, time
from multiprocessing import Array, Lock, Process

def cham(cach, pho_diem, khoa, phan, so_bai=250_000):
    rng = random.Random(phan)                 # mỗi tiến trình tự sinh 250.000 điểm của phần mình
    diem = [rng.randint(0, 10) for _ in range(so_bai)]
    if cach == "chung, không khóa":
        for d in diem:
            pho_diem[d] += 1                  # đọc – cộng – ghi: có thể bị chen ngang
    elif cach == "chung, có khóa":
        for d in diem:
            with khoa:                        # mỗi lần cộng phải xin khóa
                pho_diem[d] += 1
    else:                                     # "riêng rồi gộp"
        rieng = [0] * 11
        for d in diem:
            rieng[d] += 1                     # bảng riêng, không ai tranh
        with khoa:                            # chỉ xin khóa một lần, lúc gộp
            for i in range(11):
                pho_diem[i] += rieng[i]

if __name__ == "__main__":
    for cach in ("chung, không khóa", "chung, có khóa", "riêng rồi gộp"):
        pho_diem, khoa = Array("i", 11, lock=False), Lock()   # bảng 11 ô: điểm 0 tới 10
        t = time.perf_counter()
        nhom = [Process(target=cham, args=(cach, pho_diem, khoa, k)) for k in range(4)]
        for p in nhom: p.start()
        for p in nhom: p.join()
        print(f"{cach:18} {sum(pho_diem):>9,} bài  {time.perf_counter() - t:5.2f} giây")

Một lần chạy trên máy thử:

chung, không khóa    914,219 bài   0.93 giây
chung, có khóa     1,000,000 bài  12.96 giây
riêng rồi gộp      1,000,000 bài   0.54 giây

Cách thứ nhất nhanh nhưng sai: mất hàng chục nghìn bài, mỗi lần chạy mất một con số khác. Cách thứ hai đúng nhưng chậm hơn cách thứ ba khoảng hai mươi lần: mỗi lần cộng phải xin rồi trả một cái khóa chung, nên bốn người làm song song biến thành bốn người xếp hàng trước một cuốn sổ. Cách thứ ba vừa đúng vừa nhanh, vì nó tránh dùng chung: mỗi tiến trình đếm vào bảng riêng, cuối cùng mới cộng mười một con số vào bảng chung. Giống mỗi hội đồng chấm thi tự lập phổ điểm của mình rồi gửi về để cộng lại, thay vì một triệu lần chen nhau ghi vào một cuốn sổ.

Kiểu "mỗi người một phần riêng, cuối cùng gộp lại" gọi là phép gộp (reduction), và nó có sẵn trong mọi công cụ song song: mệnh đề reduction của OpenMP, hàm MPI_Reduce của MPI, các hàm gộp trên GPU. Khóa vẫn cần, nhưng người làm song song giỏi thiết kế sao cho phải dùng nó càng ít càng tốt.

4. Cân bằng tải: cả đội chờ người về chót

Sau bữa cỗ ngày giỗ, bốn người chia nhau rửa một chậu bát đĩa: 36 chồng bát, mỗi chồng mất một phút, và 4 cái nồi to, mỗi cái chín phút, nằm dưới đáy chậu. Cách thứ nhất: chia sẵn, mỗi người nhận mười món theo thứ tự trong chậu. Cách thứ hai: để chung một chồng, ai rửa xong thì lấy món tiếp theo.

python
import heapq

def xong_luc(viec, so_nguoi, chia_truoc):
    if chia_truoc:                          # chia sẵn: mỗi người một phần liền nhau, số món bằng nhau
        phan = len(viec) // so_nguoi
        return max(sum(viec[i * phan:(i + 1) * phan]) for i in range(so_nguoi))
    ranh_luc = [0] * so_nguoi               # chồng chung: ai rảnh trước thì lấy món tiếp theo
    for v in viec:
        heapq.heapreplace(ranh_luc, ranh_luc[0] + v)
    return max(ranh_luc)

chau = [1] * 36 + [9] * 4                   # 36 chồng bát (1 phút), 4 cái nồi to (9 phút) ở cuối chậu
print("Chia sẵn:   ", xong_luc(chau, 4, True), "phút")
print("Chồng chung:", xong_luc(chau, 4, False), "phút")

chau2 = [1] * 36 + [30]                     # lần này có một nồi luộc gà 30 phút
print("Một nồi 30 phút:", xong_luc(chau2, 4, False), "phút;",
      "rửa nồi trước:", xong_luc(sorted(chau2, reverse=True), 4, False), "phút")
Chia sẵn:    42 phút
Chồng chung: 18 phút
Một nồi 30 phút: 39 phút; rửa nồi trước: 30 phút

Chia sẵn "công bằng" theo số món, nhưng người cuối nhận cả bốn cái nồi: ba người kia xong sau mười phút rồi đứng chờ, cả nhà phải đợi tới phút 42. Chồng chung xong sau 18 phút — đúng bằng tổng công chia bốn. Đó là cân bằng tải (load balancing), và kẻ kéo cả đội lại gọi là người về chót (straggler). Lần rửa thứ hai cho thấy giới hạn: có một cái nồi 30 phút, để nó cuối chậu thì mất 39 phút, rửa nó trước thì còn 30 — nhưng xếp khéo đến mấy cũng không xong trước 30 phút. Ngoài đời không cắt đôi được cái nồi, nhưng trong phần mềm thường cắt được — vì vậy chương trình ở ý 2 chia việc thành 200 đoạn nhỏ, chứ không phải 4 đoạn lớn.

Ở đó, chia sẵn thành 4 đoạn lớn sẽ lệch: số càng lớn càng phải thử chia nhiều lần hơn, nên đoạn cuối phải làm gấp khoảng 2,3 lần số phép chia của đoạn đầu; trên máy chạy thử, đoạn đầu xong sau khoảng 1,4 giây, đoạn cuối mất khoảng 2,8 giây. Các thư viện song song có sẵn cách chia động: schedule(dynamic) của OpenMP, hay cơ chế trộm việc (work stealing), nơi nhân hết việc sang lấy bớt việc của nhân khác. Ở quy mô nghìn máy, người về chót có thể là một máy có ổ đĩa sắp hỏng; MapReduce xử lý bằng cách, lúc việc gần xong, giao bản sao những phần còn dở cho máy khác, bản nào xong trước thì lấy — bài Hệ phân tán kể tiếp MapReduce chịu lỗi thế nào.

5. Chi phí giao tiếp: chuyển dữ liệu đắt hơn tính

Đếm số nguyên tố chia song song rất lợi, vì mỗi đoạn chỉ cần gửi đi hai con số và nhận về một, trong khi phải tính tới vài trăm nghìn phép chia. Giờ thử điều ngược lại: cộng mười triệu số, một việc rất nhẹ, nhưng phải gửi cả dữ liệu cho các tiến trình:

python
import time
from multiprocessing import Pool

if __name__ == "__main__":
    so = [i % 100 for i in range(10_000_000)]              # mười triệu số nhỏ
    khoi = [so[i:i + 2_500_000] for i in range(0, len(so), 2_500_000)]

    t = time.perf_counter()
    tong = sum(so)
    print(f"Một tiến trình tự cộng:   {time.perf_counter() - t:.2f} giây")

    with Pool(4) as pool:                                   # khởi động sẵn, không tính giờ
        t = time.perf_counter()
        tong4 = sum(pool.map(sum, khoi))                    # gửi bốn khối số sang bốn tiến trình
        print(f"Bốn tiến trình cùng cộng: {time.perf_counter() - t:.2f} giây")
    print(tong == tong4)

Trên máy chạy thử, một tiến trình cộng xong trong chưa tới 0,1 giây; bốn tiến trình mất khoảng 0,6 tới 0,9 giây — chậm hơn chừng mười lần, dù kết quả giống hệt. Phần lớn thời gian dành cho việc đóng gói dữ liệu, gửi qua lại giữa các tiến trình và mở gói ra. Song song chỉ lợi khi lượng tính trên mỗi byte phải chuyển đủ lớn.

Phần cứng cũng vậy. Theo Mark Horowitz (Stanford, 2014), một lần đọc bộ nhớ chính tốn khoảng 1–2 nanojoule, gấp hàng trăm lần năng lượng của một phép tính. Giữa hai máy trong một cụm, một thông điệp qua mạng tốc độ cao mất cỡ một micro giây — đủ để một nhân 3 GHz đi qua 3.000 nhịp đồng hồ. Vì thế người viết chương trình song song luôn tính kỹ dữ liệu nằm ở đâu.

Có một tin tốt, nối lại với Gustafson. Khi chia một lưới mô phỏng cho nhiều máy, mỗi máy giữ một ô vuông k × k và phải tính k² điểm, nhưng mỗi bước chỉ cần trao đổi khoảng 4k điểm ở viền với các máy bên cạnh. Tỷ lệ trao đổi trên tính là 4/k: với k = 100 là 4%, với k = 1.000 chỉ còn 0,4%. Phần việc mỗi máy càng lớn, giao tiếp càng rẻ so với tính — lý do bài toán lớn song song tốt hơn bài toán nhỏ.

Tính toán song song nằm ở đâu trong chồng tầng

Trong chồng tầng của bài Từ electron đến ứng dụng, tính toán song song không nằm gọn ở một tầng mà xuyên qua nhiều tầng: từ tầng 3 (nhiều nhân, GPU, bộ nhớ đệm dùng chung), qua tầng 5 (hệ điều hành chia tiến trình và luồng lên các nhân), tầng 6 (thư viện như OpenMP, MPI, CUDA, multiprocessing), tới tầng 7 (thuật toán song song: sắp xếp, nhân ma trận, duyệt đồ thị trên nhiều bộ xử lý).

Đưa lên

Một cách nói "chia việc này cho N bên" — tiến trình, luồng, thông điệp, phép gộp — để bài toán lớn xong trong thời gian chấp nhận được, hoặc lớn hơn trong cùng thời gian.

Giấu đi

Phần nào chạy trên nhân nào, máy nào, vào lúc nào. Nhưng như bốn ý cuối cho thấy, hiệu năng phụ thuộc đúng những thứ bị giấu: dữ liệu nằm ở đâu, ai phải chờ ai.

Học trước và học sau

· 6 môn

Hệ điều hành

Operating Systems

Tiến trình, luồng, khóa, bế tắc — công cụ mà chương trình song song dùng hằng ngày. Nên học trước.

Xem chủ đề trên OpenER: Operating Systems

Kiến trúc máy tính

Computer Architecture and Engineering

Bộ nhớ đệm, nhiều nhân, SIMD, GPU và định luật Amdahl: phần cứng mà mọi con số tăng tốc phụ thuộc vào. Nên học trước hoặc song song.

Xem chủ đề trên OpenER: Computer Architecture and Engineering

Cấu trúc dữ liệu và giải thuật

Data Structures and Algorithms

Phải biết phiên bản tuần tự tốt nhất trước khi chia nó ra; nhiều thuật toán song song là thuật toán quen thuộc được cắt lại.

Xem chủ đề trên OpenER: Data Structures and Algorithms

Hệ phân tán

Distributed Systems

Khi các máy ở xa nhau, mạng chập chờn và máy có thể hỏng giữa chừng: MapReduce, sao chép dữ liệu, đồng thuận. Học sau.

Xem chủ đề trên OpenER: Distributed Systems

Tính toán khoa học

Scientific Computing

Những mô phỏng chạy trên siêu máy tính: phương pháp số, lưới, sai số. Hai môn bổ sung cho nhau.

Xem chủ đề trên OpenER: Scientific Computing

Học sâu

Deep Learning

Huấn luyện mô hình lớn là song song dữ liệu và song song mô hình trên hàng nghìn GPU, với phép gộp gradient sau mỗi bước.

Xem chủ đề trên OpenER: Deep Learning

Ứng dụng thật và nghề nghiệp

  • Tính toán hiệu năng cao (HPC): dự báo thời tiết, khí hậu, mô phỏng vật liệu, dược phẩm, động đất trên siêu máy tính, viết bằng MPI và OpenMP.
  • Lập trình GPU: viết và tối ưu các nhân tính toán (kernel) bằng CUDA hay các công cụ tương tự, cho AI, xử lý ảnh, mô phỏng.
  • Hạ tầng AI: chia việc huấn luyện và chạy mô hình lớn ra nhiều GPU, nhiều máy; đây là nơi cân bằng tải và chi phí giao tiếp quyết định thời gian và tiền bạc.
  • Dữ liệu lớn: các hệ như Spark chia một truy vấn trên hàng tỷ dòng cho cả cụm máy.
  • Game và phần mềm hiệu năng cao: chia việc vật lý, âm thanh, dựng hình cho mọi nhân của máy chơi game; cơ sở dữ liệu chạy một truy vấn trên nhiều nhân.

Học xong làm được gì, bắt đầu từ đâu

Sau môn này bạn có thể:

  • ước lượng một chương trình đáng song song hóa tới đâu, bằng cả Amdahl lẫn Gustafson, và đo tăng tốc thật trên máy mình;
  • chia một bài toán theo dữ liệu, chọn cỡ phần việc vừa đủ lớn để giao tiếp không nuốt hết lợi ích;
  • nhận ra tranh chấp dữ liệu, sửa bằng khóa, rồi tốt hơn nữa là thiết kế lại bằng phần riêng và phép gộp;
  • dùng chia việc động để không ai phải chờ người về chót;
  • viết chương trình với OpenMP trên một máy nhiều nhân, MPI trên nhiều máy, và đọc được một chương trình CUDA.

Nên biết trước: chủ đề Operating Systems (tiến trình, luồng, khóa) và Data Structures and Algorithms; lập trình C ở mức đọc được con trỏ, vì phần lớn công cụ song song chuẩn dùng C hoặc C++. Python đủ để học khái niệm như các ví dụ ở trên, nhưng nên làm ít nhất vài bài bằng C để thấy tốc độ thật.

Bắt đầu trên OpenER: trang chủ đề Parallel Computing có các khóa học đã chọn lọc, và hướng dẫn học đi qua sáu bước, từ giới hạn của song song hóa, đa luồng, OpenMP, MPI, thiết kế thuật toán song song tới các kỹ thuật đồng bộ không khóa. Khóa chính là CMU 15-418/618 Parallel Computer Architecture and Programming: cân bằng phần cứng và phần mềm, bài tập chạy trên CPU nhiều nhân và GPU thật. Stanford CS149 đi cùng mạch, thêm phần bộ tăng tốc và Spark; một khóa video của NPTEL thiên về OpenMP và MPI hợp với ai chưa có GPU. Khi đã vững, MIT 6.172 Performance Engineering of Software Systems đặt song song vào bức tranh tối ưu hiệu năng toàn diện. Lời khuyên cho môn này: mỗi lần thêm nhân, hãy đo lại. Con số không tăng như mong đợi chính là chỗ môn học bắt đầu.

Tài liệu tham khảo

  • Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar — Introduction to Parallel Computing, bản thứ hai (2003): giáo trình chính của hướng dẫn chủ đề.
  • Paul E. McKenney — Is Parallel Programming Hard, And, If So, What Can You Do About It?: sách mở của một kỹ sư nhân Linux, về khóa và đồng bộ.
  • Wen-mei W. Hwu, David B. Kirk, Izzat El Hajj — Programming Massively Parallel Processors: A Hands-on Approach: lập trình GPU với CUDA.
  • Carnegie Mellon University 15-418/618 Parallel Computer Architecture and Programming — trang khóa học.
  • Stanford CS149 Parallel Computing — trang khóa học.
  • MIT 6.172 Performance Engineering of Software Systems — MIT OpenCourseWare.
  • John L. Gustafson — "Reevaluating Amdahl's Law", Communications of the ACM, tập 31, số 5, 1988.
  • Mark Horowitz — "Computing's Energy Problem (and what we can do about it)", ISSCC 2014.
  • MPI Forum — đặc tả MPI tại mpi-forum.org; OpenMP Architecture Review Board — đặc tả OpenMP tại openmp.org.
  • Tài liệu Python — mô-đun multiprocessing.

Ban biên tập OpenER, “Tính toán song song: chia một việc lớn cho nhiều nhân và nhiều máy”, OpenER, 2026. Phát hành theo CC BY 4.0: được chia sẻ, chỉnh sửa, kể cả thương mại, miễn ghi công tác giả và dẫn link bài gốc.