Trong phân tích thuật toán, chúng ta đếm các thao tác và bước. Điều này về cơ bản là hợp lý khi máy tính mất nhiều thời gian hơn để thực hiện một hoạt động so với thời gian chúng cần để tìm nạp dữ liệu cần thiết cho hoạt động đó. Ngày nay, chi phí thực hiện một thao tác thấp hơn đáng kể so với chi phí tìm nạp dữ liệu từ bộ nhớ.
Thời gian chạy của nhiều thuật toán bị chi phối bởi số lượng tham chiếu bộ nhớ (số bộ nhớ cache) hơn là số lượng hoạt động. Vì vậy, khi chúng tôi cố gắng mô tả một số thuật toán, chúng tôi phải tập trung vào việc giảm không chỉ số lượng hoạt động mà còn cả số lượng truy cập bộ nhớ. Cũng phải tập trung vào việc thiết kế các thuật toán che giấu độ trễ của bộ nhớ.
Giả sử có một mô hình máy tính đơn giản trong đó bộ nhớ của máy tính bao gồm bộ nhớ đệm L1, bộ nhớ đệm L2 và bộ nhớ chính. Chúng tôi thực hiện một số phép toán Số học và logic bằng ALU trên cư trú dữ liệu trong thanh ghi (R)
Đây là sơ đồ khối của nó -
Từ sơ đồ, chúng ta cũng có thể nhận được một số kiến thức về kích thước của bộ nhớ và bộ nhớ đệm. Bộ nhớ chính về cơ bản là hàng trăm hoặc hàng nghìn MB. Trong đó bộ đệm L2 là một số phần nhỏ MB và bộ đệm L1 là một số KB. Kích thước thanh ghi là một số bit. Khi chúng ta thực thi một chương trình, tất cả dữ liệu trong bộ nhớ. Nếu chúng ta thêm một số thao tác như ADD, thì số đầu tiên sẽ được lưu vào thanh ghi, dữ liệu trong thanh ghi được thêm vào, sau đó kết quả được ghi vào bộ nhớ.
Gọi một chu kỳ là khoảng thời gian cần thêm dữ liệu đã có trong thanh ghi. Thời gian cần thiết để tải dữ liệu từ bộ đệm L1 vào một thanh ghi giả sử là hai chu kỳ trong mô hình này. Nếu dữ liệu được yêu cầu không có trong bộ đệm L1 nhưng có trong bộ đệm L2, chúng tôi nhận được lỗi bộ nhớ cache L1 và dữ liệu cần thiết được đưa từ bộ đệm L2 đến bộ đệm L1 và thanh ghi trong 10 chu kỳ. Khi dữ liệu được yêu cầu của chúng tôi cũng không có trong bộ đệm L2, chúng tôi có lỗi bộ nhớ cache L2 và dữ liệu cần thiết sẽ được đưa từ bộ nhớ chính vào bộ nhớ đệm L2, bộ đệm L1 và thanh ghi trong 100 chu kỳ. Khi đó, thao tác ghi được tính là một chu kỳ ngay cả khi dữ liệu được ghi vào bộ nhớ chính, vì chúng ta không đợi ghi hoàn chỉnh trước khi tiếp tục thao tác tiếp theo