Bộ nhớ đệm (còn gọi là bộ nhớ cache, bộ nhớ đệm cao tốc, bộ nhớ ẩn; tiếng Anh cache memory, cache) là một bộ nhớ RAM có dung lượng nhỏ, tốc độ cao được sử dụng kết hợp với một bộ nhớ RAM dung lượng lớn hơn và tốc độ thấp hơn để tạo nên một bộ nhớ có dung lượng bằng dung lượng của bộ nhớ lớn hơn nhưng hoạt động với tốc độ của bộ nhớ có tốc độ cao hơn.

Lịch sử phát triển

Trong của máy tính, bộ xử lý luôn có tốc độ cao hơn bộ nhớ chính, khi bộ nhớ chính được cải tiến để nâng cao tốc độ thì bộ xử lý cũng được cải tiến, đạt được tốc độ lớn hơn (xt. thế hệ máy tính). Vấn đề này không phải là do có khó khăn về công nghệ chế tạo bộ nhớ chính mà vì lý do kinh tế, các bộ nhớ tốc độ cao có giá thành cao, làm giảm khả năng cạnh tranh của sản phẩm.

Tính cục bộ của các chương trình

Khi phân tích hoạt động của các chương trình, người ta thấy rằng: tại mỗi thời điểm các chương trình chỉ truy cập (đọc/ghi) một phần tương đối nhỏ trong miền địa chỉ bộ nhớ của nó. Tính chất cục bộ có hai kiểu khác nhau:

• Cục bộ về thời gian: nếu một phần tử nào đó của chương trình được truy cập thì không lâu sau nó dễ được truy cập lại.
• Cục bộ về không gian: Nếu một phần tử nào đó của chương trình được truy cập thì sau đó các phần tử nằm gần phần tử đó dễ được truy cập.

Thí dụ về tính cục bộ của chương trình:

• Hầu hết các chương trình đều chứa vòng lặp, vì vậy các chỉ thị trong vòng lặp và dữ liệu mà chúng sử dụng rất có thể được truy cập lặp đi lặp lại, thể hiện tính cục bộ về thời gian ở mức độ cao.
• Các chỉ thị trong chương trình thường được truy cập tuần tự - thể hiện tính cục bộ về không gian ở mức độ cao. Việc truy cập dữ liệu cũng thể hiện tính cục bộ về không gian một cách rất tự nhiên, chẳng hạn khi chúng ta truy cập một phần tử của mảng hay một bản ghi (record) thì sau đó thường sẽ truy cập phần tử mảng hay bản ghi lân cận.

Ý tưởng về bộ nhớ đệm

Dựa trên đặc tính cục bộ của các chương trỉnh, khi bộ xử lý cần truy cập một từ (xt. từ máy tính), từ đó sẽ được bộ xử lý chuyển từ bộ nhớ lớn tốc độ thấp (bộ nhớ chính - main memory) về bộ nhớ nhỏ tốc độ cao (bộ nhớ đệm), để lần sau nếu cần đến từ đó thì bộ xử lý có thể truy cập nhanh hơn. Nếu một từ được đọc hoặc ghi k lần trong một khoảng thời gian ngắn thì bộ xử lý chỉ cần truy cập bộ nhớ lớn tốc độ thấp một lần và truy cập bộ nhớ nhỏ tốc độ cao k-1 lần. Số k càng lớn thì hiệu quả của bộ nhớ đệm càng cao.

Tốc độ truy cập

Chúng ta có thể xây dựng công thức tính thời gian truy cập trung bình của bộ nhớ đệm bằng cách đưa ra một số ký hiệu: c - là thời gian truy cập bộ nhớ đệm, m - là thời gian truy cập bộ nhớ chính, h - là tỉ số tìm thấy (hit ratio), là tỉ số của tổng số lần truy cập được thoả mãn từ bộ nhớ đệm trên số lần truy cập bộ nhớ. Trong ví dụ chúng ta vừa dẫn ra ở phần trên, h = (k-1)/k. Cũng có những tác giả định nghĩa tỉ số không tìm thấy (miss ratio), đó là 1-h.

Với các ký hiệu như trên, chúng ta có thể tính được thời gian truy cập bộ nhớ trung bình (mean access time) bằng c + (1-h)m. Khi h tiến tới 1, nghĩa là mọi sự truy cập bộ nhớ có thể được thoả mãn nhờ bộ nhớ đệm, thời gian truy cập trung bình tiến tới c. Trường hợp này bộ nhớ đệm đem lại hiệu quả cao nhất về tốc độ truy cập bộ nhớ trung bình. Khi h tiến tới 0, nghĩa là luôn không tìm thấy từ cần tìm trong bộ nhớ đệm, do đó phải truy cập bộ nhớ chính, vì vậy thời gian truy cập trung bình tiến tới c+m. Trường hợp này bộ nhớ đệm đem lại hiệu quả thấp nhất về tốc độ truy cập bộ nhớ trung bình, hệ thống máy tính có bộ nhớ đệm sẽ chạy chậm hơn so với trường hợp không có bộ nhớ đệm.

Trong một số hệ thống, việc truy cập bộ nhớ chính được bắt đầu song song với việc tìm kiếm trong bộ nhớ đệm, vì thế nếu không thấy trong bộ nhớ đệm thì việc tìm kiếm trong bộ nhớ chính đã được bắt đầu rồi. Chiến lược này đòi hỏi phải dừng ngay lại việc tìm kiếm trong bộ nhớ chính khi tìm thấy trong bộ nhớ đệm. Thuật toán cơ bản để tìm kiếm trong bộ nhớ đệm và để bắt đầu hoặc dừng việc truy cập bộ nhớ tuỳ thuộc vào kết quả của sự tìm kiếm trong bộ nhớ đệm được thực hiện bằng vi chương trình.

