Sunday, August 31, 2008

[Gtk] glade3

  • Glade Interface Designer
  • Download : Gtk-RanPass.zip

    在linux平台底下要做視窗程式設計多半會使用到Gtk或者是Qt,這裡介紹一個Gtk圖形化介面設計的輔助工具-glade。你可以透過下面的指令來安裝:

    • sudo apt-get install glade3

    為什麼我不用glade而選擇glade3?原因是因為我在glade裡開發的程式常常會出現跟我預期不同結果,有可能是我用build raw source code之後沒有好好設定的原因。而glade3雖然沒有內建build raw source code的功能,但我還是滿推薦使用它,至少目前為止我的小程式還沒出問題。安裝完後你會在Application->Programming裡會找到Glade Interface Designer。

    我概略的敘述Glade Interface Designer使用步驟,假設我的專案名稱叫做RanPass

    • 使用Glade Interface Designer設計一個介面
    • 設計完後存檔成RanPass.glade
    • 使用gtk-builder-convert將RanPass.glade轉成RanPass.xml,指令如下:

      gtk-builder-convert RanPass.glade RanPass.xml

    • 使用GtkBuilder相關函式來載入RanPass.xml,以及與你的程式功能結合編譯成圖形化介面

    光是上面四點的簡述你可能還是不知道如何下手,你可以參考下面的Tutorial來了解如何使用Glade Interface Designer:

    http://www.micahcarrick.com/12-24-2007/gtk-glade-tutorial-part-1.html

    另外這個網頁有完整的GTK+ Reference Manual

    http://library.gnome.org/devel/gtk/2.12/index.html

    Gtk圖形化開發環境本來就會比VB還要複雜一點,但如果你非常了解Gtk的語法,直接拋棄glade輔助設計會來的方便許多。glade3是一個滿新的套件,網路上這類的相關文件支援就相對較少,只能靠大家共同努力啦!

    #你可以下載我的Gtk-RanPass範例來編譯,我已經將基本的makefile寫好,裡面結合Password Generator的小功能,該有的註解也寫上了,或許這個小範例可以幫你了解到如何使用Gtk+glade。

    範例畫面如下:

    如果你不喜歡透過glade來處理UI的部份,那你可以下載下面沒有glade版的Password Generator

    Download: GGenPass.c

    透過下面的指令就可以編譯GGenPass.c了

    • gcc GGenPass.c -o GGenPass `pkg-config --cflags --libs gtk+-2.0`

    所以以小程式來講,自行設計也不是多大的負擔。

Saturday, August 30, 2008

[UTips. 52] Apache, PHP, MySQL, phpMyAdmin

  • Apache, PHP, MySQL, phpMyAdmin
  • 在ubuntu裡面要一次安裝這麼多套件其實是一件很簡單的事情,透過下面的指令你可以分別安裝Apache2, PHP5以及MySQL5

    • sudo apt-get install apache2
    • sudo apt-get install libapache2-mod-auth-mysql
    • sudo apt-get install mysql-server
    • sudo apt-get install php5
    • sudo apt-get install php5-mysql
  • Apache
  • Apache的設定檔位置預設在/etc/apache2/apache2.conf,關於apache2.conf的詳細訊息可以參考下面的網頁,裡面頁有提到之前介紹的OpenSSL。

    http://tech.seety.org/debian/ApacheConf.html#apache-apache2

    啟動Apache2

    • sudo /etc/init.d/apache2 start

    關閉Apache2

    • sudo /etc/init.d/apache2 stop
  • MySQL
  • 如果安裝過程中並沒有設定MySQL的root密碼,你可以透過下面的指令新增:

    • mysqladmin -u root password yourPassword

    啟動mysql

    • sudo /etc/init.d/mysql start

    關閉mysql

    • sudo /etc/init.d/mysql stop
  • PHP
  • PHP的設定檔位置在/etc/php5/apache2/php.ini,如果沒有特殊需求的話,安裝完即可正常使用,更改完畢之後請重新啟動apache。

    除此之外,如果你有用到mcrypt這個module,請透過以下指令安裝

    sudo apt-get install php5-mcrypt

  • phpMyAdmin
  • 這是一個圖形化MySQL管理工具,請到官方下載原始碼

    http://www.phpmyadmin.net/home_page/downloads.php

    解壓縮後將整個目錄放置/var/www裡,然後將phpMyAdminXXX這個資料夾裡的檔案重新命名:

    config.sample.inc.php

    改成

    config.inc.php

    接著編輯config.inc.php這個檔案,找到$cfg['blowfish_secret'] = ''; ,在''輸入任意英文字母,存檔案輸入以下網址在瀏覽器(假設你的資料夾名稱為phpMyAdmin)

    http://localhost/phpMyAdmin

    如果你能夠正常使用phpMyAdmin登入MySQL,那就設定完成了。

  • MySQL Query Browser
  • MySQL Query Browser是一個開發過程中的好用工具,你可以從官方下載原始馬來編譯:

    http://dev.mysql.com/downloads/gui-tools/5.0.html

    但是為了方便我們還是直接使用apt-get吧!

    • sudo apt-get install mysql-query-browser

    安裝完後在你的Application->Programming就會有MySQL Query Browser了。

