Cải thiện hiệu năng chương trình bằng CPU hay thuật toán

Hiệu năng thực hiện 1 chương trình chủ yếu phụ thuộc vào 3 yếu tố:

• Tốc độ của CPU
• Số nhân của CPU (khả năng thực hiện chạy song song đa luồng)
• Giải thuật thực hiện bài toán

Dưới đây mình sẽ phân tích để các bạn thấy hiệu năng của chương trình phụ thuộc như nào vào từng yếu tố.

I. Tốc độ của CPU

Và đa số các bạn nghĩ là CPU mới có xung nhịp cao hơn CPU cũ bao nhiêu lần hoặc có nhiều nhân hơn CPU cũ bao lần thì tốc độ thực thi chương trình sẽ nhanh hơn bây nhiêu lần. Nếu các bạn nghĩ như vậy thì chắc chắn các bạn chưa đọc qua hoặc chưa biết đến định luật Amdahl.

Định luật Amdahl Giả sử bạn thay CPU mới có tốc độ cao hơn CPU cũ.

Định luật Amdahl nói rằng sự tằng tốc nhờ cải thiện hiệu năng của CPU = thời gian chạy toàn bộ tác vụ khi sử dụng CPU cũ / thời gian chạy toàn bộ tác vụ khi sử dụng CPU mới.

Độ tăng tốc phụ thuộc vào 2 thừa số:

• Tỉ lệ chương trình có thể cải thiện nhờ CPU mới. Ví dụ chương trình của bạn có 60 tính toán, 20 tính toán có thể được chuyển qua CPU mới (ví dụ CPU mới cung cấp tập lệnh mà CPU không có) như vậy tỉ lệ này là 20/60. Tỉ lệ này luôn nhỏ hơn hoặc bằng 1.
• Độ Tăng tốc thu được thu được từ CPU mới. Ví dụ 20 tính toán ở ví dụ trên ở CPU cũ hết 5s, CPU mới hết 2s, độ tăng tốc sẽ là 5/2

Thời gian chạy với CPU mới = Thời gian chạy CPU cũ * (1 - tỉ lệ chương trình có thể cải thiện nhờ CPU mới + tỉ lệ chương trình có thể cải thiện nhờ CPU mới / độc tăng tốc thu được từ CPU mới).

Độ tăng tốc tổng thể= Thời gian chạy trên CPU cũ / Thời gian chạy trên CPU mới

hay bằng 1 / (1 - tỉ lệ chương trình cải thiện nhờ CPU mới + tỉ lệ chương trình cải thiện nhờ CPU mới / độ tăng tốc thu được từ CPU mới).

Ví dụ 1:

Bạn thay CPU cho máy chủ web. CPU mới chạy nhanh hơn CPU cũ 10 lần (với số nhân giữa CPU cũ và mới là bằng nhau). Chương trình web của bạn giả sử tốn 60% cho SQL (I/O) và 40% tính toán (nhận kết quả từ cơ sở dữ liệu, render page). Hỏi tốc độ cải thiện từ việc thay CPU là bao nhiêu?

Giải:

Tỉ lệ chương trình có thể cải thiện nhờ CPU mới = 0.4 Độ tăng tốc = 10 Độ tăng tốc tổng thể = 1 / (0.6 + 0.4/10) = 1 / 0.64 = 1.56

Vậy dù rằng CPU có tính nhanh 10 lần thì tốc độ của cả hệ thống chỉ được cải thiện 1.56 lần.

Ví dụ 2:

Hàm căn bậc hai của một số thực được sử dụng rất nhiều trong đồ hoạ máy tính. Giả sử tính toán căn bậc 2 chiếm 20% tổng thời chạy của thao tác đồ hoạ. Bạn muốn tăng tốc độ của hệ thống đồ hoạ của bạn. Có 2 lựa chọn sau đây:

• Mua card đồ hoạ mới với chip tính toán nhanh hơn 10 lần.
• Tăng tốc độ của các thao tác số thực khác lên 1.6 lần (ngoài thao tác tính căn bậc 2). Giả sử tổng số thao tác số thực là 50% (50% tính toán của bạn liên quan đến số thực).

Bạn sẽ đầu tư tiền hay bỏ thời gian và trí não cải thiện các thao tác còn lại.

Giải:

Trường hợp 1, độ tăng tốc = 1 / (0.8 + 0.2 / 10) = 1 / 0.82 = 1.22

