Mô hình hiệu năng hệ thống

Phương tiện TT và đồng bộ là các thành phần hệ thống thiết yếu hỗ trợ việc thực hiện đồng thời các QT tương tác. Trước khi thực hiện, QT cần phải được lên lịch (lập lịch) và định vị tài nguyên. Mục đích chính của lập lịch là nâng cao độ đo hiệu năng tổng thể hệ thống, chẳng hạn thời gian hoàn thành QT và tận dụng bộ xử lý. Việc tồn tại các nút xử lý phức trong hệ phân tán làm nảy sinh vấn đề thách thức cho lập lịch QT trên các bộ xử lý và ngược lại. Lập lịch không chỉ được thực hiện cục bộ trên mỗi nút mà trên toàn bộ hệ thống. Các QT phân tán có thể được thực hiện trên các nút xử lý từ xa và có thể di trú từ nút này tới nút khác để phân bố tải nhằm tăng hiệu năng. Mục đích thứ hai của lập lịch là thẹc hiện trong suốt định vị và hiệu năng bằng lập lịch QT phân tán.

Vấn đề lập lịch QT (hay công việc) đã được khảo sát rộng rãi đối với nghiên cứu điều hành. Đã có nhiều kết quả lý thuyết về độ phức tạp của lập lịch bộ đa xử lý. Tuy nhiên, lập lịch QT trong hệ phân tán cần đề cập cácλchú ý thực tế thường bị bỏ qua trong phân tích lập lịch đa xử lý truyền thống. Trong hệ phân tán, tổng phí TT là đáng kể, tác dụng của hạ tầng cơ sở không thể bỏ qua và tính “động” của hệ thống phải được định vị. Các thực tế này góp phần tạo thêm sự phức tạp của lập lịch QT phân tán.

Chương này đưa ra mô hình nhằm đạt được hiệu quả hạ tầng TT và hệ thống khi lập lịch. Lập lịch QT phân tán được tổ chức thành hai nội dung: lập lịch QT tĩnh, và chia sẻ và cân bằng tải động. Thi hành thuật toán lập lịch phân tán đòi hỏi thực hiện từ xa và/hoặc năng lực di trú QT trong hệ thống. Một số vấn đề thi hành thực hiện từ xa và di trú QT được đề cập. Kết thúc chương giới thiệu hệ thống thời gian thực phân tán, trong đó lập lịch là khoảng tới hạn thời gian và xứng đáng được quan tâm đặc biệt.

Các thuật toán song song và phân tán được mô tả như tập QT phức được chi phối bằng các quy tắc điều chỉnh tương tác giữa các QT. ánh xạ thuật toán vào một kiến trúc được xem xét như bộ phận của thiết kế thuật toán hoặc được xem xét một cách riêng biệt như bài toán lập lịch đối với một thuật toán cho trước và một kiến trúc hệ thống cho trước. Chương 3 sử dụng mô hình đồ thị để mô tả TT QT và tại đây xem xét tương tác QT theo mô tả tổng quát nhất theo thuật ngữ ánh xạ. Hình 5.1 cho ví dụ đơn giản về một chương trình tính toán gồm có 4 QT được ánh xạ tới một hệ thống máy tính kép với 2 bộ xử lý. Tương tác QT được biểu diễn khác nhau theo ba mô hình.

Trong mô hình QT đi trước ở hình 5.1 (a), tập QT được biểu diễn bằng một đồ thị định phướng phi chu trình (DAG-Directed Acycle Graph). Cung có hướng biểu thị quan hệ đi trước giữa các QT và chịu tổng phí truyền thông nếu các QT kết nối với nhau bằng một cung được ánh xạ tới 2 bộ xử lý khác nhau. Mô hình này được ứng dụng tốt nhất cho các QT đồng thời được sinh ra do các cấu trúc ngôn ngữ đồng thời như cobegin/coend hay fork/join. Một độ đo hữu dụng cho lập lịch tập QT như vậy là làm giảm thời gian hoàn thành bài toán xuống mức tối thiểu, bao gồm cả thời gian tính toán và TT.

Mô hình QT TT trong hình 5.1 (b) mô tả một kịch bản khác, trong đó QT được tạo ra để cùng tồn tại và truyền thông dị bộ. Cung vô hướng trong mô hình QT TT chỉ mô tả nhu cầu truyền thông giữa các QT. Do thời gian thực hiện trong mô hình là không rõ ràng nên mục tiêu lập lịch là tối ưu tổng giá truyền thông và tính toán. Bài toán được chia theo phương pháp như vậy làm giảm đến mức tối thiểu chi phí truyền thông liên-bộ xử lý và giá tính toán của QT trên các bộ xử lý. Mô hình của QT đi trước và truyền thông là các mô hình QT tương tác.

