Lập lịch quá trình tĩnh

Mô hình QT đi trước trong hình 5.1 (a) được sử dụng trong lập lịch đa xử lý tĩnh mà mục tiêu căn bản là tối thiểu hoá toàn bộ thời gian hoàn thành. Trong mô hình QT đi trước, một chương trình được trình bày bằng một DAG. Mỗi một nút trong hình vẽ biểu thị một nhiệm vụ được thực hiện trong một khoảng thời gian xác định. Mỗi cung nối biểu thị quan hệ đi trước giữa hai nhiệm vụ và được gán nhãn là trọng số biểu diễn số đơn vị TĐ được chuyển tới công việc tiếp sau khi hoàn thành công việc. Hình 5.5 a là ví dụ của chương trình DAG, bao gồm 7 nhiệm vụ (từ A đến G) cùng với việc chỉ rõ thời gian thực thi các nhiệm vụ đó là số đơn vị TĐ truyền thông giữa những nhiệm vụ với nhau. Kiến trúc hạ tầng trên đó các nhiệm vụ nền được thiết lập được đặc trưng bằng mô hình hệ thống truyền thông chỉ rõ giá thành truyền thông đơn vị giữa các bộ xử lý. Hình 5.5 b là một ví dụ của một mô hình hệ thống truyền thông cùng với ba bộ xử lý (P1, P2, P3). Giá thành truyền thông đơn vị thường là đáng kể với truyền thông đa xử lý và không đáng kể (không trọng lượng trong các đường nối nội tại) đối với truyền thông nội bộ. Mô hình này rất đơn giản, nó giữ truyền thông mà không cần đưa ra chi tiết cấu trúc phần cứng. Giá thành truyền thông giữa hai nhiệm vụ được tính bằng tích đơn vị giá thành truyền thông trong đồ thị hệ thống truyền thông với số đơn vị TĐ trong đồ thị xử lý ưu tiên. Ví dụ, nhiệm vụ A và E trong hình 5.5 được lập lịch tương ứng trên bộ xử lý P1 và P3, giá thành truyền thông là 8 = 2*4. Raywayd – Smith đưa ra khảo sát mô hình tương tự nhưng với một số hạn chế trong tất cả các QT có đơn vị tính toán và thời gian truyền thông. Thậm chí với một giả thiết đơn giản thì việc tìm giá trị tối thiểu của toàn bộ thời gian hoàn thành là NP-complete. Vì vậy chúng ta sẽ ứng dụng thuật toán heuristic cho việc tìm kiếm một ánh xạ tốt từ mô hình QT tới mô hình hệ thống.

Nếu bỏ qua phí tổn đường truyền, chúng ta xem xét phương pháp “heuristic tham ăn” đơn giản: chiến lược LS (lập lịch danh sách). Không một bộ xử lý nào đặt ở chế độ nhàn rỗi nếu còn những tác vụ có thể cần xử lý. Đối với DAG trong hình 5.5 a, kết quả lập lịch trong hình 5.6 a. Tổng thời gian hoàn thành là 16 đơn vị. Đối với đồ thị QT đi trước, khái niệm về đường tới hạn là rất có ích. Đường tới hạn là đường thực hiện dài nhất trong DAG, nó lại là đường ngắn nhất của toàn bộ thời gian hoàn tất. Đường tới hạn rất quan trọng trong nội dung lập lịch. Nó được sử dụng thường xuyên để phân tích việc thực thi một thuật toán “heuristic”. Đường tới hạn trong đồ thị hình 5.5 a là (ADG và AEG) độ dài 16 = 6+6+4. Vì vậy, LS trong hình 5.6 a (tổng thời gian hoàn thành cũng là 16) là tốt ưu nhất ngay khi tìm ra thuật toán. Một số thuật toán lập lịch được tìm ra cũng dựa vào đường tới hạn bắt nguồn từ tính ưu tiên cho những nhiệm vụ. Một số chiến lược lập lịch được tìm ra đơn giản là vạch ra tất cả công việc trong đường tới hạn lên một bộ xử lý đơn. Ví dụ trong hình 5.5 a, những nhiệm vụ A,D và G trên đường tới hạn được vạch tới bộ xử lý P1.

Tổng chi phí là 16

Tổng chi phí là 28

Tổng chi phí là 18

Hình 5.6.

Nếu tính đến phí tổn đường truyền, chúng ta có thể mở rộng việc lập lịch các danh sách trực tiếp (LS). Lập lịch các danh sách mở rộng đầu (ELS) đầu tiên thực hiện chỉ định những công việc tới bộ xử lý bằng việc cung tấp LS như khi hệ thống rỗi trong truyền thông liên kết. Nó thêm vào thời gian trễ truyền thông khi cần thiết để lập lịch được chứa bởi LS. Những trì hoãn truyền thông được tính toán bởi việc nhân giá thành đơn vị truyền thông và những đơn vị thông báo. Kết quả ELS cho cùng một vấn đề lập lịch có tổng thời gian hoàn thành là 28 đơn vị, như trình bày trong hình 5.6 b Dashed – lines trong hình biểu diễn QT đợi truyền thông (giá thành đơn vị truyền thông được nhân bởi số lượng các đơn vị thông báo).