Friday, August 29, 2008

[SSH/SSL] OpenSSL Programing : Connection

  • OpenSSL Programing : Connection
  • Linux: unix_openssl_conn.zip

    MinGW: mingw_openssl_conn.zip

    Visual C++ 2008: vc2k8_openssl_conn.zip

    繼這篇[SSH/SSL] Creating Certificate之後,我將三種環境的基本SSL連線程式給打包設定好,有需要的人下載對應的版本,裡面的程式範例是最簡易的,結合之前的[C/C++] Socket Connection在搭配OpenSSL而已,只是原先的 send()/recv()將會改由SSL_read()/SSL_write()來取代。

    流程架構如下:

    輸出範例畫面(linux):

    /*** Server ***/

    /*** Client ***/

    如此一來你就可以使用OpenSSL來加密你的通訊資料。

    #其中有爭議的是Visual C++2008的版本,我在編譯過程中出現ossl_typ.h裡175~177的程式碼有錯誤,我暫且先把他們給註解掉,初步判斷這是0.9.8h才有的功能,所以如果你有用到Online Certificate Status Protocol (OCSP)的功能,建議你把註解給放掉,然後想辦法解決啦!

[SSH/SSL] Creating Certificate

  • Creating Certificate
  • 建立憑證是OpenSSL Programming裡的一項重要的前置工作,這裡我介紹使用CA.pl來製做Server跟Client的憑證。

    製作憑證的一個簡單流程圖如上圖,概略描述如下:

    • 產生Self-Sigh Root CA 憑證中心
    • 產生Server的Private key
    • 使用Server的Certificate Request(csr)+CA的Private Key(簽名)來產生Server的Public Key
    • 產生Client的Private key
    • 使用Client的Certificate Request(csr)+CA的Private Key(簽名)來產生Client的Public Key
    • 最簡易的方式就是這五個步驟(如同圖上由CA.pl連出來的五條線)


    概略的了解這樣一個製作過程後,我以ubuntu為例來製作Certificate,如果你是透過apt-get來安裝openssl的話,你的CA.pl的路徑如下:

    • /usr/lib/ssl/misc/

    如果你是自行安裝OpenSSL,且沒有設定路徑的話,那你的CA.pl會在這裡

    • /usr/lcoal/ssl/misc


  • RootCA
  • 產生RootCA,請用以下指令

    • CA.pl -newca

    接著他會要你設定一組密碼給CA。再來你就依照螢幕指示輸入相關憑證訊息即可,要注意的是最後他會問你要不要設定Extra attributes,你就直接按Enter跳過。

    產生完後在你的openssl資料夾下,例如:

    • /usr/local/ssl/misc/demoCA

    裡面就會有分別以下目錄與資料

    • cacert.pem <-- CA的public key
    • private <-- CA的private key所在的資料夾
    • crl <-- Certificate Rovoke List (註銷的憑證清單目錄)
    • newcerts <-- CA所簽發過的憑證

    而一般OpenSSL Programming你會先用到的cacert.pem,其餘的之後使用到再說。如果你沒有要建立,ChildCA,那麼CA的建立就完成了(別忘了你的CA的密碼,之後簽發時要使用到)。

  • Server Key/Certificate
  • 產生Server的Private Key請輸入

    • CA.pl -newreq

    接著他會要你設定一組密碼給Server的Private key使用,接著你就按照螢幕上的指示去設定即可,最後的Extra attributes,你也直接按Enter跳過即可。

    產生完後會在你的openssl資料夾,例如

    • /usr/loca/ssl/misc/

    裡面會出現如下檔案:

    • newkey.pem <-- Server的Private Key
    • newcsr.pem <-- Server的Certificate Request

    有了Private Key和csr之後,我們要再建立Server的Public Key,輸入下面的指令

    • CA.pl -sign

    這時你就要輸入CA的密碼了,其餘皆按照螢幕指示操作即可,產生完後也會在剛剛那個目錄下多了一個檔案:

    • newcert.pem <--- Server的public key

    如此一來Server的Public & Private Key都產生好了,你可以把newcsr.pem刪除,然後把newkey.pem, newcert.pem重新命名完後移至別的資料夾裡保存。

  • Client Key/Certificate
  • Client的Key/Certificate產生方式跟Server一模一樣,因為不管你的憑證是要給Server還是Client,對rootCA而言,這些都是他的子層級,沒有任何差別。

    總結一下,產生完後你會有以下五個Programming必備的檔案

    • CaPuk.pem (CA的Public Key,由cacert.pem改命名而來)
    • SrvPrK.pem(Server的Private Key由產生Server的憑證過程時,將newkey.pem改名而來)
    • SrvPuK.pem(Server的Public Key由產生Server的憑證過程時,將newcert.pem改名而來)
    • CliPrK.pem(Client的Private Key由產生Client的憑證過程時,將newkey.pem改名而來)
    • CliPuK.pem(Client的Public Key由產生Client的憑證過程時,將newcert.pem改名而來)

    CaPuK.pem, SrvPuK.pem, SrvPrK.pem, CliPuK.pem, CliPrK.pem這五個檔案好好保存,在下一篇[SSH/SSL] OpenSSL Programing : Connection裡會用到。

    #關於Windows用戶如果無法使用CA.pl的使用者,你可以使用傳統建立憑證的指令來產生(先切換到openssl.exe所在的目錄底下,一般沒有設定的話會在c:\usr\local\ssl\bin):

    RootCA:

    • openssl genrsa -des3 -out ca.key 4096
    • openssl req -new -x509 -days 365 -key ca.key -out ca.crt

    Server:

    • openssl genrsa -des3 -out server.key 4096
    • openssl req -new -key server.key -out server.csr
    • openssl x509 -req -days 365 -in server.csr -CA ca.crt -CAkey ca.key -set_serial 01 -out serve

    Client:

    • openssl genrsa -des3 -out client.key 4096
    • openssl req -new -key client.key -out client.csr
    • openssl x509 -req -days 365 -in client.csr -CA ca.crt -CAkey ca.key -set_serial 01 -out serve

    雖然用傳統的方式要多打一些指令,但是同時你也可以發現你有比較多的參數可以設定,像是密碼的位元數,憑證的期限,以及加密的規格,再者透過上面的指令你更能了解憑證產生以及簽署的關聯。