Trường hợp 2, độ tăng tốc = 1 / (0.5 + 0.5 / 1.6) = 1.23

Như vậy lựa chọn 2 cho kết quả tốt hơn 1 chút!

Quan sát

Nếu thử quan sát, bạn sẽ thấy từ công thức Amdahl có thể rút ra là độ tăng tốc phụ thuộc cả vào bản chất bài toán. Nếu tỉ lệ có thể tăng tốc được không cao, việc bạn thêm song song cũng không giải quyết vấn đề gì. Nói cách khác nếu tỉ lệ cải thiện nhờ CPU mới = 0 thì độ tăng tốc tổng thể sẽ là 1 / (1 + 0/10) = 1 tức không thay đổi.

Vậy thực sự một CPU mới khỏe hơn CPU cũ nhiều lần thì cũng chưa chắc cải thiện được nhiều hiệu năng xử lý chương trình của bạn.

II. Thực hiện các tác vụ song song

Giả sử bạn CPU bạn có 4 cores. Chương trình của bạn sẽ được lập lịch bởi kernel. Nếu bạn dùng 2 threads, tại thời điểm CPU được cấp cho process của bạn, 2 cores sẽ được sử dụng để chạy chương trình. Giả sử chương trình bạn dùng CPU để tính toán 50% thời gian, 50% thời gian còn lại được chia đều cho các cores.

Nếu không dùng thread, chương trình của bạn là 1 chương trình liên tục bình thường, tốc độ sẽ cải thiện sẽ là:

Độ tăng tốc = 1 / (0.5 + 0.5 / 1) = 1 (không tăng tí nào!) Nếu bạn dùng 2 threads:

Độ tăng tốc = 1 / (0.5 + 0.5 / 2) = 1.33 (Tăng 33%!)

Nếu bạn dùng 4 threads:

Độ tăng tốc = 1 / (0.5 + 0.5 / 4) = 1.6 (Tăng 60%!) Nếu dùng 8 threads, bạn mong chờ tốc độ tăng tốc là 1.7! Sai lầm! Lý do: giống như quan sát ở trên, bản thân việc chia việc cho CPU không phải là việc làm song song được. Nói cách khác CPU chỉ thực hiện được cùng 1 lúc 4 tác vụ. Nếu có nhiều hơn 4 tác vụ, tỉ lệ thực hiện song song (số task thực hiện đồng thời không đổi, nhưng só task phải thực hiện tăng lên) sẽ giảm khiến hiệu năng toàn hệ thống giảm xuống.

Ví dụ ta có 4 threads, thì số task có thể tận dụng được CPU là 100%. Khi ta có 5 threads, số threads có thể tận dụng được CPU sẽ giảm xuống 80%. Ta có thể xem sự thay đổi về hiệu năng so sánh tương đối với trường hợp 1 thread như sau:

4 threads: Độ tăng tốc = 1 / (0 + 1 / 4) = 4

5 threads: Độ tăng tốc = 1 / (0.2 + 0.8 / 4) = 1 / 0.4 = 2.5

Như vậy độ tăng tốc tương đối với trường hợp chỉ sử dụng 1 thread đã giảm từ 4 lần xuông còn 2.5 lần.

Nói cách khác, khi tất cả các cores đã làm việc thì việc tăng threads sẽ chỉ làm tăng thêm phần không thể tính song song, khiến hiệu năng hệ thống giảm. Ngoài ra còn có các chi phí khác mà ta chưa kể đến như: tạo một thread cũng tốn thời gian, bộ nhớ v.v.

Nói cách khác là tạo các tác vụ chạy song song thì các bạn chỉ nên tạo ra số Thread tối đa bằng số nhân (hoặc Thread với 1 số dòng CPU cao cấp có hỗ trợ. VD trên cac CPU Intel cóIntel® Hyper-Threading Technology) mà CPU hỗ trợ. Còn nếu bạn tăng số Thread lên quá số Thread mà CPU hỗ trợ thì có khi lại phản tác dụng là hiệu suất chương trình giảm xuống.

II. Giải thuật thực hiện bài toán

Cải thiện thuật toán xử lý các tác vụ đơn lẻ. Với trường hợp này nhiều bạn nghĩ là nó đơn giản, nhưng thực sự nó là mấu chốt để giải quyết bài toán về hiệu năng của chương trình.