Chiến lược ELS không thể đạt tối ưu. Vấn đề cơ bản là việc quyết định lập lịch đã được thiết lập mà không được báo trước trong việc truyền thông. Thuật toán có thể được cải tiến khi chúng ta trì hoãn quyết định lâu nhất cho đến khi chúng ta biết nhiều hơn về hệ thống. Theo chiến lược tham ăn này chúng ta có phương pháp lập lịch ưu tiên tác vụ đầu tiên (ETF), tác vụ sớm nhất phải được lập lịch đầu tiên. Sử dụng chiến lược này trong cùng một ví dụ, chúng ta sẽ trì hoãn lập lịch tác vụ F bởi tác vụ E sẽ trở thành lập lịch đầu tiên nếu trì hoãn truyền thông cũng liên quan đến việc tính toán. Lập lịch ETF trong hình 5.6 c đưa ra kết quả tốt hơn là tổng thời gian hoàn thành là 18 đơn vị.

212353446128126Hình 5.7. Giá tính toán và đồ thị truyền thôngMô hình QT và hệ thống là khá rõ ràng để mô hình hoá bài toán quá trình lập lịch trong DAG vào hệ thống với sự trễ truyền thông. Ví dụ chỉ ra rằng một lịch tối ưu cho hệ thống này không nhất thiết là lịch tốt cho hệ thống khác đồng thời với cấu trúc truyền thông khác nhau. Lập lịch tốt hơn có thể đạt được nhờ trộn nhau giữa truyền thông với tính toán và vì vậy che dấu hiệu quả tổng phí truyền thông. Khái niệm đường tới hạn có thể được dùng để hỗ trợ việc che dấu truyền thông (thu hút tổng phí truyền thông vào đường tới hạn). Bất kỳ đường tính toán ngắn hơn đường tới hạn được thu vào tổng phí TT nào đó để chập với một tính toán khác mà không ảnh hưởng đến tổng thời gian hoàn thiện.

Mô hình đồ thị đi trước biểu diễn QT được thảo luận trong phần trước là mô hình tính toán. Chương trình được biểu diễn bằng DAG là những ứng dụng người dùng điển hình, trong đó ràng buộc đi trước giữa các bài toán trong chương trình được người dùng chỉ dẫn rõ ràng. Mục tiêu cơ bản của lập lịch là đạt sự đồng thời tối đa việc thực hiện bài toán trong chương trình. Giảm tối thiểu truyền thông bài toán đóng vai trò thứ yếu, mặc dù có ảnh hưởng đáng kể tới số hiệu hiệu năng chính: thời gian hoàn thiện tổng thể.

Lập lịch QT cho những ứng dụng hệ thống theo nhiều bối cảnh rất khác nhau, bởi vì các QT trong một ứng dụng hệ thống có thể tạo ra một cách độc lập. Không có ràng buộc trước-sau ngoại trừ nhu cầu truyền thông giữa các QT. Không có thời gian hoàn thành của các QT như trường hợp mô hình QT đi trước. Mục tiêu của lập lịch QT là tận dụng tối đa nguồn tài nguyên và giảm tối thiểu truyền thông liên QT. Những ứng dụng này là mô hình tốt nhất cho mô hình QT truyền thông, được trình bày trong hình 5.1 b.

Mô hình QT truyền thông được biểu diễn bằng một đồ thị vô hướng G với tập V các đỉnh biểu diễn QT và tập E các cạnh có trọng số nối hai đỉnh biểu diễn số lượng giao dịch của hai QT liên kết nhau. Giả thiết về việc thực hiện QT và truyền thông là tương tự mô hình đi trước song có một sự khác biệt nhỏ. Việc thực hiện QT và truyền thông được biểu diễn theo giá thành.

Giá thành thực hiện QT là hàm theo BXL mà QT được gán tới đo để thực hiện. Vấn đề chính yếu là các bộ xử lý không đồng nhất (khác nhau về tốc độ và cấu trúc phần cứng). Do vậy, dùng ký hiệu e_j (pi) để biểu thị giá thành cho QT j trên pi, trong đó p_i là bộ xử lý được dùng cho QT j. Giá thành truyền thông ci,j (pi, pj) giữa hai QT i và j dùng cho hai bộ xử lý khác nhau p_i và p_j là tỉ lệ với trọng số cung kết nối i với j. Giá thành truyền thông được xem là không đáng kể (giá thành bằng 0) khi i =j. Bài toán được đặt ra là tìm phân công tối ưu của mô hình m mođun QT tới P bộ xử lý theo mối quan hệ của hàm đối tượng dưới đây được gọi là Bài toán định vị mođun.