[C/C++] Password Security Checking

  • Password Security Checking
  • Download:passSecurityChecking.c

    一支簡單的密碼安全檢測程式,裡面包括了以下不合格的檢測項目:

    • 密碼長度低於8
    • 密碼皆為數字
    • 連續字母超過4個以上
    • 相同字母連續超過3個以上
    • 特殊鍵盤碼

    在特殊pattern部份並沒有完全,另外還可以擴充檢查身份證字號格式,常用英文人名,常用英文單字,以及常用密碼組合等。

[C/C++] Random Password

  • Random Password
  • Download: ranpass.c

    提供一個簡單的密碼產生程式,RanPass()函式如下:

    參考輸出畫面如下:

[SSH/SSL] OpenSSL Installation

  • OpenSSL Installation
  • OpenSSL下載頁面如下:

    http://www.openssl.org/source/

  • Windows
  • 在windows底下我以Visual C++ 2008來做安裝範例,在安裝之前你要先裝ActivePerl,你可以到下面的頁面去下載:

    ActivePerl

    安裝完後你可以設定環境變數把perl/bin的目錄加到PATH裡面,或者你可以開啟cmd打上

    • set path=C:\Perl\bin

    接著設定Visual C++ Environment:

    • "C:\Program Files\Microsoft Visual Studio 9.0\VC\bin\vcvars32"

    將openssl解壓縮到c:\底下,進入openssl的資料夾

    • cd openssl-0.9.8h
    • perl configure VC-WIN32
    • ms\do_ms
    • nmake -f ms\ntdll.mak
    • nmake -f ms\ntdll.mak test
    • nmake -f ms\ntdll.mak install

    執行完上面的指令後,程式就會安裝至c:/usr/lcoal/ssl底下,裡面分別有bin, lib, include,這些都是openssl programming你會需要用到的。

    詳細訊息可以參考INSTALL.W32文件。

    如果你覺得自行編譯很困難,你也可以到下面的網站去下載已經編譯好的函式庫

    http://www.slproweb.com/products/Win32OpenSSL.html

  • Linux
  • Linux用戶一樣是使用上面的下載頁面的openssl原始碼,解壓縮後執行下面指令

    • ./config
    • make
    • make test
    • sudo make install

    安裝完後程式會在/usr/local/ssl,裡面的lib, include也是openssl programming需要用到的。

    詳細的訊息可以參考INSTALL這個文件。

    另外如果你是ubuntu類的linux,你可以直接打上下面的指令完成安裝openssl

    • sudo apt-get install openssl

    只是deb內的版本會比官方舊一點,同樣的,沒有特殊需求直接使用打包好的deb會方便許多。

