為了找出並行計算上的各種狀況，需要找到可以表達的模型。
目前已知並行狀態機可以使用Petri Net來表達。
在找Petri Net資料中，找到了工作流模式(workflow pattern)。
也就是所有並行式工作流，都可以使用工作流模式內的模型來表達。
工作流模式基本模型有21種：
1. 順序（Sequence）
2. 平行拆分（Parallel Split）
3. 同步（Synchronization）
4. 排他選擇（Exclusive Choice）
5. 單合併（Single Merge）
6. 多選（Multi-choice）
7. 平行合併（Synchronize Merge）
8. 多合併（Multi-merge）
9. 鑒別器（Discriminator）
10. M中的N模式（N-out-of-M Join）
11. 強制循環（Arbitrary Cycles）
12. 隱式終止（Implicit Termination）
13. 非同步的多實例（Multiple Instances Without Synchronization）
14. 在設計期間預先確定的多實例（Multiple Instances With a Priori Design Time Knowledge）
15. 在運行期預先確定的多實例（Multiple Instances With a Priori Runtime Knowledge）
16. 無法在運行期預先確定的多實例（Multiple Instances Without a Priori Runtime Knowledge）
17. 延遲選擇（Deferred Choice）
18. 交替平行路由（Interleaved Parallel Routing）
19. 里程碑（Milestone）
20. 取消活動（Cancel Activity）
21. 取消實例（Cancel Case）
可以到
http://is.ieis.tue.nl/research/patterns/patterns.htm
上面有動畫實例，可以很容易的了解各模型的差異。
有了這個工作流模式，只要把各狀況找出解決方式，就不會用自己想的怪方法來解，然後遇到不明的問題。
2010年3月31日 星期三
2010年3月30日 星期二
2010年3月16日 星期二
"多核計算與程式設計"介紹
1.讀書原由
在CUDA程式設計上面遇到許多多核心程式計算的問題。個人從單核心作業系統一下子變成多核心程式設計，才發覺對於多核心知識的不足。
而CPU多核心已流行數年，在新的PC硬體上，要使用雙核心已是基本配備。意指，多核心已經是免費午餐。
但在軟體設計上，卻很少使用到雙核心，甚至四核心來做為加速。為何會如此?轉換程式是如此慢，其原因為何?
在收集網路資料後發現，出在使用語言上的問題比作業系統支援多核心來得嚴重。但不管如何，中文資料一樣貧乏。
a.作業系統支援及其問題
過去：
作業系統支援多核心是最早的，在Unix作業系統就已發展出支援多核心的方式。
但是現代作業系統都有支援的狀況下，為何沒有什麼程式設計師願意使用?原因在於使用的門檻高，且其經濟效應不好。
因為多核心程式在單核心的CPU運行效率不好，在市場尚未普及前，多數工程師仍未接受多核心程式訓練。
現在：
但現在環境已經不同了，多核心時代真的到來。
b.電腦語言支援多核心問題
過去：
其實這才是目前多核心程式發展的最大阻礙。撰寫多核心程式只能使用作業系統支援的狀況下，困難度太高。
而大部分使用者所使用的語言皆為對於單核心所設計。能使用在多核心的電腦語言則是太少。
所以大部分程式設計仍然被單核心程式語言所限住。這才是多核心程式真正無法流行的原因。
因為程式語言就是要讓使用者方便處理設計，若是學習門檻太高，就不易推行。
現在：
語言延伸：MPI、OpenMP
平行語言：Erlang、Scala
c.使用CUDA之後才發現的問題
CUDA的推行以資料為主的平行計算。和之前在作業系統所提的工作為主的平行計算上有很大的不同。
在超過八核心同時運算時，為了要增加產出率，勢必要採行以SIMD為主的語言架構，也就是資料為主的程式概念。
但個人發現，可以找到的資料不多，所以轉以找多核心程式的資料，所以找到此書。
2.書本結構
a.基礎知識
多核計算概述
多線程編程基礎
OpenMP程式設計
b.基礎資料結構及算法
結構
Link List
Hash
Tree
AVL search tree
c.平行運算法
並行程式設計模式
並行搜尋
並行排序
並行數值計算
d.共享資源分散式計算
分散式計算設計模式
分散式陣列
分散式查找
分散式記憶體管理
e.任務分解及調度
任務圖分解及調度
動態任務分解及調度
Lock-Free編程基礎
3.比對CUDA
a.有許多問題是一樣的
b.CUDA中有些問題解法未表明產生原因，在多核心中則有解釋
c.CUDA可視為多核心的一種實現
d.可以有效利用CUDA中的原子函式
e.免除遇到多核心問題，無從看出問題產生原因
2010年2月20日 星期六
8051簡單多工7：堆疊(stack)使用狀況
發現忘了說使用這個架構是為了什麼。當然是省記憶體，但到底是省到那一種。答案是我想省下使用8051 Register file。
有玩8051的應該會知道8051產生副程式呼叫所使用的堆疊在那裏，就是Registers file。問題是它的大小只有256byte。
也就是說，最大只能呼叫128層的副程式，還要扣除使用暫存器、中斷程式的使用，實際上連100層都到不了。
當堆疊玩爆了，什麼怪現象都會冒出來，沒有對處理器了解的人，是永遠也不知問題出在那裡。
可是有人會問，是誰有辦法寫出40層以上的呼叫，玩到堆疊爆掉。其實也不用那麼多層也可以爆掉的。
在函式內的區域變數也是在用堆疊的，也就是如果函式內皆使用30byte的區域變數，呼叫個十層，就會爆了。
可是有人會問，他寫8051程式已經很大了，並沒有遇到我說的現象。這就是Compiler的工作了，像Keil C在每次函式呼叫，會去計算使用多少堆疊。所以可以預測是否出現堆疊爆掉的狀況。
不過中斷程式也是使用堆疊，卻不在計算範圍內，所以有時中斷程式寫太大仍會發生怪現象。
好了，談了這麼多，和多工有何關係?
當然有，因為多工，所以函式的數量一定大增，以RTOS來寫，每一個Task都會要求獨立的堆疊，8051的堆疊根本不夠用。
不過8051上仍有RTOS，像uCOS就有8051版本，只不過它在切換Task時，是將整個Stack都搬到外部記憶體去，然後又從外部記憶體搬另一個Task的回來。這樣做其實效率並不好，但也只能接受。因為8051原設計就沒想到裝作業系統這樣東西進去。
而Bee在設計上，有想到保留堆疊(stack)，所以採用非強制多工的方法，如此一來就可以確定函式執行完成退出後，才會輪到另一個task的函式執行。這就是一開始設計上的考量。
不過有所犧牲，程式只能以狀態機的方式寫，會使得別人不好閱讀程式。
不過Task之間因為要回到main()中才能切換，回到main()即表示全部堆疊都已釋放，也就是Task之間不會有堆疊互相堆積的問題。也就可以確保每個Task都幾乎有完整的8051堆疊可用。
這是這個架構的好處，在實際使用上，就有許多變數可以放進Register file可以增加8051的運作速度了。或者可以使用比較多層的中斷程式也比較不用擔心。
但這個架構仍有一個問題，那就是Keil C因為會去預測堆疊的使用。當安排一個Task是由一群循環的狀態函式所組成時，Keil C會提出使用到遞迴結構的警告。這個我還不知要如何去除。看看那天能有人給點建議。
不過只是警告，還不至於影響執行。
Bee實作上，有遇到一次的是，單一的Task掛了，產生資料存取錯誤，另三個Task仍很正常。大概是沒有影響到全域變數，所以還好。可見穩定性還可以。
至於是那一個事件，可以去另一篇LCM當機解法看看。
有玩8051的應該會知道8051產生副程式呼叫所使用的堆疊在那裏，就是Registers file。問題是它的大小只有256byte。
也就是說，最大只能呼叫128層的副程式，還要扣除使用暫存器、中斷程式的使用，實際上連100層都到不了。
當堆疊玩爆了，什麼怪現象都會冒出來，沒有對處理器了解的人，是永遠也不知問題出在那裡。
可是有人會問，是誰有辦法寫出40層以上的呼叫，玩到堆疊爆掉。其實也不用那麼多層也可以爆掉的。
在函式內的區域變數也是在用堆疊的，也就是如果函式內皆使用30byte的區域變數，呼叫個十層，就會爆了。
可是有人會問，他寫8051程式已經很大了，並沒有遇到我說的現象。這就是Compiler的工作了，像Keil C在每次函式呼叫，會去計算使用多少堆疊。所以可以預測是否出現堆疊爆掉的狀況。
不過中斷程式也是使用堆疊，卻不在計算範圍內，所以有時中斷程式寫太大仍會發生怪現象。
好了，談了這麼多，和多工有何關係?
當然有，因為多工，所以函式的數量一定大增，以RTOS來寫，每一個Task都會要求獨立的堆疊，8051的堆疊根本不夠用。
不過8051上仍有RTOS，像uCOS就有8051版本，只不過它在切換Task時，是將整個Stack都搬到外部記憶體去，然後又從外部記憶體搬另一個Task的回來。這樣做其實效率並不好，但也只能接受。因為8051原設計就沒想到裝作業系統這樣東西進去。
而Bee在設計上，有想到保留堆疊(stack)，所以採用非強制多工的方法，如此一來就可以確定函式執行完成退出後，才會輪到另一個task的函式執行。這就是一開始設計上的考量。
不過有所犧牲，程式只能以狀態機的方式寫，會使得別人不好閱讀程式。
不過Task之間因為要回到main()中才能切換，回到main()即表示全部堆疊都已釋放，也就是Task之間不會有堆疊互相堆積的問題。也就可以確保每個Task都幾乎有完整的8051堆疊可用。
這是這個架構的好處，在實際使用上，就有許多變數可以放進Register file可以增加8051的運作速度了。或者可以使用比較多層的中斷程式也比較不用擔心。
但這個架構仍有一個問題，那就是Keil C因為會去預測堆疊的使用。當安排一個Task是由一群循環的狀態函式所組成時，Keil C會提出使用到遞迴結構的警告。這個我還不知要如何去除。看看那天能有人給點建議。
不過只是警告，還不至於影響執行。
Bee實作上，有遇到一次的是，單一的Task掛了，產生資料存取錯誤，另三個Task仍很正常。大概是沒有影響到全域變數，所以還好。可見穩定性還可以。
至於是那一個事件，可以去另一篇LCM當機解法看看。
2010年2月18日 星期四
8051簡單多工6：核心編譯之組語
這篇是給慣用組合語言的人做為比較的，並且看看8051是如何去做函式指標呼叫。
我使用SDCC的組譯程式來看，因為Keil c的比較複雜。以下為main()中程式轉成組合語言段落：
C語言部分：前面數字為行號，可以在組合語言中找到對應段落。TASK_NUM設為4
77:void main(void)
78:{
79: PCA0MD &= ~0x40; // Disable Watchdog timer
80: Init_Device();
81: while (1)
82: {
83: register void (*Current_Func)(void);
84: EA = 0;
85: Current_Func = TaskFunc[FuncID]; // may break with interrupt
86: EA = 1;
87: Current_Func();
88: FuncID = (++FuncID) % TASK_NUM;
89: }
90:}
ASM組合語言結果：
;------------------------------------------------------------
;Allocation info for local variables in function 'main'
;------------------------------------------------------------
;Current_Func Allocated to registers r2 r3
; main.c 77
; -----------------------------------------
; function main
; -----------------------------------------
_main:
; main.c 79
anl _PCA0MD,#0xBF
; main.c 80
lcall _Init_Device
; main.c 81
00102$:
; main.c 84
clr _EA
; main.c 85
mov r0,#_FuncID
mov a,@r0
add a,acc
; Peephole 105 removed redundant mov
mov r2,a
add a,#_TaskFunc
mov r0,a
mov ar2,@r0
inc r0
mov ar3,@r0
dec r0
; main.c 86
setb _EA
; main.c 87
mov a,#00107$
push acc
mov a,#(00107$ >> 8)
push acc
push ar2
push ar3
ret
00107$:
; main.c 88
mov r0,#_FuncID
mov a,#0x01
add a,@r0
mov r2,a
mov r0,#_FuncID
mov b,#0x04
mov a,r2
div ab
mov @r0,b
; Peephole 132 changed ljmp to sjmp
sjmp 00102$
00104$:
ret
可以看到Current_Func是使用r2及r3暫存器。
取函式指標執行是第87行的動作，使用四個push及一個ret來做，這不是一般人可以理解的吧。Keil C呼叫更多東西。
唯一可以確定的是push ar2及puah ar3中的ar2及ar3就是暫存器r2及r3。
從這裏可以看到除餘(%)真的是拿去除，所以上一篇才會提到加速及展開的問題。不過Keil C就聰明多了，會用and 3去做。
要玩MCU還是要看一下組合語言在幹什麼，常常和想的不同。
我使用SDCC的組譯程式來看，因為Keil c的比較複雜。以下為main()中程式轉成組合語言段落：
C語言部分：前面數字為行號，可以在組合語言中找到對應段落。TASK_NUM設為4
77:void main(void)
78:{
79: PCA0MD &= ~0x40; // Disable Watchdog timer
80: Init_Device();
81: while (1)
82: {
83: register void (*Current_Func)(void);
84: EA = 0;
85: Current_Func = TaskFunc[FuncID]; // may break with interrupt
86: EA = 1;
87: Current_Func();
88: FuncID = (++FuncID) % TASK_NUM;
89: }
90:}
ASM組合語言結果：
;------------------------------------------------------------
;Allocation info for local variables in function 'main'
;------------------------------------------------------------
;Current_Func Allocated to registers r2 r3
; main.c 77
; -----------------------------------------
; function main
; -----------------------------------------
_main:
; main.c 79
anl _PCA0MD,#0xBF
; main.c 80
lcall _Init_Device
; main.c 81
00102$:
; main.c 84
clr _EA
; main.c 85
mov r0,#_FuncID
mov a,@r0
add a,acc
; Peephole 105 removed redundant mov
mov r2,a
add a,#_TaskFunc
mov r0,a
mov ar2,@r0
inc r0
mov ar3,@r0
dec r0
; main.c 86
setb _EA
; main.c 87
mov a,#00107$
push acc
mov a,#(00107$ >> 8)
push acc
push ar2
push ar3
ret
00107$:
; main.c 88
mov r0,#_FuncID
mov a,#0x01
add a,@r0
mov r2,a
mov r0,#_FuncID
mov b,#0x04
mov a,r2
div ab
mov @r0,b
; Peephole 132 changed ljmp to sjmp
sjmp 00102$
00104$:
ret
可以看到Current_Func是使用r2及r3暫存器。
取函式指標執行是第87行的動作，使用四個push及一個ret來做，這不是一般人可以理解的吧。Keil C呼叫更多東西。
唯一可以確定的是push ar2及puah ar3中的ar2及ar3就是暫存器r2及r3。
從這裏可以看到除餘(%)真的是拿去除，所以上一篇才會提到加速及展開的問題。不過Keil C就聰明多了，會用and 3去做。
要玩MCU還是要看一下組合語言在幹什麼，常常和想的不同。
8051簡單多工5：使用上的調整及範例
編譯環境差異：
目前在Keil c及SDCC下編譯皆有過。但Bee沒有使用SDCC實際去執行過。不過SDCC編出來的組合語言看來沒有問題，應是可以用的。
核心加速：
在看編出來的組合語言，可以發現Bee使用除餘(%)來做FuncID調整會動用到除法，使執行效率下降。
比較好的寫法是將FuncID整個展開，這樣也不用去計算它。
以使用三個Task為例，將while改寫為：
while (1)
{
TaskID = 0;
EA = 0;
Current_Func = TaskFunc[TaskID];
EA = 1;
Current_Func();
TaskID++;
EA = 0;
Current_Func = TaskFunc[TaskID];
EA = 1;
Current_Func();
TaskID++;
EA = 0;
Current_Func = TaskFunc[TaskID];
EA = 1;
Current_Func();
}
這樣執行起來更有效率。
另一個例子：
這是Key Scan範例
// Key Scan function
#define KEY_SCAN_DELAY 1 // 1ms
void key_scan2(void);
void key_scan3(void);
void key_scan4(void);
void key_Encode(void);
unsigned char KeyScan[5]; // unknow why KeyScan[0] can't be used? just skip
void key_scan1(void)
{
KeyScan[4] = P1;
P1 = ~(1<<0)<<4 | 0x0F;
Task_Delay_Next(key_scan2);
Task_Delay_Ms(KEY_SCAN_DELAY);
}
void key_scan2(void)
{
KeyScan[1] = P1;
P1 = ~(1<<1)<<4 | 0x0F;
Task_Delay_Next(key_scan3);
Task_Delay_Ms(KEY_SCAN_DELAY);
}
void key_scan3(void)
{
KeyScan[2] = P1;
P1 = ~(1<<2)<<4 | 0x0F;
Task_Delay_Next(key_scan4);
Task_Delay_Ms(KEY_SCAN_DELAY);
}
void key_scan4(void)
{
KeyScan[3] = P1;
P1 = ~(1<<3)<<4 | 0x0F;
Task_Set_Next(key_Encode);
}
// Encode Key code
void key_Encode(void)
{
// do some thing here
Task_Delay_Next(key_scan1);
Task_Delay_Ms(KEY_SCAN_DELAY);
}
// Key Scan function end
比較一下使用uCOS的寫法
void key_scan(void)
{
while(1)
{
KeyScan[4] = P1;
P1 = ~(1<<0)<<4 | 0x0F;
OSTimeDly(10);
KeyScan[1] = P1;
P1 = ~(1<<1)<<4 | 0x0F;
OSTimeDly(10);
KeyScan[2] = P1;
P1 = ~(1<<2)<<4 | 0x0F;
OSTimeDly(10);
KeyScan[3] = P1;
P1 = ~(1<<3)<<4 | 0x0F;
// do something here
OSTimeDly(10);
}
}
可以發現這個簡單多工是以狀態機的方式下去寫，就是以一個狀態的函式再跳到另一個狀態的函式的寫法。
而uCOS在執行OSTimeDly()之後可以再從它的下一行執行下去。這個是比較容易理解的寫法。
不過8051的資源不多，Bee才會自創多工核心。
目前在Keil c及SDCC下編譯皆有過。但Bee沒有使用SDCC實際去執行過。不過SDCC編出來的組合語言看來沒有問題，應是可以用的。
核心加速：
在看編出來的組合語言，可以發現Bee使用除餘(%)來做FuncID調整會動用到除法，使執行效率下降。
比較好的寫法是將FuncID整個展開，這樣也不用去計算它。
以使用三個Task為例，將while改寫為：
while (1)
{
TaskID = 0;
EA = 0;
Current_Func = TaskFunc[TaskID];
EA = 1;
Current_Func();
TaskID++;
EA = 0;
Current_Func = TaskFunc[TaskID];
EA = 1;
Current_Func();
TaskID++;
EA = 0;
Current_Func = TaskFunc[TaskID];
EA = 1;
Current_Func();
}
這樣執行起來更有效率。
另一個例子：
這是Key Scan範例
// Key Scan function
#define KEY_SCAN_DELAY 1 // 1ms
void key_scan2(void);
void key_scan3(void);
void key_scan4(void);
void key_Encode(void);
unsigned char KeyScan[5]; // unknow why KeyScan[0] can't be used? just skip
void key_scan1(void)
{
KeyScan[4] = P1;
P1 = ~(1<<0)<<4 | 0x0F;
Task_Delay_Next(key_scan2);
Task_Delay_Ms(KEY_SCAN_DELAY);
}
void key_scan2(void)
{
KeyScan[1] = P1;
P1 = ~(1<<1)<<4 | 0x0F;
Task_Delay_Next(key_scan3);
Task_Delay_Ms(KEY_SCAN_DELAY);
}
void key_scan3(void)
{
KeyScan[2] = P1;
P1 = ~(1<<2)<<4 | 0x0F;
Task_Delay_Next(key_scan4);
Task_Delay_Ms(KEY_SCAN_DELAY);
}
void key_scan4(void)
{
KeyScan[3] = P1;
P1 = ~(1<<3)<<4 | 0x0F;
Task_Set_Next(key_Encode);
}
// Encode Key code
void key_Encode(void)
{
// do some thing here
Task_Delay_Next(key_scan1);
Task_Delay_Ms(KEY_SCAN_DELAY);
}
// Key Scan function end
比較一下使用uCOS的寫法
void key_scan(void)
{
while(1)
{
KeyScan[4] = P1;
P1 = ~(1<<0)<<4 | 0x0F;
OSTimeDly(10);
KeyScan[1] = P1;
P1 = ~(1<<1)<<4 | 0x0F;
OSTimeDly(10);
KeyScan[2] = P1;
P1 = ~(1<<2)<<4 | 0x0F;
OSTimeDly(10);
KeyScan[3] = P1;
P1 = ~(1<<3)<<4 | 0x0F;
// do something here
OSTimeDly(10);
}
}
可以發現這個簡單多工是以狀態機的方式下去寫，就是以一個狀態的函式再跳到另一個狀態的函式的寫法。
而uCOS在執行OSTimeDly()之後可以再從它的下一行執行下去。這個是比較容易理解的寫法。
不過8051的資源不多，Bee才會自創多工核心。
訂閱：
文章 (Atom)