Ở đây mình đưa các bạn 1 bài toán quen thuộc để thấy sự cải thiện hiệu năng trong các lần cải thiện thuật toán.

Bài toán tìm số nguyên tố

Chắc với các bạn lập trình thì ai cũng biết bài toán đơn giản này đúng ko. Ngày trước mình học thì giảng viên có bày cho cách đơn giản nhất để giải quyết nó.

def primeNumber1(n):
    i = 2
    while i < n:
        if n % i == 0:
            return False
        i += 1
    return True

Đây là thuật toán đơn giản và dễ hiểu nhất. Nhưng khi chạy thì nó cho hiệu năng chậm nhất. Và chỉ là để các bạn mới học lập trình tham khảo.

Rồi dần dần bạn nhận ra là ko cần chia hết các số chạy từ 2 -> nữa mà chỉ cần kiểm tra các số từ 2 -> n/2 rồi các số từ 2 -> căn bậc 2 của n thôi. Và thế là ta có 1 thuật toán mới để giải quyết bài toán.

def primeNumber2(n):
    i = 2
    m  = math.sqrt(n)
    while i < m:
        if n % i == 0:
            return False
        i += 1
    return True

Như vậy là các bạn đã cải thiện đáng kể hiệu xuất rồi "ít nhất là tăng 2 lần tốc độ chạy" và các bạn nghĩ minh đã tìm ra 1 thuật toán tối ưu. Nhưng các bạn có nghĩ là mình có thể thêm 1 số kiểm tra với số n trong vòng lặp để giảm thiểu số lượng vòng lặp đi chưa.

Ở đây mình giới thiệu với các bạn 1 thuận toán tốt hơn để giải quyết bài toán này.

def primeNumber3(n):
    if n == 2 or n == 3:
        return True

    if n == 1 or n % 2 == 0 or n % 3 == 0:
        return False

    if n < 25:
        return True

    m = math.sqrt(n)
    i, j = 5, 2
    while i <= m:
        if n % i == 0:
            return False
        else:
            i += j
            j = 6 - j
    return True

Như các bạn đã thấy ở trên là số lượng vòng lặp của chúng ta đã giả đi đánh kể rồi đúng ko. ở đây mình có 1 sô sánh nhỏ về thời gian thực hiện.

Đầu tiên chúng ta thử nghiệm 1 với 1 số tương đối nhỏ để kiểm nghiệm kết quả.

Số: 3083058289

Ở đây bạn đã thấy sự khác biệt về hiệu năng giữa thuật toán đơn giản 1 và thuật toán rút gọn 2 và 3 chưa. Với số tương đối nhỏ như này thì thuật toán 2 vs 3 chưa thể dc hiện sự khác nhau nhiều lắm về hiệu năng.

Tiếp đây mình sẽ thử 1 số lớn hơn chút để thấy sự khác biệt giữa thuật toán 2 và 3 nhé. ** Số: 292345358739978707**

Như các bạn thấy, thời gian tính toán đã giảm đi gần 3 lần.

Vậy để cải thiện hiệu năng của 1 bài toán đơn lẻ thì việc quan trọng nhất là bạn phải tìm ra thuật toán tốt để giải quyết bài toán thay vì nâng cấp máy tính của bạn với 1 CPU mới nhanh hơn và mạnh hơn.

Kết hợp các yếu tố

Nếu thực sự thuật toán bạn tìm ra đã tốt rồi mà thời gian hoàn thành bài toán vẫn còn lâu thì bạn có thể tìm cách nhằm chia nhỏ bài toán thành các phần nhỏ để chúng ta có thể sử dụng các tính toán song song để năng cao hiệu năng tính toán nhằm giảm thời gian thực hiện bài toán.

Để ví dụ mình sẽ áp dụng thuật toán tìm số nguyên tố primeNumber3(n) ở phần trên để tìm tất cả các số nguyên tố nhỏ hơn 1 số cho trước.

Ở đây mình sẽ thực hiện 2 cách. Đầu tiên là tính toán với 1 thread và 8 thread ( CPU mình là 4core/8thread nên để tối ưu mình sẽ cho chạy cả 8 thread cùng 1 lúc ) Số: 10000000

Thông qua bài viết trên đây, mình hy vọng các bạn hiểu dc tầm quan trọng của thuật toán cũng như cách tăng hiệu suất thực hiện 1 bài toán.