Tuesday, August 26, 2008

[C.C++] Socket Programming: MultiPerson Chat

  • Socket Programming: MultiPerson Chat
  • Download: unix_multiperson_chat.zip

    沒想到才隔一天我就無聊到把Multiperson Chat程式給實做出來,當然還是得感謝Beej's Guide to Network Programming的selectserver.c範例,解決了我最苦惱的多人連線問題,也因此了解到fork(), pthread在socket programming裡的可行性部份。

    整個程式是以一個Server對多個Client的架構,而基礎程式依然是沿用[C/C++] Scoket Programming : Non-Blocking Communat裡的範例,而核心select()程式碼則是參照Beej的selectserver.c裡寫法。

    由於程式碼的邏輯環節還挺不單純的,所以請有興趣的人自行觀瞻啦!

    本程式我提供了下面的指令:

    • :n 更改名子
    • :t 更改聊天者
    • :i 查看自己的訊息
    • :? 說明支援
    • :q 離開

    因為是使用select()來達到多人連線的功能,自然程式的邏輯上就比較複雜一點點,也因此程式碼顯得很難看,且較不人性化,當然會這樣的原因也有可能是筆者我功力不足,還不是很了解socket programming的細節,所以產生這麼難看的程式碼。自然這整個程式裡仍然存在著許多要改善的地方,總之,這是個demo版,測試畫面如下:

    /*** Server *****/

    基本上Server除了重要訊息以外,能不顯示就不要顯示,以免造成負擔。

    /*** Client - xinyu ***/

    OK!我連上線了,第一步先取個名子。此時我要等待steven也上線,否則我要跟誰聊?(不好意思,這裡沒有實做誰已經上線了)。

    /*** Client - steven ***/

    Steven上線了,但是他設定完名子之後卻忘記要設定聊天者,但是這個時候xinyu已經把他設為聊天者並發送訊息過來(xinyu: hello),因為steven剛上線,且沒有聊天者,所以系統自動把他的聊天者設定為xinyu,steven可以透過輸入:t發現他的id為粉紅色,而xinyu為綠色。

    繼續聊天直到兩個人都下線時,Server上就會顯示如下的訊息:

    我想最起碼Server要顯示目前有多少人在線上。

    詳細的部份就請您自己編譯後玩玩看吧!

Monday, August 25, 2008

[C/C++] Scoket Programming : Non-Blocking Communation

  • Scoket Programming : Non-Blocking Communation
  • Download: unix_chat.zip

    現在大部分的設計師都比較少人去實做底層的功能,畢竟直接使用以成熟的API會比較方便。在Scoket Programming過程中,你可能會發現當A端send一些資料到B端時,這時如果B端沒有對應的recv去接收這些資料,A,B兩端將會無法正常工作下去,這就是所謂的阻塞式(Blocking)的傳輸,為了解決這樣的一個問題你可以加上一些timeout,讓程式不會永遠一直在等待接收或傳輸的資料,而在unix socket programming裡我們可以用select()這個函式來實現。這裡就以一個簡單的聊天程式作為範例,程式主架構沿用[C/C++] Socket Connection這一篇的基礎,因為是non-blocking 傳輸,所以我刻意讓Server跟Client都共用一個chat()函式,以方便修改,主要部份如下:

    進入一個無限的while loop之後先清空FD集合,以便做之後的監聽工作

    接著設定timeout的時間,並且開始等待

    如果等待的回傳值大於一,代表I/O上有動作,接著使用兩個if來判斷訊息的來源,如下:

    使用FD_ISSET來判斷資料的來源,再決定是要傳送出去還是列印在螢幕上。

    如此一來,non-blocking的設計就完成了,關於細部的select()資訊可以參考下面的網頁:

    http://linux.die.net/man/2/select

    因為程式是在terminal底下執行,為了讓文字好區別我同時也用了設定文字顏色的功能,這部份的資訊你可以參考[C/C++] Colour Terminal,另外關於聊天程式的設計你可能不解的是為什麼有一方會是Server來等待接收,而不是雙方都是Client?是因為這是展示版,所以並沒有實做得很完全,如果真的要達到類似即時通訊的架構,有一個Server然後多個Client連上Server後去做通訊,這時整個架構就需要改寫成Server有多個thread去處理多個Client間的通訊了,有時間我在把他實做出來吧!

