CUDA新書到

Bee之前都是自己收集資料，看原文去理解。所以差不多是遇到什麼再去查。
終於有本比較集中資料的書了。常用的運算法也都有解釋。雖然Bee也查的差不多了。
不過買了除了自己查外，拿來教人也是真的。
隨著CUDA運算的流行，實驗室影像組的CUDA人員正在擴張中。

除了影像運算外，Bee本身就是控制組的人，也很想用到Robot控制上。
其中最大的原因是GPGPU的價格低到可以和影像處理的DSP差不多了。
一台使用Atom+ION的NetPC也很合適於控制Robot。
看看控制組何時也想用用CUDA了。

acer小主機

Bee因為有使用P2P下載軟體，使用四核心電腦來用實在有點耗電，所以買了atom處理器的小主機，價格為7xxx元。
不過因為有之前買筆電的經驗，所以決定買具有獨立顯示晶片的機種。
其實能選的不多，只能選用ION晶片。
最後買了acer小主機。
後來才和同事的小筆電比一下效能。
以atom來說是差不了太多。都可以很順的跑Office。
但玩Facebook就不一樣了。
ION晶片可以處理四個Facebook網頁，小筆電第二頁就不太行了。
可見獨立顯示晶片對於現代電腦的重要性。
當時同事說小筆電只是上網及打報告，結果Facebook流行起來，又不行了。

不過當時拿到公司去安裝作業系統時，發現小主機跑得比公司給我的電腦快。
CPU等級沒有比較好，但RAM及HDD都是比較快的，所以整體表現就比較好。
所以拿公司電腦去做PCI卡上的FPGA程式開發是對的，讓它早死早超生吧！

看"遊戲編程精粹6"心得

這篇不太能稱得上是心得。
主要是驚訝於2006年的書，已經預測了2009年Bee所使用的技術。
Bee目前有用到的且書上提到的有：
OpenMP,
OpenCV,
Lua,
GPU,
人工智慧

可見得遊戲上所使用的軟體技術是相當先進的。目前才在Bee的使用上開花結果。
但Bee更相信所謂的專家，真的有預測正確，只是有多少人看出來並願意去相信。
早個一二年去相信，也許整個狀況將大不相同了。

2009年參賽獎狀

假共享(False Sharing)問題

在看CUDA Programming Guide時，有一大篇討論Shared Memory Access Patterns with Bank Conflicts問題。這個一直不太了解。

後來找多核心文章，發現假共享(False Sharing)問題。仔細看，這個不就是CUDA裏面提的問題。
由此Bee之前推測的CUDA中的Share memory是軟體管理的cache，這個論點是確認無誤了。因為使用一樣的硬體，才會有一樣的問題，連解法都一樣。

好在之前沒有將share memory做為寫入用，所以問題不大。
之後要小心考量使用share memory的寫入問題了。

CUDA計算積分數列的方法

使用平行運算計算總和，還可以理解。但要算積分，不符合平行運算的方法，這下要如何?
積分數列的數學問題是這樣的：
數列 X=[ a0 a1 a2 ... aN ]
要算出 Y=[ a0 a0+a1 a0+a1+a2 ... a0+a1+a2+...+aN ]

其實有注意到的人會發現，為何這個問題Bee要用平行運算。因為這就是圖像積分法(integral image)的基本運算。因為要移進GPGPU來做，問題就來了。
因為每一個數列元素要等上一個元素的值出現才能算，可是平行運算要沒有相關才能用，這下子有解嗎?
找了許多文章，一張圖解了這個問題。

果然還是因為沒有收集平行運算的演算法，才會不知道往那裡去找。
找到了之後，發現這個動作可以做以下的計算：
Radix sort
Quicksort
String comparison
Lexical analysis
Stream compaction
Sparse matrices
Polynomial evaluation
Solving recurrences
Tree operations
Histograms
看來是很重要的演算法，值得好好去了解。

CPU和GPU的合作，和大腦分工相似。

Bee是搞自動控制的，有一個問題一直是系統不好選擇的。到底是要用分散式處理器來做系統運算，還是用PC做中央控制。
分散控制也是有好處的，系統加元件是很快，因為關係單純，但程式不好改，要改許多處理器程式。
中央控制則是要經過中央管理系統，比較複雜，但程式好改。

這個問題到Bee開始處理影像相關問題，才知道要如何選。
原因在於影像處理無法使用分散運算的方式，若是真的要用，那訊息傳輸系統一定一直在傳影像相關資料，反而是一種浪費。

不過一開始Bee處理影像控制是想用FPGA來做，但它的記憶體不足，必須外掛SDRAM。
規劃到一半GPGPU興起，完全符合影像處理的需求，我就直接轉到GPGPU的領域去。
其實對於影像處理，其瓶頸在於運算相同，但資料量很大，平行計算才能有效解決。
但資料之間有相關，無法分開存放，要使用集中式的存放才能有效運算。

只是理解之後，Bee在想，一樣的工程問題，生物界是如何解的?
果然，大腦的發展，差不多和眼睛的出現是相關的。不是一個感光細胞的眼睛，是一群感光細胞組成的眼睛。

Sensor Array的出現，就是引入大量平行處理的開始。
在multi-sensor的狀況下，腦不需很大，大概就處理環境記憶和時間相關資訊。
但Sensor Array就不同了，記憶體需求量大，且運算力大增，才可做出分析。

