Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Trình biên dịch] Lập lịch lệnh theo đường găng

    Lập lịch lệnh (instruction scheduling) là phép tối ưu ở giai đoạn sinh mã cuối, nhằm sắp xếp thứ tự/thời điểm phát hành các lệnh trên một kiến trúc pipeline sao cho tôn trọng các ràng buộc phụ thuộc dữ liệu (data hazard), ví dụ độ trễ (latency) giữa một lệnh nạp dữ liệu (load) và lệnh sử dụng kết quả của nó. Bài này yêu cầu tính thời điểm bắt đầu sớm nhất (earliest start time) của từng lệnh và tổng số chu kỳ (cycle) cần thiết, giả sử có đủ tài nguyên phần cứng để thực thi song song (không giới hạn số lệnh phát hành đồng thời), chỉ bị ràng buộc bởi phụ thuộc dữ liệu.

    Cho nnn lệnh (đánh số 0,…,n−10, \ldots, n-10,…,n−1), lệnh iii có thời lượng thực thi di≥1d_i \ge 1di​≥1 chu kỳ. Có mmm ràng buộc phụ thuộc dạng (u,v,lat)(u, v, lat)(u,v,lat), nghĩa là lệnh vvv chỉ được phép bắt đầu khi lệnh uuu đã bắt đầu được ít nhất latlatlat chu kỳ, tức start(v)≥start(u)+lat\text{start}(v) \ge \text{start}(u) + latstart(v)≥start(u)+lat (giá trị latlatlat có thể nhỏ hơn dud_udu​, mô phỏng việc lệnh vvv có thể bắt đầu trước khi uuu hoàn tất, nếu kiến trúc cho phép pipeline). Dữ liệu đảm bảo tập ràng buộc tạo thành một đồ thị có hướng không chu trình (DAG).

    Thời điểm bắt đầu sớm nhất của mỗi lệnh được tính bằng: start(v)=max⁡(0, max⁡(u,v,lat) laˋ một raˋng buộc(start(u)+lat))\text{start}(v) = \max\Big(0,\ \max_{(u,v,lat) \text{ là một ràng buộc}} \big(\text{start}(u) + lat\big)\Big)start(v)=max(0, max(u,v,lat) laˋ một raˋng buộc​(start(u)+lat)) (lệnh không có ràng buộc nào bắt đầu ở chu kỳ 000).

    Tổng số chu kỳ cần thiết (makespan) là thời điểm hoàn tất của lệnh kết thúc muộn nhất: makespan=max⁡i=0,…,n−1(start(i)+di)\text{makespan} = \max_{i=0,\ldots,n-1} \big(\text{start}(i) + d_i\big)makespan=maxi=0,…,n−1​(start(i)+di​)

    Ví dụ: 3 lệnh với d=(2,3,1)d = (2, 3, 1)d=(2,3,1) và hai ràng buộc (0,1,2)(0,1,2)(0,1,2), (1,2,3)(1,2,3)(1,2,3): start(0)=0\text{start}(0)=0start(0)=0, start(1)=max⁡(0,0+2)=2\text{start}(1)=\max(0, 0+2)=2start(1)=max(0,0+2)=2, start(2)=max⁡(0,2+3)=5\text{start}(2)=\max(0, 2+3)=5start(2)=max(0,2+3)=5; makespan =max⁡(0+2, 2+3, 5+1)=6=\max(0+2,\ 2+3,\ 5+1)=6=max(0+2, 2+3, 5+1)=6.

    • Định dạng đầu vào:

      Dòng đầu tiên chứa hai số nguyên nnn, mmm (1≤n≤5001 \le n \le 5001≤n≤500, 0≤m≤50000 \le m \le 50000≤m≤5000).

      Dòng thứ hai chứa nnn số nguyên d0,d1,…,dn−1d_0, d_1, \ldots, d_{n-1}d0​,d1​,…,dn−1​ (1≤di≤10001 \le d_i \le 10001≤di​≤1000).

      mmm dòng tiếp theo, mỗi dòng ba số nguyên uuu, vvv, latlatlat (0≤u,v<n0 \le u, v < n0≤u,v<n, u≠vu \ne vu=v, 0≤lat≤10000 \le lat \le 10000≤lat≤1000) mô tả ràng buộc start(v)≥start(u)+lat\text{start}(v) \ge \text{start}(u) + latstart(v)≥start(u)+lat. Đảm bảo các ràng buộc tạo thành DAG.

    • Định dạng đầu ra:

      In ra nnn dòng đầu: dòng thứ iii (i=1,…,ni = 1, \ldots, ni=1,…,n) là start(i−1)\text{start}(i-1)start(i−1) — thời điểm bắt đầu sớm nhất của lệnh i−1i-1i−1. Dòng cuối cùng (dòng thứ n+1n+1n+1) in ra giá trị makespan (tổng số chu kỳ cần thiết) như định nghĩa ở trên.

    Ví dụ:

    Đầu vào:

    3 2
2 3 1
0 1 2
1 2 3

    Đầu ra:

    0
2
5
6

    Đầu vào:

    1 0
5

    Đầu ra:

    0
5

    Đang tải editor...