trang chủ / đề bài / icpcwf13_e

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 f (tính bằng byte) trong một bank và một bit a dùng để chọn bank được truy cập. Nếu a=0 thì bank 0 được truy cập. Nếu a=1 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ó 4 bank, mỗi bank 8 byte. Để truy cập ô nhớ 5, có thể dùng một lệnh duy nhất với a=0 và f=5, hoặc dùng một lệnh đặt BSR bằng 0 rồi một lệnh với a=1 và f=5. 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à ô 20. Chỉ có một cách làm được: thực hiện một lệnh đặt BSR bằng 2 (trừ khi BSR đã có giá trị 2) rồi một lệnh với a=1 và f=4.

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à Vi, trong đó i là một số nguyên dương;
  • một vòng lặp, viết là Rn <ch tr> E, trong đó n 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 n 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 b và s, trong đó b là số bank và s 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 Rn, Vi 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

  • 1≤b≤13, 1≤s≤13.
  • Chương trình có không quá 1000 phần tử.
  • Với mỗi vòng lặp Rn: 1≤n≤106.
  • Trong mỗi vòng lặp Rn <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 Vi: 1≤i≤min(b·s,13).
  • 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á 1012.

Ví dụ

Input Output Giải thích
1 2
V1 V2 V1 V1 V2
5 Chỉ có bank 0 chứa được cả hai biến, mọi lần truy cập dùng a=0: 5 lệnh.
2 1
V1 V2 V1 V1 V2
6 Xếp V1 vào bank 0, V2 vào bank 1: đặt BSR bằng 1 một lần trước lần truy cập V2 đầu tiên, sau đó BSR giữ nguyên. Tổng 5+1=6.
1 2
R10 V1 V2 V1 E
30 Cả hai biến ở bank 0, chương trình truy cập 30 lần.
4 1
V1 R2 V2 V4 R2 V1 E V3 E
17 Chương trình truy cập biến 11 lần. Ví dụ xếp V1 vào bank 0, V2, V3, V4 vào ba bank khác: dãy truy cập ngoài bank 0 là V2 V4 V3 V2 V4 V3, cần đặt BSR 6 lần, tổng 17.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0