Mô hình QT độc lập ở hình 5.1(c), tương tác QT là ngầm định, và giả sử rằng các QT có thể chạy một cách độc lập và được hoàn thành trong thời gian hữu hạn. Các QT được ánh xạ tới các bộ xử lý sao cho tận dụng được các bộ xử lý một cách tối đa và làm giảm thời gian quay vòng các QT xuống đến mức nhỏ nhất. Thời gian quay vòng các QT được xác định như tổng thời gian thực hiện và xếp hàng do phải chờ các QT khác. Trong trường hợp động, cho phép QT “di trú” giữa các bộ xử lý để đạt hiệu quả trong chia xẻ và cân bằng tải. Nếu QT được phép di trú từ nút có tải lớn đến nút có tải nhỏ thì định vị ban đầu các QT là chưa tới hạn. Hơn nữa, hiệu năng được cải tiến đáng kể do lịch các QT trở nên thích ứng với sự thay đổi tải hệ thống. Chia xẻ và cân bằng tải không hạn chế các QT độc lập. Nếu QT truyền thông với một QT khác thì chiến lược “di trú” nên chú ý cân bằng các thay đổi trong các nhu cầu truyền thông giữa các bộ xử lý do thay đổi bộ xử lý và lợi ích từ chia xẻ tải.

Phân hoạch bài toán thành nhiều QT để giải làm thời gian hoàn thành bài toán nhanh hơn. Tăng tốc được coi như độ đo hiệu năng là mục tiêu đáng quan tâm trong thiết kế các thuật toán song song và phân tán. Tăng tốc tính toán là một hàm của thiết kế thuật toán và hiệu quả của thuật toán lập lịch ánh xạ thuật toán vào kiến trúc hệ thống hạ tầng. Dưới đây đưa ra một mô hình tăng tốc mô tả và phân tích mối quan hệ giữa thuật toán, kiến trúc hệ thống và lịch thực hiện. Trong mô hình này, hệ số tăng tốc S là hàm của thuật toán song song, kiến trúc của hệ thống và lịch thực hiện, được biểu diễn theo công thức:

S = F(thuật toán, hệ thống, lịch).

S có thể được viết như sau:

$S = \frac{OSPT}{CPT} = \frac{OSPT}{{OCPT}_{ideal}} x \frac{{OCPT}_{iedal}}{CPT} = S_{i} {xS}_{d}$ Trong đó :

+ OSPT (Optimal Sequential Processing Time): thời gian tốt nhất có thể đạt được trên bộ đơn xử lý sử dụng thuật toán tuần tự tốt nhất.

+ CPT (Concurrent Processing Time): thời gian thực sự đạt được trên một hệ n-bộ xử lý cùng với thuật toán đồng thời và một phương pháp lập lịch cụ thể đang được xem xét.

+ OCPT_ideal(Optimal Concurrent Processing Time on an ideal system): thời gian tốt nhất có thể đạt được với cũng thuật toán đồng thời được xem xét trên một hệ n-bộ xử lý lý tưởng (một hệ thống không tính tới tổng phí truyền tin giữa các bộ xử lý) và đã được lên chương trình bằng một phương thức lập lịch tối ưu nhất.

+ S_i: độ tăng tốc lý tưởng đạt được nhờ sử dụng hệ đa xử lý phức so với thời gian tuần tự tốt nhất.

+S_d: độ hao phí của hệ thống thực hiện trên thực tế so với hệ thống lý tưởng.

Để nhận rõ vai trò của thuật toán, hệ thống và lập lịch, công thức biểu diễn độ tăng tốc được rút gọn hơn. S_i có thể được viết lại như sau:

$S_{i} = \frac{RC}{RP} \times n$ trong đó: $RP = \frac{\sum_{i = 1}^{m} P_{i}}{OSPT}$ và $RC = \frac{\sum_{i = 1}^{m} P_{i}}{{OSPT}_{ideal} \times n}$

và n là số lượng bộ xử lý. Đại lượng $\sum_{i = 1}^{m} P_{i}$ là tổng số các thao tác tính toán của thuật toán đồng thời, trong đó m là số bài toán con trong thuật toán. Đại lượng này thường lớn hơn OSPT do các mã phụ có thể được bổ sung khi biến đổi thuật toán tuần tự thành thuật toán đồng thời. S_d có thể được viết lại như sau:

$S_{d} = \frac{1}{1 + ρ}$ trong đó, $ρ = \frac{CPT - {OCPT}_{ideal}}{{OCPT}_{ideal}}$

Trong biểu thức S_i, RP là yêu cầu xử lý liên quan (Relative Processing), là tỷ số giữa tổng số thời gian tính toán cần thiết cho thuật toán song song so với thời gian xử lý của thuật toán tuần tự tối ưu. Nó cho thấy lượng hao phí tăng tốc do thay thế thuật toán tuần tự tối ưu bằng một thuật toán thích hợp thực hiện đồng thời nhưng có thể có tổng nhu cầu xử lý lớn hơn. RP khác với S_d ở chỗ RP là lượng thời gian hao phí của thuật toán song song do việc thay đổi thuật toán, trong khi S_d là lượng thời gian hao phí của thuật toán song song do việc thi hành thuật toán.

Độ đo đồng thời liên quan RC (Relative Concurency) đo mức độ sử dụng tốt nhất của hệ n-bộ xử lý. Nó cho thấy bài toán đã cho và thuật toán dành cho bài toán tốt như thế nào đối với hệ n-bộ xử lý lý tưởng. RC=1 tương ứng với việc sử dụng các bộ xử lý là tốt nhất. Một thuật toán đồng thời tốt là thuật toán làm cho RP đạt giá trị nhỏ nhất và RC đạt giá trị lớn nhất. Biểu thức cuối cùng cho tăng tốc S là:

S = \frac{RC}{RP} \times \frac{1}{1 + ρ} \times n

Tóm lại, nhân tố tăng tốc S là một hàm của RC (tổn thất lý thuyết khi song song hóa), RP (lượng bổ sung vào tổng nhu cầu tính toán), ρ (thiếu hụt song song hóa khi thi hành trên một máy thực) và n (số bộ xử lý được sử dụng).

Số hạng ρ được goi là hiệu suất tổn thất, được xác định như tỷ số giữa tổng phí theo hệ thống thực nói trên theo mọi nguyên nhân đối với thời gian xử lý tối ưu lý tưởng. Nó là hàm của lập lịch và kiến trúc hệ thống. Rất hữu dụng khi phân tích ρ thành 2 số hạng riêng biệt : ρ = ρsyst+ ρsched , tương ứng với hiệu suất hao phí do hệ thống và lịch gây ra. Tuy nhiên, điều này không dễ thực hiện do lịch và hệ thống phụ thuộc vào nhau. Do tổng phí TT đôi lúc bị che khuất và chồng chéo lên các QT tính toán khác trong lập lịch nên có thể không ảnh hưởng tới tổn thất hiệu suất. Đây là một điểm chính trong lập lịch QT có tính đến tổng phí TT giữa các bộ xử lý. Một lịch tốt là lịch hợp lý nhất trên hệ thống đã cho sao cho nó có khả năng che dấu được tổng phí càng nhiều càng tốt. Đoạn tiếp theo minh hoạ về sự phụ thuộc lẫn nhau giữa hai yếu tố lập lịch và hệ thống và phân tích sơ bộ hai yếu tố này.

Giả sử X mô tả một hệ đa máy tính đang được nghiên cứu và Y' mô tả một chiến lược lập lịch được mở rộng cho hệ thống X từ chiến lược lập lịch Y trên hệ thống lý tưởng tương ứng. CPT( X,Y') và CPTiedal (Y) tương ứng là các thời gian quá trình đồng thời cho máy X theo các chiến lược lập lịch Y' và Y tương ứng. Có thể biểu diễn hiệu suất hao phí ρnhư sau:

Tương tự, chúng ta làm ngược quá trình phân tích theo giải tích tổn thất hiệu quả lập lịch không tối ưu trước khi giải tích hiệu quả của hệ thống không lý tưởng. Như thế,

Hình 5.2 phân tích tường minh hiệu suất hao phí do lập lịch và TT trong hệ thống gây ra. ảnh hưởng đáng kể của TT trong hệ thống được định vị cẩn thận khi thiết kế các thuật toán lập lịch phân tán.