Phân loại

Một kiến trúc bộ nhớ đệm nhiều mức: L1, L2, L3, L4.

Bộ nhớ đệm có thể được phân loại theo phương pháp tổ chức:

• Bộ nhớ đệm kiểu liên kết (associative cache): bao gồm một số đơn vị được gọi là khe, dòng hay đề mục (slot, line, entry), mỗi dòng giống như một bản ghi (record) có ba trường. Trường value chứa nội dung một khối nhớ được mang về từ bộ nhớ chính, trường block number chứa số hiệu khối nhớ tương ứng và trường valid kích thước một bit cho biết rằng hiện thời slot đó có được sử dụng hay không. Chính việc sử dụng trường block number như trên dẫn đến tên gọi bộ nhớ đệm kiểu liên kết.
• Bộ nhớ đệm kiểu ánh xạ trực tiếp (direct-mapped cache): nội dung mỗi khối nhớ mang về từ bộ nhớ chính được đặt vào một khe mà số thứ tự của khe có thể tính được dễ dàng từ số thứ tự khối nhớ. Loại bộ nhớ đệm này tránh được việc tìm kiếm như ở bộ nhớ đệm kiểu liên kết, dẫn đến giá thành rẻ hơn.
• Bộ nhớ đệm kiểu liên kết thành bộ (set associative cache): là loại bộ nhớ đệm được tổ chức theo kiểu lai giữa hai loại trên.

Mỗi loại bộ nhớ đệm kể trên đều có ưu và nhược điểm, người thiết kế máy tính sẽ căn cứ vào giá thành của máy tính cũng như đặc điểm cục bộ và một số đặc điểm khác của các chương trình dự kiến sẽ chạy trên máy để quyết định lựa chọn loại bộ nhớ đệm.

Bộ nhớ đệm cũng có thể được phân loại theo mức (level). Việc áp dụng ý tưởng về nhớ đệm vào tổ chức bộ nhớ của máy tính đem lại hiệu quả rất lớn, đến mức các tất cả các máy tính ngày nay đều có áp dụng phương pháp nhớ đệm với số bộ nhớ đệm nằm giữa bộ xử lý và bộ nhớ chính từ một đến ba. Nếu giữa CPU và bộ nhớ chính có hai hoặc ba bộ nhớ đệm, thì bộ nhớ đệm nằm gần CPU nhất được gọi là bộ nhớ đệm mức 1, cg. bộ nhớ đệm L1 (L1 cache), bộ nhớ đệm kế tiếp là L2 (L2 cache), sau đó nếu có thì là L3 (L3 cache). Nếu chỉ có một bộ nhớ đệm nằm giữa CPU và bộ nhớ chính thì nó được gọi là bộ nhớ đệm một mức (single cache).

Tốc độ hoạt động của bộ nhớ đệm L1 phải bằng hoặc gần bằng tốc độ hoạt động của bộ xử lý, nhưng cao hơn các bộ nhớ đệm khác; dung lượng của nó thường là nhỏ nhất trong các bộ nhớ đệm. Tốc độ hoạt động của bộ nhớ đệm L2 thấp hơn tốc độ hoạt động của bộ nhớ đệm L1, nhưng cao hơn tốc độ hoạt động của bộ nhớ đệm L3; dung lượng của nó lớn hơn dung lượng của bộ nhớ đệm L1 nhưng nhỏ hơn dung lượng của bộ nhớ đệm L3. Với bộ nhớ đệm L3, chênh lệch về tốc độ và dung lượng của nó so với bộ nhớ đệm L2 và bộ nhớ chính cũng tương tự như trên. Việc so sánh tốc độ và dung lượng bộ nhớ cache ở các mức khác nhau bên trên chỉ là tương đối. Những người nghiên cứu thiết kế bộ nhớ cache cần tính toán định lượng để nắm được chính xác mức độ chênh lệch cần có để máy tính hoạt động với hiệu năng cao nhất và giá của bộ nhớ đệm.

Việc áp dụng ý tưởng về bộ nhớ đệm không dừng lại ở ba mức như trên: trong một số máy tính số mức có thể nhiều hơn; bộ nhớ ảo cũng là theo ý tưởng này.

Một số chủ đề nghiên cứu

• Tỉ lệ giá/hiệu suất (cost/performance): những người nghiên cứu thiết kế bộ nhớ đệm cho máy tính ngoài mục tiêu là đạt được tốc độ truy cập bộ nhớ trung bình càng cao càng tốt, họ còn có một mục tiêu quan trọng nữa là xác định được với mỗi tốc độ trung bình đạt được thì chi phí cả phần cứng và phần mềm là bao nhiêu.

• Kích thước bộ nhớ đệm: dựa vào việc phân tích tính cục bộ của các chương trình đã và sẽ chạy trên máy tính, người nghiên cứu thiết kế bộ nhớ đệm sẽ quyết định chọn kích thước bộ nhớ đệm bằng bao nhiêu để đạt được giá trị h (và thời gian truy cập trung bình) mong muốn.

Tài liệu tham khảo

• A. S. Tannenbaum, Structured Computer Organization, 6th Edition, Pearson, 2013. ISBN 10: 0-13-291652-5, ISBN 13: 978-0-13-291652-3.
• Microsoft Computer Dictionary, Fifth Edition, Microsoft Press, 2002. ISBN 0-7356-1495-4.
• William Stallings, Computer Organization and Architecture: Design for Performance, 9th Edition, Pearson, 2013. ISBN 10: 0-13-293633-X, ISBN 13: 978-0-13-293633-0.