在玩CUDA之後，發現並非所有的問題都合適GPU運算。在做統合判定的地方，CPU的運算更合適。
而且CUDA的異質運算結構，可以比OpenMP更容易去選擇運算結構。簡單的說何時要用CPU運算，何時要做GPU運算，是很容易分的。
但OpenMP不是如此明顯，但還是有平行運算的味道在。

最近看了"你腦內的兩個世界"
http://blog.xuite.net/unlimiter1001/unlimiter/29032221
了解兩個半腦的分工，更可以確定人工智能真的需要並行處理器及串行處理器的配合。
腦之所以二個完全分開，正因為腦的運算為成長型。右腦專精於平行處理，左腦專精於串行處理。二種迴路基本型式必然完全不同，所以分成二個腦來成長。
也可以說生物界對於平行運算和串行運算，沒有做出統一的解，所以長出二個處理器來做。
那Intel想用X86來做GPU，想必無法有效和真正的GPU來競爭。果不其然Larrabee的計劃真的失敗。

但並行運算就算是解了影像處理問題，但後繼串行處理的部分也是會增加運算量。原因是資訊也跟著變多，串行處理的資料及儲存也是要跟著增加上去。
所以左右腦的大小一直都是一樣，可見得二者重要性誰也沒有贏過誰。
意指，就算CPU和GPU就算合成一個晶片來做通用運算，二者電路的比例可能仍是很相近。那關於這個預測，要等GPGPU運算普及才會有人探討。

那對於現在，Bee的問題出在沒有收集過平行運算的運算法。因為才開始流行，資料不多。但對於軟體發展，這是無法避免的。
只能開始注意及了解相關的發展了。

使用積分影像法(integral image)取代金字塔圖層

做影像處理常用到金字塔圖層的方式做影像加速處理的方法。
但金字塔圖層會多用掉記憶體，使用量剛好是原圖的一半。
後來發現有人使用積分影像法(integral image)，它可以同時代表原圖及金字塔圖層。
因為可以做不同大小的差分而獲得所需的圖。
只要取點時算A-B-C+D就好了。

如何將影像處理程式改寫為CUDA程式

這裡提出我遇到問題時找到的原則：

1.保留原程式結構，先找出最多層for的地方，先將這個函式GPU化。

2.找出要GPU化的函式所要的輸入及輸出資料。從個別處理改為表格化資料，因為要展成並行處理。

3.找出各for對應的並行層。
  就是將各for展成threadIdx及BlockIdx。
  和圖檔長寬相關的for主要以BlockId.x及BlockId.y做分配。因為這二個系統變數可用範圍最大。

4.先產生CPU可執行函式取代，用以分離函式準備GPU化。但可以驗證及除錯。

5.驗證成功後，GPU化的程式再試。

6.針對GPU結構開始最佳化。在CPU的GPU版本上做除錯及驗證。

7.完成關鍵的CPU轉GPU函式，再找需要做的部分進行合併。

實際上執行仍有許多問題要克服，解決了再整理。

CUDA工作排程的了解

寫了一點CUDA程式，但對於寫出最佳程式並沒有什麼好辦法去了解，難到只有實測一途了嗎?
當然不是，可以找一下CUDA SDK中有一個試算表CUDA_Occupancy_calculator.xls。
玩了試算表，就可以稍為了解CUDA指令排程，其實和發動的執行時所使用資源有關。

可以發現只有三項資源可以調整。
1. 每一個Block使用多少Threads
2. 每一個Thread使用多少Registers
3. 每一個Block使用多少Shared memory

使用CUDA寫程式時對於每一個Block使用多少資源是很明確的，但對於每一個Thraeds使用多少Registers則不是可以直接得到。
不過調整一下數值可以發現CUDA的排程限制。

從文件可以知道一次CUDA指令可以有32個核心動作，這個叫Wraps。在不同核心架構下一次可以發動的Wraps數目不同。
因為工作上是以Block為主要規劃，所以Threads的數目除以32就是Wraps數。
像Bee用的G9600M最大的Wraps數目是24，24是不太好的數字，因為Bee寫的程式動作大部分和2的倍數有關，所以常常無法有效使用。

但不是可以使用的Threads多，Wraps數目就會多，因為因為每一個Threads都是一個core task會用掉Registers。對每一個multiprocessor來說，Registers數目是有限的。
所以就會有Registers總數限制，就是第二項要控制的。

通常一個Block會有共有的變數，此時就要使用到Shared memory，這項資源為每一個multiprocessor才有，所以又變成另一個限制。
由此可以看到一件事，雖然一個multiprocessor有八個core，但可以執行的Threads數目不是八。
可能Threads數目是32，八個core要分成四次執行。
另一種可能是因資源用完，32個Threads是分成4個multiprocessor去做。
若是資源使用很多，有可能每一個multiprocessor只能使用4 core，這時1個wraps會佔用更多的multiprocessor。

可以見得使用比較好的顯卡，因為Multiprocessor多，所以可以解比較耗資源的threads task。
以上為玩試算表所得的心得，實際上可能要實驗才能證實。

玩過後，發現程式工作如果分得比較細小的程式段，會有助於執行分配。
但要分到多細小，真的就要用這個試算表下去估了。