Kiến trúc Harvard
Đề bài
Mô tả
Thuật ngữ "kiến trúc Harvard" dùng để chỉ một máy tính có bộ nhớ lệnh và bộ nhớ dữ liệu tách rời nhau về mặt vật lý. Thuật ngữ này bắt nguồn từ máy tính Harvard Mark I do IBM bàn giao năm 1944, dùng băng giấy để chứa lệnh và rơ le để chứa dữ liệu. Một số vi điều khiển hiện đại vẫn dùng kiến trúc Harvard, tất nhiên không còn băng giấy và rơ le nữa!
Bộ nhớ dữ liệu được chia thành các bank, mỗi bank chứa cùng một số lượng ô dữ liệu. Mỗi lệnh truy cập dữ liệu có một độ lệch (tính bằng byte) trong một bank và một bit dùng để chọn bank được truy cập. Nếu thì bank được truy cập. Nếu thì giá trị trong thanh ghi chọn bank (BSR) cho biết bank được dùng. Giả sử mọi lệnh đều tốn cùng một lượng thời gian, và có một lệnh để đặt giá trị cho BSR.
Ví dụ, giả sử có bank, mỗi bank byte. Để truy cập ô nhớ , có thể dùng một lệnh duy nhất với và , hoặc dùng một lệnh đặt BSR bằng rồi một lệnh với và . Cách thứ nhất nhanh hơn vì không cần đặt BSR.
Bây giờ giả sử (vẫn với bộ nhớ đó) ô cần truy cập là ô . Chỉ có một cách làm được: thực hiện một lệnh đặt BSR bằng (trừ khi BSR đã có giá trị ) rồi một lệnh với và .
Một chương trình là một dãy các thao tác. Mỗi thao tác là một trong hai loại:
- một lần truy cập biến, viết là
V, trong đó là một số nguyên dương; - một vòng lặp, viết là
R<ch tr>E, trong đó là một số nguyên dương và <ch tr> là một chương trình bất kỳ. Thao tác này tương đương với lần liên tiếp thực hiện <ch tr>.</ch></ch></ch>
Nhiệm vụ của bạn là xác định thời gian chạy nhỏ nhất của chương trình. Cụ thể, cho số lượng và kích thước các bank cùng một chương trình cần thực thi, hãy tìm số lệnh nhỏ nhất (gồm các lệnh truy cập ô nhớ và các lệnh đặt BSR) cần thực thi để chạy xong chương trình. Muốn vậy, bạn cần chọn cách xếp các biến vào các bank sao cho thời gian thực thi nhỏ nhất, và in ra thời gian đó, tức là tổng số lần truy cập bộ nhớ và số lần đặt thanh ghi BSR. Ban đầu giá trị của BSR chưa xác định, và nó chỉ thay đổi khi có một lệnh đặt giá trị cho nó.
Dữ liệu vào
Dòng đầu tiên gồm hai số nguyên và , trong đó là số bank và là số biến có thể chứa trong mỗi bank.
Dòng thứ hai là một chương trình khác rỗng gồm các phần tử cách nhau bởi dấu cách (mỗi R, V và E được tính là một phần tử).
Dữ liệu ra
In ra số lệnh nhỏ nhất cần thực thi để chạy xong chương trình.
Ràng buộc
- , .
- Chương trình có không quá phần tử.
- Với mỗi vòng lặp
R: . - Trong mỗi vòng lặp
R<ch tr>E, thân vòng lặp <ch tr> khác rỗng.</ch></ch> - Với mỗi lần truy cập biến
V: . - Tổng số lần truy cập biến được thực hiện khi chạy chương trình không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 2 V1 V2 V1 V1 V2 |
5 | Chỉ có bank chứa được cả hai biến, mọi lần truy cập dùng : lệnh. |
| 2 1 V1 V2 V1 V1 V2 |
6 | Xếp V1 vào bank , V2 vào bank : đặt BSR bằng một lần trước lần truy cập V2 đầu tiên, sau đó BSR giữ nguyên. Tổng . |
| 1 2 R10 V1 V2 V1 E |
30 | Cả hai biến ở bank , chương trình truy cập lần. |
| 4 1 V1 R2 V2 V4 R2 V1 E V3 E |
17 | Chương trình truy cập biến lần. Ví dụ xếp V1 vào bank , V2, V3, V4 vào ba bank khác: dãy truy cập ngoài bank là V2 V4 V3 V2 V4 V3, cần đặt BSR lần, tổng . |
Bình luận