Tách địa chỉ cache thành tag, chỉ số tập và độ lệch

Nếu bạn đọc được con trỏ ở dạng thập lục phân nhưng vẫn thấy sơ đồ cache khó hiểu, hãy bắt đầu với một cấu hình được xác định đầy đủ. Địa chỉ không có sẵn một trường tag dùng chung cho mọi cache. Dung lượng, kích thước dòng, số đường liên kết và quy tắc chọn tập của cache quyết định vai trò của từng bit địa chỉ.

Bài này dùng một mô hình nhỏ có chủ ý: địa chỉ byte rộng 16 bit, dung lượng dữ liệu cache 1.024 byte, mỗi dòng chứa 16 byte và ánh xạ trực tiếp. Mỗi byte được yêu cầu chỉ có đúng một dòng cache có thể chứa nó. Các ví dụ phân loại truy cập đọc bằng Python; chúng không đo bộ xử lý, lấy nội dung bộ nhớ hay dự đoán độ trễ truy cập.

Suy ra các trường từ cấu hình cache

Một địa chỉ byte xác định một byte, nên một dòng 16 byte bao phủ mười sáu địa chỉ liên tiếp. Cần bốn bit để chọn byte trong dòng vì hai mũ bốn bằng mười sáu. Bốn bit thấp này là độ lệch byte, hay byte offset. Chúng không dùng để chọn một trong mười sáu dòng cache.

Lấy dung lượng dữ liệu chia cho kích thước dòng, ta được 1.024 / 16 = 64 dòng. Cache ánh xạ trực tiếp có một dòng trong mỗi tập, nên có sáu mươi tư tập. Cần sáu bit địa chỉ để chọn tập. Sáu bit còn lại nhận diện khối bộ nhớ đang chiếm tập đó. Đây là trường nhãn, hay tag: mười sáu bit địa chỉ trừ bốn bit độ lệch và sáu bit chỉ số tập.

Quy tắc trong ví dụ dùng bốn bit thấp nhất làm độ lệch, sáu bit tiếp theo làm chỉ số tập và sáu bit cao nhất làm tag. Đây là cách chia các trường bit liên tiếp mà ta đã chọn rõ ràng cho mô hình. Trong bài giảng về cache của Chris Terman thuộc Computation Structures, các ví dụ ánh xạ trực tiếp cũng chọn một dòng ứng viên, rồi so sánh tag được lưu và kiểm tra bit hợp lệ. Các kích thước trong bài này khác với những cache minh họa trong bài giảng.

Dung lượng ở đây chỉ tính byte dữ liệu. Nó chưa gồm tag, bit hợp lệ hay phần lưu trữ phục vụ triển khai khác. Ngoài ra, “tag sáu bit” chỉ đúng với không gian địa chỉ mười sáu bit đang xét. Áp dụng độ rộng ấy cho địa chỉ vật lý rộng hơn mà không tính lại sẽ làm mất thông tin cần thiết để phân biệt các khối bộ nhớ.

Tách một địa chỉ rồi ghép lại

Xét địa chỉ byte 0x3A6D, bằng 14.957 ở hệ thập phân. Mười sáu chữ số nhị phân của nó được chia thành 001110 | 100110 | 1101. Các trường lần lượt có giá trị tag mười bốn, chỉ số tập ba mươi tám và độ lệch mười ba. Cache chọn tập ba mươi tám; độ lệch mười ba chọn một byte bên trong khối mười sáu byte đang được yêu cầu.

Xóa các bit độ lệch để tìm địa chỉ đầu khối, được 0x3A60. Byte cuối của khối nằm tại 0x3A6F. Cache không làm tròn yêu cầu đến dòng gần nhất: nó chọn khối đã căn chỉnh chứa địa chỉ đó. Cụ thể, 0x3A6F vẫn thuộc cùng khối, dù nó nằm ngay trước 0x3A70.

Mở ảnh kích thước đầy đủ ↗

Ta cũng có thể ghép các trường để lấy lại địa chỉ ban đầu. Dịch tag sang trái mười bit, dịch chỉ số tập sang trái bốn bit, rồi kết hợp chúng với độ lệch. Các vùng bit này không chồng lấn. Tính bằng số, mười bốn nhân 1.024 cộng ba mươi tám nhân mười sáu cộng mười ba bằng 14.957. Ghép lại địa chỉ là phép kiểm tra hữu ích khi gỡ lỗi: các trường trông có vẻ hợp lý vẫn chưa đủ nếu một bit bị bỏ sót hoặc được gán vào hai trường.