[C/C++] Colour Terminal

  • Colour Terminal
  • 雖然現在的程式多以視窗為主,但是如果你很不幸的想要在terminal底下美化文字的顏色你可以用下面筆者我所寫好的函式來設定,這裡我針對兩個作業系統分別寫出簡易的setColor()的C函式,下載如下:

    For Linux:unixsetcolor.h

    For Windows:w32setcolor.h

    下面是一個簡易的使用範例:

    依照你的環境來載入對應的header file,然後在你要色彩化的文字前後分別呼叫setColor(),如果你沒有在第七行也呼叫setColor(WHITE),那你的文字會一直都是紅色,直到關閉terminal,或者改變其他顏色為止,關於顏色的定義請參照header file啦!至於unix底下細部的顏色資訊可以參考下面的網頁:

    http://www.pixelbeat.org/docs/terminal_colours/

Saturday, August 23, 2008

[C/C++] sleep

  • sleep
  • 在MutliThreading Programming裡sleep()會很常被使用到,為了要最佳化各個thread的效率,有些thread我們會視情況在裡面加上sleep()讓其他的thread獲得較高的CPU使用資源。而在linux底下的sleep函式是以秒為單位,範例程式如下:

    • sleep(5);

    上面就是讓terminal畫面停留五秒的程式指令,詳細的sleep指令資訊可以參考下面的網頁

    http://linux.die.net/man/3/sleep

    但是光只有秒的單位還不太夠用,如果要使用到微秒的函式就要使用到usleep(),範例如下:

    • usleep(1000000);

    上面的寫法可以讓程式暫停1秒。

Friday, August 22, 2008

[C/C++] Threads Limitation

  • Threads Limitation
  • Download :threadlimit.c

    在MultiThreading Programming裡一個很重要的議題就是Threads Limitation,究竟一個程式的最多可以分配多少個Threads?又一個Threads的Stack大小佔多少?該分配多少個Threads才能 將效能提到最高?這些問題都是程式設計師在做MultiThreading Programming感到痛苦的問題,往往為了要符合這些環境設定,程式的結構也因此被修改得很亂。底下是一個簡單的小程式用來測試你的電腦能開多少個 Threads:

    這裡我們預設最大thread數為10000,以及最大遞迴呼叫次數為100次,還有最大變數大小80K(8192*10=8192*1000/100)。我們的主程式如下:

    這是一個很基本的multithreading的程式,只是這裡使用了pthread_detach()來取代pthread_join(),以及pthread_attr_getstacksize()來取得stack的大小資訊(同樣的你也可以在terminal裡輸入ulimit -a看stack的資訊)。呼叫的函式如下:

    參考輸出結果:

    在我的測試電腦裡stack為8MB(2^23 bytes)上限,而我產生了第383個thread時則返回如上的錯誤,而383這個數字是怎麼來的,我概略算了一下。我的記憶體為2GB, SWAP:1GB,所以總共是3GB( 3*(2^30) bytes),所以理論上thread的數量會是:

    3*(2^30)/2^23 等於384(384是個概略值,你還得扣掉一些記憶體的消耗)。所以我的系統會在383的地方停止產生thread。

    如果你將原始碼裡的MAX_STACK_SIZE加大,你就會得到segmemtation fault,stack overflow的問題你可以參考這一篇[C/C++] Stack Overflow

  • 結論
    • 一個程式能跑多少個thread還得視程式所運行環境的記憶體大小)
    • 每個thread有各自的stack,一旦使用超過stack大小也會crash,但你可以透過pthread_setstack(), pthread_getstack()來修改stack大小,但同時你就得自行承擔記憶體錯誤的風險。
    • 一個程式有多少個thread效能才好,基本上thread的數量不宜多,一般來講最佳化的情況是在同一個時間內有同等於你的核心數量的thread,例如你是8核心cpu,那你的程式同時間使用8個thread的效果是最好的。

    當然MultiThreading程式的效能並不能單單就以threads的數量而定,因為在實際的設計案例中,每個thread的結束時間並不一定一樣(concurrent programming)自然有些thread必須去等待其他thread來做結合,所以有很大的機會你的MultiThreading的程式跑的比single threading程式還要慢。

    網路上有許多已經實做出來的Thread API,其中較具有名氣的OpenMP就是設計來提昇簡易的Parallel的程式效能,有機會我會再用幾篇來探討OpenMP。

