[計算機]第七章_存儲系統(tǒng)-資料下載頁
2024-10-16 23:03本頁面
【正文】 對角線和按反對角線訪問，并且在不同的變址位移量情況下，都能實現(xiàn)無沖突訪問。 39 多維數(shù)組（向量）的無沖突訪問存儲器 下面以 4 4的二維數(shù)組為例來討論這個問題。如果按照地址順序存儲，一個 4 4二維數(shù)組存儲在 4個并行存儲體中的情況 如圖 所示。顯而易見，對于按行、按對角線訪問能做到不發(fā)生沖突。但是，若按列訪問，由于 4個元素都放在同一個存儲體內(nèi)，只能分 4個存儲周期順序讀取它們。 0號體 1號體 2號體 3號體 體內(nèi)地址 0 a00 a01 a02 a03 1 a10 a11 a12 a13 2 a20 a21 a22 a23 3 a30 a31 a32 a33 40 多維數(shù)組（向量）的無沖突訪問存儲器 為了實現(xiàn)按行和按列都能無沖突訪問，有一種存儲方案是將數(shù)組的各個元素在 4個并行存儲體中錯位存放，如圖 所示。但是，這種存儲方案造成按對角線訪問時又發(fā)生沖突了。 0號體 1號體 2號體 3號體 體內(nèi)地址 0 a00 a01 a02 a03 1 a13 a10 a11 a12 2 a22 a23 a20 a21 3 a31 a32 a33 a30 41 二維數(shù)組（向量）的無沖突訪問存儲器 參照一維數(shù)組的情況，不難證明，如果二維數(shù)組的各個元素采用按地址順序存儲的方案，當(dāng)并行存儲體的個數(shù)是偶數(shù)時，對于 n n二維數(shù)組就不可能實現(xiàn)按行、按列、按對角線和反對角線的無沖突訪問。當(dāng)然，也可以針對不同的數(shù)組采取各種變通的措施，例如，采用不同的錯位存儲方案等。但是，這會給編譯程序增加很大的麻煩，硬件實現(xiàn)的代價也很高。因此，希望尋找到一種對用戶來說最為方便的均勻無沖突存儲方案，能夠?qū)崿F(xiàn)二維數(shù)組的按行、按列、按對角線和反對角線的變址無沖突訪問，而且，硬件實現(xiàn)比較簡單，代價不要太高。 42 二維數(shù)組（向量）的無沖突訪問存儲器 對于 n n的二維數(shù)組， PBudnik和 DJKuck提出了一種能夠?qū)崿F(xiàn)上述要求的無沖突存儲方案。這種方案要求并行存儲體的個數(shù) m≥n，并且取質(zhì)數(shù)，同時還要在行、列方向上錯開一定的距離存儲數(shù)組元素。設(shè)同一列相鄰元素在并行存儲器中錯開 d1個存儲體存放，同一行相鄰元素在并行存儲器中錯開 d2個存儲體存放。 當(dāng) m=22p+1（ p為任意自然數(shù)）時，能夠同時實現(xiàn)按行、按列、按對角線和按反對角線無沖突訪問的充要條件是： d1=2p d2=1 43 二維數(shù)組（向量）的無沖突訪問存儲器 以 4 4的二維數(shù)組為例，取大于 4的最小質(zhì)數(shù) m＝ 5作為并行存儲體的個數(shù)，并把 m代入關(guān)系式 ，解得到 p＝ 1，從而計算得到 一個4 4的二維數(shù)組在 5個存儲體中的存儲情況如圖所示。原來在同一列中的相鄰元素要錯開兩個存儲體存放，如 a10要存放在 2號存儲體中，a20要存放在 4號存儲體中， … 。原來在同一行中的各個元素仍然按順序存放在該行中，但要按 5取模。 0號體 1號體 2號體 3號體 4號體 體內(nèi)地址 0 a00 a01 a02 a03 1 a13 a10 a11 a12 2 a21 a22 a23 a20 3 a30 a31 a32 a33 44 二維數(shù)組（向量）的無沖突訪問存儲器 很明顯，按照 圖 所示的存儲方案， 4 4二維數(shù)組在按行、列、對角線和反對角線訪問時均沒有沖突。并且，由于并行存儲體的個數(shù)是質(zhì)數(shù)，對于不同的變址位移量，對這個數(shù)組的訪問仍然是沒有沖突的。 假設(shè) aij是 n n二維數(shù)組中的任意一個元素，則這個元素在無沖突并行存儲器中的體號地址和體內(nèi)地址可以通過如下的一般公式來計算： 體號地址 : (2pi+j+k) MOD m 體內(nèi)地址： I 0≤i≤n－ 1， 0≤j≤n－ 1， k是數(shù)組的第一個元素 a00所在體號地址，一般情況下取 k＝ 0； m是并行存儲體的個數(shù)，要求 m≥n且為質(zhì)數(shù)； p是滿足 m=22p+1 關(guān)系的任意自然數(shù)； MOD是模運算的符號。 45 拓寬存儲器帶寬的方法 增加存儲器數(shù)據(jù)寬度的方法一般用單體多字方法。它和多體交叉存儲器類似，采用模 m交叉編址，并行讀出多個字。 Cache的寬度通常為一個字，因為大多數(shù)訪存都是一個字的寬度。帶有 cache的主存的寬度可以是一個塊的寬度，因為主存與 Cache交換數(shù)據(jù)是以塊為單位的。在有些系統(tǒng)中，主存與處理器通過總線相連，主存的寬度受總線寬度的限制不能做得太寬，為提高數(shù)據(jù)傳輸?shù)乃俣?，這些系統(tǒng)中廣泛采用突發(fā)方式（ Burst mode）傳送數(shù)據(jù)，即在一個總線操作周期中以數(shù)據(jù)塊傳送方式將數(shù)據(jù)塊從主存調(diào)入Cache。 多體交叉存儲器的實際帶寬要比單體多字存儲器的高，前者只要m個地址不發(fā)生分體沖突，使各地址不是按順序排列的，仍可并行訪問；而單體多字存儲器只有在訪問連續(xù)存儲的數(shù)據(jù)時方可提高其吞吐率。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1