Khi tăng số bộ xử lý và lõi lên gấp đôi, gấp bốn, chúng ta dễ kỳ vọng chương trình cũng sẽ hoàn thành nhanh hơn tương ứng. Nhưng khi thực sự chạy thử, mức tăng tốc cảm nhận được thường thấp hơn kỳ vọng rất nhiều. Nhận định rằng phần công việc không thể chia ra xử lý song song sẽ kìm hãm tốc độ tổng thể chính là nội dung của “định luật Amdahl (Amdahl’s Law)”.
Nói đơn giản, định luật Amdahl giải thích rằng “khi chỉ cải tiến hoặc chạy song song một phần công việc, giới hạn trên của hệ số tăng tốc tổng thể được quyết định bởi phần tuần tự chưa thể cải thiện”. Nhà khoa học máy tính Gene Amdahl đã trình bày lập luận này trong bài báo “Tính khả thi của phương pháp tiếp cận dùng một bộ xử lý để đạt năng lực tính toán quy mô lớn (Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities)”, được công bố tại Hội nghị Máy tính Liên hợp Mùa xuân AFIPS năm 1967.
Trong tài liệu này, chúng ta sẽ lần lượt tìm hiểu ý nghĩa của hệ số tăng tốc trong định luật Amdahl, cách tỷ lệ tuần tự quyết định giới hạn trên, các ví dụ đời thường như nấu ăn và dây chuyền lắp ráp cùng thực tế của hệ thống đa lõi, rồi đến sự khác biệt với định luật Gustafson và cách vận dụng.
Giới hạn của xử lý song song theo định luật Amdahl
Ý nghĩa của hệ số tăng tốc và phần tuần tự
Định luật Amdahl vốn là một nguyên lý tổng quát về việc “hiệu năng tổng thể tăng bao nhiêu khi cải tiến một phần của hệ thống”, và ngày nay thường được dùng nhất để dự đoán hệ số tăng tốc lý thuyết trong tính toán song song. Điểm cốt lõi là xem xét riêng phần có thể chia ra xử lý song song và phần bắt buộc phải thực hiện tuần tự, thay vì mở rộng toàn bộ công việc cùng một lúc.
Nếu gọi p là tỷ lệ thời gian có thể chia ra xử lý song song trong tổng thời gian thực thi, và N là số bộ xử lý (hoặc lõi), thì hệ số tăng tốc lý thuyết bằng 1 chia cho ((1-p) + p/N). Nếu biểu diễn cùng nội dung bằng tỷ lệ tuần tự s, hệ số tăng tốc bằng 1 chia cho (s + (1-s)/N). Khi N càng lớn, ảnh hưởng của phần song song càng giảm, nhưng phần tuần tự s vẫn còn nguyên. Dù tăng số bộ xử lý đến vô hạn, hệ số tăng tốc cũng không thể vượt quá 1/s.
- Hệ số tăng tốc (Speedup): Giá trị bằng thời gian thực thi trước khi cải tiến chia cho thời gian thực thi sau khi cải tiến.
- Tỷ lệ tuần tự (Serial Fraction): Tỷ lệ thời gian phải xử lý theo thứ tự vì không thể chia ra thực hiện đồng thời.
- Tỷ lệ song song (Parallel Fraction): Tỷ lệ thời gian có thể phân chia cho nhiều bộ xử lý để thực hiện đồng thời.
Vì sao tăng số lõi mà mức tăng tốc cảm nhận được vẫn nhỏ?
Chỉ nhìn công thức có thể thấy trừu tượng, nhưng hình dung những giới hạn trên thường được nhắc đến sẽ giúp hiểu trực quan hơn. Nếu chỉ một nửa công việc có thể chia ra xử lý song song, thì dù tăng số lõi bao nhiêu, hệ số tăng tốc tổng thể cũng chỉ đạt tối đa hai lần. Ngay cả khi tỷ lệ có thể xử lý song song là 95 phần trăm, giới hạn trên lý thuyết vẫn là hai mươi lần. Đó là vì phần tuần tự chiếm 5 phần trăm còn lại kìm hãm tốc độ tổng thể.
(1) Lợi ích cận biên nhanh chóng giảm dần
Với cùng một tỷ lệ tuần tự, lợi ích thu được khi tăng số lõi từ 2 lên 4 rồi 8 sẽ ngày càng nhỏ. Khi phần song song đã được rút ngắn, phần tuần tự sẽ trở thành nút thắt cổ chai.
(2) Giao tiếp và đồng bộ hóa cũng gần với xử lý tuần tự
Trong thực tế, khi phân chia công việc cho các lõi, hệ thống cần thời gian để tập hợp kết quả, đặt khóa và đồng bộ bộ nhớ. Những chi phí này nằm ngoài giả định “song song hoàn hảo” của công thức, nên hệ số tăng tốc cảm nhận được thường còn thấp hơn giá trị lý thuyết.
(3) Nút thắt chỉ một dòng cũng quyết định toàn bộ
Ngay cả đoạn mã tuần tự ngắn như đọc tệp, khởi tạo hay tính tổng cuối cùng cũng làm giảm đáng kể giới hạn trên nếu chiếm tỷ lệ không nhỏ. Đây là lý do khi thiết kế CPU đa lõi và tăng tốc bằng GPU, người ta hỏi “phần tuần tự còn nằm ở đâu” trước khi hỏi “nên song song hóa phần nào”.
Ví dụ đời thường qua nấu ăn và dây chuyền lắp ráp
Định luật Amdahl cũng xuất hiện với cùng cấu trúc trong những lĩnh vực ngoài máy tính. Hãy hình dung việc chuẩn bị bữa tối cho mười vị khách. Thêm người phụ giúp có thể đẩy nhanh việc thái rau và xào nấu, nhưng thời gian nướng trong lò không giảm dù có nhiều người hơn. Nếu lò nướng là phần tuần tự, thì dù thêm bao nhiêu người, tổng thời gian chuẩn bị bữa tối vẫn bị ràng buộc bởi phần đó.
Dây chuyền lắp ráp trong nhà máy cũng tương tự. Dù nhiều trạm cùng lắp các bộ phận, nếu khâu kiểm tra cuối cùng hoặc đóng gói chỉ diễn ra trên một tuyến, năng suất của tuyến đó sẽ quyết định tốc độ tổng thể. Trong các cuộc họp, việc nghiên cứu tài liệu có thể phân chia cho nhiều người, nhưng quá trình đi đến một sự đồng thuận để ra quyết định khó có thể chia ra thực hiện đồng thời.
Những điểm cần xem xét trong đời sống
- Nút thắt cổ chai (Bottleneck): Phần tuần tự chậm nhất chi phối toàn bộ luồng công việc.
- Công việc có thể phân chia (Parallel Work): Phần có thể tiến hành độc lập và đồng thời.
- Công việc phối hợp (Coordination): Chi phí tập hợp kết quả và sắp xếp đúng trình tự cũng làm giảm tốc độ cảm nhận được.
Cách xem xét cùng với định luật Gustafson
Định luật Amdahl cho thấy giới hạn trên khi tăng số bộ xử lý trong khi “giữ nguyên kích thước bài toán”. Trong khi đó, định luật Gustafson (Gustafson’s Law), được John Gustafson hệ thống hóa vào khoảng năm 1988, nhìn nhận rằng khi số bộ xử lý tăng, có thể tăng cả kích thước bài toán để thực hiện khối lượng công việc lớn hơn trong cùng thời gian. Hoàn thành nhanh hơn một bài tập cố định và chạy mô phỏng chính xác hơn trong cùng thời hạn là hai câu hỏi khác nhau.
(1) Amdahl đặc biệt hữu ích với bài toán có kích thước cố định
Khi mục tiêu là “nhanh hơn” với cùng dữ liệu và cùng độ phân giải, điều cốt lõi là giảm tỷ lệ tuần tự. Những thiết kế như thay đổi thuật toán, giảm I/O và loại bỏ đồng bộ hóa không cần thiết thuộc trường hợp này.
(2) Gustafson hữu ích khi mở rộng quy mô
Với những bài toán có thể tăng số ô lưới hoặc mẫu như tính toán khí tượng và khoa học, số lõi càng tăng thì khối lượng công việc được xử lý song song cũng tăng theo, nhờ đó lợi ích thực tế có thể lớn hơn.
(3) Không đặt hai định luật vào thế đối lập
Đây là những kịch bản khác nhau về việc “giữ nguyên điều gì và tăng điều gì”, chứ không phải một trong hai công thức sai. Khi phát triển sản phẩm, trước hết hãy xác định mục tiêu là giảm độ trễ hay tăng thông lượng và quy mô, rồi sử dụng góc nhìn phù hợp.
Thay vì nâng kỳ vọng chỉ dựa vào quảng cáo về số lõi, điều quan trọng là đo trước xem phần nào trong công việc của chúng ta vẫn phải xử lý tuần tự. Thành bại của việc song song hóa gắn với mức độ rút ngắn thời gian không thể phân chia hơn là số lõi đã mua.
Định luật Amdahl là nguyên lý cho rằng khi chỉ cải tiến phần có thể chia ra xử lý song song, giới hạn trên của hệ số tăng tốc tổng thể vẫn được quyết định bởi tỷ lệ của phần tuần tự. Việc tìm và rút ngắn phần tuần tự gây nút thắt tác động trực tiếp hơn đến trần hiệu năng so với việc tăng số lõi.
Đo thời gian không thể phân chia trước khi xem xét số bộ xử lý chính là bước đầu tiên để vận dụng sáng suốt định luật Amdahl trong thực tiễn.
