Xử lý song song là gì

Xử lí song song từ xa xưa cho đến gần đây là lãnh vực cao cấp hầu như chỉ dành cho các nhà khoa học. Có ít nhất 2 nguyên nhân:

• Xử lí song song đòi hỏi siêu máy tính đắt tiền, chỉ chính phủ hoặc tập đoàn lớn mới kham nổi.
• Nhà khoa học mới cần tính toán cao cấp, như trong nghiên cứu vật lí hạt và vũ trụ, sinh học cấu tạo, khí tượng địa cầu, khoa học máy tính.
  

Gần đây nhờ sự phổ biến của phần cứng rẻ như CPU đa lõi, phần mềm tiện dụng như Erlang, đại chúng bắt đầu biết đến xử lí song song. Nhà khoa học xây để học, kĩ sư học để xây, bài viết này giới thiệu xử lí song song qua hình thức hỏi đáp dành cho kĩ sư.

Phần 1: Ý tưởng

Q: Xử lí song song là gì, có lợi gì?
A: Là phân chia bài toán to thành nhiều bài toán nhỏ, rồi giải cùng lúc, nhờ đó tốc độ giải bài toán gốc tăng lên.

Q: Ví dụ?
A: Tính tích phân trong khoảng [0, 100], thì có thể phân làm 2 bài toán nhỏ là tính tích phân trong khoảng [0, 50] và [50, 100], rồi cộng 2 kết quả lại.

Q: Windows là hệ điều hành đa nhiệm, chẳng phải xử lí song song đã đến tay đại chúng 20 chục năm nay là gì?
A: Concurrent khác parallel. Concurrent = song song về mặc cảm giác, hệ điều hành giả lập bằng chỉ một CPU bằng chiêu thức chia sẻ thời gian [scheduling]. Parallel = song song về mặt vật lí, phải có 2 CPU hoặc 2 lõi trở lên. Ví dụ người có đầu 2 lõi có thể viết 2 tay 2 văn bản khác nhau cùng lúc, còn người chỉ có 1 lõi nếu bảo là có thể vừa chat chit vừa làm việc, thì chỉ có thể làm việc được tẹo, ngưng, rồi chuyển sang chat chit.

Q: Tóm lại vấn đề cốt lõi là làm sao phân chia bài toán to được thành nhiều bài toán nhỏ?
A: WHAT chỉ vậy, còn HOW thì nhiều, hãy tìm hiểu vài từ khoá sau:

• domain decomposition: phân chia bài toán to thành nhiều bài toán nhỏ
  
• parameter search: cùng chương trình, nhưng chạy thành nhiều process khác nhau, mỗi process nhận tham số khác nhau, sau đó kết quả chạy của các process được tập hợp lại thành kết quả cuối cùng
• data parallel: phân chia dữ liệu cần xử lí thành nhiều phần rồi xử lí
• pipeline: gán từng resource song song với nhau cho từng luồng xử lí
• master/worker: phân pool chứa việc cần xử lí cho lần lượt nhiều worker, ví dụ theo kiểu round robin [không cần viết hoa vì không phải tên người như Robin Hood]
• EP [embarassingly parallel]

Phần 2: Kiến trúc hệ thống

Q: Như vậy sau khi phân chia được thành nhiều bài toán nhỏ, tốc độ xử lí chỉ còn tuỳ tốc độ CPU?
A: Đúng chưa đến một nửa.

• Còn yếu tố cực quan trọng ảnh hưởng đến tốc độ xử lí về mặt tồng thể nữa là tốc độ truyền tin, như băng thông bộ nhớ, băng thông mạng truyền dữ liệu giữa các máy tính trong trường hợp điện toán phân tán. Cụ thể hơn, hãy tìm hiểu 2 định luật Amdahl và Gustafson.
• Chi phí CPU là O[N] thì giá của mạng để nối N CPU với nhau là O[N log[N]], nên chi phí nối mạng làm đội giá thành hệ thống lên rất nhiều!
• Về lịch sử, tỉ lệ tính năng CPU : tính năng bộ nhớ : tính năng truyền tin theo thời gian ngày càng xấu đi.

Q: Kiến trúc phần cứng của hệ thống có khả năng xử lí song song thế nào?
A: Có 3 loại kiến trúc, phân loại dựa trên bộ nhớ.

• Bộ nhớ phân tán [distributed memory system]: Các CPU [số lượng có thể lên đến hàng chục ngàn!] có bộ nhớ độc lập với nhau [mỗi cái chừng vài GB đến chục GB], muốn kết thành mạng lưới thì phải truyền thông điệp cho nhau. Cấu trúc này scalable và dễ thực hiện nhất, vài đứa bạn cũng rủ nhau nối máy tính với nhau được, nhưng tốc độ xử lí phụ thuộc rất nhiều vào tốc độ mạng.
  