[C/C++] Stack Overflow

  • Stack Overflow
  • Download : stackoverflow.c

    在程式設計過程中你可能會不免會遇到segmentation fault,這樣的錯誤訊息除了有可能是因為非法存取未定義的記憶體位址之外,另外也有可能是你的堆疊溢位,例如下面這一個例子:

    我的系統最大堆疊區塊為8MB,所以上面的程式一旦執行到func2()就會出現segmentation fault,程式執行到func1()時就已經佔用了超過4mb的stack空間,一旦函式進入func2()我們再宣告一個4mb的變數a,此時即會消耗掉超過8mb的stack空間,因此那傷眼的訊息segmentation fault就這麼出來了,為了解決這個問題,你可以透過下面的方式來處理:

    • dynamic memory allocation:
    • 使用動態記憶體配置的解決方式是一個最簡易的方法,你可以將原本的靜態變數a改成

      char *a = (char*)calloc(MAX_VAR_SIZE,sizeof(char));

      只是別忘了用完記得要釋放掉。

      free(a);

      如此一來每宣告一個a的變數,stack裡所消耗的空間就會從MAX_VAR_SIZE降到4bytes(指標的大小)。只是相對的動態記憶體配置就會比靜態配置多花一些時間。

    • ulimit
    • 如果想要加速運算的速度且又需要大的記憶體空間,這時你就必須修改系統的預設stack值,關於使用ulimit的方法你可以參考下面的網頁:

      http://www.ss64.com/bash/ulimit.html

      不特別強調ulimit的使用是因為一旦你變更了stack值之後,你的程式在其他系統上仍有crash的機會,除非你的程式需求只是單在某台電腦上做工程運算模擬。

    • MultiThreading
    • MultiThreading固然是一個方案,因為每個Thread都有自己的stack空間,且 thread跟thread之前是可以通訊,但前提是你必須要將你的程式劃分為concurrent和parallel,且要非常的清楚thread的內部意義,否則你的程式除了變得很慢之外,也有可能很不幸的又收到segmentation fault的訊息。

Wednesday, August 20, 2008

[C/C++] pthread-win32

  • pthread-win32
  • Download:pthread_win32.zip

    pthread這麼好用的一個API要是能夠在Windows底下執行也能開發那該有多好,感謝有人去做這個API的平台移植,現在你可以到下面這個網頁去下載pthread-win32,讓你在Windows環境底下也能使用pthread:

    http://sourceware.org/pthreads-win32/index.html

    筆者我自己在Windows底下使用Visual C++ 2008以及MinGW都成功開發pthread的程式,如果你不想自行去官方下載原始碼來編譯的話,你可以下載上面筆者我自己打包好的,裡面還有一個適用於MinGW編譯器的範例,我把編譯指令寫成makefile,你只需要make就可以編譯出一個叫做thread.exe的程式,這個程式預設是四個thread,所以如果你的CPU是四核心的話可以發揮到最大效能,我在Intel Q6600上面跑花了0.33秒(這個程式有經過最佳化)比起Visual C++ 2008經過最佳化後快了許多。

    關於MinGW的安裝方式你可以參考這一篇[GCC] GCC for Windows (MinGW/DEV-C++)

[C/C++] Multithreading Porgramming - pthread

  • Multithreading Porgramming
  • 之前才剛談過Process Programming現在就跳到Multithreading Programming會不會快了點,實際上現在很少人使用Process Programming,因為他除了要在複製一份記憶空間之外,彼此的Process也不容易通訊,縱使你透過vfork()可以一起共用記憶體,但是vfork()並不是做同步處理,他是先做child process才做parent process,這樣反而失去我們原先的Process Programming意圖。所以我們要開始轉戰到linux的pthread開發。

    [C/C++] Process Programming - fork()裡的範裡改寫成Multithreading的版本如下:

    Download:equThread.c

    首先你會看到我們多了一個結構體宣告,且solveEqu函式的型態也變了。

    他變成回傳void*以及接收void*,這樣的型態宣告是要應和pthread的呼叫,我們之後會看到,因為只能傳送一個變數(void* data),所以我把要處理的檔案宣告在一個結構體上EquData,傳送時只要傳整個結構體就OK。下面是main()的部份。

    19~20行我們分別宣告了要傳送的資料陣列以及pthread_t變數thread1,thread2,因為這裡我們只處理兩個 thead,所以只宣告兩個(你也可以用很多個thread)。

    24跟28行分別建立了一個thread,thread1是計算equation1,thread2是計算equation2,而pthread_create的詳細參數部份你可以參考下面的網頁:

    http://www.opengroup.org/onlinepubs/007908799/xsh/pthread_create.html

    30~31行是在等待thread處理完並且把他們給集結起來。

    上面的程式你可以透過下面得指令來編譯:

    gcc -o equThread equThread.c -lm -lpthread

    輸出結果就跟之前的Process Porgramming一樣,你也可以拿到不同核心上跑跑看,看看是否效能有提昇。

    基本的thread設計其實很簡單,但如果要考慮到許多thread的溝通與資源共用問題,那就比較複雜一點了。

Monday, August 18, 2008