Mã chọn chỉ số tập của gem5 tại phiên bản đã cố định cũng dùng phép dịch và mặt nạ để chọn tập, đồng thời ghép tag với chỉ số tập để khôi phục địa chỉ đầu khối. Lớp cơ sở của chính sách lập chỉ số suy ra số tập từ số dòng và số đường liên kết. Đây là những ví dụ triển khai đã được đọc để đối chiếu; đoạn Python sau không chạy gem5.

Chỉ số tập chọn dòng ứng viên, chưa bảo đảm cache hit

Địa chỉ 0x3E6D lớn hơn 0x3A6D đúng 1.024 byte. Nó có cùng độ lệch và chỉ số tập, nhưng tag bằng mười lăm thay vì mười bốn. Hai khối được yêu cầu cạnh tranh tập ba mươi tám. Tập này chỉ chứa được một trong hai khối, kể cả khi mọi tập khác đều trống.

Cache hit xảy ra khi dòng được chọn chứa dữ liệu hợp lệ và có tag đúng với yêu cầu. Một dòng rỗng có các bit lưu tag tình cờ bằng 0 không được phép đáp ứng nhầm yêu cầu có tag bằng 0. Mô hình dùng None để biểu diễn dòng chưa hợp lệ; bit hợp lệ trong phần cứng thực hiện sự phân biệt tương ứng.

Hãy chạy khối Python 3 dưới đây. Mỗi lần gọi hàm mô phỏng, mọi dòng đều chưa hợp lệ; sau một cache miss, toàn bộ dòng được yêu cầu được nạp ngay. Không có phép ghi, tìm nạp trước, vô hiệu hóa hay yêu cầu đang chờ hoàn tất. Mô hình chỉ lưu tag, nên có thể phân loại truy cập mà không triển khai đường trả về dữ liệu bộ nhớ.

def split(address):
    if type(address) is not int or not 0 <= address < 65536:
        raise ValueError("address must be a built-in 16-bit unsigned integer")
    return address >> 10, (address >> 4) & 63, address & 15


def trace(addresses):
    tags = [None] * 64
    rows = []
    for address in addresses:
        tag, index, offset = split(address)
        hit = tags[index] is not None and tags[index] == tag
        tags[index] = tag
        rows.append((f"{address:04X}", tag, index, offset,
                     "hit" if hit else "miss"))
    return rows


addresses = [0x3A6D, 0x3A6E, 0x3E6D, 0x3A6D, 0x3A70, 0x3A6F]
assert split(0x3A6D) == (14, 38, 13)
assert (14 << 10) | (38 << 4) | 13 == 0x3A6D
rows = trace(addresses)
assert [row[-1] for row in rows] == ["miss", "hit", "miss", "miss", "miss", "hit"]
assert [row[-1] for row in trace([0, 1])] == ["miss", "hit"]
print(*rows, sep="\n")

Yêu cầu đầu tiên nạp tag mười bốn vào tập ba mươi tám. Yêu cầu tiếp theo hit vì 0x3A6E là một byte khác trong cùng khối. Yêu cầu thứ ba thay dòng bằng tag mười lăm, còn yêu cầu thứ tư thay nó trở lại tag mười bốn. Vì vậy, đọc lại một byte vừa được yêu cầu trước đó vẫn có thể miss; việc được truy cập gần đây không tự giữ chỗ cho byte trong cache.

Yêu cầu thứ năm, 0x3A70, chọn tập ba mươi chín và không thay đổi tập ba mươi tám. Do đó, yêu cầu thứ sáu tại 0x3A6F hit. Bốn miss và hai hit chỉ mô tả chính xác sáu yêu cầu đọc byte trong mô hình này. Chúng không xác định số chu kỳ, số nhịp truyền trên bus hay hiệu năng của một luồng lệnh tải trên CPU thật.

Mở ảnh kích thước đầy đủ ↗

Hai khối được truy cập luân phiên chỉ chiếm ba mươi hai byte trong không gian địa chỉ, nhưng vẫn xung đột trong cache 1.024 byte này. So sánh kích thước tập dữ liệu đang dùng với tổng dung lượng cache sẽ bỏ qua ràng buộc về vị trí. Cách ánh xạ chỉ số tập cũng quan trọng như số byte có thể lưu.

Một truy cập nhiều byte có thể chạm hai khối