Bài toán định vị mođun được Stone đưa ra đầu tiên và được nghiên cứu rộng rãi khá lâu. Tương tự như phần lớn các ứng dụng đồ thị, Bài toán định vị môđun tổng quát là NP-đầy đủ ngoại trừ một vài trường hợp hạn chế. Với P=2, Stone dự đoán một cách giải đa thức hiệu quả sử dụng thuật toán dòng - cực đại (maximum – flow) của Ford-Fulkerson. Các thuật toán giải đa thức cũng đã được phát triển bởi Bokhari và Towsley cho một vài đồ thị tôpô đặc biệt như đồ thị dạng cây và song song chuỗi. Trong ví dụ dưới đây chúng ta minh họa khái niệm trên bằng xem xét mô hình hàng hoá song xử lý cuả Stone trong việc phân chia đồ thị QT truyền thông tới kiến trúc để đạt được tổng giá thành thực hiện và truyền thông nhỏ nhất.

Khảo sát một chương trình bao gồm 6 QT sẽ được lập lịch vào hai bộ xử lý A và B nhằm giảm tối thiểu giá thành tổng tính toán và truyền thông. Thời gian thực hiện cho mỗi QT trên mỗi bộ xử lý được trình bày qua hình 5.7 a. Hình 5.7 b là đồ thị biểu diễn đa xử lý truyền thông giữa 6 QT. Hai bộ xử lý là không giống nhau. Ví dụ QT 1 cần 5 đơn vị giá thành để chạy trên bộ xử lý A nhưng cần 10 đơn vị giá thành khi chạy trên bộ xử lý B. Nhãn gán trên một cạnh của đồ thị truyền thông là giá thành truyền thông nếu hai QT kết nối nhau được định vị tới những bộ xử lý khác nhau. Để ánh xạ QT tới các bộ xử lý, phân chia thành hai đồ thị rời nhau bằng một đường kẻ cắt ngang qua một số cung. Kết quả phân chia thành hai đồ thị rời nhau, mỗi đồ thị gán tới một bộ xử lý. Tập các cung bị loại bỏ qua nhát cắt được gọi là tập cắt (cut set). Giá thành của một tập cắt là tổng trọng lượng của những cung biểu thị chính tổng giá thành truyền thông liên QT giữa hai bộ xử lý.

Bài toán tối ưu sẽ là tầm thường khi chúng ta chỉ phải giảm tối thiểu giá thành truyền thông vì chúng ta có thể sắp đặt tất cả các QT lên một bộ xử lý đơn và loại trừ tất cả trần các truyền thông liên QT. Tối ưu là vô nghĩa trừ phi cần phải đảm bảo các ràng buộc nào đó trong việc tính toán thực hiện và thi hành khác. Điều kiện hạn chế là QT nào đó chỉ có thể chạy được trên một bộ xử lý nào đó như hình 5.7 a là một ví dụ tốt về ràng buộc tính toán. Một vài việc thực thi có thể yêu cầu không nhiều hơn k QT chỉ định cho một bộ xử lý hay những QT đó đưọc chỉ định tới tất cả các bộ xử lý hiện có.

Hình 5.8 chỉ ra nhắt cắt giá thành tối thiểu cho trường hợp hình 5.7 với hàm tính giá COST (G, P). Trong lược đồ, bổ sung hai đỉnh mới biểu diễn các bộ xử lý A và B vào đồ thị truyền thông (cùng những cung nối mỗi bộ xử lý tới mỗi đỉnh QT). Trọng số được gán tới cạnh nối giữa bộ xử lý A và QT i là giá thành thực hiện QT i trên bộ xử lý B và ngược lại. Việc gán trọng số kiểu này là khôn ngoan bởi vì một vết cắt dọc theo đường đậm nét liên quan đến phân công QT được thực hiện trên bộ xử lý B. Chúng ta xem xét chỉ các nhát cắt phân chia các nút (A và B). Tổng trọng số của các đường nối trong vết cắt là tổng giá thành truyền thông và giá thành tính toán.

