TAOCP 1.3.1 Exercise 25

Bài toán không yêu cầu chứng minh một mệnh đề duy nhất, mà yêu cầu đề xuất các mở rộng cho MIX sao cho mọi chương trình được viết đúng theo tinh thần của Mục 1.

taocpmathematicsalgorithmsvolume-1hard

Section 1.3.1: Description of MIX

Exercise 25. [30] Suppose that the manufacturer of MIX wishes to come out with a more powerful computer ("Mixmaster"?), and he wants to convince as many as possible of those people now owning a MIX computer to invest in the more expensive machine. He wants to design this new hardware to be an extension of MIX, in the sense that all programs correctly written for MIX will work on the new machines without change. Suggest desirable things that could be incorporated in this extension. (For example, can you make better use of the I-field of an instruction?)

Verified: yes
Solve time: 1m30s

Setup

Bài toán không yêu cầu chứng minh một mệnh đề duy nhất, mà yêu cầu đề xuất các mở rộng cho MIX sao cho mọi chương trình được viết đúng theo tinh thần của Mục 1.3.1 vẫn chạy chính xác mà không cần sửa đổi. Do đó cần xác định các thay đổi phần cứng thỏa mãn điều kiện tương thích ngược:

  1. Mọi lệnh MIX hiện hành vẫn giữ nguyên ý nghĩa.
  2. Mọi chương trình chỉ giả thiết các tính chất được nêu trong Mục 1.3.1 vẫn cho cùng kết quả.
  3. Các khả năng mới phải làm tăng sức mạnh hoặc hiệu quả của máy.

Solution

Một mở rộng tự nhiên là tăng kích thước bộ nhớ. Theo Mục 1.3.1, chương trình MIX chỉ được phép giả thiết rằng các địa chỉ hợp lệ nằm trong khoảng từ $0$ đến $3999$. Nếu máy mới có nhiều hơn $4000$ ô nhớ nhưng vẫn giữ nguyên các địa chỉ cũ, mọi chương trình MIX vẫn hoạt động chính xác trên phần đầu của bộ nhớ. Các chương trình mới có thể khai thác vùng nhớ bổ sung bằng các cơ chế địa chỉ hóa mở rộng.

Việc tăng số lượng thanh ghi chỉ số cũng tương thích hoàn toàn. MIX hiện có sáu thanh ghi chỉ số $rI1,\ldots,rI6$, và trường $I$ của lệnh chỉ sử dụng các giá trị từ $0$ đến $6$. Một máy mở rộng có thể diễn giải các giá trị còn lại của byte $I$ như các thanh ghi chỉ số mới. Vì các chương trình MIX hợp lệ không bao giờ sử dụng các giá trị này, ý nghĩa của mọi lệnh cũ được bảo toàn.

Có thể tận dụng trường $I$ mạnh hơn bằng cách cho phép các giá trị mới biểu diễn những chế độ địa chỉ hóa khác. Chẳng hạn:

  • Một giá trị của $I$ có thể chỉ định địa chỉ gián tiếp.
  • Một giá trị khác có thể chỉ định cộng nhiều thanh ghi chỉ số.
  • Một giá trị khác nữa có thể chỉ định địa chỉ tương đối theo bộ đếm lệnh.

Các giá trị $I=0,1,\ldots,6$ phải giữ nguyên ý nghĩa hiện tại. Khi đó mọi chương trình MIX cũ vẫn thực hiện đúng như trước.

Một mở rộng quan trọng khác là tăng kích thước thanh ghi tích lũy và thanh ghi mở rộng. Giả sử máy mới dùng các thanh ghi dài hơn năm byte nhưng mọi lệnh MIX chuẩn chỉ tác động lên năm byte thấp theo đúng quy tắc cũ. Các bit hoặc byte bổ sung có thể được dùng bởi những lệnh mới. Do các chương trình MIX chỉ dựa trên năm byte được định nghĩa trong Mục 1.3.1, tính tương thích được duy trì.

Có thể bổ sung các lệnh số học mới, chẳng hạn:

  • Nhân và chia nhanh hơn.
  • Dịch vòng.
  • Thao tác trên nhiều từ liên tiếp.
  • So sánh và chuyển dữ liệu theo khối.

Các mã thao tác mới phải sử dụng các giá trị $C$ chưa được gán cho MIX chuẩn. Khi đó không có lệnh cũ nào bị thay đổi ý nghĩa.

Một cải tiến đặc biệt hữu ích là hỗ trợ ngắt vào-ra. MIX hiện xem các thiết bị vào-ra như những đơn vị hoạt động bên ngoài bộ xử lý. Máy mới có thể cho phép chương trình tiếp tục tính toán trong khi thiết bị truyền dữ liệu, rồi sinh ngắt khi thao tác hoàn thành. Nếu chế độ ngắt mặc định bị vô hiệu hóa, hành vi của mọi chương trình MIX hiện có sẽ không thay đổi.

Tăng kích thước byte cũng tương thích với triết lý của MIX. Mục 1.3.1 yêu cầu mọi chương trình hợp lệ phải hoạt động với bất kỳ kích thước byte nào có ít nhất $64$ và nhiều nhất $100$ giá trị. Vì thế một máy mới có thể chọn bất kỳ kích thước byte nào trong khoảng này mà không ảnh hưởng đến các chương trình được viết đúng quy tắc.

Cuối cùng, có thể bổ sung các thanh ghi chuyên dụng mới, ví dụ:

  • Bộ đếm vòng lặp.
  • Thanh ghi cơ sở địa chỉ.
  • Thanh ghi dấu thời gian hoặc đồng hồ.

Các thanh ghi này chỉ được truy cập bằng các lệnh mới; do đó chúng không làm thay đổi trạng thái được sử dụng bởi các chương trình MIX hiện hành.

Verification

Mỗi đề xuất ở trên đều thỏa mãn cùng một tiêu chuẩn.

Ý nghĩa của mọi mã thao tác hiện có được giữ nguyên.

Các giá trị của trường $I$ từ $0$ đến $6$ tiếp tục thực hiện đúng quy tắc địa chỉ hóa đã được định nghĩa trong Mục 1.3.1.

Các địa chỉ từ $0$ đến $3999$ tiếp tục tham chiếu đúng các ô nhớ cũ.

Mọi khả năng mới chỉ xuất hiện thông qua các mã thao tác, giá trị trường $I$, thanh ghi, hoặc vùng nhớ mà các chương trình MIX hợp lệ không sử dụng.

Do đó mọi chương trình được viết đúng theo các quy tắc của MIX sẽ cho kết quả giống hệt trên máy mở rộng, trong khi các chương trình mới có thể khai thác phần cứng mạnh hơn.

Notes

Việc khai thác các giá trị chưa dùng của trường $I$ là mở rộng hấp dẫn nhất. Trường này chiếm trọn một byte nhưng MIX chuẩn chỉ dùng bảy giá trị. Vì một byte chứa ít nhất $64$ giá trị, còn ít nhất $57$ giá trị chưa được sử dụng. Các giá trị đó có thể cung cấp nhiều chế độ địa chỉ hóa mới mà không ảnh hưởng đến bất kỳ chương trình MIX hiện có nào.