2009年9月2日 星期三

似MIPS多核心處理器

終於~
終於完成我理想中雙核心CPU啦~
我的理想是設計一個雙核心CPU~
使用者可以完全不用做甚麼特殊的設計,只需要把一般的程式放進去執行,
CPU內部自行判斷,將程式變成可平行化的處理!
這顆CPU不是像市面上的CPU,是用於多工處理的!
(就是只做一件事時,還是只有一個CPU處理,不會比較快,要做到兩件事以上才會用到兩顆CPU處理)
這次完成的CPU是為了讓處理一件事變快的CPU,這樣的CPU才真正達成平行處理,不是只是將兩顆接在一起。

接下來就是簡單的介紹啦~
似 MIPS 多核心處理器


圖中就是我所設計的似MIPS多處理器核心架構~
整個架構包含兩顆可平行化之似MIPS 處理器、一顆浮點數運算之似MIPS處理
器、處理器控制器與共用暫存器和外部記憶體控制器。

紅色部分為處理器1與處理器2是兩顆相同且可平行處理之似MIPS處理器,其中包含27個整數處理的指令,橙色部分為FPU處理器為處理浮點數之運算,包含18個指令,綠色部分為外部記憶體的控制器介面,藍色部分為處理器控制器與共享暫存器,此處理器控制器主要功能為判斷兩相鄰指令是否相依,並分配這些指令由哪些處理器工作,並將需要用到的暫存器資料傳進工作中處理器裡,且接收處理完的資料,更新其暫存器內容值,以確保資料同步。

至於控制器中判斷指令相依就是依照MIPS的指令格式分成暫存器指令格式,立即指令格式與跳躍指
令格式三種,控制器會根據不同之指令格式產生出不同的相依條件判斷。

資料同步與更新方面~
因為考慮到未來將發展更多處理器核心之系統晶片,
因此採用UMA(Uniform Memory Access)共享記憶體架構,如下圖,
此架構擁有一個共同記憶體,因此所有處理器皆須向此記憶體模組提取相關資料,並將處理完之資料更新回此記憶體模組,雖然在傳遞資料中會浪費相對的時間但用於多處理器核心架構中可以省去分別更新每顆處理器內的資料的時間。



在相同程式輸入下,此雙處理器比單處理器有效提升約150%之速率。
之後的工作重點就是將這次完成的雙核心處理器,兩個串在一起
這樣的話,完成的CPU不只有我設計的可平行處理一件事的CPU,更可以多工處理多件事~
達到真的做一件事也快,做多件事也快的理想~

期望畢業以前能完成四核心,八核心的CPU設計~
不然要畢業也難啦~

LDPC碼之SPA解碼演算法

好久好久沒有更新部落格啦!
應該是說!只發過一篇而已啦!!哈~
很快的!第二篇,是一年後!!
終於完成研討會的論文了!!
難得有空!就把研討會資料整理貼上來啦~

LDPC碼SPA解碼演算法
這次我所完成的LDPC解碼器設計方法,都是參考胡大湘老師上課的講義啦~
胡老師也有將講義公開在網路上~
有興趣的人可以上胡老師的"老胡小舖"下載來看喔~


而為什麼要用SPA(Sum-Product Algorithm)解碼演算法來當這次的主題呢??
因為書上說SPA是LDPC碼擁有最好效能的解碼演算法~
至於是不是真的~
我也不知道啦!
還有另一個原因就是~
在上課的時候~
胡老師就已經叫我們用matlab實現這個decoder啦~
所以~
matlab轉C~
OK的~
由於這次完成的程式只是在於驗證用,
因此所用的檢測矩陣是一個5X10的規則矩陣,
如下面的圖片~



所謂的規則矩陣就是說矩陣中每行每列含 1 的個數都相同。
接下來就是這個矩陣的Tanner Graph 圖啦~



Tanner Graph 圖真是LDPC碼的關鍵~
Tanner Graph 就是將檢測矩陣之行以檢查點(Check Node)表示,列以位元點(Bit Node)表示~
而SPA decoder 就是要計算出各檢查點與位元點之間為0與1的機率比值(比值大於等於0代表訊號接近0,比值小於0代表訊號接近1),以達到解碼效果。

我是把步驟分成四個~
第一步驟~
即計算出所有檢查點到位元點間為0與1的機率比值,以上面圖中上半部顏色線條為例~
檢查點m1到位元點l1之關係,計算m1到l1之間的機率比值必須計算出所有位元點到m1(除了l1到m1)的機率比值,在做第一次解碼時所有位元點到檢查點的機率比值為初始輸入的訊號為 0 與 1 的機率比值,之後的遞迴則運用步驟二得到的結果。

第二步驟~
計算出所有位元點到檢查點間為0與1的機率比值,以上圖下半部顏色線條為例~
位元點l10到檢查點m5之關係,計算l10 到m5之間的機率比值必須計算出所有檢查點到l10(除了m5到l10)的機率比值(由第一步驟求得),再加上初始收到的訊息為0與1的機率比值(圖中沒有畫出初始訊號)。

第三步驟~
求出所有檢查點與位元點之間為0與1的機率比值,經過公式的推導與簡化,其實就是將第一步驟求得之結果加上與第二步驟求得之結果。

第四步驟~
將機率的比值做判斷(大於等於0判斷為0,小於0判斷為1),再將其乘上檢測矩陣的轉置矩陣,若結果為全零則代表此判斷後的結果為解碼後得到的訊號,反之則遞迴至第一步驟。

一般書上跟胡老師講義是只分成三步驟啦(第一步跟第二步合在一起)!
但是我想說這樣比較好解釋,所以我自己拆成四步驟啦~