Việc tính tập cắt giá thành tối thiểu cho mô hình trên là tương đương với việc tìm dòng cực đại (maximum-flow) và cắt tối thiểu (minimum-cut) của mạng hàng hóa. Đồ thị ở hình 5.8 có thể hiểu như một mạng với các đường giao thông (cung) nối các thành phố (đỉnh) với nhau. Trọng số trên đường nối là thông lượng của đoạn. Nút A là thành phố nguồn và nút B là thành phố đích của việc vận chuyển hàng hoá. Khi cho một đồ thị hàng hoá, vấn đề tối ưu là tìm ra luồng cực đại từ nguồn tới đích. Fort và Fulkerson trình bày một thuật toán gán nhãn cho phép tìm một cách hệ thống đường mở rộng dần từ nguồn tới đích (thuật toán được thấy trong hầu hết các cuốn sách giáo khoa về thụât toán). Hai ông cũng chứng minh rằng luồng cực đại (maximum fow) cho một mạng tương đương mặt cắt nhỏ nhất (minimum cut) làm tách rời nguồn với đích trong đồ thị. Thuật toán luồng cực đại và định lý mặt cắt nhỏ nhất của luồng cực đại hoàn toàn phù hợp với sự tối ưu hoá bài toán định vị mô - đun (sự lập lịch QT) cho hai bộ xử lý.

Để tổng quát hoá bài toán có nhiều hơn hai bộ xử lý, Stone phác thảo giải pháp cho hệ thống có 3 bộ xử lý và đề xuất một phương pháp lặp sử dụng thuật toán cho hai bộ xử lý để giải quyết những bài toán có n bộ xử lý. Để tìm ra một sự định vị mô-đun của m QT cho n bộ xử lý, thuật toán mặt cắt nhỏ nhất luồng cực đại có thể áp dụng cho một bộ xử lý P_i và một bộ siêu xử lý ảo P bao gồm các bộ xử lý còn lại. Sau khi vài QT đã được lên lịch cho P_i, thủ tục được lặp lại tương tự trên bộ siêu xử lý cho đến khi tất cả các QT được ấn định.

Bài toán định vị mô-đun là phức tạp vì những mục đích của sự tối ưu hoá cho việc giảm chi phí tính toán và truyền tin xuống mức thấp nhất thường mâu thuẫn (đối lập) với nhau. Bài toán đủ quan trọng để chứng minh cho những giải pháp mang tính kinh nghiệm (tự tìm tòi). Một phương pháp để phân chia sự tối ưu hoá tính toán và truyền thông trở thành 2 vấn đề riêng biệt. Trong một mang máy tính nơi chi phí truyền tin có thể có ý nghĩa (đáng kể) hơn chi phí tính toán, ta có thể kếtp hợp các QT với sự tương tác giữa các QT bậc cao thành các nhóm QT. Các QT trong mỗi nhóm sau khi được ấn định cho bộ xử lý sẽ làm giảm chi phí tính toán xuống mức thấp nhất. Sự hợp nhất các QT truỳen tin giữa các bộ xử lý đơn giản nhưng có thể thực hiện được nhiều phép tính hơn trên bộ xử lý và do đó làm giảm bớt sự trùng lặp. Một giải pháp đơn giản là chỉ kết hợp những QT có chi phí truyền tin cao hơn một ngưỡng C nào đó. Thêm vào đó, số các QT trong một nhóm đơn không thể vượt quá một ngưỡng X khác. Sử dụng ví dụ trong hình 5.7 và chi phí truyền tin trung bình được ước lượng C=9 như mộtngưỡng, 3 nhóm (2,4), (1,6), (3,5) có thể tìm ra. Hiển nhiên nhóm (2,4) và (1,6) phải được sắp đặt tương ứng cho các bộ xử lý A và B. Nhóm (3,5) có thể được ấn định cho bộ xử lý A hoặc B. Việc ấn định chúng cho B có chi phí tính toán thấp hơn nhưng phải chịu một chi phí truyền tin cao hơn nhiều. Vì vậy chúng được ấn định cho A, kêt quả là chi phí tính toán trên A là 17, trên B là 14 và chi phí truyền tin giữa A và B là 10. Tổng chi phí là 41, một chi phí không cao hơn nhiều so với chi phí tối ưu là 38 nhận được từ thuật toán mặt cắt nhỏ nhất. Giá trị của ngưỡng X có thể được sử dụng để cân bằng sự thực hiện công việc trên các bộ xử lý. Sử dụng một giá trị X thích hợp để phân phối công việc cần làm thậm chí cũng sẽ ảnh hưởng tới sự phân chia (3,5) cho bộ xử lý A trong ví dụ tương tự.

Lịch trình tĩnh tối ưu có độ phức tạp cao. Các thuật toán đơn giản để tìm ra là hấp dẫn, thu hút. Mặc dù nhiều giải pháp để tìm ra tạo ra nhiều sự xét đoán nhưng chúng ta chỉ có những thông tin gần đúng về giá truyền thông và tình toán. Hơn thế nữa việc thi hành sự phân chia xử lý khởi tạo là không được phê bình nếu những xử lý có thể bị di chuyển sau khi chúng vừa được phân chia. Đó là một trong những thúc đẩy cho lập lịch xử lý động được đưa ra trong đoạn tiếp theo.