設計一個可真正平行的個人專用人工智慧電腦 電腦發明時，當時的人不知道電腦可當作打字機、音響、電話或可發展成國際網路。不過他們卻知道電腦可平行處理，而且未來是平行處理的天下。於是他們將兩台電腦放在一起，用軟體程式讓電腦通訊，平行處理各種運算。此方式產生的超級電腦單價高且CP值低，因此早期CDC、Cray computer...等超級電腦公司全部難逃破產命運，INTEL面對AMD 64 bit處理器競爭開始推出多核心共用記憶體結構電腦，卻沒有真正面對平行處理時Amdahl's law產生的問題，雲端可輕易擁有數十萬台電腦，然而系統效能卻取決於不可平行部分，不可平行部分為整個工作的5%時，Speedup<20，等於少於20台電腦平行運算，其他電腦都在睡覺。IBM深知多核心共用記憶體結構的侷限性，採用分散式系統發展雲端的WATSON。用相同的技術，Apple推出SIRI供手機用戶使用，Microsoft也推出Cortana給window用戶使用。 硬體的特質就是平行處理，大量的晶體與邏輯閘可同時平行工作，而軟體則是以依序處理為主，華盛頓大學系主任M. J. Quinn在其1998年著書中("Designing Efficient Algorithms for Parallel Computers"，Mcgraw-Hill )批評：研究者在共用記憶體中，假設沒有通訊與資料衝突問題是不切實際的，最後他總結：有效率的平行搜尋非常困難。解決此難題，本人認為雖然軟件是主導整個系統的要角，但是在執行平行處理時，軟體可以不要參與。換句話說，我們建議：平行處理時軟體下達開始執行一個平行處理的指令後，主導權轉交給硬體，硬體使用控制器與特殊硬體電路來執行並行處理，而不是使用軟體程式，完成平行指令後，硬體用interrupt訊號，將主導權交還給軟體，這樣的平行裝置可更簡單、更快速、且更可靠，電路不可平行度降至最低程度，可徹底解決Amdahl's law產生的問題。 圖一、 單核型許文龍電腦結構 圖一為單核心型的許文龍電腦結構，用PC及我們發明的平行硬體搜尋裝置(PHSD)來解決軟、硬體間的矛盾，由傳統PC下令後，純硬體搜尋器平行處理大數據，需要彈性的小數據則由傳統PC處理，硬體和軟體優點充分發揮，且避免彼此的弱點。此結構有幾個特點： 圖二、 OSI模型1. 通訊不會造成問題：圖二為處理器間通訊用的OSI模型，大量的時間耗費在許多軟體層(layer)。PHSD的PU不支援軟體，所有的資料在物理層（physical layer)平行傳輸，因此通訊不會造成問題。 圖三、 Shift left/ right register chain2. 沒有資料衝突問題：一般電腦叢集裏，電腦間必須相互借調資料，因此產生資料衝突問題。PHSD的PU都有自己的記憶體模組（BRAM module)，利用排序關係，巧妙地讓PU所需處理的資料全在自己的記憶體內，因此沒有資料衝突問題。硬體只有五個運算指令(fetch、store、search、insert和delete)，卻能處理電腦最重要的兩個運算：搜尋與排序，搜尋與人工智慧的推理有關，而排序可處理大數據運算。fetch、store、search明顯可以是真正平行運算，圖三為PU間的register chain，PUi將32bit由BRAMi傳至REGi，REGi值可同時送給鄰近的PUi-1和PUi+1，一個區塊的資料可向左或向右移動一個位置，因此insert和delete也是真正平行的運算，PU處理的資料全在自己的記憶體內，絕對沒有資料衝突問題。 圖四、將index file轉化成B-tree結構3. 資料庫的記錄指標(record pointer) 含有4 bytes 的page number與2 bytes 的offset，用來讀取表單完整的資料，用以快速搜尋的Index file含有關鍵資料(key)與其記錄指標，可轉化成如圖四所示的B-tree並且建立於DRAM，B-tree為許多區段(segment)組成的樹狀資料結構。在LEVEL=0的所有記錄的指標為讀取表單資料的記錄指標，在由根(root)至LEVEL=1的所有記錄則使用區段指標，區段指標包含4 bytes 的區段編號與2 bytes 的區段大小，用以搜尋下一層的區段，每一區段的記錄數量不大於32，如果大小為32，PC將此區段分裂成兩個區段，並修飾BRAM中的資料成為完整的B-tree。有兩種可能的情況來分割區段：（1）如果區段是根，此區段分裂成兩個區段，則新根的LEVEL增加1，並且新 根的區段包含兩筆記錄，分別指向分裂的兩個區段。（2）如果分裂的區段不是根，根的LEVEL不變，PC修飾BRAM中B-tree的鄰近資料成為完整的B-tree結構。4. 假設有m個PU(理論上，m可為任意正整數)，其中一個PU需進入休息狀態。假設比較k次，總共可搜尋到的資料為(m-1)k筆資料，現在的電腦沒有平行能力，使用Binary Search在每個B-tree結點(node)，比較k次，總共可搜尋到的資料為(2k)-1筆資料，如果k=3或4, 數種最好狀況搜尋到的資料總數比較於下： PC 3000PCsWaston 32PUs PHSD Method 128PUsPHSD Method 1024PUsPHSD Methodk=3 7 7*3000=21,000 (32-1)3=29,791 (128-1)3=2.0*106 (1024-1)3=1.07*109k=4 15 15*3000=45,000 (32-1)4=923,521 (128-1)4=2.6*108 (1024-1)4=1.09*1012Xilinx的kintex7可以設計為500 個PU 的PHSD。PHSD的最差情況的搜索總數量是 0.5 *最好情況的搜索總數量，PHSD的平均的搜索總數量是0.75 *最好情況的搜索總數量。擁有1000個PU的PHSD只要比較3次就可以搜索到十億筆記錄，只要比較4次即可搜索到一萬億筆記錄，並且PHSD的比較時間快軟體比較時間數十倍。32位元且有32個PU的PHSD其搜索能力優於含3000個處理器的Watson。5. PC可使用SQL軟體作簡單的資料庫運算如selection或重組記錄中的attributes。資料庫覆雜的運算中，兩個表單中任意兩筆記錄都要比較，PHSD可有效支援所有覆雜運算：利用B-tree搜尋處理Random Selection, Equijoin, Delete duplicates for Projection, Set operations (Union, Intersection and Difference) , Update operations (Insert, Delete and Update). 利用排序與merge處理Non-equijoin, Aggregate function over groups，Division則需使用前兩方式。大數據運算可彈性且快速處理machine learning所需的各種統計模型。 圖五、人工智慧電腦處理prolog智識庫6. 圖五中tidarray 為index file所建構的B_tree資料結構含function name與記錄指標陣列，由queries中的function name，可在 hornclause表單快速找到相關的智識，並且送到SWI-PROLOG軟體系統執行，個人電腦可因此具備人工智慧推理的功能。Patents:1. “Method of Implementing B++ Tree Search on Parallel Using Virtual Tree Structure.( 運用平行樹狀搜尋方法之虛擬樹搜尋器)” 美國發明專利: US7,596,551 B2. Sep. 29, 2009， 台灣發明專利: I353535。2. “A Parallel Hardware Search System for Building Artificial Intelligent Computer (一種用以建構人工智慧電腦之平行硬體搜索系統)” 美國發明專利: US9,384,449 B2, Jul. 5, 2016， 中國 CN 新型 Utility Model 專利號：ZL201320658123.5，台灣新型專利: TW M485443，中國與台灣發明專利申請中。3. “Use a Parallel Hardware Search Device to Implement Big Databases Efficiently.” 美國專利申請號:15/170,281.
請問若欲加入AI 創新或教師等研究研習活動，如何加入? 陳瑞陽老師
Follow
設計一個可真正平行的個人專用人工智慧電腦
回覆刪除電腦發明時，當時的人不知道電腦可當作打字機、音響、電話或可發展成國際網路。不過他們卻知道電腦可平行處理，而且未來是平行處理的天下。於是他們將兩台電腦放在一起，用軟體程式讓電腦通訊，平行處理各種運算。此方式產生的超級電腦單價高且CP值低，因此早期CDC、Cray computer...等超級電腦公司全部難逃破產命運，INTEL面對AMD 64 bit處理器競爭開始推出多核心共用記憶體結構電腦，卻沒有真正面對平行處理時Amdahl's law產生的問題，雲端可輕易擁有數十萬台電腦，然而系統效能卻取決於不可平行部分，不可平行部分為整個工作的5%時，Speedup<20，等於少於20台電腦平行運算，其他電腦都在睡覺。IBM深知多核心共用記憶體結構的侷限性，採用分散式系統發展雲端的WATSON。用相同的技術，Apple推出SIRI供手機用戶使用，Microsoft也推出Cortana給window用戶使用。
硬體的特質就是平行處理，大量的晶體與邏輯閘可同時平行工作，而軟體則是以依序處理為主，華盛頓大學系主任M. J. Quinn在其1998年著書中("Designing Efficient Algorithms for Parallel Computers"，Mcgraw-Hill )批評：研究者在共用記憶體中，假設沒有通訊與資料衝突問題是不切實際的，最後他總結：有效率的平行搜尋非常困難。解決此難題，本人認為雖然軟件是主導整個系統的要角，但是在執行平行處理時，軟體可以不要參與。換句話說，我們建議：平行處理時軟體下達開始執行一個平行處理的指令後，主導權轉交給硬體，硬體使用控制器與特殊硬體電路來執行並行處理，而不是使用軟體程式，完成平行指令後，硬體用interrupt訊號，將主導權交還給軟體，這樣的平行裝置可更簡單、更快速、且更可靠，電路不可平行度降至最低程度，可徹底解決Amdahl's law產生的問題。
圖一、 單核型許文龍電腦結構
圖一為單核心型的許文龍電腦結構，用PC及我們發明的平行硬體搜尋裝置(PHSD)來解決軟、硬體間的矛盾，由傳統PC下令後，純硬體搜尋器平行處理大數據，需要彈性的小數據則由傳統PC處理，硬體和軟體優點充分發揮，且避免彼此的弱點。此結構有幾個特點：
圖二、 OSI模型
1. 通訊不會造成問題：圖二為處理器間通訊用的OSI模型，大量的時間耗費在許多軟體層(layer)。PHSD的PU不支援軟體，所有的資料在物理層（physical layer)平行傳輸，因此通訊不會造成問題。
圖三、 Shift left/ right register chain
2. 沒有資料衝突問題：一般電腦叢集裏，電腦間必須相互借調資料，因此產生資料衝突問題。PHSD的PU都有自己的記憶體模組（BRAM module)，利用排序關係，巧妙地讓PU所需處理的資料全在自己的記憶體內，因此沒有資料衝突問題。硬體只有五個運算指令(fetch、store、search、insert和delete)，卻能處理電腦最重要的兩個運算：搜尋與排序，搜尋與人工智慧的推理有關，而排序可處理大數據運算。fetch、store、search明顯可以是真正平行運算，圖三為PU間的register chain，PUi將32bit由BRAMi傳至REGi，REGi值可同時送給鄰近的PUi-1和PUi+1，一個區塊的資料可向左或向右移動一個位置，因此insert和delete也是真正平行的運算，PU處理的資料全在自己的記憶體內，絕對沒有資料衝突問題。
圖四、將index file轉化成B-tree結構
3. 資料庫的記錄指標(record pointer) 含有4 bytes 的page number與2 bytes 的offset，用來讀取表單完整的資料，用以快速搜尋的Index file含有關鍵資料(key)與其記錄指標，可轉化成如圖四所示的B-tree並且建立於DRAM，B-tree為許多區段(segment)組成的樹狀資料結構。在LEVEL=0的所有記錄的指標為讀取表單資料的記錄指標，在由根(root)至LEVEL=1的所有記錄則使用區段指標，區段指標包含4 bytes 的區段編號與2 bytes 的區段大小，用以搜尋下一層的區段，每一區段的記錄數量不大於32，如果大小為32，PC將此區段分裂成兩個區段，並修飾BRAM中的資料成為完整的B-tree。有兩種可能的情況來分割區段：
（1）如果區段是根，此區段分裂成兩個區段，則新根的LEVEL增加1，並且新 根的區段包含兩筆記錄，分別指向分裂的兩個區段。
（2）如果分裂的區段不是根，根的LEVEL不變，PC修飾BRAM中B-tree的鄰近資料成為完整的B-tree結構。
4. 假設有m個PU(理論上，m可為任意正整數)，其中一個PU需進入休息狀態。假設比較k次，總共可搜尋到的資料為(m-1)k筆資料，現在的電腦沒有平行能力，使用Binary Search在每個B-tree結點(node)，比較k次，總共可搜尋到的資料為(2k)-1筆資料，如果k=3或4, 數種最好狀況搜尋到的資料總數比較於下：
PC 3000PCs
Waston 32PUs
PHSD Method 128PUs
PHSD Method 1024PUs
PHSD Method
k=3 7 7*3000=21,000 (32-1)3=29,791 (128-1)3=2.0*106 (1024-1)3=1.07*109
k=4 15 15*3000=45,000 (32-1)4=923,521 (128-1)4=2.6*108 (1024-1)4=1.09*1012
Xilinx的kintex7可以設計為500 個PU 的PHSD。PHSD的最差情況的搜索總數量是 0.5 *最好情況的搜索總數量，PHSD的平均的搜索總數量是0.75 *最好情況的搜索總數量。擁有1000個PU的PHSD只要比較3次就可以搜索到十億筆記錄，只要比較4次即可搜索到一萬億筆記錄，並且PHSD的比較時間快軟體比較時間數十倍。32位元且有32個PU的PHSD其搜索能力優於含3000個處理器的Watson。
5. PC可使用SQL軟體作簡單的資料庫運算如selection或重組記錄中的attributes。
資料庫覆雜的運算中，兩個表單中任意兩筆記錄都要比較，PHSD可有效支援所有覆雜運算：利用B-tree搜尋處理Random Selection, Equijoin, Delete duplicates for Projection, Set operations (Union, Intersection and Difference) , Update operations (Insert, Delete and Update). 利用排序與merge處理Non-equijoin, Aggregate function over groups，Division則需使用前兩方式。大數據運算可彈性且快速處理machine learning所需的各種統計模型。
圖五、人工智慧電腦處理prolog智識庫
6. 圖五中tidarray 為index file所建構的B_tree資料結構含function name與記錄指標陣列，由queries中的function name，可在 hornclause表單快速找到相關的智識，並且送到SWI-PROLOG軟體系統執行，個人電腦可因此具備人工智慧推理的功能。
Patents:
1. “Method of Implementing B++ Tree Search on Parallel Using Virtual Tree Structure.( 運用平行樹狀搜尋方法之虛擬樹搜尋器)” 美國發明專利: US7,596,551 B2. Sep. 29, 2009， 台灣發明專利: I353535。
2. “A Parallel Hardware Search System for Building Artificial Intelligent Computer (一種用以建構人工智慧電腦之平行硬體搜索系統)” 美國發明專利: US9,384,449 B2, Jul. 5, 2016， 中國 CN 新型 Utility Model 專利號：ZL201320658123.5，台灣新型專利: TW M485443，中國與台灣發明專利申請中。
3. “Use a Parallel Hardware Search Device to Implement Big Databases Efficiently.” 美國專利申請號:15/170,281.
請問若欲加入AI 創新或教師等研究研習活動，如何加入? 陳瑞陽老師
回覆刪除