Theo dõi phép ghi qua cache write-through và write-back

Khi bạn theo dõi một phép ghi đi qua cache, hãy xét khi nào byte đã thay đổi được ghi xuống bộ nhớ cấp dưới. Câu trả lời phụ thuộc chính sách ghi. Một câu hỏi riêng là liệu phép ghi bị cache miss có nên nạp một dòng vào cache hay không. Gộp hai quyết định này khiến diễn tiến ghi khó giải thích và có thể che khuất thời điểm bản sao mới nhất của giá trị vẫn chỉ nằm trong một dòng dirty.

Bài này dùng một cache ánh xạ trực tiếp xử lý tuần tự, gồm bốn dòng tám byte, nối với bộ nhớ cấp dưới có sáu mươi tư byte. Địa chỉ nằm từ 0 đến sáu mươi ba; giá trị lưu là byte không dấu. Ban đầu, mỗi byte ở bộ nhớ cấp dưới chứa chính giá trị địa chỉ của nó. Ta sẽ chạy mô hình dữ liệu nhỏ bằng Python, không đo CPU hay thực thi lệnh bảo trì cache của phần cứng. Bạn cần biết khái niệm dòng cache và phép chia nguyên để theo dõi cách tính chỉ số.

Phân biệt truyền dữ liệu và cấp phát dòng

Với write-through, hay ghi xuyên, một phép ghi vào dòng đang có trong cache cập nhật dòng đó và gửi byte vừa thay đổi xuống bộ nhớ cấp dưới. Mô hình hoàn thành việc truyền byte ngay lập tức. Triển khai thật có thể dùng bộ đệm ghi, nên chỉ tên chính sách chưa xác định được lúc một bên quan sát khác thấy giá trị mới hay số giao dịch trên bus.

Với write-back, hay ghi trả, phép ghi vào dòng đang có cập nhật byte trong cache và đánh dấu dòng là dirty, tức cần được ghi trả. Bộ nhớ cấp dưới có thể vẫn giữ giá trị trước đó. Trước khi thay một dòng dirty, mô hình chép trả toàn bộ tám byte của dòng. Dòng sạch có thể bị thay mà không cần ghi trả dữ liệu. Bit dirty cho biết cần ghi trả; nó không nhất thiết chứng minh mọi byte đều khác bộ nhớ cấp dưới.

Bài giảng cache của Chris Terman giải thích vai trò của trạng thái dirty trong việc tránh ghi trả không cần thiết. Mã cache của gem5 tại phiên bản đã cố định cũng phân biệt ghi trả dòng dirty với loại bỏ dòng sạch. Mã đó có chi tiết nhất quán và cấu hình không nằm trong mô hình này, nên ta không suy ra lưu lượng thật chỉ từ tên hàm.

Cấp phát dòng trả lời câu hỏi về write miss. Khi bật write allocation, một miss nạp toàn bộ dòng chứa địa chỉ trước khi sửa byte được yêu cầu. Khi không cấp phát lúc ghi trượt, mô hình ghi byte thẳng xuống bộ nhớ cấp dưới và giữ nguyên nội dung cache. Cụ thể, một write miss có cùng chỉ số tập không loại dòng khác đang ở đó chỉ để thực hiện phép ghi bỏ qua cache.

Hai quyết định này có thể được xác định độc lập. Tài liệu thư viện Dinero IV cũ, tệp d4.3 trong gói tài liệu nguồn chính thức, cung cấp hai chính sách riêng wallocf và wbackf. Ta sẽ triển khai rõ bốn tổ hợp. Điều này không khẳng định bộ xử lý cụ thể hỗ trợ cả bốn hay mô hình Python đang chạy Dinero IV.

Theo dõi giá trị dirty qua hai lần xung đột

Dùng năm thao tác: ghi chín vào địa chỉ một, đọc địa chỉ một, ghi mười vào địa chỉ một, ghi bảy vào địa chỉ ba mươi ba, rồi đọc địa chỉ một. Địa chỉ một và ba mươi ba thuộc các khối bắt đầu tại 0 và ba mươi hai. Cả hai khối chọn chỉ số cache 0 vì số hiệu khối là 0 và bốn trong cache ánh xạ trực tiếp có bốn dòng.

Với write-back và cấp phát khi ghi trượt, phép ghi đầu miss, nạp các byte từ 0 đến bảy rồi đổi byte một trong cache thành chín. Byte một ở bộ nhớ cấp dưới vẫn bằng một. Phép đọc hit và trả về chín. Phép ghi thứ hai hit, đổi giá trị trong cache thành mười và giữ dòng đó ở trạng thái dirty. Cả hai phép ghi vẫn chưa ghi byte nào xuống cấp dưới.