• Bộ nhớ chia sẻ [shared memory system]: Các CPU chia sẻ cùng một cục bộ nhớ duy nhất [dung luợng có thể lên đến vài trăm ngàn GB!]. Cấu trúc này kém scalable, khó thực hiện do đòi hỏi trình độ kĩ thuật phần cứng siêu đẳng. Hệ thống tạo ra nhìn trông như một [1!] máy tính duy nhất.
  
• Loại này không phổ biến, kết hợp cả 2 loại trên bằng phần mềm, thường ở cấp độ hệ điều hành.

Q: Nêu thử cấu hình của một siêu máy tính nào đó xem?
A: Đại học Tsukuba vừa đưa vào sử dụng vào tháng 6/2008

• Tổng khả năng xử lí 95 TFLOPS
• Tổng dung lượng ổ cứng 800TB, RAM 21TB
  
• Gồm 648 nút, mỗi nút gồm 4 CPU AMD quad-core Opteron 8000 [4x4 = 16 lõi], băng thông bộ nhớ 40GB/s [dùng Mellanox ConnectX Ininiband]
  
• Mạng để nối các nút có băng thông 8GB/s [dùng Quad-rail Infiniband]
  
• Hệ điều hành Red Hat Enteprise v.5 WS
• Dùng OpenMP hoặc MPI trong cùng nút, dùng MPI giữa các nút

Phần 3: Viết chương trình

Q: OK học đủ rồi, bây giờ muốn xây thử chương trình thì xây thế nào?
A: Có 2 thư viện nổi tiếng ứng với 2 kiến trúc trên.

• MPI: Ứng với kiến trúc bộ nhớ phân tán.
  
• OpenMP: Ứng với kiến trúc bộ nhớ chia sẻ. Cực hay ở chỗ chương trình vẫn viết như bình thường, muốn biến đoạn mã nào thành xử lí song song thì chỉ cần thêm vài dòng hướng dẫn cho trình biên dịch [directive]. Tuy nhiên khó có thể áp dụng vì người thường thì làm sao có trong tay một cái máy có cấu hình khủng khiếp trên.
• Nên dùng OpenMP nếu dưới 16 CPU [nên đặt số thread = số CPU], 16 trở lên nên dùng MPI.
• Chuyển từ chương trình bình thường sang chương trình dùng 2 thư viện trên thật ra không khó. Tập vài lần sẽ nhận ra "pattern".
• Thường không thể song song hoá hàm đệ qui, ví dụ nếu mỗi lần gọi sinh ra N thread, thì gọi vài lần máy sẽ treo. Do đó ví dụ cần biến giải thuật DFS thành BFS, vì DFS phải dùng đệ qui, còn BFS không cần. Tuy vậy, về nguyên tắc có thể biến mọi hàm đệ qui thành vòng lặp bằng cách dùng stack.

Q: Máy tôi có mỗi CPU cũng chẳng phải đa lõi, có dùng thử 2 thư viện trên được không?
A: Được. Xem câu hỏi về Windows ở trên.

Q: MPI trên Mac OS X?
A: Mac đã cài sẵn MPI.

• Biên dịch: gcc -l mpi
• Chạy: mpirun -n

Q: OpenMP trên Mac OS X?
A: Từ gcc 4.2 trở lên hỗ trợ OpenMP.

• Biên dịch: gcc-mp-4.2 -fopenmp
• Chạy: OMP_NUM_THREADS=

Q: Có chương trình ví dụ không?
A: Có thể tìm đầy trên mạng. Phía dưới bài viết này có đính kèm chương trình xếp ba lô [knapsack] dùng OpenMP và nhân ma trận dùng OpenMPI.

Phần 4: Câu hỏi dành cho độc giả

Q: Dòng CPU Xeon của Intel và Opteron của AMD đều theo kiến trúc x86, đều là CPU đa lõi được dùng rộng rãi. Nhưng Xeon theo kiến trúc SMP, Opteron theo kiến trúc NUMA, nên tính chất khác nhau. Hãy tìm hiểu băng thông bộ nhớ, từ đó nêu những điểm chú ý khi lập trình song song cho 2 dòng CPU này.

Q: Gần đây băng thông mạng tăng khủng khiếp, lên đến vài GB/s, nhưng độ trễ mạng không giảm mức như vậy. Điều này ảnh hưởng gì đến lập trình song song?

Q: Có bài toán khi chạy trên một CPU mất T1[sec]. Giả sử một cách lí tưởng có thể song song hoá để chạy trên p CPU với overhead là Tcomm[p][sec] [thời gian truyền tin là phụ thuộc số CPU]. [1] Hãy tính tỉ lệ tăng tốc s[p] và tỉ lệ song song hoá e[p]. [2] Giả sử Tcomm[p] = ap [phụ thuộc tuyến tính vào số CPU]. Để e[p] đạt tối thiểu 80% thì a phải có giá trị thế nào? Hãy biểu diễn nó theo T1 và p. [3] T1 là qui mô bài toán, p là độ song song, a là yếu tố ảnh hưởng thời gian truyền tin. Hãy bình luận quan hệ T1 và p với a.

Download chương trình ví dụ