Giả sử phần mềm cần bốn byte bắt đầu tại 0x3A6E. Các địa chỉ là 0x3A6E, 0x3A6F, 0x3A70 và 0x3A71. Hai byte đầu thuộc khối bắt đầu tại 0x3A60; hai byte sau thuộc khối bắt đầu tại 0x3A70. Chỉ xét địa chỉ bắt đầu sẽ khiến ta bỏ sót khối thứ hai.

Hàm hỗ trợ sau, chạy sau khối mã đầu tiên, trả về địa chỉ đầu của tất cả các khối mà một khoảng byte có độ dài dương đi qua. Nó từ chối khoảng vượt ra ngoài không gian địa chỉ đã khai báo, thay vì âm thầm quay vòng về địa chỉ 0.

def span_blocks(address, count):
    split(address)
    if type(count) is not int or count < 1:
        raise ValueError("count must be a positive built-in integer")
    if address + count > 65536:
        raise ValueError("the byte interval leaves the address space")
    first = address // 16 * 16
    last = (address + count - 1) // 16 * 16
    return tuple(range(first, last + 16, 16))


assert span_blocks(0x3A6E, 4) == (0x3A60, 0x3A70)
assert span_blocks(0x3A60, 16) == (0x3A60,)
assert span_blocks(0x3A60, 17) == (0x3A60, 0x3A70)
assert span_blocks(0xFFFF, 1) == (0xFFF0,)
print([f"{base:04X}" for base in span_blocks(0x3A6E, 4)])

Đây là phép tính trên địa chỉ, không phải bảo đảm của tập lệnh. Một lệnh truy cập bốn byte không căn chỉnh có được hỗ trợ không, nó được tách bên trong bộ xử lý ra sao và có tính nguyên tử không đều cần quy tắc kiến trúc riêng. Thứ tự byte quyết định cách các byte góp phần tạo nên giá trị nhiều byte; nó không thay đổi tập địa chỉ byte nằm trong khoảng này.

Đổi tham số thì phải tính lại các trường

Tag và thông tin hợp lệ cũng tốn chỗ lưu. Sáu mươi tư dòng cần sáu mươi tư nhân bảy bit để lưu tag sáu bit và một bit hợp lệ cho mỗi dòng: 448 bit, tức năm mươi sáu byte. Cộng với 1.024 byte dữ liệu, tổng dung lượng bit trừu tượng là 1.080 byte. Con số này chưa tính sửa lỗi, trạng thái phục vụ chính sách ghi, trạng thái nhất quán cache hay chi phí mạch vật lý; nó không phải ước lượng diện tích chip.

Giữ nguyên dung lượng và kích thước dòng nhưng chuyển sang liên kết hai đường. Vẫn có sáu mươi tư dòng, nay được chia thành ba mươi hai tập, mỗi tập có hai dòng ứng viên. Độ lệch vẫn rộng bốn bit, chỉ số tập giảm còn năm bit và tag tăng lên bảy bit. Giữ nguyên chỉ số sáu bit của cấu hình ánh xạ trực tiếp sẽ mô tả một cache khác. Chọn dòng nào để thay khi có nhiều ứng viên là một chính sách riêng, chưa xuất hiện trong mô hình chỉ có một ứng viên của bài này.

Để luyện tập, hãy duyệt đủ 65.536 địa chỉ rồi kiểm tra rằng tách và ghép lại luôn cho địa chỉ ban đầu. Sau đó đổi kích thước dòng thành ba mươi hai byte, vẫn giữ nguyên dung lượng dữ liệu của cache ánh xạ trực tiếp. Dự đoán độ rộng các trường trước khi sửa mặt nạ: năm bit độ lệch, năm bit chỉ số tập và sáu bit tag. Theo quy tắc ánh xạ đang xét, hai địa chỉ cách nhau 1.024 byte vẫn chọn cùng tập, nhưng mỗi khối được giữ trong cache nay bao phủ gấp đôi số byte lân cận.

Dùng các phép tính này để phân tích một thiết kế cache đã xác định hoặc một chuỗi truy cập có kiểm soát. Trước khi áp dụng cho bộ xử lý cụ thể, hãy xác định cache đó dùng miền địa chỉ nào và quy tắc chọn tập nào. Chỉ riêng con trỏ ảo chưa xác định được tag vật lý; cache dùng hàm lập chỉ số khác cũng không nhất thiết chia địa chỉ thành các trường bit liên tiếp như trong ví dụ.