Phép ghi tại địa chỉ ba mươi ba bị miss. Trước khi nạp khối mới, cache ghi trả khối dirty cũ, nên byte một ở cấp dưới trở thành mười. Sau đó nó nạp các byte từ ba mươi hai đến ba mươi chín và đổi byte ba mươi ba trong cache thành bảy. Khối thứ hai này ở trạng thái dirty, còn byte ba mươi ba ở cấp dưới vẫn chứa ba mươi ba.

Phép đọc cuối tại địa chỉ một lại miss. Nó ghi trả khối thứ hai đang dirty, rồi nạp khối thứ nhất và trả về mười. Byte ba mươi ba ở cấp dưới lúc này đã bằng bảy. Chuỗi thao tác cần ba lần nạp tám byte và hai lần ghi trả tám byte: đọc hai mươi tư byte từ bộ nhớ cấp dưới và ghi mười sáu byte xuống đó.

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

Chạy cả giá trị byte lẫn quyết định hit

Mô hình chỉ có tag không thể xác lập rằng giá trị dirty được giữ đúng khi dòng bị thay. Mô hình Python 3 này lưu byte thật và đếm số byte dữ liệu đi qua ranh giới duy nhất giữa cache với bộ nhớ. Phép đọc luôn cấp phát dòng. flush ghi trả các dòng dirty và đánh dấu chúng sạch nhưng vẫn hợp lệ; nó không vô hiệu hóa cache hay mô phỏng lưu trữ bền vững.