[C/C++] Process Programming - fork()

  • Unix Process Programming - fork()
  • Download: Process.c

    這裡介紹最基本的Unix Programming - fork(),基於現在的電腦都是多核心之下,我們可以透過fork()來將程式的效能提升到CPU的極限,考慮一個雙核心CPU,我們用C來解兩個簡單的方程式。

    • y=x^2+(4/3)x+4/9
    • y=x^2+4x+16

    我將方程式定義成如下的形式,這裡我使用指標函式來實做解equation的函式

    如果不使用process programming你可能會這樣寫:

    solveEqu(equation1,&ans,10);
    printf("Ans for equation 1: %.2f\n",ans);
    solveEqu(equation2,&ans,10);
    printf("Ans for equation 2: %.2f\n",ans);

    很直觀的就是先解完equation1,然後再解equation2,但是使用fork(),之後程式將不再是循序的執行,而是同步運行,核心程式如下:

    我使用switch去處理fork()的回傳值,但是實際上你可以直接使用if去判斷回傳值是否如下:

    • -1 : fail to create process
    • 0 : child process
    • >0 : parent process

    而這裡我將solveEqu(equation1,&ans,10);放在default裡,實際上parent process的程式碼可以直接拉到switch case之外(也就是程式碼 29之後),在這個小範例裡要還要注意的是18行的exit(0),目的是要終止child process,以及27行的wait(NULL),意思是parnet process要等待child process處理好才繼續往下做(如果parent跑的比child快的話),輸出參考如下:

    And for equation 1: -0.67
    Ans for equation 2:4.00

    這裡只有用一個child process,所以整體最大效能不會超過200%,同時你也可以知道這兩個equation所需的時間也不一樣,自然整個程式不可能提升到200%的peak performance。這時你可能也會思考一個問題,假設我要一次處理多個process,那我的parent process只使用wait(NULL)就可以知道我要等哪個process嗎?這裡你就需要將程式碼改寫成如下的形式:

    waitpid() 可以指定要等待的child process,詳細的使用方式你可以參考下面的網頁

    http://man.he.net/man2/waitpid

    撰寫Process的程式要注意的是每一個Process他們會有各自的變數,例如我們的child process跟parent process都要使用到ans這個變數時,實際上在process運行過程中,他們各自複製了一份ans的變數來做處理,所以process programming通常使用於各自獨立的工作去分工,頂多將解出來的值做合併,但是你無法得知哪一個process會先做完,所以在做process programming時必須很小心的去分析你要分離的工作會不會影響到程式執行的結果。

Sunday, August 17, 2008

[ANN] Gaussian Random

  • Gaussian Random
  • Download: GaussianRandom.c

    一般在初始化網路的Weight和Bias值時我們通常會使用Gaussian Random來取代一般的Random函式,因為Gaussian Random的機率分佈曲線並不像一般的random函式一樣成水平狀,而是以中心向外遞減,如下圖(此圖是將GaussianRandom.c所產生的數據去作圖的):

    這樣的機率分佈狀況非常符合我們做初始化的需求,因為初始化的值往往會影響到結果,而Gaussian Random的值讓大部分的Weight值靠近0,讓收斂不完全的機率降至更低。

    核心程式碼如下:

    詳細的Gaussian Random資訊你可以參考下面的網頁

    http://www.bearcave.com/misl/misl_tech/wavelets/hurst/random.html

Tuesday, August 12, 2008

UTips. 51: gcj

  • gcj
  • Java的compiler除了可以使用eclipse,你可以使用gnu的gcj來編譯,下面是一個很簡單的程式碼:

    透過下面的指令來編譯:

    • gcj -c -g -O HelloJava.java
    • gcj --main=HelloJava -o HelloJava HelloJava.o

    雖然用gcj編譯出來的執行效率跟eclipse差不多,但是以開發的方便性來講,我還是比較推薦eclipse。

UTips, 50: eclipse

  • eclipse
  • 在Linux底下我比較推薦使用eclipse來做Java 的開發工具。

    • sudo apt-get install eclipse

    其實eclipse是跨平台的,在windows底下也可以使用eclipse。

Monday, August 11, 2008