Mô hình tăng tốc chung tích hợp 3 thành phần chính: phát triển thuật toán, kiến trúc hệ thống và chiến lược lập lịch, với mục đích làm giảm đến mức tối thiểu tổng thời gian hoàn thành (makespan) của tập các QT tương tác. Nếu các QT không bị ràng buộc bởi quan hệ đi trước và được tự do phân phối lại hoặc được di trú dọc theo các bộ xử lý trong hệ thống thì hiệu năng được cải tiến hơn nữa nhờ chia xẻ tải. Điều đó có nghĩa là, các QT có thể được di trú từ những nút có tải lớn tới những nút rỗi (nếu tồn tại các nút đó). Có thể được tiến thêm một bước xa hơn khi tới chia xẻ tải giữa tất cả các nút sao cho càng đều càng tốt, bằng phương pháp tĩnh hoặc động. Phân bố tải tĩnh được gọi chia xẻ tải, và phân bố tải động được gọi là cân bằng tải. Lợi ích của phân bố tải là các bộ xử lý được tận dụng triệt để hơn và cải tiến được thời gian quay vòng các QT. Di trú QT rút gọn thời gian xếp hàng, kể cả giá tăng thêm theo tổng phí TT.

Mục đích của chia xẻ tải trong hệ phân tán là làm hoàn toàn rành mạch. Điều đó cũng phù hợp với bất kỳ việc khởi tạo máy tính gồm nhiều nút xử lý được ghép nối lỏng, luôn có một số nút có tải lớn và một số nút có tải nhỏ, nhưng phần lớn các nút là hoàn toàn không tải. Để tận dụng hơn về năng suất xử lý, các QT có thể được gửi tới các bộ xử lý rỗi theo phương pháp tĩnh ngay khi chúng vừa xuất hiện (tương ứng với mô hình bộ xử lý xâu) hoặc “di trú” theo phương pháp động từ những bộ xử lý có tải lớn đến những bộ xử lý có tải nhỏ (tương ứng với mô hình trạm làm việc). Thời gian quay vòng QT cũng được cải tiến.

Hình 5.3 trình bày hai mô hình hàng đợi đơn giản về môi trường phân tán theo bộ xử lý xâu và theo trạm làm việc so sánh với hệ thống các trạm làm việc cô lập với đường tham chiếu (baseline). Để rõ ràng, trong các mô hình này chỉ gồm hai nút xử lý. Trong mô hình bộ xử lý xâu, một QT được gửi tới một bộ xử lý phù hợp và ở lại đó trong suốt thời gian thực hiện nó.

Hiệu năng hệ thống được mô tả theo mô hình dòng xếp hàng có thể tính được nhờ sử dụng kiến thức toán học như lý thuyết hàng đợi. Sử dụng kí hiệu chuẩn Kendall để mô tả tính chất thống kê của hàng đợi. Hàng đợi X/Y/c là một QT X xuất hiện, một phân bố thời gian phục vụ Y, và c máy phục vụ. Ví dụ, có thể mô tả bộ xử lý xâu như hàng đợi M/M/2. M tuân theo phân bố Markov, là loại phân bố dễ xử lý khi phân tích. Mô hình hệ thống với hai máy phục vụ trong đó công việc đợi xử lý có thể được phục vụ trên một bộ xử lý bất kỳ. Tổng quát, mô hình hóa bộ xử lý xâu là hàng đợi M/M/k.

Trong mô hình trạm làm việc di trú, các QT được phép dịch chuyển từ trạm này tới trạm khác. Quyết định di trú QT vào lúc nào, ở đâu, như thế nào sẽ được xem xét sau và chưa được trình bày tường minh trong hình vẽ. Di trú QT phải chịu độ trễ truyền thông được lấy mẫu bởi một hàng đợi truyền thông do một kênh truyền thông phục vụ. Tỷ số di trú  là hàm của dải thông kênh truyền, giao thức di trú QT, và quan trọng hơn là ngữ cảnh và thông tin trạng thái của QT đang được chuyển giao.

Hình 5.4 chỉ ra lợi ích của phân bố (hoặc phân bố lại) tải trong các mô hình bộ xử lý xâu và trạm làm việc. Các cận trên và cận dưới cho thời gian quay vòng quá trình trung bình được trình bày bằng hai phương trình của mô hình M/M/1 và M/M/2:

{TT}_{1} = \frac{1}{μ - λ}

{TT}_{2} = \frac{μ}{(μ + γ) (μ + λ)}

TT1_{là thời gian quay vòng trung bình, với λ và μ là tần suất xuất hiện QT và tần suất được phục vụ của mỗi nút xử lý. Công thức liên quan có thể tìm thấy trong lý thuyết hàng đợi cổ điển. Hiệu năng trong mô hình trạm làm việc với tổng chi phí TT nằm giữa M/M/1 (không có chia xẻ tải) và M/M/2 (mô hình bộ xử lý xâu lý tưởng với tổng phí TT là không đáng kể). Tỷ lệ di trú QT  thay đổi từ 0 đến ∞, tương ứng với hiệu năng tiệm cận của M/M/1 và M/M/2.}