class ByteCache:
    def __init__(self, writeback, allocate):
        if type(writeback) is not bool or type(allocate) is not bool:
            raise ValueError("policy switches must be booleans")
        self.writeback, self.allocate = writeback, allocate
        self.memory = list(range(64))
        self.lines = {}
        self.read_bytes = self.write_bytes = 0

    def _copy_back(self, index):
        line = self.lines.get(index)
        if line is not None and line["dirty"]:
            base = line["base"]
            self.memory[base:base + 8] = line["data"]
            self.write_bytes += 8
            line["dirty"] = False

    def access(self, operation, address, value=None):
        if operation not in ("R", "W"):
            raise ValueError("operation must be R or W")
        if type(address) is not int or not 0 <= address < 64:
            raise ValueError("address must be a built-in integer from 0 to 63")
        if operation == "W":
            if type(value) is not int or not 0 <= value < 256:
                raise ValueError("a write requires an unsigned byte")
        elif value is not None:
            raise ValueError("a read takes no value")
        base = address // 8 * 8
        index = (address // 8) % 4
        line = self.lines.get(index)
        hit = line is not None and line["base"] == base
        if not hit:
            if operation == "W" and not self.allocate:
                self.memory[address] = value
                self.write_bytes += 1
                return False, None
            self._copy_back(index)
            line = {"base": base, "data": self.memory[base:base + 8],
                    "dirty": False}
            self.lines[index] = line
            self.read_bytes += 8
        offset = address - base
        if operation == "R":
            return hit, line["data"][offset]
        line["data"][offset] = value
        if self.writeback:
            line["dirty"] = True
        else:
            self.memory[address] = value
            self.write_bytes += 1
        return hit, None

    def flush(self):
        for index in self.lines:
            self._copy_back(index)


events = [("W", 1, 9), ("R", 1), ("W", 1, 10),
          ("W", 33, 7), ("R", 1)]
for writeback in (False, True):
    for allocate in (False, True):
        cache = ByteCache(writeback, allocate)
        answers = [cache.access(*event) for event in events]
        assert [value for _, value in answers if value is not None] == [9, 10]
        cache.flush()
        assert cache.memory[1] == 10 and cache.memory[33] == 7
        print(writeback, allocate, cache.read_bytes, cache.write_bytes)

Theo thứ tự được in, tổng byte đọc/ghi lần lượt là tám/ba, hai mươi tư/ba, tám/mười và hai mươi tư/mười sáu. Cả bốn chính sách trả về cùng hai giá trị đọc và kết thúc với cùng nội dung bộ nhớ sau khi ghi trả. Giá trị trung gian ở bộ nhớ cấp dưới và lưu lượng truyền thì khác nhau.

Cần giữ sự phân biệt giữa làm sạch và loại bỏ dòng cả khi đọc mã nguồn. Trong mã lớp cache cơ sở của gem5 tại phiên bản đã cố định, hàm duyệt để ghi trả chép dữ liệu dirty rồi xóa trạng thái dirty; hàm duyệt để vô hiệu hóa là hàm riêng và cảnh báo về dòng dirty. flush trong bài là thao tác mô hình có định nghĩa chính xác, không phải tên gọi dùng chung cho một trong hai thao tác phần cứng thật.

Ghi bỏ qua cache không nhất thiết đụng tới dòng dirty khác

Khi không cấp phát dòng lúc ghi trượt, phép ghi đầu ghi chín thẳng vào byte một ở bộ nhớ cấp dưới. Phép đọc tiếp theo miss và nạp khối đó. Với write-back, phép ghi kế tiếp đổi byte một trong cache thành mười, để byte một ở cấp dưới vẫn bằng chín.

Phép ghi tại ba mươi ba lúc này bỏ qua cache. Nó ghi bảy trực tiếp vào bộ nhớ mà không thay khối dirty ở chỉ số 0. Vì vậy, phép đọc địa chỉ một cuối cùng hit và trả về mười. Chỉ thao tác flush ở cuối mới chép trả dòng đó, làm byte một ở cấp dưới bằng mười. Lưu lượng gồm một lần nạp tám byte, hai phép ghi byte bỏ qua cache và một lần ghi trả tám byte: đọc tám byte, ghi mười byte.

Với write-through không cấp phát khi ghi trượt, cache có cùng quyết định bố trí nhưng còn ghi xuyên cả phép ghi đã hit. Nó không có dòng dirty cần flush, nên tổng cộng ba phép ghi truyền ba byte dữ liệu. Cần phân biệt tác động của các quy tắc bỏ qua cache khác: loại dòng đang giữ sẽ khiến phép đọc cuối miss; làm sạch dòng dirty sẽ đổi thời điểm các byte của nó đến bộ nhớ cấp dưới mà không nhất thiết đổi kết quả hit của phép đọc đó.

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

Đếm đủ khoảng thao tác trước khi đánh giá đánh đổi

Write-back gửi nhiều byte hơn write-through trong ví dụ nhỏ này vì mỗi lần loại dòng dirty truyền tám byte sau chỉ vài phép ghi byte. Điều đó không khiến write-through luôn rẻ hơn. Nhiều phép ghi vào cùng khối đang có có thể được gộp thành một lần ghi trả sau đó; ngược lại, việc đệm và gộp các phép ghi trong triển khai write-through cũng quan trọng trên hệ thống thật.

Sau khi định nghĩa lớp, hãy thử bài tập dưới đây. Đọc địa chỉ một một lần để nạp khối chứa nó, rồi ghi đè một trăm lần và flush. Cả hai chính sách kết thúc với giá trị chín mươi chín. Theo quy tắc truyền đã khai báo, write-through gửi một trăm byte, còn write-back gửi tám byte. Cả hai đều đọc tám byte trong lần nạp đầu.

for writeback in (False, True):
    cache = ByteCache(writeback, True)
    cache.access("R", 1)
    for value in range(100):
        cache.access("W", 1, value)
    cache.flush()
    assert cache.memory[1] == 99
    assert cache.read_bytes == 8
    assert cache.write_bytes == (8 if writeback else 100)
    print(writeback, cache.write_bytes)

Kết thúc khoảng đo trước khi dữ liệu dirty được ghi trả sẽ bỏ sót công việc bị hoãn lại. Tương tự, coi mỗi byte dữ liệu là một giao dịch bus vật lý sẽ thêm giả định mà mô hình chưa nêu. Truyền dữ liệu thật có độ rộng, hàng đợi và khả năng gộp; tổng byte ở đây không xác lập thời gian chạy hay mức tiêu thụ điện.

Cuối cùng, dirty không có nghĩa không hợp lệ. Trong mô hình chỉ có một bên yêu cầu này, bản sao dirty trong cache là giá trị hiện tại. Loại bản sao đó trước khi ghi trả có thể làm mất kết quả ghi; đọc trực tiếp bộ nhớ cấp dưới lại có thể thấy giá trị cũ. Nhiều bộ xử lý, DMA, nhất quán cache, thứ tự bộ nhớ và tính bền vững đưa thêm các hợp đồng khác vào bài toán. Bài tập tách riêng truyền dữ liệu với cấp phát dòng để các câu hỏi sau đó bắt đầu từ trạng thái rõ ràng, thay vì một tên chính sách dễ gây nhầm.