[ANN] BackPropagation

  • BackPropagation
  • [ANN] Perceptron這一篇我們可以得知沒有隱藏層的Perceptron是無法解決XOR的問題,就算我們自行加了隱藏層也沒有對應的演算法去計算隱藏層的值,Paul Werbos於1974提出了BackPropagation Neural Network並解決隱藏層演算的問題。

    各參數意義如下:

    • X1,X2 :輸入層,兩個inputs
    • H1,H2 :隱藏層,兩個hidden nodes
    • Y:輸出層,一個output
    • thetaxh1,thetaxh2 :隱藏層的bias
    • thetahy:輸出層的bias

    而使用BackPropagation的網路時通常會搭配著以下兩種Transfer Function:

    • Sigmoid:
    • Hyperbolic Tangent:

    網路計算公式如下:

    如過算出的Y值沒又達到目標值,我們必須計算delta以及更新Weight跟Bias

    delta的計算公式如下:

    計算weight值


    計算Bias值

    更新所有的weight和bias

    重複上述的運算直到收斂到目標值為止,依據上述的公式我分別使用了C,Java,Perl來實做BackPropagation

    Download: BackPropagation.c BackPropagation.java BackPropagation.pl

    除了可以比較運行的速度之外,也可以探討精準度,速度方面當然是c語言佔上風,但是精準度卻沒有Java跟Perl,詳細的資料你可以參考下面的網頁。

    http://www.adahome.com/History/Steelman/steeltab.htm

    在學習速率方面筆者我並沒有讓他們給固定,我使用了下面這行程是碼:

    這裡我只是簡單的利用到二次曲線去變動學習速率,而變動依據則是按照目標差距值而定。只是這樣的修改方式並沒有什麼根據,比較好的動態學習速率應該依照DBD,EXDBD或者weight值得觀察來變動,這部份詳細訊息我們之後再來探討。


    關於誤差計算方式我則是使用RMSE

    當然你可以使用其他方式去計算誤差,RMSE在這個範例裡並不是那麼的重要。輸出畫面如下:

    以學習速率0.1為基準,在c語言版本下我們花了0.024秒,算了4000多個epoch之後得到我們的RMSE在0.1以內的解。結果可以說是相當不錯。當然還是有幾個問題需要探討。在多次測試下你可能會發現有時後會收斂不完全,這些問題筆者我會在之後逐一去講解。

[ANN] Perceptron

  • Artificial Neural Network (ANN)
  • 在人工智慧的領域裡Artificial Neural Network(ANN)扮演著一個很重要的角色,他是一個基於大腦神經元的架構而構成的人工類神經網路,廣泛應用在電機、資訊、醫學、環境、商業等等各領域上。

    而依造類神經網路學習的類別可分為:

    1. Supervised learning - 監督式學習
    2. Unsupervised learning - 非監督式學習
    3. Reinforcement learning - 增強式學習

    依造所要解決的問題環境不同而選擇對應的學習網路,基本的ANN資訊你可以參考wikipedia。

    http://en.wikipedia.org/wiki/Neural_network#Real_life_applications

  • Perceptron
  • 於1957年Frank Rosenblatt.在康乃爾航空實驗室時期所發表的類神經網路學習模式,是屬於監督行網路,圖形定義如下:

    將這些節點寫成數學式如下:


    x1,x2是我們的input, y1是我們的output(這只是最簡易的範例,你的input,output數量會隨著你要解決的問題而定),我們還有三個參數要控制,分別為 w1,w3,theta,也就是所謂的加權職(weight)以及Bias。要計算修改weight跟bias的值我們必須基於兩個參數,eta(學習速率)和delta(差距向量),公式如下:

    其中T代表著目標值。

    計算deltaWight並更新新的weight值。

    計算並更新新的bias值。

    根據上述的公式我們可以用程式語言去實做一個Perceptron學習模式來解決AND,OR的邏輯問題。

    Download:perceptron.c

    為了執行效率我選擇c語言來撰寫,程式碼並沒有經過最佳化,如此比較方便做公式的對照。以OR為例,input,output如下:

    • x1=0 x2=0 y=0
    • x1=0 x2=1 y=1
    • x1=1 x2=0 y=1
    • x1=1 x2=1 y=1

    我們以0.1的學習速率去跑這個程式,結果如下(僅供參考,不同的Weight初始值會有不同的解)

    經過三個epoch之後我們的perceptron已經完全學到OR的pattern,你可以將目標輸出改成AND的輸出,或者更改學習速率以觀察輸出結果。

    將perceptron的線性方程式畫在座標上類似如下。

    由圖形我們可以得知weight影響著此方程式的斜率,而bias決定著這條線離原點的距離,同時你也可以了解到bias一定介於0~0.707 (也就是根號2再除以2),如果你要再加上如下一組pattern

    • x1=-1 x2=1 y=1

    由圖形我們可以輕易的得知這是可行的,同理你也可以將上面的資料改成如下:

    • x1=1 x2=-1 y=1

    所以你絕對不可能使用這個model找到可以同時滿足下面情況的解:

    • x1=-1 x2=1 y=1
    • x1=1 x2=-1 y=1

    這時你也許也發現到這個model是不能解XOR的問題,不具隱藏層的Perceptron是不能解XOR的問題,下一次我會介紹Back-Propagation Neural Network並用它來解XOR問題。