下面介紹cache的組織和結構。一個cache隻是可用存儲空間的一小部分。那麼什麼樣的資料可以進入cache？資料會放在什麼位置？相比于主存儲器，cache存儲系統的設計以及與計算機系統的內建都要更困難。部分是因為cache速度快，部分是因為其複雜性高。事實上，直到20世紀80年代，隻能在小型機和大型機上見到cache。直到20世紀80年代後期，随着68020/30以及80386/486微處理器的出現，cache才開始在個人計算機中出現。今天，已經可以将超過10億個半導體內建在晶片中，這樣可以確定所有高性能處理器都包含一個大容量的片内cache。
cache設計的根本問題是如何建構一個存儲體來存放來自大容量主存儲器任意位置的一組資料元素。解決該映射問題的方法很多，但實際cache系統通常使用組相聯（set associative）方式進行組織。下面首先介紹兩個cache結構執行個體，以便讀者了解組相聯cache的操作。
在設計任何一種存儲系統時需要問的第一個問題是，基本資料單元的大小是多少？主存儲器處理機關資料的大小與機器的基本字長相同。例如，具有64位寄存器的64位機器采用64位存儲器。如果計算機需要少于一個字的資料，它首先讀取整個字，然後再忽略它不想要的位。
雖然計算機可以從cache中讀取一個字，但該字的大小并不是cache基本存儲單元的大小。cache基本存儲單元為包含幾個連續字的塊（line）。假定cache是按照字的粒度（granularity）來組織的。當通路某條指令時，如果它不在cache中，則必須從主存儲器中讀取。然而，下一條指令又有可能會失效。是以需要比一個字大的cache基本存儲單元。
cache塊（cache line）由一系列連續的字構成，這樣從cache中可以連續讀出幾條指令進而不會發生失效。當發生失效時，包含該字的整個cache塊将從主存調入cache。cache塊大小的最優值取決于cache的總容量、代碼的屬性以及采用的資料結構。
人們希望cache對存放在其中的資料不加限制；即cache中的資料可以來自主存的任何地方。這種cache使用相聯存儲器把資料存放在其中的任意位置，此時是根據其值（value）而不是根據其位址/位置（address/location）來通路資料。
圖1-7說明了相聯存儲器的概念。每個資料項有兩個值，關鍵字（key）以及資料元素；例如，最上面一行包含關鍵字52b1和資料f0000。此時，資料沒有排序，一個資料項可以儲存在存儲器的任意位置。通路關鍵字是檢索資料的主要手段。通路相聯存儲器時需要将關鍵字輸入存儲器，然後将此關鍵字與存儲器中所有關鍵字進行并行比對。如果發現了該關鍵字，該資料就被檢索到了（即與關鍵字關聯的資料）。例如，計算機向圖1-7中的系統輸入關鍵字f001。該關鍵字将同時交給存儲器中的所有位置進行比較。由于給定f001會發生比對（即命中），存儲器将給出一個命中響應信号，同時将數值42220在資料端口輸出。
相聯cache的工作原理看上去與圖1-7中的機制相似，用關鍵字作為處理器通路的位址，資料就存放在該位址處。傳統存儲器與相聯存儲器的差別在于，傳統存儲器包含以0,1,2，…編号連續存儲的元素，而相聯存儲器包含的元素并沒有排序或者按順序存放。
下面詳細讨論全相聯cache的部分細節。圖1-8所示的相聯存儲器允許cache中的任意一塊都可以存放來自主存儲器的任意一塊資料。此例中，存儲器被劃分成包含兩個字的塊（每塊兩個字是為了簡單起見，實際的cache可能每塊含有8個或更多的字）。
相聯cache的大小可以任意，cache中塊的數量與主存儲器中塊的數量之間沒有關系。考慮主存儲器為16mb，相聯映射存儲器為64kb。如果一塊包含4個32位的字（即塊大小為16位元組），則主存儲器由224/16 = 1m個塊構成，而cache包含216/16 = 4096個塊。
相聯cache允許主存儲器的任意一塊資料存放在其任意一塊中。上例中，相聯cache的第i塊可以存放來自主存儲器中1m塊中的任何一個。是以，cache中第i塊需要一個标志（tag）來唯一辨別其與主存儲器中的某一塊相關聯。由于在該例中，主存儲器有1m塊，是以标志應該為20位來代表220個塊。
當處理器産生一個位址時，将使用塊内位址來定位主存儲器或者cache中一個字的位置（上例中，塊内位址為2位）。來自cpu的20位的塊位址a23～a04不能用于定位cache中的塊，這是為什麼？因為相聯存儲器将主存儲器中1m個塊中的任意一個存放于其4096個塊中的任意一個，cache并不知道要通路的塊目前是否在cache中。即使知道塊在cache中，也不知道它到底在哪裡。
圖1-9說明了為什麼針對在cache中定位一塊這個問題找不到簡單的解決方案。在該例中，同樣使用24位位址總線通路主存中16mb的dram和塊大小為64kb的相聯映射cache。cache中每一塊有16個位元組，對應4個32位的字。cpu可以通路的全部塊的總數是224/24 = 220，使用24位位址。該位址由a23～a04（塊位址）、a03～a02（塊内位址）以及a01～a00（位元組位址）組成。是以，需要20位的标志來唯一辨別一塊。
如何把來自cpu的包含1m個塊的位址映射為cache中包括4096個塊對應的位址？圖1-9給出了一種解決方案，該方案使用220個字、每個字12位的随機通路存儲器來存儲指向cache塊的4096個指針。該存儲器是稀疏的，因為1m個存儲位置中隻有cache中的4096塊具有指針。其他位置沒有指針是因為目前塊在主存儲器中而不是在cache中。當然，為了實作這個機制，需要在查找表中每一行增加一個額外的位來表示目前塊是否在cache中（即“命中/失效”位）。
圖1-9所示系統實作起來不便宜，因為需要儲存指向cache的指針構成的存儲器容量可能與主存儲器一樣大或者超過主存儲器的容量！此外，查找表必須非常快以避免增加cache的通路時間。在該例中，64kb的cache對應的查找表有1m個字，每個字12位（即大小為1.5mb），故該方案是不切實際的。可行的解決方案是使用相聯存儲器。
相聯cache名稱來源于其使用相聯存儲器來存放标志。相聯存儲器具有n位輸入但并不一定需要對應2n個唯一内部位置。n位輸入交給相聯存儲器并與每個位置上的标志域同時進行比較。如果輸入位址與某個正存儲的标志相比對，則輸出與該位置關聯的資料。否則，相聯存儲器輸出不比對。
繼續前面的例子，相聯cache使用相聯存儲器儲存4096個20位的标志（cache中的每塊對應一個标志）。當cpu進行存儲器通路時，位址總線的高20位将作為相聯存儲器的輸入。如果相聯存儲器包含該标志，則傳回相應的cache塊。
由于來自主存儲器的塊可位于相聯cache中的任意位置，當cache滿了會出現什麼情況？需要删除哪個塊來為新調入的塊提供空間？實際上，相聯cache會儲存每塊上次被通路的時間，這樣就可以将最久沒有使用的塊淘汰（或使用其他參數來決定将哪一塊淘汰出cache）。cache的替換政策與虛拟存儲器使用的類似（見下一節，例如，最近最少使用（lru）、先入先出（fifo），或随機政策等）。最近最少使用算法直覺上最好，因為它旨在清除最長時間沒有被通路的資料（如果不使用它就丢棄它）。然而，lru算法不容易實作，因為這樣做需要記錄每塊的最後通路時間。
相聯存儲器很昂貴，因為它需要大量的并行邏輯将輸入關鍵字（即目前的位址）與目前存儲的關鍵字同時進行比對。市場上現有的相聯存儲器都太小，不能用來實作實用的cache系統。
相聯cache可能會産生兩種類型的失效：一種是在第一次通路時的強制失效（compulsory miss）。它是強制的，因為cache塊中初始時是沒有資料的。減少強制失效的唯一方法是在通路所需的資料之前預先向cache中調入資料。當相聯cache已經滿了，所需資料不在cache中的時候，就會産生第二種cache失效——容量失效（capacity miss）。
組織cache最簡單的方法就是采用直接映射（direct mapping），它依賴于一種簡單的算法将主存儲器中的資料塊映射到cache中的塊。在直接映射cache中，主存塊被分為若幹個組（set），組的大小與cache的大小一緻。如前面的例子，一台具有16mb記憶體和64kb cache的計算機會将存儲空間分為16mb/64kb = 256個組。
為說明直接映射cache是如何工作的，假定主存儲器包括32個字，需要5位的位址來通路，cache的大小為8個字，塊大小為2個字。根據前面的定義，組大小為：存儲器容量/cache容量= 32/8 = 4。給定5位位址s0、s1、l1、l0和w，其中s位定義了組，l位定義了塊，w位定義了字。圖1-10展示處理器目前需要的字是如何根據組位址、塊位址以及字位址進行通路的。為了友善讨論，這裡隻考慮組和塊的通路，而不管一塊中有多少個字。
圖1-10所示的組織形式被稱為直接映射cache，因為cache中某塊的位置與主存儲器中塊的位置之間有直接的關系。在圖1-10給出的例子中，cache具有2位的塊位址，是以具有22=4個塊。如果直接映射cache有b位塊位址字段，則cache就有2b個資料塊。
當處理器産生一個位址，就會通路cache中對應的塊。例如，如果處理器生成5位位址01100，則通路第2塊。圖1-10顯示了主存儲器中有4個塊編号為第2塊：第0組的第2塊、第1組的第2塊、第2組的第2塊以及第3組的第2塊。假設在這個例子中，處理器通路第1組中的第2塊，顯然的問題是：系統如何知道cache中被通路的第2塊是來自主存儲器中第1組的第2塊？
圖1-11顯示了直接映射cache是如何解決這個問題的。在cache中每塊都有一個标志來辨別該塊來自主存儲器中的哪個組。當處理器給出的通路位址中塊位址為3，cache中第3塊對應的标志将發送給比較器。同時，處理器位址中的組字段也被發送給比較器。如果它們相同，則表明cache中的塊就是所需要的塊，發生命中。如果它們不相同，則發生失效，對應cache塊中的資料必須更新。
當通路第i塊并發生失效時，cache中原來的第i塊要麼被丢棄，要麼被寫回主存儲器，這取決于主存儲器的更新是如何組織實作的。後文将對cache這方面的問題進行研究。
圖1-12從另一種觀點來描述直接映射cache，其中主存儲器被當成一個組數×塊數的矩陣，該例中為4塊×4組。矩陣的旁邊是cache，它具有與主存儲器相同的塊數。目前cache中的塊與主存儲器中陰影部分的塊相對應。圖1-12表明，cache中的塊是如何從組号相同的主存儲器的某組中獲得的。
圖1-13給出了直接映射cache存儲器系統的架構結構。cache存儲體由儲存資料的高速ram構成。cache标志ram（cache tag ram）是一種由高速随機通路存儲器和資料比較器構成的特殊裝置。cache标志存儲器的位址輸入是處理器通路的塊位址（line address），該位址用來通路或指向包含該組标志的标志ram中的位置。将該位址對應cache标志ram中的資料送往比較器并與位址總線上的組位址進行比較。如果處理器給出的組字段與被通路塊的标志相比對，cache标志ram傳回命中信号。
直接映射cache不需要複雜的塊替換算法。如果需要通路組y中的塊x且發生了失效，主存儲器組y中的塊x将被加載到cache中的第x塊。當新塊載入時，直接将失效位置對應的塊淘汰出cache。
直接映射cache的優點是其固有的并行性。由于儲存資料的cache存儲器和cache标志ram是獨立的，它們可以被同時通路。一旦從位址總線給出的标志字段與cache标志ram的标志字段相比對，則命中，從cache中擷取的資料就是有效的。
直接映射cache的缺點是它對被緩存資料的位置敏感。可以聯系位址簿來了解，假設為每個字母保留6個位置。如果你已經有6個朋友的姓是以s開頭的，那麼下一次再碰到一個人的姓是以s開頭時就會出現問題。這很煩人，因為給q和x預留的位置可能完全是空的而不能用。由于隻有一個編号為x的塊能夠放在cache中，通路主存儲器中其他不同的組中塊号為x的塊将導緻cache中第x塊被替換。
即使cache沒有存滿，在通路主存儲器不同組中相同塊号的兩個塊時，會導緻塊在cache和主存儲器間進行交換。該問題會導緻較低的cache使用率和高失效率。這種在即使cache沒有存滿時也發生塊替換的情況稱為沖突失效（conflict miss），這是由于新塊和原緩存塊之間存在沖突。讀者很快會看到，提高直接映射cache的性能并不難。
雖然在資料組織不恰當時，直接映射cache的性能會非常差，但實際程式的統計測量結果表明，直接映射cache在最壞情況下的性能對其平均性能的影響并不明顯。
圖1-14展示了一個非常簡單的直接映射cache的操作，該系統具有16個字的主存儲器和8個字的直接映射cache。為簡化讨論，隻考慮對指令的通路。該cache可以儲存來自兩個組的一個塊。圖中在cache左側将塊編号為0～7，在其右側編号8～15，用來表明主存儲器中8～15塊被緩存。假定塊大小與字的長度相等，并運作如下代碼：
圖1-14隻顯示了取指周期。圖1-14a給出了系統的初始狀态。圖1-14b～d顯示取前3條指令，每條都存放在連續的cache位置。當圖1-14d中調用子程式後，轉向位址為10的指令。在該直接映射cache中，塊10和塊2将映射到相同的cache塊。之後，在圖1-14e中，add覆寫了cache塊2中的bl指令此時發生了沖突失效，由于目的位置已經被占用，資料不能調入cache，除非該位置被空出來。
圖1-14f中，第11塊中的mov pc,lr指令被裝入cache中第3塊。最後，在圖1-14g中，程式傳回，第3塊中的指令b xyz被裝入cache中的第3塊，替換掉以前的塊。
圖1-14表明，即使在一個簡單的系統中，直接映射cache中的元素可以很容易地被替換。如果上述這段代碼循環執行，頻繁替換cache中的資料将降低性能。
上一節介紹的直接映射cache很容易實作，不需要塊替換算法。然而，它不允許來自不同組但具有相同塊号的塊被同時緩存。全相聯cache對塊存放的位置沒有限制，但它需要考慮一旦cache已滿将替換哪個塊。此外，容量大的全相聯cache實作起來十分昂貴。組相聯（set-associative）cache結合了上述兩種cache的優點，實作起來代價也不高。是以，它是計算機上常見的cache組織形式。
直接映射cache隻為每個塊i配置設定了一個位置。如果使用兩個直接映射cache并行工作，就可以使塊i進入它們中的任意一個。如果使用n個直接映射cache并行工作，就可以使塊i進入n個位置中的任意一個。這就是n路組相聯cache。
在n路組相聯cache中，給定塊可載入cache中n個可能的位置。通常情況下，n的範圍是2～8。圖1-15展示了一個四路組相聯cache的結構，它由4個并行操作的直接映射cache構成。在此情況下，塊i可以載入4個直接映射cache中的任意一個。是以，具有相同塊号的不同塊在調入cache時産生的沖突将大大減少。這種方式稱為相聯（associative），因為來自處理器的塊位址被并行送給每個直接映射cache。然而，一般并不會對成千上萬的存儲單元同時進行搜尋，而隻對2～8個直接映射cache進行并行通路。每個cache的比較結果（即命中）将被交給或門，其輸出結果表示是否有一個cache命中。
圖1-16使用組相聯cache重複了圖1-14中給出的例子。兩個例子基本相同，隻是組相聯cache中的每個直接映射cache隻有4塊，但總容量還是8塊。圖1-16中所示為一個二路組相聯cache，塊可以儲存在上面或者下面的直接映射cache中的任意一個。
圖1-16中前幾步是一樣的，直到圖1-16e，當位址為10的add r1,r2,r1指令映射到第2塊（組大小為4）時，該塊已經被bl adder指令占用。在相聯的第2個cache的相應位置是空閑的，是以該指令可以緩存在下面的cache的第2塊，而不必替換上面cache中的塊。圖1-16f，mov pc,lr指令的塊号為3，儲存在上面的cache中。然而，當執行主存儲器第3塊中的b xyz指令時，上面的cache的第3塊已被占用，故它被緩存在下面cache的第3塊中。
來自idt應用筆記an-07《cache标志ram晶片簡化cache存儲器設計》的表1-1展示了cache的組織形式對失效率的影響。該失效率已經與直接映射cache的失效率相除進行了歸一化，用來表示相對于直接映射cache的結果。四路組相聯cache的結果要比直接映射cache的結果好30%。進一步增加相聯度對于性能的改善有限。
來自freescale半導體公司應用筆記的圖1-17展示了不同容量的cache、使用gcc編譯器時相聯度和命中率之間的關系。可以看出，cache容量比較小時，相聯度是一個重要因子。當cache容量達到256kb時，相聯度的作用就不十分顯著了。
由于cache非常重要，針對它的改進已經進行了大量的研究，特别是針對異常行為的處理（例如，當資料被緩存、替換并再次被緩存，等等）。
在直接映射cache基礎上進行變更可以得到僞相聯（pseudo-associative）cache。當直接映射cache發生沖突失效時，為失效的塊提供一個後備位置（alternative accommodation）。下面文本框中的“流緩沖和條緩沖”部分對沖突失效和其他類型失效的自然屬性進行了進一步的讨論。當直接映射cache發生失效時，僞相聯cache根據舊的位址再計算一個新的位址來存放資料。通常情況下，新的位址是對目前位址高端的一位或幾位進行取反操作得到。雖然這是規避直接映射cache限制一種巧妙方法，但它需要在一次失效以後進行第二次cache通路。
victim cache是一個小的cache，用來儲存最近被替換出cache的項目（即遇難者（victim））。victim cache與原cache并行通路，理想情況下，它是全相聯的。因為它的容量非常小，可以同時搜尋的塊數有限，是以可以使用全相聯的方式建構。
一個小的victim cache可以減少直接映射cache的沖突失效，這是因為它儲存的被替換塊的塊号與剛調入塊的塊号相同。victim cache也可以在主cache被充滿、開始出現容量失效的時候使用。victim cache儲存了被替換出cache的塊，由于資料既沒有在主cache也沒有在victim cache中複制，是以并沒有浪費空間。
victim cache典型應用的例子是嵌套循環。考慮在一個循環内調用了一段程式，循環的起點與被調用程式間有一定的距離。循環開始後，程式被調用。cache被充滿了，就必須替換一些塊為新的指令提供空間。當程式執行完傳回循環時，cache又需要替換一些塊，依此類推。victim cache可以儲存被替換的指令并確定它們在循環和函數調用序列被執行時命中。jouppi針對victim cache的研究表明，它可以很小，但十分有效。一些基準測試表明，當使用容量少到4項的victim cache時，可以減少80%的沖突失效。jouppi在研究使用victim cache來減少總的失效時，發現不同的基準測試程式的結果差異很大。使用容量為4項的victim cache時，各種基準測試程式平均會使失效率降低15%，而其中的某個基準測試程式最多會降低70%。
對victim cache的修改是使用選擇性（selective）victim cache，victim cache中的項可能來自cache中被替換的塊或者主存儲器。當新的塊被預取時，采用一種預測算法來确定它是否應該被載入cache或是victim cache。預測的目的是為了盡量避免cache污染，即避免載入不會被使用的塊。預測機制要求記錄每塊的曆史狀态資訊。該機制使用了兩位訓示器：一位用來表示位于cache中的塊從來沒有被通路過，另一位表示慣性（inertia）以避免在cache和victim cache間進行過度的交換。
另一個由john和subramanian提出的特殊cache為annex cache。與victim cache一樣，annex是一個專用的cache，但位于一級cache的前面。即victim cache位于cache的出口，而annex cache位于入口。victim cache給替換出cache的資料第二次機會，而annex cache要求想進入cache的資料證明自己的價值。
annex cache有助于防止很少使用的資料進入cache，進而減少cache污染。如果cache為不常使用的資料提供空間而将頻繁使用的資料替換出去的話，其效率肯定不高。在啟動時，所有資料塊以正常的方式進入cache。最初階段後，所有進入cache的資料都需要通過annex。隻有在主cache發生沖突失效且該失效塊已經在annex cache中被通路了兩次時，annex cache中的資料塊才會被交換進入主cache。進入annex cache的資料必須被證明在時間或空間局部性上存在價值。在實踐中，類似annex cache這樣的複雜cache機制是不容易實作的，由于附加功能的複雜性，需要在本來簡單的組相聯cache的基礎上增加大量的控制電路。